2022-10-13
Efficient NIZKs and signatures from commit-and-open protocols in the QROM
Publication
Publication
Commit-and-open Σ -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. [CFHL21] 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.
| Additional Metadata | |
|---|---|
| doi.org/10.1007/978-3-031-15979-4_25 | |
| Lecture Notes in Computer Science | |
| Algebraic Methods for Stronger Crypto , Taming Quantum Adversaries | |
| , | |
| Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
|
Don, J., Fehr, S., Majenz, C., & Schaffner, C. (2022). Efficient NIZKs and signatures from commit-and-open protocols in the QROM. In Advances in Cryptology - CRYPTO 2022 (pp. 729–757). doi:10.1007/978-3-031-15979-4_25 |
|
