zbMATH — the first resource for mathematics

Zero-knowledge arguments for lattice-based accumulators: logarithmic-size ring signatures and group signatures without trapdoors. (English) Zbl 1369.94552
Fischlin, Marc (ed.) et al., Advances in cryptology – EUROCRYPT 2016. 35th annual international conference on the theory and applications of cryptographic techniques, Vienna, Austria, May 8–12, 2016. Proceedings. Part II. Berlin: Springer (ISBN 978-3-662-49895-8/pbk; 978-3-662-49896-5/ebook). Lecture Notes in Computer Science 9666, 1-31 (2016).
Summary: 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.
For the entire collection see [Zbl 1337.94002].

94A60 Cryptography
Full Text: DOI