# Cryptographic Accumulator and Its Application: A Survey

Authors: Yongjun Ren; Xinyu Liu; Qiang Wu; Ling Wang; Weijian Zhang
Journal: Security and Communication Networks
 (2022)

---

## Abstract

Since the concept of cryptographic accumulators was first proposed in 1993, it has received continuous attention from researchers. The application of the cryptographic accumulator is also more extensive. This paper makes a systematic summary of the cryptographic accumulator. Firstly, descriptions and characteristics of cryptographic accumulators are given, and the one-way accumulator, collision-free accumulator, dynamic accumulator, and universal accumulator are introduced, respectively. Cryptographic accumulator can be divided into two types: symmetric accumulator and asymmetric accumulator. In the asymmetric accumulator, three different cryptographic accumulator schemes were classified based on three security assumptions. Finally, this paper summarized the applications of cryptographic accumulators in ring signature, group signature, encrypted data search, anonymous credentials, and cryptographic promise.


---

## Body

## 1. Introduction

The concept of cryptographic accumulators was first proposed in 1993 by Benaloh and de Mare [1], who developed a one-way accumulator encryption protocol that could be used for timestamp and membership testing through a hash function with quasi-commutativeness and one-way property. That is to say, for all x∈X and y1,y2∈Y, this one-way hash function h:X×Y⟶X satisfies the quasi-commutativeness:(1)hhx,y1,y2=hhx,y2,y1.The cryptographic accumulator scheme allows the accumulation of elements from a finite setX=x1,…,xn into a concise value accX of constant size, known as a cryptographic accumulator. Because the cryptographic accumulator satisfies the characteristic of quasi-commutativeness, the accumulated value accX does not depend on the order of the accumulated elements. Choose g∈G as the base, and the original cryptographic accumulator is defined as(2)accX=hhh…hhhg,x1,x2,x3,…,xn−2,xn−1,xn.The witnesswitxi of each element xi∈X in the set is calculated to verify hwitxi,xi=accX, that is, to effectively prove the membership of element xi.At the same time, it is not feasible to find a membership witness for any unaccumulated elementy∉X because of the collision resistance of one-way hash function.The cryptographic accumulator has several important characteristics, such as being dynamic, robustness, universality, security assumption, and compactness, as shown in Table1.Table 1
Characteristics of the cryptographic accumulator.
CharacteristicsDynamic [2]The cryptographic accumulator has efficient algorithms for adding, deleting, witnessing, and updating elements.Robustness [1]The administrator of the cryptographic accumulator does not need to be trusted, and trapdoor information cannot be used to forge witnesses.Universality [3]The cryptographic accumulator can provide not only membership proof but also nonmembership proof.Security assumption [4]Under the premise of security assumption declaration, the member verification function of the cryptographic accumulator is not affected by attackers.Compactness [5]The cryptographic accumulator can map a large set to accumulation value of a smaller order of magnitude, which is manifested by the small storage space required for accumulated value and witness, as well as the low time complexity of updating algorithm.Although cryptographic accumulators have been roughly described in the review of cryptographic accumulators published by Ozcelik et al. [6], the summary of this paper is not comprehensive. Therefore, this paper makes a more comprehensive and detailed summary.The roadmap of this paper is organized as follows: Section2 introduces the descriptions of cryptographic accumulator. Section 3 classifies the cryptographic accumulators into symmetric accumulator and asymmetric accumulator. In Section 4, cryptographic accumulators based on various security assumptions are introduced in detail. Section 5 describes the cryptographic accumulator scheme of hidden order group and known order group. In Section 6, the applications of cryptographic accumulator are introduced. The seventh section gives a summary.


## 2. Descriptions of Cryptographic Accumulators

### 2.1. One-Way Accumulators

The concept of the cryptographic accumulator originated from the one-way accumulator first proposed by Benaloh and Mare [1]. A one-way accumulator is defined as a set of one-way hash functions with quasi-commutativeness.One-Way Hash Functions [1, 7]. A family of one-way hash functions is an infinite sequence of families of functions Hλλ∈N, where Hλ=hk:Xk×Yk⟶Zk (k is a security parameter), with the following properties:(1)
For any integerλ and any hk∈Hλ,hk.,. is computable in time polynomial in λ.(2)
Any probabilistic, polynomial-time algorithm A satisfies(3)PrhkH⟵Rλ;xX⟵Rk;y,Y⟵Rk;x,⟵A1λ,x,y,y,:hkx,y=hkx,,y,<neglλ,where the probability depends on the random selection ofhk, x, y, y′ and random output of A.From the above description, it is seen that the one-way hash function is computable and one-way; that is, givenx and y, the calculation of z=hx,y can be completed in polynomial time, and if given x, y, and y′, the probability of finding x′ satisfying hkx,y=hkx′,y′ is too small to be ignored; that is, the conflict between the outputs generated by different inputs is very little.Quasi-Commutativeness [7, 8]. A function f: X×Y⟶X has quasi-commutativeness means that the following equation holds:(4)∀x∈X,∀y1,y2∈Y:ffx,y1,y2=ffx,y2,y1.If a one-way hash function satisfies the quasi-commutativeness, first of all, the forward calculation is easy according to the one-way property, while the reverse calculation is difficult. Second, satisfying the quasi-commutativeness means that, under the condition of given initial value (Seeds), the results of multiple hash operations will not change with different calculation order.A one-way hash function with quasi-commutativeness can be used to verify whether a valueyi is in a specified set Y=yi. Specifically, the accumulative results z of Y can be calculated by the one-way accumulative function h∈H, using the following formula:(5)z=hh…hhhx0,y1,y2,y3,…,yl−1,yl.The accumulated value (called partial accumulated value) ofyi=y|y∈Y,y≠yi other than yi can also be calculated using a one-way accumulative function:zi=hh…hhhx0,y1,y2,y3,…,yi−1,yi+1,…,yl−1,yl. When verifying yi∈Y is required, the formula z′:z′=hzi,yi is used for calculation. If z′=z, yi∈Y.The above conclusion holds because if the attacker does not knowyi, according to the description of one-way function, it will face the computational difficulty that constructing y′ makes z=hzi,y′ established. Hence, (yi,zi) can be regarded as a witness of yi∈Y. During the following discussion, ZN represents the set of all positive integers, and Zn represents the set of positive integers with length within n.One-Way Accumulators [1, 7]. (yi,zi) is the witness of yi∈Y meaning that it meets the following condition:(6)Prk∈ZN,zi,yi::∃y′∈Y,y′≠yi:hzi,yi<1Ak.However, there is an obvious problem with the above analysis: Assume that the attacker can only randomly select predictive valuesy′ in a given set Y. In fact, it is entirely possible for an attack to easily find y′ satisfying z=hzi,y′ beyond the value domain set Y, thus destroying the above description of the witness. A strong description is obtained if the attacker's optional range of predictive values is extended beyond the specified set Y.Strongly One-Way Hash Functions [7]. A family of strongly one-way hash functions is an infinite sequence of families of functions HλλϵN, where Hλ=hk:Xk×Yk⟶Zk (k is a security parameter), having the following properties:(1)
For any integerλ and any hkϵHλ,hk.,. is computable in time polynomial in λ.(2)
Any probabilistic, polynomial-time algorithmA satisfies(7)PrhkH⟵Rλ;xX⟵Rk;yY⟵Rk;x′,y′⟵A1λ,x,y:y′≠yΛhkx,y=hkx′,y′<neglλ.The probability is taken over the random choice ofhk,x,y and random output of A.One-way property means that, given valuesy1,y2,…,yn, their accumulative value z, and another value y′, the attacker has difficulty finding the corresponding witness accu′ such that haccu′,y′=z. Strongly one-way property means that, given y1,y2,…,yn and z, it is hard to find the value corresponding to y′,accu′ so haccu′,y′=z, and y′∉y1,y2,…,yn.


### 2.2. Collision-Free Accumulators

Strongly one-way property does not completely solve the problem of ensuring security in the case of an adversary actively participating in the selection of values to be accumulated (i.e.,x and y in the above description are no longer randomly chosen but carefully chosen by the adversary). In order to fill this gap, Baric and Pfitzmann [5] proposed the concept of collision-free accumulators.Baric and Pfitzmann [5] proposed that the cryptographic accumulator needs to be more strict when building FSS mechanisms. Under the strongly one-way property, the attacker may still carefully forge the member value y1′,y2′,…,yn′ to construct witness accu′ for y′. Therefore, a collision-free accumulator is introduced. On the strongly one-way property basis, the member value y1′,y2′,…,yn′ does not need to be given.Cryptographic Accumulator Scheme [5, 7]. The scheme of a cryptographic accumulator is a 4-tuple containing 4 polynomial time algorithms (Gen, Eval, Wit, and Ver):(1)
Gen (key generation algorithm): it is a probabilistic algorithm for generating initial parameters. Gen receives two parameters: a security variable1λ and an accumulator threshold N, an upper bound on the total number of values that can be securely accumulated, and finally returns an accumulator key k, k∈kλ,N.(2)
Eval (evaluation algorithm): it is a probabilistic algorithm for finding accumulated values. Calculate all accumulated values in the setL=y1,y2,…,yN′, N′∈N, where yi∈Yk,k∈Kλ,N. Eval inputs k,y1,y2,…,yN′ and outputs an accumulated value of z∈Zk and some auxiliary information of aux, which will be used as an input to other algorithms. Note that Eval outputs the same accumulated value for the same input, and the auxiliary information may be different.(3)
Wit (witness extraction algorithm): it is a probabilistic algorithm for generating member witnesses based on relevant information. Wit inputs an accumulatork∈kλ,N, a value yi∈Yk, and auxiliary information aux outputted by Eval k,y1,y2,…,yN′; if yi is in L, a witness wi∈WK is outputted to prove that yi is accumulated within z; otherwise, it returns symbol ⊥.(4)
Ver (verification algorithm): it is a deterministic algorithm for verifying the membership of a value by witness. Ver inputsk,yi,wi,z to verify that yi is accumulated into z and outputs Yes or No according to witness wi.N-Times Collision-Freeness [5, 7]. A cryptographic accumulator scheme is said to be N-times collision-free when it satisfies the following property: A cryptographic accumulator scheme is said to be N-times collision-free if, for any integer λ and for any probabilistic, polynomial-time algorithm A,(8)Prk⟵Gen1λ,N;y1…,yN,y′,w′⟵A1λ,N,k;z,aux⟵Evalk,y1,…,yN:y1,…,yN∈YkΛy′∉y1…,yNΛVerz,y′,w′=Yes<neglλ.where the probability is taken from random output of Gen, Eval, and A.Collision-Freeness [5, 7]. A cryptographic accumulator scheme is collision-free if it is in all N-times collision-free.


### 2.3. Dynamic Accumulators

