内积加密:一次一密

题图:模拟安全题图:模拟安全题图:模拟安全题图:模拟安全题图:模拟安全
题图:模拟安全

“内积加密”系列文章的前半部分旨在总结和科普 Agrawal、Libert、Stehlé 在 2016 年提出 ALS16,Wee 在 2017 年改进 Wee17,Agrawal、Libert、Monosij、Titiu 在 2020 年完善 ALMT20 的内积加密算法。在这一篇里我们讨论如何用一次一密构造完美一次性模拟安全的(私钥)内积加密。

前情提要

第一篇 里,我们定义了一次性私钥内积加密的语法、语义、安全性。在这样一个加密体制中,密钥和密文都与某个向量关联,解密的结果是向量的内积。我们希望掌握了多个密钥的情况下,密文也只能提供明文向量中和密钥里向量的内积,而无其他;为此我们定义了两种安全性——完美保密性和模拟安全性。

本篇讨论一次一密 (one-time pad) 版内积加密 (IPFE),并证明它具有模拟安全性。另外,题图里可能把一次一密和模拟器的剪贴画对换更加准确,不过我已经用 PowerPoint 画出来了,就懒得改了。

一次一密

从一次一密的角度抽象出一次性安全的私钥 IPFE 使构造过程易于理解,要归功于 Hoeteck Wee,他构造了 Wee17 一个非常简洁的一次一密的 IPFE:

  • 抽取均匀随机的 维向量 作为
  • 生成的 的密钥为
  • 加密 时就输出密文
  • 密钥和密文都是 维向量,解密算法 就计算这两个向量的内积(作为 的内积),很容易验证

显然如果没有任何向量的密钥,则这个方案就是一次一密,具有完美安全性。在有密钥的时候呢?也是,不过我们不直接证明,而是将它作为模拟安全性的推论得出。

注意 如果加密两个向量,则该方案不再“安全”,道理同一次一密多次使用不安全。这里“安全”打引号是因为安全可以有很多种定义,就第一篇里的定义来说,完美安全和模拟安全都不考虑加密两个向量的情况,加密两个向量无论发生什么情况都不抵触第一篇里定义的安全性。严格来说,在针对加密多个向量的情况定义安全性之前,无从谈论这种情况安不安全。

模拟器

实际上 O’N10ALS16 已经知道如何构造一个不支持 询问 II(挑战后的密钥查询)的模拟器了;Wee17ACF⁺18 构造了一个不支持 询问 I(挑战前的密钥查询)的模拟器;ALMT20 首次1在文献中记载了一个适应性模拟器。

不过 ALMT20 没有像 Wee17 一样抽象出一次一密版本的模拟器,此外它的证明用到了初学者比较难以理解的撬动复杂度杠杆 (complexity leveraging),或者说适应性换元法 (adaptive change of variable)。这里我展示我原先想到的一个理念上很简单的做法——在每一步正确模拟使坏者眼中的条件分布。

注意密钥中非平凡的信息只是 密文中非平凡的信息是 只要讨论如何模拟这些即可。为了简单,模拟器状态的传递蕴含在描述中,不显式写出。

  • 初始化 之时:抽取
  • 询问 I 中:此时模拟器的输入是 记下 并返回
  • 挑战 之时:此时模拟器的输入是 其中 考虑关于 的方程组 抽取2该方程组的一个均匀随机解作为密文,记录该密文 并返回。此时可以忘记所有之前记住的 以及
  • 询问 II 中:此时模拟器的输入是 输出 作为密钥。

我们来验证模拟器的分布确实和实际分布是一样的:

  • 询问 I 中:真实世界里的密钥 就是 和某个均匀随机向量(主密钥)的内积,模拟世界里也是这样。
  • 挑战 之时:真实世界里 的分布是方程组 的一个均匀随机解(之前每次透露密钥相当于在完全均匀随机的分布上加一个条件)。而 当下的条件分布独立,3且是方程组 一个特解 (a particular solution)。因此 是方程组 的一个均匀随机解,3模拟器也是这么做的。4
  • 询问 II 中:真实世界里的密钥是 模拟器也是这么做的。

这就证明了模拟器的完美性。

1 可把我憋死了,要是这篇论文不出,这篇博文的草稿不知道要等到猴年马月才能见世。

2小学生都会的高斯消元法可以在多项式时间内求出通解,进而可以抽取一个均匀随机解。

3 对此感到怀疑的读者可以自行更加形式化地验证。

4 如果你觉得这一步论证有点怪,很可能是你潜意识里觉得模拟器必须输出 并不是这样,只要输出的条件分布正确,输出是怎么产生的无所谓。实际上,在适应性换元的观点下,可以假装有一个主密钥 并假装是用它加密了一个 它们满足 在这个视角下,询问 II 里模拟器就是在不断根据关于 的新信息对我们的假想进行修正,且修正的过程不需要修改已经公布的信息。

本篇结语

这一篇里介绍了如何用一次一密构造完美一次性模拟安全的私钥 IPFE,并构造了它的模拟器。下一篇 里我们将了解计算意义下的不可区分性 (computational indistinguishability)并定义公钥 IPFE 的语法、语义、安全性。

参考文献

ACF⁺18 Michel Abdalla, Dario Catalano, Dario Fiore, Romain Gay, and Bogdan Ursu. Multi-Input Functional Encryption for Inner Products: Function-Hiding Realizations and Constructions Without Pairings. In Hovav Shacham and Alexandra Boldyreva, editors, CRYPTO 2018, Part I, volume 10991 of LNCS, pages 597–627. Springer, Heidelberg, August 2018.
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.
O’N10 Adam O’Neill. Definitional Issues in Functional Encryption. Cryptology ePrint Archive, Report 2010/556, 2010. http://eprint.iacr.org/2010/556.
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 驱动的评论。