高級密碼學復習番外篇

【扯蛋證明】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語意安全性思路簡單證明，