高级密码学复习番外篇
【扯蛋证明】FE和HE不满足语义安全
1、PKE语义安全性证明
A
—
—
m
0
,
m
1
⟶
C
⟵
c
b
,
b
=
0
/
1
—
—
—
—
g
u
e
s
s
b
=
0
/
1
→
A —— m_0,m_1longrightarrow C \ longleftarrow c_b ,b=0/1—— \ —— guess b=0/1 rightarrow
A —— m0,m1⟶C⟵cb,b=0/1———— guess b=0/1→
首先强调公钥加密的两个特点：正确性、语义安全性
1）正确性。公钥和私钥相对应，明文在经过加解密之后恢复正确。
2）语义安全性。相同的明文经过相同的公钥加密之后，会得到不同的密文,同时也可以使用相同的私钥进行解密。根据密文，攻击者无法判断明文任意比特的信息。
2、用PKE语义安全性证明思路不能证明FE的语义安全性
A
—
—
m
0
,
m
1
⟶
C
←
c
b
,
b
=
0
,
1
—
—
A
k
n
o
w
n
d
f
k
1
、
d
f
k
ϵ
、
f
k
1
A——m_0,m_1longrightarrow C\ leftarrow c_b,b=0,1—— \ A known df_{k_1}、df_{k_epsilon}、f_{k_1}
A——m0,m1⟶C←cb,b=0,1——A known dfk1、dfkϵ、fk1
**定义攻击者的已知能力：**此时根据FE函数加密的特性，用户已知至少两个私钥
d
f
k
1
和
d
f
k
ϵ
large df_{k_1} 和df_{k_epsilon}
dfk1和dfkϵ，当让用户也知道
f
k
1
large f_{k_{1}}
fk1。此处定义攻击者的能力具备一般用户的能力。
破解b的方法：使用
d
f
k
ϵ
large df_{k_epsilon}
dfkϵ可以得到密文的长度，使用
d
f
k
1
large df_{k_1}
dfk1进行解密能够得到
f
1
(
m
b
)
f_{1}(m_b)
f1(mb),与
f
1
(
m
0
)
，
f
1
(
m
1
)
f_1(m_0)，f_1(m_1)
f1(m0)，f1(m1)进行比较，即可推出b。
FE的语义安全性有属于他自己的证明方式，不能用PKE语义安全性思路简单证明。
3、用PKE语义安全性证明思路，证明HE不满足语义安全性的错误思路
A
—
—
m
0
,
m
1
⟶
C
←
c
b
,
b
=
0
,
1
—
—
A
k
n
o
w
n
p
k
,
m
1
=
f
(
m
0
)
,
t
h
e
h
o
m
o
m
o
r
p
h
i
s
m
o
f
t
h
e
E
n
c
A——m_0,m_1longrightarrow C\ leftarrow c_b,b=0,1—— \ A known pk,m_1=f(m_0), the homomorphism of the Enc
A——m0,m1⟶C←cb,b=0,1——A known pk,m1=f(m0),the homomorphism of the Enc
**定义攻击者的已知能力：**此时根据HE函数加密的特性，用户已知Enc加密函数具有的同态特征，攻击者具备一般用户的的能力之外，由于公钥加密中C使用的公钥和加密算法也是公开的，所以这些也可以被攻击者所知。
破解b的方法： A可以计算出
c
0
和
c
1
c_0和c_1
c0和c1，由PKE的语义安全性可以知道，
c
0
和
c
1
c_0和c_1
c0和c1对安全性并不造成威胁，因为加密中使用了随机数，使得每次加密的密文都不同；但在同态加密的环境下，情况就会发生改变。
假设Enc加密方法使用paillier Encryption，支持的同态性：
E
n
c
(
m
1
)
m
2
=
E
n
c
(
m
1
⋅
m
2
)
、
E
n
c
(
m
1
)
k
=
E
n
c
(
m
1
⋅
k
)
Enc(m_1)^{m_2}=Enc(m_1·m_2)、Enc(m_1)^k=Enc(m_1·k)
Enc(m1)m2=Enc(m1⋅m2)、Enc(m1)k=Enc(m1⋅k)
攻击者可以构造
m
1
=
4
m
0
m_1=4m_0
m1=4m0,根据同态性，可以知道
E
n
c
(
m
0
)
4
=
E
n
c
(
m
1
)
Enc(m_0)^4=Enc(m_1)
Enc(m0)4=Enc(m1),那么如果
b
=
0
b=0
b=0时，我们可以利用
c
b
4
是
否
等
于
c
1
{c_b}^{4}是否等于c_1
cb4是否等于c1来判断
b
=
0
b=0
b=0；反之，则可以推断出
b
=
1
b=1
b=1。
**错误的原因：**上述证明， 是存在一个问题的。上述描述的加密支持的同态性在密文形态下是不满足的，只有在解密、消除随机数之后才能成立，比如说
E
n
c
(
m
0
)
4
=
E
n
c
(
m
1
)
Enc(m_0)^4=Enc(m_1)
Enc(m0)4=Enc(m1)，应该写成
D
e
c
(
E
n
c
(
m
0
)
4
)
=
=
D
e
c
(
E
n
c
(
m
1
)
)
=
m
1
Dec(Enc(m_0)^4)==Dec(Enc(m_1))=m_1
Dec(Enc(m0)4)==Dec(Enc(m1))=m1我们应该是并不能比较
c
b
4
是
否
等
于
c
1
{c_b}^4是否等于c_1
cb4是否等于c1来判断b的取值的。
HE的语义安全性有属于他自己的证明方式，不能用PKE语义安全性思路简单证明。