寫在最前面

主要在 哈工大密碼學(xué)課程 張宇老師課件 的基礎(chǔ)上學(xué)習(xí)記錄筆記。

內(nèi)容補(bǔ)充：駱婷老師的PPT
《introduction to modern cryphtography》–Jonathan Katz, Yehuda Lindell（現(xiàn)代密碼學(xué)——原理與協(xié)議）中相關(guān)章節(jié)
密碼學(xué)復(fù)習(xí)筆記 這個(gè)博主好有意思

初步筆記，如有錯(cuò)誤請指正

快速補(bǔ)充一些密碼相關(guān)的背景知識(shí)

8.1 公鑰加密理論

1. 本節(jié)學(xué)習(xí)用于保護(hù)信息的完整性和真實(shí)性的消息認(rèn)證碼（MAC）和抗碰撞的哈希函數(shù)（CRHF）。

2. 目錄：公鑰加密的定義和安全，陷門排列，選擇密文攻擊安全，在隨機(jī)預(yù)言機(jī)模型中從陷門排列到公鑰加密。

3. 私鑰密碼學(xué)局限性

   • 密鑰分發(fā)需要通信各方在物理上會(huì)面；
   • $U$個(gè)用戶的密鑰的數(shù)量 $\Theta (U^2)$；
   • 開放系統(tǒng)的安全通信：基于私鑰密碼學(xué)的解決方案無法充分處理開放系統(tǒng)中的安全通信問題，在開放系統(tǒng)中通信各方不能物理上會(huì)面，或只能暫時(shí)交互；
   • 注：私鑰密碼學(xué)中的一個(gè)核心問題就是密鑰分發(fā)與管理問題。

4. Needham-Schroeder 協(xié)議

   • Needham–Schroeder Symmetric Key Protocol：在開放網(wǎng)絡(luò)中雙方通過一個(gè)可信的第三方建立一個(gè)會(huì)話密鑰（session key）；
   • 密鑰分發(fā)中心（Key Distribution Center，KDC）作為可信的第三方（Trusted Third Party，TTP），與通信雙方Alice和Bob在事前分別建立了對稱密鑰；
   • KDC根據(jù)Alice的請求，生成一個(gè)新的 $k$ 會(huì)話密鑰（session key），分別用與Alice和Bob分別共享的密鑰來加密并發(fā)送給Alice；$E_{Bob}(k)$ 作為一個(gè)來訪問Bob所需的憑證（ticket）；
   • 用于MIT’s Kerberos 協(xié)議 (in Windows)；
   • 優(yōu)點(diǎn)：每一方只需要存儲(chǔ)一個(gè)密鑰；不需要更新通信雙方密鑰（因?yàn)椴捎眯碌臅?huì)話密鑰）；
   • 弱點(diǎn)：單點(diǎn)失效，一旦KDC被破壞，則整個(gè)系統(tǒng)都不安全。

