属性加密：1-ABE

本文是我的 2019 年科研“属性加密”系列博文第三篇。在这一篇里，我将介绍 [LL20] 里构造一次性安全的属性加密方案（叫做 1-ABE）的思路——使用内积加密计算算术密钥乱码化方案的标签。本文有彩蛋！

前情提要

第一篇里介绍了属性加密 (ABE) 的概念：密文和属性相关联，密钥和策略相关联，解密成功当且仅当策略允许属性。我们定了一个“小目标”：构造支持算术公式的 ABE。

第二篇里定义了算术密钥乱码化方案 (arithmetic key garbling scheme)，简称 AKGS：把 $f,\alpha ,\beta$ 乱码化可得若干标签函数 (label functions) L1​,…,Lm​，把 $\mathbf{x}$ 代入就得到标签 (labels) ℓ1​,…,ℓm​，通过 $f,\mathbf{x},{\ell }_1,\dots ,{\ell }_m$ 可还原 αf(x)+β，且标签中无任何其他关于 $\alpha ,\beta$ 的信息。此外，还构造了用于算术公式 (arithmetic formulae) 的 AKGS。

思路回顾

先来考虑一个简化情况，不考虑抗乌合 (collusion resistance)，只需要在单个密钥、单个密文、随机消息（稍后解释这是什么意思）的情况下安全，且只考虑私钥方案，这种情况下的 ABE 叫做 1-ABE。此外，为了方便，再加一个小修改：把消息放在密钥里（即和算术公式 $f$ 关联）。这对于私钥方案没问题，因为可以把 $\mu$ 当作实际消息的一次性密钥。

假设希望当 $f(\mathbf{x})\ne 0$ 时可以还原消息 μ，[LL20] 利用内积加密 (IPFE) 构造 1-ABE，当密文和密钥放在一起时，首先算得 $f,\mu ,0$ 乱码化的标签，然后进行 AKGS 求值即得到 μf(x)+0。

具体来说，[LL20] 会用到泛函保密 (function-hiding) 的内积加密。之前我已在“内积加密”系列文章中介绍过其语法、语义、安全性、具体构造，而且用到了双线性群。不过就目前来说，它用了双线性群这一点只和正确性有点关系，和（一次性）安全性关系不大。这里快速回忆（并重命名）一下 IPFE 的四个算法：

• $\mathsf{I}\mathsf{P}\mathsf{S}\mathsf{e}\mathsf{t}\mathsf{u}\mathsf{p}(1^n)$ 输入向量维数 n，它用来生成主密钥 imsk。
• $\mathsf{I}\mathsf{P}\mathsf{K}\mathsf{e}\mathsf{y}\mathsf{G}\mathsf{e}\mathsf{n}(\mathsf{i}\mathsf{m}\mathsf{s}\mathsf{k},\mathbf{v})$ 生成对应于 $\mathbf{v}$ 的密钥 isk。
• $\mathsf{I}\mathsf{P}\mathsf{E}\mathsf{n}\mathsf{c}(\mathsf{i}\mathsf{m}\mathsf{s}\mathsf{k},\mathbf{u})$ 生成对应于 $\mathbf{u}$ 的密文 ict。
• $\mathsf{I}\mathsf{P}\mathsf{D}\mathsf{e}\mathsf{c}(\mathsf{i}\mathsf{s}\mathsf{k},\mathsf{i}\mathsf{c}\mathsf{t})$ 输出密钥里的向量和明文向量的内积。

方便起见，用 $\mathsf{i}\mathsf{s}\mathsf{k}(\mathbf{v}),\mathsf{i}\mathsf{c}\mathsf{t}(\mathbf{u})$ 表示正常生成的、对应于 $\mathbf{v},\mathbf{u}$ 的密钥、密文。重命名是为了和 ABE 算法、密钥、密文区分开来。

构造 1-ABE

既然 AKGS 标签函数 $L_1,\dots ,L_m$ 是 $\mathbf{x}$ 的仿射函数，那么可以写出每个 $L_j$ 的系数向量 Lj​，它满足 Lj​(x)=⟨Lj​,(1,x)⟩。可以用 IPFE 加密系数向量和属性，解密时先用 IPFE 解密算法得到 AKGS 标签，然后再进行 AKGS 求值即可。1-ABE 构造如下：

