内积加密：双层加密、三仙归洞与空当接龙

欢迎来到“内积加密”系列文章的后半部分，这部分科普 Lin 与 Vaikuntanathan 在 2016 年提出 [LV16] 的内积加密算法。在第二篇里，我们说说如何构造具有泛函保密性的私钥 IPFE 以及它的安全性证明。（本来计划的双槽内积加密推到第三篇了。）

前情提要

在“内积加密”系列文章的 前半部分 介绍了内积加密的定义和构造。后半部分的 第一篇 解释了为什么泛函保密性只对私钥 IPFE 有意义，并基于不可区分性定义了泛函保密性，然后还引入了新工具——双线性映射。

这一篇我们通过双层加密构造一个 IND-wFH 的 IPFE，然后把它变成一个 IND-FH 的 IPFE。这里的方法归功于 [LV16]，顺便一提，这个方法在 [Lin17] 里又比较完整地写过一次，所以文献中也有 [ACF⁺18, Tom19] 管这个技巧叫做 Lin’s technique 的。

改造 ALS 方案

首先回忆 [ALS16] 公钥 IPFE 的构造，它有几个特殊性质：

• $\mathsf{E}\mathsf{n}\mathsf{c}$ 的输入是群编码的向量，输出也是群编码的向量。
• $\mathsf{K}\mathsf{e}\mathsf{y}\mathsf{G}\mathsf{e}\mathsf{n}$ 是 $\mathbf{v}$ 的线性函数，且系数容易用数字形式写出（就是主密钥）。
• $\mathsf{D}\mathsf{e}\mathsf{c}$ 只是计算 $\mathsf{c}\mathsf{t}$（所编码的向量）和 $\mathsf{s}\mathsf{k}$ 的内积（的群编码）。

由于系数是数字的线性运算总是可以在群编码中进行，这说明可以稍微改造一下 [ALS16] 方案，让密钥里的向量和密钥本身也都用群编码，此时解密算法只需要利用双线性映射 (bilinear map) 即可算出内积（在目标群 [target group] 中的编码）。为了方便忘性比较大的读者，这里简述一下改造后的方案：

• $\mathsf{S}\mathsf{e}\mathsf{t}\mathsf{u}\mathsf{p}(1^n)$ 输入向量维数 n，它输出 mpk=[[A,AW]]1​,msk=W，其中 $\mathbf{A},\mathbf{W}$ 是随机矩阵，型 (shape) 分别是 k×(k+1),(k+1)×n。
• $\mathsf{K}\mathsf{e}\mathsf{y}\mathsf{G}\mathsf{e}\mathsf{n}(\mathsf{m}\mathsf{s}\mathsf{k},[[\mathbf{v}{]]}_2)$ 输入 $G_2$ 编码的向量 v，输出 (−W[[v]]2​[[v]]2​​)。
• $\mathsf{E}\mathsf{n}\mathsf{c}(\mathsf{m}\mathsf{p}\mathsf{k},[[\mathbf{u}{]]}_1)$ 抽取 $\mathbf{s}\stackrel{{}_{\$}}{\leftarrow }{\mathbb{Z}}_p^k$ 并输出 (sT[[A]]1​,sT[[AW]]1​+[[uT]]1​)。
• $\mathsf{D}\mathsf{e}\mathsf{c}$ 通过双线性映射计算内积： $$\begin{array}{r}\cancel{[[{\mathbf{s}}^{\text{T}}\mathbf{A}{]]}_1[[-\mathbf{W}\mathbf{v}{]]}_2}+[[\cancel{{\mathbf{s}}^{\text{T}}\mathbf{A}\mathbf{W}}+{\mathbf{u}}^{\text{T}}{]]}_1[[\mathbf{v}{]]}_2=[[{\mathbf{u}}^{\text{T}}\mathbf{v}{]]}_{\text{T}}.\end{array}$$

这样调整后的构造仍然保持 IND-CPA（假设 ${\text{MDDH}}_k$ 在 $G_1$ 里成立；可以归约为改造前方案的 IND-CPA），且之前的特殊性可以总结如下：

• 加密、生成密钥分别保持编码方式不变。
• 加密、生成密钥合在一起保持内积不变。

双层加密

