动机
公钥加密规则必须让任何人都能构造密文,却不能让每个人都能解密。确定性加密立刻带来一个问题:观察者可以对两个猜测的明文分别加密,再与挑战密文比较。随机性可以防止这种直接比较,但仅仅说密文“看起来是随机的”并不是证明。我们需要一个明确规定的实验,以及一个把该实验与某个困难数学问题联系起来的明确假设。
ElGamal 提供了一个清晰的例子。它的解密等式来自循环群中指数的交换律。它的保密性论证则使用一个更强且独立的断言:某个特定的共享群元素在计算上应与一个独立的均匀群元素不可区分。把这个共享元素换成随机掩码之后,挑战明文就从其分布中消失了。
我们证明这一条件性陈述,其中包括用固定的有界个公平比特来实现随机指数。这里的明文是群元素。我们不构造任意字符串的编码、带认证的系统,也不构造已部署的参数集;这些都需要进一步的定义与构造。
定义
对每个正的安全参数 ,假设给定一个素数阶 的循环群 。它的描述以及定长的群元素规范编码的长度都是 的多项式。乘法、求逆、成员判定以及用二进制整数作指数的幂运算都在多项式时间内完成。 的比特长度受多项式限制。这些是明确的群族假设;本章既不构造这样的群族,也不证明其困难性。
定义 4.2.1
(判定性 Diffie–Hellman 假设)
离散对数问题是由 求 。计算性 Diffie–Hellman 问题是由 求 。判定性 Diffie–Hellman 假设(DDH)是指:没有任何有界概率多项式时间算法能以不可忽略的优势区分分布
其中 在 中独立均匀取值。优势定义为输出为一的两个概率之差的绝对值。若对每个正整数 ,函数最终都至多为 ,则称该函数是可忽略的。这里的理想分布是数学实验;我们并不声称用有界的公平比特带可以从奇数大小的集合中精确采样。
定义 4.2.2
(ElGamal 加密)
理想的加密规则是
其中 。对于正确性,任何 都是允许的。有界比特实现则用下面所证明的程序来采样秘密 和每个新的随机数 。
概念视角结构
Diffie–Hellman 交换之后接一个群上的一次一密
ElGamal 是一次临时的 Diffie–Hellman 交换,再接一个乘法掩码。新鲜的 与公开的 决定共享元素 :发送者把它算成 ,接收者把它算成 。消息被掩码为 ,这是群 上的一次一密,再乘以 便去掉掩码。安全性证明把共享元素换成一个独立的均匀元素;到了那一步,这个掩码就完美地隐藏了 。
定义 4.2.3
(选择明文不可区分性实验)
在选择明文不可区分性实验中,敌手收到 ,选择两个合法的群明文 ,并保留任意多项式大小的状态。挑战者选取一个新的公平比特 ,用新的随机数加密 ,再让敌手猜测 。其优势为 。敌手可以自己进行任意多项式次数的公开加密;在这一公钥实验中不需要秘密的加密预言机。不提供解密预言机。
定理/命题
定理 4.2.4
(正确性与有界比特指数采样)
ElGamal 能把其加密规则产生的每个合法密文解密为原来的群明文。此外,若 ,则把一个 比特均匀整数模 约化,得到的分布在全变差距离下与 上的均匀分布相差不超过 ,且运行时间有固定的多项式上界。
定理 4.2.5
(选择明文保密性由 DDH 推出)
对每个有界概率多项式时间的选择明文敌手 ,存在这样的 DDH 区分器 ,使得
对上述有界比特实现成立。因此 DDH 蕴含可忽略的选择明文优势。该定理断言的是在所指定实验中的机密性;它并不断言选择密文安全性或密文完整性。
证明思路或证明
正确性是一个代数恒等式
证明
(指数恒等式)
对于合法密文,。因此 。解密时不需要计算任何对数。秘密指数允许对收到的第一分量作幂运算;它并不是从任意群元素中提取指数的方法。当任一指数为零时该公式仍然正确,不过这些罕见的选择可能暴露消息,必须计入安全性实验的概率核算之中。
用有界公平比特近似均匀指数
证明
(计算原像并比较实验)
令 。模 的每个剩余类在这 个整数中恰有 或 个原像。因此其概率与 之差小于 。按全变差距离定义为绝对差之和的一半,所得距离至多为 。在所述规模假设下,抽取 个公平比特并做整数除法的代价是有界的多项式。
我们还要用到全变差的两个初等推论。对两个分布施加共同的确定性或随机化后处理不会使它增大:对任一输出事件,把其条件概率(介于零与一之间的数)分别对两个输入分布取平均即可。把两次独立抽样(各自与其理想分布相差不超过 )替换后,联合分布至多改变 ,做法是一次替换一个抽样并使用三角不等式。即使后面的消息依赖于较早的抽样,这些陈述仍然成立。
把它们应用到密钥指数与挑战随机数上。用同一个敌手代码、它的随机硬币以及挑战比特,对两个完整实验进行耦合或比较。转录与最终成功事件的概率至多相差 。敌手内部进行的公开加密只是同一个随机化后处理的一部分,因此那里不需要未经说明的精确非二进制采样。
把敌手嵌入 DDH 检验
证明
(把敌手变成区分器的包装)
先分析理想指数实验。给 一个来自两种 DDH 分布之一的三元组 。它把 作为公钥发给 ,获得其两条消息和状态,选取一个新的公平比特 ,并把密文 交给 。当 猜对 时,区分器恰好输出一。所有包装操作都是高效的,而且 从不计算未知指数。
对于真实的 Diffie–Hellman 三元组, 且 。于是模拟出的密文恰好具有理想的加密分布, 以该实验的成功概率输出一。
对于独立三元组, 在群中均匀分布,并且独立于公钥、、所选消息和敌手状态。在这些数据以及 的任一取值的条件下,乘以 是群上的双射。因此 是均匀的,且两种选择下具有相同的分布。完整视图不泄露关于新比特的任何信息,每个猜测策略的成功概率恰为二分之一。所以,按我们的绝对值约定,两个输出为一的概率之差恰是理想选择明文优势。
最后,用前面的 界把有界比特实现与理想实验进行比较。三角不等式即给出该定理。在假设下,加性的统计项是可忽略的,DDH 优势也是可忽略的;它们之和是可忽略的。这里证明的是对生成密钥取平均的概率界,并不是保证每一个可能的密钥都具有同样的保密性。
证明透视
归约并没有解决 Diffie–Hellman 问题
挑战三元组的每个分量各有一个用途。 成为公钥, 成为密文第一分量,所以敌手看到的密钥与随机数恰好具有理想分布。第三分量 只用作消息掩码;包装程序从不需要 、 或 ,所以它能高效运行,也因此并没有证明任何求解 Diffie–Hellman 的能力。
关键一步是随机分支。 独立于 、、所选消息与敌手状态,使 对 的两个取值都均匀,所以该分支中的成功概率恰为二分之一;仅有 的边际均匀性并不足够。论证以相减收尾:区分器的优势等于理想选择明文优势,而有界比特采样经三角不等式再加上 。
例题详解
例题 4.2.6
(一个完整的玩具加密与解密)
在模二十三下,取由二生成的子群。由于 且二不等于一,这个子群的素数阶为十一。取秘密 ,公钥 ,消息 ,随机数 。于是 ,,。密文为 。
解密计算 。它模二十三的逆元是十二,所以 ,即原来的消息。对十一个指数的穷举搜索立即就能攻破这个玩具群。它只说明代数上的正确性,并不为渐近的 DDH 假设提供任何证据。
例题 4.2.7
(重复使用随机数会泄露消息之比)
用同样的密钥和随机数加密消息四和八。密文为 与 。它们第二分量之比 等于消息之比 。一般地,重复使用 会给出 。若其中一条消息已知,另一条通过乘法即可恢复。独立的新随机数是实验的明确组成部分;解密的正确性不能弥补随机性假设的失败。
例题 4.2.8
(一次有意的密文修改)
把第二分量乘以二,将 改为 。它解密为八,即原消息的两倍。更一般地,对每个已知的 , 解密为 。
这给出一个选择密文攻击:收到挑战 后,选取 ,向解密预言机询问不同的密文 。把它的回答除以 即得到挑战消息,进而对不同的两条消息得知所选的比特。该询问不同于被禁止的挑战密文,所以仅仅禁止这个确切的询问并不能阻止此攻击。选择明文定理仍然有效,因为它的游戏中没有提供这样的预言机。
常见错误
反例模式
被掩蔽群以外的消息
均匀掩码论证使用的是乘法在确切的消息群上的双射性。设在上面的玩具例子中允许消息来自环境群 ,其中 的阶为十一。取 与 。由于 ,元素 不在 中。每个密文都有 ,其中 ,所以不论密钥与随机数为何, 时 , 时 。一次幂运算便确定地恢复 。修正正是定理的假设:两条挑战消息都必须属于 。任意比特串需要另行分析的编码或混合构造。
常见错误
(DDH 是计算性的,不是统计性的)
DDH 是一个计算性不可区分假设,并不是说 Diffie–Hellman 三元组在统计上是均匀的:无界的观察者可以恢复指数并加以检验。此外,离散对数求解器可得到共享秘密求解器,后者又可得到判定检验;这些容易的方向并不能证明相反方向的等价性。最后,带认证的通信系统需要对修改提供进一步的保护,正如这个明确的攻击所展示的那样。
常见错误
(新的不等于永不重复)
“新的随机性”指的是一个新的独立样本,而不是承诺某个值永远不会再次出现。在理想的均匀采样下,两次随机数抽样相同的概率为 ;对 次抽样取并集界,碰撞概率至多为 。有意重复使用已存储的随机数则是另一个过程,独立性论证不再适用。
总结
加密等式对每个指数都证明了正确性。一个精确陈述的 DDH 假设,通过把共享值替换为均匀群掩码的包装器,证明了选择明文机密性。有界比特的指数生成引入了一个明确可忽略的统计误差。这些陈述都不能阻止乘法式的密文修改,也不能解决其余的编码与认证问题。
练习
快速检查
(解释为什么确定性的、公开可计算的、正确的加密在对不同明文的双消息挑战实验中会失败。)
解答
对两条所选消息分别加密,并将挑战与这两个输出比较。正确的解密蕴含这两个密文不同:否则一个密文必须同时解密为两条消息。因此比较可以确定地恢复比特,按我们的约定优势为二分之一。
快速检查
(当秘密指数为零时,ElGamal 密文会发生什么?为什么这一观察本身并不能反驳取平均密钥的定理?)
解答
此时公钥为一,第二分量等于明文。在理想分布下这个密钥出现的概率为 ,是可忽略的。该定理是对生成的密钥取平均的,可以允许一个可忽略的例外集合。它并不为被有意选取的零密钥确立安全性。
快速检查
(为什么证明必须要求替换掩码独立于公钥和挑战的第一分量,而不仅仅是边缘分布上均匀?)
解答
边缘均匀性在取条件后不一定保持。例如,一个等于另一个公开均匀群元素的均匀掩码,在观察到那个元素之后就完全已知。随机 DDH 实验提供了条件均匀掩码论证所需的更强的独立性。
快速检查
(若每个指数采样器与均匀分布相差不超过 ,则定理中的统计项 应换成什么?)
解答
一次一个地替换密钥抽样和挑战随机数抽样。三角不等式以及在共同敌手计算下的收缩性给出成功概率的总变化至多为 。因此同一归约给出 DDH 优势加上 ;只有当这个统计项本身可忽略时,才能推出可忽略性。