内积加密：ALS 公钥方案

“内积加密”系列文章的前半部分旨在总结和科普 Agrawal、Libert、Stehlé 在 2016 年提出 [ALS16]，Wee 在 2017 年改进 [Wee17]，Agrawal、Libert、Monosij、Titiu 在 2020 年完善 [ALMT20] 的内积加密算法。本篇是前半部分的最后一篇，叙述 ALS 公钥内积加密方案并证明它的 SIM-CPA 安全性。它的构造思想既可以理解为光滑投影哈希（也叫“哈希证明系统”）[CS02] 加换元法，也可以理解为双系统加密 [Wat09]。

植入广告 我和我导师在 Eurocrypt 2020 发表的文章（也是我在博士生阶段的第一个工作）终于发布在 ePrint 上啦 [LL20]！“内积加密”系列文章就是为了科普这篇论文里的结果做铺垫的。

前情提要

本系列的 第一篇 和 第二篇 里，我们探讨了一次性私钥内积加密。从 第三篇 和 第四篇 介绍了公钥内积加密的概念和这一篇要用的工具。

关于私钥内积加密，读者需要回忆 一次一密的构造，简述如下：

• 主密钥是 w←$​Zpn​。
• $\mathbf{v}$ 的密钥是 wTv。
• $\mathbf{u}$ 的密文是 w+u。

该构造具有完美模拟安全性。

关于公钥内积加密的工具，读者需要回忆 MDDH 假设，简述如下：

• 有一个可以做任意线性组合（系数以数字给出）的 ${\mathbb{Z}}_p$ 元素的编码 [[⋅]]，叫做“循环群”。
• 在这个编码下，$k$ 个随机向量编码的随机线性组合是伪随机 (pseudorandom) 的： $$[[\mathbf{A},{\mathbf{s}}^{\text{T}}\mathbf{A}]]\approx [[\mathbf{A},{\mathbf{c}}^{\text{T}}]],$$ 其中 A←$​Zpk×(k+1)​,s←$​Zpk​,c←$​Zpk+1​。

构造

这里的构造需要小小作弊一下，改变 IPFE 的功能和安全性定义：¹

• 加密时的明文和解密后的结果都是用群编码的，但密钥还是数字。
• 上一条的一个后果是，在 IND-CPA 的定义中，使坏者只需要提供群编码的明文挑战向量。
• 不过，虽然解密结果是群编码的，在 SIM-CPA 的定义中，我们还是允许模拟器获得作为数字的内积。

最初，[ALS16] 的公钥 IPFE 基于 DDH，基于 MDDH 的变体首次记载于 [Wee17]，它的构造如下：

• $\mathsf{S}\mathsf{e}\mathsf{t}\mathsf{u}\mathsf{p}(1^n)$ 输入向量维数 n，它抽取随机矩阵并这样设置主公钥和主私钥： $$\begin{array}{rlrl}\mathbf{A}& \stackrel{{}_{\$}}{\leftarrow }{\mathbb{Z}}_p^{k\times (k+1)},& \mathbf{W}& \stackrel{{}_{\$}}{\leftarrow }{\mathbb{Z}}_p^{(k+1)\times n},\\ \mathsf{m}\mathsf{p}\mathsf{k}& =[[\mathbf{A},\mathbf{A}\mathbf{W}]],& \mathsf{m}\mathsf{s}\mathsf{k}& =\mathbf{W}.\end{array}$$
• $\mathsf{K}\mathsf{e}\mathsf{y}\mathsf{G}\mathsf{e}\mathsf{n}(\mathsf{m}\mathsf{s}\mathsf{k},\mathbf{v})$ 输出 skv​=(−Wvv​)。
• $\mathsf{E}\mathsf{n}\mathsf{c}(\mathsf{m}\mathsf{p}\mathsf{k},[[\mathbf{u}]])$ 抽取 $\mathbf{s}\stackrel{{}_{\$}}{\leftarrow }{\mathbb{Z}}_p^k$ 并输出 $$\mathsf{c}\mathsf{t}=({\mathbf{s}}^{\text{T}}[[\mathbf{A}]],{\mathbf{s}}^{\text{T}}[[\mathbf{A}\mathbf{W}]]+[[\mathbf{u}{]]}^{\text{T}}).$$
• $\mathsf{D}\mathsf{e}\mathsf{c}({\mathsf{s}\mathsf{k}}_{\mathbf{v}},\mathsf{c}\mathsf{t})$ 输出 $$\begin{array}{rl}\mathsf{c}\mathsf{t}\cdot {\mathsf{s}\mathsf{k}}_{\mathbf{v}}& =[[{\mathbf{s}}^{\text{T}}\mathbf{A}]](-\mathbf{W}\mathbf{v})+[[{\mathbf{s}}^{\text{T}}\mathbf{A}\mathbf{W}+{\mathbf{u}}^{\text{T}}]]\mathbf{v}\\ & =[[{\mathbf{u}}^{\text{T}}\mathbf{v}]].\end{array}$$

