安全参数
1
n
1^n
1
n
-
算法及复杂度理论中，算法的运行时间为输入长度(数据规模)的函数，因此把安全参数表示为
1n
1^n
1
n
的形式，也就是一个长度为
nn
n
的全一串，用它代表安全参数，提供给攻防双方作为输入参数(它们使用的算法以
1n
1^n
1
n
为输入应该在多项式时间内运行完毕)
可忽略函数
n
e
g
l
negl
n
e
g
l
- 定义
∀
p
(
⋅
)
,
∃
N
,
s
t
.
∀
n
>
N
,
f
(
n
)
<
1
p
(
n
)
,
f
(
n
)
i
s
n
e
g
l
i
g
i
b
l
e
\forall p(\cdot), \exist N, st. \forall n \gt N, f(n) \lt \frac{1}{p(n)}, \quad f(n) \quad is \quad negligible
∀
p
(
⋅
)
,
∃
N
,
s
t
.
∀
n
>
N
,
f
(
n
)
<
p
(
n
)
1
,
f
(
n
)
i
s
n
e
g
l
i
g
i
b
l
e
-
推论
-
ne
g
l
3
(
n
)
=
n
e
g
l
1
(
n
)
+
n
e
g
l
2
(
n
)
negl_3(n) = negl_1(n) + negl_2(n)
n
e
g
l
3
(
n
)
=
n
e
g
l
1
(
n
)
+
n
e
g
l
2
(
n
)
可忽略 -
ne
g
l
4
(
n
)
=
p
(
n
)
∗
n
e
g
l
1
(
n
)
negl_4(n) = p(n) * negl_1(n)
n
e
g
l
4
(
n
)
=
p
(
n
)
∗
n
e
g
l
1
(
n
)
可忽略
-
私钥加密方案
(
G
e
n
,
E
n
c
,
D
e
c
)
(Gen, Enc, Dec)
(
G
e
n
,
E
n
c
,
D
e
c
)
-
定义
-
Ge
n
Gen
G
e
n
以安全参数
1n
1^n
1
n
为输入，输出密钥
kk
k
，记作
k←
G
e
n
k \leftarrow Gen
k
←
G
e
n
(”
←\leftarrow
←
“强调其是一个随机算法)，并不失一般性的假设
∣k
∣
≥
n
|k| \ge n
∣
k
∣
≥
n
-
En
c
Enc
E
n
c
以密钥
kk
k
和明文
m∈
{
0
,
1
}
∗
m \in \{0, 1\}^*
m
∈
{
0
,
1
}
∗
(注意此处明文可以是任意长度)为输入，输出密文
cc
c
。因为
En
c
Enc
E
n
c
可能是一个随机算法，所以将其记为
c←
E
n
c
k
(
m
)
c \leftarrow Enc_k(m)
c
←
E
n
c
k
(
m
)
(注意没有使用
c:
=
E
n
c
k
(
m
)
c := Enc_k(m)
c
:
=
E
n
c
k
(
m
)
，这强调了
En
c
Enc
E
n
c
可能是随机算法) -
De
c
Dec
D
e
c
以密钥
kk
k
和密文
cc
c
为输入，输出明文
mm
m
。不失一般性的，
De
c
Dec
D
e
c
被假设为确定算法，因此记作
m:
=
D
e
c
k
(
c
)
m := Dec_k(c)
m
:
=
D
e
c
k
(
c
)
-
-
基本正确性要求
D
e
c
k
(
E
n
c
k
(
m
)
)
=
m
,
∀
n
,
∀
k
,
∀
m
Dec_k(Enc_k(m)) = m, \forall n, \forall k, \forall m
D
e
c
k
(
E
n
c
k
(
m
)
)
=
m
,
∀
n
,
∀
k
,
∀
m
-
定长私钥加密方案
当对明文长度有要求时，即
m∈
{
0
,
1
}
l
(
n
)
m \in \{0, 1\}^{l(n)}
m
∈
{
0
,
1
}
l
(
n
)
，称为定长私钥加密方案，其具有长度参数
l(
n
)
l(n)
l
(
n
)
窃听不可区分实验
P
r
i
v
K
A
,
Π
e
a
v
(
n
)
PrivK_{\Alpha, \Pi}^{eav}(n)
P
r
i
v
K
A
,
Π
e
a
v
(
n
)
-
定义
-
给敌手
A\Alpha
A
指定
1n
1^n
1
n
作为输入，(敌手在多项式时间内)输出一对等长的消息
m0
,
m
1
m_0, m_1
m
0
,
m
1
-
产生随机密钥
k←
G
e
n
(
1
n
)
k \leftarrow Gen(1^n)
k
←
G
e
n
(
1
n
)
，随机选择一个比特
b←
{
0
,
1
}
b \leftarrow \{0, 1\}
b
←
{
0
,
1
}
，计算密文
c←
E
n
c
k
(
m
b
)
c \leftarrow Enc_k(m_b)
c
←
E
n
c
k
(
m
b
)
并交给
A\Alpha
A
-
A\Alpha
A
输出一个比特
b′
b^{\\’}
b
′
-
如果
b′
=
b
b^{\\’} = b
b
′
=
b
，则实验输出为
11
1
，否则为
00
0
。如果
Pr
i
v
K
A
,
Π
e
a
v
(
n
)
=
1
PrivK_{\Alpha, \Pi}^{eav}(n) = 1
P
r
i
v
K
A
,
Π
e
a
v
(
n
)
=
1
，则称敌手成功。
-
给敌手
窃听者存在下的不可区分性
- 定义
P
r
[
P
r
i
v
A
,
Π
e
a
v
(
n
)
=
1
]
≤
1
2
+
n
e
g
l
(
n
)
Pr[Priv_{\Alpha, \Pi}^{eav}(n) = 1] \le \frac{1}{2} + negl(n)
P
r
[
P
r
i
v
A
,
Π
e
a
v
(
n
)
=
1
]
≤
2
1
+
n
e
g
l
(
n
)
-
理解
在窃听不可区分实验中，敌手成功的概率中，多于
12
\frac{1}{2}
2
1
的部分是可忽略的
窃听者存在下的不可区分性等价定义
- 定义
∣
P
r
[
o
u
t
p
u
t
(
P
r
i
v
A
,
Π
e
a
v
(
n
,
0
)
)
=
1
]
−
P
r
[
o
u
t
p
u
t
(
P
r
i
v
A
,
Π
e
a
v
(
n
,
1
)
)
=
1
]
∣
≤
n
e
g
l
(
n
)
|Pr[output(Priv_{\Alpha, \Pi}^{eav}(n, 0)) = 1] – Pr[output(Priv_{\Alpha, \Pi}^{eav}(n, 1)) = 1]| \le negl(n)
∣
P
r
[
o
u
t
p
u
t
(
P
r
i
v
A
,
Π
e
a
v
(
n
,
0
)
)
=
1
]
−
P
r
[
o
u
t
p
u
t
(
P
r
i
v
A
,
Π
e
a
v
(
n
,
1
)
)
=
1
]
∣
≤
n
e
g
l
(
n
)
-
理解
在窃听不可区分实验中，当选择
b=
0
b = 0
b
=
0
时，敌手输出
b′
=
1
b^{\\’} = 1
b
′
=
1
的概率，和
b=
1
b = 1
b
=
1
时，敌手输出
b′
=
1
b^{\\’} = 1
b
′
=
1
的概率差是可忽略的
窃听者存在下的语义安全
- 定义
∣
P
r
[
A
(
1
n
,
E
n
c
k
(
m
)
,
h
(
m
)
)
=
f
(
m
)
]
−
P
r
[
A
′
(
1
n
,
h
(
m
)
)
=
f
(
m
)
]
∣
≤
n
e
g
l
(
n
)
|Pr[\Alpha(1^n, Enc_k(m), h(m)) = f(m)] – Pr[\Alpha^{\\’}(1^n, h(m)) = f(m)]| \le negl(n)
∣
P
r
[
A
(
1
n
,
E
n
c
k
(
m
)
,
h
(
m
)
)
=
f
(
m
)
]
−
P
r
[
A
′
(
1
n
,
h
(
m
)
)
=
f
(
m
)
]
∣
≤
n
e
g
l
(
n
)
-
理解
对于得到和未得到密文的攻击者，利用已知的明文相关信息，可获得的其他明文信息是几乎一样的；
也就是说，密文没有泄露有关明文的任何信息