Cryptology ePrint Archive: Report 2017/1154

Post-Quantum Zero-Knowledge Proofs for Accumulators with Applications to Ring Signatures from Symmetric-Key Primitives

David Derler and Sebastian Ramacher and Daniel Slamanig

Abstract: In this paper we address the construction of privacy-friendly cryptographic primitives for the post-quantum era and in particular accumulators with zero-knowledge membership proofs and ring signatures. This is an important topic as it helps to protect the privacy of users in online authentication or emerging technologies such as cryptocurrencies. Recently, we have seen first such constructions, mostly based on assumptions related to codes and lattices. We, however, ask whether it is possible to construct such primitives without relying on structured hardness assumptions, but solely based on symmetric-key primitives such as hash functions or block ciphers. This is interesting because the resistance of latter primitives to quantum attacks is quite well understood.

In doing so, we choose a modular approach and firstly construct an accumulator (with one-way domain) that allows to efficiently prove knowledge of (a pre-image of) an accumulated value in zero-knowledge. We, thereby, take care that our construction can be instantiated solely from symmetric-key primitives and that our proofs are of sublinear size. Latter is non trivial to achieve in the symmetric setting due to the absence of algebraic structures which are typically used in other settings to make these efficiency gains. Regarding efficient instantiations of our proof system, we rely on recent results for constructing efficient non-interactive zero-knowledge proofs for general circuits. Based on this building block, we then show how to construct logarithmic size ring signatures solely from symmetric-key primitives. As constructing more advanced primitives only from symmetric-key primitives is a very recent field, we discuss some interesting open problems and future research directions. Finally, we want to stress that our work also indirectly impacts other fields: for the first time it raises the requirement for collision resistant hash functions with particularly low AND count.

Category / Keywords: post-quantum cryptography, privacy-preserving cryptography, provable security, accumulator, zero-knowledge for circuits

Original Publication (with major differences): PQCrypto 2018

Date: received 28 Nov 2017, last revised 10 Apr 2018

Contact author: sebastian ramacher at iaik tugraz at

Available format(s): PDF | BibTeX Citation

Note: This is an extended full version of the PQCrypto'18 paper. It additionally contains a concrete, optimized implementation of the circuit used in the zero-knowledge membership proof for the accumulator, which reduces the initial signature size estimations roughly by a factor of 2.

Version: 20180410:151041 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]