高级密码学复习番外篇
【扯蛋证明】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语义安全性思路简单证明。