属性加密：引子

本文是我的 2019 年科研“属性加密”系列博文的首篇，该系列博文旨在用汉语介绍我和我导师的合作论文 Compact Adaptively Secure ABE from k-Lin: Beyond ${\mathsf{N}\mathsf{C}}^1$ and Towards $\mathsf{N}\mathsf{L}$ [LL20]。在这一篇里，我将介绍属性加密的基本概念并定下一个“小目标”。

关于 2020 的怨念：因为新冠肺炎，公费去 Zagreb 旅游的机会没有了😔，不过求学和探索的脚步不能停止。（当然，今年的坏事儿可不止肺炎。）

属性加密

属性加密 (ABE) 全称基于属性的加密 (attribute-based encryption)，起源于 2005 年 Sahai、Waters 提出的模糊身份加密 (fuzzy identity-based encryption)  [SW05, GPSW06]，是一种公钥加密方案。它是更早的身份加密 (IBE) 的扩展 [Sha84, BF01]。一句话来说的话，属性加密就是用密码学施行的 (cryptographically enforced) 访问控制列表 (access control list)。

在属性加密中有一个权威机构 (authority)，它负责选择一个谓词 $P:X\times Y\to \{0,1\}$ 并生成整个系统的公钥和主密钥。任何人都可以用公钥加密任何消息，并且每个密文都和一个属性 $x\in X$ 相关联；权威机构可以（利用主密钥）颁发受限密钥（通常是颁发给有特定权限的用户），每个受限密钥和一个属性 $y\in Y$ 相关联。解密密文使用的是受限密钥，且解密能够成功当且仅当 P(x,y)=1，这就是说，每个用户只能解密他具有权限访问的密文（权限用 $y$ 描述）。

常见的 ABE 有两种，“密钥策略 (key-policy / KP) ”和“密文策略 (ciphertext-policy / CP) ”。在 KP-ABE 中，$x$ 是程序的输入（狭义的“属性”），而 $y$ 是输出一个 bit 的程序（狭义的“策略”），而 $P(x,y)$ 就是“程序 $y$ 在输入 $x$ 时的输出”。在 CP-ABE 中，密钥和属性关联，密文和策略关联。

在 ABE 中，属性 $x,y$ 都是公开的，惟一需要保护的是消息本身。这样的加密方案在安全方面要求抗乌合 (collusion-resistant)：多个单独不能解密某个密文的用户在一起合作，仍然不能解密该密文。这里我援引 Wee 在 ASIACRYPT 2016 受邀讲座 [Wee16] 里的一个例子：

考虑一个婚恋网站，假设你想发布相亲信息——信息里有很多私人数据——所以你希望只有你心仪的约会对象可以解密你的信息。这个需求可以用 CP-ABE 实现，如下图：

👤

相亲信息🔒
$\to$
(高 && 皮肤黝黑 && 帅)
|| (博士 && 计算机科学)

👥👥
👥👥👥
👥👥👥👥
👥👥👥

用户注册时向婚恋网站提交认证信息，认证通过后即可获得对应属性的密钥。假设有两个串通好的用户，一个长得高、皮肤黝黑但不是很帅且是计算机科学硕士，另一个长得不高、皮肤白嫩但是很帅，是生物学博士，这两个人就分别有两个密钥，对应于他们的属性（高、皮肤黝黑、计算机科学；帅、博士）。如果这两个人共享他们的密钥，那么他们仍然不应该能解密上述相亲信息。

这个例子也表明对合取式策略（就是一堆属性的“且”）单纯地嵌套加密是不安全的。

语法和正确性

现在来形式化定义 ABE。简单起见，固定消息（明文）集合 $M$ 以及属性集合、谓词 P:X×Y→{0,1}，一个适用于 $P$ 的 ABE 有 4 个高效随机算法：¹