5. Merkle難題（無需可信第三方的密鑰交換）

   • Alice準(zhǔn)備 $2^{32}$ 個(gè)難題 ${\mathsf{P}\mathsf{u}\mathsf{z}\mathsf{z}\mathsf{l}\mathsf{e}}_i$，并且發(fā)送給Bob；難題如下：

     ${\mathsf{P}\mathsf{u}\mathsf{z}\mathsf{z}\mathsf{l}\mathsf{e}}_i\leftarrow {\mathsf{E}\mathsf{n}\mathsf{c}}_{(0^{96}\Vert p_i)}(\text{“Puzzle?\#”}{x}_i\Vert k_i),$，其中 $\mathsf{E}\mathsf{n}\mathsf{c}$ 是 128位加密， p i ← { 0 , 1 } 32 p_i \gets \{0,1\}^{32} pi?←{0,1}32 并且 x i , k i ← { 0 , 1 } 128 x_i,k_i \gets \{0,1\}^{128} xi?,ki?←{0,1}128。

     注：每個(gè)難題中明文包括一個(gè)隨機(jī)數(shù)和一個(gè)密鑰，用一個(gè)密鑰加密；

   • Bob隨機(jī)選擇一個(gè)難題 ${\mathsf{P}\mathsf{u}\mathsf{z}\mathsf{z}\mathsf{l}\mathsf{e}}_j$，并且在 $2^{32}$ 時(shí)間內(nèi)猜測 $p_j$ ，獲得 $x_j,k_j$ 并將 $x_j$ 發(fā)送給 Alice。

   • Alice 按照$x_j$查詢謎題，并且使用 $k_j$ 作為密鑰。

   • 敵手需要 $2^{32+32}$ 時(shí)間，是誠實(shí)方所需時(shí)間復(fù)雜性的二次方。

   • 在誠實(shí)方和敵手之間存在更好的差距嗎？如果將加密方法看作是一個(gè)黑盒預(yù)言機(jī)，那么二次差距是最好的。

   • Merkle難題的缺點(diǎn)是謎題數(shù)量太大，獲得密鑰的代價(jià)太大；

   • 注：Merkle當(dāng)時(shí)是UC的一名本科生，這是他的一門課程設(shè)計(jì)申請。

6. 公鑰革命

   • 在1976年，Whitfield Diffie 和 Martin Hellman 發(fā)表了 “New Directions in Cryptography” （密碼學(xué)的新方向）。在這篇論文中，提出公鑰加密方案、陷門（Trap door）和數(shù)字簽名等概念。論文原文鏈接
   • 非對稱（Asymmetric）或公鑰（public-key）加密方案:
     • 公鑰（Public key）作為加密密鑰；（注：接收方產(chǎn)生，發(fā)送方持有）
     • 私鑰（Private key）作為解密密鑰； （注：接收方產(chǎn)生，接收方持有）
   • 公鑰原語（Public-key primitives）:
     • 公鑰加密（Public-key encryption）
     • 數(shù)字簽名（Digital signatures） (不可抵賴性，non-repudiation)
     • 交互式密鑰交換（Interactive key exchange）
   • 優(yōu)點(diǎn)：
     • 在公開信道上密鑰分發(fā)
     • 減少保存大量密鑰的需求
     • 使得在開放系統(tǒng)的安全成為可能
   • 缺點(diǎn)：慢兩到三個(gè)數(shù)量級，針對公鑰分發(fā)的主動(dòng)攻擊
     • 注：如何保證Alice得到的公鑰真的是Bob的公鑰？

7. 公鑰加密定義

   • 密鑰生成（Key-generation）算法: $(pk,sk)\leftarrow \mathsf{G}\mathsf{e}\mathsf{n}$, 密鑰長度 $\ge n$；
   • 明文空間： $\mathcal{M}$ 與 $pk$ 相關(guān)；（注：公鑰加密方案通常以數(shù)學(xué)難題為基礎(chǔ)，明文與公鑰之間并不完全獨(dú)立）
   • 加密（Encryption）算法: $c\leftarrow {\mathsf{E}\mathsf{n}\mathsf{c}}_{pk}(m)$.
   • 解密（Decryption）算法：$m:={\mathsf{D}\mathsf{e}\mathsf{c}}_{sk}(c)$, 或者輸出 $\perp$.
   • 需求：$\mathrm{Pr}[{\mathsf{D}\mathsf{e}\mathsf{c}}_{sk}({\mathsf{E}\mathsf{n}\mathsf{c}}_{pk}(m))=m]\ge 1?\mathsf{n}\mathsf{e}\mathsf{g}\mathsf{l}(n)$. （注：公鑰加密方案通常以數(shù)學(xué)難題為基礎(chǔ)，存在解密不成功的可能。）

8. 對竊聽者的安全 = CPA

   • 由于公鑰是公開的，敵手不僅能竊聽，而且能夠加密任意明文。
   • 在敵手和挑戰(zhàn)者間竊聽不可區(qū)分實(shí)驗(yàn) ${\mathsf{P}\mathsf{u}\mathsf{b}\mathsf{K}}_{\mathcal{A},\Pi }^{\mathsf{e}\mathsf{a}\mathsf{v}}(n)$:
     • 挑戰(zhàn)者生成密鑰 $(pk,sk)\leftarrow \mathsf{G}\mathsf{e}\mathsf{n}(1^n)$。
     • 敵手 $\mathcal{A}$ 被給予 $\mathbf{p}\mathbf{k}$ 以及 ${\mathsf{E}\mathsf{n}\mathsf{c}}_{\mathbf{p}\mathbf{k}}(?)$ 預(yù)言機(jī)的訪問，輸出相同長度的 $m_0,m_1$ 。
     • 挑戰(zhàn)者隨機(jī)生成 b ← { 0 , 1 } b \gets \{0,1\} b←{0,1}。將挑戰(zhàn)密文 $c\leftarrow {\mathsf{E}\mathsf{n}\mathsf{c}}_{pk}(m_b)$ 發(fā)送給敵手 $\mathcal{A}$。
     • $\mathcal{A}$ 繼續(xù)訪問預(yù)言機(jī) ${\mathsf{E}\mathsf{n}\mathsf{c}}_{\mathbf{p}\mathbf{k}}(?)$ 并且輸出 $b^{\prime }$。
     • 如果 $b^{\prime }=b$，$\mathcal{A}$ 成功 ${\mathsf{P}\mathsf{u}\mathsf{b}\mathsf{K}}_{\mathcal{A},\Pi }^{\mathsf{e}\mathsf{a}\mathsf{v}}=1$，否則 0。
   • 定義：$\Pi$ 是 CPA-secure， 如果 $?$ ppt $\mathcal{A}$, $?$ $\mathsf{n}\mathsf{e}\mathsf{g}\mathsf{l}$ 使得 $\mathrm{Pr}\left[{\mathsf{P}\mathsf{u}\mathsf{b}\mathsf{K}}_{\mathcal{A},\Pi }^{\mathsf{c}\mathsf{p}\mathsf{a}}(n)=1\right]\le \frac{1}{2}+\mathsf{n}\mathsf{e}\mathsf{g}\mathsf{l}(n)$。

9. 公鑰加密的安全屬性

   • 對稱加密可以加密32比特消息，產(chǎn)生32比特密文，例如，使用一次一密。在公鑰系統(tǒng)中能夠做到同樣的嗎？
   • 一個(gè)確定性的公鑰加密方案在竊聽者出現(xiàn)時(shí)是安全的？
   • 如果 $\Pi$ 在竊聽者出現(xiàn)時(shí)是安全的，那么 $\Pi$ 也是CPA安全的? 是否是多重加密安全的？
   • 完美保密的公鑰加密是可能的嗎？（注：不可能）

10. 密鑰長度比較

    NIST（美國國家標(biāo)準(zhǔn)技術(shù)研究所）推薦可比較的密鑰長度 (按比特) 。NIST 認(rèn)為一個(gè)112比特的有效密鑰長度直到2030年是可接受的，但是推薦 128 比特或更長的密鑰。

    對稱密鑰（AES）	RSA/DH	ECC
    56	512	112
    80	1024	160
    112	2048	224
    128	3072	256
    192	7680	384
    256	15360	512

11. 混合加密（Hybrid Encryption）構(gòu)造

    • 為了加速加密，采用私鑰加密方案 ${\Pi }^{\prime }$ (數(shù)據(jù)封裝機(jī)制，data-encapsulation mechanism, DEM) 與公鑰加密方案 $\Pi$ (密鑰封裝機(jī)制, key-encapsulation mechanism, KEM) 一起。
    • ${\Pi }^{\mathsf{h}\mathsf{y}}=({\mathsf{G}\mathsf{e}\mathsf{n}}^{\mathsf{h}\mathsf{y}},{\mathsf{E}\mathsf{n}\mathsf{c}}^{\mathsf{h}\mathsf{y}},{\mathsf{D}\mathsf{e}\mathsf{c}}^{\mathsf{h}\mathsf{y}})$:
    • ${\mathsf{G}\mathsf{e}\mathsf{n}}^{\mathsf{h}\mathsf{y}}$: $(pk,sk)\leftarrow \mathsf{G}\mathsf{e}\mathsf{n}(1^n)$. 注：只需提前生成公鑰加密方案所需密鑰
    • ${\mathsf{E}\mathsf{n}\mathsf{c}}^{\mathsf{h}\mathsf{y}}$: $pk$ and $m$.
      • k ← { 0 , 1 } n k \gets \{0,1\}^n k←{0,1}n. 注：生成私鑰加密密鑰
      • $c_1\leftarrow {\mathsf{E}\mathsf{n}\mathsf{c}}_{pk}(k)$, $c_2\leftarrow {\mathsf{E}\mathsf{n}\mathsf{c}}_k^{\prime }(m)$. 注：用公鑰加密的公鑰加密私鑰加密密鑰，用私鑰加密密鑰加密消息。
    • ${\mathsf{D}\mathsf{e}\mathsf{c}}^{\mathsf{h}\mathsf{y}}$: $sk$ and $?c_1,c_2?$.
      • $k:={\mathsf{D}\mathsf{e}\mathsf{c}}_{sk}(c_1)$. 注：用公鑰加密中私鑰解密獲得私鑰加密密鑰
      • $m:={\mathsf{D}\mathsf{e}\mathsf{c}}_k^{\prime }(c_2)$. 注：用私鑰加密密鑰獲得明文
    • 問題：混合加密方案是公鑰加密還是私鑰加密？

12. 混合加密安全

    • 定理：如果 $\Pi$ 是一個(gè)CPA安全的公鑰加密方案，并且 ${\Pi }^{\prime }$ 是竊聽者不可區(qū)分的私鑰加密方案，那么 ${\Pi }^{\mathsf{h}\mathsf{y}}$ 是CPA安全的公鑰加密方案。
    • 這里對于私鑰加密方案的安全性要求只是竊聽者不可區(qū)分的，不要求是CPA安全的，因?yàn)?strong>私鑰加密密鑰是每次加密時(shí)隨機(jī)產(chǎn)生的新密鑰，私鑰加密的加密預(yù)言機(jī)提供的結(jié)果無法被利用。
    • 整個(gè)方案安全證明的思路是利用各方案之間不可區(qū)分性，以及不可區(qū)分性所具有的傳遞性（transitiviy）。
    • 目標(biāo)是證明 （1）$?pk,{\mathsf{E}\mathsf{n}\mathsf{c}}_{pk}(k),{\mathsf{E}\mathsf{n}\mathsf{c}}_k^{\prime }(m_0)?$ 與（2） $?pk,{\mathsf{E}\mathsf{n}\mathsf{c}}_{pk}(k),{\mathsf{E}\mathsf{n}\mathsf{c}}_k^{\prime }(m_1)?$ 之間對于不同明文的不可區(qū)分性。為此，先觀察（1） $?pk,{\mathsf{E}\mathsf{n}\mathsf{c}}_{pk}(k),{\mathsf{E}\mathsf{n}\mathsf{c}}_k^{\prime }(m_0)?$ 與（3） $?pk,{\mathsf{E}\mathsf{n}\mathsf{c}}_{pk}(0^n),{\mathsf{E}\mathsf{n}\mathsf{c}}_k^{\prime }(m_0)?$ 之間對于不同公鑰加密明文（私鑰加密密鑰）之間由于公鑰加密方案不可區(qū)分性也是不可區(qū)分的；同理，（2）$?pk,{\mathsf{E}\mathsf{n}\mathsf{c}}_{pk}(k),{\mathsf{E}\mathsf{n}\mathsf{c}}_k^{\prime }(m_1)?$ 與（4） $?pk,{\mathsf{E}\mathsf{n}\mathsf{c}}_{pk}(0^n),{\mathsf{E}\mathsf{n}\mathsf{c}}_k^{\prime }(m_1)?$ 之間也是不可區(qū)分的。（3）$?pk,{\mathsf{E}\mathsf{n}\mathsf{c}}_{pk}(0^n),{\mathsf{E}\mathsf{n}\mathsf{c}}_k^{\prime }(m_0)?$ 與（4） $?pk,{\mathsf{E}\mathsf{n}\mathsf{c}}_{pk}(0^n),{\mathsf{E}\mathsf{n}\mathsf{c}}_k^{\prime }(m_1)?$ 之間由于私鑰加密方案不可區(qū)分性也是不可區(qū)分的。最后，根據(jù)不可區(qū)分性所具有的傳遞性，證明混合加密方案的不可區(qū)分性。

13. 混合加密范式應(yīng)用

    • 共享文件訪問，Alice用自己的對稱密鑰加密文件，Bob的公鑰加密對稱密鑰
    • 密鑰托管，Alice用托管服務(wù)器的公鑰加密對稱密鑰，領(lǐng)導(dǎo)從托管服務(wù)器獲得私鑰來解鎖

14. 陷門函數(shù)（Trapdoor Function）

    • 陷門函數(shù)（Trapdoor function）: 易于計(jì)算，在缺乏特定信息（陷門）時(shí)難以求逆，即帶有陷門的單向函數(shù)。
    • 1982年，姚期智在論文《Theory and Applications of Trapdoor Functions》中提出，從任意陷門函數(shù)中可構(gòu)造一個(gè)公鑰加密方案。

15. 函數(shù)族（Families of Functions）

    • $\Pi =(\mathsf{G}\mathsf{e}\mathsf{n},\mathsf{S}\mathsf{a}\mathsf{m}\mathsf{p},f)$ 是一個(gè)函數(shù)組，如果：
      • 參數(shù)生成（Parameter-generation）算法: $I\leftarrow \mathsf{G}\mathsf{e}\mathsf{n}(1^n)$。參數(shù)$I$定義了定義域（domain）${\mathcal{D}}_I$和值域（range）${\mathcal{D}}_R$。注：這里產(chǎn)生了一個(gè)具體的函數(shù)參數(shù)。
      • 采樣（sampling）算法: $x\leftarrow \mathsf{S}\mathsf{a}\mathsf{m}\mathsf{p}(I)$，均勻隨機(jī)地產(chǎn)生一個(gè)$x$。
      • 確定性賦值（evaluation）算法: $y:=f_I(x)$。
    • 這里強(qiáng)調(diào)采樣算法是因?yàn)楹竺嬉獙W(xué)習(xí)的數(shù)論難題的輸入是要滿足某些條件的。

16. 陷門排列族

    • 一組多項(xiàng)式時(shí)間算法 $\Pi =(\mathsf{G}\mathsf{e}\mathsf{n},\mathsf{S}\mathsf{a}\mathsf{m}\mathsf{p},f,\mathsf{I}\mathsf{n}\mathsf{v})$ 是一個(gè)陷門排列族（family of trapdoor permutations，TDP），如果：
      • 參數(shù)生成（parameter generation）算法 $\mathsf{G}\mathsf{e}\mathsf{n}$, 輸入 $1^n$，輸出 $(I,\mathsf{t}\mathsf{d})$ 有 $|I|\ge n$。其中， $(I,\mathsf{t}\mathsf{d})$ 定義了集合 ${\mathcal{D}}_I={\mathcal{D}}_{\mathsf{t}\mathsf{d}}$。注：陷門排列族是一個(gè)函數(shù)集合，參數(shù)生成算法產(chǎn)生一個(gè)具體陷門排列所需的參數(shù)。
      • ${\mathsf{G}\mathsf{e}\mathsf{n}}_I$ 只輸出 $I$。$({\mathsf{G}\mathsf{e}\mathsf{n}}_I,\mathsf{S}\mathsf{a}\mathsf{m}\mathsf{p},f)$ 是 OWP。其中的$\mathsf{S}\mathsf{a}\mathsf{m}\mathsf{p}$是采樣函數(shù)，用于獲得函數(shù)的輸入$x\leftarrow {\mathcal{D}}_I$。
      • 一個(gè)確定性求逆算法 $\mathsf{I}\mathsf{n}\mathsf{v}$，對于 $?(I,\mathsf{t}\mathsf{d})$ 并且 $?x\in {\mathcal{D}}_I$， $ \mathsf{Inv}_{\mathsf{td}}(f_I(x))=x$。注：可求逆
    • 核心斷言：確定性多項(xiàng)式時(shí)間算法 $\mathsf{h}\mathsf{c}$ 是$\Pi$ 的一個(gè)核心斷言（hard-core predicate），如果 $?$ ppt $\mathcal{A}$，$?$ $\mathsf{n}\mathsf{e}\mathsf{g}\mathsf{l}$ 使得 $ \Pr[\mathcal{A}(I,f_I(x)) = \mathsf{hc}_I(x)] \le \frac{1}{2} +\mathsf{negl}(n)$。
    • 定理：給定一個(gè)陷門排列族$\Pi =(\mathsf{G}\mathsf{e}\mathsf{n},\mathsf{S}\mathsf{a}\mathsf{m}\mathsf{p},f,\mathsf{I}\mathsf{n}\mathsf{v})$，則存在一個(gè)帶有核心斷言的陷門排列族$\hat{\Pi }=(\widehat{\mathsf{G}\mathsf{e}\mathsf{n}},\mathsf{S}\mathsf{a}\mathsf{m}\mathsf{p},f,\mathsf{I}\mathsf{n}\mathsf{v})$。注：證明與單向函數(shù)部分關(guān)于核心斷言的定理類似。

