[KW19] 标准假设下适用于 NC¹ 策略的紧凑、适应性安全的属性加密

本文的创建日期设置为决定在密码学读书会上讲这篇文章的日期，这篇总结是那时起到密码学读书会之前的几周内断断续续写的，初次公开时已经是创建日期之后很久了。

Kowalczyk 和 Wee 在 EUROCRYPT 2019（欧密会）上发表的文章 [KW19] Compact Adaptively Secure ABE for ${\mathsf{N}\mathsf{C}}^1$ from $k$-Lin 可以说是彻底解决了 ${\mathsf{N}\mathsf{C}}^1$ 访问策略的属性加密问题。我在最近的密码学读书会上将讲述该文，这篇博文算是我用母语对该文章的总结（感觉我脑内思考语言仍然是汉语），也算是在中文密码学社区里传播知识。

本文大部分内容是 [KW19] 的翻译，因为翻译部分太多，就不全都加上双引号了，以免干扰阅读。Kowalczyk 和 Wee 的文章写得非常好——我大概几个小时就弄懂了其重点（起初我并不知道其中的两个工具），对于能够阅读英文的读者，直接阅读 文献 当然是最好的选择。

属性加密

（密钥策略的）属性加密（key-policy attribute-based encryption 或称 ABE）是一种公钥加密方案，其中密文和属性绑定，私钥和访问策略绑定，只有访问策略允许属性时，私钥才可解密密文，否则不能解密，并且这样的加密方案应该可以抵御数个持有不能解密私钥的攻击者联手尝试的情况。

一个经典的例子是：假设属性的长度是两位，分别代表是否必须是政府高官才能看、是否必须是公司高层才能看，甲是是政府高官但不是公司高层（持有一个私钥），乙不是政府高官且是公司高层（持有另一个私钥），则这两者的私钥放在一起仍然不能解密一条必须是政府高官且是公司高层才能解密的密文。

形式化来说，ABE 的语法和语义是（这些算法都是概率多项式时间的）：

• 初始化算法根据安全参数和属性长度产生公钥（master public key）和万能私钥（master secret key）：Setup(1λ,1n)→(mpk,msk)。
• 密钥生成算法根据万能私钥和访问策略 $f:\{0,1{\}}^n\to \{0,1\}$ 生成限制于 $f$ 的私钥：KeyGen(msk,f)→skf​。
• 加密算法根据公钥、属性 $x\in \{0,1{\}}^n$ 和消息 $m\in \{0,1\}$ 产生密文：Enc(mpk,x,m)→ctx,m​。
• 解密算法根据受限私钥、访问策略、密文、属性进行解密，如果私钥和策略对应、密文和属性对应且 f(x)=1，则要求解密总是成功：Dec(skf​,f,ctx,m​,x)=m。

一个 ABE 方案并不一定要能够处理所有可能的策略函数 $f$——或者说一定不能——一共有 $2^{2^n}$ 个可能的策略函数，仅仅是描述所有可能的策略函数也必定用到超多项式长度的串。所以我们通常只考虑一类特殊的 f。最容易想到的是 P，多项式时间可计算的策略。确实有适用于 $\mathsf{P}$ 的 ABE 的构造，不过本文考虑的范围更小，是 NC1，对数深度电路可计算的函数。

安全定义刻画了“任意多个不能解密的密钥放在一起也不能解密”的要求。对使坏者（adversary）$\mathcal{A}$ 和 b∈{0,1}，定义实验 $G_b^{\mathcal{A}}$ 为如下过程：

1. 运行初始化算法 Setup→(mpk,msk)，向 $\mathcal{A}$ 发送 mpk。
2. $\mathcal{A}$ 可以进行若干次密钥询问和若干次密文询问（顺序随 $\mathcal{A}$ 的便，密文询问可以在两次密钥询问中间）：
   • 进行密钥询问时，$\mathcal{A}$ 选择一个访问策略 $f:\{0,1{\}}^n\to \{0,1\}$ 并获得 skf​←KeyGen(msk,f)。
   • 进行密文询问时，$\mathcal{A}$ 选择一个属性 $x\in \{0,1{\}}^n$ 和两个密文 $m_0,m_1\in \{0,1\}$ 并获得 ctx,m​←Enc(mpk,x,mb​)。
3. 如果在询问期间某个策略 $f$ 和某个属性 $x$ 满足 f(x)=1，则实验的结果是 0。
4. 否则，使坏者 $\mathcal{A}$ 最终输出一位 b′，它就是实验的结果。

所谓一个 ABE 方案安全，就是说对任意多项式时间使坏者 A，都有（下式叫做 $\mathcal{A}$ 的优势） $$\mathrm{Pr}\left[G_0^{\mathcal{A}}\to 1\right]-\mathrm{Pr}\left[G_1^{\mathcal{A}}\to 1\right]$$ 是 $\lambda$ 的可忽略函数。

以上定义的安全性叫做适应性安全，如果我们要求 $\mathcal{A}$ 在看到 $\mathsf{m}\mathsf{p}\mathsf{k}$ 后一股脑选好所有的 $f^{(1)},f^{(2)},\dots ,f^{(s)}$ 以及 x(1),m0(1)​,m1(1)​,…,x(t),m0(t)​,m1(t)​，则（这种较弱的安全性）叫做选择性安全。

此外，ABE 也可以定义私钥版本，语法、语义上的区别在于没有公钥，并且加密需要使用私钥，安全性定义上的区别在于使坏者将不再看到公钥，但仍然可以查询任意多（多项式那么多次）密文和受限制私钥。

[KW19] ABE 的新处

这篇工作第一次构造出同时满足以下四个性质的 ABE：

• 密文长度只和属性长度有关（紧凑性），和策略函数的大小（可以想成把策略写成 C 语言之后源码的长度）无关，即使该策略多次令同一个属性参与运算；
• 是适应性安全的（归约产生的安全损失是多项式级别的，以前使用标准假设的紧凑方案和证明得到的安全损失是超多项式级的）；
• 只用简单、标准的困难假设（以前的紧凑且适应性安全的方案使用了人们研究不够透彻的困难性假设）；
• 可以用素数阶非对称双线性群构造。

简化考虑

在这篇读书笔记中，有如下的简化：

• 只考虑多项式大小的、只用 AND 和 OR 组成的逻辑公式 f。
  • 多项式大小的公式和 ${\mathsf{N}\mathsf{C}}^1$（对数深的电路）是等价的，原文也总是先把电路公式化。
  • 只用 AND 和 OR 写出来的逻辑公式是单调的，注意这和逻辑公式对应的谓词的单调性是两码事。
  • 原文主体也只考虑单调逻辑公式，因为对于公式来说可以把 NOT 逐层传递到自变量上，然后让自变量增加一倍（每个多出来的变量就存储原变量的否定），这样就总是可以把任意公式写成（另一些变量下的）单调公式，而不会显著增加各参数大小。
• 只考虑私钥版本的 ABE，且只考虑一次密钥查询和一次密文查询的情况。
  • 原文精华在于如何构造一个证明策略来证明（在无公钥、单密钥、单密文的适应性选择明文攻击下）方案是适应性安全的，非对称双线性群的使用是构造中很小的一部分。
  • 原文提到支持公钥和多个密钥是一次教科书级别对双系统加密法 [Wat09] 的应用。我个人阅读文章时，是改用 [Wee17] 附录中的适应性安全 IPE 实例化 [LV16] 中的 slotted IPE 来代替这一步骤的。（不过在读书会开始之前我仍然需要理解什么是双系统加密法。）
  • 标题中的 $k$-Lin 只是用来构造能够使用双系统加密法的公钥加密方案的。
  • 由于这个步骤不是我想转述的重点，故做此替换来简化讨论。原文的抽象构造是基于公钥加密方案的，不过私钥加密方案在这里也没区别。

路线图

之前我们已经介绍了 ABE 的概念，并提到了私钥版本的 ABE。为了介绍 [KW19] 构造的 ABE 方案，我们需要几个工具——私钥加密（SKE）、${\mathsf{N}\mathsf{C}}^1$ 秘密分发（secret sharing）。介绍了这些工具之后我们就可以给出 [KW19] 的 ABE 构造（的变体），并思考证明的初步思路。在初步思路形成后我们介绍分段猜测法（piecewise guessing framework）和 ${\mathsf{N}\mathsf{C}}^1$ 摆石子策略（pebbling strategy），最终给出完整的证明思路。

我们将会使用 SKE 构造 ABE，每个 ABE 密钥将是若干个 SKE 密文，一个 ABE 密文将是若干个 SKE 密钥。ABE 密钥里 SKE 密文的明文通过秘密分发方案来生成。在可以解密时，解密算法解密 SKE 密文并进行另外一些和策略函数 $f$ 的结构有关的计算来还原明文；在不能解密时，我们将使用分段猜测法，将 ABE 的安全性归结于 SKE 的安全性、秘密分发的安全性、摆石子策略的高效性。

启程之前，先完整形式化定义私钥 ABE 方案和适应性单次安全性。和公钥版本不同的地方已经加了下划线。

• 初始化算法根据安全参数和属性长度产生万能私钥：Setup(1λ,1n)→msk。
• 密钥生成算法根据万能私钥和访问策略 $f:\{0,1{\}}^n\to \{0,1\}$ 生成限制于 $f$ 的私钥：KeyGen(msk,f)→skf​。
• 加密算法根据万能私钥、属性 $x\in \{0,1{\}}^n$ 和消息 $m\in \{0,1\}$ 产生密文：Enc(msk,x,m)→ctx,m​。
• 解密算法根据受限私钥、访问策略、密文、属性进行解密，如果私钥和策略对应、密文和属性对应且 f(x)=1，则要求解密总是成功：Dec(skf​,f,ctx,m​,x)=m。

