Constructive post-quantum reductions
From MaRDI portal
Abstract: Is it possible to convert classical cryptographic reductions into post-quantum ones? It is customary to argue that while this is problematic in the interactive setting, non-interactive reductions do carry over. However, when considering quantum auxiliary input, this conversion results in a non-constructive post-quantum reduction that requires duplicating the quantum auxiliary input, which is in general inefficient or even impossible. This violates the win-win premise of provable cryptography: an attack against a cryptographic primitive should lead to an algorithmic advantage. We initiate the study of constructive quantum reductions and present positive and negative results for converting large classes of classical reductions to the post-quantum setting in a constructive manner. We show that any non-interactive non-adaptive reduction from assumptions with a polynomial solution space (such as decision assumptions) can be made post-quantum constructive. In contrast, assumptions with super-polynomial solution space (such as general search assumptions) cannot be generally converted. Along the way, we make several additional contributions: 1. We put forth a framework for reductions (or general interaction) with stateful solvers for a computational problem, that may change their internal state between consecutive calls. We show that such solvers can still be utilized. This framework and our results are meaningful even in the classical setting. 2. A consequence of our negative result is that quantum auxiliary input that is useful against a problem with a super-polynomial solution space cannot be generically ``restored post-measurement. This shows that the novel rewinding technique of Chiesa et al. (FOCS 2021) is tight in the sense that it cannot be extended beyond a polynomial measurement space.
Recommendations
- Quantum computing, postselection, and probabilistic polynomial-time
- Reductions and quantization
- Quantum computation, entanglement and state reduction
- Quantum circuit optimization by Hadamard gate reduction
- Quantum reduction in the twisted case
- Reduction of theoretical uncertainty in quantum computing
- An operational approach to quantum state reduction
- Efficient simulation of quantum state reduction
- Completely Reducible Maps in Quantum Information Theory
Cites work
- scientific article; zbMATH DE number 1579275 (Why is no real title available?)
- scientific article; zbMATH DE number 2086396 (Why is no real title available?)
- A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device
- Advances in Cryptology - CRYPTO 2003
- Classical vs quantum random oracles
- Cryptography in the Bounded-Quantum-Storage Model
- Encryption Schemes Using Random Oracles: From Classical to Post-Quantum Security
- From absolute distinguishability to positive distinguishability
- Hidden cosets and applications to unclonable cryptography
- How to record quantum queries, and applications to quantum indifferentiability
- IND-CCA-secure key encapsulation mechanism in the quantum random oracle model, revisited
- On lattices, learning with errors, random linear codes, and cryptography
- On the (Im)Possibility of Key Dependent Encryption
- Post-Quantum Security of the Fujisaki-Okamoto and OAEP Transforms
- Random oracles in a quantum world
- Revisiting post-quantum Fiat-Shamir
- Secure identity-based encryption in the quantum random oracle model
- Security of the Fiat-Shamir transformation in the quantum random-oracle model
- The measure-and-reprogram technique 2.0: multi-round Fiat-Shamir and more
- Tighter security proofs for GPV-IBE in the quantum random oracle model
Cited in
(8)- Post-quantum insecurity from LWE
- Revocable cryptography from learning with errors
- Universal reductions: reductions relative to stateful oracles
- Quantum search-to-decision reduction for the LWE problem
- How to verify that a small device is quantum, unconditionally
- Cloning games: a general framework for unclonable primitives
- Quantum key leasing for PKE and FHE with a classical lessor
- Polynomial commitments from lattices: post-quantum security, fast verification and transparent setup
This page was built for publication: Constructive post-quantum reductions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6163970)
