内积加密(线性泛函加密):引子

题图:内积加密题图:内积加密题图:内积加密题图:内积加密题图:内积加密
题图:内积加密

本篇博文是一系列关于内积加密的科普文章的首篇。该系列文章的前半部分旨在总结和科普 Agrawal、Libert、Stehlé 在 2016 年提出 ALS16,Wee 在 2017 年改进 Wee17,Agrawal、Libert、Monosij、Titiu 在 2020 年完善 ALMT20 的内积加密算法。在这一篇里我们讨论内积加密、完美保密性和完美模拟安全性的定义,并初步讨论这两种安全性之间的关系。

本来我打算在我最近一篇论文发布之后再发这篇博文的,不过今天我发现本篇的内容完全载于已有文献中,所以不用憋着了。另外这篇也顺便充当生日庆祝文🎂

2019 年 12 月 23 日更新 我发现之前我认为 Abdalla、Catalano、Fiore、Gay、Ursu 在 2018 年 ACF⁺18 完善了该内积加密算法(我以为他们证明了适应性完美模拟安全性)是误解,因此暂时重新把功劳归为我导师和我(即将发布的论文)。这篇博文已经抢发了,所以就这样搁着吧。

2020 年 2 月 19 日更新 今天 ePrint 上出来了 ALMT20,他们已经证明了内积加密的模拟安全性,所以把功劳归于他们。

内积加密

密码学 (cryptography) 在信息化的世界中不可或缺,它是保障数据安全的重要手段之一。自从 Shannon 对一次一密 (one-time pad) 完美保密性 (perfect secrecy) 的研究 Sha49 以来,现代密码学已经有了长足的发展,公钥加密 (public-key encryption) 对很多人已经是耳熟能详的概念。

在云与大数据的时代,人们希望利用服务提供商的计算能力,同时也要保障自己数据的隐私。现代密码学有(或者至少定义了)一系列工具用于各种有意思的场景,例如零知识证明 (zero-knowledge proof)多方安全计算 (multi-party computation)全同态加密 (fully homomorphic encryption)基于属性的加密 (attribute-based encryption)泛函加密 (functional encryption)程序混淆 (program obfuscation)……这里我们讨论比较简单而又不那么简单的线性泛函加密 (inner-product functional encryption),也叫内积加密 (IPFE)。(“线性泛函”是“行向量”的“大学生说法”,只是名字唬烂,概念很简单。)

内积加密是一种特殊的泛函加密,在这样一个加密体制里,密文和密钥都和向量相关联,而用密钥解密密文会得到两个向量的内积,而无其他。要研究一个密码学对象,第一步是要给出它的语法、语义的定义,第二步是给出安全性的定义,接下来便是研究各种安全性之间的关系(如果有多个安全性的定义),满足特定安全性的方案可以如何实现,以及这样一个方案有什么用等等。

在本文里,我们考虑最简单的“一次性”私钥 IPFE。我们主要感兴趣的是 上向量的内积加密,其中 是一个质数。两个 维向量 的内积定义为 严格来说,这不是(欧几里得意义下的)内积,而是线性空间与对偶空间(通过对偶基同构于自身)之间自然的双线性形式——这也是为什么我管这个加密叫做线性泛函加密的原因。

先来定义内积加密的语法,一个内积加密包括四个高效随机1算法:

  • 初始化算法 输入2质数 (的二进制表示)和向量的维数 (的一进制表示),输出主密钥
  • 密钥生成算法 用来产生任何一个向量 密钥
  • 加密算法 用来加密任何一个向量 得到密文
  • 解密算法 应该能够计算

接下来是语义,也就是所谓的正确性。内积加密方案正确,意思是说对(任意安全参数 和)任意质数 维数 以及任意 都有

1 任何方案里的“高效随机算法”都是指概率多项式时间图灵机 (probabilistic polynomial-time Turing machine)。完整的定义里,每个算法还会接收 安全参数 (的一进制表示)作为输入,不过这对信息论意义下安全的算法不是很有必要。一个数 的一进制表示就是 个 1 连着写在一起。另外,任何确定性算法也都是随机算法,以后都只考虑随机算法。