对使坏者 $\mathcal{A}$ 和 b∈{0,1}，定义实验 $G_b^{\mathcal{A}}$ 为如下过程：

1. 运行初始化算法 Setup→msk，启动 $\mathcal{A}$（它只知道安全参数）。
2. $\mathcal{A}$ 可以进行一次密钥询问和一次密文询问（顺序随 $\mathcal{A}$ 的便）：
   • 进行密钥询问时，$\mathcal{A}$ 选择一个访问策略 $f:\{0,1{\}}^n\to \{0,1\}$ 并获得 skf​←KeyGen(msk,f)。
   • 进行密文询问时，$\mathcal{A}$ 选择一个属性 $x\in \{0,1{\}}^n$ 和两个密文 $m_0,m_1\in \{0,1\}$ 并获得 ctx,m​←Enc(msk,x,mb​)。
3. 如果询问满足 f(x)=1，则实验的结果是 0。
4. 否则，使坏者 $\mathcal{A}$ 最终输出一位 b′，它就是实验的结果。

所谓一个私钥 ABE 方案适应性单次安全，就是说对任意多项式时间使坏者 A，都有（优势） $$\mathrm{Pr}\left[G_0^{\mathcal{A}}\to 1\right]-\mathrm{Pr}\left[G_1^{\mathcal{A}}\to 1\right]$$ 是 $\lambda$ 的可忽略函数。

私钥加密

私钥是一个加密方案 SKE=(Gen,Enc,Dec)：

• $\mathsf{G}\mathsf{e}\mathsf{n}$ 生成密钥 sk。
• $\mathsf{E}\mathsf{n}\mathsf{c}(\mathsf{s}\mathsf{k},x)$ 生成对应于 $x$ 的密文 ctx​。
• $\mathsf{D}\mathsf{e}\mathsf{c}(\mathsf{s}\mathsf{k},{\mathsf{c}\mathsf{t}}_x)$ 得到 x。

在这篇笔记中，我们将会黑箱使用私钥加密。需要用到的性质是 IND-CPA（选择明文攻击下的不可区分性），它的定义用到了如下的过程 GbA​：

1. 运行初始化算法 Setup→msk，启动 A。
2. $\mathcal{A}$ 可以进行若密文询问，每次询问 $\mathcal{A}$ 选择一对明文 $(x_i^{(0)},x_i^{(1)})$ 并获得 cti​←Enc(sk,xi(b)​)。
3. 使坏者 $\mathcal{A}$ 最终输出一位 b′，它就是实验的结果。

一个私钥加密方案满足 IND-CPA 安全性，就是说对于任意概率多项式时间使坏者 A，有（优势） $$\mathrm{Pr}\left[G_0^{\mathcal{A}}\to 1\right]-\mathrm{Pr}\left[G_1^{\mathcal{A}}\to 1\right]$$ 是 $\lambda$ 的可忽略函数。

${\mathsf{N}\mathsf{C}}^1$ 秘密分发（secret sharing）

${\mathsf{N}\mathsf{C}}^1$ 秘密分发是根据单调逻辑公式控制对秘密的恢复权限的工具，具体来说是两个高效算法 (Share,Reconstruct)：

• 对任意秘密 $\mu$（有限域中的元素）和 $n$ 元逻辑公式 f，$\mathsf{S}\mathsf{h}\mathsf{a}\mathsf{r}\mathsf{e}(\mu ,f)$ 输出一组向量 $({\vec{\mu }}_0,\dots ,{\vec{\mu }}_n)$（注意，每个 ${\vec{\mu }}_i$ 都是一个向量，且它们的长度之间没有必然联系）。
• 对任意属性 x∈{0,1}n：
  • 若 f(x)=1，则 $\mathsf{R}\mathsf{e}\mathsf{c}\mathsf{o}\mathsf{n}\mathsf{s}\mathsf{t}\mathsf{r}\mathsf{u}\mathsf{c}\mathsf{t}(f,x,{\vec{\mu }}_0,{({\vec{\mu }}_i)}_{x_i=1})$ 输出原先的秘密 μ；
  • 若 f(x)=0，则 $(f,x,{\vec{\mu }}_0,{({\vec{\mu }}_i)}_{x_i=1})$ 的分布不随着原先的秘密 $\mu$ 变化。

最初使用秘密分发的场合是要把一个秘密分成好多份（shares），每份由一个实体获得，只有当一组被策略所允许的实体聚在一起时才可恢复原先的秘密（例子：危险化学品只有 3 个管理员中至少 2 个同意才可取出）。这里每个实体的“存在性”就由 $x_i$ 所代表。[KW19] 的构造使用 ${\mathsf{N}\mathsf{C}}^1$ 秘密分发，这也是为什么必须先把公式写成单调公式的原因——如果一组实体聚在一起可以还原秘密，那么更多实体聚在一起当然也可以还原。

