属性加密：算术密钥乱码化

本文是我的 2019 年科研“属性加密”系列博文第二篇。在这一篇里，我将引入 [LL20] 中建立信息论意义下安全性的核心工具——算术密钥乱码化方案 (AKGS)——并给出适用于算术公式的构造。

前情提要

第一篇里介绍了属性加密 (ABE) 的概念：在密钥策略 (KP) ABE 中，密文和属性（程序输入）相关联，密钥和策略（程序）相关联；正确性保证若策略允许属性（程序输出 1），则可以解密；安全性确保即使拿到多个密钥，只要每个密钥的策略都不允许属性，就无法（高效）获得关于明文的任何信息。它可以看成是用密码学施行的访问控制列表 (ACL)。我们定了一个“小目标”：构造支持算术公式的 ABE。

ABE 与乱码电路

假设希望当 $f(\mathbf{x})\ne 0$ 时可以还原消息 μ，由于 ABE 不隐藏 f,x，故这相当于计算 μf(x)。当 $f(x)\ne 0$ 时，只要把计算结果除以 $f(\mathbf{x})$ 即可得到 μ；如果假设密钥和密文只透露了 $\mu f(\mathbf{x})$ 而无其他关于 $\mu$ 的信息，则直观上当 $f(\mathbf{x})=0$（即不允许解密）时，密钥和密文不包括任何关于 $\mu$ 的信息，从而得以隐藏消息。

顺带一提，如果希望当且仅当 $f(\mathbf{x})=0$ 时可以解密，则相当于计算 αf(x)+μ，且密钥和密文不透露任何其他关于 $\alpha ,\mu$ 的信息。这里 $\alpha$ 是一个随机数，当 $f(\mathbf{x})\ne 0$ 时，计算结果里 $\alpha f(\mathbf{x})$ 相当于一次性密钥 (one-time pad)，完美隐藏 μ。

熟悉一些基本密码学概念的读者可能会意识到这种情况和安全函数求值 (secure function evaluation) 很类似：生成密钥时只知道 $f$ 而不知道 μ,x，加密时则相反，但把密钥和密文放在一起时希望能且只能计算 μf(x)，计算结果同时依赖两边各自的信息。

这个问题的经典解决方案是姚先生的乱码电路 (garbled circuit)¹ [Yao86]，也叫随机化编码 (randomized encoding) [App17]。在 [LL20] ABE 中，当把密文和密钥放在一起时，首先计算出的就是 $\mu f(\mathbf{x})$ 的随机化编码，对随机化编码再行运算，就得到 $\mu f(\mathbf{x})$ 本身。安全性建立在如下几点上：

• 随机化编码本身安全，即编码不包括 $\mu f(\mathbf{x})$ 之外任何关于 $\mu$ 的信息。
• 计算随机化编码的过程安全，它不应该透露编码之外的任何信息（比如不能透露随机化编码所用的随机数）。
• 计算出的随机化编码使用了合适的随机数。

注意在第一点里，随机化编码不需要隐藏 f,x，因为只隐藏部分输入，所以这是一种部分乱码化方案 (partial garbling scheme) [IW14]。第二点暗示我们要用一种泛函加密 (functional encryption) 来计算编码本身。通常来说，泛函加密比属性加密要困难得多，不过内积加密 (IPFE) 相对容易一些。

Aime ce que tu as quand t’as pas ce que t’aimes !
Quand t’as pas ce que t’aimes, aime ce que tu as !

— La journée est finie, les Misérables

“爱吾所有，即使一无所有。一无所有时只得爱汝所有。”（“所有”指“拥有”而不是“全部”。）[LL20] 构造 ABE 时就用 IPFE 来计算随机化编码，这要求编码很“线性”，这些要求总结出来就是所谓的“算术密钥乱码化方案”。

算术密钥乱码化

算术密钥乱码化方案 (arithmetic key garbling scheme)²简称 AKGS，它包含两个算法：

• $\mathsf{G}\mathsf{a}\mathsf{r}\mathsf{b}\mathsf{l}\mathsf{e}(f,\alpha ,\beta ;\mathbf{r})$ 是乱码化算法，其中算术函数 $f:{\mathbb{Z}}_p^n\to {\mathbb{Z}}_p$ 的输入记作 x，另两个输入 $\alpha ,\beta \in {\mathbb{Z}}_p$ 即所谓的“算术密钥”，而 $\mathbf{r}$ 是算法使用的随机数（若干个 ${\mathbb{Z}}_p$ 中独立均匀的随机数）。算法输出若干标签函数 (label functions) L1​,…,Lm​，每个 $L_j$ 都是 $\mathbf{x}$ 的仿射函数 [affine function]（即一次函数），且 $L_j$ 的每个系数都是 $\alpha ,\beta ,\mathbf{r}$ 的线性函数。$m$ 叫做 $f$ 的乱码化规模 (garbling size)。
• $\mathsf{E}\mathsf{v}\mathsf{a}\mathsf{l}(f,\mathbf{x},{\ell }_1,\dots ,{\ell }_m)$ 是求值算法，其中 ${\ell }_j$ 叫做标签 (labels)，它们应该是 Lj​(x)。这个算法是 ${\ell }_1,\dots ,{\ell }_m$ 的线性函数，且它的输出应该是 αf(x)+β。

