現代密碼學3.4--CPA安全，多次加密

• CPA安全
• • oracle
  • 例子
  • 含oracle的實驗過程
  • CPA安全定義
• 多次加密的CPA安全
• • "left-or-right" oracle $L{R}_{k,b}(?,?)$
  • 含"left-or-right" oracle的多次加密實驗過程
  • 多次加密的CPA安全定義
• 多次加密和單次加密對比
• • 唯密文攻擊/計算安全
  • 選擇明文攻擊/CPA安全

博主正在學習INTRODUCTION TO MODERN CRYPTOGRAPHY (Second Edition) --Jonathan Katz, Yehuda Lindell，做一些筆記供自己回憶，如有錯誤請指正。整理成一個系列現代密碼學，方便檢索。

• 第二章定義的完美安全是一種理論上的討論，而第三章需要定義的計算安全是一種更偏向實際需求的討論。
• 3.1節討論了定義計算安全的兩種方法，3.2節討論了什么是計算安全，3.3節給出了基于PRG構造的計算安全的密碼方案。
• 以上3.1-3.3節都在討論計算安全，這是一種抵御唯密文攻擊的安全，根據1.4節的四種攻擊模型可知，這是對敵手能力的一種最弱描述。現在，我們考慮敵手具有選擇明文攻擊的攻擊能力，來定義一種更強的安全性：CPA安全，以及考慮多次加密的計算安全和多次加密的CPA安全。

CPA安全

oracle

攻擊者可以選擇明文$m$傳給加密者，加密者用加密算法$En{c}_k(m)$得到$c$……返回給攻擊者。把這個過程看作一次查詢，由攻擊者來確定查什么，可以進行任意多次，且每次都用同樣的密鑰$k$。

例子

美軍vs日軍，中途島海戰：美軍監聽到日軍要攻擊“AF”，但是無法破解“AF”是什么地方。美軍猜測是“中途島”，于是讓中途島發假信息說缺水，日本截獲了這個信息并立即報告給總部：“AF”缺水，這就讓美軍知道了在日軍的加密方案中“AF”就是“中途島”。這就是選擇明文攻擊，美軍選擇了明文“中途島”，日軍加密得到“AF”，雖然不是日軍自愿參與的，但美軍仍達到了他們的需要。

含oracle的實驗過程

• 敵手$\mathcal{A}$已知安全參數$1^n$，有一個連接$En{c}_k(?)$的oracle（可以詢問$En{c}_k(?)$任意多次），輸出等長明文$m_0,m_1$給加密者；
• 加密者任選$b\in \{0,1\}$，輸出密文$c\leftarrow En{c}_k(m_b)$給敵手$\mathcal{A}$；
• 敵手$\mathcal{A}$在獲得$c$后，仍有一個連接$En{c}_k(?)$的oracle（可以根據$c$調整，繼續查詢），輸出猜測的$b^{\prime }$；
• 如果$b^{\prime }=b$輸出1，否則輸出0。

CPA安全定義

私鑰加密方案$\Pi =(Gen,Enc,Dec)$如果對于任意PPT敵手$\mathcal{A}$，都有一個可忽略函數negl滿足$Pr[Priv{K}_{\mathcal{A},\Pi }^{cpa}(n)=1]\le \frac{1}{2}+$negl$(n)$，則稱該方案$\Pi$在選擇明文攻擊下有不可區分的加密，是滿足CPA安全的。

多次加密的CPA安全

“left-or-right” oracle $L{R}_{k,b}(?,?)$

攻擊者輸入等長明文$m_0,m_1$給$L{R}_{k,b}(?,?)$，如果$b=0$，輸出$c\leftarrow En{c}_k(m_0)$；如果$b=1$，輸出$c\leftarrow En{c}_k(m_1)$。

• “left-or-right” oracle $L{R}_{k,b}(m,m)$可以模擬oracle $En{c}_k(m)$
• $L{R}_{k,b}(m_{0,1},m_{1,1})\dots \dots L{R}_{k,b}(m_{0,t},m_{1,t})$可以模擬多次加密

不輸入$m_{0,1},\dots \dots m_{0,t}$和$m_{1,1},\dots \dots m_{1,t}$，而選擇分別輸入$L{R}_{k,b}(m_{0,1},m_{1,1})\dots \dots L{R}_{k,b}(m_{0,t},m_{1,t})$，是因為加密者每次加密$L{R}_{k,b}(m_{0,i},m_{1,i})$返回密文$c_i$給敵手，敵手可以據此去選擇下一次希望判斷的明文，這樣定義下的敵手能力更強。

含"left-or-right" oracle的多次加密實驗過程

• 確定$b\in \{0,1\}$
• 敵手$\mathcal{A}$已知安全參數$1^n$，有一個連接$L{R}_{k,b}(?,?)$的oracle（可以詢問$L{R}_{k,b}(?,?)$任意多次）
• 敵手$\mathcal{A}$輸出猜測的$b^{\prime }$；
• 如果$b^{\prime }=b$輸出1，否則輸出0。

多次加密的CPA安全定義

私鑰加密方案$\Pi =(Gen,Enc,Dec)$如果對于任意PPT敵手$\mathcal{A}$，都有一個可忽略函數negl滿足$Pr[Priv{K}_{\mathcal{A},\Pi }^{LR?cpa}(n)=1]\le \frac{1}{2}+$negl$(n)$，則稱該方案$\Pi$在選擇明文攻擊下有不可區分的多次加密，是滿足CPA安全的多次加密。

多次加密和單次加密對比

唯密文攻擊/計算安全

考慮計算安全和多次加密下的計算安全。

• 計算安全：敵手傳$m_0,m_1$給加密者，加密者選擇$m_b,b\in \{0,1\}$進行加密得到$c\leftarrow En{c}_k(m_b)$返回給敵手，敵手猜測$b^{\prime }$。$b^{\prime }=b$則輸出1，否則輸出0。$Pr[Priv{K}_{\mathcal{A},\Pi }^{eav}=1]\le \frac{1}{2}+$negl$(n)$。具體描述可看3.2節：什么是計算安全
• 多次加密下的計算安全：敵手傳$M_0=\{m_{0,1\dots \dots m_{0,t}}\},M_1=\{m_{1,1},\dots \dots m_{1,t}\},|m_{0,i}|=|m_{1,i}|$給加密者，加密者選擇$b\in \{0,1\}$進行加密$c_i\leftarrow En{c}_k(m_{b,i})$得到$C=(c_1\dots \dots c_t)$返回給敵手，敵手猜測$b^{\prime }$。$b^{\prime }=b$則輸出1，否則輸出0。$Pr[Priv{K}_{\mathcal{A},\Pi }^{mult}=1]\le \frac{1}{2}+$negl$(n)$。

如果$En{c}_k$是確定性算法，安全性：多次加密的計算安全>計算安全。

選擇明文攻擊/CPA安全

考慮CPA安全和多次加密下的CPA安全。

• CPA安全：定義含oracle的實驗，$Pr[Priv{K}_{\mathcal{A},\Pi }^{cpa}(n)=1]\le \frac{1}{2}+$negl$(n)$
• 多次加密下的CPA安全：定義含$L{R}_{k,b}(?,?)$的實驗，$Pr[Priv{K}_{\mathcal{A},\Pi }^{LR?cpa}(n)=1]\le \frac{1}{2}+$negl$(n)$

安全性：多次加密的CPA安全=單次加密的CPA安全。

總結

以上是生活随笔為你收集整理的现代密码学3.4--CPA安全，多次加密的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。