内积加密:MDDH 假设

题图:判定性 Diffie–Hellman 假设

“内积加密”系列文章的前半部分旨在总结和科普 Agrawal、Libert、Stehlé 在 2016 年提出 ALS16,Wee 在 2017 年改进 Wee17,Agrawal、Libert、Monosij、Titiu 在 2020 年完善 ALMT20 的内积加密算法。在这一篇里我们讨论一些针对 ALS 方案的准备知识:循环群、MDDH 假设。

插播新闻 加州 出现了首例 无已知与出国旅行有联系的新冠患者,目前许多密码学、量子计算学者正在访问 Simons Institute,希望大家平安!

前情提要

第一篇第二篇 里,我们定义了一次性私钥内积加密的语法、语义、安全性并用一次一密构造了完美模拟安全的一次性私钥内积加密。从 第三篇 开始,我们的话题转向公钥 IPFE,进行了语法、语义、安全性的定义。

公钥 IPFE 的安全性基于计算意义下的不可区分性 (computational indistinguishability),上回我们也提到从完美不可区分弱化为计算意义下不可区分是 必要的,运用相同的论证可以知道:若存在着 IND-CPA 的公钥 IPFE,则 这是因为在非确定性多项式时间 (non-deterministic polynomial time) 内可以轻松出主私钥,若 则主私钥也可以在多项式时间内算出,从而可以轻松区分 IND-CPA 里面的两个实验。

既然目前没有人解决 问题,那怎么可能证明一个公钥 IPFE 具有 IND-CPA 安全性呢?答案是我们需要假设一些问题难解 (intractable),这也叫做计算性假设 (computational assumption),然后证明“如果某某假设成立,则某某 IPFE 具有 IND-CPA 安全性”这种命题。

这里我们要用到的是大名鼎鼎的判定性 Diffie–Hellman 假设 (decisional Diffie–Hellman assumption),简称 DDH 假设。实际上有时它的一个变体——判定性矩阵 Diffie–Hellman 假设 (decisional matrix Diffie–Hellman assumption),即 MDDH 假设——更好用。无论是考虑哪个假设,都需要先介绍循环群 (cyclic group) 的概念。

循环群

如果读者知道什么是循环群 (cyclic group),则可以跳过这段麻瓜版1循环群说明。一个质数阶循环群 包括三个部分:

  • 集合 包含恰好质数 个元素,这里 叫做该群的 (order)
  • 一个双射 我们管 叫做 的编码,或者指数里的 ( in the exponent),而 叫做 离散对数 (discrete logarithm)
  • 一个运算 满足 对任意 成立。

用人话来说, 阶循环群允许我们对 里的元素编码,并且可以用编码运算,并且先(作为数)运算再编码等价于先编码再(作为群元素)运算。通常来说,双中括号和减号本身并不是很重要,或者在一个具体的上下文中有明确指代,这时也直接说 是循环群。

习题 出发,如何对任意 用多项式次 算出 注意 的长度是 使用 的次数应该是 的多项式。

解答

解答 注意到 写成二进制便可在多项式时间内算出所要的编码。

此外,我们还可以把 扩展到矩阵记法,考虑 矩阵的运算也可以自然定义,即 容易验证这些运算也都可只用多项式次 完成。

最后,实际上人类还是更喜欢使用 利用上面习题解答中的技巧,可以用 高效实现

1 如果你不是麻瓜却看不懂这个定义,说明还需要练习数学语言熟练度 (mathematical maturity)。(准确来说,你需要掌握如何在明知一个概念时用【另】一套拗口的形式化语言说出一个定义的技能,无论这个“明知”是形式化地知道还是 感性地知道。)

MDDH 假设

说了这么多,搞一个循环群出来有什么用呢?考虑有 很容易算出 然而这个运算过程是需要知道 作为数的写法的。如果现在只知道 则看起来没有什么好方法可以计算 ——当然,由于 是双射,总是可以还原 这两个数,但这看起来无法用多项式次 完成。