2 参见上方的链接,这种编码方式是理论计算机科学中的一个标准饶舌补丁,用来表示在正常的参数选取里, 这个数的长度以及 这个数本身分别是安全参数 的多项式。

完美保密性

朴素来说,加密算法应该保证没有密钥的人看到密文后不知道明文是什么。这里有几个问题:

  • 如何刻画不知道的含义?尤其是,如果攻击者已经知道一部分关于明文的信息时如何刻画?
  • 若攻击者已知 的密钥,那它当然可以计算明文向量和这些向量的内积,因此我们不可能保护这部分关于明文向量的信息。如何刻画“其他信息都被保护”?

常见的安全性定义对攻击者 (attacker) 的能力估计都非常保守,通常最大化攻击者可以知道的关于明文的信息,但仍有 1 bit 的关于明文的信息未知,然后刻画“攻击者无法知道这额外 1 bit 的知识”。这里最简单的刻画是完美保密性

现在我们换密码学里更常见的术语3使坏者 (adversary) 挑战者 (challenger) 考虑两个实验 示意图如下:

尝试辨别密文来自哪个明文

严格来说,实验分成 5 个阶段:

  • 初始化:使坏者 发送 挑战者 运行 并自己记下
  • 询问 I:这个阶段可以进行任意多轮,第 轮使坏者 发送一个向量 挑战者 运行 并发送
  • 挑战:使坏者选择两个向量 挑战者运行 并把 发送给
  • 询问 II:同询问 I。
  • 猜测:使坏者输出

我们要求使坏者查询过密钥的所有向量 都满足 表示让 参与实验 的输出结果,这是一个随机变量(随机性来源于 IPFE 算法的随机性和使坏者本身的随机性)。我们说这个 IPFE 方案完美保密,如果对任意 (它可以具有无限的计算能力),都有 这也记作 此外,上述等式左边的量叫做 区分 优势 (advantage)

如何理解这个定义?可以把 输出 1 的概率当成 这个算法行为的度量,那么这个定义就是在说任何算法在这两个实验里的行为都一样(即这两个实验从外部观察具有同一性 [are identical])。另一种理解是, 的输出是对 的猜测,考虑如下博弈:

  • 初始化、询问 I 和上述实验相同。
  • 挑战 之时,挑战者随机选择 生成 的密文并发送给使坏者。
  • 询问 II、猜测和上述实验相同。使坏者获胜当且仅当 即使坏者猜对了

