Idealized Models

Status	Statement	Tags
	Constant-round Luby–Rackoff, quantum Resolved for r=7. Carolan (Compressed Permutation Oracles, ePrint 2025/1734, STOC 2026) proves seven-round Luby-Rackoff with truly random round functions is indistinguishable from a random invertible permutation against Omega(N^{1/12}) bidirectional quantum queries (his Theorem 6.5), exactly this page’s conjecture with r=7 – and states, without full proof here, that the result lifts to pseudorandom round functions (the strong qPRP form) by a standard hybrid argument. The paper’s own abstract calls this ‘resolving an open question of (Zhandry, 2012).’	Feistel Networks Pseudorandom Permutations Quantum Query Complexityotherequivalenceresearch-solved
	dv-SNARG, One Group Element Numbered Conjecture 1.3 of the source. Its own theorems achieve one group element plus O(tau) bits, and (with a random oracle) one group element, one hash output and about 2 tau bits; the conjecture halves the additive term to tau + o(tau) and asks for no random oracle. 4 open	Generic Group Model Proof Size Lower Bounds Snarksggmcharacterization
	Four-party NIKE, quadratic, Maurer’s model Open. Achieved in Shoup’s generic group model by the source paper (Construction 9, Theorem 10); in Maurer’s model the paper’s own O(n^2) attack sets a ceiling that a construction would meet exactly, and nothing is known about reaching it. 5 open	Generic Group Model Non Interactive Key Exchangeggmseparation
	Quadratic attack on 3-NIKE, Shoup’s model Open in Shoup’s model. Settled by the source paper in Maurer’s model for every K at least 3, including imperfect correctness; its own three-party Shoup construction achieves only an n^1.5 gap, so the truth for three parties lies somewhere between n^1.5 and n^2. 5 open	Generic Group Model Non Interactive Key Exchangeggmlower-bound
	Two-block sponge attack, quadratic advice Open: whether the multi-instance two-block sponge attack of advantage (S^2T4/C²⁾S lifts to an auxiliary-input attack of advantage S^2T4/C^2, matching the best proved security bound. Settled in the multi-instance model; no partial result in the auxiliary-input model. 7 open	Collision Finding Collision Resistant Hashing Time Space Tradeoffspromlower-boundadaptation (ai)
	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 Finding Collision Resistant Hashing Quantum Query Complexity Quantum Random Oracle Model Time Space Tradeoffsqromtight-bound
	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 Noise Pseudorandom Correlation Functions Random Oracle Modelassumption
	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 Complexity Quantum Random Oracle Model Time 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 Agreement Quantum Query Complexity Quantum 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	Presampling Quantum Query Complexity Quantum Random Oracle Model Random 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 Extractors Random Oracle Model Randomness Extractionromtight-bound
	r-round DLOG tradeoff Open for every intermediate r: the r = 1 endpoint is the source’s own theorem and r = T is Corrigan-Gibbs–Kogan, with nothing proved in between. The source conjectures the interpolating formula and says a matching attack exists at every r, so the missing half is the lower bound. 6 open	Adaptivity Discrete Logarithm Generic Group Model Time Space Tradeoffsggmtight-bound
	Double-sided zero search Resolved, unconditionally. Carolan (Compressed Permutation Oracles, ePrint 2025/1734, STOC 2026) proves this exact statement – his Problem 3, p. 72, naming it ‘the double-sided zero search problem, due to Unruh’ – as a corollary (Corollary 7.6) of a general predicate-search lower bound (Theorem 7.5) proved directly from his own compressed permutation oracle’s soundness (Theorem 5.19). Unlike Unruh’s own derivation, this proof does not route through Unruh’s CPO-soundness conjecture (c/0036) at all, so it holds regardless of that conjecture’s status.	Compressed Oracle Quantum Query Complexityotherlower-boundresearch-solved
	NISC Overhead from a PRG The source poses this question and then answers the variant in which the pseudorandom generator is replaced by a random oracle, which leaves the question as posed unresolved. Each of the four relaxations – polylogarithmic overhead, correlated-abort security, extra rounds, or programmable OLE correlations – is already known. 4 open	Garbled Circuits Non Interactive Secure Computationcharacterizationadaptation (ai)
	Simon-oracle amplification, strong version Open. The version without the collision finder is known only when the one-way function is itself a random oracle; with an arbitrary one-way function, with or without the collision finder, nothing is established. 5 open	Black Box Separations Collision Resistant Hashing One Way Functionsotherlower-bound
	No round-optimal pairing-free blind signature Open for a polynomial query budget. The impossibility is proved when User_2 and Verify together make O(log lambda) random-oracle queries, including when oracle outputs contain group elements; the superpolynomial message space hypothesis is retained. 5 open	Black Box Separations Blind Signatures Generic Group Model Signature Schemesggmimpossibilityadaptation (ai)
	RBR Soundness Amplification Known in the special case of r-round protocols whose standard and round-by-round soundness errors are maximally separated, eps_RBR about eps^{1/r}; open in general, including the eps^{2/r} regime the source’s own protocol occupies. 4 open	Fiat Shamir Parallel Repetitionlower-bound
	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)
	Compressed permutation oracle soundness Still open as formalized, but the underlying research question – can the compressed-oracle technique be extended to permutations at all – is now resolved in the affirmative by a different construction. Carolan (Compressed Permutation Oracles, ePrint 2025/1734, STOC 2026) proves his own compressed permutation oracle unconditionally sound. That oracle is, in his own words, ‘similar to that of Unruh [Unr23], though we explicitly and unitarily maintain injectivity of the database’ – a change that goes beyond resolving Unruh’s own left-open choice of how the flipping operator acts on non-injective inputs. Whether Unruh’s original construction (for an arbitrary such choice) is itself sound remains, on the reading defended here, unestablished.	Compressed Oracle Pseudorandom Permutations Quantum Query Complexityotherequivalence
	Non-adaptive DDH bound Open, and asserted rather than asked: the source proves 1/2 + O~(T^2/N + sqrt(ST/N)), states twice that it conjectures this is not tight for DDH, and names 1/2 + O~(T^2/N + ST/N) as the right answer. The same theorem’s square-DDH bound is sharp, with a matching attack, which is what makes the DDH case a question rather than a suspicion. 6 open	Adaptivity Discrete Logarithm Generic Group Model Time Space Tradeoffsggmtight-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)
	STB conjecture (sponge) Open for every B >= 2 except B ~ T: at B=2 in the regime ST^3 > C, and at B >= 3 with a gap of about T/B. The source asks for a proof or a refutation and takes no position. 7 open	Collision Finding Collision Resistant Hashing Time Space Tradeoffspromtight-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