循环群的定义中刻意忽略了一些数上面容易进行的运算,从语法上 (syntactically)看起来我们只能用 和“字符串相等”来操作编码,于是导致一些整数表示下简单的问题变得困难起来。这种困难性正是密码学所需要的——当然,什么都困难也不行,毕竟密码学算法也是要有人正常使用的。我们需要一些操作是简单的,另一些问题是困难的:一个正常用户可以通过“简单”部分正常使用系统,而一个攻击者则会面对“困难”的部分。

我们要求 和映射 可以高效计算。这样通过刚才的习题,我们可以高效进行如下两件事:

  • 输入一个数,计算它的编码。
  • 输入一些(不需要知道离散对数的)编码和一些系数(以数的形式给出),计算这些编码在这些系数下的线性组合。

然而,“计算一个编码的离散对数”并不是必然容易的——实际上人们相信对于一些群来说这个问题是困难的,这叫做离散对数假设 (),简称 DLOG 假设。这个假设可以用来构造一些密码学工具,然而这里我们要用到一些更强的假设。

最直观的刻画循环群里问题困难性的方法是说“任何对编码的操作都只能是对编码的字符串相等和 调用”。这种刻画方式叫做一般群模型 (generic group model)。它和现实世界脱节比较大——比如,凭什么我不可以调用 运算到一半去看运算的中间过程?这是一个过强,甚至无法在现实世界实现 Den02 的模型。

一个常见的标准模型下的假设是 DDH 假设,它说的是两个分布的不可区分性: 其中 对于一个从未考虑过计算复杂性的人来说这个假设简直不可思议,因为这两个分布统计上非常不同:

  • 第一个分布里第三个群元素完全决定于前两个,第二个分布里第三个群元素和前两个独立且是均匀随机的。
  • 大多数来自于第二个分布的样本是不可能出现于第一个分布的。
  • 第一个分布的熵是 第二个分布的熵是

的确,一个运行指数时间的使坏者可以轻松区分两个分布,然而对于一些循环群,人们相信2 DDH 假设是成立的——目前没有发现任何技巧可以在多项式时间内以不可忽略的优势区分两个分布。

DDH 假设的推广是 MDDH 假设。令 是一个常数, 是多项式, 假设是说如下两个分布不可区分: 其中

注意,当 超过任何多项式时,这个假设无条件成立——那两个分布统计意义下不可区分。但如果 必须超过任何多项式才有意义(否则可以计算离散对数,从而容易区分)。如果不提 这种情况下:

  • 第一个分布中 的行空间里,第二个分布中 几乎一定不在 的行空间里。
  • 如果把第二部分和 拼成一个大矩阵,则第一个分布里这个矩阵的 (rank) 几乎一定是 (从而不可逆),而第二个分布里这个矩阵的秩几乎一定是 (从而可逆)。
  • 第一个分布的熵远远低于第二个。

我们将会看到,这些魔法般的假设可以帮助我们实现安全的公钥密码系统。

2 仅针对经典计算机。量子计算机可以在多项式时间内算出离散对数,从而轻松区分 DDH 假设(以及后面的 MDDH 假设)里的两个分布。

小试牛刀

我们现在举一个使用计算性假设和多项式时间归约 (polynomial-time reduction) 来证明安全性的例子。考虑经典的 ElGamal 加密 EG84

  • 一个用户的私钥是 公钥是
  • 加密 时生成 并输出
  • 解密时输出

我们证明它的 SIM-CPA 安全性——定义类似 IPFE 的 SIM-CPA,但不存在询问 I/II 环节,模拟器只需要生成模拟公钥和一个模拟密文(不知道明文的情况下)。这个模拟器十分简单:抽取 并输出 作为模拟公钥,以及 作为模拟密文。

