Zero-Knowledge Arguments for Lattice-Based Accumulators: Logarithmic-Size Ring Signatures and Group Signatures Without Trapdoors

Abstract : An accumulator is a function that hashes a set of inputs into a short, constant-size string while preserving the ability to efficiently prove the inclusion of a specific input element in the hashed set. It has proved useful in the design of numerous privacy-enhancing protocols, in order to handle revocation or simply prove set membership. In the lattice setting, currently known instantiations of the primitive are based on Merkle trees, which do not interact well with zero-knowledge proofs. In order to efficiently prove the membership of some element in a zero-knowledge manner, the prover has to demonstrate knowledge of a hash chain without revealing it, which is not known to be efficiently possible under well-studied hardness assumptions. In this paper, we provide an efficient method of proving such statements using involved extensions of Stern's protocol. Under the Small Integer Solution assumption, we provide zero-knowledge arguments showing possession of a hash chain. As an application, we describe new lattice-based group and ring signatures in the random oracle model. In particular, we obtain: (i) The first lattice-based ring signatures with logarithmic size in the cardinality of the ring; (ii) The first lattice-based group signature that does not require any GPV trapdoor and thus allows for a much more efficient choice of parameters.
Type de document :
Communication dans un congrès
Eurocrypt 2016, May 2016, Vienne, Austria. Springer, 9666, 2016, Eurocrypt 2016. 〈http://ist.ac.at/eurocrypt2016/〉. 〈10.1007/978-3-662-49896-5_1〉
Liste complète des métadonnées

Littérature citée [69 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01314642
Contributeur : Benoit Libert <>
Soumis le : mercredi 11 mai 2016 - 16:46:46
Dernière modification le : vendredi 20 avril 2018 - 15:44:26
Document(s) archivé(s) le : mercredi 16 novembre 2016 - 01:47:32

Fichier

LLNW-16.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Benoît Libert, San Ling, Khoa Nguyen, Huaxiong Wang. Zero-Knowledge Arguments for Lattice-Based Accumulators: Logarithmic-Size Ring Signatures and Group Signatures Without Trapdoors. Eurocrypt 2016, May 2016, Vienne, Austria. Springer, 9666, 2016, Eurocrypt 2016. 〈http://ist.ac.at/eurocrypt2016/〉. 〈10.1007/978-3-662-49896-5_1〉. 〈hal-01314642〉

Partager

Métriques

Consultations de la notice

277

Téléchargements de fichiers

414