• $\mathsf{S}\mathsf{e}\mathsf{t}\mathsf{u}\mathsf{p}$ 是初始化算法，输出公钥/主密钥对 (mpk,msk)。
• $\mathsf{K}\mathsf{e}\mathsf{y}\mathsf{G}\mathsf{e}\mathsf{n}(\mathsf{m}\mathsf{s}\mathsf{k},y)$ 是受限密钥生成算法，用来生成和 $y$ 相关联的密钥 sky​。
• $\mathsf{E}\mathsf{n}\mathsf{c}(\mathsf{m}\mathsf{p}\mathsf{k},x,g)$ 是加密算法，用来产生加密了消息 $g$ 且和 $x$ 相关联的密文 ctx​(g)。
• $\mathsf{D}\mathsf{e}\mathsf{c}(\mathsf{s}\mathsf{k},\mathsf{c}\mathsf{t})$ 是解密算法，它输出一条消息（解密结果）或者一个特殊的符号 $\perp$ 表示“不能解密”或者“解密出错”。

正确性要求对任意满足 $P(x,y)=1$ 的 $x,y$ 以及任意 g∈M，都有 $$\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}()\\ \mathsf{s}\mathsf{k}& \stackrel{{}_{\$}}{\leftarrow }\mathsf{K}\mathsf{e}\mathsf{y}\mathsf{G}\mathsf{e}\mathsf{n}(\mathsf{m}\mathsf{s}\mathsf{k},y)\\ \mathsf{c}\mathsf{t}& \stackrel{{}_{\$}}{\leftarrow }\mathsf{E}\mathsf{n}\mathsf{c}(\mathsf{m}\mathsf{p}\mathsf{k},x,g)\end{array}|\mathsf{D}\mathsf{e}\mathsf{c}(\mathsf{s}\mathsf{k},\mathsf{c}\mathsf{t})=g\right]=1.$$

安全性

这里采用基于不可区分性的安全性，不过和上次内积加密不同，这次用猜测博弈定义。考虑使坏者 (adversary) $\mathcal{A}$ 和挑战者 (challenger) $\mathcal{C}$ 进行如下博弈：

• 初始化：$\mathcal{C}$ 运行 $(\mathsf{m}\mathsf{p}\mathsf{k},\mathsf{m}\mathsf{s}\mathsf{k})\stackrel{{}_{\$}}{\leftarrow }\mathsf{S}\mathsf{e}\mathsf{t}\mathsf{u}\mathsf{p}()$ 并把 $\mathsf{m}\mathsf{p}\mathsf{k}$ 发送给 A。
• 询问 I：$\mathcal{A}$ 可以进行任意多轮询问，每轮它可以向 $\mathcal{C}$ 发送一个 yi​∈Y，$\mathcal{C}$ 收到后运行 ${\mathsf{s}\mathsf{k}}_i\stackrel{{}_{\$}}{\leftarrow }\mathsf{K}\mathsf{e}\mathsf{y}\mathsf{G}\mathsf{e}\mathsf{n}(\mathsf{m}\mathsf{s}\mathsf{k},y_i)$ 并把 ${\mathsf{s}\mathsf{k}}_i$ 返回给 A。
• 挑战：$\mathcal{A}$ 发送一个 $x\in X$ 和两条消息 g1​,g2​∈M，其中 $x$ 必须满足 $P(x,y_i)=0$ 对所有 $i$ 成立（这个密文必须不能被 $\mathcal{A}$ 已经知道的密钥解密）。$\mathcal{C}$ 收到后均匀随机地选择 b←$​{0,1}，运行 $\mathsf{c}\mathsf{t}\stackrel{{}_{\$}}{\leftarrow }\mathsf{E}\mathsf{n}\mathsf{c}(\mathsf{m}\mathsf{p}\mathsf{k},x,g_b)$ 并把挑战密文 $\mathsf{c}\mathsf{t}$ 发送给 A。
• 询问 II：同询问 I，但任何询问必须满足 $P(x,y_i)=0$（新的密钥必须不能解密挑战密文）。
• 猜测：$\mathcal{A}$ 输出 b′∈{0,1}，它获胜当且仅当 b=b′。

ABE 安全（准确说是 IND-CPA——在选择明文攻击下密文不可区分 [ciphertext-indistinguishable under chosen plaintext attack]）当且仅当对任意高效²的使坏者 A，都有³ $\mathrm{Pr}[\mathcal{A}\text{ wins}]-{}^1/{}_2$（即使坏者的优势 [advantange]） 是可忽略 (negligible)⁴函数。