The application of member authentication requires that the selected cryptographic accumulator can not only enable the verifier to authenticate efficiently but also ensure the security. When a member set changes (added or deleted), the accumulated value and witness of each member can be updated efficiently; otherwise, whenever members are added or deleted, all members need to recalculate the current accumulated value and their respective witness. When the member set changes dynamically, the cryptographic accumulator cannot operate efficiently to meet the practical application requirements. For this reason, researchers put forward the concept of dynamic accumulator, which can add, delete, and update operations on the basis of the original 4-tuple.Dynamic Accumulator Scheme [2, 7]. A dynamic accumulator scheme is a seven-tuple containing seven polynomial time algorithms (Gen, Eval, Wit, Ver, Add, Del, and Upd), where Gen, Eval, Wit, and Ver are the same as in the cryptographic accumulator scheme:(1)
Add (element addition algorithm): it is usually a deterministic algorithm. Given an accumulator keyk, an accumulated value z obtained as the accumulation of some set L of less than N elements, where L⊆YK,z∈Zk, and the value y′∈L to be deleted, it returns a new accumulator value z′ corresponding to the set L∖y′, along with a witness w′∈Wk for y′ and some updated information auxAdd which will be used by the Upd algorithm.(2)
Del (element deletion algorithm): it is usually a deterministic algorithm. Given an accumulator keyk, an accumulated value z obtained as the accumulation of some set L of less than N elements, where L⊆YK,z∈Zk, and the value y′∈Yk to be added, it returns a new accumulator value z′ corresponding to the set L∪y′, along with some update information auxDel which will be used by the Upd algorithm.(3)
Upd (witness update algorithm): it is a deterministic algorithm used to update the witnessw∈Wk of each existing element in the set y∈Yk after adding or deleting elements in L. Upd takes k, y, w, op, and auxop as input (where op is either Add or Del) and returns an updated witness w′ to prove that y has been accumulated into z′.


### 2.4. Universal Accumulators

Universal accumulators are dynamic and support (non)membership proofs [3]. Cryptographic accumulators that support membership proof are called positive accumulators, those that support nonmembership proof are called negative accumulators, and those that support both are called universal accumulators [9].Assuming thatk is a security parameter, the safe universal accumulator of the input {χk} family is a family of functions {Fk} with the following properties [3]:(i)
Effective generation: there is an effective probabilistic polynomial time algorithmG, which generates a random function Fk on input 1k. Moreover, G also outputs some auxiliary information about f, expressed as auxf.(ii)
Efficient evaluation: eachf∈Fk is a polynomial time function, which outputs a value h∈gf when inputting g,x∈gf×χk, where gf is the input domain of the function f and χk is the input domain to accumulate the element.(iii)
Quasi-commutativity: for allf∈Fk, all g∈gf, and all x1,x2∈χk, if ffg,x1,x2=ffg,x2,x1,fg,X can represent ff…g,x1,…,xm).(iv)
Membership witness: for eachf∈Fk, there is a membership validation function ρ1. Set c∈gf and x∈χk. If ρ1c,x,ω1=1, the value ω1 is called membership witness.(v)
Nonmembership witness: for eachf∈Fk, there is a nonmembership validation function ρ2. Set c∈gf and x∈χk; the value ω2 is called nonmembership witness if ρ2 (c, x,w2) = 1.(vi)
Security: for all polynomial-time probability, attackerAk satisfies(9)prf⟵G1k;g⟵gfx,w1,w2,X⟵Akf,gf,gx∈χk;X⊂χk;ρ1fg,X,x,w1=1;ρ2fg,X,x,w2=1=negk.Then, the universal accumulator scheme is safe.Table2 provides description of different types of cryptographic accumulators.Table 2
Descriptions of the cryptographic accumulator.
DescriptionOne-way accumulator [10]One-way hash function [11]A family of one-way hash functions is an infinite sequence of families of functionsHλλϵN, where Hλhk:Xk×Yk⟶Zk, with the following properties:① For any integer λ and any hkϵHλ,hk.,. is computable in polynomial time in λ; ② for any probabilistic, polynomial-time algorithm A, (3) is satisfied, where the probability is taken over the random choice of hk,x,y,y, and the random coins of A.Quasi-commutativityA functionf:X×Y⟶X is said to be quasi-commutative if (4) is satisfied.One-way accumulatorA one-way accumulator is defined as a family of one-way hash functions with quasi-commutativeness. This description is elegant and simple, but, in order to clarify the basic function of the security cryptographic accumulator, the ability to intuitively accumulate setL as a small value can be proved only for element y∈L. In fact, the one-way property imposed by the second requirement is often too weak for applications where the attacker can choose some value to accumulate.Strongly one-way hash functionA family of strongly one-way hash functions is an infinite sequence of families of functionsHλλϵN, where Hλ=hk:Xk×Yk⟶Zk, having the following properties:① For any integer λ and any hkϵHλ,hk.,. is computable in polynomial time in λ; ② for any probabilistic, polynomial-time algorithm A, (7) is satisfied, where the probability is taken over the random choice of hk,x,y,y, and the random coins of A.Collision-free accumulator [5]Cryptographic accumulator schemeThe cryptographic accumulator scheme is a 4-tuple of polynomial-time algorithm (Gen, Eval, Wit, and Ver)N-times collision-freenessA cryptographic accumulator scheme is said to beN-times collision-free if, for any integer λ and for any probabilistic, polynomial-time algorithm A, probability is taken from Gen, Eval, and random coins of A.Collision-freeWhen a cryptographic accumulator scheme isN-times collision-free for any value of N polynomial in λ, it is called collision-free.Dynamic accumulator [12]Dynamic accumulators include polynomial-time algorithms (Gen, Eval, Wit, Ver, Add, Del, and Upd) for 7-tuples.Universal accumulator [13]Universal accumulators are dynamic and support membership and nonmembership proofs.


## 2.1. One-Way Accumulators

The concept of the cryptographic accumulator originated from the one-way accumulator first proposed by Benaloh and Mare [1]. A one-way accumulator is defined as a set of one-way hash functions with quasi-commutativeness.One-Way Hash Functions [1, 7]. A family of one-way hash functions is an infinite sequence of families of functions Hλλ∈N, where Hλ=hk:Xk×Yk⟶Zk (k is a security parameter), with the following properties:(1)
For any integerλ and any hk∈Hλ,hk.,. is computable in time polynomial in λ.(2)
Any probabilistic, polynomial-time algorithm A satisfies(3)PrhkH⟵Rλ;xX⟵Rk;y,Y⟵Rk;x,⟵A1λ,x,y,y,:hkx,y=hkx,,y,<neglλ,where the probability depends on the random selection ofhk, x, y, y′ and random output of A.From the above description, it is seen that the one-way hash function is computable and one-way; that is, givenx and y, the calculation of z=hx,y can be completed in polynomial time, and if given x, y, and y′, the probability of finding x′ satisfying hkx,y=hkx′,y′ is too small to be ignored; that is, the conflict between the outputs generated by different inputs is very little.Quasi-Commutativeness [7, 8]. A function f: X×Y⟶X has quasi-commutativeness means that the following equation holds:(4)∀x∈X,∀y1,y2∈Y:ffx,y1,y2=ffx,y2,y1.If a one-way hash function satisfies the quasi-commutativeness, first of all, the forward calculation is easy according to the one-way property, while the reverse calculation is difficult. Second, satisfying the quasi-commutativeness means that, under the condition of given initial value (Seeds), the results of multiple hash operations will not change with different calculation order.A one-way hash function with quasi-commutativeness can be used to verify whether a valueyi is in a specified set Y=yi. Specifically, the accumulative results z of Y can be calculated by the one-way accumulative function h∈H, using the following formula:(5)z=hh…hhhx0,y1,y2,y3,…,yl−1,yl.The accumulated value (called partial accumulated value) ofyi=y|y∈Y,y≠yi other than yi can also be calculated using a one-way accumulative function:zi=hh…hhhx0,y1,y2,y3,…,yi−1,yi+1,…,yl−1,yl. When verifying yi∈Y is required, the formula z′:z′=hzi,yi is used for calculation. If z′=z, yi∈Y.The above conclusion holds because if the attacker does not knowyi, according to the description of one-way function, it will face the computational difficulty that constructing y′ makes z=hzi,y′ established. Hence, (yi,zi) can be regarded as a witness of yi∈Y. During the following discussion, ZN represents the set of all positive integers, and Zn represents the set of positive integers with length within n.One-Way Accumulators [1, 7]. (yi,zi) is the witness of yi∈Y meaning that it meets the following condition:(6)Prk∈ZN,zi,yi::∃y′∈Y,y′≠yi:hzi,yi<1Ak.However, there is an obvious problem with the above analysis: Assume that the attacker can only randomly select predictive valuesy′ in a given set Y. In fact, it is entirely possible for an attack to easily find y′ satisfying z=hzi,y′ beyond the value domain set Y, thus destroying the above description of the witness. A strong description is obtained if the attacker's optional range of predictive values is extended beyond the specified set Y.Strongly One-Way Hash Functions [7]. A family of strongly one-way hash functions is an infinite sequence of families of functions HλλϵN, where Hλ=hk:Xk×Yk⟶Zk (k is a security parameter), having the following properties:(1)
For any integerλ and any hkϵHλ,hk.,. is computable in time polynomial in λ.(2)
Any probabilistic, polynomial-time algorithmA satisfies(7)PrhkH⟵Rλ;xX⟵Rk;yY⟵Rk;x′,y′⟵A1λ,x,y:y′≠yΛhkx,y=hkx′,y′<neglλ.The probability is taken over the random choice ofhk,x,y and random output of A.One-way property means that, given valuesy1,y2,…,yn, their accumulative value z, and another value y′, the attacker has difficulty finding the corresponding witness accu′ such that haccu′,y′=z. Strongly one-way property means that, given y1,y2,…,yn and z, it is hard to find the value corresponding to y′,accu′ so haccu′,y′=z, and y′∉y1,y2,…,yn.


## 2.2. Collision-Free Accumulators

Strongly one-way property does not completely solve the problem of ensuring security in the case of an adversary actively participating in the selection of values to be accumulated (i.e.,x and y in the above description are no longer randomly chosen but carefully chosen by the adversary). In order to fill this gap, Baric and Pfitzmann [5] proposed the concept of collision-free accumulators.Baric and Pfitzmann [5] proposed that the cryptographic accumulator needs to be more strict when building FSS mechanisms. Under the strongly one-way property, the attacker may still carefully forge the member value y1′,y2′,…,yn′ to construct witness accu′ for y′. Therefore, a collision-free accumulator is introduced. On the strongly one-way property basis, the member value y1′,y2′,…,yn′ does not need to be given.Cryptographic Accumulator Scheme [5, 7]. The scheme of a cryptographic accumulator is a 4-tuple containing 4 polynomial time algorithms (Gen, Eval, Wit, and Ver):(1)
Gen (key generation algorithm): it is a probabilistic algorithm for generating initial parameters. Gen receives two parameters: a security variable1λ and an accumulator threshold N, an upper bound on the total number of values that can be securely accumulated, and finally returns an accumulator key k, k∈kλ,N.(2)
Eval (evaluation algorithm): it is a probabilistic algorithm for finding accumulated values. Calculate all accumulated values in the setL=y1,y2,…,yN′, N′∈N, where yi∈Yk,k∈Kλ,N. Eval inputs k,y1,y2,…,yN′ and outputs an accumulated value of z∈Zk and some auxiliary information of aux, which will be used as an input to other algorithms. Note that Eval outputs the same accumulated value for the same input, and the auxiliary information may be different.(3)
Wit (witness extraction algorithm): it is a probabilistic algorithm for generating member witnesses based on relevant information. Wit inputs an accumulatork∈kλ,N, a value yi∈Yk, and auxiliary information aux outputted by Eval k,y1,y2,…,yN′; if yi is in L, a witness wi∈WK is outputted to prove that yi is accumulated within z; otherwise, it returns symbol ⊥.(4)
Ver (verification algorithm): it is a deterministic algorithm for verifying the membership of a value by witness. Ver inputsk,yi,wi,z to verify that yi is accumulated into z and outputs Yes or No according to witness wi.N-Times Collision-Freeness [5, 7]. A cryptographic accumulator scheme is said to be N-times collision-free when it satisfies the following property: A cryptographic accumulator scheme is said to be N-times collision-free if, for any integer λ and for any probabilistic, polynomial-time algorithm A,(8)Prk⟵Gen1λ,N;y1…,yN,y′,w′⟵A1λ,N,k;z,aux⟵Evalk,y1,…,yN:y1,…,yN∈YkΛy′∉y1…,yNΛVerz,y′,w′=Yes<neglλ.where the probability is taken from random output of Gen, Eval, and A.Collision-Freeness [5, 7]. A cryptographic accumulator scheme is collision-free if it is in all N-times collision-free.


