Welcome to the resource topic for 2020/737
Title:
A non-PCP Approach to Succinct Quantum-Safe Zero-Knowledge
Authors: Jonathan Bootle, Vadim Lyubashevsky, Ngoc Khanh Nguyen, Gregor Seiler
Abstract:Today’s most compact zero-knowledge arguments are based on the hardness of the discrete logarithm problem and related classical assumptions. If one is interested in quantum-safe solutions, then all of the known techniques stem from the PCP-based framework of Kilian (STOC 92) which can be instantiated based on the hardness of any collision-resistant hash function. Both approaches produce asymptotically logarithmic sized arguments but, by exploiting extra algebraic structure, the discrete logarithm arguments are a few orders of magnitude more compact in practice than the generic constructions. In this work, we present the first (poly)-logarithmic, potentially post-quantum zero-knowledge arguments that deviate from the PCP approach. At the core of succinct zero-knowledge proofs are succinct commitment schemes (in which the commitment and the opening proof are sub-linear in the message size), and we propose two such constructions based on the hardness of the (Ring)-Short Integer Solution (Ring-SIS) problem, each having certain trade-offs. For commitments to N secret values, the communication complexity of our first scheme is \tilde{O}(N^{1/c}) for any positive integer c, and O(\log^2 N) for the second. Both of these are a significant theoretical improvement over the previously best lattice construction by Bootle et al. (CRYPTO 2018) which gave O(\sqrt{N})-sized proofs.
ePrint: https://eprint.iacr.org/2020/737
Talk: https://www.youtube.com/watch?v=HX2tnynXK9Q
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .