内积加密：泛函保密、配对

欢迎来到“内积加密”系列文章的后半部分，这部分科普 Lin 与 Vaikuntanathan 在 2016 年提出 [LV16] 的内积加密算法。这一篇我们开始讨论前半部分未解的一个疑问：如何保护密钥里的向量？延续之前的习惯，我们先定义泛函保密性。为了构造这样的方案，我们要引入另一个工具——配对（即双线性映射）。

从题图的风格可以看出我真的懒得想一个有“哄宝宝”效果（即吸引眼球）的配图。另外按照行文顺序，题图里的两行公式应该交换顺序，但我太懒了……😂

前情提要

在“内积加密”系列文章的 前半部分 介绍了内积加密的定义和构造，最终在循环群里的 MDDH 假设下得到了满足 SIM-CPA 和 IND-CPA 的公钥内积加密，在这个过程中用到了一个一次一密的私钥 IPFE 作为垫脚石，并利用光滑投影哈希将私钥 IPFE 转换成了公钥 IPFE。

再谈私钥 IPFE

在定义泛函保密性之前，思考这么一件事：公钥 IPFE 可以保护密钥里的向量吗？

取决于你怎么定义“保护”。在不可区分 (indistinguishability) 意义下不能保护密钥里的向量：任何掌握公钥的人都可以加密标准基向量 ${\mathbf{e}}_1,\dots ,{\mathbf{e}}_n$ 获得密文 ct1​,…,ctn​，如果获得了密钥 skv​，则可以通过 $\mathsf{D}\mathsf{e}\mathsf{c}({\mathsf{s}\mathsf{k}}_{\mathbf{v}},{\mathsf{c}\mathsf{t}}_i)$ 获得 v[i]。在 [ALS16] 方案中，我们只能获得群编码的结果，编码和数之间具有双射，如果使坏者已经知道密钥里的 $\mathbf{v}$ 可能是某两个之一，则可以轻松区分。

在模拟 (simulation) 意义下，模拟器可以获得和密钥里的向量有双射关系的信息，如果模拟器输入的是（写成数字的）密钥里的向量，那么就跟 SIM-CPA 没区别了。对于 [ALS16] 方案，如果模拟器输入的是群编码后的密钥里的向量，则模拟器不可能高效：可以通过分别查询 $[[{\mathbf{e}}_1]],[[x]]{\mathbf{e}}_1$ 的密钥（其中 $[[x]]$ 是任意待求解离散对数 [discrete logarithm] 的群元素）来求出 x，但 MDDH 假设蕴含着离散对数困难。$\to \parallel$

基于以上原因，我们只考虑私钥 IPFE 在不可区分意义下的泛函保密性。在私钥 IPFE 中，用加密基向量再解密的方式（在指数 [exponent] 里）提取 (extract) 密钥里的向量的策略无效，因为加密也需要主私钥。回忆上半部分第一篇里对私钥 IPFE 语法、语义的 定义，它包括四个高效算法：

• 初始化算法 $\mathsf{S}\mathsf{e}\mathsf{t}\mathsf{u}\mathsf{p}(1^n)$ 输入¹向量维数 $n$（的一进制表示），输出主密钥 msk。
• 密钥生成算法 $\mathsf{K}\mathsf{e}\mathsf{y}\mathsf{G}\mathsf{e}\mathsf{n}(\mathsf{m}\mathsf{s}\mathsf{k},\mathbf{v})$ 用来产生任何一个向量 $\mathbf{v}$ 的密钥 skv​。
• 加密算法 $\mathsf{E}\mathsf{n}\mathsf{c}(\mathsf{m}\mathsf{s}\mathsf{k},\mathbf{u})$ 用来加密任何一个向量 $\mathbf{u}$ 得到密文 ctu​。
• 解密算法 $\mathsf{D}\mathsf{e}\mathsf{c}({\mathsf{s}\mathsf{k}}_{\mathbf{v}},{\mathsf{c}\mathsf{t}}_{\mathbf{u}})$ 应该能够计算 uTv。

