Random oracles in a quantum world
From MaRDI portal
Abstract: The interest in post-quantum cryptography - classical systems that remain secure in the presence of a quantum adversary - has generated elegant proposals for new cryptosystems. Some of these systems are set in the random oracle model and are proven secure relative to adversaries that have classical access to the random oracle. We argue that to prove post-quantum security one needs to prove security in the quantum-accessible random oracle model where the adversary can query the random oracle with quantum states. We begin by separating the classical and quantum-accessible random oracle models by presenting a scheme that is secure when the adversary is given classical access to the random oracle, but is insecure when the adversary can make quantum oracle queries. We then set out to develop generic conditions under which a classical random oracle proof implies security in the quantum-accessible random oracle model. We introduce the concept of a history-free reduction which is a category of classical random oracle reductions that basically determine oracle answers independently of the history of previous queries, and we prove that such reductions imply security in the quantum model. We then show that certain post-quantum proposals, including ones based on lattices, can be proven secure using history-free reductions and are therefore post-quantum secure. We conclude with a rich set of open problems in this area.
Recommendations
- Classical vs quantum random oracles
- Encryption Schemes Using Random Oracles: From Classical to Post-Quantum Security
- Quantum random oracle model with auxiliary input
- A Note on the Instantiability of the Quantum Random Oracle
- How to record quantum queries, and applications to quantum indifferentiability
Cited in
(only showing first 100 items - show all)- Provable secure post-quantum signature scheme based on isomorphism of polynomials in quantum random oracle model
- Revisiting TESLA in the quantum random oracle model
- ORAMs in a quantum world
- Public key compression for constrained linear signature schemes
- Leighton-Micali hash-based signatures in the quantum random-oracle model
- Traceable ring signatures: general framework and post-quantum security
- Adaptively secure lattice-based revocable IBE in the QROM: compact parameters, tight security, and anonymity
- \textsc{Fractal}: post-quantum and transparent recursive proofs from holography
- Signatures from sequential-OR proofs
- Measure-rewind-measure: tighter quantum random oracle model proofs for one-way to hiding and CCA security
- Generic authenticated key exchange in the quantum random oracle model
- Threshold ring signatures: new definitions and post-quantum security
- Tight and optimal reductions for signatures based on average trapdoor preimage sampleable functions and applications to code-based signatures
- Classical vs quantum random oracles
- On the compressed-oracle technique, and post-quantum security of proofs of sequential work
- QCCA-secure generic key encapsulation mechanism with tighter security in the quantum random oracle model
- Banquet: short and fast signatures from AES
- Round-optimal verifiable oblivious pseudorandom functions from ideal lattices
- IND-secure quantum symmetric encryption based on point obfuscation
- Quantum zero correlation linear cryptanalysis
- Quantum cryptanalysis of the full AES-256-based Davies-Meyer, Hirose and MJH hash functions
- The ``Quantum annoying property of password-authenticated key exchange protocols
- Quantum indistinguishability for public key encryption
- Separate your domains: NIST PQC KEMs, oracle cloning and read-only indifferentiability
- Finding hash collisions with quantum computers by using differential trails with smaller probability than birthday bound
- On tight quantum security of HMAC and NMAC in the quantum random oracle model
- A new simple technique to bootstrap various lattice zero-knowledge proofs to QROM secure NIZKs
- A hybrid cryptosystem for digital contents confidentiality based on rotation of quantum spin states
- One-time traceable ring signatures
- \textsf{GM}\textsuperscript{MT}: a revocable group Merkle multi-tree signature scheme
- Security analysis of DGM and GM group signature schemes instantiated with XMSS-T
- Tightly secure ring-LWE based key encapsulation with short ciphertexts
- \textsc{Mitaka}: a simpler, parallelizable, maskable variant of \textsc{Falcon}
- Anonymous, robust post-quantum public key encryption
- Watermarking PRFs against quantum adversaries
- Anonymity of NIST PQC round 3 KEMs
- Online-extractability in the quantum random-oracle model
- Succinct arguments in the quantum random oracle model
- Delegating quantum computation in the quantum random oracle model
- Tighter proofs of CCA security in the quantum random oracle model
- Quantum random oracle model with auxiliary input
- Being a permutation is also orthogonal to one-wayness in quantum world: impossibilities of quantum one-way permutations from one-wayness primitives
- The lattice-based digital signature scheme qTESLA
- Quantum spin half algebra and generalized Megrelishvili protocol for confidentiality of digital images
- How to record quantum queries, and applications to quantum indifferentiability
- Quantum security proofs using semi-classical oracles
- More efficient construction of anonymous signatures
- Complete analysis of Simon's quantum algorithm with additional collisions
- A quantum related-key attack based on the Bernstein-Vazirani algorithm
- A multi-valued quantum fully homomorphic encryption scheme
- Applications of Simon's algorithm in quantum attacks on Feistel variants
- CCA-secure (puncturable) KEMs from encryption with non-negligible decryption errors
- Post-quantum verification of Fujisaki-Okamoto
- Post-quantum resettably-sound zero knowledge
- Unifying presampling via concentration bounds
- Breaking symmetric cryptosystems using quantum period finding
- Semantic security and indistinguishability in the quantum world
- A note on quantum security for post-quantum cryptography
- Computational Security of Quantum Encryption
- Provably secure password authenticated key exchange based on RLWE for the post-quantum world
- Post-Quantum Security of the Fujisaki-Okamoto and OAEP Transforms
- Tighter security proofs for post-quantum key encapsulation mechanism in the multi-challenge setting
- A note on quantum related-key attacks
- Quantum hardness of learning shallow classical circuits
- Memory-Tight Reductions for Practical Key Encapsulation Mechanisms
- A Note on the Instantiability of the Quantum Random Oracle
- Encryption Schemes Using Random Oracles: From Classical to Post-Quantum Security
- Post-quantum Security of Plain OAEP Transform
- Supersingular isogeny-based cryptography: a survey
- A practical multivariate blind signature scheme
- Tighter security proofs for GPV-IBE in the quantum random oracle model
- Extended security arguments for signature schemes
- Classical and quantum security of elliptic curve VRF, via relative indifferentiability
- Multi-instance secure public-key encryption
- Post-quantum anonymity of Kyber
- QCCA-secure generic transformations in the quantum random oracle model
- A lightweight identification protocol based on lattices
- \texttt{POLKA}: towards leakage-resistant post-quantum CCA-secure public key encryption
- Certified everlasting zero-knowledge proof for QMA
- On the impossibility of key agreements from quantum random oracles
- Efficient NIZKs and signatures from commit-and-open protocols in the QROM
- Code-Based Signature Schemes from Identification Protocols in the Rank Metric
- An injectivity analysis of Crystals-Kyber and implications on quantum security
- Quantum-resistant password-based threshold single-sign-on authentication with updatable server private key
- Implicit rejection in Fujisaki-Okamoto: framework and a novel realization
- KDM security for the Fujisaki-Okamoto transformations in the QROM
- A note on the post-quantum security of (ring) signatures
- Group action key encapsulation and non-interactive key exchange in the QROM
- IND-CCA security of Kyber in the quantum random oracle model, revisited
- Nostradamus goes quantum
- Non-uniformity and quantum advice in the quantum random oracle model
- Black-box separations for non-interactive classical commitments in a quantum world
- Formal verification of Saber's public-key encryption scheme in easycrypt
- On the non-tightness of measurement-based reductions for key encapsulation mechanism in the quantum random oracle model
- Redeeming reset indifferentiability and applications to post-quantum security
- Quantum computationally predicate-binding commitments with application in quantum zero-knowledge arguments for NP
- Quantum encryption with certified deletion, revisited: public key, attribute-based, and classical communication
- Tight adaptive reprogramming in the QROM
- Fault-injection attacks against NIST's post-quantum cryptography round 3 KEM candidates
- A new lattice-based online/offline signatures framework for low-power devices
This page was built for publication: Random oracles in a quantum world
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3102175)