模拟器

我们不直接谈模拟器的构造，而是通过过渡证明法自然到达一个可以模拟的过渡实验——那里面主公钥、密钥、挑战密文的生成方式就会是模拟器的做法。开始之前提醒一下：模拟器只要模拟一个挑战密文（“选择明文”体现在使坏者掌握公钥，故自然可以随意加密它选择的向量）。理同一次一密的模拟器，密钥里只有 $\mathbf{W}\mathbf{v}$ 有必要讲怎么模拟。这里证明过程在书写上和 [ALMT20] 不同（本质一样），我借鉴了 [Wee17] 的写法，并且自认为我的展示方法更“自然”。

• ${\mathsf{H}}_0$ 就是真实实验。
• ${\mathsf{H}}_1$ 里，改变挑战密文的应答： $$[[{\mathbf{s}}^{\text{T}}\mathbf{A},{\mathbf{s}}^{\text{T}}\mathbf{A}\mathbf{W}+{\mathbf{u}}^{\text{T}}]]⟹[[{\mathbf{c}}^{\text{T}},{\mathbf{c}}^{\text{T}}\mathbf{W}+{\mathbf{u}}^{\text{T}}]],$$ 其中 c←$​Zpk+1​。
• ${\mathsf{H}}_2$ 里，进一步限制 $\mathbf{c}$ 不能在 $\mathbf{A}$ 的行空间里，即不存在 $\mathbf{s}\in {\mathbb{Z}}_p^k$ 满足 cT=sTA。
• ${\mathsf{H}}_3$ 里，对 $\mathbf{W}$ 作换元：在按照上一个过渡实验的要求抽取 $\mathbf{A},\mathbf{c}$ 后，求关于 ${\mathbf{a}}^{\perp }$ 的方程组 $$\mathbf{A}{\mathbf{a}}^{\perp }=0,{\mathbf{c}}^{\text{T}}{\mathbf{a}}^{\perp }=1$$ 随便的一个解，解就记作 a⊥，再抽取 $\tilde{\mathbf{W}}\stackrel{{}_{\$}}{\leftarrow }{\mathbb{Z}}_p^{(k+1)\times n}$ 和 w←$​Zpn​，并令 $$\mathbf{W}=\tilde{\mathbf{W}}+{\mathbf{a}}^{\perp }{\mathbf{w}}^{\text{T}}.$$

先来证明这几个实验不可区分：

• ${\mathsf{H}}_0\approx {\mathsf{H}}_1$ 是 上次习题 2 的第一部分。
• ${\mathsf{H}}_1{\approx }_s{\mathsf{H}}_2$ 是因为 $\mathbf{A}$ 行空间（至多 $k$ 维）不是整个空间（k+1 维），故一个随机向量以 $\le 1/p$ 的概率落在子空间中，本来发生的概率就是可忽略的。
• ${\mathsf{H}}_2\equiv {\mathsf{H}}_3$ 是因为两个实验里除了 $\mathbf{W}$ 的抽样方式完全一样，而 $\mathbf{W}$ 在两个实验里其实也都是均匀随机、独立于 $\mathbf{A},\mathbf{c}$ 的矩阵——换元只是一个观点上的变化 (conceptual change) （即改变抽样方式），而不改变分布。

大费周章改变 $\mathbf{W}$ 的抽样方式必然有其用意（“没有无缘无故的第一小问”）。现在来看看在 ${\mathsf{H}}_3$ 里主公钥、密钥、挑战密文分别长什么样_儿。主公钥是 $$\begin{array}{rl}\mathsf{m}\mathsf{p}\mathsf{k}& =[[\mathbf{A},\mathbf{A}\mathbf{W}]]\\ & =[[\mathbf{A},\mathbf{A}\tilde{\mathbf{W}}+\mathbf{A}{\mathbf{a}}^{\perp }{\mathbf{w}}^{\text{T}}]]\\ & =[[\mathbf{A},\mathbf{A}\tilde{\mathbf{W}}]],\end{array}$$ 其中第三个等号是因为 Aa⊥=0。密钥是 $$\mathbf{W}\mathbf{v}=\tilde{\mathbf{W}}\mathbf{v}+{\mathbf{a}}^{\perp }(\boxed{{\mathbf{w}}^{\text{T}}\mathbf{v}}).$$ 挑战密文是 $$\begin{array}{rl}\mathsf{c}\mathsf{t}& =[[{\mathbf{c}}^{\text{T}},{\mathbf{c}}^{\text{T}}\mathbf{W}+{\mathbf{u}}^{\text{T}}]]\\ & =[[{\mathbf{c}}^{\text{T}},{\mathbf{c}}^{\text{T}}\tilde{\mathbf{W}}+{\mathbf{c}}^{\text{T}}{\mathbf{a}}^{\perp }{\mathbf{w}}^{\text{T}}+{\mathbf{u}}^{\text{T}}]]\\ & =[[{\mathbf{c}}^{\text{T}},{\mathbf{c}}^{\text{T}}\tilde{\mathbf{W}}+(\boxed{\mathbf{w}+\mathbf{u}}{)}^{\text{T}}]],\end{array}$$ 其中第三个等号是因为 cTa⊥=1。

如果你还记得一次一密 IPFE（下称 OTP-IPFE）的构造（最好还记得模拟器），那么这里的用意应该很明显。上述公式里方框框住的项恰好是 OTP-IPFE 的密钥和密文，而其它部分都是不需要知道 $\mathbf{w}$（即 OTP-IPFE 主私钥）和 $\mathbf{u}$（即挑战明文向量）也可以自己高效计算的。所以下一步就是把这些 OTP-IPFE 密钥、密文用模拟的版本代替。

模拟器这样做：自己抽样 $\mathbf{A},\tilde{\mathbf{W}},\mathbf{c}$ 并内部使用一个 OTP-IPFE 的模拟器，通过拼接 (stitch) 它自己可以计算的和 OTP-IPFE 模拟器帮它计算的部分（即方框内的内容）来产生模拟应答。由于模拟器只有在调用 OTP-IPFE 模拟器的时候才会用到关于 $\mathbf{u}$ 的信息，故它只需要作为数字的内积（符合修改过的 SIM-CPA 里模拟器的要求）。由于 OTP-IPFE 的完美模拟安全性，模拟器等同于 H3​，从而与真实实验 ${\mathsf{H}}_0$ 不可区分。

读者习题 证明该方案也具有 IND-CPA 安全性。

光滑投影哈希

看完了形式化证明，自然要问：这个思路是怎么来的？它来自于光滑投影哈希 (smooth projective hash)，也叫哈希证明系统 (hash proof systems) [CS02]。在最初构造该 IPFE 的 [ALS16] 中就有：

Our DDH-based construction and its security proof implicitly build on hash proof systems [CS02].

关于光滑投影哈希的中文科普，可以看陈宇的文章：知乎、PDF。

这里我特化到这个方案来说说证明的思路，不妨设 $\mathbf{A}$ 行满秩（即行空间是 $k$ 维的）。注意到在正常的系统中，$\mathsf{m}\mathsf{p}\mathsf{k}$ 并不完全决定 $\mathsf{m}\mathsf{s}\mathsf{k}$——它只包括 $\mathbf{W}$ 在 $\mathbf{A}$ 行空间上的投影。可以把 $\mathbf{W}$ 想成 $k+1$ 份 OTP-IPFE（每行一份），而公钥里 $\mathbf{W}$ 在一个 $k$ 维子空间上的投影则允许任何人使用“其中 $k$ 份”OTP-IPFE 实例。

注意到 OTP-IPFE 对私钥有同态性，正常密文会对 $\mathbf{W}$ 的投影进行随机组合，作为“这个密文使用的 OTP-IPFE 主私钥”，并给出组合系数（作为原来 $k+1$ 个实例的组合）。而密钥则是这所有 $k+1$ 份 OTP-IPFE 的私钥。解密的时候按照系数组合私钥后即可用 OTP-IPFE 的方式解密。

因为主公钥只有 $k$ 维的投影，所以正常密文只用得到 $k$ 份，它没用到（也用不到）的那一份是用来进行安全证明的。利用 MDDH 假设，可以证明即使在挑战密文里使用最后一份 OTP-IPFE 的实例也不会被（多项式时间的）使坏者察觉，这就是 ${\mathsf{H}}_0$ 到 ${\mathsf{H}}_2$ 的转换。

这里要再次提醒初见密码学的读者关于计算性假设反直觉的事情，不过和 之前提醒的方向 不同：是否使用最后一份实例虽然在计算意义下不可区分，但它们在信息论意义下截然不同（“截然不一样”）。

一旦挑战密文使用了最后一份实例（即 ${\mathsf{H}}_2$ 中的情况）整个实验就相当于套了壳的私钥 IPFE 安全性实验了，在信息论意义下，使坏者收到的主公钥不包含任何将来会出现的挑战密文的信息（即相当于没有主公钥），而它收到的私钥里面只有对应于 $\mathbf{c}$ 张成的子空间的 1 个自由度（另外 $k$ 个对应于 $\mathbf{A}$ 的行空间，蕴含于主公钥，即套的“壳”）。而在 ${\mathsf{H}}_3$ 里做换元是为了清楚写出“挑战密文到底用相当于哪个 OTP-IPFE 实例”。把专属于挑战密文的 OTP-IPFE 实例“脱壳”后，模拟器的构造就很自然了——只需要把模拟的任务代理给 OTP-IPFE 的模拟器，并完成“套壳”的杂事儿即可。

双系统加密

另一种理解该构造的方法是 [Wat09] 提出的双系统加密 (dual system encryption)，它的“官方宣传语”是这样的：

In a dual system, ciphertexts and keys can take on two forms: normal or semi-functional. Semi-functional ciphertexts and keys are not used in the real system, they are only used in the security proof. A normal key can decrypt normal or semi-functional ciphertexts, and a normal ciphertext can be decrypted by normal or semi-functional keys. However, when a semi-functional key is used to decrypt a semi-functional ciphertext, decryption will fail.

以上摘录的是 [LW10] 的版本。在 IPFE 的语境下，并不是说半功能 (semi-functional) 密钥和密文解密会失败，更自然的理解思路是：当挑战密文半功能且所有密钥都半功能时，安全性在信息论意义下成立。

[Wee17] 是首次用双系统加密描述 ALS IPFE 的。实际上，就我个人所见，质数阶群里标准假设下的经典双系统加密都是光滑投影哈希——而且从概念上考虑可以认为是用两次光滑投影哈希，一次左乘 $\mathbf{A}$ 一次右乘 BT。

关于双系统加密和光滑投影哈希的联系，[Wee14] 也提到：

Along the way, we introduce a conceptual simplification where we define the semi-functional entities via auxiliary algorithms, reminiscent of Cramer–Shoup projective hashing [CS02].

这里，正常分量 (normal component) 就是光滑投影哈希里的公钥部分，而半功能分量 (semi-functional component) 就是私钥部分。

另外，dual system encryption 翻译为“双系统加密”而不是“对偶系统加密”是准确的，因为 Lewko [Lew13] 提到：

We’re gonna sell things up, so that it’s called “dual system”, because, you know, the word “dual” has so many uses, so this should mean absolutely nothing. Just to confuse you, (we) call it “dual system”. But you should think of… we have two distributions of keys, and two distributions of ciphertexts. So the “dual” is just coming from the simple meaning of having two things.

本篇结语

这一篇我们一口气完结了 ALS 方案的构造，并更加模块化地展示了模拟器，还指出了模拟器构造思路——光滑投影哈希、双系统加密。至此，“内积加密”系列上半部分完结。后半部分 讨论如何保护密钥里的向量，为科普 [LL20] 做铺垫。

参考文献