【扯蛋证明】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_1\longrightarrow 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_1\longrightarrow 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_1\longrightarrow 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
cb?4是否等于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
cb?4是否等于c1?来判断b的取值的。
HE的语义安全性有属于他自己的证明方式，不能用PKE语义安全性思路简单证明。
|