Random Oracle Model (ROM)

Status	Statement	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 Noise Pseudorandom Correlation Functions Random Oracle Modelromassumption
	1+1 adaptively secure lattice threshold signature Resolved. Oriole (Jiang, Wee, Zhu, ePrint 2026/793, posted April 2026, a month after Tweed) gives a lattice-based threshold signature with exactly this shape – two rounds, only the second message-dependent, adaptive security against T-1 corruptions with no erasures, from MSIS and MLWE in the ROM – verified here directly against the paper’s PDF (Definition of adp-TS-sUF-4 in its Figure 4, and the Theorem 2 + Theorem 3 reduction chain to MSIS), not just its abstract. The proof is human-written and published, but not yet independently re-verified line-by-line by this site, nor formalized in Lean.	Learning With Errors Threshold Signatures Tight Reductionsromseparationresearch-solved
	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 Extractors Random Oracle Model Randomness 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 Lemma Random Oracle Model Randomness 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 Separations Random Oracle Model Verifiable 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	Indifferentiability Random 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	Indifferentiability Random Oracle Modelromcharacterizationadaptation (ai)
	3-way collision, oblivious sequential curve Open: closing the factor-root-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 Finding Random Oracle Model Time 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~T, and every 2<B<T with ST^2 <= 2^n. 6 open	Collision Finding Collision Resistant Hashing Random Oracle Model Time 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 Signatures Random Oracle Model Signature Schemes Tight Reductionsromassumption
	Single-session lattice Chevallier-Mames tightness Open: whether the one-session lattice translation of the Chevallier-Mames signature has a tight SUF-CMA reduction to search Module-LWE, or whether the paper’s two-fold parallel repetition (which doubles signature size and signing time) is inherent to a tight proof of this shape. 4 open	Learning With Errors Signature Schemes Tight Reductionsromtight-bound
	Tight \(k\)-collision time-space tradeoff The exact tight time-space tradeoff for k>=3 collisions under preprocessing is open; only the k=2 case has a matching upper and lower bound. 2 open	Collision Finding Random Oracle Model Time Space Tradeoffsromtight-bound