Accumulator (cryptography): Difference between revisions

Content deleted Content added

Inline

Revision as of 04:05, 8 February 2021

In cryptography, an accumulator is a one way membership hash function. It allows users to certify that potential candidates are a member of a certain set without revealing the individual members of the set. This concept was formally introduced by J. Benaloh and M. de Mare in 1993.^[1]

Formal definition

Benaloh and de Mare define a one-way hash function as a family of functions $h_{\ell }:X_{\ell }\times Y_{\ell }\to Z_{\ell }$ which satisfy the following three properties:^[1]^[2]

For all $\ell \in \mathbb {Z} ,x\in X_{\ell },y\in Y_{\ell }$ , one can compute $h_{\ell }(x,y)$ in time ${\text{poly}}(\ell ,|x|,|y|)$ . (Here the "poly" symbol refers to an unspecified, but fixed, polynomial.)
No probabilistic polynomial-time algorithm will, for sufficiently large $\ell$ , map the inputs $\ell \in \mathbb {Z} ,(x,y)\in X_{\ell }\times Y_{\ell },y'\in Y_{\ell }$ , find a value $x'\in X_{\ell }$ such that $h_{\ell }(x,y)=h_{\ell }(x',y')$ with more than negligible probability.
For all $\ell \in \mathbb {Z} ,x\in X_{\ell },y_{1},y_{2}\in Y_{\ell }$ , one has $h(h(x,y_{1}),y_{2})=h(h(x,y_{2}),y_{1})$ . (A function that satisfies this property is called quasi-commutative.)

(With the first two properties, one recovers the normal definition of a cryptographic hash function.)

From such a function, one defines the "accumulated hash" of a set $\{y_{1},\dots ,y_{m}\}$ w.r.t. a value $x$ to be $h(\dots h(h(x,y_{1}),y_{2}),\dots ,y_{m})$ . (This does not depend on the order of elements because $h$ is quasi-commutative.)

Examples

One example is multiplication over large prime numbers. This is a cryptographic accumulator, since it takes superpolynomial time to factor a composite number (at least according to conjecture), but it takes only a small amount of time (polynomial in size) to divide a prime into an integer to check if it is one of the factors and/or to factor it out. New members may be added or subtracted to the set of factors by multiplying or factoring out the number respectively. In this system, two accumulators that have accumulated a single shared prime can have it trivially discovered by calculating their GCD, even without prior knowledge of the prime (which would otherwise require prime factorization of the accumulator to discover).^{[citation needed]}

More practical accumulators use a quasi-commutative hash function, so that the size of the accumulator does not grow with the number of members. For example, Benaloh and de Mare propose a cryptographic accumulator inspired by RSA: the quasi-commutative function $h(x,y):=x^{y}{\pmod {n}}$ for some composite number $n$ . They recommend to choose $n$ to be a rigid integer (i.e. the product of two safe primes).^[1]

David Naccache observed that $e_{n,c}(x,y):=x^{y}c^{y-1}{\pmod {n}}$ is quasi-commutative for all constants $c,n$ , generalizing the previous RSA-inspired cryptographic accumulator. Naccache has also noted that the Dickson polynomials are quasi-commutative in the degree, but it is unknown whether this family of functions is one-way.^[1]

Applications

Haber and Stornetta showed in 1990 that accumulators can be use to timestamp documents through cryptographic chaining. (This concept anticipates the modern notion of a cryptographic blockchain.)^[1]^[3] Benaloh and de Mare proposed an alternative scheme in 1991 based on discretizing time into rounds.^[1]^[4]

Additionally, Benaloh and de Mare showed that accumulators can be used so that a large group of people can recognize each other at a later time. Each person selects a $y$ representing their identity, and the group collectively selects a public accumulator $h$ and a secret $x$ . Then, the group publishes or saves the hash function and the accumulated hash of all the group's identities w.r.t the secret $x$ and public accumulator; simultaneously, each member of the group keeps both its identity value $y$ and the accumulated hash of all the group's identities except that of the member. (If the large group of people do not trust each other, or if the accumulator has a cryptographic trapdoor as in the case of the RSA-inspired accumulator, then they can compute the accumulated hashes by secure multiparty computation.) To verify that a claimed member did indeed belong to the group later, they present their identity and personal accumulated hash; by accumulating the identity of the claimed member and checking it against the accumulated hash of the entire group, anyone can verify a member of the group.^[1]

The concept has received renewed interest recently due to the proposed Zerocoin add on to bitcoin, which employs cryptographic accumulators to eliminate trackable linkage in the bitcoin blockchain, which would make bitcoin anonymous and untraceable, increasing privacy of transactions.^[5]^[6]^[7]

References

^ ^a ^b ^c ^d ^e ^f ^g J. Benaloh and M. de Mare, One-way accumulators: a decentralized alternative to digital signatures, Advances in Cryptology—Eurocrypt’93, LNCS, vol. 765, Springer-Verlag, 1993, pp. 274–285.
^ Fazio, Nelly; Nicolosi, Antonio (2002). "Cryptographic Accumulators: Definitions, Constructions and Applications" (PDF). Archived (PDF) from the original on 3 June 2006. Retrieved 30 January 2021.
^ Haber, Stuart; Stornetta, W. Scott (1991). Menezes, Alfred J.; Vanstone, Scott A. (eds.). "How to Time-Stamp a Digital Document". Advances in Cryptology-CRYPTO’ 90. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer: 437–455. doi:10.1007/3-540-38424-3_32. ISBN 978-3-540-38424-3.
^ Benaloh, J.; de Mare, M. (August 1991). "Efficient Broadcast Time-Stamping". Clarkson University Department of Mathematics and Computer Science. TR 91-1 – via Citeseer.
^ Miers, Ian. Zerocoin: Anonymous Distributed E-Cash from Bitcoin. isi.jhu.edu
^ "A Few Thoughts on Cryptographic Engineering: Zerocoin: making Bitcoin anonymous". Archived from the original on 21 May 2014.. Blog.cryptographyengineering.com (11 April 2013). Retrieved on 20 April 2013.
^ Zerocoin: Anonymous Distributed E-Cash from Bitcoin Archived 8 February 2014 at the Wayback Machine

External links

[:0-1] ^ ^a ^b ^c ^d ^e ^f ^g J. Benaloh and M. de Mare, One-way accumulators: a decentralized alternative to digital signatures, Advances in Cryptology—Eurocrypt’93, LNCS, vol. 765, Springer-Verlag, 1993, pp. 274–285.

[2] Fazio, Nelly; Nicolosi, Antonio (2002). "Cryptographic Accumulators: Definitions, Constructions and Applications" (PDF). Archived (PDF) from the original on 3 June 2006. Retrieved 30 January 2021.

[3] Haber, Stuart; Stornetta, W. Scott (1991). Menezes, Alfred J.; Vanstone, Scott A. (eds.). "How to Time-Stamp a Digital Document". Advances in Cryptology-CRYPTO’ 90. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer: 437–455. doi:10.1007/3-540-38424-3_32. ISBN 978-3-540-38424-3.

[4] Benaloh, J.; de Mare, M. (August 1991). "Efficient Broadcast Time-Stamping". Clarkson University Department of Mathematics and Computer Science. TR 91-1 – via Citeseer.

[5] Miers, Ian. Zerocoin: Anonymous Distributed E-Cash from Bitcoin. isi.jhu.edu

[6] "A Few Thoughts on Cryptographic Engineering: Zerocoin: making Bitcoin anonymous". Archived from the original on 21 May 2014.. Blog.cryptographyengineering.com (11 April 2013). Retrieved on 20 April 2013.

[7] Zerocoin: Anonymous Distributed E-Cash from Bitcoin Archived 8 February 2014 at the Wayback Machine

[1]

[2]

[3]

[4]

[5]

[6]

[7]

@@ Line 1: / Line 1: @@
 {{Use dmy dates|date=May 2014}}
