密码累加器用于高效地证明元素是否存在于集合中，定义：

集合 $X = \{x_1, …,x_n\}$
集合的累加值 $acc_X$
集合中的元素 $x_i$，对应一个证明 $w_i$

通过证据 $w_i$，可以证明元素 $x_i$ 存在于集合 $X$

累加器的三个性质：正确性、健壮性、不可区分性

正确性：对于所有诚实生成的密钥、所有诚实计算的累加值和证据，验证算法始终返回 1

健壮性：指无碰撞性，对于元素 $y\notin X$，很难找到其成员证明，而对于元素 $x_i \in X$，也很难找到其非成员证明

不可区分性：累加器和持有证明的用户都不会泄露有关累加集合 $X$ 的信息

发展历程

1993年首次被提出，其最初的构造为静态累加器，集合固定不变
2002年提出了动态累加器的概念，可以支持动态添加、删除元素
2007年，通用累加器被提出，可以姐姐成员证明和非成员证明

非通用累加器智能支持元素的成员证明，即证明 $x_i \in X$，无法提供 $y\notin X$ 的证明 $w_y$

模型

一个密码累加器中有三个主体：

累加器管理员：生成密钥对，创建并发布累加器
用户：接收累加器管理员提供的证证明，这个证明是它们在累加器系统中的凭证，可以提供给验证方进行验证
验证方：通过证明 $w$ 和 $acc_X$，验证某个元素在累加器中

静态累加器

静态累加器可以描述为四元组 $\Pi=(Gen, Eval, WitCreate, Ver)$，静态累加器不能动态地添加元素

$Gen(1^\lambda, t) \Rightarrow (sk_{acc}, pk_{acc})$：管理员输入安全参数$\lambda$，累加上限$t$，输出密钥对$(sk_{acc},pk_acc)$，如果没有陷门，陷门信息$sk_{acc} = \varphi$

$Eval((sk_{acc}, pk_{acc}),X) \Rightarrow acc_X$：管理员计算累加值和辅助信息，输入集合、密钥对，输出一个累加值。并且，公布给用户和验证方，输出辅助信息$aux$发送给用户，用户通过辅助信息更新本地证明

$WitCreate((sk_{acc},pk_{acc}), x_i, acc_X, aux) \Rightarrow w_i$：创建用户 $x_i$ 的证明，输入密钥对、累加值、元素 $x_i$ 和辅助信息 $aux$，生成证据 $w_i$

$Ver(pk_{acc}, x_i, w_i,acc_X) \Rightarrow \{0/1\}$：验证方验证元素 $x_i$ 是否在累加器中，如果 $w_i$ 是 $x_i$ 的证据，返回1，否则返回0

动态累加器

为了可以支持动态地更新集合 $X$，并且可以有效地更新集合中的证明对静态累加器进行扩展，可以得到动态累加器

动态累加器在静态累加器的基础上添加了一个三元组 $\Pi=(Add, Del, MemWitUp)$

$Add((sk_{acc},pk_{acc}),acc_X,aux,x) \Rightarrow (acc_{X’},aux’)$：累加器管理员添加元素 $x\notin X$ 到累加器中，并且更新累加值 $acc_x$，这个过程和 $WitCreate$ 较类似，它输出的是 $x$ 加入后的累加值$acc_{X’}$，并且更新辅助信息 $aux$

$Del((sk_{acc},pk_{acc}),acc_x,x,aux)\Rightarrow(acc_{X’},aux’x)$：与上一个元素类似，输入需要删除的元素 $x$ 和辅助信息，然后输出新的累加值，更新辅助信息

$MemWitUp((sk_{acc},pk_{acc}), x, w_i, aux) \Rightarrow w_{i’}$：在添加或删除元素后，用户更新元素 $x_i$ 的证明 $w_i$，它输出$x_i$更新后的证明$w_i’$

通用累加器

通用累加器在前面 $WitCreate$ 组件中，添加一个布尔参数 $type$，创建成员证明时 $type=0$，创建非成员证明时 $type=1$。通用累加器可以根据是否可以添加元素进行分类，如果不可动态添加元素称为通用静态累加器，如果可以动态添加元素则称为通用动态累加器

如果是通用动态累加器，则需要在前面两个累加器的基础上添加 $NonMemWitUp$ 组件，在累加器集合更新时，对非成员证明更新

$NonMemWitUp((sk_{acc},pk_{acc}),x,w,aux) \Rightarrow u’$：在添加或删除元素 $x$ 时,用户更新非成员元素 $y \notin X$ 的证据$u$ 为 $u’$

基于 RSA 的累加器

静态累加器

最开始在1993年被提出的静态累加器就是基于 RSA 实现的，其具体构造方案如下

$Gen(1^\lambda, t) \Rightarrow ((p, q), N)$：输入安全参数，生成累加器的初始值 $g\in Z_n$，输出密钥对，私钥是 RSA 加密中的两个大素数，$N = pq$

$Eval(pk_{acc}, X) \Rightarrow acc_X$：管理员计算累加值，$acc_X=g^{x_1…x_n}\ mod\ N$，其中$X = \{x_1,…,x_n\}$

$WitCreate(pk_{acc},x,acc_X) \Rightarrow w_i$：生成用户的证明 $w_i=g^{x_1…x_{i-1}x_{i+1}…x_n}\ mod\ N$

$VerMem(pk_{acc},x_i,w,acc_X) \Rightarrow \{0/1\}$：验证方判断等式$acc_X=w_i^{x_i} \ mod\ N$ 是否成立来验证元素是否在累加器中

动态累加器

动态累加器利用了 RSA 的陷门来更新累加器，利用陷门信息 $sk_{acc}$ 进行求逆运算，删除信息时需要利用陷门信息更新累加值，更新成员证明时不需要陷门信息

$Gen(1^\lambda, t) \Rightarrow ((p,q),N)$：和静态累加器一样，生成密钥对

$Add(acc_X,x,X,pk_{acc}) \Rightarrow acc_X$：添加元素 $x$ 后，更新累加值
$$
acc_{X’}=acc_{X \cup\{x\}}=acc_X^x \ mod\ N
$$
$Del(acc_X,x,X,(sk_{acc},pk_{acc}))$：删除元素 $x$ 后更新累加值，删除元素后更新累加值为
$$
acc_{X’}=acc_{X \textbackslash \{x\}}=acc_{X}^{x^{-1} \ mod\ \varphi(N)} \ mod \ N
$$
其中，$\varphi$ 是欧拉函数

$VerMem(acc_X,x,w_i,pk_{acc})$：验证方通过等式 $acc_X =w_i^{x_i}\ mod\ N$ 来判断元素是否在集合中

$MemWitUp(x,w_i,x_i,pk_{acc},acc_X,acc_{X’})$：用户更新元素 $x_i$ 的证明。

添加元素 $x\notin X$ 到累加器时，用户更新证明 $w_i’ = w_i^x \ mod\ N$。

删除元素 $x \neq x_i \in X$ 时，通过扩展欧几里得算法求出 $a,b\in Z$ 使得 $ax_i + bx = 1$，然后从 $x_i$ 的旧证明计算新证明
$$
w_i’ = w_i^bacc_{X’}^a
$$