17. TDP例題

    • 如果答案是肯定的，則需要反證法證明，$f^{\prime }$若不是TDP，那么$f$也不是；
    • 如果答案是否定的，則需要給出一個(gè)有效的求逆方法。

18. 從TDP到公鑰加密方案

    • 從一個(gè)帶有核心斷言$\mathsf{h}\mathsf{c}$的陷門排列族$\hat{\Pi }=(\widehat{\mathsf{G}\mathsf{e}\mathsf{n}},\mathsf{S}\mathsf{a}\mathsf{m}\mathsf{p},f,\mathsf{I}\mathsf{n}\mathsf{v})$來構(gòu)造一個(gè)公鑰加密方案：
      • $\mathsf{G}\mathsf{e}\mathsf{n}$: $(I,\mathsf{t}\mathsf{d})\leftarrow \widehat{Gen}$ 輸出公鑰 $I$ 和私鑰 $\mathsf{t}\mathsf{d}$。
      • $\mathsf{E}\mathsf{n}\mathsf{c}$: 輸入 $I$ 和 m ∈ { 0 , 1 } m \in \{0,1\} m∈{0,1}，選擇一個(gè) $x\leftarrow {\mathcal{D}}_I$ 并且輸出 $?f_I(x),{\mathsf{h}\mathsf{c}}_I(x)\oplus m?$。
      • $\mathsf{D}\mathsf{e}\mathsf{c}$: 輸入 $\mathsf{t}\mathsf{d}$ 和 $?y,m^{\prime }?$，計(jì)算 $x:=f_I^{?1}(y)$ 并且輸出 ${\mathsf{h}\mathsf{c}}_I(x)\oplus m^{\prime }$。
    • 定理：如果 $\hat{\Pi }=(\widehat{Gen},f)$ 是 TDP，并且 $\mathsf{h}\mathsf{c}$ 是$\hat{\Pi }$的 HCP ，那么構(gòu)造 $\Pi$ 是 CPA安全的。
    • 問題：這個(gè)方案是安全的嗎？${\mathsf{E}\mathsf{n}\mathsf{c}}_I(m)=f_I(m)$， ${\mathsf{D}\mathsf{e}\mathsf{c}}_{\mathsf{t}\mathsf{d}}(c)=f_I^{?1}(c)$。