-A cryptographic '''accumulator''' is a [[one way function|one way]] membership function.  It answers a query as to whether a potential candidate is a member of a set without revealing the individual members of the set. The concept was introduced by J. Benaloh and M. de Mare in 1993.<ref name=":0">J. Benaloh and M. de Mare, [https://link.springer.com/content/pdf/10.1007%2F3-540-48285-7_24.pdf One-way accumulators: a decentralized alternative  to digital signatures], Advances in Cryptology—Eurocrypt’93,  LNCS, vol. 765, Springer-Verlag, 1993, pp. 274–285.</ref>
+In [[cryptography]], an '''accumulator''' is a [[one way function|one way]] membership [[hash function]]. It allows users to certify that potential candidates are a member of a certain [[set]] without revealing the individual members of the set. This concept was formally introduced by J. Benaloh and M. de Mare in 1993.<ref name=":0">J. Benaloh and M. de Mare, [https://link.springer.com/content/pdf/10.1007%2F3-540-48285-7_24.pdf One-way accumulators: a decentralized alternative  to digital signatures], Advances in Cryptology—Eurocrypt’93,  LNCS, vol. 765, Springer-Verlag, 1993, pp. 274–285.</ref>
 == Formal definition ==
@@ Line 7: / Line 7: @@
 # For all <math>\ell\in\mathbb{Z}, x\in X_{\ell}, y\in Y_{\ell}</math>, one can compute <math>h_{\ell}(x,y)</math> in time <math>\text{poly}(\ell, |x|, |y|)</math>. (Here the "poly" symbol refers to an unspecified, but fixed, polynomial.)
 # No [[PP (complexity)|probabilistic polynomial-time algorithm]] will, for sufficiently large <math>\ell</math>, map the inputs <math>\ell\in\mathbb{Z}, (x, y)\in X_{\ell}\times Y_{\ell}, y'\in Y_{\ell}</math>, find a value <math>x'\in X_{\ell}</math> such that <math>h_{\ell}(x, y) = h_{\ell}(x', y')</math> with more than negligible probability.
-# For all <math>\ell\in\mathbb{Z}, x\in X_{\ell}, y_1, y_2\in Y_{\ell}</math>, one has <math>h(h(x, y_1), y_2) = h(h(x, y_2), y_1)</math>.
+# For all <math>\ell\in\mathbb{Z}, x\in X_{\ell}, y_1, y_2\in Y_{\ell}</math>, one has <math>h(h(x, y_1), y_2) = h(h(x, y_2), y_1)</math>. (A function that satisfies this property is called ''quasi-commutative''.)
-(With the first two properties, one recovers the normal definition of a [[cryptographic hash function]].)
+(With the first two properties, one recovers the normal definition of a cryptographic hash function.)
+From such a function, one defines the "accumulated hash" of a set <math>\{y_1,\dots, y_m \}</math> w.r.t. a value <math>x</math> to be <math>h(\dots h(h(x, y_1), y_2),\dots, y_m)</math>. (This does not depend on the order of elements because <math>h</math> is quasi-commutative.)
 == Examples ==
-One example is how large [[composite numbers]] accumulate their [[prime factors]], as it's currently impractical to [[integer factorization|factor]] a composite number, but relatively easy to divide a specific prime into another number to see if it is one of the factors and/or to factor it out.  New members may be added or subtracted to the set of factors simply by multiplying or factoring out the number respectively. In this system, two accumulators that have accumulated a single shared prime can have it trivially discovered by calculating their GCD, even without prior knowledge of the prime (which would otherwise require prime factorization of the accumulator to discover). More practical accumulators use a [[Quasi-commutative property#Applied to functions|quasi-commutative]] hash function where the size (number of bits) of the accumulator does not grow with the number of members.
+One example is [[multiplication]] over large [[Prime number|prime numbers]]. This is a cryptographic accumulator, since it takes superpolynomial time to [[integer factorization|factor]] a composite number (at least according to conjecture), but it takes only a small amount of time (polynomial in size) to divide a prime into an integer to check if it is one of the factors and/or to factor it out. New members may be added or subtracted to the set of factors by multiplying or factoring out the number respectively. In this system, two accumulators that have accumulated a single shared prime can have it trivially discovered by calculating their GCD, even without prior knowledge of the prime (which would otherwise require prime factorization of the accumulator to discover).{{Citation needed|date=February 2021}}
+More practical accumulators use a [[Quasi-commutative property#Applied to functions|quasi-commutative]] hash function, so that the size of the accumulator does not grow with the number of members. For example, Benaloh and de Mare propose a cryptographic accumulator inspired by [[RSA (cryptosystem)|RSA]]: the quasi-commutative function <math>h(x, y) := x^y\pmod{n}</math> for some composite number <math>n</math>. They recommend to choose  <math>n</math> to be a ''rigid'' integer (i.e. the product of two [[Safe prime|safe primes]]).<ref name=":0" />
+David Naccache observed that <math>e_{n, c}(x, y) := x^y c^{y - 1} \pmod{n}</math> is quasi-commutative for all constants <math>c, n</math>, generalizing the previous RSA-inspired cryptographic accumulator. Naccache has also noted that the [[Dickson polynomial|Dickson polynomials]] are quasi-commutative in the degree, but it is unknown whether this family of functions is one-way.<ref name=":0" />
 == Applications ==
+Haber and Stornetta showed in 1990 that accumulators can be use to [[timestamp]] documents through cryptographic chaining. (This concept anticipates the modern notion of a cryptographic [[blockchain]].)<ref name=":0" /><ref>{{Cite journal|last=Haber|first=Stuart|last2=Stornetta|first2=W. Scott|date=1991|editor-last=Menezes|editor-first=Alfred J.|editor2-last=Vanstone|editor2-first=Scott A.|title=How to Time-Stamp a Digital Document|url=https://link.springer.com/chapter/10.1007/3-540-38424-3_32|journal=Advances in Cryptology-CRYPTO’ 90|series=Lecture Notes in Computer Science|language=en|location=Berlin, Heidelberg|publisher=Springer|pages=437–455|doi=10.1007/3-540-38424-3_32|isbn=978-3-540-38424-3}}</ref> Benaloh and de Mare proposed an alternative scheme in 1991 based on discretizing time into rounds.<ref name=":0" /><ref>{{Cite journal|last=Benaloh|first=J.|last2=de Mare|first2=M.|date=August 1991|title=Efficient Broadcast Time-Stamping|url=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.38.9199&rep=rep1&type=pdf|journal=Clarkson University Department of Mathematics and Computer Science|volume=TR 91-1|pages=|via=Citeseer}}</ref>
+Additionally, Benaloh and de Mare showed that accumulators can be used so that a large group of people can recognize each other at a later time. Each person selects a <math>y</math> representing their identity, and the group collectively selects a public accumulator <math>h</math> and a secret <math>x</math>. Then, the group publishes or saves the hash function and the accumulated hash of all the group's identities w.r.t the secret <math>x</math> and public accumulator; simultaneously, each member of the group keeps both its identity value <math>y</math> and the accumulated hash of all the group's identities ''except that of the member''. (If the large group of people do not trust each other, or if the accumulator has a cryptographic trapdoor as in the case of the RSA-inspired accumulator, then they can compute the accumulated hashes by [[Secure multi-party computation|secure multiparty computation]].) To verify that a claimed member did indeed belong to the group later, they present their identity and personal accumulated hash; by accumulating the identity of the claimed member and checking it against the accumulated hash of the entire group, anyone can verify a member of the group.<ref name=":0" />
 The concept has received renewed interest recently due to the proposed [[Zerocoin]] add on to [[bitcoin]], which employs cryptographic accumulators to eliminate trackable linkage in the bitcoin blockchain, which would make bitcoin anonymous and untraceable, increasing privacy of transactions.<ref>Miers, Ian. [http://spar.isi.jhu.edu/~mgreen/ZerocoinOakland.pdf Zerocoin: Anonymous Distributed E-Cash from Bitcoin]. isi.jhu.edu</ref><ref>{{cite web|url=http://blog.cryptographyengineering.com/2013/04/zerocoin-making-bitcoin-anonymous.html |title=A Few Thoughts on Cryptographic Engineering: Zerocoin: making Bitcoin anonymous |archiveurl=https://www.webcitation.org/6PjkkIDkx?url=http://blog.cryptographyengineering.com/2013/04/zerocoin-making-bitcoin-anonymous.html |archivedate=21 May 2014 |url-status=dead |df=dmy }}. Blog.cryptographyengineering.com (11 April 2013). Retrieved on 20 April 2013.</ref><ref>[http://research.microsoft.com/apps/video/dl.aspx?id=192058 Zerocoin: Anonymous Distributed E-Cash from Bitcoin] {{webarchive |url=https://web.archive.org/web/20140208140359/http://research.microsoft.com/apps/video/dl.aspx?id=192058 |date=8 February 2014 }}</ref>
@@ Line 25: / Line 35: @@
 ==External links==
-* [http://www.cs.nyu.edu/~fazio/research/publications/accumulators.pdf Cryptographic Accumulators: Definitions,  Constructions and Applications]
+* [http://www.cs.nyu.edu/~fazio/research/publications/accumulators.pdf Cryptographic Accumulators: Definitions, Constructions and Applications]
 * [http://eprint.iacr.org/2009/625.pdf Cryptographic Accumulators for Authenticated Hash Tables.]