如何构造这样的一个秘密分发？[KW19] 的秘密分发方案的 $\mathsf{S}\mathsf{h}\mathsf{a}\mathsf{r}\mathsf{e}$ 算法是这样进行的：

1. 把公式写成一个二叉树，并在树根（也就对应公式电路里的输出门）上方加上一根电线，设置它的值为 $\mu$（将要分发的秘密）。
2. 为二叉树上的其他边（也就对应公式电路本身的每条电线）设置一个随机数 μ^​w​。
3. 二叉树的每个节点（也就对应公式电路里的每个门）对输出的 ${\vec{\mu }}_i$ 有如下贡献（遍历每个门并执行如下操作）：
   • 如果这是对应于 $x_i$ 的输入门（叶子节点），则向 ${\vec{\mu }}_i$ 中添加 μ^​w​，其中 $w$ 是该门的输出电线。
   • 如果这是一个 AND 门，则向 ${\vec{\mu }}_0$ 中添加 μ^​i1​​+μ^​i2​​+μ^​o​，其中 $i_1,i_2$ 是输入电线，$o$ 是输出电线。
   • 如果这是一个 OR 门，则向 ${\vec{\mu }}_0$ 中添加 μ^​i1​​+μ^​o​,μ^​i2​​+μ^​o​，其中 $i_1,i_2$ 是输入电线，$o$ 是输出电线。
4. 输出 (μ​0​,…,μ​n​)。

$\mathsf{R}\mathsf{e}\mathsf{c}\mathsf{o}\mathsf{n}\mathsf{s}\mathsf{t}\mathsf{r}\mathsf{u}\mathsf{c}\mathsf{t}$ 相当于是解方程。可以证明如果 f(x)=0，则 ${\vec{\mu }}_i$ 中拿出的部分的分布不随着秘密 $\mu$ 变化。

↩↩[Example] 这里举一个例子：允许还原秘密当且仅当 $x_1,x_2,x_3$ 中至少有两个是 1。例子里公式的写法是 $$f(x_1,x_2,x_3)=((x_1\vee x_2)\wedge x_3)\vee (x_1\wedge x_2).$$ 图中电线旁边的数是赋予电线的值，非输入门旁边的数是该门对 ${\vec{\mu }}_0$ 的贡献。$\mathsf{S}\mathsf{h}\mathsf{a}\mathsf{r}\mathsf{e}$ 的输出是： $$\begin{array}{rl}{\vec{\mu }}_0=& ({\hat{\mu }}_3+{\hat{\mu }}_1,{\hat{\mu }}_3+{\hat{\mu }}_2,\\ & {\hat{\mu }}_3+{\hat{\mu }}_4+{\hat{\mu }}_7,\\ & {\hat{\mu }}_5+{\hat{\mu }}_6+{\hat{\mu }}_8,\\ & {\hat{\mu }}_7+\mu ,{\hat{\mu }}_8+\mu ),\\ {\vec{\mu }}_1=& ({\hat{\mu }}_1,{\hat{\mu }}_5),\\ {\vec{\mu }}_2=& ({\hat{\mu }}_2,{\hat{\mu }}_6),\\ {\vec{\mu }}_3=& ({\hat{\mu }}_4).\end{array}$$

[KW19] 的 ABE 构造（的变体）

我们假设已经有一个 IND-CPA 私钥加密方案 SKE=(SKE.Gen,SKE.Enc,SKE.Dec)，并用 $(\mathsf{S}\mathsf{h}\mathsf{a}\mathsf{r}\mathsf{e},\mathsf{R}\mathsf{e}\mathsf{c}\mathsf{o}\mathsf{n}\mathsf{s}\mathsf{t}\mathsf{r}\mathsf{u}\mathsf{c}\mathsf{t})$ 指代前述秘密分发方案，那么 ABE 的构造是这样的：

• ABE.Setup：
  1. 采样 μ←Zp​；
  2. 执行 $n+1$ 次 SKE.Gen→ski​ (i=0,…,n)；
  3. 输出 $\mathsf{m}\mathsf{s}\mathsf{k}\leftarrow (\mu ,{\mathsf{s}\mathsf{k}}_0,\dots ,{\mathsf{s}\mathsf{k}}_n)$ 作为 ABE 方案的万能密钥。
• ABE.KeyGen(msk,f)：
  1. 执行 (μ​0​,…,μ​n​)←Share(μ,f)；
  2. 执行 ctSKE,f,i​←SKE.Enc(ski​,μ​i​) (i=0,…,n)；
  3. 输出 skf​←(ctSKE,f,i​)i=0,…,n​。
