Welcome to the resource topic for 2016/1110
Title:
Efficient Post-Quantum Zero-Knowledge and Signatures
Authors: Steven Goldfeder, Melissa Chase, Greg Zaverucha
Abstract:In this paper, we present a new post-quantum digital signature algorithm that derives its security entirely from assumptions about symmetric-key primitives, which are very well studied and believed to be quantum-secure (with increased parameter sizes). We present our new scheme with a complete post-quantum security analysis, and benchmark results from a prototype implementation. Our construction is an efficient instantiation of the following design: the public key is y=f(x) for preimage-resistant function f, and x is the private key. A signature is a non-interactive zero-knowledge proof of x, that incorporates a message to be signed. Our security analysis uses recent results of Unruh (EUROCRYPT’12,'15,'16) that show how to securely convert an interactive sigma protocol to a non-interactive one in the quantum random oracle model (QROM). The Unruh construction is generic, and does not immediately yield compact proofs. However, when we specialize the construction to our application, we can reduce the size overhead of the QROM-secure construction to 1.6x, when compared to the Fiat-Shamir transform, which does not have a rigorous post-quantum security analysis. Our implementation results compare both instantiations, with multiple choices of f for comparison. Our signature scheme proposal uses the block cipher LowMC for f, as it gives the shortest signatures. In addition to reducing the size of signatures with Unruh’s construction, we also improve the size of proofs in the underlying sigma protocol (of Giacomelli et al., USENIX’16) by a factor of two. This is of independent interest as it yields more compact proofs for arbitrary choices of f in the classical case as well. Further, this reduction in size comes at no additional computational cost.
ePrint: https://eprint.iacr.org/2016/1110
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 .