## 2.3. Dynamic Accumulators

The application of member authentication requires that the selected cryptographic accumulator can not only enable the verifier to authenticate efficiently but also ensure the security. When a member set changes (added or deleted), the accumulated value and witness of each member can be updated efficiently; otherwise, whenever members are added or deleted, all members need to recalculate the current accumulated value and their respective witness. When the member set changes dynamically, the cryptographic accumulator cannot operate efficiently to meet the practical application requirements. For this reason, researchers put forward the concept of dynamic accumulator, which can add, delete, and update operations on the basis of the original 4-tuple.Dynamic Accumulator Scheme [2, 7]. A dynamic accumulator scheme is a seven-tuple containing seven polynomial time algorithms (Gen, Eval, Wit, Ver, Add, Del, and Upd), where Gen, Eval, Wit, and Ver are the same as in the cryptographic accumulator scheme:(1)
Add (element addition algorithm): it is usually a deterministic algorithm. Given an accumulator keyk, an accumulated value z obtained as the accumulation of some set L of less than N elements, where L⊆YK,z∈Zk, and the value y′∈L to be deleted, it returns a new accumulator value z′ corresponding to the set L∖y′, along with a witness w′∈Wk for y′ and some updated information auxAdd which will be used by the Upd algorithm.(2)
Del (element deletion algorithm): it is usually a deterministic algorithm. Given an accumulator keyk, an accumulated value z obtained as the accumulation of some set L of less than N elements, where L⊆YK,z∈Zk, and the value y′∈Yk to be added, it returns a new accumulator value z′ corresponding to the set L∪y′, along with some update information auxDel which will be used by the Upd algorithm.(3)
Upd (witness update algorithm): it is a deterministic algorithm used to update the witnessw∈Wk of each existing element in the set y∈Yk after adding or deleting elements in L. Upd takes k, y, w, op, and auxop as input (where op is either Add or Del) and returns an updated witness w′ to prove that y has been accumulated into z′.


## 2.4. Universal Accumulators

Universal accumulators are dynamic and support (non)membership proofs [3]. Cryptographic accumulators that support membership proof are called positive accumulators, those that support nonmembership proof are called negative accumulators, and those that support both are called universal accumulators [9].Assuming thatk is a security parameter, the safe universal accumulator of the input {χk} family is a family of functions {Fk} with the following properties [3]:(i)
Effective generation: there is an effective probabilistic polynomial time algorithmG, which generates a random function Fk on input 1k. Moreover, G also outputs some auxiliary information about f, expressed as auxf.(ii)
Efficient evaluation: eachf∈Fk is a polynomial time function, which outputs a value h∈gf when inputting g,x∈gf×χk, where gf is the input domain of the function f and χk is the input domain to accumulate the element.(iii)
Quasi-commutativity: for allf∈Fk, all g∈gf, and all x1,x2∈χk, if ffg,x1,x2=ffg,x2,x1,fg,X can represent ff…g,x1,…,xm).(iv)
Membership witness: for eachf∈Fk, there is a membership validation function ρ1. Set c∈gf and x∈χk. If ρ1c,x,ω1=1, the value ω1 is called membership witness.(v)
Nonmembership witness: for eachf∈Fk, there is a nonmembership validation function ρ2. Set c∈gf and x∈χk; the value ω2 is called nonmembership witness if ρ2 (c, x,w2) = 1.(vi)
Security: for all polynomial-time probability, attackerAk satisfies(9)prf⟵G1k;g⟵gfx,w1,w2,X⟵Akf,gf,gx∈χk;X⊂χk;ρ1fg,X,x,w1=1;ρ2fg,X,x,w2=1=negk.Then, the universal accumulator scheme is safe.Table2 provides description of different types of cryptographic accumulators.Table 2
Descriptions of the cryptographic accumulator.
DescriptionOne-way accumulator [10]One-way hash function [11]A family of one-way hash functions is an infinite sequence of families of functionsHλλϵN, where Hλhk:Xk×Yk⟶Zk, with the following properties:① For any integer λ and any hkϵHλ,hk.,. is computable in polynomial time in λ; ② for any probabilistic, polynomial-time algorithm A, (3) is satisfied, where the probability is taken over the random choice of hk,x,y,y, and the random coins of A.Quasi-commutativityA functionf:X×Y⟶X is said to be quasi-commutative if (4) is satisfied.One-way accumulatorA one-way accumulator is defined as a family of one-way hash functions with quasi-commutativeness. This description is elegant and simple, but, in order to clarify the basic function of the security cryptographic accumulator, the ability to intuitively accumulate setL as a small value can be proved only for element y∈L. In fact, the one-way property imposed by the second requirement is often too weak for applications where the attacker can choose some value to accumulate.Strongly one-way hash functionA family of strongly one-way hash functions is an infinite sequence of families of functionsHλλϵN, where Hλ=hk:Xk×Yk⟶Zk, having the following properties:① For any integer λ and any hkϵHλ,hk.,. is computable in polynomial time in λ; ② for any probabilistic, polynomial-time algorithm A, (7) is satisfied, where the probability is taken over the random choice of hk,x,y,y, and the random coins of A.Collision-free accumulator [5]Cryptographic accumulator schemeThe cryptographic accumulator scheme is a 4-tuple of polynomial-time algorithm (Gen, Eval, Wit, and Ver)N-times collision-freenessA cryptographic accumulator scheme is said to beN-times collision-free if, for any integer λ and for any probabilistic, polynomial-time algorithm A, probability is taken from Gen, Eval, and random coins of A.Collision-freeWhen a cryptographic accumulator scheme isN-times collision-free for any value of N polynomial in λ, it is called collision-free.Dynamic accumulator [12]Dynamic accumulators include polynomial-time algorithms (Gen, Eval, Wit, Ver, Add, Del, and Upd) for 7-tuples.Universal accumulator [13]Universal accumulators are dynamic and support membership and nonmembership proofs.


## 3. Symmetric and Asymmetric Accumulators

### 3.1. Symmetrical Accumulators

The symmetric cryptographic accumulator is a trapdoor-free structure and does not require witness verification. In random oracle models, the existing structures are secure. The symmetric accumulator [14] basically consists of a one-way function f:Y⟶X and a vector x∈X of length l, initialized to the 0 vector. This set of values y1,y2,…,yn accumulates as vector z:z=x∨fy1∨fy2∨…∨fyn, where ∨ is contained by bit. Given the accumulative vector z and values yi, verify that membership in the accumulative vector includes calculating v=fyi and verifying that, ∀k∈0,l−1,vk=1 means zi=1. Symmetric accumulator does not need to calculate the witness. But it is stuck with the long output of cryptographic accumulators. Actually, the length of the cryptographic accumulator depends also on the number of values added to the cryptographic accumulator and not only on the security parameters.Nyberg [15] proposed a symmetric accumulator. The idea is to use the hash function to generate hash values for the values to be accumulated. Each hash value h is considered to consist of r blocks of size d bits h1,h2,…,hr composition. Then, by mapping each block to one bit, map such code to an r bit string. Accumulated value z is calculated as the coordinate directional bit product corresponding to the string to be accumulated. To verify the membership, the values y and the corresponding bit string y′ with r length can be calculated. Check that, for all 1≤i≤r, when yi′=0, zi=0.Bloom filter [16] can be used as a cryptographic accumulator. Furthermore, Yum et al. [17] proved that it is superior to other symmetric accumulators. Secure Bloom filter consists of k hash functions fi:Y⟶X. These functions actually belong to the hash family. Each hash function uniformly returns a vector index. To add a value to the cryptographic accumulator, it is fed to each hash function to get k indexes. The bit of x at these indexes is set to 1. To verify that a given value is accumulated, k hash functions are applied again to obtain the vector index. If any bit of the accumulative vector is 0 at these indexes, then the value is definitely not accumulated. If all the bits at these indexes are 1, then an incorrect positive response may be obtained. Another variant of Bloom filter has been studied in the past, where the hash function is replaced by a hash-based message authentication code (HMAC).It can be noted that, in the case of symmetric accumulators, the size ofl increases as the number of elements in the filter increases or the false positive rate is set as low.


### 3.2. Asymmetric Accumulators

The first cryptographic accumulator proposed is asymmetric and requires witness verification [1]. This construct takes the modulus f (x, y) = xymodN as a one-way and quasi-commutative function because it satisfies(10)ffx,y1,y2=xy1y2=xy2y1=ffx,y2,y1.For power operations for one-way accumulators, the module is chosen as the product of two safe prime numbersp and q of equal size. If p−1/2 is also a prime, prime p is safe. Malicious attacker who knows the accumulated value z may forge witness w for the randomly selected value y by finding the initial value x verifying xymodN=z. However, this is not feasible under the RSA assumption.Table3 shows the development of symmetric and asymmetric accumulators.Table 3
Development process.
Symmetric accumulatorBloom filter constructs an cryptographic accumulator.A symmetric accumulator is proposed to generate hash values for the values to be accumulated hash functions.Asymmetric accumulatorThe first cryptographic accumulator proposed in 1993 is asymmetric and requires witness validation.


## 3.1. Symmetrical Accumulators

The symmetric cryptographic accumulator is a trapdoor-free structure and does not require witness verification. In random oracle models, the existing structures are secure. The symmetric accumulator [14] basically consists of a one-way function f:Y⟶X and a vector x∈X of length l, initialized to the 0 vector. This set of values y1,y2,…,yn accumulates as vector z:z=x∨fy1∨fy2∨…∨fyn, where ∨ is contained by bit. Given the accumulative vector z and values yi, verify that membership in the accumulative vector includes calculating v=fyi and verifying that, ∀k∈0,l−1,vk=1 means zi=1. Symmetric accumulator does not need to calculate the witness. But it is stuck with the long output of cryptographic accumulators. Actually, the length of the cryptographic accumulator depends also on the number of values added to the cryptographic accumulator and not only on the security parameters.Nyberg [15] proposed a symmetric accumulator. The idea is to use the hash function to generate hash values for the values to be accumulated. Each hash value h is considered to consist of r blocks of size d bits h1,h2,…,hr composition. Then, by mapping each block to one bit, map such code to an r bit string. Accumulated value z is calculated as the coordinate directional bit product corresponding to the string to be accumulated. To verify the membership, the values y and the corresponding bit string y′ with r length can be calculated. Check that, for all 1≤i≤r, when yi′=0, zi=0.Bloom filter [16] can be used as a cryptographic accumulator. Furthermore, Yum et al. [17] proved that it is superior to other symmetric accumulators. Secure Bloom filter consists of k hash functions fi:Y⟶X. These functions actually belong to the hash family. Each hash function uniformly returns a vector index. To add a value to the cryptographic accumulator, it is fed to each hash function to get k indexes. The bit of x at these indexes is set to 1. To verify that a given value is accumulated, k hash functions are applied again to obtain the vector index. If any bit of the accumulative vector is 0 at these indexes, then the value is definitely not accumulated. If all the bits at these indexes are 1, then an incorrect positive response may be obtained. Another variant of Bloom filter has been studied in the past, where the hash function is replaced by a hash-based message authentication code (HMAC).It can be noted that, in the case of symmetric accumulators, the size ofl increases as the number of elements in the filter increases or the false positive rate is set as low.


## 3.2. Asymmetric Accumulators

The first cryptographic accumulator proposed is asymmetric and requires witness verification [1]. This construct takes the modulus f (x, y) = xymodN as a one-way and quasi-commutative function because it satisfies(10)ffx,y1,y2=xy1y2=xy2y1=ffx,y2,y1.For power operations for one-way accumulators, the module is chosen as the product of two safe prime numbersp and q of equal size. If p−1/2 is also a prime, prime p is safe. Malicious attacker who knows the accumulated value z may forge witness w for the randomly selected value y by finding the initial value x verifying xymodN=z. However, this is not feasible under the RSA assumption.Table3 shows the development of symmetric and asymmetric accumulators.Table 3
Development process.
Symmetric accumulatorBloom filter constructs an cryptographic accumulator.A symmetric accumulator is proposed to generate hash values for the values to be accumulated hash functions.Asymmetric accumulatorThe first cryptographic accumulator proposed in 1993 is asymmetric and requires witness validation.


## 4. Accumulator Based on Various Security Assumptions

Table4 shows the evolution of different types of security assumptions.Table 4
Security assumptions.
1993 [1]Proposing the first cryptographic accumulator which is asymmetric and requires witness verification.Hash-based construction2000 [18] 2002 [19]Proposing the first universal dynamic accumulator satisfying nonrepudiation.2008 [20]A universal accumulator structure based on the hash tree is proposed, which satisfies the concept similar to the nonrepudiation, called a strong universal accumulator.RSA assumption1996 [15]Imposing one-way property (applications where some adversaries can access the list of values to accumulate may not succeed).Strong RSA assumption1999 [21]Proposing a trapdoor-free accumulator.2002 [2]Dynamic accumulator.2005 [22]Dynamic accumulator for bilinear pairs.t-SDH2004 [23]Elliptic curves construction of cryptographic accumulator.2007 [24](Nonmembership proof is inevitable) providing a dynamic accumulator, then called a universal accumulator.2009 [25]Dynamic pairing accumulator (more efficient witness update algorithm).t-DHE2005 [26]Bilinear map accumulator.2009 [25]t-bound accumulator scheme based on t-DHE assumption is presented.


### 4.1. Accumulator Based on Hash Tree

#### 4.1.1. Hash Tree

Hash tree, in cryptography and computer science, is a tree data structure in which every leaf node is labeled with the hash of the data block, while the node other than the leaf node is labeled with the encrypted hash of its child node label. Hash trees can efficiently and securely validate the contents of large data structures. A prime resolution algorithm is selected to build a hash tree [20]. Consecutive primes starting at 2 are selected to build a ten-level hash tree. The node of the first layer is the root node, and there are two nodes under the root node. The second layer has three nodes under each node, and so on; that is, the number of children of each node layer is a continuous prime number. By the tenth level, there are 29 nodes under each node. The children of the same node, from left to right, represent different remainder results. For example, the second layer node has three children. So, from left to right, 0 is divided by 3, 1 is divided by 3, and 2 is divided by 3. The remainder of the mod operation on a prime number determines the path of processing.


#### 4.1.2. Accumulator Based on Hash Tree

In a hash tree, values are associated with the leaves of a binary tree. The value of the sibling node is hash in order to calculate the value associated with its parent node, and so on, until the value of the tree root is obtained. The root value of the tree is defined as the cryptographic accumulator of the set of values associated with the leaves of the tree [20]. The hash tree cannot be directly used to obtain the functions of general and dynamic accumulators. In fact, cumulative sets need to add and remove elements (tree node values if a hash tree is used), while generating nonmembership proof. So, instead of associating values with the leaves of the tree, a pair of continuously accumulated set elements are associated. To prove that element x is not in the accumulative set, it is now equivalent to indicating that a pair x∝,xβ (where x∝<x<xβ) belongs to the tree, but pairs (x∝, x) and (x,xβ) do not belong to the tree.


#### 4.1.3. Development Process of the Accumulator Based on Hash Tree

Buldas et al. [18, 19] proposed the first universal dynamic accumulator satisfying nonrepudiation (called the nonrepudiable certifier and formalized in the context of the cryptographic accumulator). Its construction is based on collision-resistant hashes and hash trees. Then, a universal accumulator structure based on hash tree is proposed, which satisfies the concept similar to nonrepudiation (the scheme is called strong universal accumulator). Recently, another cryptographic accumulator based on hash tree has been introduced, which uses the promise of modular operations on RSA composite modules based on binary polynomials as a collision-resistant hash function.


### 4.2. Accumulator Based on RSA Assumption

#### 4.2.1. RSA Assumption

RSA hard problem means that,∀y,z,n∈Zn1,∃x∈Zn:z=xymodn is known. The RSA assumption refers to the fact that the RSA assumption is computationally infeasible for all polynomial-time algorithms A [5]; that is,(11)Pry,z,n∈Zn::∃x:z=xymodn≤1An.According to the RSA hard problem assumption, first, the functionz=xymodn satisfies the one-way property. Second, the function z=xy satisfies the quasi-commutativeness. That is, ∀y1,y2: z(z(x,y1,), y2) = xy1y2 = xy1y2 = z(z(x,y2), y1) is established.When the modulusN is large enough and is generated randomly and the exponential y and value z are given, it is difficult to calculate x satisfying xymodN=z. However, as informally noted in [1] and later recognized in Nyberg [15], the one-way property imposed in the description may not succeed for applications where certain adversaries have access to the list of values to accumulate. To remedy, a stronger property called strongly one-way property should be considered, where choices do not impose y′ on the attacker as one-way hash functions.


#### 4.2.2. Strong RSA Assumption

The strong RSA hard problem means that,∀z,n∈Zs,∃x∈Zp,y:z=xymodn is known, where Zp is the set of prime numbers. The strong RSA hard problem assumption means that the strong RSA hard problem is computationally infeasible for all polynomial-time methods A [2]; that is,(12)Prz∈Zn,n∈Zs::∃x∈Zn,y∈Zp:z=xymodn≤1An.In contrast to general RSA, the strong RSA hard problem assumption allows free choice of combinations (x, y); that is, the attacker can choose not only the base of the exponential function but also the exponent. In addition, the strong RSA assumption also requires that the exponent be prime, while the general RSA assumption has no special requirement for the exponent. For the strong RSA hard problem assumption, there is no strict proof that it is computationally feasible. Again, there is no rigorous theoretical proof that it works on a computer.When the modulusN is large enough and randomly generated and given the value z, it is difficult to find x and y that satisfy xymodN=z as previously demonstrated; impact resistance can be obtained under strong RSA assumptions only if the value to be accumulated is prime.Cryptographic accumulators without trapdoor should be able to be constructed. Trapdoors are unnecessary in the cryptographic accumulator scheme. The side that providesN during system setup also knows trapdoors p and q. Unfortunately, the side that knows p and q can completely bypass the security of the system. Because by knowing p and q, it is possible to recover the initial value and then independently accumulate additional values and generate false witnesses. A trapdoor-free solution will not rely on trusted online or offline services. Then a trapdoor-free accumulator is introduced, which is proved to be safe in the standard model. The authors suggest the use of a generalized RSA module with unknown complete factorization and call it RSA-UFOS. A number N is an RSA-UFO, and if N has at least two large prime factors p and q, then no participant in the union, including those that produce N, will be able to find an N that splits into factors N1 and N2, thus making P|N1 and q|N2. A probabilistic algorithm is also proposed to generate such numbers. Under the standard model, security is proved under a new assumption called “strong RSA-UFO assumption.” This assumption is very similar to the strong RSA assumption, with the only difference being that module N is set to RSA-UFO.


#### 4.2.3. Accumulator Based on Strong RSA Assumption

All schemes in this setting are [1, 5] extensions. The accumulator accx is defined as accx⟵g∏x∈XxmodN, where N is an RSA modulus consisting of two large safe prime numbers p and g, which is randomly drawn from the cyclic group of the quadratic remainder of N. There are skacc,pkacc=p,q,N and the witnesses of the value xi given by witxi⟵accxxi−1modN. Obviously, if the value xi not included in acc can forge witness witxi⟵accxxi−1modN, then the strong RSA assumption will be broke. Because of the product relation of the accumulated value in the exponent, the domain of the accumulated value is limited to prime number. Note that when a given witness wita (i.e., witb≡witacmodN), accumulating a compound number will allow a=b·c derivation of the witness for each of its factors, to accumulate sets from more general domains, an appropriate mapping from these domains to prime numbers will be required (see [27]).Certain cryptographic accumulator schemes in this setting [2] also provide dynamic functionality. Simply summing the cryptographic accumulator and its witness can add values to the cryptographic accumulator without any secret. On the contrary, if the value xj is to be deleted, the xj−th root of the cryptographic accumulator must be calculated, which is difficult to solve under strong RSA assumptions without skacc. However, after removing the value, membership witnesses can still be publicly updated using arithmetic techniques. To update the witness accx/xj of the value xi, find a,b∈Z, so that axi+bxj=1 and calculate the new witness as witxi′⟵witxib·accx/xjmodN and original witness is witxi.Moreover, cryptographic accumulator scheme provides general functionality because it supports nonmembership witnesses:accX is accumulator for set X and yj∉X. Now it holds that gcd∏x∈Xx,yj=1 or equivalently for a,b∈Z, a∏x∈Xx+byj=1. Therefore, d⟵g−bmodN is calculated, where g is the initial value of the empty cryptographic accumulator and forms a nonmembership witness wityi⟵a,b. Then, the verification of nonmembership witnesses is completed by checking whether accxa≡dyi·gmodN is established. Similar to what is done for membership, nonmembership witnesses can also be publicly updated (see [24]).


### 4.3. Accumulator Based on t-SDH Assumption

#### 4.3.1. t-SDH Assumption

Given a tuplet = (p, G, P), where p is prime, G is a cyclic group generated by P and a tuple in the form of value (P, sP, … stP) in Z/pZ, wheres∈Z/pZ0 [8]. For any probabilistic polynomial-time algorithm A, the following probabilities can be negligible:(13)Pr=AtP,sP…,stP=c,1s+cPΛc∈ZpZ.Tartary et al. [28] made requirements for the conflict resistance performance of the scheme, thus refuting previous claims against cryptographic accumulators. Attack is based on improperly defined security models in which adversaries have access to functions f and g. The proposed patch includes providing compound functions g (f(.)) to the adversary instead of providing functions f and g, respectively. However, the patches proposed by the authors cannot prevent other types of attacks and have proved the scheme to be unsafe. Camenisch et al. [25] proposed another cryptographic accumulator based on dynamic pairing, which provides a more efficient witness update algorithm.Fazio and Nicolosi [7] pointed out in their investigation of the cryptographic accumulator that the original structure makes the time to update the witness after m changes the cryptographic accumulator proportional to m. They raised the question of whether batch updates are possible, that is, whether it is possible to build a cryptographic accumulator where the time to update the witness is independent of the number of changes to the cryptographic accumulator set. Wang et al. [29] designed a cryptographic accumulator with batch processing update and then made improvements to solve the above problems. The scheme is based on the Paillier cipher system and is proven to be secure under a new assumption called the extended strong RSA assumption, which is a variant of the strong RSA assumption with modulus N2. However, contrary to this claim, Camacho and Hevia [30] have shown evidence of an attack and further demonstrated that the time to update the witness in the worst case must be at least Ωm. Therefore, this provides impossible results on a cryptographic accumulator with batch update capabilities.Previous works have produced only membership witnesses, but, in some cases, nonmembership witnesses may be unavoidable. The authors present a dynamic accumulator that supports both membership and nonmembership short witnesses, which they call the universal accumulator. The initial value of the cryptographic accumulator must be public so that nonmembership witnesses can be verified. This construct is based on the RSA function, so only prime numbers are allowed to accumulate.Karlof et al. [23] used elliptic curves to construct cryptographic accumulators. To add up the values (scalars), multiply them by the public key (i.e., scalars multiply the base point of the curve). Witness generation follows the same algorithm but does not include corresponding values. Validation is simple; if the product of the witness and the value is equal to the accumulated value, it is necessary to check for equality.


