内积加密：双槽内积加密

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

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

前情提要

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

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

定义双槽 IPFE

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

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

• $\mathsf{S}\mathsf{e}\mathsf{t}\mathsf{u}\mathsf{p}(1^{n_{\text{pub}}},1^{n_{\text{priv}}})$ 用于初始化公有槽维数是 npub​、私有槽维数是 $n_{\text{priv}}$ 的实例，它输出主密钥对 (mpk,msk)。
• $\mathsf{K}\mathsf{e}\mathsf{y}\mathsf{G}\mathsf{e}\mathsf{n}(\mathsf{m}\mathsf{s}\mathsf{k},[[{\mathbf{v}}_{\text{pub}},{\mathbf{v}}_{\text{priv}}{]]}_2)$ 输出 $({\mathbf{v}}_{\text{pub}},{\mathbf{v}}_{\text{priv}})$ 的密钥 sk。
• $\mathsf{E}\mathsf{n}\mathsf{c}(\boxed{\mathsf{m}\mathsf{s}\mathsf{k}},[[{\mathbf{u}}_{\text{pub}},{\mathbf{u}}_{\text{priv}}{]]}_1)$ 输出 $({\mathbf{u}}_{\text{pub}},{\mathbf{u}}_{\text{priv}})$ 的密文 ct，注意这个算法输入的是主私钥。
• $\mathsf{D}\mathsf{e}\mathsf{c}(\mathsf{s}\mathsf{k},\mathsf{c}\mathsf{t})$ 需要计算内积在 $G_{\text{T}}$ 的编码。
• $\mathsf{S}\mathsf{l}\mathsf{o}\mathsf{t}\mathsf{E}\mathsf{n}\mathsf{c}(\boxed{\mathsf{m}\mathsf{p}\mathsf{k}},[[{\mathbf{u}}_{\text{pub}}{]]}_1)$ 是公有槽的加密算法，它需要只用主公钥就能加密 (upub​,0)。