在这样的观点下显然我们必须要求任何请求的密钥都不能(通过内积)区分两个明文向量,否则使坏者可以以 1 的概率获胜。注意到挑战者抽取到 时,使坏者参与实验 故使坏者的获胜概率和它的区分优势之间的关系是 这说明对于完美保密的 IPFE,使坏者即使已经知道密文一定来自某两个明文,且这两个明文各有先验一半的概率出现,甚至它还获得了一些密钥,只要这些密钥不能通过内积区分明文,那么使坏者的任何猜测都是瞎猜(瞎猜猜对的概率永远是

惟一的不同之处在于挑战密文里加密的明文向量不同,使坏者在这两组实验里几乎掌握了密文里蕴含的明文的所有信息,除了 1 bit 不知道——明文是它选择的两个向量中的哪一个。这个定义就是刻画:使坏者在这样“予坏人方便”的条件下仍然使不出坏。

3 这里“使坏者”的通常翻译是“敌手”,但我觉得不够可爱和接地气,我和 Ting Fung Lau 把 adversarial 译作“别有用心、一肚子坏水儿”,可以认为 adversary 尽其所能使坏,而安全性定义就要求没有使坏招数可以攻破加密算法。注意:形式化定义并没有表达该含义,因为“使坏”本身不是一个形式化概念。此外,为什么“挑战者”叫做挑战者,我个人的猜想是在通常的归约算法 (reduction) 中,归约算法面对使坏者扮演挑战者的角色,而归约算法是为了解决一个计算难题(称作挑战),有人认为这应该翻译成 被挑战者

那么再次总结:假设使坏者已经有一些关于明文的信息(通过它可以选择 刻画),即使再获得一些其他信息(通过它可以查询密钥刻画),只要新的信息不能通过该方案设计的功能(也就是计算内积)推断出关于明文的新信息,就确实无法推断任何关于明文的新信息。

我们这里没有尝试保护密钥里的向量,保护密钥里的向量的定义(和方法)留到以后的博文再分解,感兴趣的读者可以阅读 LV16Lin17

完美模拟安全性

另一种常见的安全性定义方法是利用模拟范式 (simulation paradigm)4。在这个范式里,我们想象一个使坏者偷窥正常用户产生的密文和密钥,并尝试从中计算一些信息。显然,根据 IPFE 的功能,获取了 的密钥和密文后,使坏者可以计算 这是无法避免的信息泄露。现在我们希望用一个定义刻画“只有这些信息泄露了”,这句话的形式化版本就是:任何可以通过观察密钥和密文计算出信息,都可以通过只观察内积计算出。

然而,一个观察密文和密钥的使坏者,如果对其输入内积,它很明显就会察觉到异样——输入格式都变了。为了消除密钥密文内积结果之间的鸿沟,模拟范式引入了模拟器 (simulator) 的概念。简单来说,模拟器的目的是完成使坏者进行的计算,但是它的输入是内积而不是密钥和密文。

一个无聊的结论是:完美保密的 IPFE 永远有模拟器,只是它不一定高效。

我们可以加强要求,令模拟器必须高效,但这个定义对于本身就不高效的使坏者来说没有道理。一种解决方案是:要求模拟器只能以预言机使用 (have oracle access to) 使坏者来完成计算(它不知道使坏者的代码),并且它是多项式时间带预言的图灵机 (oracle Turing machine),但是这个定义太复杂了,不太适合大众。

我们采用一个更强的定义,用一种特别的黑盒模拟:模拟器和真实算法具有类似的接口!模拟器可以生成模拟密钥模拟密文,而且只需要用能够计算的内积就可以完成模拟。一旦我们有这样一个模拟器(再加上合适的定义使得这个模拟器能够代表真实算法),那么对于任何观察密钥和密文的使坏者,我们给它看模拟密钥和模拟密文(而不是真实密钥和真实密文),它也会产生一个输出,可以证明这个输出将会和真实输出是一致的。

一个模拟器是指四个高效随机算法

  • 输入参数,输出模拟器的初始状态
  • 输入模拟器当前状态和一个向量,输出一个模拟密钥 和一个新状态
  • 输入模拟器当前状态以及若干个内积,输出一个模拟密文 和一个新状态 注意:模拟密文的时候,模拟器的输入不包括明文向量
  • 输入模拟器当前状态、一个向量、一个内积,输出一个模拟密钥 和一个新状态

模拟器当然最好是完美的,考虑一个使坏者 它可能参与两个实验——“真实实验 和“模拟实验 ——之一,表示为下图(“世界”和“实验”在这里是同义词):

与真实世界、模拟世界交互

上图应该清楚说明了为什么刚才的定义里 的模拟算法拆成了两个。实验过程是这样的:

  • 初始化:使坏者选择参数,我们用这些参数初始化真实算法或者模拟算法。
  • 询问 I:使坏者查询若干个 的密钥,我们要么生成真实密钥,要么生成模拟密钥。无论是真实算法还是模拟器,都会得到 作为输入。假设这一阶段查询了 个密钥。
  • 挑战:使坏者选择一个向量 我们要么用真实算法加密 要么用模拟器以及 (其中 生成模拟密文。注意,这里模拟器的输入不包括
  • 询问 II:类似询问 I,但在模拟世界中,模拟器额外得到 作为输入。这里给模拟器输入这个值的原因是,它是真实世界里在查询发生后可以计算的内积;另一方面,如果模拟器不知道这个信息,它是不可能模拟出正确的结果的。
  • 猜测:使坏者输出 可以理解为它猜测自己在哪个世界里,或者对使坏者(观察者)在不同世界里行为的度量。

再次强调:我们任何时刻提供给模拟器的信息都是内积加密在设计上 (by design) 应该能计算的信息,而模拟器的工作就是仅使用这些信息产生密钥和密文。这个模拟器完美,如果对任意 (可以有无限计算能力)都有 换言之,这个定义就是在说真实实验和模拟实验(从外部观察)没有差别。

另一种理解模拟范式的方法是 缸中之脑 的比喻:我们可以给使坏者(脑)营造一个它无法发现和真实世界区别的环境(缸);使坏者(脑)本来观察(“接”)的是真实世界(真实算法的输出),在模拟世界(缸)里面它“接”的管子通到模拟算法上。

用模拟范式定义安全性可以直观地刻画最终达到的效果,它基于两步论证:

  • 真实世界和模拟世界没有差别,所以真实世界里密文和密钥泄露的信息就是模拟世界里泄露的信息;
  • 模拟世界里能够泄露的信息最多就是模拟器用到的信息

这里模拟器用到的就是 IPFE 所有允许计算的信息,这就刻画了密文和密钥不包含密文里的向量、明文向量与密文里的向量的内积之外的任何信息这一命题。此外,该模拟器是适应性 (adaptive) 的,它可以回答使坏者适应性提出的任何问题,并保持模拟的完美性,这说明信息的泄露也是适应性的——在任何阶段泄露的信息就是到那个阶段为止所有被允许算出的信息。

4 模拟范式由 Goldwasser、Micali、Rackoff GMR89 引入,最初用于定义“零知识” (zero-knowledge)。对于内积加密,这个定义就是说密文、密钥里仅仅包含内积的知识。模拟范式也叫做“真实—理想范式” (real–ideal paradigm),它的基本定义思路是:在真实的密码学系统之外,定义一个理想世界(即模拟世界),在这个世界里安全是显然的(表现为模拟器的输入只有设计上允许计算的信息),然后定义一个桥接真实世界、理想世界的模拟器,并刻画真实世界和理想世界是等效的(不可区分)。

过渡证明法

之前已经说过,任何完美保密的 IPFE 都具有一个(不一定高效的)模拟器。现在自然要问:如果一个 IPFE 具有上述定义里完美的模拟器,它是否也是完美保密的?

答案是肯定,用密码学中的常见套路过渡证明法 (hybrid argument) 即可:要证明两种回答使坏者问题的方式是等价的,只要每次修改一点回答方式,保证每次修改都和前一次等价,直到从第一种修改到第二种即可。这其实就是概率等式的传递性;更一般的情况是三角不等式,不过那是后话了。

现在我们想证明 考虑下面两个过渡实验 (hybrid experiments)

  • 中,使用模拟器和 生成模拟密钥和密文来回应使坏者的查询和挑战。

中,使坏者收到的是 的真实密钥、密文,根据模拟安全性 (simulation security),用 生成模拟密钥、密文是等价的,这恰好是我们在 里的做法,因此 同理,

最后,因为我们约束使坏者的挑战和查询满足 所以 ——它们是用同一个模拟器和同一组密钥里的向量和内积生成的应答。于是得到

本篇结语

这一篇里我们定义了内积加密的语法、语义,并定义了两种安全性——完美保密性和模拟安全性。前者刻画了“密钥和密文无法用于推断明文中除了内积之外的任何新信息”,后者刻画了“密钥和密文中关于明文的信息只有内积”。此外,模拟安全性蕴含着完美保密性。

下一篇 我们会讲如何构造一个模拟安全的内积加密。

参考文献

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.
GMR89 Shafi Goldwasser, Silvio Micali, and Charles Rackoff. The Knowledge Complexity of Interactive Proof Systems. SIAM Journal on Computing, 18(1):186–208, 1989.
Lin17 Huijia Lin. Indistinguishability Obfuscation from SXDH on 5-Linear Maps and Locality-5 PRGs. In Jonathan Katz and Hovav Shacham, editors, CRYPTO 2017, Part I, volume 10401 of LNCS, pages 599–629. Springer, Heidelberg, August 2017.
LV16 Huijia Lin and Vinod Vaikuntanathan. Indistinguishability Obfuscation from DDH-Like Assumptions on Constant-Degree Graded Encodings. In Irit Dinur, editor, 57th FOCS, pages 11–20. IEEE Computer Society Press, October 2016.
Sha49 Claude E. Shannon. Communication theory of secrecy systems. Bell Systems Technical Journal, 28(4):656–715, 1949.
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 驱动的评论。