• $\mathsf{S}\mathsf{e}\mathsf{t}\mathsf{u}\mathsf{p}$ 运行 $\mathsf{i}\mathsf{m}\mathsf{s}\mathsf{k}\stackrel{{}_{\$}}{\leftarrow }\mathsf{I}\mathsf{P}\mathsf{S}\mathsf{e}\mathsf{t}\mathsf{u}\mathsf{p}(1^{n+1})$ 并令 msk=imsk。
• $\mathsf{K}\mathsf{e}\mathsf{y}\mathsf{G}\mathsf{e}\mathsf{n}(\mathsf{m}\mathsf{s}\mathsf{k},f,\mu )$ 用 IPFE 生成一堆密钥，其中密钥里的向量是 $f,\mu ,0$ 乱码化标签函数的系数向量，这些 IPFE 密钥和 $f$ 本身构成了 ABE 密钥： $$\begin{array}{rl}{L}_1,\dots ,L_m& \stackrel{{}_{\$}}{\leftarrow }\mathsf{G}\mathsf{a}\mathsf{r}\mathsf{b}\mathsf{l}\mathsf{e}(f,\mu ,0),\\ \forall j\in [m]\text{:}{\mathsf{i}\mathsf{s}\mathsf{k}}_j& \stackrel{{}_{\$}}{\leftarrow }\mathsf{I}\mathsf{P}\mathsf{K}\mathsf{e}\mathsf{y}\mathsf{G}\mathsf{e}\mathsf{n}(\mathsf{i}\mathsf{m}\mathsf{s}\mathsf{k},{\mathbf{L}}_j),\\ \mathsf{s}\mathsf{k}& =(f,{\mathsf{i}\mathsf{s}\mathsf{k}}_1,\dots ,{\mathsf{i}\mathsf{s}\mathsf{k}}_m).\end{array}$$
• $\mathsf{E}\mathsf{n}\mathsf{c}(\mathsf{m}\mathsf{s}\mathsf{k},\mathbf{x})$ 产生对应于 $(1,\mathbf{x})$ 的 IPFE 密文，它和 $\mathbf{x}$ 本身构成了 ABE 密文： $$\mathsf{i}\mathsf{c}\mathsf{t}\stackrel{{}_{\$}}{\leftarrow }\mathsf{I}\mathsf{P}\mathsf{E}\mathsf{n}\mathsf{c}(1,\mathbf{x}),\mathsf{c}\mathsf{t}=(\mathbf{x},\mathsf{i}\mathsf{c}\mathsf{t}).$$
• $\mathsf{D}\mathsf{e}\mathsf{c}(\mathsf{s}\mathsf{k},\mathsf{c}\mathsf{t})$ 先计算 f(x)，若等于 0 则输出 $\perp$ 并结束，否则先用 IPFE 解密获得 AKGS 标签，再用 AKGS 求值得 μ′=μf(x)+0，最后除以 $f(\mathbf{x})$ 即可： $$\begin{array}{rl}\forall j\in [m]\text{:}{\ell }_j& \leftarrow \mathsf{I}\mathsf{P}\mathsf{D}\mathsf{e}\mathsf{c}({\mathsf{i}\mathsf{s}\mathsf{k}}_j,\mathsf{i}\mathsf{c}\mathsf{t}),\\ {\mu }^{\prime }& \leftarrow \mathsf{E}\mathsf{v}\mathsf{a}\mathsf{l}(f,\mathbf{x},{\ell }_1,\dots ,{\ell }_m),\\ \mu & ={\mu }^{\prime }/f(\mathbf{x}).\end{array}$$