• ABE.Enc(msk,x,m)：输出 ctx,m​←(m+μ,sk0​,(ski​)xi​=1​)。
• ABE.Dec(skf​,f,ctx,m​,x)：
  1. 若 $f(x)=0$ 则放弃；否则
  2. 执行 μ​i​←SKE.Dec(ski​,ctSKE,f,i​)；
  3. 执行 μ←Reconstruct(f,x,μ​0​,(μ​i​)xi​=1​)；
  4. 输出 m←(m+μ)−μ。

正确性显而易见，关键是证明适应性单次安全性。

证明初探

直觉上来说，如果 xi​=0，那么使坏者就没有能解密 ${\vec{\mu }}_i$ 的 SKE 密钥，于是对于使坏者来说 ${\vec{\mu }}_i$ 应该是被隐藏的。如果这种隐藏是信息论意义上的，那么我们可以直接通过秘密分发的安全性得出：对于使坏者，$\mu$ 是一个均匀随机数，这样明文 $m$ 就相当于被 one-time pad 保护。

然而事与愿违，这种隐藏只是计算意义上的，所以这个论证不能成功。那我们先考虑一个弱化版本的安全性——选择性安全——这种安全性要求使坏者一次决定密钥和密文查询（而不能看到密钥之后再决定密文查询的内容，或者看到密文之后再决定密钥查询的内容）。回应查询的时候我们已经知道哪些 ${\vec{\mu }}_i$ 不会被解密，于是我们可以把这些 ${\overrightarrow{\mathsf{c}\mathsf{t}}}_{\mathsf{S}\mathsf{K}\mathsf{E},f,i}$ 从 ${\vec{\mu }}_i$ 的密文替换成一个随机等长向量的密文。根据 SKE 在选择明文攻击下的不可区分性，该变化不会被使坏者察觉。一旦做出这样的变化，我们就又可以通过秘密分发的安全性得出结论了。

不熟悉密码学证明策略（归约）的读者可能会疑惑为什么同样的论证不适用于适应性安全性，原因是当我们回应密钥查询的时候，我们不知道哪些 ${\vec{\mu }}_i$ 不能被解密，如果我们不幸伪造了一个将会被使坏者解密的 ctSKE,f,i​，那么使坏者就会注意到该变化。

现在回到适应性安全的证明上，观察之前的例子 [Example]，我们发现 ABE 密钥里面和 $\mu$ 有关的部分只有输出门产生的贡献。如果我们能把它修改成和 $\mu$ 无关的量，则又可以论证 $\mu$ 是一个 one-time pad 了。这似乎和选择性安全的证明不太一样，但实际上是一样的——当我们把不能解密的 ${\overrightarrow{\mathsf{c}\mathsf{t}}}_{\mathsf{S}\mathsf{K}\mathsf{E},f,i}$ 换掉后，剩下的 ${\vec{\mu }}_i$ 就和 $\mu$ 独立了（虽然写起来还包含 μ）。

回过头来，抹去 ${\overrightarrow{\mathsf{c}\mathsf{t}}}_{\mathsf{S}\mathsf{K}\mathsf{E},f,i}$ 蕴含的 ${\vec{\mu }}_i$ 的难点在于我们不知道整个属性向量 x∈{0,1}n，这是因为 $x$ 的长度实在是太长了。但是我们或许可以猜一猜 $x_1$ 是不是 0，如果是 0，则可以抹去 μ​1​；如果我们一开始瞎猜，那么正确率是 50%，接下来的实验中，如果我们发现之前猜错了，就放弃整个实验（输出 0），可以证明这样操作将会把优势降低一半。如果我们能证明降低优势之后的优势仍然可忽略，那么原先的优势就是可忽略函数的两倍，从而也是可忽略的。问题是这样的猜测不可持续——如果我们继续猜每一位，最终会产生 $2^{-n}$ 的优势损失——于是为了补偿原来的优势就需要乘 2n，这样无法证明原先的优势是可忽略函数。

实际上，猜测法（专业名字叫 complexity leveraging）是证明适应性安全的重要技巧之一，但是我们承受不起一下子猜长度为 $\Omega (n)$ 的字符串，不过我们可以猜长度为 $\mathcal{O}(\log n)$ 的字符串，这只会产生多项式倒数的优势损失。并且我们不能串联猜很多次（这相当于一次猜出所有的），但我们可以“并联”地猜，这就是后文要用到的分段猜测法。