正确性也再抄一遍：对任意 $n$ 和任意 u,v∈Zpn​， $$\mathrm{Pr}\left[\begin{array}{rl}\mathsf{m}\mathsf{s}\mathsf{k}& \stackrel{{}_{\$}}{\leftarrow }\mathsf{S}\mathsf{e}\mathsf{t}\mathsf{u}\mathsf{p}(1^n)\\ \mathsf{s}\mathsf{k}& \stackrel{{}_{\$}}{\leftarrow }\mathsf{K}\mathsf{e}\mathsf{y}\mathsf{G}\mathsf{e}\mathsf{n}(\mathsf{m}\mathsf{s}\mathsf{k},\mathbf{v})\\ \mathsf{c}\mathsf{t}& \stackrel{{}_{\$}}{\leftarrow }\mathsf{E}\mathsf{n}\mathsf{c}(\mathsf{m}\mathsf{s}\mathsf{k},\mathbf{u})\end{array}:\mathsf{D}\mathsf{e}\mathsf{c}(\mathsf{s}\mathsf{k},\mathsf{c}\mathsf{t})={\mathbf{u}}^{\text{T}}\mathbf{v}\right]=1.$$

泛函保密性

现在定义不可区分意义下的泛函保密性 (indistinguishability-based function-hiding)，简称 IND-FH。在这个定义里，使坏者 (adversary) 给出两组可能的密钥、密文里的向量组合，这两组向量满足可以计算的内积都对应相等，在此条件下，使坏者获得其中一组的密钥、密文，它需要判断这组密钥、密文来自于哪一组向量。形式化来说就是在 ${\mathsf{E}\mathsf{x}\mathsf{p}}_{\text{FH}}^b$ 中：

• 初始化：使坏者 $\mathcal{A}$ 发送 1n，挑战者 $\mathcal{C}$ 运行 msk←$​Setup(1n)。
• 挑战：使坏者可以进行任意多轮挑战，每一轮它有两个选项。
  • 一个选项是 密钥挑战，使坏者选择 vj(0)​,vj(1)​∈Zpn​，挑战者运行 ${\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^{(b)})$ 并将 ${\mathsf{s}\mathsf{k}}_j$ 发送给 A。
  • 另一个选项是 密文挑战，使坏者选择 ui(0)​,ui(1)​∈Zpn​，挑战者运行 ${\mathsf{c}\mathsf{t}}_i\stackrel{{}_{\$}}{\leftarrow }\mathsf{E}\mathsf{n}\mathsf{c}(\mathsf{m}\mathsf{s}\mathsf{k},{\mathbf{u}}_i^{(b)})$ 并将 ${\mathsf{c}\mathsf{t}}_i$ 发送给 A。
• 猜测：使坏者输出一个猜测 b′∈{0,1}。

为了从设计使然 (by design) 的功能上排除平凡 (trivial) 的使坏者，使坏者选择的向量必须满足 $$({\mathbf{u}}_i^{(0)}{)}^{\text{T}}{\mathbf{v}}_j^{(0)}=({\mathbf{u}}_i^{(1)}{)}^{\text{T}}{\mathbf{v}}_j^{(1)}\forall i,j.$$ IND-FH 要求 ExpFH0​≈ExpFH1​。这就是说：如果设计上可以计算的（也就是那些内积）无法区分两组向量，则无法区分这两组向量的密钥和密文。

来讨论一下这个安全性定义。谈到私钥 IPFE，第一个安全性定义是 完美保密性，它和 IND-FH 有三个不同：

1. 前者为信息论意义下的安全性，后者是计算意义下的安全性；
2. 前者只允许使坏者获得一个密文，后者允许使坏者获取任意多个密文；
3. 前者不刻画密钥里的向量的保密性（使坏者总是知道密钥里的向量就是它选择的那些），后者对此有刻画（使坏者不知道密钥来自于上标是 0 还是 1 的那一组向量）。

如果适当改变完美保密性的定义，允许使坏者获得任意多个密文，并且只要求计算意义下的安全性，则可得到私钥 IPFE 的 IND-CPA——回忆 这里的讨论。容易发现 IND-FH 蕴含着 IND-CPA，即它同时²刻画了密钥和密文的安全性。

一个自然的问题是：有没有一个更模块化的方式定义安全性呢？譬如这样一个定义：它只考虑密钥里的向量的安全性，且如果一个方案同时满足 IND-CPA 和这个定义，则可以推出该方案也满足 IND-FH。

第一部分，答案是可以：只需要把私钥版本里 IND-CPA 里密钥和密文的地位互换即可，得到的定义仅刻画密钥里的向量的保密性。该定义叫³弱泛函保密性 (weakly function-hiding)，简称 IND-wFH。

