Abstract: An accumulator is a succinct aggregate of a set of values where it is possible to issue short membership proofs for each accumulated value. A party in possession of such a membership proof can then demonstrate that the value is included in the set. Accumulators have proven to be a very strong mathematical tool with applications in a variety of privacy-preserving technologies. Applications of accumulators include efficient time-stamping, anonymous credential systems and group signatures, ring signatures, redactable signatures, sanitizable signatures, P-homomorphic signatures, and Zerocoin (an extension of the cryptographic currency Bitcoin), etc.

In this talk, we present a lattice-based accumulator scheme that issues compact membership proofs. The security of our scheme is based on the hardness of the Short Integer Solution problem.

In recent years, there has been rapid development in the use of lattices for constructing rich cryptographic schemes (these include digital signatures, identity-based encryption, non-interactive zero-knowledge, and even a fully homomorphic cryptosystem.  Among other reasons, this is because such schemes have yet to be broken by quantum algorithms, and their security can be based solely on worst-case computational assumptions.

This is a joint work with Rei-Safavi Naini.