通过分段猜测法可以把证明从适应性变成选择性，但是不能一次猜测太多，那么每次猜多少内容合适呢？我们从真实的加密出发来看一看。如果我们知道一个输入门的输入是 0，那么这个输入们对 ${\vec{\mu }}_i$ 贡献的那一项就可以被抹去（注意我们只尝试抹去这一项），在之前的例子 [Example] 里，假设我们知道最左边的门的输入是 0，那么我们就可以把送去用 SKE 加密的 ${\vec{\mu }}_i$ 改成 $${\vec{\mu }}_0=\cdots ,{\vec{\mu }}_2=\cdots ,{\vec{\mu }}_3=\cdots ,{\vec{\mu }}_1=(\star ,{\hat{\mu }}_5).$$ 做出这个改变后，我们换一种方式来画这个电路。注意最左边的门和它的输出电线被分开了，我用这个画法表示最左边的门对 ${\vec{\mu }}_1$ 的贡献和那根线上的数值是独立的。这样的画法下，门和电线相连当且仅当门对 ${\vec{\mu }}_i$ 的贡献和电线上的 ${\hat{\mu }}_{?}$ 有关系。

接下来想象我们猜测左起第二个门的输入也是 0，那么我们同样可以切断那个门和它的输出线的连接——也就是把门的贡献替换为一个独立的随机数。做了这两个改变之后，我们可以发现它们的父节点对 ${\vec{\mu }}_0$ 的贡献实际上是两个和 ${\hat{\mu }}_3$ 独立的随机数，我们改变采样策略，让它不再从 ${\hat{\mu }}_3$ 计算，这就相当于切断了该节点和它的所有线（包括输入线和输出线）之间的连接。这三个改变之后，电路变成了下图的样子。

此时，我们的 ${\vec{\mu }}_i$ 已经变成了 $$\begin{array}{rl}{\vec{\mu }}_0=& (\star ,\star ,{\hat{\mu }}_3+{\hat{\mu }}_4+{\hat{\mu }}_7,\dots ),\\ {\vec{\mu }}_1=& (\star ,{\hat{\mu }}_5),{\vec{\mu }}_2=(\star ,{\hat{\mu }}_6),{\vec{\mu }}_3=({\hat{\mu }}_4).\end{array}$$ 到了这一步，我们可以选择把左起第一、第二个输入门的输出线和它们接回去，因为 ${\hat{\mu }}_1,{\hat{\mu }}_2$ 根本没有被用到，也是独立于其他输出的随机数。如果我们能一步步把电路的状态变成“输出门和额外加的那根线之间的连接被切断”的状态，那么就保证了 ${\vec{\mu }}_i$ 里面不含秘密 $\mu$（只有输出门的贡献直接用到了这个秘密），从而可以用 one-time pad 的论证。

我们可以通过猜一个和这个“剪电线”状态有关的字符串来完成证明，这就是后文要用的 ${\mathsf{N}\mathsf{C}}^1$ 摆石子策略。

分段猜测法（piecewise guessing framework）

可以把过渡证明法（hybrid argument）和猜测法结合：

• 设置多项式个过渡的适应性博弈；
• 相邻博弈之间可以通过猜测一个长度为 $\mathcal{O}(\log \lambda )$ 的字符串“把适应性选择（adaptive choice）给猜出来”；
• 一旦猜出适应性选择，可以证明相邻博弈（这时就相当于选择性博弈而不是适应性博弈了）之间是不可区分的。

这样就可以通过猜测法证明相邻博弈之间本来就不可区分，进而通过过渡证明法得出两端的博弈不可区分。形式化来说，考虑 $m+1$ 个过渡博弈 $H_0,\dots ,H_m$ 和函数 ℓ，如果博弈 $H_i$ 可以通过预先承诺一个长度为 $\ell$ 的字符串 $s$ 变为选择性（该字符串是本来是适应性的选择的一个函数，承诺该字符串表示之后的适应性选择的函数必须等于该字符串），且区分相邻的选择化后的博弈 $H_i^{s_i}$ 和 $H_{i+1}^{s_{i+1}}$ 优势上界为 ε，则区分 $H_0$ 和 $H_m$ 优势的一个上界是 22ℓmε；特别地，当 $m={\lambda }^{\mathcal{O}(1)},\ell =\mathcal{O}(\log \lambda ),\epsilon ={\lambda }^{-\omega (1)}$ 时，$H_0$ 和 $H_m$ 不可区分。

${\mathsf{N}\mathsf{C}}^1$ 摆石子策略（pebbling strategy）

回顾之前的“剪电线”操作，它的专业名字叫做 pebble game（常见翻译是“卵石博弈”）。公式电路中每个门某一时刻处于有石子（pebbled）或无石子（unpebbled）的状态。有石子状态就是一个门和它的所有电线之间的连接都被切断的状态，也就是一个门对 ${\vec{\mu }}_i$ 的贡献和 ${\hat{\mu }}_{?}$ 完全没关系的状态。

