PaperlayerView exact revision on arXiv

Source-linked AI summary

Random Oracles in a Quantum World

Dan Boneh, Özgür Dagdelen, Marc Fischlin, Anja Lehmann, Christian Schaffner, Mark Zhandry

arXiv:1008.0931v2quant-phcs.CR

TL;DR

Post-quantum cryptosystems proven in the classical random-oracle model may not remain secure when adversaries make quantum oracle queries. The paper separates these models, develops history-free reductions and simulation techniques, and applies them to selected signatures and encryption schemes while identifying unresolved cases.

  • Problem

    Classical random-oracle proofs for post-quantum systems do not address adversaries that query the oracle with quantum states, even though concrete hash instantiations permit such attacks.

  • Method

    The paper separates the two oracle models, defines history-free reductions, and uses quantum-accessible pseudorandom functions to simulate quantum-accessible random oracles.

  • Results

    History-free reductions imply quantum-accessible random-oracle security for selected signatures, including GPV and FDH-related schemes, while the paper also proves quantum CPA security for an encryption scheme.

  • Takeaways & Limitations

    Selected classical random-oracle proofs can establish post-quantum security when their reductions have the required history-free structure.

  • Takeaways & Limitations

    Quantum security remains open for generic FDH signatures, Fiat–Shamir-derived signatures, and generic CPA-to-CCA transformations.

Abstract

from arXiv · show

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.

1 Introduction

Post-quantum schemes proven secure with classical random-oracle access may fail against quantum oracle queries, motivating quantum-accessible analysis and proof techniques. The paper separates the models and develops history-free reductions for transferring selected classical security proofs to the quantum setting.

  • The quantum-accessible model: A signature proof that embeds a challenge in one randomly selected oracle response succeeds classically with probability 1/q but fails in the quantum-accessible model.Each quantum query potentially evaluates the oracle at exponentially many inputs, defeating the classical guessing strategy.
  • The quantum-accessible model: Quantum attackers can evaluate a random oracle on superpositions, so classical proofs based on adaptive programming, query extraction, or rewinding may not carry over.A quantum query can reveal information about exponentially many oracle inputs, while changing previously encountered hash values may be detectable.
  • Generic proof conditions: Efficient simulation can be recovered using quantum-accessible pseudorandom functions, although the existence of such functions remains an open problem.The technique simulates the quantum-accessible random oracle through an efficient pseudorandom function.
  • Separation: The paper separates the models with a protocol secure under classical oracle access but insecure when quantum adversaries access the oracle quantumly.The separation uses the polynomial gap between birthday collision attacks and Grover-based collision finding.
  • Generic proof conditions: History-free reductions answer oracle queries independently of prior query history, and such reductions imply quantum existential unforgeability for signatures.The paper applies this framework to GPV signatures and selected FDH-related schemes, with essentially the same tightness as classical reductions.
  • Open problems: The paper leaves quantum security of generic FDH, Fiat–Shamir-derived signatures, and generic CPA-to-CCA transformations unresolved.These open problems concern both signature and encryption constructions in the quantum random-oracle model.

2 Preliminaries

The preliminaries define the classical and quantum models, the oracle-query framework, and the indistinguishability tools used for quantum-accessible random oracles. They also formalize hard problems and trapdoor-function security against quantum algorithms.

  • Quantum computation and oracle access: A quantum attacker is modeled as alternating unitary transformations and oracle calls, with quantum access preserving superpositions across query inputs.Classical access instead measures the query register before applying the oracle transformation.
  • Quantum-accessible random oracles: Quantum-accessible random-oracle simulation requires consistent answers over superposition queries, motivating quantum-resistant pseudorandom functions as auxiliary oracles.The resulting oracle must be computationally indistinguishable from a truly random oracle for polynomial-time quantum algorithms.
  • Quantum-accessible random oracles: A quantum-accessible pseudorandom function is efficiently computable yet indistinguishable from a random oracle to every efficient quantum distinguisher.The definition’s probabilities range over PRF keys versus random oracles, with negligible distinguishing advantage.
  • Hard problems: Hard problems are formalized as adversarial games with success thresholds, including inversion and collision games for secure trapdoor and preimage-sampleable trapdoor functions.The relevant hardness notions are defined against quantum computers.