#### 4.3.2. Accumulator Based on t-SDH Assumption

Nguyen [22] proposed a t-bound accumulator. The cryptographic accumulator uses a group G of prime number p generated by g and has bilinear maps e:G×G⟶GT. Here, pkacc=g,gs,gs2,…,gst,u and skacc=s.  The accumulator accx of set X=x1,x2,…,xn∈Zp (n≤t) is defined as accx⟵gu∏x∈Xx+s, and the membership witness witxi⟵gu∏x∈X\xix+s is calculated, where u⟵RZp∗. Then, check whether accX contains the value xi by verifying whether eaccx,g=egxigs,witxi is true or not. The scheme allows the public evaluation of cryptographic accumulators; that is, ghs is obtained by extending polynomial hx=∏x∈Xx+s∈ZpX and by evaluating it in G through pkacc. The public calculation of the witnesses of xi also works on set X/xi. Furthermore, these witnesses can be updated at a constant time without knowing the secret key (see [22]).Nguyen’s scheme is extended by nonmembership witnesses, and the random valueu is eliminated [31, 32]. Previous work also showed how to publicly update nonmembership witnesses within a fixed period of time. Note that these adjustments can also be applied to the latter [31]. The calculation of nonmembership witnesses with value yj∉X makes use of the following facts: hx=∏x∈Xx+X is divided by the polynomial division remainder of yj+X. Such witnesses take the form of a,b=ghs−d/yi+s,d) and may be validated by eaccx,g?=ea,gyi,gseg,gs).


### 4.4. Accumulator Based on t-DHE Assumption

Diffie–Hellman Exponent (DHE) Assumption. The t-DHE problem in a group G of prime order q is defined as follows: Let gi=gγi, γ⟵RZq. On input {g, g1, g2, …, gt, gt+2, …, g2t} ∈G2t, output gt+1.The t-DHE assumption states that this problem is hard to solve.Camenisch et al. [25] gave a scheme of t-bound accumulator based on t-DHE assumption, like the cryptographic accumulator in t-SDH settings, which uses a group G of prime number p generated by g and has bilinear mapping e: G×G⟶GT. Besides, it needs a signature scheme with corresponding key pairs sksig,pksig. Here, skacc=sksig, public key is pkacc=g1,…,gt,gt+2,…,g2t,z,pksig=gγ1,…,gγt,gγt+2,…,gγ2t,eg,gγt+1,pksig, andγR⟵Zp∗. Xx1,…,xm can be accumulated by calculating accX⟵∏i=1mgt+1−i and signing gi with xi using sksig, where m≤t, thus assigning the value of xi to gi. The witness witxj of xj∈X is accX⟵∏i=1,i≠jmgt+1−i+j. The membership of xj can be verified by checking whether egj,accX=z⋅eg,witxj is valid and verifying the signatures of gj and xj under pksig.This scheme allows public updates for witnesses and cryptographic accumulators to be deleted, as this requires onlypkacc. However, if the value xi is to be added to the cryptographic accumulator, a secret signature key skacc is required to create signatures on gi and xi to link the value xi to this parameter. Therefore, the public addition of the cryptographic accumulator requires that a signature be included for each potential value to be stored in the public parameter. Obviously, this seems impractical except for the small accumulative domain.


## 4.1. Accumulator Based on Hash Tree

### 4.1.1. Hash Tree

Hash tree, in cryptography and computer science, is a tree data structure in which every leaf node is labeled with the hash of the data block, while the node other than the leaf node is labeled with the encrypted hash of its child node label. Hash trees can efficiently and securely validate the contents of large data structures. A prime resolution algorithm is selected to build a hash tree [20]. Consecutive primes starting at 2 are selected to build a ten-level hash tree. The node of the first layer is the root node, and there are two nodes under the root node. The second layer has three nodes under each node, and so on; that is, the number of children of each node layer is a continuous prime number. By the tenth level, there are 29 nodes under each node. The children of the same node, from left to right, represent different remainder results. For example, the second layer node has three children. So, from left to right, 0 is divided by 3, 1 is divided by 3, and 2 is divided by 3. The remainder of the mod operation on a prime number determines the path of processing.


### 4.1.2. Accumulator Based on Hash Tree

In a hash tree, values are associated with the leaves of a binary tree. The value of the sibling node is hash in order to calculate the value associated with its parent node, and so on, until the value of the tree root is obtained. The root value of the tree is defined as the cryptographic accumulator of the set of values associated with the leaves of the tree [20]. The hash tree cannot be directly used to obtain the functions of general and dynamic accumulators. In fact, cumulative sets need to add and remove elements (tree node values if a hash tree is used), while generating nonmembership proof. So, instead of associating values with the leaves of the tree, a pair of continuously accumulated set elements are associated. To prove that element x is not in the accumulative set, it is now equivalent to indicating that a pair x∝,xβ (where x∝<x<xβ) belongs to the tree, but pairs (x∝, x) and (x,xβ) do not belong to the tree.


### 4.1.3. Development Process of the Accumulator Based on Hash Tree

Buldas et al. [18, 19] proposed the first universal dynamic accumulator satisfying nonrepudiation (called the nonrepudiable certifier and formalized in the context of the cryptographic accumulator). Its construction is based on collision-resistant hashes and hash trees. Then, a universal accumulator structure based on hash tree is proposed, which satisfies the concept similar to nonrepudiation (the scheme is called strong universal accumulator). Recently, another cryptographic accumulator based on hash tree has been introduced, which uses the promise of modular operations on RSA composite modules based on binary polynomials as a collision-resistant hash function.


## 4.1.1. Hash Tree

Hash tree, in cryptography and computer science, is a tree data structure in which every leaf node is labeled with the hash of the data block, while the node other than the leaf node is labeled with the encrypted hash of its child node label. Hash trees can efficiently and securely validate the contents of large data structures. A prime resolution algorithm is selected to build a hash tree [20]. Consecutive primes starting at 2 are selected to build a ten-level hash tree. The node of the first layer is the root node, and there are two nodes under the root node. The second layer has three nodes under each node, and so on; that is, the number of children of each node layer is a continuous prime number. By the tenth level, there are 29 nodes under each node. The children of the same node, from left to right, represent different remainder results. For example, the second layer node has three children. So, from left to right, 0 is divided by 3, 1 is divided by 3, and 2 is divided by 3. The remainder of the mod operation on a prime number determines the path of processing.


## 4.1.2. Accumulator Based on Hash Tree

In a hash tree, values are associated with the leaves of a binary tree. The value of the sibling node is hash in order to calculate the value associated with its parent node, and so on, until the value of the tree root is obtained. The root value of the tree is defined as the cryptographic accumulator of the set of values associated with the leaves of the tree [20]. The hash tree cannot be directly used to obtain the functions of general and dynamic accumulators. In fact, cumulative sets need to add and remove elements (tree node values if a hash tree is used), while generating nonmembership proof. So, instead of associating values with the leaves of the tree, a pair of continuously accumulated set elements are associated. To prove that element x is not in the accumulative set, it is now equivalent to indicating that a pair x∝,xβ (where x∝<x<xβ) belongs to the tree, but pairs (x∝, x) and (x,xβ) do not belong to the tree.


## 4.1.3. Development Process of the Accumulator Based on Hash Tree

Buldas et al. [18, 19] proposed the first universal dynamic accumulator satisfying nonrepudiation (called the nonrepudiable certifier and formalized in the context of the cryptographic accumulator). Its construction is based on collision-resistant hashes and hash trees. Then, a universal accumulator structure based on hash tree is proposed, which satisfies the concept similar to nonrepudiation (the scheme is called strong universal accumulator). Recently, another cryptographic accumulator based on hash tree has been introduced, which uses the promise of modular operations on RSA composite modules based on binary polynomials as a collision-resistant hash function.


## 4.2. Accumulator Based on RSA Assumption

### 4.2.1. RSA Assumption

RSA hard problem means that,∀y,z,n∈Zn1,∃x∈Zn:z=xymodn is known. The RSA assumption refers to the fact that the RSA assumption is computationally infeasible for all polynomial-time algorithms A [5]; that is,(11)Pry,z,n∈Zn::∃x:z=xymodn≤1An.According to the RSA hard problem assumption, first, the functionz=xymodn satisfies the one-way property. Second, the function z=xy satisfies the quasi-commutativeness. That is, ∀y1,y2: z(z(x,y1,), y2) = xy1y2 = xy1y2 = z(z(x,y2), y1) is established.When the modulusN is large enough and is generated randomly and the exponential y and value z are given, it is difficult to calculate x satisfying xymodN=z. However, as informally noted in [1] and later recognized in Nyberg [15], the one-way property imposed in the description may not succeed for applications where certain adversaries have access to the list of values to accumulate. To remedy, a stronger property called strongly one-way property should be considered, where choices do not impose y′ on the attacker as one-way hash functions.


### 4.2.2. Strong RSA Assumption

The strong RSA hard problem means that,∀z,n∈Zs,∃x∈Zp,y:z=xymodn is known, where Zp is the set of prime numbers. The strong RSA hard problem assumption means that the strong RSA hard problem is computationally infeasible for all polynomial-time methods A [2]; that is,(12)Prz∈Zn,n∈Zs::∃x∈Zn,y∈Zp:z=xymodn≤1An.In contrast to general RSA, the strong RSA hard problem assumption allows free choice of combinations (x, y); that is, the attacker can choose not only the base of the exponential function but also the exponent. In addition, the strong RSA assumption also requires that the exponent be prime, while the general RSA assumption has no special requirement for the exponent. For the strong RSA hard problem assumption, there is no strict proof that it is computationally feasible. Again, there is no rigorous theoretical proof that it works on a computer.When the modulusN is large enough and randomly generated and given the value z, it is difficult to find x and y that satisfy xymodN=z as previously demonstrated; impact resistance can be obtained under strong RSA assumptions only if the value to be accumulated is prime.Cryptographic accumulators without trapdoor should be able to be constructed. Trapdoors are unnecessary in the cryptographic accumulator scheme. The side that providesN during system setup also knows trapdoors p and q. Unfortunately, the side that knows p and q can completely bypass the security of the system. Because by knowing p and q, it is possible to recover the initial value and then independently accumulate additional values and generate false witnesses. A trapdoor-free solution will not rely on trusted online or offline services. Then a trapdoor-free accumulator is introduced, which is proved to be safe in the standard model. The authors suggest the use of a generalized RSA module with unknown complete factorization and call it RSA-UFOS. A number N is an RSA-UFO, and if N has at least two large prime factors p and q, then no participant in the union, including those that produce N, will be able to find an N that splits into factors N1 and N2, thus making P|N1 and q|N2. A probabilistic algorithm is also proposed to generate such numbers. Under the standard model, security is proved under a new assumption called “strong RSA-UFO assumption.” This assumption is very similar to the strong RSA assumption, with the only difference being that module N is set to RSA-UFO.