起初，所有的门都没有石子，我们希望经过一系列操作之后只有输出门有石子，每个操作就是向某个门上放置石子或者拿走某个门上的石子。当然，放置和拿走的规则必须和我们想要做的证明相适应——什么时候才能把门对 ${\vec{\mu }}_i$ 的贡献从 ${\hat{\mu }}_{?}$ 的计算改成独立随机数（或者反过来）？只有当改变前后的计算结果本身都是独立随机数时才行，一个充分条件就是切断前（或连接后）该门对 ${\vec{\mu }}_i$ 每个贡献都有一个只出现了一次的 ${\hat{\mu }}_{?}$ 时候。从之前的尝试可以看出，非叶子节点的门只有当它的子节点和子节点输出线（也就是那个节点的输入线）的连接切断时才有这样的性质。于是可以定义如下摆石子规则：

• 如果一个输入门是 0，则任何时候都可以放置或者拿走石子。（原因是该门对于 ${\vec{\mu }}_i$ 的贡献根本不会被选择出来，注意这里和 ABE 里发生的事情还不太一样，稍后解释。）
• 如果一个门是 AND 门，那么当它的某个子节点有石子时，可以放置或拿走石子。
• 如果一个门是 OR 门，那么当它的两个子节点都有石子时，可以放置或拿走石子。
• 其他情况下既不能放置也不能拿走石子。

继续之前，有一个值得思考的问题：为什么要拿走石子？整个电路都摆上石子不是更好吗？我们马上就能看到原因。

对于任意一个合法的摆石子策略（放置、拿走石子的指令序列），我们可以考虑执行它若干步之后每个门上是否有石子，这叫做石子配置（pebbling configuration）。这有什么用？注意到摆石子规则不但和公式电路的结构有关，也和具体的输入有关（只有对应位是 0 的时候才可能在一个输入门上摆石子），因此对任意 $t$ 和任意根据电路和输入产生摆石子策略的算法，策略进行 $t$ 步之后的石子配置是适应性选择的一个函数。我们将要分段猜测的东西就是石子配置——每个过渡博弈代表进行摆石子策略若干步，$H_0$ 进行 0 步（也就是正常的单次安全性博弈），而 $H_m$ 进行 $m$ 步。要让证明成功，我们需要三个条件：

• 摆石子策略不能太长，这对应于 $m$ 的大小，因此必须是多项式步；
• 石子配置不能太复杂，这对应于 $\ell$ 的大小，必须能用对数长度的字符串高效描述；
• 在合法的摆石子策略下，能够证明 $H_i^{s_i}$ 和 $H_{i+1}^{s_{i+1}}$ 不可区分，其中 $s_i,s_{i+1}$ 是（猜对的）执行前 $i,i+1$ 步摆石子策略后的石子配置。

幸运的是，这样的摆石子策略是存在的。用 ${\mathsf{P}\mathsf{E}\mathsf{B}\mathsf{B}\mathsf{L}\mathsf{E}}_g,{\mathsf{U}\mathsf{N}\mathsf{P}\mathsf{E}\mathsf{B}\mathsf{B}\mathsf{L}\mathsf{E}}_g$ 表示放置、拿走 $g$ 上的石子，[KW19] 构造了两个函数用来计算一个公式电路在一个输入下的摆石子策略：

• $\mathsf{R}\mathsf{e}\mathsf{v}\mathsf{e}\mathsf{r}\mathsf{t}(S)$ 输入一个摆石子策略 $S$ 并输出它的反向操作（把 ${\mathsf{P}\mathsf{E}\mathsf{B}\mathsf{B}\mathsf{L}\mathsf{E}}_g$ 替换成 UNPEBBLEg​，把 ${\mathsf{U}\mathsf{N}\mathsf{P}\mathsf{E}\mathsf{B}\mathsf{B}\mathsf{L}\mathsf{E}}_g$ 替换成 PEBBLEg​，并倒序）。
• $\mathsf{P}\mathsf{e}\mathsf{b}\mathsf{b}\mathsf{l}\mathsf{e}(g,x)$ 输入一个逻辑门 $g$ 和属性 x，假设 $g$ 的输出值是 0，它输出一个摆石子策略，使得最终状态是有且只有 $g$ 上有石子。这个过程是递归的：
  • 如果 $g$ 是输入门（叶子节点），则输出 PEBBLEg​。
  • 如果 $g$ 是 OR 门，其左右子节点是 g1​,g2​，则输出 $\mathsf{P}\mathsf{e}\mathsf{b}\mathsf{b}\mathsf{l}\mathsf{e}(g_1,x),\mathsf{P}\mathsf{e}\mathsf{b}\mathsf{b}\mathsf{l}\mathsf{e}(g_2,x),{\mathsf{P}\mathsf{E}\mathsf{B}\mathsf{B}\mathsf{L}\mathsf{E}}_g,\mathsf{R}\mathsf{e}\mathsf{v}\mathsf{e}\mathsf{r}\mathsf{t}(\mathsf{P}\mathsf{e}\mathsf{b}\mathsf{b}\mathsf{l}\mathsf{e}(g_2,x)),\mathsf{R}\mathsf{e}\mathsf{v}\mathsf{e}\mathsf{r}\mathsf{t}(\mathsf{P}\mathsf{e}\mathsf{b}\mathsf{b}\mathsf{l}\mathsf{e}(g_1,x))$ 的串接。
  • 如果 $g$ 是 AND 门，其左右子节点是 g1​,g2​，令 $i\in \{1,2\}$ 较小的使得 $g_i(x)=0$ 成立者，输出 $\mathsf{P}\mathsf{e}\mathsf{b}\mathsf{b}\mathsf{l}\mathsf{e}(g_i,x),{\mathsf{P}\mathsf{E}\mathsf{B}\mathsf{B}\mathsf{L}\mathsf{E}}_g,\mathsf{R}\mathsf{e}\mathsf{v}\mathsf{e}\mathsf{r}\mathsf{t}(\mathsf{P}\mathsf{e}\mathsf{b}\mathsf{b}\mathsf{l}\mathsf{e}(g_i,x))$ 的串接。