正确性显而易见。在实际的方案中，所用的 IPFE 基于双线性群，得到的是群编码的 $[[{\ell }_j{]]}_{\text{T}}$ 而不是裸的 ℓj​∈Zp​，好在 AKGS $\mathsf{E}\mathsf{v}\mathsf{a}\mathsf{l}$ 关于 ${\ell }_j$ 线性，且除以 $f(\mathbf{x})$ 也线性，故两者可在指数中（同态）进行并得到 [[μ]]T​。虽然这个方案不能还原 $\mu \in {\mathbb{Z}}_p$ 本身，不过它也不是最终方案，我们以后会解决这个问题。（上述论证不适用于 x，$\mathsf{E}\mathsf{v}\mathsf{a}\mathsf{l}$ 需要在知道 $\mathbf{x}$ 本身的情况下才能进行。）

安全性

之前说过 1-ABE 安全性只需要对单个密钥、单个密文、随机消息成立，前两点限制很好理解，第三点是这个意思：在安全博弈 (security game) 中，密钥总是针对一条随机消息 $\mu$ 生成，并且在生成密钥时额外告诉使坏者 (adversary) 一条消息 μ^​；当 $b=0$ 时 μ^​=μ，当 $b=1$ 时 $\hat{\mu }$ 是和 $\mu$ 独立的均匀随机数；使坏者的任务是猜测这两种情况中哪一种发生了。

换言之，使坏者需要判断它收到的密钥里蕴含的是它收到的消息，还是蕴含着另一条独立随机消息。熟悉密码学的读者容易发现这类似于密钥封装机制 (key-encapsulation mechanism)、非交互式密钥协商 (non-interactive key exchange) 安全性的定义，也类似于 [BS20] 中随机消息的语义安全性。

直观上讲，安全性似乎显而易见：IPFE 的安全性保证使坏者只能计算标签，而 AKGS 安全性保证一组标签里不包含 $\mu f(\mathbf{x})$ 之外关于 $\mu$ 的任何信息。因为在 ABE 安全博弈中使坏者查询的密钥、密文对应的策略、属性必须满足 $f(\mathbf{x})=0$（即“不允许解密”），所以标签里不包含任何关于 $\mu$ 的信息，这样的话 $\hat{\mu }$ 无论是等于 $\mu$ 还是独立随机，都只不过是一个独立于其他东西的随机数罢了，故使坏者无法猜出是哪种情况。

顺着这个思路很容易写出证明。回忆泛函保密性 (function-hiding) 即 IND-FH：它允许我们更改 IPFE 密钥、密文里的向量，只要对应内积保持不变，这种改变就不可区分。考虑如下过渡论证：

注意 ⟨Lj​,(1,x)⟩=Lj​(x)=⟨(Lj​(x),0),(1,x)⟩，故 IND-FH 保证 Exp1-ABE​≈H1​。

在 ${\mathsf{H}}_2$ 中 ${\ell }_j$ 由 AKGS 标签模拟算法生成，由 AKGS 完美模拟安全性可知 H1​≡H2​。注意模拟器的输入是 f,x,μf(x)=0，和 $\mu$ 独立，故 ${\mathsf{H}}_2$ 中的东西除了 $\hat{\mu }$ 都和 $\mu$ 独立。无论 $b=0$ 还是 b=1，使坏者收到的 $\hat{\mu }$ 都是一个和其他东西都独立的均匀随机数，整个博弈和 $b$ 独立，故使坏者猜对 $b$ 的概率是 1/2​，这就完成了安全性证明。

证毕……了吗？上面的证明看起来有模有样，实则暗藏谬误，是诈和。你能找到错误在哪儿吗？验证证明最直接的方法是只用形式逻辑思考并尝试自己说服自己，把过渡实验的回答方式、归约算法都具体写出来看看！

画外 直觉思考也必不可少，良好的直觉建立在长年累月对形式化的熟稔之上，我在这方面还有很长的路要走。

本篇结语

这一篇里我介绍了 [LL20] 中用 AKGS 和 IPFE 构造单个密钥、单个密文、随机消息安全的 ABE（即 1-ABE）的方法，不过，我给出了一个“错误”的安全证明，并且作为一个小悬念留了下来。下一次我会先解释目前的安全证明错误在哪儿，然后给出初步解决方案。后面的几篇会是这个系列里最精彩的部分，会详实记录文献中“冰冷的美丽”背后“火热的思考”。

参考文献