A
\mathcal{A}
A选择两个长度相同、内容不同明文
m
0
,
m
1
m_0, m_1
m0?,m1?,并发送给
C
\mathcal{C}
C;
C
\mathcal{C}
C根据密钥生成算法生成一个新密钥
k
k
k,随机生成一个比特
b
b
b并挑选一个明文
m
b
m_b
mb?,加密
E
n
c
k
(
m
b
)
\mathsf{Enc}_k(m_b)
Enck?(mb?)后得到挑战密文
c
c
c,并发送给
A
\mathcal{A}
A;
A
\mathcal{A}
A输出对所加密明文的猜测
b
′
b'
b′,若
b
=
b
′
b=b'
b=b′,则
A
\mathcal{A}
A成功;否则,失败;
关于明文的信息用明文的函数来表示,
h
(
m
)
h(m)
h(m)表示敌手预先了解的关于明文的外部信息,
f
(
m
)
f(m)
f(m)表示敌手希望获取的关于明文的有意义的信息
定义:加密方案是窃听者出现时语义安全的,如果对于任意敌手,任意明文分布,任意函数
f
f
f和
h
h
h,一个敌手根据密文和
h
(
m
)
h(m)
h(m)获得
f
(
m
)
f(m)
f(m),另一个敌手只根据
h
(
m
)
h(m)
h(m)获得
f
(
m
)
f(m)
f(m),这两个敌手成功的概率之间的差异是可以忽略的
一个确定性的多项式时间算法
G
:
{
0
,
1
}
n
→
{
0
,
1
}
?
(
n
)
G : \{0,1\}^n \to \{0,1\}^{\ell(n)}
G:{0,1}n→{0,1}?(n)是一个伪随机生成器(PRG),如果:
延展:
?
n
,
?
(
n
)
>
n
\forall n, \ell(n) > n
?n,?(n)>n。只有生成更长的串才有意义,否则可以直接从种子中复制一段输出;
伪随机:对于任意PPT区分器
D
D
D,
∣
Pr
?
[
D
(
r
)
=
1
]
?
Pr
?
[
D
(
G
(
s
)
)
=
1
]
∣
≤
n
e
g
l
(
n
)
\left|\Pr[D(r)=1] - \Pr[D(G(s))=1]\right| \le \mathsf{negl}(n)
∣Pr[D(r)=1]?Pr[D(G(s))=1]∣≤negl(n)。其中,
r
r
r是随机的,种子
s
s
s随机的,
?
(
?
)
\ell(\cdot)
?(?)是延展因子。这里的意思是输出不同结果的概率差可以忽略,如果有一个区分器始终输出1,则两个概率都是1,差为0;另外,输出1并不需要表示特定含义,改成输出0也可以。
存在性:若单向函数存在或
P
≠
N
P
\mathcal{P} \ne \mathcal{NP}
P=NP,则PRG存在。后面我们会进一步学习。
将解决“假设”
X
X
X问题的算法
A
′
\mathcal{A}'
A′规约到“破解”
Π
\Pi
Π的算法
A
\mathcal{A}
A。如果加密方案可以被破解,则假设问题也可以解决。然而,由于假设问题是难以解决的,这导致矛盾,说明加密方案不可以被破解。
先令一个概率多项式时间的算法
A
\mathcal{A}
A能够以概率
ε
(
n
)
\varepsilon(n)
ε(n)破解
Π
\Pi
Π ;
假设:一个问题
X
X
X是难以解决的,即不存在多项式时间算法来解决
X
X
X;
A
′
\mathcal{A}'
A′是一个解决
X
X
X的概率算法;
规约:解决假设问题
X
X
X可以通过破解加密方案
Π
\Pi
Π,即将
A
′
\mathcal{A}'
A′规约到
A
\mathcal{A}
A,
A
′
\mathcal{A}'
A′通过以
A
\mathcal{A}
A作为子函数可以以概率
1
/
p
(
n
)
1/p(n)
1/p(n)有效地解决问题
X
X
X;
矛盾:若加密方案可以被有效破解,即
ε
(
n
)
\varepsilon(n)
ε(n)是不可忽略的,则
A
′
\mathcal{A}'
A′可以以不可忽略的概率
ε
(
n
)
/
p
(
n
)
\varepsilon(n)/p(n)
ε(n)/p(n)解决问题
X
X
X,这与假设矛盾,因而
ε
(
n
)
\varepsilon(n)
ε(n)一定是可忽略的。
一个规约法证明PRG的例子
假设
F
F
F是PRG,证明
G
G
G也是PRG。
问题A:如何区分
F
F
F;问题B:如何区分
G
G
G;
从A规约到B:区分
F
F
F的算法输入按位取反后作为区分
G
G
G的算法输入,区分
G
G
G的算法输出作为区分
F
F
F的算法输出。
一个规约法证明PRG的例子(续)
由此,建立了不可区分定义中概率的联系。
构造安全的加密方案
一个安全的定长加密方案
∣
G
(
k
)
∣
=
?
(
∣
k
∣
)
|G(k)| = \ell(|k|)
∣G(k)∣=?(∣k∣),
m
∈
{
0
,
1
}
?
(
n
)
m \in \{0,1\}^{\ell(n)}
m∈{0,1}?(n), 一个PRG以长度为
n
n
n的密钥作为种子,输出与明文相同长度的pad;
G
e
n
\mathsf{Gen}
Gen:
k
∈
{
0
,
1
}
n
k \in \{0,1\}^n
k∈{0,1}n,密钥作为种子,长度小于明文长度;
E
n
c
\mathsf{Enc}
Enc:
c
:
=
G
(
k
)
⊕
m
c := G(k)\oplus m
c:=G(k)⊕m,加密方法和一次一密一样;
D
e
c
\mathsf{Dec}
Dec:
m
:
=
G
(
k
)
⊕
c
m := G(k)\oplus c
m:=G(k)⊕c,解密也是;
思路:区分伪随机性为难题假设,破解加密方案为规约的子函数。针对伪随机生成器
G
G
G的区分器
D
D
D以
A
\mathcal{A}
A为子函数,使得当
A
\mathcal{A}
A破解了
Π
\Pi
Π则
D
D
D可以区分出
G
G
G,与
G
G
G的伪随机性矛盾。注意这里我们用了符号
Π
~
\tilde{\Pi}
Π~来表示
Π
\Pi
Π的一个变体,来刻画加密方案中可能使用了真随机串来加密;
回顾针对伪随机生成器的区分器
D
D
D的问题是,输入一个串
w
w
w,输出一个比特;这里关键问题是输出的比特从何而来?
将
D
D
D规约到
A
\mathcal{A}
A。回顾窃听者不可区分实验中,
A
\mathcal{A}
A与一个挑战者进行3轮交互:
A
\mathcal{A}
A选择两个不同明文
m
0
,
m
1
m_0, m_1
m0?,m1?,并发送给挑战者;
挑战者生成密钥,并随机挑选一个明文
m
b
m_b
mb?加密后得到挑战密文
c
c
c,并发送给
A
\mathcal{A}
A;
A
\mathcal{A}
A输出对所加密明文的猜测
b
′
b'
b′,若
b
=
b
′
b=b'
b=b′,则
A
\mathcal{A}
A成功;否则,失败;
区分器
D
D
D成为窃听不可区分实验中的挑战者,特别之处在于:在第2步,不需要生成密钥,而是直接以输入串
w
w
w作为pad来加密,
c
:
=
w
⊕
m
b
c := w \oplus m_b
c:=w⊕mb?;根据
w
w
w的两种可能,分两种情况:
当
w
w
w是由
G
G
G生成的,即伪随机串,则
c
c
c就是加密方案
Π
\Pi
Π中密文,
A
\mathcal{A}
A面对的就是
Π
\Pi
Π;
当
w
w
w是真随机串,则
c
c
c不同于加密方案
Π
\Pi
Π中密文,而与一次一密中一样,
A
\mathcal{A}
A面对的就是
Π
~
\tilde{\Pi}
Π~一次一密;
回答前面关于
D
D
D输出什么的问题:破解加密方案的
A
\mathcal{A}
A成功时,
D
D
D输出1;否则,
D
D
D输出0。
证明不可区分加密方案(续)
规约完毕,证明
A
\mathcal{A}
A在实验中成功的概率是可忽略的
当
w
w
w为真随机串
r
r
r,就是一次一密,
Pr
?
[
D
(
r
)
=
1
]
=
Pr
?
[
P
r
i
v
K
A
,
Π
~
e
a
v
(
n
)
=
1
]
=
1
2
\Pr[D(r)=1] = \Pr[\mathsf{PrivK}^{\mathsf{eav}}_{\mathcal{A},\tilde{\Pi}}(n)=1]=\frac{1}{2}
Pr[D(r)=1]=Pr[PrivKA,Π~eav?(n)=1]=21?;
当
w
w
w为伪随机串
G
(
k
)
G(k)
G(k),
Pr
?
[
D
(
G
(
k
)
)
=
1
]
=
Pr
?
[
P
r
i
v
K
A
,
Π
e
a
v
(
n
)
=
1
]
=
1
2
+
ε
(
n
)
\Pr[D(G(k))=1] = \Pr[\mathsf{PrivK}^{\mathsf{eav}}_{\mathcal{A},\Pi}(n)=1] = \frac{1}{2} + \varepsilon(n)
Pr[D(G(k))=1]=Pr[PrivKA,Πeav?(n)=1]=21?+ε(n);
根据伪随机生成器定义,上下两个公式相减,
∣
Pr
?
[
D
(
r
)
=
1
]
?
Pr
?
[
D
(
G
(
k
)
)
=
1
]
∣
=
ε
(
n
)
≤
n
e
g
l
(
n
)
\left|\Pr[D(r)=1] - \Pr[D(G(k))=1]\right| = \varepsilon(n) \le \mathsf{negl}(n)
∣Pr[D(r)=1]?Pr[D(G(k))=1]∣=ε(n)≤negl(n);
所以
ε
(
n
)
\varepsilon(n)
ε(n)是可忽略的,即
Π
\Pi
Π是窃听者不可区分的。
小结:通过规约将
A
\mathcal{A}
A的不可区分实验成功的概率与
D
D
D的区分器实验输出1的概率建立等式;分析输入真随机串时
D
D
D输出1的概率(即不可区分实验成功概率)是1/2;根据PRG的定义,输入伪随机串时
D
D
D输出1的概率(1/2+
ε
(
n
)
\varepsilon(n)
ε(n))与输入真随机串时
D
D
D输出1的概率(1/2)的差异时可忽略的。