容易证明策略的长度不超过 5d，其中 $d$ 是公式的深度（对数级别）。此外，该策略下的石子配置有一个非常好的性质：对于任意一个门，如果右子树里有石子，则左子树只有两种情况——完全没有石子或者只有左子节点（左子树的根）上有石子。

用上述性质可以作出一个非常高效的石子配置编码，长度是 2d+1：

• 用 $d$ 组 2 位二进制数描述一条从根到叶子的路径，每一步根据右子树和左子节点（注意一个是子树一个是节点）的石子配置，做如下记录并选择走法：
  • 如果右子树里没有石子且左子节点上没有石子，记录 00 并向左走；
  • 如果右子树里没有石子且左子节点上有石子，记录 01 并向左走；
  • 如果右子树里有石子且左子节点上没有石子，记录 10 并向右走；
  • 如果右子树里有石子且左子节点上有石子，记录 11 并向右走。
• 最后用一位描述输出门（根节点）上是否有石子。

现在我们可以回答为什么需要拿走石子了——如果不拿走石子，我们不知道怎样的摆石子策略允许我们用对数长度的字符串编码石子配置。在 [KW19] 策略下，虽然摆石子策略和属性向量 $x$ 有关，但它在所有的 $x$ 下能产生的石子配置总共也只有不超过 $2^{2d+1}$ 种。

证明思路

设策略公式的最大深度是 d=O(logλ)，定义过渡博弈 H0​,…,Hm=5d​，在 $H_i$ 中如此应答密钥询问：

1. 执行 (μ​0​,…,μ​n​)←Share(μ,f)；
2. 执行 $\mathsf{P}\mathsf{e}\mathsf{b}\mathsf{b}\mathsf{l}\mathsf{e}(f,x)$ 的前 $i$ 步（策略步数不足 $i$ 步则停在最后一步），把所有有石子的门对 ${\vec{\mu }}_i$ 贡献的项都替换成独立随机数，替换后的向量仍然记作 μ​i​；
3. 执行 ctSKE,f,i​←SKE.Enc(ski​,μ​i​) (i=0,…,n)；
4. 回答 skf​←(ctSKE,f,i​)i=0,…,n​。

应答密文询问时，总是加密 m0​。设置 ℓ=2d+1，长度为 $\ell$ 的承诺字符串解析为石子配置，如果实际发生的石子配置和猜测不符则放弃。现在我们证明相邻选择版本博弈的不可区分性，根据相邻博弈中多执行的一步策略分类讨论：

• 如果没有执行任何策略（因为下标超过了策略的步数），则相邻的这两个博弈是完全一样的；
• 如果执行的是在输入门上放置或拿走石子，则相邻不可区分性是 SKE 的 IND-CPA 性质的推论——相邻博弈中的变化在于被 SKE 加密的明文是电线的数值还是一个随机数，但该加密是在一个不能被解密的 SKE 实例上进行的（注意，只有输入为 0 的输入门才能放置或拿走石子）；
• 如果执行的是在非输入门上放置或拿走石子，则根据摆石子策略的合法性，相邻的博弈是完全一样的（只是换了一个采样 ${\vec{\mu }}_0$ 的方式，这种改变是概念性、观点性的，而不是实质性的）。

由分段猜测法可知 $H_0$ 和 $H_m$ 不可区分。注意 $H_0$ 是私钥 ABE 单次安全性中的 G0​，而 $G_m$ 中的 ABE 私钥和 $\mu$ 没关系，而密文里的 $m_0+\mu$ 是一个独立随机数。

仿照 $H_i$ 定义 Ki​，但在应答密文询问时加密 m1​。同理可证任何多项式时间使坏者区分 $K_0$ 和 $K_m$ 的优势可忽略。注意到 $H_m$ 和 $K_m$ 是同一个博弈，再利用传递性知道区分 $H_0$ 和 $K_0$ 的优势也可忽略，也就是我们需要的单次安全性。

参考文献