双槽 IPFE 需要有两个正确性保证。一是私钥模式下正确 (correct in private mode)，即“加密、产生密钥之后再解密，得到的确实是内积”，这一点读者应该很熟悉了：对任意 $n_{\text{pub}},n_{\text{priv}}\in \mathbb{N}$ 和任意 ${\mathbf{u}}_{\text{pub}},{\mathbf{v}}_{\text{pub}}\in {\mathbb{Z}}_p^{n_{\text{pub}}},{\mathbf{u}}_{\text{priv}},{\mathbf{v}}_{\text{priv}}\in {\mathbb{Z}}_p^{n_{\text{priv}}}$ 有 $$\begin{array}{rl}\mathrm{Pr}\left[\begin{array}{rl}(\mathsf{m}\mathsf{p}\mathsf{k},\mathsf{m}\mathsf{s}\mathsf{k})& \stackrel{{}_{\$}}{\leftarrow }\mathsf{S}\mathsf{e}\mathsf{t}\mathsf{u}\mathsf{p}(1^{n_{\text{pub}}},1^{n_{\text{priv}}})\\ \mathsf{s}\mathsf{k}& \text{ ↵}\\ \mathsf{c}\mathsf{t}& \stackrel{{}_{\$}}{\leftarrow }\mathsf{E}\mathsf{n}\mathsf{c}(\mathsf{m}\mathsf{s}\mathsf{k},[[{\mathbf{u}}_{\text{pub}},{\mathbf{u}}_{\text{priv}}{]]}_1)\\ & :\mathsf{D}\mathsf{e}\mathsf{c}(\mathsf{s}\mathsf{k},\mathsf{c}\mathsf{t})=[[{\mathbf{u}}_{\text{pub}}^{\text{T}}{\mathbf{v}}_{\text{pub}}+{\mathbf{u}}_{\text{priv}}^{\text{T}}{\mathbf{v}}_{\text{priv}}{]]}_{\text{T}}\end{array}\right]& =1.\end{array}$$ 二是槽模式正确性 (slot-mode correctness)¹，实际上这算是半个²安全性，它要求 $\mathsf{S}\mathsf{l}\mathsf{o}\mathsf{t}\mathsf{E}\mathsf{n}\mathsf{c}$ 效果完全等同于 $\mathsf{E}\mathsf{n}\mathsf{c}$ 里 upriv​=0：对任意 $n_{\text{pub}},n_{\text{priv}}\in \mathbb{N}$ 和任意 upub​∈Zpnpub​​，下述两个分布是同一个分布 (are identical)³ $$\begin{array}{rl}& \left\{\begin{array}{rl}(\mathsf{m}\mathsf{p}\mathsf{k},\mathsf{m}\mathsf{s}\mathsf{k})& \stackrel{{}_{\$}}{\leftarrow }\mathsf{S}\mathsf{e}\mathsf{t}\mathsf{u}\mathsf{p}(1^{n_{\text{pub}}},1^{n_{\text{priv}}})\\ \mathsf{c}\mathsf{t}& \stackrel{{}_{\$}}{\leftarrow }\mathsf{S}\mathsf{l}\mathsf{o}\mathsf{t}\mathsf{E}\mathsf{n}\mathsf{c}(\mathsf{m}\mathsf{p}\mathsf{k},[[{\mathbf{u}}_{\text{pub}}{]]}_1)\end{array}:(\mathsf{m}\mathsf{p}\mathsf{k},\mathsf{m}\mathsf{s}\mathsf{k},\mathsf{c}\mathsf{t})\right\}\\ \equiv & \left\{\begin{array}{rl}(\mathsf{m}\mathsf{p}\mathsf{k},\mathsf{m}\mathsf{s}\mathsf{k})& \stackrel{{}_{\$}}{\leftarrow }\mathsf{S}\mathsf{e}\mathsf{t}\mathsf{u}\mathsf{p}(1^{n_{\text{pub}}},1^{n_{\text{priv}}})\\ \mathsf{c}\mathsf{t}& \stackrel{{}_{\$}}{\leftarrow }\mathsf{E}\mathsf{n}\mathsf{c}(\mathsf{m}\mathsf{s}\mathsf{k},[[{\mathbf{u}}_{\text{pub}},0{]]}_1)\end{array}:(\mathsf{m}\mathsf{p}\mathsf{k},\mathsf{m}\mathsf{s}\mathsf{k},\mathsf{c}\mathsf{t})\right\}.\end{array}$$

双槽 IPFE 同时具有公钥 IPFE 和私钥 IPFE 的功能：令 $n_{\text{priv}}=0$ 则得到公钥 IPFE；相反，若令 $n_{\text{pub}}=0$ 则得到私钥 IPFE。这种方式得到的方案叫做双槽 IPFE 所诱导的 (induced by …)⁴方案。

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

$\underset{\begin{array}{c}\\ \\ 1^{n_{\text{pub}}},1^{n_{\text{priv}}}\end{array}}{\to }$

$(\mathsf{m}\mathsf{p}\mathsf{k},\mathsf{m}\mathsf{s}\mathsf{k})\stackrel{{}_{\$}}{\leftarrow }\mathsf{S}\mathsf{e}\mathsf{t}\mathsf{u}\mathsf{p}(1^{n_{\text{pub}}},1^{n_{\text{priv}}})$

$\stackrel{\mathsf{m}\mathsf{p}\mathsf{k}}{\leftarrow }$

$\mathcal{A}$$\begin{array}{c}\Rsh |\\ \left|\right|\\ \left|\right|\\ \left|\right|\\ \left|⌣\right|\end{array}$

$\underset{[[{\mathbf{v}}_{j,\text{pub}},{\mathbf{v}}_{j,\text{priv}}^{(0)},{\mathbf{v}}_{j,\text{priv}}^{(1)}{]]}_2}{\to }$

${\mathsf{s}\mathsf{k}}_j\stackrel{{}_{\$}}{\leftarrow }\mathsf{K}\mathsf{e}\mathsf{y}\mathsf{G}\mathsf{e}\mathsf{n}(\mathsf{m}\mathsf{s}\mathsf{k},[[{\mathbf{v}}_{j,\text{pub}},{\mathbf{v}}_{j,\text{priv}}^{(b)}{]]}_2)$

$\stackrel{{\mathsf{s}\mathsf{k}}_j}{\leftarrow }$

$\underset{[[{\mathbf{u}}_{i,\text{pub}}^{(0)},{\mathbf{u}}_{i,\text{pub}}^{(1)},{\mathbf{u}}_{i,\text{priv}}^{(0)},{\mathbf{u}}_{i,\text{priv}}^{(1)}{]]}_1}{\to }$

${\mathsf{c}\mathsf{t}}_i\stackrel{{}_{\$}}{\leftarrow }\mathsf{E}\mathsf{n}\mathsf{c}(\mathsf{m}\mathsf{s}\mathsf{k},[[{\mathbf{u}}_{i,\text{pub}}^{(b)},{\mathbf{u}}_{i,\text{priv}}^{(b)}{]]}_1)$

$\stackrel{{\mathsf{c}\mathsf{t}}_i}{\leftarrow }$

$\mathcal{C}$

$\hookrightarrow b^{\prime }$

当然，这里要求对任意 $i,j$ 有 $$\begin{array}{rl}& ({\mathbf{u}}_{i,\text{pub}}^{(0)}{)}^{\text{T}}{\mathbf{v}}_{j,\text{pub}}+({\mathbf{u}}_{i,\text{priv}}^{(0)}{)}^{\text{T}}{\mathbf{v}}_{j,\text{priv}}^{(0)}\\ =& ({\mathbf{u}}_{i,\text{pub}}^{(1)}{)}^{\text{T}}{\mathbf{v}}_{j,\text{pub}}+({\mathbf{u}}_{i,\text{priv}}^{(1)}{)}^{\text{T}}{\mathbf{v}}_{j,\text{priv}}^{(1)}.\end{array}$$$$({\mathbf{u}}_{i,\text{pub}}^{(0)}{)}^{\text{T}}{\mathbf{v}}_{j,\text{pub}}+({\mathbf{u}}_{i,\text{priv}}^{(0)}{)}^{\text{T}}{\mathbf{v}}_{j,\text{priv}}^{(0)}=({\mathbf{u}}_{i,\text{pub}}^{(1)}{)}^{\text{T}}{\mathbf{v}}_{j,\text{pub}}+({\mathbf{u}}_{i,\text{priv}}^{(1)}{)}^{\text{T}}{\mathbf{v}}_{j,\text{priv}}^{(1)}.$$

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

之前说过双槽 IPFE 通过设置公有槽、私有槽的长度为零可以（从语法和语义上）退化为私钥、公钥 IPFE，安全性也是如此：如果考虑 $n_{\text{pub}}=0$ 时双槽 IPFE 的 IND-FH，它恰好就是它诱导的私钥 IPFE 的 IND-FH；若 npriv​=0，则双槽 IPFE 的 IND-FH 就是它诱导的公钥 IPFE 的 IND-CPA（密钥里向量的私有槽没得选）。

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

构造双槽 IPFE

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

