现代密码学【4】之计算安全性安全规约证明对称加密的窃听不可区分实验

计算安全性

• 计算安全性弱于信息论安全性。它目前也依赖于假设，而实现后者不需要任何假设。
• 计算安全是大多数现代密码学构造方法的目标。
• 计算安全的方案，只要给足够的时间和计算能力总能被攻破！
• 使用完善保密的加密方案是不必要的。只要在实践上是不可破译的密码方案即可实用，如某方案在200年内，使用最快的可用的超级计算机，也不能以大于10^(−30)的概率攻破。
• 基于计算安全的方法包含两种放宽的完善安全概念：
  • 对抗可行性时间内运行的敌手，安全性存在。
  • 敌手成功率很小，以至于不关心是否真的存在。

计算安全的渐进度量方法

1. 渐进方法的核心：该方法基于复杂性理论，将敌手（攻击者）的运行时间与成功概率视为安全参数n nn的函数（而非具体数值）。密码方案包含安全参数n nn，诚实双方初始化时选定n nn，且假设敌手已知该n nn，敌手的运行时间与成功概率均由n nn决定。
2. 可行策略与多项式时间：将“可行的策略”或“有效的算法”等同于在以n nn为参数的多项式时间内运行的概率算法（运行时间表示为a ⋅ n c a \cdot n^ca⋅nc，其中a , c a, ca,c为常量）。诚实方需在多项式时间内运行，敌手虽可能计算能力更强（运行时间更长），但也在多项式时间内运行；超多项式时间的攻击策略因无现实意义而被忽略。
3. 小的成功概率与可忽略性：将“小的成功概率”等同于成功概率小于任何以n nn为参数的多项式倒数（即对任意常量c cc，当n nn足够大时，概率小于n − c n^{-c}n−c）。比任何多项式倒数增长更慢的函数称为“可忽略的（negligible）”。

假设方案安全时，敌手运行n 3 n^3n3分钟攻破方案的概率为2 40 ⋅ 2 − n 2^{40} \cdot 2^{-n}240⋅2−n（该函数关于n nn可忽略）。不同n nn值下的情况：

• 当n ≤ 40 n \leq 40n≤40，敌手运行约6周（40 3 40^3403分钟）时，攻破概率为1，此时n nn无实际意义；
• 当n = 50 n = 50n=50，敌手运行约3个月（50 3 50^3503分钟）时，攻破概率约1 / 1000 1/10001/1000，无法接受；
• 当n = 500 n = 500n=500，敌手运行超200年时，攻破概率仅为2 − 500 2^{-500}2−500。

计算安全的渐进安全度量方法

• 有效计算：在概率多项式时间内执行的计算。
• 可忽略的成功概率：对任意多项式p pp，如果攻破该方案的概率渐进小于1 p ( n ) \frac{1}{p(n)}p(n)1​，则认为该方案安全，否则视为不安全。

定义 3.4
函数f ff为可忽略的，如果对于每个多项式p ( ⋅ ) p(\cdot)p(⋅)，存在一个N NN，使得对于所有的整数n > N n > Nn>N，都满足
f ( n ) < 1 p ( n ) . f(n) < \frac{1}{p(n)}.f(n)<p(n)1​.
等价的公式化的表述是:对所有常量c cc，存在一个N NN，使得对于所有的n > N n > Nn>N，满足
f ( n ) < n − c . f(n) < n^{-c}.f(n)<n−c.
为了方便记忆，上面的表述也可以陈述如下：对于任意多项式p ( ⋅ ) p(\cdot)p(⋅)以及所有足够大的n nn值，满足
f ( n ) < 1 p ( n ) . f(n) < \frac{1}{p(n)}.f(n)<p(n)1​.
通常将一个可忽略函数表示为negl \text{negl}negl。

命题 3.6
令negl 1 \text{negl}_1negl1​和negl 2 \text{negl}_2negl2​为可忽略函数。则
(1) 函数negl 3 \text{negl}_3negl3​被定义为negl 3 ( n ) = negl 1 ( n ) + negl 2 ( n ) \text{negl}_3(n) = \text{negl}_1(n) + \text{negl}_2(n)negl3​(n)=negl1​(n)+negl2​(n)，则该函数是可忽略的。
(2) 对于任何正多项式p pp，函数negl 4 \text{negl}_4negl4​被定义为negl 4 ( n ) = p ( n ) ⋅ negl 1 ( n ) \text{negl}_4(n) = p(n) \cdot \text{negl}_1(n)negl4​(n)=p(n)⋅negl1​(n)，则该函数是可忽略的。

安全规约证明（重点）

• PPT(Probabilistic Polynomial Time)：概率多项式时间。

