累加器的构造

1. One-way accumulator

2. Broadcast Encryption

先看一个 Broadcast Encryption 的构造¹，这个构造也是由 Boneh 提出来的，而且是基于双线性映射。

Note

$Setup(n)\rightarrow (d_1,...,d_n,PK)$ ，其中 $d_1,...,d_n$ 为私钥， $PK$ 为公钥；
$Encrypt(S,PK)\rightarrow (Hdr,K)$ ，其中 $S\subseteq \{1,...,n\}$ ， $Hdr$ 一般称作 header ， $K\in\mathcal{K}$ ，是一个消息加密密钥（message encryption key），广播的内容为 $(S,Hdr,C_M)$ ， $C_M$ 就是消息 $M$ 的密文，一般 $(S,Hdr)$ 是 full header ， $C_M$ 是 body；
$Decrypt(S,i,d_i,Hdr,PK)\rightarrow K$ ，如果用户 $i$ 是在 $S$ 中，则使用 $i$ 的私钥 $d_i$ 可以生成密钥 $K$ ，然后使用 $K$ 解密。

2-1. 一个特殊的例子

$Setup(n)\rightarrow (d_1,...,d_n,PK)$ ：

先随机选取 $g\in\mathbb{G}, \alpha\in\mathbb{Z}_p$ ，计算 $g_i=g^{\alpha^i}\in\mathbb{G}$ for $i=1,2,...,n,n+2,...,2n$ ；
随机选取 $\gamma\in\mathbb{Z}_p$ ，令 $v=g^\gamma\in\mathbb{G}$ ，那么公钥为 $PK=(g,g_1,...,g_n,g_{n+2},...,g_{2n},v)\in\mathbb{G}^{2n+1}$ ，私钥为 $d_i=g_i^\gamma\in\mathbb{G}$ 。

$Encrypt(S,PK)\rightarrow (Hdr,K)$ ：

先随机选取 $t\in\mathbb{Z}_p$ ，令 $K=e(g_{n+1},g)^t\in\mathbb{G}_1$ ；
令 $Hdr=(g^t,(v\cdot \prod_{j\in S}g_{n+1-j})^t)\in\mathbb{G}_2$ ，输出 $(Hdr,K)$

$Decrypt(S,i,d_i,Hdr,PK)\rightarrow K$ ：

对于 $Hdr=(C_0,C_1)$ ，有： $k=e(g_i,C_1)/e(d_i\cdot \prod_{j\in S,j\neq i}g_{n+1-j+i},C_0)$

3. CKS09

CKS09 是一个基于双线性对上的累加器方案²，核心思想基于 第二节 中的加密方案，即

在给定随机的 $\alpha\in \mathbb{Z}_q$ ，我们记 $g_i$ 为 $g^{\alpha^i}$ ，如 $g_1=g^{\alpha}$ 。那么，我们恒有： $$ e(g_{n+1},g)=e(g_{n},g_1) $$

假设 $V\subset\{1,2,...,n\}$ ，那么：

$\frac{e(g_{i},\prod_{j\in V}g_{n+1-j})}{e(g,\prod_{j\in V,j\neq i}g_{n+1-j+i})}=e(g,g_{n+1})$

这样的话，问题就变得简单了，对于首先，我们将 $\alpha$ 作为 主密钥，令

$z=e(g_{n+1},g)$

针对一个列表 $V$ ，我们用 $acc_V$ 代表 $V$ 的累加值，即 $$ acc_V=\prod_{j\in V}g_{n+1-j} $$

对于列表中的某个 $i\in V$ ，相对应的 $wit_i$ 为：

$wit_i=\prod_{j\in V,j\neq i}g_{n+1-j+i}$

那么，下面等式将会始终成立：

$\frac{e(g_i,acc_V)}{e(g,wit_i)}=z$

因此，必须找个方式公开 $g_i$ 。

这里使用了 $state_U$ 来记录当前的状态，注意， $state_U$ 只有在拥有私钥 $\alpha$ 的情况下才可以进行更新，其形式为：

$state_U=\{U,g_1,g_2,...,g_n,g_{n+2},...,g_{2n}\}$

$U$ 指的就是 当前状态下 所有的用户索引，那么有 $V\subseteq U$

假设现在我们需要添加索引为 $\ell$ 的用户，那么 $$ acc_{V\cup {\ell}}=acc_V \cdot g_{n+1-\ell} $$ $$ state_{U\cup{\ell}}=\{U\cup{\ell},g_1,g_2,...,g_n,g_{n+2},...,g_{2n}\} $$

D. Boneh, C. Gentry, and B. Waters, “Collusion resistant broadcast encryption with short ciphertexts and private keys,” in Annual International Cryptology Conference, 2005, pp. 258–275. ↩
J. Camenisch, M. Kohlweiss, and C. Soriente, “An accumulator based on bilinear maps and efficient revocation for anonymous credentials,” in International Workshop on Public Key Cryptography, 2009, pp. 481–500. ↩