Random Oracle Model
Statements set in the classical (non-quantum) random oracle model.
| Status | Problem | Tags |
|---|---|---|
|
Subexponential-query PCF from sparse LPN Open in both directions, and the source paper poses it as a question rather than conjecturing an answer; the affirmative direction is this page’s reading. The one follow-up construction from sparse LPN inherits the same superpolynomial ceiling and says so. 6 open |
Learning Parity With NoisePseudorandom Correlation FunctionsRandom Oracle Modelromassumption | |
|
Standard-model weak PCF from sparse LPN Open, posed by the source as its second open question with an obstruction it names explicitly; the affirmative direction is this page’s reading. An independent follow-up construction reports the same random oracle as inherent to the same recursion. 6 open |
Learning Parity With NoisePseudorandom Correlation FunctionsRandom Oracle Modelassumption | |
|
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) | |
|
Split-source decomposition Open for a query budget of two or more: whether a random oracle decomposes into bit-fixing mixtures when the advice is produced by two sources that never communicate. Proved and tight at \(q=0\), and proved at \(q=1\) under an extra hypothesis. 4 open |
Multi Source ExtractorsRandom Oracle ModelRandomness Extractionromtight-bound | |
|
LHL extraction, public seed Proven, and the statement is now formalized in Lean with an AI match check: the public-seed bound holds with a concrete constant, but the proof itself is still only informal (PDF), unreviewed, and unformalized. 6 open |
Leftover Hash LemmaRandom Oracle ModelRandomness Extractionromtight-boundresearch-solvedadaptation (ai) | |
|
Computationally unique VDFs in the ROM Resolved. Guan, Riazanov and Yuan, Breaking Verifiable Delay Functions in the Random Oracle Model (ePrint 2024/766, CRYPTO 2025), prove that no VDF in the parallel ROM can have completeness and computational uniqueness and be \(\sigma\)-sequential for \(\sigma\) a fixed polynomial in the security parameter and the Setup/Verify query counts – their Theorem 5.1, which in fact covers general (not just perfect) completeness error, strictly more than this conjecture asked for. The proof is human-authored and published; it has not yet been independently re-derived by this site or formalized in Lean. 3 open |
Black Box SeparationsRandom Oracle ModelVerifiable Delay Functionsromimpossibilityresearch-solved | |
|
Salt Length vs. Call Count Fully open in both directions: no construction with \(O(\lambda)\)-length, message-independent salts and \(O(1)\) Merkle-Damgård calls is known, and no proof that none can exist, nor any trade-off between the two, has been given either. 4 open |
IndifferentiabilityRandom Oracle Modelromcharacterization | |
|
Short-Salt MD Combiner Security Open in both directions: the source’s Theorem 3.1 proves security only when salts exceed the message by at least the security parameter, and reports neither an attack nor a security proof once the salts shrink to a constant number of blocks. 4 open |
IndifferentiabilityRandom Oracle Modelromcharacterizationadaptation (ai) | |
|
3-way collision, oblivious sequential curve Open: closing the factor-\(\sqrt{S}\) gap between the proved oblivious lower bound and a matching table-and-hunt algorithm for finding a 3-way collision with an oblivious sequential branching program. 2 open |
Collision FindingRandom Oracle ModelTime Space Tradeoffsromtight-boundadaptation (ai) | |
|
STB conjecture (Merkle-Damgård) Open for non-constant \(B\) in the regime \(ST^2>2^n\), where the best published security bound and the best published attack are a factor of up to \(S\) apart; settled at \(B=1\), \(B=2\), every constant \(B\), \(B\approx T\), and every \(2<B<T\) with \(ST^2\le 2^n\). 6 open |
Collision FindingCollision Resistant HashingRandom Oracle ModelTime Space Tradeoffsromtight-boundbarrier (ai) | |
|
Three moves from DL, ROM only Open: three moves, black-box in the group, ROM only, from DL alone. Three moves is achieved from DDH in the ROM and from DL in AGM+ROM; four moves is achieved from DL in the ROM. 5 open |
Blind SignaturesRandom Oracle ModelSignature SchemesTight Reductionsromassumption | |
|
Tight \(k\)-collision time-space tradeoff The exact tight time-space tradeoff for \(k\ge 3\) collisions under preprocessing is open; only the \(k=2\) case has a matching upper and lower bound. 2 open |
Collision FindingRandom Oracle ModelTime Space Tradeoffsromtight-bound |
No matching items