1. 指定有效(概率多项式时间)敌手A \mathcal{A}A攻击方案Π \PiΠ，其成功概率为ε ( n ) \varepsilon(n)ε(n)。
2. 构造“规约”算法A ′ \mathcal{A}'A′，将A \mathcal{A}A作为子程序，解决难题X \mathcal{X}X：
   • A ′ \mathcal{A}'A′仅知A \mathcal{A}A想攻击Π \PiΠ，对A \mathcal{A}A的内部工作一无所知；
   • 对难题X \mathcal{X}X的输入实例x xx，A ′ \mathcal{A}'A′模拟Π \PiΠ的实例，使A \mathcal{A}A与Π \PiΠ交互的分布，A \mathcal{A}A的分布和A \mathcal{A}A自身与Π \PiΠ交互的分布相同（或接近）。
3. 若A \mathcal{A}A成功“攻破”模拟的Π \PiΠ实例，则A ′ \mathcal{A}'A′解决X \mathcal{X}X的概率至少为多项式倒数1 / p ( n ) 1/p(n)1/p(n)。
4. 若ε ( n ) \varepsilon(n)ε(n)非可忽略，则A ′ \mathcal{A}'A′解决X \mathcal{X}X的概率为ε ( n ) / p ( n ) \varepsilon(n)/p(n)ε(n)/p(n)（非可忽略）。因A ′ \mathcal{A}'A′有效，存在有效算法以非可忽略概率解决X \mathcal{X}X，与假设矛盾。
   
5. 结论：给定难题X \mathcal{X}X的假设下，不存在有效敌手A \mathcal{A}A能以非可忽略概率攻破Π \PiΠ，即Π \PiΠ是计算上安全的。

对称加密的窃听不可区分实验（带n） （重点）

• 窃听不可区分实验对任何对称密钥方案π = ( G e n , E n c , D e c ) \pi =(Gen,Enc,Dec)π=(Gen,Enc,Dec)，任何敌手A \mathcal{A}A，以及对任何安全参数n nn的值都适用。
• 窃听不可区分实验PrivK A , Π eav ( n ) : \text{PrivK}_{A,\Pi}^{\text{eav}}(n):PrivKA,Πeav​(n):
  1. 给定输入1 n 1^n1n给敌手A AA,A AA输出一对长度相等的消息m 0 , m 1 m_0, m_1m0​,m1​
  2. 运行Gen ( 1 n ) \text{Gen}(1^n)Gen(1n)生成一个密钥k kk, 选择一个随机比特b bb,b ← { 0 , 1 } b \leftarrow \{0,1\}b←{0,1}。一个密文c ← Enc k ( m b ) c \leftarrow \text{Enc}_k(m_b)c←Enck​(mb​)被计算并且给A AA。 把c cc叫做挑战密文。
  3. A 输出一个比特b ′ b'b′。
  4. 如果b = b ′ b = b'b=b′, 则为1, 否则为0 00。 如果PrivK A , Π eav ( n ) = 14 \text{PrivK}_{A,\Pi}^{\text{eav}}(n) = 14PrivKA,Πeav​(n)=14, 则称A AA成功。

定义 3.8
如果对于所有的概率多项式时间敌手A \mathcal{A}A，存在一个可忽略函数negl \text{negl}negl使得：
Pr ⁡ [ PrivK A , Π eav ( n ) = 1 ] ⩽ 1 2 + negl ( n ) \Pr\left[\text{PrivK}_{\mathcal{A},\Pi}^{\text{eav}}(n) = 1\right] \leqslant \frac{1}{2} + \text{negl}(n)Pr[PrivKA,Πeav​(n)=1]⩽21​+negl(n)
则一个对称密钥加密方案Π = ( Gen , Enc , Dec ) \Pi = (\text{Gen}, \text{Enc}, \text{Dec})Π=(Gen,Enc,Dec)具备在窃听者存在的情况下不可区分的加密，其中概率的来源是A \mathcal{A}A的随机性以及实验的随机性。

定义 3.9
如果对于所有的概率多项式时间的敌手A \mathcal{A}A，存在一个可忽略函数negl \text{negl}negl使得：
∣ Pr ⁡ [ output ( PrivK A , Π eav ( n , 0 ) ) = 1 ] − Pr ⁡ [ output ( PrivK A , Π eav ( n , 1 ) ) = 1 ] ∣ ⩽ negl ( n ) \left| \Pr\left[\text{output}\left(\text{PrivK}_{\mathcal{A},\Pi}^{\text{eav}}(n,0)\right) = 1\right] - \Pr\left[\text{output}\left(\text{PrivK}_{\mathcal{A},\Pi}^{\text{eav}}(n,1)\right) = 1\right] \right| \leqslant \text{negl}(n)​Pr[output(PrivKA,Πeav​(n,0))=1]−Pr[output(PrivKA,Πeav​(n,1))=1]​⩽negl(n)
则对称密钥加密方案Π = ( Gen , Enc , Dec ) \Pi = (\text{Gen}, \text{Enc}, \text{Dec})Π=(Gen,Enc,Dec)具有窃听者存在的情况下不可区分性。