19. 證明

    • ${\mathsf{h}\mathsf{c}}_I(x)$ 是偽隨機(jī)的。將 ${\mathcal{A}}_{\mathsf{h}\mathsf{c}}$ for $\mathsf{h}\mathsf{c}$ 規(guī)約到 $\mathcal{A}$ for $\Pi$。
    • $\mathrm{Pr}[{\mathcal{A}}_{\mathsf{h}\mathsf{c}}(I,f_I(x))={\mathsf{h}\mathsf{c}}_I(x)]=$ $\frac{1}{2}?(\mathrm{Pr}[b^{\prime }=b|z={\mathsf{h}\mathsf{c}}_I(x)]+\mathrm{Pr}[b^{\prime }=b|z={\mathsf{h}\mathsf{c}}_I(x)]).$
    • 上面的公式的含義是 ${\mathcal{A}}_{\mathsf{h}\mathsf{c}}$成功得到核心斷言包含兩種情況：
      • 當(dāng)$z$是核心斷言，則$\mathcal{A}$面對的是方案$\Pi$，$\mathcal{A}$成功（$b^{\prime }=b$），輸出的$z$就是核心斷言；
      • 當(dāng)$z$不是核心斷言，則$\mathcal{A}$面對的挑戰(zhàn)密文與$\Pi$中是相反的，$\mathcal{A}$失敗（$b^{\prime }=b$），輸出的$\overline{z}$就是核心斷言；

