The measure-and-reprogram technique 2.0: multi-round Fiat-Shamir and more
From MaRDI portal
Publication:2104233
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.
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
- A concrete treatment of Fiat-Shamir signatures in the quantum random-oracle model
- Computationally binding quantum commitments
- From 5-pass \(\mathcal {MQ}\)-based identification to \(\mathcal {MQ}\)-based signatures
- scientific article; zbMATH DE number 1406779 (Why is no real title available?)
- Information Security and Privacy
- Non-interactive zero-knowledge proofs in the quantum random oracle model
- Post-quantum security of Fiat-Shamir
- Public-Key Identification Schemes Based on Multivariate Quadratic Polynomials
- Quantum proofs of knowledge
- Revisiting post-quantum Fiat-Shamir
- Security of the Fiat-Shamir transformation in the quantum random-oracle model
- Signatures from sequential-OR proofs
- SOFIA: \(\mathcal{MQ}\)-based signatures in the QROM
- The Fiat-Shamir transformation in a quantum world
Cited in
(48)- A concrete treatment of Fiat-Shamir signatures in the quantum random-oracle model
- Classical vs quantum random oracles
- Banquet: short and fast signatures from AES
- A non-PCP approach to succinct quantum-safe zero-knowledge
- Improved lattice-based mix-nets for electronic voting
- A compressed \(\varSigma \)-protocol theory for lattices
- A new simple technique to bootstrap various lattice zero-knowledge proofs to QROM secure NIZKs
- Fiat-Shamir bulletproofs are non-malleable (in the algebraic group model)
- Revisiting post-quantum Fiat-Shamir
- Security of the Fiat-Shamir transformation in the quantum random-oracle model
- Post-quantum security of Fiat-Shamir
- Shorter lattice-based zero-knowledge proofs for the correctness of a shuffle
- Post-quantum resettably-sound zero knowledge
- The Fiat-Shamir transformation in a quantum world
- Spartan and bulletproofs are simulation-extractable (for free!)
- Classical and quantum security of elliptic curve VRF, via relative indifferentiability
- A generic transform from multi-round interactive proof to NIZK
- A thorough treatment of highly-efficient NTRU instantiations
- Efficient NIZKs and signatures from commit-and-open protocols in the QROM
- A note on the post-quantum security of (ring) signatures
- Classically verifiable NIZK for QMA with preprocessing
- Fiat-Shamir transformation of multi-round interactive proofs (Extended version)
- Redeeming reset indifferentiability and applications to post-quantum security
- Tight adaptive reprogramming in the QROM
- Constructive post-quantum reductions
- Fiat-Shamir transformation of multi-round interactive proofs
- Fixing and mechanizing the security proof of Fiat-Shamir with aborts and Dilithium
- Obfuscation of pseudo-deterministic quantum circuits
- Compact ring signatures with post-quantum security in standard model
- Lattice-based polynomial commitments: towards asymptotic and concrete efficiency
- Post-quantum security of key encapsulation mechanism against CCA attacks with a single decapsulation query
- Probabilistic hash-and-sign with retry in the quantum random oracle model
- Selective opening security in the quantum random oracle model, revisited
- Evaluating the security of CRYSTALS-Dilithium in the quantum random oracle model
- On the (in)security of the BUFF transform
- On round elimination for special-sound multi-round identification and the generality of the hypercube for MPCitH
- On soundness notions for interactive oracle proofs
- Fiat-Shamir bulletproofs are non-malleable (in the Random Oracle Model)
- Straight-line knowledge extraction for multi-round protocols
- Succinct arguments for \textsf{BatchQMA} and friends under 8 rounds
- Quantum lifting for invertible permutations and ideal ciphers
- Relaxed vector commitment for shorter signatures
- Privacy-preserving certificate-less authenticated key exchange with key registration privacy
- Tighter proofs for PKE-to-KEM transformation in the quantum random oracle model
- CPA-secure KEMS are also sufficient for post-quantum TLS 1.3
- Improved quantum lifting by coherent measure-and-reprogram
- The Fiat-Shamir transformation of (_1,,_ )-special-sound interactive proofs
- NISQ security and complexity via simple classical reasoning
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)