3 Separation Result

The separation result constructs an identification protocol that adds a timed near-collision stage to a quantum-immune identification scheme. It is secure against classical random-oracle access but becomes insecure with quantum oracle access because Grover-based collision search defeats the timing barrier.

  • 3 Separation Result: The section establishes a protocol secure with classical random-oracle access against classical and quantum adversaries, yet insecure for any hash function under quantum oracle access.This separates the classical and quantum-accessible random-oracle models.
  • 3.1 Assumptions: Classically, collision resistance is bounded by the birthday attack, which requires roughly 2^(n/2) probes for an n-bit hash output.For random oracles, this generic attack is optimal.
  • 3.1 Assumptions: The construction relies on bounded parallel speed-up and simplified unit-time and zero-time assumptions for hash evaluation and other protocol actions.The authors acknowledge that zero-time overhead for quantum speed-up may be optimistic because quantum computation can have higher overall costs than massive parallel computation.
  • 3.2 Construction: The protocol augments an identification scheme with repeated timed near-collision tests before running the standard identification stage.The verifier accepts when the prover finds enough collisions or identifies correctly.
  • 3.2 Construction: The protocol is complete when the underlying identification scheme is complete, and its classical security follows under a suitable choice of ℓ and a quantum-immune base scheme.The stated condition is ℓ > 6 log(α), where α captures bounded parallel speed-up.
  • 3.3 Separation: A quantum adversary can use Grover’s algorithm to find collisions in time 2^ℓ with probability at least 1/2, enabling r/4 collisions with noticeable probability.The same negative result holds in the quantum-accessible random-oracle model because Grover search needs only quantum black-box access.

4 Signature Schemes in the Quantum-Accessible Random Oracle Model

The section establishes history-free reductions as a sufficient route from classical random-oracle proofs to quantum-accessible security, then applies this framework to PSF- and claw-free-permutation-based signatures.

  • General framework: History-free reductions answer oracle and signature queries independently of prior responses or query number.This property enables classical security reductions to extend to quantum-accessible random-oracle adversaries.
  • General framework: Theorem 4.2 proves quantum-accessible security when a history-free reduction uses a classical adversary, the underlying problem is quantum-hard, and quantum-accessible pseudorandom functions exist.The pseudorandom-function assumption supports efficient simulation of the quantum-accessible random oracle.
  • PSF signatures: For FDH-PSF, the collision-finding reduction is tight up to negligible loss when conditional signature min-entropy is super-logarithmic; with min-entropy 1, it retains advantage ε/2.The extracted collision probability is 1 − 2^-E, where E is the relevant minimum conditional min-entropy.
  • PSF signatures: The FDH-PSF reduction is history-free, yielding security against quantum adversaries when quantum-accessible pseudorandom functions exist and the PSF is quantum-secure.The reduction uses INSTANCE(pk) := pk, and the PSF’s min-entropy supports collision extraction from valid forgeries.
  • Claw-free permutations: Claw-free permutations support three history-free signature reductions: standard FDH, Katz-Wang, and FDH-PSF.Katz-Wang and FDH-PSF have tight reductions, while the Coron-based proof loses a factor of q_s, the number of signing queries.
  • Claw-free permutations: The claw-free-permutation instantiations of FDH and Katz-Wang are secure against quantum adversaries under quantum-accessible pseudorandom functions.The simulated oracle is truly random, giving FDH advantage approximately ε/q_SIGN and Katz-Wang advantage ε/2.

5 Encryption Schemes in the Quantum-Accessible Random Oracle Model