20. 證明（續(xù)）

    • $\mathrm{Pr}[b^{\prime }=b|z={\mathsf{h}\mathsf{c}}_I(x)]=\mathrm{Pr}[{\mathsf{P}\mathsf{u}\mathsf{b}\mathsf{K}}_{\mathcal{A},\Pi }^{\mathsf{e}\mathsf{a}\mathsf{v}}(n)=1]=\epsilon (n)$。 注：$\mathcal{A}$實(shí)驗(yàn)成功。
    • 如果 $z={\mathsf{h}\mathsf{c}}_I(x)$, $m^{\prime }=m_b\oplus {\overline{\mathsf{h}\mathsf{c}}}_I(x)=m_{\overline{b}}\oplus {\mathsf{h}\mathsf{c}}_I(x)$，這意味著 $m_{\overline{b}}$ 被加密了。
    • $\mathrm{Pr}[b^{\prime }=b|z={\mathsf{h}\mathsf{c}}_I(x)]=\mathrm{Pr}[{\mathsf{P}\mathsf{u}\mathsf{b}\mathsf{K}}_{\mathcal{A},\Pi }^{\mathsf{e}\mathsf{a}\mathsf{v}}(n)=0]=1?\epsilon (n)$。 注：$\mathcal{A}$實(shí)驗(yàn)失敗了。
    • $\mathrm{Pr}[b^{\prime }=b|z={\mathsf{h}\mathsf{c}}_I(x)]=\epsilon (n)$。
    • $\mathrm{Pr}[{\mathcal{A}}_{\mathsf{h}\mathsf{c}}(I,f_I(x))={\mathsf{h}\mathsf{c}}_I(x)]=\frac{1}{2}?(\epsilon (n)+\epsilon (n))=\epsilon (n)$。 注：根據(jù)上一頁的公式。
    • 至此，我們學(xué)習(xí)了基于陷門排列的公鑰加密方案，但只能加密一個(gè)比特，如何加密一個(gè)更長的明文？后面學(xué)習(xí)隨機(jī)預(yù)言機(jī)模型設(shè)定下的公鑰加密方案。

21. 在公鑰設(shè)定中CCA情景

    • CCA
      • 敵手 $\mathcal{A}$ 觀察由 $\mathcal{S}$ 發(fā)送給 $\mathcal{R}$ 的密文 $c$ 。
      • $\mathcal{A}$ 以$\mathcal{S}$ 或自己的名義發(fā)送 $c^{\prime }$ 給 $\mathcal{R}$ 。
      • $\mathcal{A}$ 根據(jù)從 $c^{\prime }$ 中解密出的 $m^{\prime }$ 來推斷 $m$。
    • 情景
      • 用口令來登陸在線銀行：試錯(cuò)，從銀行反饋中獲得信息。
      • 郵件回復(fù)中包含解密出的文本的引用。
      • 密文的可鍛造性，例如，在拍賣中將其他人的出價(jià)翻倍。

22. 對CCA/CCA2的安全定義

    • CCA/CCA2 不可區(qū)分實(shí)驗(yàn) ${\mathsf{P}\mathsf{u}\mathsf{b}\mathsf{K}}_{\mathcal{A},\Pi }^{\mathsf{c}\mathsf{c}\mathsf{a}}(n)$：
      • $(pk,sk)\leftarrow \mathsf{G}\mathsf{e}\mathsf{n}(1^n)$.
      • $\mathcal{A}$ 給定輸入 $pk$ 和預(yù)言機(jī)訪問 ${\mathsf{D}\mathsf{e}\mathsf{c}}_{sk}(?)$，輸出相同長度的 $m_0,m_1$ 。
      • b ← { 0 , 1 } b \gets \{0,1\} b←{0,1}。挑戰(zhàn)密文 $c\leftarrow {\mathsf{E}\mathsf{n}\mathsf{c}}_{pk}(m_b)$ 給 $\mathcal{A}$。
      • 在CCA2中，$\mathcal{A}$ 除了 $c$ 之外還可以訪問 ${\mathsf{D}\mathsf{e}\mathsf{c}}_{sk}(?)$，并輸出$b^{\prime }$ 。注：CCA 也被稱作午餐攻擊。CCA2 也被稱為適應(yīng)性的 CCA。
      • 如果 $b^{\prime }=b$，那么 $\mathcal{A}$ 成功， ${\mathsf{P}\mathsf{r}\mathsf{i}\mathsf{v}\mathsf{K}}_{\mathcal{A},\Pi }^{\mathsf{c}\mathsf{c}\mathsf{a}}=1$，否則 0。
    • $\Pi$ 是 CCA/CCA2安全的，如果 $?$ ppt $\mathcal{A}$, $?$ $\mathsf{n}\mathsf{e}\mathsf{g}\mathsf{l}$ 使得 $\mathrm{Pr}\left[{\mathsf{P}\mathsf{u}\mathsf{b}\mathsf{K}}_{\mathcal{A},\Pi }^{\mathsf{c}\mathsf{c}\mathsf{a}}(n)=1\right]\le \frac{1}{2}+\mathsf{n}\mathsf{e}\mathsf{g}\mathsf{l}(n)$.