### 4.2.3. Accumulator Based on Strong RSA Assumption

All schemes in this setting are [1, 5] extensions. The accumulator accx is defined as accx⟵g∏x∈XxmodN, where N is an RSA modulus consisting of two large safe prime numbers p and g, which is randomly drawn from the cyclic group of the quadratic remainder of N. There are skacc,pkacc=p,q,N and the witnesses of the value xi given by witxi⟵accxxi−1modN. Obviously, if the value xi not included in acc can forge witness witxi⟵accxxi−1modN, then the strong RSA assumption will be broke. Because of the product relation of the accumulated value in the exponent, the domain of the accumulated value is limited to prime number. Note that when a given witness wita (i.e., witb≡witacmodN), accumulating a compound number will allow a=b·c derivation of the witness for each of its factors, to accumulate sets from more general domains, an appropriate mapping from these domains to prime numbers will be required (see [27]).Certain cryptographic accumulator schemes in this setting [2] also provide dynamic functionality. Simply summing the cryptographic accumulator and its witness can add values to the cryptographic accumulator without any secret. On the contrary, if the value xj is to be deleted, the xj−th root of the cryptographic accumulator must be calculated, which is difficult to solve under strong RSA assumptions without skacc. However, after removing the value, membership witnesses can still be publicly updated using arithmetic techniques. To update the witness accx/xj of the value xi, find a,b∈Z, so that axi+bxj=1 and calculate the new witness as witxi′⟵witxib·accx/xjmodN and original witness is witxi.Moreover, cryptographic accumulator scheme provides general functionality because it supports nonmembership witnesses:accX is accumulator for set X and yj∉X. Now it holds that gcd∏x∈Xx,yj=1 or equivalently for a,b∈Z, a∏x∈Xx+byj=1. Therefore, d⟵g−bmodN is calculated, where g is the initial value of the empty cryptographic accumulator and forms a nonmembership witness wityi⟵a,b. Then, the verification of nonmembership witnesses is completed by checking whether accxa≡dyi·gmodN is established. Similar to what is done for membership, nonmembership witnesses can also be publicly updated (see [24]).


## 4.2.1. RSA Assumption

RSA hard problem means that,∀y,z,n∈Zn1,∃x∈Zn:z=xymodn is known. The RSA assumption refers to the fact that the RSA assumption is computationally infeasible for all polynomial-time algorithms A [5]; that is,(11)Pry,z,n∈Zn::∃x:z=xymodn≤1An.According to the RSA hard problem assumption, first, the functionz=xymodn satisfies the one-way property. Second, the function z=xy satisfies the quasi-commutativeness. That is, ∀y1,y2: z(z(x,y1,), y2) = xy1y2 = xy1y2 = z(z(x,y2), y1) is established.When the modulusN is large enough and is generated randomly and the exponential y and value z are given, it is difficult to calculate x satisfying xymodN=z. However, as informally noted in [1] and later recognized in Nyberg [15], the one-way property imposed in the description may not succeed for applications where certain adversaries have access to the list of values to accumulate. To remedy, a stronger property called strongly one-way property should be considered, where choices do not impose y′ on the attacker as one-way hash functions.


## 4.2.2. Strong RSA Assumption

The strong RSA hard problem means that,∀z,n∈Zs,∃x∈Zp,y:z=xymodn is known, where Zp is the set of prime numbers. The strong RSA hard problem assumption means that the strong RSA hard problem is computationally infeasible for all polynomial-time methods A [2]; that is,(12)Prz∈Zn,n∈Zs::∃x∈Zn,y∈Zp:z=xymodn≤1An.In contrast to general RSA, the strong RSA hard problem assumption allows free choice of combinations (x, y); that is, the attacker can choose not only the base of the exponential function but also the exponent. In addition, the strong RSA assumption also requires that the exponent be prime, while the general RSA assumption has no special requirement for the exponent. For the strong RSA hard problem assumption, there is no strict proof that it is computationally feasible. Again, there is no rigorous theoretical proof that it works on a computer.When the modulusN is large enough and randomly generated and given the value z, it is difficult to find x and y that satisfy xymodN=z as previously demonstrated; impact resistance can be obtained under strong RSA assumptions only if the value to be accumulated is prime.Cryptographic accumulators without trapdoor should be able to be constructed. Trapdoors are unnecessary in the cryptographic accumulator scheme. The side that providesN during system setup also knows trapdoors p and q. Unfortunately, the side that knows p and q can completely bypass the security of the system. Because by knowing p and q, it is possible to recover the initial value and then independently accumulate additional values and generate false witnesses. A trapdoor-free solution will not rely on trusted online or offline services. Then a trapdoor-free accumulator is introduced, which is proved to be safe in the standard model. The authors suggest the use of a generalized RSA module with unknown complete factorization and call it RSA-UFOS. A number N is an RSA-UFO, and if N has at least two large prime factors p and q, then no participant in the union, including those that produce N, will be able to find an N that splits into factors N1 and N2, thus making P|N1 and q|N2. A probabilistic algorithm is also proposed to generate such numbers. Under the standard model, security is proved under a new assumption called “strong RSA-UFO assumption.” This assumption is very similar to the strong RSA assumption, with the only difference being that module N is set to RSA-UFO.


## 4.2.3. Accumulator Based on Strong RSA Assumption

All schemes in this setting are [1, 5] extensions. The accumulator accx is defined as accx⟵g∏x∈XxmodN, where N is an RSA modulus consisting of two large safe prime numbers p and g, which is randomly drawn from the cyclic group of the quadratic remainder of N. There are skacc,pkacc=p,q,N and the witnesses of the value xi given by witxi⟵accxxi−1modN. Obviously, if the value xi not included in acc can forge witness witxi⟵accxxi−1modN, then the strong RSA assumption will be broke. Because of the product relation of the accumulated value in the exponent, the domain of the accumulated value is limited to prime number. Note that when a given witness wita (i.e., witb≡witacmodN), accumulating a compound number will allow a=b·c derivation of the witness for each of its factors, to accumulate sets from more general domains, an appropriate mapping from these domains to prime numbers will be required (see [27]).Certain cryptographic accumulator schemes in this setting [2] also provide dynamic functionality. Simply summing the cryptographic accumulator and its witness can add values to the cryptographic accumulator without any secret. On the contrary, if the value xj is to be deleted, the xj−th root of the cryptographic accumulator must be calculated, which is difficult to solve under strong RSA assumptions without skacc. However, after removing the value, membership witnesses can still be publicly updated using arithmetic techniques. To update the witness accx/xj of the value xi, find a,b∈Z, so that axi+bxj=1 and calculate the new witness as witxi′⟵witxib·accx/xjmodN and original witness is witxi.Moreover, cryptographic accumulator scheme provides general functionality because it supports nonmembership witnesses:accX is accumulator for set X and yj∉X. Now it holds that gcd∏x∈Xx,yj=1 or equivalently for a,b∈Z, a∏x∈Xx+byj=1. Therefore, d⟵g−bmodN is calculated, where g is the initial value of the empty cryptographic accumulator and forms a nonmembership witness wityi⟵a,b. Then, the verification of nonmembership witnesses is completed by checking whether accxa≡dyi·gmodN is established. Similar to what is done for membership, nonmembership witnesses can also be publicly updated (see [24]).


## 4.3. Accumulator Based on t-SDH Assumption

### 4.3.1. t-SDH Assumption

Given a tuplet = (p, G, P), where p is prime, G is a cyclic group generated by P and a tuple in the form of value (P, sP, … stP) in Z/pZ, wheres∈Z/pZ0 [8]. For any probabilistic polynomial-time algorithm A, the following probabilities can be negligible:(13)Pr=AtP,sP…,stP=c,1s+cPΛc∈ZpZ.Tartary et al. [28] made requirements for the conflict resistance performance of the scheme, thus refuting previous claims against cryptographic accumulators. Attack is based on improperly defined security models in which adversaries have access to functions f and g. The proposed patch includes providing compound functions g (f(.)) to the adversary instead of providing functions f and g, respectively. However, the patches proposed by the authors cannot prevent other types of attacks and have proved the scheme to be unsafe. Camenisch et al. [25] proposed another cryptographic accumulator based on dynamic pairing, which provides a more efficient witness update algorithm.Fazio and Nicolosi [7] pointed out in their investigation of the cryptographic accumulator that the original structure makes the time to update the witness after m changes the cryptographic accumulator proportional to m. They raised the question of whether batch updates are possible, that is, whether it is possible to build a cryptographic accumulator where the time to update the witness is independent of the number of changes to the cryptographic accumulator set. Wang et al. [29] designed a cryptographic accumulator with batch processing update and then made improvements to solve the above problems. The scheme is based on the Paillier cipher system and is proven to be secure under a new assumption called the extended strong RSA assumption, which is a variant of the strong RSA assumption with modulus N2. However, contrary to this claim, Camacho and Hevia [30] have shown evidence of an attack and further demonstrated that the time to update the witness in the worst case must be at least Ωm. Therefore, this provides impossible results on a cryptographic accumulator with batch update capabilities.Previous works have produced only membership witnesses, but, in some cases, nonmembership witnesses may be unavoidable. The authors present a dynamic accumulator that supports both membership and nonmembership short witnesses, which they call the universal accumulator. The initial value of the cryptographic accumulator must be public so that nonmembership witnesses can be verified. This construct is based on the RSA function, so only prime numbers are allowed to accumulate.Karlof et al. [23] used elliptic curves to construct cryptographic accumulators. To add up the values (scalars), multiply them by the public key (i.e., scalars multiply the base point of the curve). Witness generation follows the same algorithm but does not include corresponding values. Validation is simple; if the product of the witness and the value is equal to the accumulated value, it is necessary to check for equality.


### 4.3.2. Accumulator Based on t-SDH Assumption

Nguyen [22] proposed a t-bound accumulator. The cryptographic accumulator uses a group G of prime number p generated by g and has bilinear maps e:G×G⟶GT. Here, pkacc=g,gs,gs2,…,gst,u and skacc=s.  The accumulator accx of set X=x1,x2,…,xn∈Zp (n≤t) is defined as accx⟵gu∏x∈Xx+s, and the membership witness witxi⟵gu∏x∈X\xix+s is calculated, where u⟵RZp∗. Then, check whether accX contains the value xi by verifying whether eaccx,g=egxigs,witxi is true or not. The scheme allows the public evaluation of cryptographic accumulators; that is, ghs is obtained by extending polynomial hx=∏x∈Xx+s∈ZpX and by evaluating it in G through pkacc. The public calculation of the witnesses of xi also works on set X/xi. Furthermore, these witnesses can be updated at a constant time without knowing the secret key (see [22]).Nguyen’s scheme is extended by nonmembership witnesses, and the random valueu is eliminated [31, 32]. Previous work also showed how to publicly update nonmembership witnesses within a fixed period of time. Note that these adjustments can also be applied to the latter [31]. The calculation of nonmembership witnesses with value yj∉X makes use of the following facts: hx=∏x∈Xx+X is divided by the polynomial division remainder of yj+X. Such witnesses take the form of a,b=ghs−d/yi+s,d) and may be validated by eaccx,g?=ea,gyi,gseg,gs).


