Paper 2017/279

Post-Quantum Zero-Knowledge and Signatures from Symmetric-Key Primitives

Melissa Chase, David Derler, Steven Goldfeder, Claudio Orlandi, Sebastian Ramacher, Christian Rechberger, Daniel Slamanig, and Greg Zaverucha

Abstract

We propose a new class of post-quantum digital signature schemes that: (a) derive their security entirely from the security of symmetric-key primitives, believed to be quantum-secure, and (b) have extremely small keypairs, and, (c) are highly parameterizable. In our signature constructions, the public key is an image y = f(x) of a one-way function f and secret key x. A signature is a non-interactive zero-knowledge proof of x, that incorporates a message to be signed. For this proof, we leverage recent progress of Giacomelli et al. (USENIX'16) in constructing an efficient Sigma-protocol for statements over general circuits. We improve this Sigma-protocol to reduce proof sizes by a factor of two, at no additional computational cost. While this is of independent interest as it yields more compact proofs for any circuit, it also decreases our signature sizes. We consider two possibilities to make the proof non-interactive: the Fiat-Shamir transform and Unruh's transform (EUROCRYPT'12, '15,'16). The former has smaller signatures, while the latter has a security analysis in the quantum-accessible random oracle model. By customizing Unruh's transform to our application, the overhead is reduced to 1.6x when compared to the Fiat-Shamir transform, which does not have a rigorous post-quantum security analysis. We implement and benchmark both approaches and explore the possible choice of f, taking advantage of the recent trend to strive for practical symmetric ciphers with a particularly low number of multiplications and end up using LowMC (EUROCRYPT'15).

Note: The performance figures presented here are somewhat outdated. For up to date figures see https://microsoft.github.io/Picnic/. This paper is a merge of ePrint:2016/1085 and ePrint:2016/1110.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision. ACM CCS'17
DOI
10.1145/3133956.3133997
Keywords
post-quantum cryptographyzero-knowledgesignaturesblock cipherFiat-ShamirUnruhimplementation
Contact author(s)
sebastian ramacher @ iaik tugraz at
History
2018-03-22: revised
2017-03-30: received
See all versions
Short URL
https://ia.cr/2017/279
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/279,
      author = {Melissa Chase and David Derler and Steven Goldfeder and Claudio Orlandi and Sebastian Ramacher and Christian Rechberger and Daniel Slamanig and Greg Zaverucha},
      title = {Post-Quantum Zero-Knowledge and Signatures from Symmetric-Key Primitives},
      howpublished = {Cryptology ePrint Archive, Paper 2017/279},
      year = {2017},
      doi = {10.1145/3133956.3133997},
      note = {\url{https://eprint.iacr.org/2017/279}},
      url = {https://eprint.iacr.org/2017/279}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.