具体来说，内层方案是 $2n_{\text{priv}}$ 维，外层方案是 $n_{\text{pub}}+k+1+2n_{\text{priv}}$⁵维。总方案的密钥对是 $\mathsf{m}\mathsf{p}\mathsf{k}={\mathsf{m}\mathsf{p}\mathsf{k}}_{\mathsf{o}\mathsf{u}\mathsf{t}}$ 以及 msk=(mpkout​,mpkin​,mskout​,mskin​,t)，其中 t←$​{0,1}。总方案里 $({\mathbf{v}}_{\text{pub}},{\mathbf{v}}_{\text{priv}})$ 的密钥是 $$\mathsf{s}\mathsf{k}={\mathsf{K}\mathsf{e}\mathsf{y}\mathsf{G}\mathsf{e}\mathsf{n}}_{\mathsf{o}\mathsf{u}\mathsf{t}}({\mathbf{v}}_{\text{pub}},{\mathsf{E}\mathsf{n}\mathsf{c}}_{\mathsf{i}\mathsf{n}}({\mathbf{v}}_{\text{priv}},{\mathbf{v}}_{\text{priv}})).$$ 总方案里 $({\mathbf{u}}_{\text{pub}},{\mathbf{u}}_{\text{priv}})$ 的密文这样生成： $$\begin{array}{rl}{\mathsf{s}\mathsf{k}}_{\mathsf{i}\mathsf{n}}& \leftarrow \{\begin{array}{ll}{\mathsf{K}\mathsf{e}\mathsf{y}\mathsf{G}\mathsf{e}\mathsf{n}}_{\mathsf{i}\mathsf{n}}({\mathbf{u}}_{\text{pub}},0),& t=0;\\ {\mathsf{K}\mathsf{e}\mathsf{y}\mathsf{G}\mathsf{e}\mathsf{n}}_{\mathsf{i}\mathsf{n}}(0,{\mathbf{u}}_{\text{pub}}),& t=1;\end{array}\\ \mathsf{c}\mathsf{t}& \stackrel{{}_{\$}}{\leftarrow }{\mathsf{E}\mathsf{n}\mathsf{c}}_{\mathsf{o}\mathsf{u}\mathsf{t}}({\mathbf{u}}_{\text{pub}},{\mathsf{s}\mathsf{k}}_{\mathsf{i}\mathsf{n}}).\end{array}$$ 换言之，${\mathbf{u}}_{\text{priv}}$ 可以在前半段也可以在后半段，取决于 t。解密的话自然就是调用外层解密，利用加密、密钥生成保持内积的性质自动解密内层方案，从而得到正确结果。最后，$\mathsf{S}\mathsf{l}\mathsf{o}\mathsf{t}\mathsf{E}\mathsf{n}\mathsf{c}$ 算法就是运行 Encout​(upub​,0​)，槽模式正确性是因为 [ALS16] 方案里零向量的密文是零向量。

这里弄一个 $t$ 是为了缩短过渡证明法里的过渡实验数量，从而减少归约产生的安全损失，利用的是 耦合 (coupling) 的技巧。具体来说，我的证明会把 ${\mathsf{E}\mathsf{x}\mathsf{p}}_{\text{FH}}^0$ 里 $t=r$ 的情况对应到 ${\mathsf{E}\mathsf{x}\mathsf{p}}_{\text{FH}}^1$ 里 $t=1-r$ 的情况；由于 $r$ 和 $1-r$ 分别均匀随机，这样做没问题。

下面列出 $r=0$ 的过渡实验（另一种情况只要把内层方案的前后两段倒过来即可），其中 $\mathbf{a},\mathbf{b},\mathbf{c}$ 表示 ${\mathsf{K}\mathsf{e}\mathsf{y}\mathsf{G}\mathsf{e}\mathsf{n}}_{\mathsf{o}\mathsf{u}\mathsf{t}}(\mathbf{a},{\mathsf{E}\mathsf{n}\mathsf{c}}_{\mathsf{i}\mathsf{n}}(\mathbf{b},\mathbf{c}))$ 产生的密钥或者 ${\mathsf{E}\mathsf{n}\mathsf{c}}_{\mathsf{o}\mathsf{u}\mathsf{t}}(\mathbf{a},{\mathsf{K}\mathsf{e}\mathsf{y}\mathsf{G}\mathsf{e}\mathsf{n}}_{\mathsf{i}\mathsf{n}}(\mathbf{b},\mathbf{c}))$ 产生的密文：

本篇结语

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

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

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

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

参考文献