正确性要求对任意 $f,\mathbf{x},\alpha ,\beta$ 有 $$\mathrm{Pr}\left[\begin{array}{rl}{L}_1,\dots ,L_m& \stackrel{{}_{\$}}{\leftarrow }\mathsf{G}\mathsf{a}\mathsf{r}\mathsf{b}\mathsf{l}\mathsf{e}(f,\alpha ,\beta )\\ {\ell }_j& \leftarrow L_j(\mathbf{x})\\ \gamma & \leftarrow \mathsf{E}\mathsf{v}\mathsf{a}\mathsf{l}(f,\mathbf{x},{\ell }_1,\dots ,{\ell }_m)\end{array}:\gamma =\alpha f(\mathbf{x})+\beta \right]=1.$$

折腾这么一圈计算 $\alpha f(\mathbf{x})+\beta$ 的意义在于标签和 $\mathbf{x},\alpha ,\beta ,\mathbf{r}$ 的关系十分简单（双线性函数），而计算 $\alpha f(\mathbf{x})+\beta$ 的“大头”（关于 $\mathbf{x}$ 的复杂度）都推迟到 $\mathsf{E}\mathsf{v}\mathsf{a}\mathsf{l}$ 里面了，并且求值还是关于标签线性的。

直观上，我们想说：标签里不包含 $\alpha f(\mathbf{x})+\beta$ 之外任何关于 $\alpha ,\beta$ 的信息。为什么是标签而不是标签函数（的系数）？若 $f$ 不是常数，则由于正确性的限制，标签函数的系数总是蕴含着 α,β。另一个角度是，重复使用标签函数相当于重复使用 $\mathsf{G}\mathsf{a}\mathsf{r}\mathsf{b}\mathsf{l}\mathsf{e}$（里用来保护 α,β）的随机性，而整个计算过程惟一随机的地方即是 Garble，这样做通常不安全。

形式化来说，这里采用完美模拟安全性刻画，要求存在高效算法 $\mathsf{S}\mathsf{i}\mathsf{m}(f,\mathbf{x},\gamma )$ 来模拟 $\gamma =\alpha f(\mathbf{x})+\beta$ 时的标签 ℓ1​,…,ℓm​。这要求对任意 f,x,α,β，如下两个分布（真实标签分布和模拟标签分布）相同： $$\begin{array}{rl}\left\{\begin{array}{rl}{L}_1,\dots ,L_m& \stackrel{{}_{\$}}{\leftarrow }\mathsf{G}\mathsf{a}\mathsf{r}\mathsf{b}\mathsf{l}\mathsf{e}(f,\alpha ,\beta )\\ {\ell }_j& \leftarrow L_j(\mathbf{x})\end{array}:({\ell }_1,\dots ,{\ell }_m)\right\},& \\ \left\{\begin{array}{rl}& ({\ell }_1,\dots ,{\ell }_m)\stackrel{{}_{\$}}{\leftarrow }\\ & \mathsf{S}\mathsf{i}\mathsf{m}(f,\mathbf{x},\alpha f(\mathbf{x})+\beta )\end{array}:({\ell }_1,\dots ,{\ell }_m)\right\}.& \end{array}$$

算术公式的 AKGS

既然目标是构造支持算术公式 (arithmetic formulae) 的 ABE，自然就需要用于算术公式的 AKGS，这个方案可以看作简化版的 [AIK11, BGG⁺14]。设 $f$ 为算术公式而 α,β∈Zp​，AKGS 要计算 αf(x)+β。这里同时定义 Garble,Eval,Sim，分类讨论：

若 $f$ 是输入的仿射函数，则没什么特别要做的事儿。

• $\mathsf{G}\mathsf{a}\mathsf{r}\mathsf{b}\mathsf{l}\mathsf{e}$ 直接定义标签函数为 L(x)=αf(x)+β。
• $\mathsf{E}\mathsf{v}\mathsf{a}\mathsf{l}$ 只要输出标签 $\ell$ 本身即可。
• $\mathsf{S}\mathsf{i}\mathsf{m}$ 只要用输出值本身作为模拟标签即可。

若 f=f1​−f2​，利用 α(f1​−f2​)+β=(αf1​+β+r)−(αf2​+r)。

• $\mathsf{G}\mathsf{a}\mathsf{r}\mathsf{b}\mathsf{l}\mathsf{e}$ 抽取 $r\stackrel{{}_{\$}}{\leftarrow }{\mathbb{Z}}_p$ 并递归乱码化 (f1​,α,β+r),(f2​,α,r)，再把两次递归所得标签函数放在一起即可。
• $\mathsf{E}\mathsf{v}\mathsf{a}\mathsf{l}$ 分别对两个子公式（用对应标签）递归求值得到 γ1​,γ2​，并输出 γ1​−γ2​。
• $\mathsf{S}\mathsf{i}\mathsf{m}$ 抽取 ${\gamma }_2\stackrel{{}_{\$}}{\leftarrow }{\mathbb{Z}}_p$ 并令 γ1​=γ+γ2​，然后对子公式 $f_1,f_2$ 分别用 ${\gamma }_1,{\gamma }_2$ 作为输出进行模拟，再把两次递归所得模拟标签放在一起即可。