The section proves quantum security for the BR encryption scheme and a hybrid generalization directly in the quantum-accessible random oracle model. The BR scheme is shown quantum CPA secure, while the hybrid scheme is shown quantum CCA secure under corresponding trapdoor, pseudorandom-function, and symmetric-encryption assumptions.

  • Overview: The section directly proves quantum CPA security for BR encryption and quantum CCA security for a hybrid generalization.The BR result is treated as a special case of the hybrid encryption theorem.
  • BR Encryption: The BR scheme encrypts m as (f(pk, r), O(r) ⊕m) using an injective trapdoor function and a random oracle.Its formal definition uses a trapdoor function F = (G0, f, f −1), with key generation inherited from G0.
  • BR Encryption: If quantum-accessible pseudorandom functions exist and F is quantum-immune, BR encryption is quantum CPA secure.The proof establishes this as Theorem 5.2 and omits the proof because it follows from the hybrid scheme’s CCA proof.
  • Hybrid Encryption: The hybrid scheme combines an injective trapdoor function with a CCA-secure symmetric encryption scheme, encrypting as (f(pk, r), ES(O(r), m)).Decryption recovers r with the trapdoor and applies the symmetric decryption algorithm using O(r).
  • Hybrid Encryption: Theorem 5.4 states that quantum-accessible pseudorandom functions, a quantum-immune injective trapdoor function, and quantum CCA-secure symmetric encryption imply quantum CCA security of the hybrid scheme.The BR construction is recovered when the symmetric encryption scheme is the one-time pad.
  • Proof Strategy: The proof simulates the quantum oracle through Oquant, embeds the challenge at a random query, and uses negligible query probability at the challenge point to transfer security between games.If the adversary’s total query probability at the challenge point is ǫ, the inverter succeeds with probability ǫ/q; hence ǫ is negligible under the trapdoor assumption.
  • Proof Strategy: The adversary’s quantum-oracle success is negligible because a non-negligible advantage would either invert the trapdoor function or break the symmetric scheme’s CCA security.Changing the oracle at a point with negligible total query probability changes the game distribution only negligibly.
  • Proof Strategy: The final game argument concludes that every polynomial-time quantum adversary has negligible advantage, establishing quantum CCA security for the hybrid encryption scheme.The conclusion follows after bounding both the trapdoor-inversion and symmetric-encryption reductions.

6 Conclusion

The conclusion emphasizes that classical random-oracle proofs cannot automatically establish security against quantum oracle queries. It identifies quantum-accessible pseudorandom functions and several unresolved generalizations as central directions for future work.

  • Conclusion: Security arguments using random oracles require particular care when quantum attackers can query the oracle with quantum states.The authors recommend reconsidering classical proofs in this setting.
  • Conclusion: The paper develops conditions for translating classical random-oracle security proofs into the quantum random-oracle model and applies them to selected signature and encryption schemes.The conclusion summarizes the paper’s proof strategy and applications without claiming a universal translation theorem.
  • Open Problems: Quantum-accessible pseudorandom functions appear fundamental for simulating random oracles in the quantum world, making their existence an important open question.The conclusion explicitly identifies proving or disproving their existence as an important step.
  • Open Problems: Open problems include generic FDH signatures, Fiat–Shamir-derived signatures, generic CPA-to-CCA transformations, and lattice-based identity-based encryption in the quantum random-oracle model.These classical random-oracle results remain unresolved in the quantum setting.

A Definitions

This appendix defines the trapdoor, preimage-sampleable, signature, and encryption primitives used throughout the paper, together with their security games against quantum adversaries.

  • Trapdoor Functions: A trapdoor permutation provides key generation, a permutation f(pk, ·), and an inverse f −1(sk, ·) satisfying the inverse relations.Its quantum security is defined by hardness of the inversion game Inv(F).
  • Trapdoor Functions: The appendix states that GPV08 construct a preimage-sampleable function whose security is based on the hardness of lattice problems.This connects the formal primitive to the lattice-based constructions discussed in the paper.
  • Trapdoor Functions: A preimage sampleable trapdoor function adds sampling and requires near-uniform image sampling, faithful preimage sampling, and negligible preimage concentration.Its security requires both inversion and collision resistance against quantum computers.
  • Signatures: A random-oracle signature scheme consists of key generation, signing with secret key and oracle access, and verification of signatures under the public key.Quantum security is defined by hardness of forging a valid signature on a message that was not queried to the signer.
  • Encryption: A symmetric-key encryption scheme provides oracle-dependent encryption and decryption algorithms satisfying DO(k, EO(k, m)) = m.CCA security is defined through a quantum adversary’s access to oracle, encryption, decryption, and one challenge query.
  • Encryption: An asymmetric-key encryption scheme uses key generation, public-key encryption, and secret-key decryption with correct decryption of honestly generated ciphertexts.Its quantum CCA game gives the adversary quantum oracle access, classical decryption access, and one challenge query.

