内积加密:双槽内积加密

0
题图:双槽内积加密

欢迎来到“内积加密”系列文章的后半部分,这部分科普 Lin 与 Vaikuntanathan 在 2016 年提出 LV16 的内积加密算法。终于是最后一篇了,我们说说双槽内积加密。

4 月 13 日更新 最近读到了黄健宏的博文《翻译笔记之四:消除人称代词》,整改了一下这个系列科普文章里的“我们”。我汉语写作翻译腔很重,大概是因为我中小学时对语文不上心吧,现在后悔真的有点儿来不及了。

前情提要

在“内积加密”系列文章的 前半部分 介绍了内积加密的定义和构造。后半部分的前两篇 定义了泛函保密性构造了这样的 IPFE

这一篇讲双槽内积加密(双槽 IPFE),这是 LV16Lin17 提出的一个概念,它同时推广了私钥 IPFE 和公钥 IPFE,并且针对它也可以定义泛函保密性。利用 ALS16 和双层加密法可以构造具有泛函保密性的双槽 IPFE。这一篇里的构造是 LL20 的改进版(具有更紧的安全归约)——不过这个改进实在是太无聊了,它应该不会出现在正式的文献里。

定义双槽 IPFE

在公钥 IPFE 中,任何人都可以加密任何向量,只有主私钥持有者才能生成密钥;在私钥 IPFE 中,加密也需要持有主私钥,也就是说一般人什么都不能加密。在双槽内积加密 (slotted inner-product functional encryption) 里,向量被分成了两个部分,分别叫“公有槽” (public slot) “私有槽” (private slot)公有槽类似于公钥 IPFE,任何人都能加密任何向量;私有槽类似私钥 IPFE,加密需要主密钥。

这里只考虑使用双线性映射 (bilinear map) 的双槽 IPFE,它包含五个高效算法:

  • 用于初始化公有槽维数是 私有槽维数是 的实例,它输出主密钥对
  • 输出 的密钥
  • 输出 的密文 注意这个算法输入的是主私钥
  • 需要计算内积在 的编码。
  • 是公有槽的加密算法,它需要只用主公钥就能加密

双槽 IPFE 需要有两个正确性保证。一是私钥模式下正确 (correct in private mode),即“加密、产生密钥之后再解密,得到的确实是内积”,这一点读者应该很熟悉了:对任意 和任意 二是槽模式正确性 (slot-mode correctness)1,实际上这算是半个2安全性,它要求 效果完全等同于 对任意 和任意 下述两个分布是同一个分布 (are identical)3

双槽 IPFE 同时具有公钥 IPFE 和私钥 IPFE 的功能:令 则得到公钥 IPFE;相反,若令 则得到私钥 IPFE。这种方式得到的方案叫做双槽 IPFE 所诱导的 (induced by …)4方案。

接下来刻画安全性。在不可区分意义下,显然 密钥里的公有槽 不可能受到任何保护,但其他部分仍然可以受到保护。接下来定义针对双槽 IPFE 的泛函保密性 (function-hiding),它要求除了 都受到保护(即最佳可达安全性 [best possible security])。定义方式就是把公钥 IPFE 的 IND-CPA 和私钥 IPFE 的 IND-FH 结合起来,仍然是两个实验 为了庆祝终于到最后一篇了,我又画了一次流程图:

的定义

当然,这里要求对任意

对比 双槽 IPFE 的 IND-FH 和公钥 IPFE 的 IND-CPA 定义类似之处在于使坏者可以获得 且密文挑战里明文向量可以变化;和私钥 IPFE 的 IND-FH 类似之处在于密钥挑战里密钥里向量的私有槽可以变化,且密文、密钥挑战可以随意交替、进行任意多次。由于双槽 IPFE 的私有槽只有持有 才能加密,故需要允许多次挑战才能刻画私有槽的多次安全性

之前说过双槽 IPFE 通过设置公有槽、私有槽的长度为零可以(从语法和语义上)退化为私钥、公钥 IPFE,安全性也是如此:如果考虑 时双槽 IPFE 的 IND-FH,它恰好就是它诱导的私钥 IPFE 的 IND-FH;若 则双槽 IPFE 的 IND-FH 就是它诱导的公钥 IPFE 的 IND-CPA(密钥里向量的私有槽没得选)。

一个自然的问题是:为什么要定义这么一个“怪胎”?这个东西对于外行人 (lay-people) 来说很不自然。不过,以后我们会看到它对于“双模式”型安全证明非常有用,提前剧透就是:公有槽用来实现正常功能(不使用私有槽),私有槽用来进行安全证明,利用 IND-FH 可以在两个槽之间切换。

1 作为术语的创造者(定义不是新的,不过它在 LV16 它叫做“公钥加密在统计意义下不可区分” [statistically indistinguishable public encryption])和翻译者,我要强调这个短语并不是“槽模式正确”,这里“槽模式”指的是两种加密的模式——私钥模式和公钥模式——而“正确性”是指两种加密模式的等价性,不是“解密结果正确”。当然私钥模式下正确且具有槽模式正确性的方案自然也在公钥模式下正确。

