Zero-knowledge arguments for lattice-based accumulators: Logarithmic-size ring signatures and group signatures without trapdoors

Benoît Libert*, San Ling, Khoa Nguyen, Huaxiong Wang

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingChapterpeer-review

93 Citations (Scopus)

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 zeroknowledge 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 latticebased 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.

Original languageEnglish
Title of host publicationAdvances in Cryptology - EUROCRYPT 2016
Subtitle of host publication35th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Vienna, Austria, May 8-12, 2016, Proceedings, Part II
EditorsMarc Fischlin, Jean-Sébastien Coron
Place of PublicationBerlin
PublisherSpringer, Springer Nature
Pages1-31
Number of pages31
ISBN (Electronic)9783662498965
ISBN (Print)9783662498958
DOIs
Publication statusPublished - 2016
Externally publishedYes
Event35th Annual International Conference on Theory and Applications of Cryptographic Techniques, EUROCRYPT 2016 - Vienna, Austria
Duration: 8 May 201612 May 2016

Publication series

NameLecture Notes in Computer Science
Volume9666
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other35th Annual International Conference on Theory and Applications of Cryptographic Techniques, EUROCRYPT 2016
CountryAustria
CityVienna
Period8/05/1612/05/16

Fingerprint

Dive into the research topics of 'Zero-knowledge arguments for lattice-based accumulators: Logarithmic-size ring signatures and group signatures without trapdoors'. Together they form a unique fingerprint.

Cite this