B Security of the IS∗Protocol

The IS∗ protocol separates classical and quantum security in the random-oracle setting. It is secure against classical adversaries under collision-search bounds, but quantum-accessible hashing enables an efficient collision attack that makes the protocol insecure.

  • Security Goal: The security goal is to prevent an adversary interacting with an honest prover from later impersonating that prover.The protocol’s analysis focuses on whether the verifier accepts the adversary’s interaction.
  • Classical Security: Against classical adversaries, IS∗ is secure in the random-oracle model when ℓ > 6 log(α), assuming the underlying identification scheme is secure.The proof bounds acceptance by the probability of breaking the identification scheme plus finding at least r/4 collisions.
  • Classical Security: Classical collision search is limited by the birthday bound, and fresh verifier keys force the adversary to restart the search in every round.The protocol therefore prevents reuse of previously learned oracle values across rounds.
  • Classical Security: For constant α and polynomially many rounds, the probability that a classical adversary obtains enough collisions is negligible.The argument uses a Chernoff bound after bounding the per-round collision probability.
  • Quantum Insecurity: The classical security result does not survive arbitrary hash-function instantiation against quantum adversaries: every hash function admits an efficient quantum attack on IS∗.The paper explicitly contrasts this with the security achievable in the classical random-oracle model.
  • Quantum Insecurity: Quantum access lets the adversary evaluate the hash on superpositions and apply Grover search to find collisions for each verifier key.The attack transforms the classical hash function into a quantum-accessible function and searches for distinct colliding inputs.
  • Quantum Insecurity: The quantum adversary finds a collision with probability greater than 1/2 in each round, making fewer than r/4 successful rounds negligible.Consequently, the verifier accepts with noticeable probability.
  • Quantum Insecurity: Therefore, IS∗ is not secure in the quantum-accessible random-oracle model.The result holds because Grover’s algorithm requires only quantum-accessible black-box access to the hash function.

C Proof of Lemma 4.4

The proof establishes two technical lemmas controlling how quantum query states and output distributions change when a random oracle is modified. It then constructs a modified oracle with output distribution D and bounds its distinguishability from the truly random oracle.

  • Technical lemmas: Lemma C.1 bounds how much measuring a nearby quantum state can change the probability of satisfying a property.The proof models states as vectors, projects them onto the subspace of strings satisfying the property, and uses that projections do not increase distance.
  • Technical lemmas: Lemma C.2 bounds the expected total query probability of inputs mapping to a fixed output y for a quantum algorithm making at most q oracle queries.The argument replaces a uniformly distributed oracle value with y independently at each input, then analyzes the resulting query magnitude.
  • Oracle construction: The proof constructs D′′ by first sampling y uniformly and then either outputting y with a probability determined by Pr[y|D] or sampling from D′.For probabilities below 2^-m, the construction outputs y with probability 2^m Pr[y|D].
  • Oracle construction: This construction equals D and induces an oracle O′ distributed according to D by independently replacing sufficiently unlikely oracle outputs with values drawn from D′.The expected query magnitude on changed points is then bounded using Lemma C.2, and the state distance is bounded through the query-by-query quantities σ_i, δ_i, and γ_i.
  • Conclusion: The resulting expected Euclidean distance implies that the output distributions under O′ and a truly random oracle are at most 4q2√ε apart in variational distance.The conclusion is stated after bounding the expected Euclidean distance between the corresponding algorithmic states.
Loading 1008.0931v2…