2 之所以说这是“半个安全性”,是因为这个定义是在说:即使加密时使用了主私钥,只要私有槽为零,则相当于没用过主私钥。

3 这个定义里分布包括主密钥,并且要求的是完美不可区分性,这是一个很强的要求,对于后续在密码学方案里的需求,弱化版本就足够了(如不需要对主私钥持有者不可区分,以及只需要计算意义下不可区分等)。

4 induced by … 另一个常见翻译为“…所导出的”,例如线性方程组把常数项替换为零后得到的齐次线性方程组叫做它的“导出组”,又例如“由内积所诱导的范数”,或者“导出子图”“诱导子图”。

构造双槽 IPFE

叨哔叨了这么多,该构造具有 IND-FH 安全性的双槽 IPFE 了。套路和上次一样,使用 双层加密 以及给私有槽的维数翻番以便 玩“空当接龙”,不同之处在于外层方案加密的不是内层密钥,而是公有槽本身接上私有槽的内层密钥。构造主体上和 LL20 里的一样,不过为了一个无聊的优化,我们需要给内层方案 搞搞飞机

具体来说,内层方案是 维,外层方案是 5维。总方案的密钥对是 以及 其中 总方案里 的密钥是 总方案里 的密文这样生成: 换言之, 可以在前半段也可以在后半段,取决于 解密的话自然就是调用外层解密,利用加密、密钥生成保持内积的性质自动解密内层方案,从而得到正确结果。最后, 算法就是运行 槽模式正确性是因为 ALS16 方案里零向量的密文是零向量。

这里弄一个 是为了缩短过渡证明法里的过渡实验数量,从而减少归约产生的安全损失,利用的是 耦合 (coupling) 的技巧。具体来说,我的证明会把 的情况对应到 的情况;由于 分别均匀随机,这样做没问题。

下面列出 的过渡实验(另一种情况只要把内层方案的前后两段倒过来即可),其中 表示 产生的密钥或者 产生的密文:

过渡实验 密钥应答 密文应答

这里 可以归约为内层方案的 IND-CPA,因为改变的部分是内层方案的明文向量,且改变的部分只和内层密钥里的零相乘; 可以归约为外层方案的 IND-CPA,利用 IND-FH 实验里的约束。

扩展阅读 使用 ALS16 方案构造上述双槽 IPFE 时,这个无聊优化不是很重要(等等,它甚至有些时候重要?),因为初始方案对于多重挑战 IND-CPA 安全性不紧 (not tightly secure),安全损失和挑战密文数量 成正比,因此归约到多重 IND-CPA 时损失 3 还是损失 5 就不那么重要了。感兴趣的读者可以阅读 Tom19 了解如何6构造紧安全的 IPFE。

5 上次我没有明确说内外层方案的维数。这里内层方案的维数很好理解,外层方案的维数里的 是 MDDH 假设里面的 回忆 ALS16 方案,它的密文、密钥分别是 维向量(密文用群编码)。

6 我没仔细看过这篇论文,不过一个显然的构造紧安全公钥 IPFE 的思路是这样的:注意 ALS16 具有线性同态性且可以完美重随机化 (rerandomize) 密文,于是有意义的密文挑战数量至多是维数的两倍——其他密文挑战和它们线性相关,因此使坏者可以自己用其他挑战的应答线性组合再重随机化等效得到挑战应答。这就可以把归约到 MDDH 的损失控制在维数的两倍,至于能不能让损失和维数无关,我就没去想了。

本篇结语

这一篇讨论了双槽 IPFE 的定义和安全性,并利用类似前一篇里的技巧构造了泛函保密的双槽 IPFE。

这个系列里的“高级原语”(advanced primitives) 是通过安全组合“简单原语”(simple primitives) 获得的,是密码学里模块化构造很好的例子。另外,在我的这几篇博文里,概念介绍(尤其是最开始的部分里安全定义)的篇幅远远超过方案构造的篇幅,最后这一篇里构造和证明差不多也就一页 A4 纸。这有多方面原因:

  • 概念、定义是密码学发展的重要部分,自然应该有与之匹配的篇幅。
  • 拥有概念、定义就是 掌握了方便的词汇,值得用笔墨。
  • 我有一点强迫症,希望科普所写正确、准确(在某种对“正确”的刻画下)。
  • 我希望避免我的文章给读者错误印象——一些“入门前密码学”科普的通病是令读者产生甚至文章本身默认某些“这样做具有安全性”的错误直觉

当然结果就是这些文章看起来比较难啃,不知以后能否找到兼顾通俗和正确、准确的平衡点。总之,“内积加密”系列告一段落,感谢观赏。

参考文献

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.
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.
LL20 Huijia Lin and Ji Luo. Compact Adaptively Secure ABE from -Lin: Beyond and towards . Cryptology ePrint Archive, Report 2020/318, 2020. To appear in Eurocrypt 2020, available at https://eprint.iacr.org/2020/318.
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.
Tom19 Junichi Tomida. Tightly Secure Inner Product Functional Encryption: Multi-input and Function-Hiding Constructions. In Steven D. Galbraith and Shiho Moriai, editors, ASIACRYPT 2019, Part III, volume 11923 of LNCS, pages 459–488. Springer, Heidelberg, December 2019.

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