这个定义是在用形式化语言表达“如果设计上应该不能解密，那确实就不能解密”。用大白话来说：使坏者可以获得任意多个密钥和一个密文，密钥、密文关联的属性都任它选择（而且这种选择是适应性的，就是说查询和挑战都可以基于它已经获得的信息选择），并且使坏者也知道密文加密的是某两条消息之一；使坏者的任务是搞清楚密文里面加密的是哪一条消息，为了不“白送”（让使坏者通过加密方案的正确性平凡地获胜），我们要求它获得的密钥都不应该能解密挑战密文。

至于 IND-CPA 如何体现“选择明文攻击”以及多个密文的安全性问题，读者可参考《内积加密：公钥 IPFE 和 CPA 安全性》里关于 IND-CPA 的讨论。

“小”目标

我们希望构造具有如下好性质的 ABE 方案：

• 它的 IND-CPA 安全性可以归结为常用假设。
• 密文、密钥长度和具体使用的 $x,y$ 长度分别成正比。
• 支持表达力很强的谓词。

第一条实际上可以拆成两条：一是要求适应性安全 (adaptive security)，即使坏者的任意选择都可以基于先前已经获得的信息（弱化版本是限制使坏者必须一开始就选择挑战密文的属性 x）；二是要求安全性基于标准假设。

之前，满足前两条的最高表达力的谓词是 NC1，即布尔公式 (Boolean formulae)，这归功于 [KW19]（我有一篇写得很烂的笔记）。本系列博文要介绍的工作 [LL20] 支持算术分支程序 (arithmetic branching programs) 表达的谓词，这个工作基于双线性群里的 ${\text{MDDH}}_k$ 假设。这系列博文里主要介绍针对算术公式 (arithmetic formulae) 的做法，并且采用 DDH 假设。

算术公式是形如 $(2x_1-x_2)(x_3+3x_2)+(5x_1+1)x_4$ 的形式表达式。它是由未定元和整数进行有限次求差、求积得出的表达式，运算的次数加一定义为它的规模 (size)。固定质数 p，则一个 $n$ 元算术公式 $f$ 自然定义了 f:Zpn​→Zp​，即把每个未定元替换为自变量的值后求值的函数。

我们即将讨论的 ABE 方案里，密文属性是 x∈Zpn​，密钥属性是算术公式 f，解密条件是 f(x)​=0，即 $$P(\mathbf{x},f)=\{\begin{array}{ll}1,& f(\mathbf{x})\ne 0;\\ 0,& f(\mathbf{x})=0.\end{array}$$

关于算术公式的定义有两个值得注意的地方。在算术公式中，一个未定元可以出现⁵任意多次。算术公式不直接支持 (natively support) 乘方运算，例如 $x^{10}$ 的规模是 10 而不是 2，因为这个公式的标准写法是 xxxxxxxxxx。

此外，自然也可以考虑解密条件是 $f(\mathbf{x})=0$ 的 ABE 方案。跃跃欲试的读者可能会提出这可以直接用 费马小定理 归约为“非零解密”的 ABE，即利用 $$(1-f^{p-1})(\mathbf{x})=\{\begin{array}{ll}0,& f(\mathbf{x})\ne 0;\\ 1,& f(\mathbf{x})=0.\end{array}$$ 然而这不行，因为 $1-f^{p-1}$ 的规模是 $f$ 规模的 $p-1$ 倍，而通常 $p$ 很大（超过任何多项式）。好在将要构造的 ABE 可以同时处理两种解密条件，这里省略一种只是为了简化。

本篇结语

这一篇介绍了属性加密的概念，定义了属性加密（包括安全性），并定下了一个小目标——基于 ${\text{MDDH}}_k$ 假设构造支持算术公式的 ABE。下一篇介绍 [LL20] 构造中建立信息论意义下安全性的核心工具——算术密钥乱码化方案 (arithmetic key garbling scheme)。

参考文献