Efficient NIZKs and Signatures from Commit-and-Open Protocols in the QROM

Jelle Don, Serge Fehr, Christian Majenz, and Christian Schaffner

Abstract

Commit-and-open Sigma-protocols are a popular class of protocols for constructing non-interactive zero-knowledge arguments and digital-signature schemes via the Fiat-Shamir transformation. Instantiated with hash-based commitments, the resulting non-interactive schemes enjoy tight online-extractability in the random oracle model. Online extractability improves the tightness of security proofs for the resulting digital-signature schemes by avoiding lossy rewinding or forking-lemma based extraction. In this work, we prove tight online extractability in the quantum random oracle model (QROM), showing that the construction supports post-quantum security. First, we consider the default case where committing is done by element-wise hashing. In a second part, we extend our result to Merkle-tree based commitments. Our results yield a significant improvement of the provable post-quantum security of the digital-signature scheme Picnic. Our analysis makes use of a recent framework by Chung et al. for analysing quantum algorithms in the QROM using purely classical reasoning. Therefore, our results can to a large extent be understood and verified without prior knowledge of quantum information science.

Available format(s)
Publication info
Preprint. MINOR revision.
Keywords
QROMcommit-and-openFiat-ShamirNIZKpublic-key cryptographydigital signatures
Contact author(s)
jelle don @ cwi nl
serge fehr @ cwi nl
chmaj @ dtu dk
christian schaffner @ uva nl
History
Short URL
https://ia.cr/2022/270

CC BY

BibTeX

@misc{cryptoeprint:2022/270,
author = {Jelle Don and Serge Fehr and Christian Majenz and Christian Schaffner},
title = {Efficient NIZKs and Signatures from Commit-and-Open Protocols in the QROM},
howpublished = {Cryptology ePrint Archive, Paper 2022/270},
year = {2022},
note = {\url{https://eprint.iacr.org/2022/270}},
url = {https://eprint.iacr.org/2022/270}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.