RSA Accumulator

This is a Kotlin implementation of an RSA accumulator, originally described by Benaloh and de Mar [1]. An accumulator is a cryptographic primitive that generates a succinct digest of elements in a set in a way that allows for proof of membership (called a witness) of an element in the set without revealing other information about the set.

This library implements a dynamic RSA accumulator, meaning the accumulator can be efficiently updated when elements are added and removed from the set [2]. "Efficiently", in this case, means independent of the size of the accumulated set. The method for performing dynamic updates uses auxiliary information about the accumulator, as described by Camenisch and Lysyanskaya [2] and Li et. al. [3].

This library is intended to be used to allow for verifiable observation of state from a blockchain, where the accumulator represents a digest of the entire ledger. It is therefore expected that for every block produced, multiple elements will need to be added and removed from the accumulated set. Because of this, batch updates has also been implemented in this library [4].

Building

The project can be built with:

./gradlew build

To use this library in another project, first publish it to MavenLocal.

./gradlew publishToMavenLocal

If your project uses gradle, include the following in the build.gradle to import the RSA accumulator library as a dependency.

repositories {
    ...
    maven {
        url 'file://Users/allirvin/.m2/repository'
    }
}

dependencies {
    ...
    implementation "res.dlt.accumulator:rsa-accumulator:0.1"

}

Construction of the accumulator

RSA modulus n

The RSA modulus n is a composite of two safe primes p and q. While the original RSA paper [5] and Benaloh and de Mar accumulator paper [1] recommended that n be 200 digits (663 bits), factorizations of an RSA moduli have been found up to 250 digits (829 bits). Therefore, the default modulus size in this library is 309 decimal digits (1024 bits). The primes p and q are 512 bits and p' and q' are 511 bits.

A safe prime is one that fulfils p = 2p' + 1, where p' is an odd prime. To generate these primes, random primes p' and q' of bitlength 511 are created. A probabilistic primality test (Miller-Rabin) is used to check whether 2p' + 1 and 2q' + 1 are primes. As this test is quite expensive, obvious non-primes are filtered by checking that p', q', p and q mod 3 = 2 [6].

The Euler totient function phi(n) is defined as (p - 1)(q - 1).

The elements accumulated are primes that are not equal to p' or q'.

Coding Conventions

This library uses functional programming principles wherever possible. For a detailed overview of the conventions see the Coding Conventions document.

References

• [1] Benaloh, J. and de Mar, M., 1994, One-Way Accumulators: A Decentralized Alternative to Digital Signatures, International Conference on the Theory and Applications of Cryptographic Techniques, vol 765, pp 274-285.
• [2] Camenisch, J. and Lysyanskaya, A., 2002, Dynamic accumulators and application to efficient revocation of anonymous credentials, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol 2442, pp 61-76.
• [3] Li, J., Li, N., Xue, R., 2007, Universal accumulators with efficient nonmembership proofs, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol 4521, pp 253-269.
• [4] Boneh, D., Bunz, B., Fisch, B., 2019, Batching Techniques for Accumulators with Applications to IOPs and Stateless Blockchains, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol 11692, pp 561-586.
• [5] Rivest, R., Shamir, A., Adleman, L., 1978, A Method for Obtaining Digital Signatures and Public-Key Cryptosystems, Communications of the ACM.
• [6] Naccache, D., 2003, Double-Speed Safe Prime Generation, Crypto Eprint Archive.

TODO

• The elements to be accumulated need to be in the set {e in primes; e notequal p', q' and A <= e <= B} where A and B are chosen with arbitrary polynomial dependence on the security parameter k, as long as 2 < A and B < A^2.
• Write some notes on the prime certainty constant used.
• Look into how the batching method proposed by Boneh et al [4] is different from the method proposed by Camenisch and Lysyanskaya [2].
• Include some examples of how to use the accumulator. Most functions are using the state monad so look a little different from normal functions.
  • newInstance
  • add
  • delete
  • createProof
  • verifyProof