## 4.3.1. t-SDH Assumption

Given a tuplet = (p, G, P), where p is prime, G is a cyclic group generated by P and a tuple in the form of value (P, sP, … stP) in Z/pZ, wheres∈Z/pZ0 [8]. For any probabilistic polynomial-time algorithm A, the following probabilities can be negligible:(13)Pr=AtP,sP…,stP=c,1s+cPΛc∈ZpZ.Tartary et al. [28] made requirements for the conflict resistance performance of the scheme, thus refuting previous claims against cryptographic accumulators. Attack is based on improperly defined security models in which adversaries have access to functions f and g. The proposed patch includes providing compound functions g (f(.)) to the adversary instead of providing functions f and g, respectively. However, the patches proposed by the authors cannot prevent other types of attacks and have proved the scheme to be unsafe. Camenisch et al. [25] proposed another cryptographic accumulator based on dynamic pairing, which provides a more efficient witness update algorithm.Fazio and Nicolosi [7] pointed out in their investigation of the cryptographic accumulator that the original structure makes the time to update the witness after m changes the cryptographic accumulator proportional to m. They raised the question of whether batch updates are possible, that is, whether it is possible to build a cryptographic accumulator where the time to update the witness is independent of the number of changes to the cryptographic accumulator set. Wang et al. [29] designed a cryptographic accumulator with batch processing update and then made improvements to solve the above problems. The scheme is based on the Paillier cipher system and is proven to be secure under a new assumption called the extended strong RSA assumption, which is a variant of the strong RSA assumption with modulus N2. However, contrary to this claim, Camacho and Hevia [30] have shown evidence of an attack and further demonstrated that the time to update the witness in the worst case must be at least Ωm. Therefore, this provides impossible results on a cryptographic accumulator with batch update capabilities.Previous works have produced only membership witnesses, but, in some cases, nonmembership witnesses may be unavoidable. The authors present a dynamic accumulator that supports both membership and nonmembership short witnesses, which they call the universal accumulator. The initial value of the cryptographic accumulator must be public so that nonmembership witnesses can be verified. This construct is based on the RSA function, so only prime numbers are allowed to accumulate.Karlof et al. [23] used elliptic curves to construct cryptographic accumulators. To add up the values (scalars), multiply them by the public key (i.e., scalars multiply the base point of the curve). Witness generation follows the same algorithm but does not include corresponding values. Validation is simple; if the product of the witness and the value is equal to the accumulated value, it is necessary to check for equality.


## 4.3.2. Accumulator Based on t-SDH Assumption

Nguyen [22] proposed a t-bound accumulator. The cryptographic accumulator uses a group G of prime number p generated by g and has bilinear maps e:G×G⟶GT. Here, pkacc=g,gs,gs2,…,gst,u and skacc=s.  The accumulator accx of set X=x1,x2,…,xn∈Zp (n≤t) is defined as accx⟵gu∏x∈Xx+s, and the membership witness witxi⟵gu∏x∈X\xix+s is calculated, where u⟵RZp∗. Then, check whether accX contains the value xi by verifying whether eaccx,g=egxigs,witxi is true or not. The scheme allows the public evaluation of cryptographic accumulators; that is, ghs is obtained by extending polynomial hx=∏x∈Xx+s∈ZpX and by evaluating it in G through pkacc. The public calculation of the witnesses of xi also works on set X/xi. Furthermore, these witnesses can be updated at a constant time without knowing the secret key (see [22]).Nguyen’s scheme is extended by nonmembership witnesses, and the random valueu is eliminated [31, 32]. Previous work also showed how to publicly update nonmembership witnesses within a fixed period of time. Note that these adjustments can also be applied to the latter [31]. The calculation of nonmembership witnesses with value yj∉X makes use of the following facts: hx=∏x∈Xx+X is divided by the polynomial division remainder of yj+X. Such witnesses take the form of a,b=ghs−d/yi+s,d) and may be validated by eaccx,g?=ea,gyi,gseg,gs).


## 4.4. Accumulator Based on t-DHE Assumption

Diffie–Hellman Exponent (DHE) Assumption. The t-DHE problem in a group G of prime order q is defined as follows: Let gi=gγi, γ⟵RZq. On input {g, g1, g2, …, gt, gt+2, …, g2t} ∈G2t, output gt+1.The t-DHE assumption states that this problem is hard to solve.Camenisch et al. [25] gave a scheme of t-bound accumulator based on t-DHE assumption, like the cryptographic accumulator in t-SDH settings, which uses a group G of prime number p generated by g and has bilinear mapping e: G×G⟶GT. Besides, it needs a signature scheme with corresponding key pairs sksig,pksig. Here, skacc=sksig, public key is pkacc=g1,…,gt,gt+2,…,g2t,z,pksig=gγ1,…,gγt,gγt+2,…,gγ2t,eg,gγt+1,pksig, andγR⟵Zp∗. Xx1,…,xm can be accumulated by calculating accX⟵∏i=1mgt+1−i and signing gi with xi using sksig, where m≤t, thus assigning the value of xi to gi. The witness witxj of xj∈X is accX⟵∏i=1,i≠jmgt+1−i+j. The membership of xj can be verified by checking whether egj,accX=z⋅eg,witxj is valid and verifying the signatures of gj and xj under pksig.This scheme allows public updates for witnesses and cryptographic accumulators to be deleted, as this requires onlypkacc. However, if the value xi is to be added to the cryptographic accumulator, a secret signature key skacc is required to create signatures on gi and xi to link the value xi to this parameter. Therefore, the public addition of the cryptographic accumulator requires that a signature be included for each potential value to be stored in the public parameter. Obviously, this seems impractical except for the small accumulative domain.


## 5. Cryptographic Accumulator Schemes in the Hidden Order Group and Known Order Group

Since the introduction of cryptographic accumulator, many cryptographic accumulator schemes with different characteristics have been proposed. Basically, the main work is to construct schemes in hidden order group and known order group [33].


### 5.1. Hidden Order Group

The original RSA-based schemes have been developed by Baric, which enhance the original concept of collision-free safety. Sander [21] suggested using unknown decomposed RSA modules to construct trapdoor-free accumulators. Camenisch extended the previous scheme to have the ability to dynamically add/delete values to the cryptographic accumulator, which constitutes the first dynamic accumulator scheme. Their plan also supports public updates of existing witnesses, that is, updates without knowing any trapdoor. After that, support for nonmembership witnesses was added, so a universal dynamic accumulator was obtained. They also proposed an optimization scheme to update the documents of nonmembership witnesses more effectively but later found shortcomings [34, 35]. Lipmaa [36] generalized the RSA accumulator to a module over a Euclidean ring. In all the above schemes, the accumulative domain is limited to primes to ensure that there is no conflict. Tsudik and Xu [37] proposed a variant, which allows the accumulation of semiprimes. Assuming that the semiprime used is difficult to decompose and its decomposition is unknown to the public, a collision-free accumulator is obtained. In addition, a cryptographic accumulator scheme is proposed, which allows arbitrary integers to be accumulated and supports batch updates of witnesses. However, the scheme was eventually broken.


### 5.2. Known Order Group

Nguyen proposed a dynamic accumulator scheme, which is suitable for paired-friendly groups with primep. It is secure under the t-SDH assumption and allows up to t values to be accumulated from domain Zp. Later, Damgard, Triandopoulos, and Au et al. extended the scheme of Nguyen with general functions. Recently, Acar and Nguyen [38] removed the upper limit t for the number of elements accumulated by the t-SDH accumulator. To do this, they used a set of cryptographic accumulators, each of which contained a subset of the entire set to be accumulated. Camenisch et al. introduced another cryptographic accumulator scheme for pairing-friendly prime arrays. It supports public updates of witnesses and witnesses, and its security depends on the t-DHE assumption.Table5 shows the development of cryptographic accumulator schemes.Table 5
Cryptographic accumulator schemes.
Known order group2005 [22]A dynamic accumulator scheme is proposed, which is suitable for paired-friendly groups with primep.It is secure under the t-SDH assumption and allows up to t values to be accumulated from the domain.2008 [32]Extended 2005 scheme with general functions.Hidden order groupThe accumulative domain is limited to primes1997 [5]Improved the original RSA scheme in 1993 and strengthened the original concept of collision-free safety.1999 [21]It is recommended to use unknown decomposed RSA modules to construct trapdoor-free accumulators.2002 [2]The scheme in 1997 is extended to have the ability to dynamically add/delete values to the cryptographic accumulator, and the first dynamic accumulator is constructed.2007 [24]In 2002, support for nonmembership witnesses was increased, so a universal dynamic accumulator was obtained, and an optimization scheme was proposed to update the documents of nonmembership witnesses more effectively.2012 [34]The RSA accumulator is broadly defined as a module over a Euclidean ring.The accumulative domain is limited to semiprimes2003 [37]It is allowed to accumulate semiprimes.2007 [29]The cryptographic accumulator scheme allows arbitrary integers to be accumulated and supports batch updates of witnesses.2019 [39]Dynamic accumulator based on hash greatly reduces storage space.2011 [38]The upper limitt for accumulating elements of the t-SDH accumulator is canceled.


## 5.1. Hidden Order Group

The original RSA-based schemes have been developed by Baric, which enhance the original concept of collision-free safety. Sander [21] suggested using unknown decomposed RSA modules to construct trapdoor-free accumulators. Camenisch extended the previous scheme to have the ability to dynamically add/delete values to the cryptographic accumulator, which constitutes the first dynamic accumulator scheme. Their plan also supports public updates of existing witnesses, that is, updates without knowing any trapdoor. After that, support for nonmembership witnesses was added, so a universal dynamic accumulator was obtained. They also proposed an optimization scheme to update the documents of nonmembership witnesses more effectively but later found shortcomings [34, 35]. Lipmaa [36] generalized the RSA accumulator to a module over a Euclidean ring. In all the above schemes, the accumulative domain is limited to primes to ensure that there is no conflict. Tsudik and Xu [37] proposed a variant, which allows the accumulation of semiprimes. Assuming that the semiprime used is difficult to decompose and its decomposition is unknown to the public, a collision-free accumulator is obtained. In addition, a cryptographic accumulator scheme is proposed, which allows arbitrary integers to be accumulated and supports batch updates of witnesses. However, the scheme was eventually broken.


## 5.2. Known Order Group

Nguyen proposed a dynamic accumulator scheme, which is suitable for paired-friendly groups with primep. It is secure under the t-SDH assumption and allows up to t values to be accumulated from domain Zp. Later, Damgard, Triandopoulos, and Au et al. extended the scheme of Nguyen with general functions. Recently, Acar and Nguyen [38] removed the upper limit t for the number of elements accumulated by the t-SDH accumulator. To do this, they used a set of cryptographic accumulators, each of which contained a subset of the entire set to be accumulated. Camenisch et al. introduced another cryptographic accumulator scheme for pairing-friendly prime arrays. It supports public updates of witnesses and witnesses, and its security depends on the t-DHE assumption.Table5 shows the development of cryptographic accumulator schemes.Table 5
Cryptographic accumulator schemes.
Known order group2005 [22]A dynamic accumulator scheme is proposed, which is suitable for paired-friendly groups with primep.It is secure under the t-SDH assumption and allows up to t values to be accumulated from the domain.2008 [32]Extended 2005 scheme with general functions.Hidden order groupThe accumulative domain is limited to primes1997 [5]Improved the original RSA scheme in 1993 and strengthened the original concept of collision-free safety.1999 [21]It is recommended to use unknown decomposed RSA modules to construct trapdoor-free accumulators.2002 [2]The scheme in 1997 is extended to have the ability to dynamically add/delete values to the cryptographic accumulator, and the first dynamic accumulator is constructed.2007 [24]In 2002, support for nonmembership witnesses was increased, so a universal dynamic accumulator was obtained, and an optimization scheme was proposed to update the documents of nonmembership witnesses more effectively.2012 [34]The RSA accumulator is broadly defined as a module over a Euclidean ring.The accumulative domain is limited to semiprimes2003 [37]It is allowed to accumulate semiprimes.2007 [29]The cryptographic accumulator scheme allows arbitrary integers to be accumulated and supports batch updates of witnesses.2019 [39]Dynamic accumulator based on hash greatly reduces storage space.2011 [38]The upper limitt for accumulating elements of the t-SDH accumulator is canceled.