23. 例題

    • 略

24. CCA2安全加密技術(shù)進(jìn)展

    • 零知識(shí)證明（Zero-Knowledge Proof）：復(fù)雜并不可實(shí)踐。(例如，Dolev-Dwork-Naor)
    • 隨機(jī)預(yù)言機(jī)模型（Random Oracle model）：有效，但并不踏實(shí) (將 CRHF 當(dāng)作 RO)。 (例如，RSA-OAEP 和 Fujisaki-Okamoto)
    • DDH（決策性Diffie-Hellman）假設(shè)和UOWHF（全域單向哈希函數(shù)）：大小擴(kuò)展2倍，但可以在沒有RO和ZKP場景下證明安全 (例如，Cramer-Shoup system)。
    • CCA2安全意味著明文感知（Plaintext-aware）：敵手在不知道明文的情況下，不能產(chǎn)生有效的密文。
    • 開放問題：如何構(gòu)造一個(gè)與“書本上RSA”一樣有效的，基于RSA問題的CCA2安全的方案。

隨機(jī)預(yù)言機(jī)模型（Random Oracle Model，ROM）

25. 隨機(jī)預(yù)言機(jī)模型（Random Oracle Model，ROM）

    • 為了在實(shí)踐中實(shí)現(xiàn)CPA安全和CCA安全的公鑰加密方案，引入了一個(gè)更強(qiáng)大的隨機(jī)對象，稱為隨機(jī)預(yù)言機(jī)（Random Oracle Model）。
    • 隨機(jī)預(yù)言機(jī)（RO）：一個(gè)真隨機(jī)函數(shù)（$H$）對每個(gè)可能的查詢回答一個(gè)隨機(jī)應(yīng)答。
      • 一致性：如果$H$曾經(jīng)在運(yùn)行中為一個(gè)輸入 $x$ 輸出 $y$，那么它一直對相同的輸入輸出相同的答案。
      • 無人“知道”整個(gè)函數(shù) $H$。
    • 隨機(jī)預(yù)言機(jī)模型（ROM）：存在一個(gè)公開的RO。與此相對的，不存在RO的情況，稱作標(biāo)準(zhǔn)模型。
    • 方法論：在ROM中構(gòu)造可證明的安全。
      1. 在ROM中，一個(gè)方案被設(shè)計(jì)并被證明是安全的。
      2. 將 $H$ 用一個(gè)哈希函數(shù) $\hat{H}$，例如 SHA256。
    • 無人嚴(yán)格地聲明隨機(jī)預(yù)言機(jī)存在。
    • 存在某些方案，在ROM中被證明是安全的，但無論如何將隨機(jī)預(yù)言機(jī)實(shí)例化都不是安全的。
    • 使用ROM，很容易實(shí)現(xiàn)可證明安全，同時(shí)通過正確的實(shí)例化來保持高效。

26. ROM的簡單例子

    • 由于RO “強(qiáng)大的隨機(jī)性”，其可以充當(dāng)或構(gòu)造之前學(xué)習(xí)過得密碼學(xué)原語，包括為單向函數(shù)、抗碰撞哈希函數(shù)、偽隨機(jī)函數(shù)等。

    • 一個(gè) RO 將 $n_1$ 比特輸入映射為 $n_2$ 比特輸出。

    • RO 作為 OWF，進(jìn)行如下實(shí)驗(yàn)：

      1. 選擇一個(gè)RO $H$ ；

      2. 選擇一個(gè)隨機(jī)的 x ∈ { 0 , 1 } n 1 x \in \{0,1\}^{n_1} x∈{0,1}n1? ，并且賦值 $y:=H(x)$ ；

      3. 敵手 $\mathcal{A}$ 被給予 $y$，如果輸出 $x^{\prime }$: $H(x^{\prime })=y$，則成功；

         解釋：如果敵手成功求逆，則意味著敵手“事先”詢問過RO；

    • RO 作為 CRHF，進(jìn)行如下實(shí)驗(yàn)：

      1. 選擇一個(gè)RO $H$ ；

      2. 敵手 $\mathcal{A}$ 成功，如果其輸出 $x,x^{\prime }$ 滿足 $H(x)=H(x^{\prime })$ ，但是 $x=x^{\prime }$；

         解釋：如果敵手找到碰撞，則意味著$H$不是隨機(jī)的，因?yàn)閮蓚€(gè)隨機(jī)輸出不可能相同。

    • 從一個(gè)RO構(gòu)造PRF ： $n_1=2n$, $n_2=n$.

      • $F_k(x)\stackrel{\text{def}}{=}H(k\Vert x),$ $|k|=|x|=n.$

        解釋：如果$F$不是偽隨機(jī)的，則$H$也可以與真隨機(jī)相區(qū)分。

