Venue
LH-101
Speaker
Dr. Mahabir Prasad Jhanwar
Affiliation
University of Calgary, Canada
Title
Cryptographic Accumulators using Lattices
Abstract: Accumulators are cryptographic authentication primitives for verifying set-membership relations. Given a set X of elements, an accumulator can be used to compute an accumulation value, a short secure description Acc(X) of X, subject to which there exists short witness for any element in X that has been "accumulated" to Acc(X). Each element specific witness can be used to provide an efficient cryptographic proof that the corresponding element is a member of X. The existing constructions rely on either strong-RSA assumption (subsequently, on factoring) or q-strong Diffie-Hellman assumption.
We provide the first accumulator scheme based on lattices. The security of our scheme is based on the "small integer solution (SIS)" problem, which is known to be as hard as approximating certain worst-case problems on lattices to within small approximating factors. Our lattice-based construction offers the hope of withstanding quantum computers, against which both discrete-log and factoring-based approaches are known to be utterly defenseless.