显然,这个模拟器“完全玩坏了”,因为它的输出和真实密文分布相去甚远(例如明文是 的情况,一个随机的 几乎不可能恰好等于 然而不要紧,SIM-CPA 只要求真实世界和模拟世界在计算意义下不可区分,若 DDH 假设成立,则可以证明这个模拟器🉑。

证明

证明 考虑一个对抗 SIM-CPA 的使坏者 构造如下对抗 DDH 的使坏者

  1. 接收 DDH 挑战 其中 或是随机。
  2. 运行 并给它公钥
  3. 提交密文挑战 时,提供密文
  4. 的输出作为输出。

如果 收到的是 处于真实世界里;否则, 收到的回应符合模拟世界的分布;故 对抗 DDH 的优势等于 对抗 SIM-CPA 的优势,由于 DDH 假设成立, 的优势只能可忽略,故 ElGamal 加密具有 SIM-CPA 安全性。

读者习题 1 证明 DDH 假设蕴含着 假设。(若 DDH 假设里的两个分布不可区分,则 假设里的两个分布也不可区分。)

提示

提示 去证明 其中各个变量在 上独立均匀随机。第一步可以归约为 DDH 假设,抽取 并作映射 注意 可以由归约算法自己计算。分析 随机和 情况下,右边的像服从什么分布。第二步比较简单——统计意义下不可区分。

扩展阅读 不存在一个黑盒归约 (black-box reduction)(这个归约需要黑盒使用对抗 的使坏者并且黑盒使用群运算)将 DDH 归结为 BMZ19

读者习题 2 证明 假设蕴含着 假设,其中 是任意取值为正整数的多项式。

提示

提示 可以通过抽取 并作映射 来证明,其中要么 要么 随机。

可以通过在 各行上用过渡证明法完成。

扩展阅读 这个做法带来的优势损失不够优,目前最紧的归约见 EHK⁺17

本篇结语

这一篇里我们介绍了循环群和 MDDH 假设,并练习了如何在计算性假设的前提下证明不可区分性。至此,理解 ALS16 IPFE 方案的准备工作终于搞定了,下一篇 将会是上半部分的末篇,我们叙述 ALS 的构造并证明它的 SIM-CPA 安全性。

参考文献

ALMT20 Shweta Agrawal, Benoı̂t Libert, Monosij Maitra, and Radu Titiu. Adaptive Simulation Security for Inner Product Functional Encryption. Cryptology ePrint Archive, Report 2020/209, 2020. To appear in PKC 2020, available at https://eprint.iacr.org/2020/209.
ALS16 Shweta Agrawal, Benoı̂t Libert, and Damien Stehlé. Fully Secure Functional Encryption for Inner Products, from Standard Assumptions. In Matthew Robshaw and Jonathan Katz, editors, CRYPTO 2016, Part III, volume 9816 of LNCS, pages 333–362. Springer, Heidelberg, August 2016.
BMZ19 James Bartusek, Fermi Ma, and Mark Zhandry. The Distinction Between Fixed and Random Generators in Group-Based Assumptions. In Alexandra Boldyreva and Daniele Micciancio, editors, CRYPTO 2019, Part II, volume 11693 of LNCS, pages 801–830. Springer, Heidelberg, August 2019.
Den02 Alexander W. Dent. Adapting the Weaknesses of the Random Oracle Model to the Generic Group Model. In Yuliang Zheng, editor, ASIACRYPT 2002, volume 2501 of LNCS, pages 100–109. Springer, Heidelberg, December 2002.
EG84 Taher ElGamal. A Public Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms. In G. R. Blakley and David Chaum, editors, CRYPTO’84, volume 196 of LNCS, pages 10–18. Springer, Heidelberg, August 1984.
EHK⁺17 Alex Escala, Gottfried Herold, Eike Kiltz, Carla Ràfols, and Jorge Luis Villar. An Algebraic Framework for Diffie-Hellman Assumptions. Journal of Cryptology, 30(1):242–288, January 2017.
Wee17 Hoeteck Wee. Attribute-Hiding Predicate Encryption in Bilinear Groups, Revisited. In Yael Kalai and Leonid Reyzin, editors, TCC 2017, Part I, volume 10677 of LNCS, pages 206–233. Springer, Heidelberg, November 2017.

请启用 JavaScript 来查看由 Disqus 驱动的评论。