第二部分，答案是⁴不知道可不可以但相当于可以。实际上，[LV16] 里的构造（即这个系列文章要讲的构造）就是这样分两步走的：

1. 从 IND-CPA 的特殊 IPFE 获得同时满足 IND-CPA 和 IND-wFH 的私钥 IPFE。
2. 从同时满足 IND-CPA 和 IND-wFH 的私钥 IPFE 获得 IND-FH 的私钥 IPFE。

我们也将沿着这个思路来构造 IND-FH 的私钥 IPFE。

双线性映射

为了之后构造 IND-FH 的 IPFE，我们需要一个比 循环群 更强力的工具——双线性群 (bilinear group)。熟悉这个工具的读者可以跳过这一段。

回忆一下，p 阶循环群可以编码 ${\mathbb{Z}}_p$ 元素，且编码可以和 ${\mathbb{Z}}_p$ 元素（数字）进行线性运算。编码具有一些困难问题，可以用来证明安全性，之前用到的是 MDDH 假设。不过作为代价，在困难性成立（因而安全性成立）的情况下无法把已经编码的两个数“在编码里相乘”。

在双线性群（也叫配对群 [pairing group]）中，可以对编码进行一次乘法运算。形式化来说，一个双线性群包括三个循环群和一个映射 $$((G_1,[[\cdot {]]}_1,{-}_1),(G_2,[[\cdot {]]}_2,{-}_2),(G_{\mathrm{T}},[[\cdot {]]}_{\mathrm{T}},{-}_{\mathrm{T}}),\cdot ),$$ 其中映射 $\cdot :G_1\times G_2\to G_{\mathrm{T}}$ 可以高效计算，且满足 $$[[a{]]}_1\cdot [[b{]]}_2=[[ab{]]}_{\mathrm{T}}\forall a,b\in {\mathbb{Z}}_p.$$ 这里，映射 $\cdot$ 叫做⁵配对映射。三个循环群中出现在定义域的 $G_1,G_2$ 叫做“源群” (source group)，出现在到达域⁶ (codomain) 的 $G_{\mathrm{T}}$ 叫做“目标群” (target group)。

简化记号，映射 $\cdot$ 和乘号一样通常省略不写，三个群的 $-$ 以及由此诱导的数乘、加号通常也不加下标。数乘、加号、减号（根据循环群中的讨论）可以自然诱导为矩阵记号，配对映射也可以——但运算数必须一个来自 $G_1$ 另一个来自 G2​，注意 $[[\mathbf{A}{]]}_1[[\mathbf{B}{]]}_2=[[\mathbf{A}\mathbf{B}{]]}_{\mathrm{T}}$ 和 $[[\mathbf{C}{]]}_2[[\mathbf{D}{]]}_1=[[\mathbf{C}\mathbf{D}{]]}_{\mathrm{T}}$ 都是可以高效计算的。

在双线性群里通常对源群作计算性假设，例如可以假设 ${\text{MDDH}}_k$ 分别在 $G_1,G_2$ 里成立。特别提一下，有些双线性群满足 G1​=G2​，这种叫对称双线性群，通常源群的双中括号下标就省略了。在这个情况下在源群里 ${\text{MDDH}}_1$ 假设不成立，请读者思考原因。

实际中，双线性群通常来自于 椭圆曲线 (elliptic curves)，不过要在密码学中应用双线性群不一定要知道它的内部结构，多亏这样，咱们才不需要因此特地学习代数几何。此外，Boneh 教授在 Simons Institute 做过一个介绍双线性群的讲座 [Bon15]，很赞！

最后，一个很自然的小剧透 (teaser)：之后构造的私钥 IPFE 里，$\mathbf{u},\mathbf{v}$（以及对应的密文、密钥）会分别用 $G_1,G_2$ 编码，而解密结果（内积）会用 $G_{\mathrm{T}}$ 编码。

本篇结语

本篇探讨了为什么具有泛函保密性的 IPFE 应该是私钥方案，并针对私钥方案定义了 IND-FH，它同时刻画了密钥和密文的安全性，对定义稍加讨论后我们转而了解了一个新工具——双线性映射。

下一篇 讨论 [LV16] 构造 IND-FH IPFE 的方法。

参考文献