The measure-and-reprogram technique 2.0: multi-round Fiat-Shamir and more
From MaRDI portal
Publication:2104233
DOI10.1007/978-3-030-56877-1_21zbMATH Open1504.94134arXiv2003.05207OpenAlexW3013339691MaRDI QIDQ2104233FDOQ2104233
Authors: Jelle Don, Serge Fehr, Christian Majenz 
Publication date: 7 December 2022
Abstract: We revisit recent works by Don, Fehr, Majenz and Schaffner and by Liu and Zhandry on the security of the Fiat-Shamir transformation of -protocols in the quantum random oracle model (QROM). Two natural questions that arise in this context are: (1) whether the results extend to the Fiat-Shamir transformation of multi-round interactive proofs, and (2) whether Don et al.'s loss in security is optimal. Firstly, we answer question (1) in the affirmative. As a byproduct of solving a technical difficulty in proving this result, we slightly improve the result of Don et al., equipping it with a cleaner bound and an even simpler proof. We apply our result to digital signature schemes showing that it can be used to prove strong security for schemes like MQDSS in the QROM. As another application we prove QROM-security of a non-interactive OR proof by Liu, Wei and Wong. As for question (2), we show via a Grover-search based attack that Don et al.'s quadratic security loss for the Fiat-Shamir transformation of -protocols is optimal up to a small constant factor. This extends to our new multi-round result, proving it tight up to a factor that depends on the number of rounds only, i.e. is constant for any constant-round interactive proof.
Full work available at URL: https://arxiv.org/abs/2003.05207
Recommendations
- Security of the Fiat-Shamir transformation in the quantum random-oracle model
- Fiat-Shamir transformation of multi-round interactive proofs
- Fiat-Shamir transformation of multi-round interactive proofs (Extended version)
- Revisiting post-quantum Fiat-Shamir
- The Fiat-Shamir transformation in a quantum world
Cites Work
- Title not available (Why is that?)
- Public-Key Identification Schemes Based on Multivariate Quadratic Polynomials
- Information Security and Privacy
- From 5-Pass $$\mathcal {MQ}$$-Based Identification to $$\mathcal {MQ}$$-Based Signatures
- Quantum proofs of knowledge
- Non-Interactive Zero-Knowledge Proofs in the Quantum Random Oracle Model
- Computationally Binding Quantum Commitments
- Post-quantum security of Fiat-Shamir
- A concrete treatment of Fiat-Shamir signatures in the quantum random-oracle model
- SOFIA: \(\mathcal{MQ}\)-based signatures in the QROM
- Signatures from sequential-OR proofs
- Revisiting post-quantum Fiat-Shamir
- Security of the Fiat-Shamir transformation in the quantum random-oracle model
- The Fiat–Shamir Transformation in a Quantum World
Cited In (31)
- Improved lattice-based mix-nets for electronic voting
- Efficient NIZKs and signatures from commit-and-open protocols in the QROM
- Compact ring signatures with post-quantum security in standard model
- Fiat-Shamir transformation of multi-round interactive proofs (Extended version)
- Fiat-Shamir transformation of multi-round interactive proofs
- Banquet: short and fast signatures from AES
- A compressed \(\varSigma \)-protocol theory for lattices
- A new simple technique to bootstrap various lattice zero-knowledge proofs to QROM secure NIZKs
- Constructive post-quantum reductions
- Lattice-based polynomial commitments: towards asymptotic and concrete efficiency
- A note on the post-quantum security of (ring) signatures
- Tight adaptive reprogramming in the QROM
- Post-quantum security of key encapsulation mechanism against CCA attacks with a single decapsulation query
- Spartan and bulletproofs are simulation-extractable (for free!)
- A non-PCP approach to succinct quantum-safe zero-knowledge
- Redeeming reset indifferentiability and applications to post-quantum security
- Classical and quantum security of elliptic curve VRF, via relative indifferentiability
- Probabilistic hash-and-sign with retry in the quantum random oracle model
- Fiat-Shamir bulletproofs are non-malleable (in the algebraic group model)
- Shorter lattice-based zero-knowledge proofs for the correctness of a shuffle
- Classical vs quantum random oracles
- A generic transform from multi-round interactive proof to NIZK
- Selective opening security in the quantum random oracle model, revisited
- Evaluating the security of CRYSTALS-Dilithium in the quantum random oracle model
- A thorough treatment of highly-efficient NTRU instantiations
- On the (in)security of the BUFF transform
- Fiat-Shamir bulletproofs are non-malleable (in the Random Oracle Model)
- On soundness notions for interactive oracle proofs
- Obfuscation of pseudo-deterministic quantum circuits
- Post-quantum resettably-sound zero knowledge
- Classically verifiable NIZK for QMA with preprocessing
This page was built for publication: The measure-and-reprogram technique 2.0: multi-round Fiat-Shamir and more
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2104233)