注意到上面修改后的 [ALS16] 构造里，$G_1,G_2$ 的地位几乎对等——除了安全性需要 ${\text{MDDH}}_k$ 在 $G_1$ 里成立之外，完全可以交换两个源群 (source groups) 的地位（即改用 $G_2$ 编码明文、密文，$G_1$ 编码密钥里的向量和密钥）。如果假设 ${\text{MDDH}}_k$ 在 $G_1,G_2$ 里分别成立，则这个构造给出两个具有 IND-CPA 的公钥 IPFE，它们的编码方式正好倒过来。现在，一个自然的思路是使用双层加密 (double-layer encryption)：让明文和密钥里的向量分别经过两个独立初始化的 IPFE 实例，其中一个 IPFE 保护明文向量，另一个保护密钥里的向量。

得益于保持编码方式的性质，一个 IPFE 的输出可以作为另一个 IPFE 的输入。得益于保持内积的性质，嵌套加密后仍然能够正常解密：假设内外层分别用下标 $\mathsf{i}\mathsf{n},\mathsf{o}\mathsf{u}\mathsf{t}$ 表示，那么

• 主密钥 $\mathsf{m}\mathsf{s}\mathsf{k}$ 就是 (mpkin​,mpkout​,mskin​,mskout​)。简洁起见，之后调用算法的时候就不再指明公私钥的输入了（只有一种自然的选择）。
• $\mathsf{K}\mathsf{e}\mathsf{y}\mathsf{G}\mathsf{e}\mathsf{n}(\mathsf{m}\mathsf{s}\mathsf{k},[[\mathbf{v}{]]}_2)$ 输出 KeyGenout​(Encin​([[v]]2​))。
• $\mathsf{E}\mathsf{n}\mathsf{c}(\mathsf{m}\mathsf{s}\mathsf{k},[[\mathbf{u}{]]}_1)$ 输出 Encout​(KeyGenin​([[u]]1​))。
• $\mathsf{D}\mathsf{e}\mathsf{c}$ 直接运行 Decout​，这会得到 $$\begin{array}{rl}\mathsf{D}\mathsf{e}\mathsf{c}(\mathsf{s}\mathsf{k},\mathsf{c}\mathsf{t})& ={\mathsf{D}\mathsf{e}\mathsf{c}}_{\mathsf{o}\mathsf{u}\mathsf{t}}({\mathsf{s}\mathsf{k}}_{\mathsf{o}\mathsf{u}\mathsf{t}},{\mathsf{c}\mathsf{t}}_{\mathsf{o}\mathsf{u}\mathsf{t}})\\ & =⟨{\mathsf{c}\mathsf{t}}_{\mathsf{i}\mathsf{n}},{\mathsf{s}\mathsf{k}}_{\mathsf{i}\mathsf{n}}⟩\\ & ={\mathsf{D}\mathsf{e}\mathsf{c}}_{\mathsf{i}\mathsf{n}}({\mathsf{s}\mathsf{k}}_{\mathsf{i}\mathsf{n}},{\mathsf{c}\mathsf{t}}_{\mathsf{i}\mathsf{n}})=[[{\mathbf{u}}^{\text{T}}\mathbf{v}{]]}_{\text{T}}.\end{array}$$ 这里第一行到第二行是因为外层密钥、密文分别是为内层密文、密钥生成的，第二行到第三行是因为内层算法的解密算法等同于求密文和密钥的内积，最后一个等号是因为内层算法的正确性。

这样做能达到我们想要的泛函保密性（IND-FH）吗？上回 已经剧透过了：不知道。不过这个构造具有 IND-CPA 安全性和弱泛函保密性（IND-wFH）：

• 总方案的 IND-CPA 可以归约为外层方案的 IND-CPA。
• 总方案的 IND-wFH 可以归约为内层方案的 IND-CPA。

“三仙归洞”与“空当接龙”

通俗来说，IND-CPA 和 IND-wFH 允许我们单独改变明文或密钥里的向量，但是不能同时改变。如何同时改变呢？答案是把“同时改变”分解成好几次“单独改变”，并运用过渡证明法 (hybrid argument)。为了达成目的，咱们需要制造一些冗余编程空间 (programming space)。

从一个 IND-wFH 的内积加密（下称初始方案，算法加撇表示）出发，可以构造如下的 IPFE（下称新方案，算法不加撇）： $$\begin{array}{rl}\mathsf{S}\mathsf{e}\mathsf{t}\mathsf{u}\mathsf{p}(1^n)& ={\mathsf{S}\mathsf{e}\mathsf{t}\mathsf{u}\mathsf{p}}^{\prime }(1^{\boxed{2n}}),\\ \mathsf{K}\mathsf{e}\mathsf{y}\mathsf{G}\mathsf{e}\mathsf{n}(\mathsf{m}\mathsf{s}\mathsf{k},[[\mathbf{v}{]]}_2)& ={\mathsf{K}\mathsf{e}\mathsf{y}\mathsf{G}\mathsf{e}\mathsf{n}}^{\prime }(\mathsf{m}\mathsf{s}\mathsf{k},[[\mathbf{v},0{]]}_2),\\ \mathsf{E}\mathsf{n}\mathsf{c}(\mathsf{m}\mathsf{s}\mathsf{k},[[\mathbf{u}{]]}_1)& ={\mathsf{E}\mathsf{n}\mathsf{c}}^{\prime }(\mathsf{m}\mathsf{s}\mathsf{k},[[\mathbf{u},0{]]}_1),\\ \mathsf{D}\mathsf{e}\mathsf{c}& ={\mathsf{D}\mathsf{e}\mathsf{c}}^{\prime }.\end{array}$$ 说人话：用维数是 $2n$ 的初始方案充当维数是 $n$ 的新方案，多余的维补零。

显然多余的维数对新方案的功能毫无作用，然而我们马上会看到，它在安全证明里会发挥巨大的作用：这个看起来很冗余的新方案具有 IND-FH 安全性！证明方式有种 三仙归洞 (cups and balls) 和 空当接龙 (FreeCell) 的感觉。我的导师曾经把这个方法描述为“来回倒腾”(let the things dance around)，而（另一篇论文的）审稿人说这种技巧是“在各个部件之间交换信息”(exchange information among the things)。

下表描述了每个过渡实验里如何生成密钥和密文：

上表中的方框代表和上一个过渡实验不同的部分。通过瞪眼法 (By inspection) 可知：${\mathsf{H}}_0\approx {\mathsf{H}}_1,{\mathsf{H}}_2\approx {\mathsf{H}}_3,{\mathsf{H}}_4\approx {\mathsf{H}}_5$ 可以归约为初始方案的 IND-wFH，而 ${\mathsf{H}}_1\approx {\mathsf{H}}_2,{\mathsf{H}}_3\approx {\mathsf{H}}_4$ 可以归约为初始方案的 IND-CPA。这是因为相邻两个过渡实验总是具有相同的内积，而且相邻两个过渡实验要么只改变明文，要么只改变密钥里的向量。

冗余与可证明安全

可能会有读者感觉直接用双层加密得到的 IPFE 好似¹已经很安全了，为什么还要把维数升高一倍浪费性能呢？现代密码学的原则是尽量把安全性归约为某个简单干净的 (clean and simple) 计算性假设上，即可证明安全性 (provable security)，这是现代密码学和古法炼丹术的重要区别之一。理想状态下，大家应该使用标准模型下可证明安全的方案，虽然现实几乎永远不是²这样。

可以把安全性证明理解为一种对冲 (hedging)，即 science always wins³：要么找到了一个安全的方案，要么能够解决一个计算问题。另一个理解需要可证明安全的方式是：功能需要人来实现才会存在。⁴而几乎所有安全性都是高度非平凡的功能，如果没有人来证明它可以归约为某个计算性假设，一个随机出现的构造基本上不会有安全性。

目前没有人证明⁵双层加密已经满足 IND-FH。而且从理论研究的角度，从 IND-wFH 到 IND-FH 的转换已经很满足了，它不降低多少效率，却可以轻松获得更高级别的安全性。

最后，现在才问“为什么不去掉冗余”（为了可证明安全）似乎有点后知后觉，因为 [ALS16] 方案也有冗余。引入冗余（或者说多个运作模式）是获得可证明安全性的常见手段，任何基于双系统加密 (dual system encryption) 或光滑投影哈希 (smooth projective hashing) 的方案，就功能上来看都有冗余。这种安全性证明思路通常是这样的：准备一个正常模式提供功能，准备一个特殊模式提供安全性，最后证明正常模式和特殊模式不可区分。本博客以后会发布的科普文章里也可以见到很多这样的技巧运用。

本篇结语

本篇讲述了 [LV16] 构造 IND-FH IPFE 的思路，并讨论了一下为了可证明安全而引入冗余的现象。最后一篇 讨论双槽内积加密，“内积加密”系列就完结了。

参考文献