Quantum Random Oracle Model
Statements set in the quantum random oracle model, where the oracle may be queried in superposition.
| Status | Statement | Tags |
|---|---|---|
|
Quantum two-block MD collisions Open, in both directions and with no partial result: whether the best known quantum preprocessing attack, of advantage ST^2/N + T^3/N, is optimal for two-block Merkle-Damgård collisions. The source reports that no matching quantum bounds are known at any block length. 7 open |
Collision FindingCollision Resistant HashingQuantum Query ComplexityQuantum Random Oracle ModelTime Space Tradeoffsqromtight-bound | |
|
Fully quantum time-lock puzzles Open in the fully quantum case. Settled by the source paper when the generator is classical and the solver quantum, and when the generator is quantum and the solver classical under perfect completeness; a classical-query attack on the remaining cell would prove a simulation conjecture. 5 open |
Quantum Query ComplexityQuantum Random Oracle ModelTime Lock Puzzlesqromimpossibility | |
|
CAQB key agreement, imperfect completeness Open. Settled for perfect completeness by the source paper’s Theorem 3.1; the argument’s final step uses perfect completeness in a way that no known weakening survives, and the paper’s Simulation-Conjecture barrier does not cover this party structure. 5 open |
Quantum Key AgreementQuantum Query ComplexityQuantum Random Oracle Modelqromimpossibility | |
|
Classical presampling, quantum queries Open, and provably hard to prove: the source’s Theorem 4 shows it implies a central open problem in quantum computing. No refutation has been attempted either, and the source takes no position on which way it goes – it states the conjecture in order to show that the classical technique cannot simply be transplanted. 6 open |
PresamplingQuantum Query ComplexityQuantum Random Oracle ModelRandom Oracle Modelqromlower-boundbarrier (ai) | |
|
Polynomial Compatibility Conjecture Open in the inverse-polynomial regime. Proved for exponentially small influences by the paper that introduced it, and false for influences at or above 1/(2d); everything between is what the quantum separations depend on. 5 open |
Compressed OracleQuantum Query ComplexityQuantum Random Oracle Modelqromassumption |
No matching items