内积加密：一次一密

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

前情提要

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

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

一次一密

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

• $\mathsf{S}\mathsf{e}\mathsf{t}\mathsf{u}\mathsf{p}$ 抽取均匀随机的 $n$ 维向量 $\mathbf{w}\stackrel{{}_{\$}}{\leftarrow }{\mathbb{Z}}_p^n$ 作为 msk。
• $\mathsf{K}\mathsf{e}\mathsf{y}\mathsf{G}\mathsf{e}\mathsf{n}$ 生成的 $\mathbf{v}$ 的密钥为 (−wTvv​)。
• $\mathsf{E}\mathsf{n}\mathsf{c}$ 加密 $\mathbf{u}$ 时就输出密文 (1,wT+uT)。
• 密钥和密文都是 $n+1$ 维向量，解密算法 $\mathsf{D}\mathsf{e}\mathsf{c}$ 就计算这两个向量的内积（作为 $\mathbf{u},\mathbf{v}$ 的内积），很容易验证 $$(1,{\mathbf{w}}^{\text{T}}+{\mathbf{u}}^{\text{T}})\left(\begin{array}{c}-{\mathbf{w}}^{\text{T}}\mathbf{v}\\ \mathbf{v}\end{array}\right)={\mathbf{u}}^{\text{T}}\mathbf{v}.$$

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

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

模拟器

实际上 [O’N10, ALS16] 已经知道如何构造一个不支持 询问 II（挑战后的密钥查询）的模拟器了；[Wee17, ACF⁺18] 构造了一个不支持 询问 I（挑战前的密钥查询）的模拟器；[ALMT20] 首次¹在文献中记载了一个适应性模拟器。

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

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

• 在 初始化 之时：抽取 w←$​Zpn​。
• 在 询问 I 中：此时模拟器的输入是 vq​。记下 ${\mathbf{v}}_q$ 并返回 yq​=wTvq​。
• 在 挑战 之时：此时模拟器的输入是 zq​=(u∗)Tvq​，其中 q=1,…,Q1​。考虑关于 $\mathbf{x}$ 的方程组 $${\mathbf{x}}^{\text{T}}{\mathbf{v}}_q=y_q+z_q\forall q=1,\dots ,Q_1,$$ 抽取²该方程组的一个均匀随机解作为密文，记录该密文 $\mathbf{x}$ 并返回。此时可以忘记所有之前记住的 ${\mathbf{v}}_q$ 以及 w。
• 在 询问 II 中：此时模拟器的输入是 vq​,zq​=(u∗)Tvq​。输出 ${\mathbf{x}}^{\text{T}}{\mathbf{v}}_q-z_q$ 作为密钥。

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

• 在 询问 I 中：真实世界里的密钥 $y_q$ 就是 ${\mathbf{v}}_q$ 和某个均匀随机向量（主密钥）的内积，模拟世界里也是这样。
• 在 挑战 之时：真实世界里 $\mathbf{w}$ 的分布是方程组 $${\mathbf{w}}^{\text{T}}{\mathbf{v}}_q=y_q\forall q=1,\dots ,Q_1$$ 的一个均匀随机解（之前每次透露密钥相当于在完全均匀随机的分布上加一个条件）。而 ${\mathbf{u}}^{\ast }$ 和 $\mathbf{w}$ 当下的条件分布独立，³且是方程组 $$({\mathbf{u}}^{\ast }{)}^{\text{T}}{\mathbf{v}}_q=z_q\forall q=1,\dots ,Q_1$$ 的一个特解 (a particular solution)。因此 $\mathbf{x}=\mathbf{w}+{\mathbf{u}}^{\ast }$ 是方程组 $${\mathbf{x}}^{\text{T}}{\mathbf{v}}_q=y_q+z_q\forall q=1,\dots ,Q_1$$ 的一个均匀随机解，³模拟器也是这么做的。⁴
• 在 询问 II 中：真实世界里的密钥是 $$y_q={\mathbf{w}}^{\text{T}}{\mathbf{v}}_q=(\mathbf{x}-{\mathbf{u}}^{\ast }{)}^{\text{T}}{\mathbf{v}}_q={\mathbf{x}}^{\text{T}}{\mathbf{v}}_q-z_q,$$ 模拟器也是这么做的。

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

本篇结语

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

参考文献