27. CPA安全

    • 思路：PubK CPA = PrivK + (Secret Key = TDP + RO)
    • 實(shí)現(xiàn)CPA安全的公鑰加密方案，可以基于一個(gè)安全的私鑰加密方案，其中私鑰加密的密鑰由RO得到，通過TDP傳遞生成密鑰所用的隨機(jī)量；
    • 構(gòu)造：
      • $\mathsf{G}\mathsf{e}\mathsf{n}$: $pk=I$, $sk=\mathsf{t}\mathsf{d}$.
      • $\mathsf{E}\mathsf{n}\mathsf{c}$: r ← { 0 , 1 } ? r \gets \{0,1\}^* r←{0,1}?, 輸出 $?c_1=f_I(r),c_2=\mathsf{H}(r)\oplus m?$.
      • $\mathsf{D}\mathsf{e}\mathsf{c}$: $r:=f_{\mathsf{t}\mathsf{d}}^{?1}(c_1)$, 輸出 $\mathsf{H}(r)\oplus c_2$.
    • 定理：如果 $f$ 是 TDP， 并且 $H$ 是 RO，則構(gòu)造是 CPA 安全的。
    • 解釋：私鑰加密方案只需要是竊聽下安全，因?yàn)槊看渭用芏际歉怕市缘?#xff0c;每次私鑰加密密鑰都是重新生成的。該方案不是CCA安全的，因?yàn)榇鄹拿芪目梢灾苯佑绊懨魑摹?/li>
    • 用RO的必要性：由于$r$的部分信息可能通過TPD泄漏，如果以一個(gè)PRG來替換掉RO，則由于種子的部分信息已知，PRG的輸出也不在是偽隨機(jī)的，加密方案也不再安全。

28. 基于私鑰加密的CCA安全

    • 思路：PubK CCA = PrivK CCA + (Secret Key = TPD + RO)
    • 實(shí)現(xiàn)CCA安全的公鑰加密方案，可以基于一個(gè)CCA安全的私鑰加密方案，其中私鑰加密密鑰由RO得到，通過TDP傳遞生成密鑰所用的隨機(jī)量；
    • 構(gòu)造：
      • ${\Pi }^{\prime }$ 是一個(gè)安全私鑰加密方案。
      • $\mathsf{G}\mathsf{e}\mathsf{n}$: $pk=I$, $sk=\mathsf{t}\mathsf{d}$.
      • $\mathsf{E}\mathsf{n}\mathsf{c}$: $k:=H(r),r\leftarrow D_I$, 輸出 $?c_1=f_I(r),c_2={\mathsf{E}\mathsf{n}\mathsf{c}}_k^{\prime }(m)?$.
      • $\mathsf{D}\mathsf{e}\mathsf{c}$: $r:=f_{\mathsf{t}\mathsf{d}}^{?1}(c_1)$, $k:=H(r)$, 輸出 ${\mathsf{D}\mathsf{e}\mathsf{c}}_k^{\prime }(c_2)$.
    • 定理：如果 $f$ 是 TDP，${\Pi }^{\prime }$ 是 CCA 安全的，并且 $H$ 是 RO，那么構(gòu)造是 CCA 安全的。
    • 解釋：公鑰加密方案的CCA安全性來自私鑰加密方案的CCA安全性。

29. 在ROM中基于TPD的CCA安全

    • 思路：PubK CCA = TDP + 2 RO (一個(gè)用于加密，一個(gè)用于MAC)
    • 實(shí)現(xiàn)CCA安全的公鑰加密方案，可以通過RO來構(gòu)造一個(gè)CPA安全的公鑰加密方案，以明文和密文一起作為輸入來生成MAC標(biāo)簽。
    • 構(gòu)造：
      • $\mathsf{G}\mathsf{e}\mathsf{n}$: $pk=I$, $sk=\mathsf{t}\mathsf{d}$
      • $\mathsf{E}\mathsf{n}\mathsf{c}$: $r\leftarrow D_I$，輸出 $?c_1=f_I(r),c_2=H(r)\oplus m,c_3=G(c_2\Vert m)?$
      • $\mathsf{D}\mathsf{e}\mathsf{c}$: $r:=f_{\mathsf{t}\mathsf{d}}^{?1}(c_1)$, $m:=H(r)\oplus c_2$。如果 $G(c_2\Vert m)=c_3$ 輸出 $m$，否則 $\perp$。
    • 定理：如果 $f$ 是 TDP，$G,H$ 是 RO，那么構(gòu)造是 CCA 安全的。
    • 解釋：其CCA安全性在于對密文的任何篡改，都無法通過MAC驗(yàn)證。

30. 私鑰加密 vs. 公鑰加密

    	私鑰加密	公鑰加密
    密鑰	雙方	接收者
    最弱攻擊	竊聽者	CPA
    概率性	CPA/CCA	一直
    對CPA的假設(shè)	OWF	TDP
    對CCA的假設(shè)	OWF	TDP+RO
    效率	快	慢