## 6. Cryptographic Accumulator Applications

### 6.1. Application of the Cryptographic Accumulator in Digital Signature

#### 6.1.1. Ring Signature

In anonymous authentication on trusted platform, the length of ring signature is positively related to the number of ring members, while large members lead to low efficiency. Therefore, Xu et al. [40] proposed a ring signature anonymous authentication method based on the one-way accumulator and constructed its solution in detail. In the signature phase, the length of the ring is determined by a one-way accumulator, which accumulates the information of all members so that the ring is not too large for a considerable number of members. During the verification period, the efficiency is improved, and the hash computing time, encryption computing time, and decryption computing time are reduced. Compared with the typical ring signature, it is shown that the new solution has lower time complexity and space complexity. At the same time, the new solution ensures anonymity and validity, which not only makes up for the weakness of traditional ring signature but also has high efficiency under the premise of security.


#### 6.1.2. Group Signature

Based on the knowledge of an accumulative composite dynamic accumulator and an effective protocol to prove that the factorization of a submitted value develops a novel, efficient, and provably secure group signature scheme [37], it allows authorization and ownership proof at the same time as factorization based on cumulative synthesis. It enables a group member to perform lightweight authorization proof so that the complexity of proof and verification is independent of the number of current or all deleted members. Using a dynamic accumulator to facilitate authorization, it is required that the group manager propagate certain information such as the value deleted from the cryptographic accumulator whenever a member (or group of members) joins or leaves the group.


### 6.2. Encrypted Search

The dynamic accumulator is introduced into the encrypted search scheme [41, 42], and the existing search scheme of decentralized storage based on block chain is improved. The new scheme takes advantage of the efficient verifiability of the witness in the dynamic accumulator and the dynamic addition and deletion of elements in the accumulated value and takes into account both efficiency and flexibility. In the encryption search scheme based on CCS’14 Hahn in [43], a dynamic accumulator is introduced and improved for the decentralized storage application scenario based on blockchain.


### 6.3. Revoking Anonymous Credentials

The dynamic accumulator can be used to revoke normal credentials (and certificates): First, add a unique value to each credential. Then, the accumulator value of the unique value of all valid credentials is truly published [44]. Now, users can convince the verifier that the credential is still valid by providing a witness for the unique value contained in their credential. Therefore, to check the credential, the verifier must check the publisher’s signature to obtain the current accumulator value and use the witness provided by the user to verify that the unique value contained in the credential is included in the accumulator value.For anonymous credentials, the same method can be used. However, the witnesses and values contained in the cryptographic accumulator can no longer be disclosed to the validator because this completely endangers anonymity. Instead, the user can apply zero-knowledge proof to convince the verifier that the values contained in its credentials are also included in the cryptographic accumulator. Therefore, if a valid protocol is found to prove that the values contained in the commitment are also included in the certificate, any anonymous certificate scheme can be effectively revoked.


### 6.4. Cryptographic Accumulator in Vector Commitment

Catalano and Fiore [45] proposed a black box construction of cryptographic accumulator based on vector commitment. Vector commitment allows concise commitment C to be formed for vector X=x1,…,xn. Here, it is not computationally feasible to open position i of C to a value xi′ different from that of xi. The accumulative domain in the black box construction is set D=1,…,t. The cryptographic accumulator is modeled as a commitment to a binary vector of length t; that is, each bit i represents the existence or nonexistence of element i∈D in the cryptographic accumulator. Then, the (non)membership of value i can be proved by opening position i that is committed to 1 or 0, respectively.


### 6.5. Other Applications

The applications of the cryptographic accumulator are shown in Figure1.Figure 1
Cryptographic accumulator applications.Cryptographic accumulators can be applied to membership testing, distributed signatures, responsible certificate management, and authenticated dictionaries and can also be used as editable, sanitary processing [46, 47], homomorphic signatures [48, 49], and privacy protection data outsourcing building blocks as for authenticated data structures [50, 51]. In addition, the cryptographic accumulator scheme can be used to prove the zero knowledge of (nonmembership) witnesses [52, 53], and undisclosed values are now widely used to revoke group signatures and anonymous credentials [54, 55]. Recently, cryptographic accumulators are also used in Zerocoin [56, 57], and Zerocoin is an anonymous extension of bitcoin cryptocurrencies. Therefore, the cryptographic accumulator can be applied to many aspects, and readers can understand the specific applications of the cryptographic accumulator in these aspects by consulting the above literature.


## 6.1. Application of the Cryptographic Accumulator in Digital Signature

### 6.1.1. Ring Signature

In anonymous authentication on trusted platform, the length of ring signature is positively related to the number of ring members, while large members lead to low efficiency. Therefore, Xu et al. [40] proposed a ring signature anonymous authentication method based on the one-way accumulator and constructed its solution in detail. In the signature phase, the length of the ring is determined by a one-way accumulator, which accumulates the information of all members so that the ring is not too large for a considerable number of members. During the verification period, the efficiency is improved, and the hash computing time, encryption computing time, and decryption computing time are reduced. Compared with the typical ring signature, it is shown that the new solution has lower time complexity and space complexity. At the same time, the new solution ensures anonymity and validity, which not only makes up for the weakness of traditional ring signature but also has high efficiency under the premise of security.


### 6.1.2. Group Signature

Based on the knowledge of an accumulative composite dynamic accumulator and an effective protocol to prove that the factorization of a submitted value develops a novel, efficient, and provably secure group signature scheme [37], it allows authorization and ownership proof at the same time as factorization based on cumulative synthesis. It enables a group member to perform lightweight authorization proof so that the complexity of proof and verification is independent of the number of current or all deleted members. Using a dynamic accumulator to facilitate authorization, it is required that the group manager propagate certain information such as the value deleted from the cryptographic accumulator whenever a member (or group of members) joins or leaves the group.


## 6.1.1. Ring Signature

In anonymous authentication on trusted platform, the length of ring signature is positively related to the number of ring members, while large members lead to low efficiency. Therefore, Xu et al. [40] proposed a ring signature anonymous authentication method based on the one-way accumulator and constructed its solution in detail. In the signature phase, the length of the ring is determined by a one-way accumulator, which accumulates the information of all members so that the ring is not too large for a considerable number of members. During the verification period, the efficiency is improved, and the hash computing time, encryption computing time, and decryption computing time are reduced. Compared with the typical ring signature, it is shown that the new solution has lower time complexity and space complexity. At the same time, the new solution ensures anonymity and validity, which not only makes up for the weakness of traditional ring signature but also has high efficiency under the premise of security.


## 6.1.2. Group Signature

Based on the knowledge of an accumulative composite dynamic accumulator and an effective protocol to prove that the factorization of a submitted value develops a novel, efficient, and provably secure group signature scheme [37], it allows authorization and ownership proof at the same time as factorization based on cumulative synthesis. It enables a group member to perform lightweight authorization proof so that the complexity of proof and verification is independent of the number of current or all deleted members. Using a dynamic accumulator to facilitate authorization, it is required that the group manager propagate certain information such as the value deleted from the cryptographic accumulator whenever a member (or group of members) joins or leaves the group.


## 6.2. Encrypted Search

The dynamic accumulator is introduced into the encrypted search scheme [41, 42], and the existing search scheme of decentralized storage based on block chain is improved. The new scheme takes advantage of the efficient verifiability of the witness in the dynamic accumulator and the dynamic addition and deletion of elements in the accumulated value and takes into account both efficiency and flexibility. In the encryption search scheme based on CCS’14 Hahn in [43], a dynamic accumulator is introduced and improved for the decentralized storage application scenario based on blockchain.


## 6.3. Revoking Anonymous Credentials

The dynamic accumulator can be used to revoke normal credentials (and certificates): First, add a unique value to each credential. Then, the accumulator value of the unique value of all valid credentials is truly published [44]. Now, users can convince the verifier that the credential is still valid by providing a witness for the unique value contained in their credential. Therefore, to check the credential, the verifier must check the publisher’s signature to obtain the current accumulator value and use the witness provided by the user to verify that the unique value contained in the credential is included in the accumulator value.For anonymous credentials, the same method can be used. However, the witnesses and values contained in the cryptographic accumulator can no longer be disclosed to the validator because this completely endangers anonymity. Instead, the user can apply zero-knowledge proof to convince the verifier that the values contained in its credentials are also included in the cryptographic accumulator. Therefore, if a valid protocol is found to prove that the values contained in the commitment are also included in the certificate, any anonymous certificate scheme can be effectively revoked.


## 6.4. Cryptographic Accumulator in Vector Commitment

Catalano and Fiore [45] proposed a black box construction of cryptographic accumulator based on vector commitment. Vector commitment allows concise commitment C to be formed for vector X=x1,…,xn. Here, it is not computationally feasible to open position i of C to a value xi′ different from that of xi. The accumulative domain in the black box construction is set D=1,…,t. The cryptographic accumulator is modeled as a commitment to a binary vector of length t; that is, each bit i represents the existence or nonexistence of element i∈D in the cryptographic accumulator. Then, the (non)membership of value i can be proved by opening position i that is committed to 1 or 0, respectively.


## 6.5. Other Applications

The applications of the cryptographic accumulator are shown in Figure1.Figure 1
Cryptographic accumulator applications.Cryptographic accumulators can be applied to membership testing, distributed signatures, responsible certificate management, and authenticated dictionaries and can also be used as editable, sanitary processing [46, 47], homomorphic signatures [48, 49], and privacy protection data outsourcing building blocks as for authenticated data structures [50, 51]. In addition, the cryptographic accumulator scheme can be used to prove the zero knowledge of (nonmembership) witnesses [52, 53], and undisclosed values are now widely used to revoke group signatures and anonymous credentials [54, 55]. Recently, cryptographic accumulators are also used in Zerocoin [56, 57], and Zerocoin is an anonymous extension of bitcoin cryptocurrencies. Therefore, the cryptographic accumulator can be applied to many aspects, and readers can understand the specific applications of the cryptographic accumulator in these aspects by consulting the above literature.


## 7. Conclusion

Cryptographic accumulator is a basic and important tool in the field of cryptography, which has been widely used in many aspects. This paper firstly introduces the types of cryptographic accumulators. Secondly, in the asymmetric accumulators, three different cryptographic accumulators schemes are classified through three security assumptions. Thirdly, several cryptographic accumulators based on security assumptions are introduced. Fourthly, this paper presents the cryptographic accumulator scheme under different characteristics. Finally the applications of cryptographic accumulators in different aspects are summarized. With the rapid development of big data security and blockchain, cryptographic accumulators are used more and more widely, and there is still much development space in the future.



---

*Source: 5429195-2022-03-07.xml*