若 f=f1​f2​，利用 αf1​f2​+β=(rf1​+β)−(−αf2​+r)f1​。

• $\mathsf{G}\mathsf{a}\mathsf{r}\mathsf{b}\mathsf{l}\mathsf{e}$ 抽取 $r\stackrel{{}_{\$}}{\leftarrow }{\mathbb{Z}}_p$ 并递归乱码化 (f1​,r,β),(f2​,−α,r)，再把两次递归所得标签函数放在一起即可。
• $\mathsf{E}\mathsf{v}\mathsf{a}\mathsf{l}$ 分别对两个子公式（用对应标签）递归求值得到 γ1​,γ2​，并输出 γ1​−γ2​f1​(x)。
• $\mathsf{S}\mathsf{i}\mathsf{m}$ 抽取 ${\gamma }_2\stackrel{{}_{\$}}{\leftarrow }{\mathbb{Z}}_p$ 并令 γ1​=γ+γ2​f1​(x)，然后对子公式 $f_1,f_2$ 分别用 ${\gamma }_1,{\gamma }_2$ 作为输出进行模拟，再把两次递归所得模拟标签放在一起即可。

再次强调，$f,\mathbf{x}$ 都不保密且 $\mathsf{E}\mathsf{v}\mathsf{a}\mathsf{l},\mathsf{S}\mathsf{i}\mathsf{m}$ 的输入包括两者，故上述算法良定义。显然乱码化方案正确，模拟器的完美性基于如下观察：对于需要递归的公式 $f=f_1-f_2$ 或 f=f1​f2​，给定计算结果 γ=αf(x)+β，子公式 $f_2$ 的计算结果 ${\gamma }_2$ 是一个均匀随机数，且子公式 $f_1$ 的计算结果 ${\gamma }_1$ 是惟一符合求值过程正确性的那个数，这正是模拟器递归的方式。

具体例子

光说不练假把式，考虑第一篇里举例的算术公式 (2x1​−x2​)(x3​+3x2​)+(5x1​+1)x4​，它的乱码化过程可表示为下图带标注的电路树：每个运算节点旁边标注的是递归乱码化过程中这一步引入的随机数，每条输出线旁标注的是这一条线对应的 α,β。

乱码化过程如下：

1. 把公式按照结构展开为一棵树，直到展开为输入的仿射函数作为叶子为止。
2. 在根节点的输出线上标注输入的 α,β。
3. 每个非叶子节点的输出线标注完毕后根据 $\mathsf{G}\mathsf{a}\mathsf{r}\mathsf{b}\mathsf{l}\mathsf{e}$ 的递归规则标注它的输入线。

标注完毕后叶子的输出线就指示了标签函数，它们是 $$\begin{array}{rl}{\ell }_1=L_1(\mathbf{x})& =2r_1{x}_1-r_1{x}_2+(\beta +r_2),\\ {\ell }_2=L_2(\mathbf{x})& =-\alpha x_3-3\alpha x_2+r_1,\\ {\ell }_3=L_3(\mathbf{x})& =5r_3{x}_1+(r_3+r_2),\\ {\ell }_4=L_4(\mathbf{x})& =\alpha x_4+r_3.\end{array}$$ 求值运算是 αf(x)+β=(ℓ1​−ℓ2​(2x1​−x2​))−(ℓ3​−ℓ4​(5x1​+1))。给定输出为 $\gamma$ 的模拟标签是 $$\begin{array}{rlrl}{\ell }_1& =\gamma +{\gamma }_2+{\gamma }_1(2x_1-x_2),& {\ell }_2& ={\gamma }_1,\\ {\ell }_3& ={\gamma }_2+{\gamma }_3(5x_1+1),& {\ell }_4& ={\gamma }_3,\end{array}$$ 其中 γ1​,γ2​,γ3​←$​Zp​，且 ${\gamma }_{?}$ 对应于 $r_{?}$ 对应节点右子树的中间求值结果。

显然，任意算术公式的乱码化规模不超过它（作为算术公式）的规模。此外，算术公式采用不同表示方式（例如中间运算节点里减法改成“多个节点的线性组合”，乘法改成“两个节点的积加上一个常数”，并针对这种运算递归）可以稍微降低乱码化规模，不过这都属于工程优化，我们还是多关注理论。

本篇结语

本篇介绍了 [LL20] ABE 中建立信息论意义下安全性的工具——算术密钥乱码化方案。它有诸多线性性要求，安全性采用模拟范式刻画。我们还用一个例子具体理解了 AKGS（这个例子将贯穿整个系列博文）。下一次介绍如何使用泛函保密 (function-hiding) 的内积加密构造一次性安全的 ABE。

参考文献