Quantum Cryptography

Status	Statement	Tags
	CPA PKE, Quantumly Broken The first item in the source’s Open Problems section. It builds counterexamples for PRFs, CPA-secure symmetric-key encryption, MACs, signatures and CCA-2-secure public-key encryption, all classically secure under LWE via black-box reductions and all quantumly broken with two or three classical queries. CPA-secure public-key encryption is the case its technique cannot reach, and it says why. 4 open	Black Box Separations Learning With Errors Quantum Cryptographyseparation
	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
	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
	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
	One Haar State Looks Like Many Stated in the source’s Open Problems section as a conjecture it believes true, with the note that it could neither prove it nor find it proved or even formalised anywhere. The source proves a strictly weaker pointwise domination bound, its Lemma 2, sufficient for its own applications and silent about total variation distance. 5 open	Pseudorandom Quantum States Quantum Cryptography Quantum Informationothertight-boundadaptation (ai)
	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)
	Erasing real-or-random vs Boneh–Zhandry Open: whether erasing real-or-random security implies Boneh-Zhandry security. The reverse non-implication is proved only in the quantum random oracle model, and this direction is one of six non-implications the source paper conjectures and does not prove. 5 open	Quantum Cryptography Quantum Encryption Notionsseparation
	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
	No Self-Reduction for LSN Conjecture 5.20 of the source. It proves no random self-reduction exists from an arbitrary worst-case QNCP instance into LSN, naming exchange symmetry between code and error as the obstruction, and proves the tableau-randomizing barrier conditionally on the scrambling gap being polynomially related to eps. It is explicit that this is not an impossibility for random self-reductions in general. 4 open	Average Case Hardness Learning Parity With Noise Quantum Information Stabilizer Codesimpossibilityadaptation (ai)
	One erasing challenge vs many embedding learns Open: whether a single erasing two-ciphertext challenge query, with classical learning queries, implies security against polynomially many embedding-model superposition learning queries. One of six non-implications the source paper conjectures, and on its own account the one that would close the most remaining cells. 5 open	Quantum Cryptography Quantum Encryption Notionsseparation
	Standard real-or-random vs embedding two-ciphertext Open: whether one standard-oracle real-or-random challenge query implies one embedding-model two-ciphertext challenge query, with classical learning queries on both sides. Both notions are singleton classes in the source’s classification, and this is one of six non-implications it conjectures. 5 open	Quantum Cryptography Quantum Encryption Notionsseparation
	Threshold one-shot decryption without extractability Open: whether threshold one-shot decryption (for every corruption threshold f < 1/2) follows from one-shot signatures and an ordinary, non-extractable witness encryption scheme. The one known construction needs the witness-encryption extractor to run its security reduction, and the source paper leaves open whether extractability can be weakened or dropped altogether. 4 open	One Shot Signatures Witness EncryptionassumptionIOG
	OWF minimality, non-black-box reductions Open when the classical security implication is not witnessed by a black-box reduction between the two games. Settled affirmatively whenever it is, for uniform and non-uniform quantum adversaries alike, with the implementation reduction left arbitrary. 5 open	Black Box Separations One Way Functions Quantum Cryptographyequivalence
	Signed rank-one reweighting below the square root Resolved, affirmatively and more strongly than asked: every Borel probability measure on the sphere admits a signed reweighting reaching an exact (not merely epsilon-close) nonzero rank-one second moment at entropy cost only O(log n) – below every n^delta, for every delta > 0, with the constant C(epsilon,delta) = 2/(e*delta) independent of epsilon. Proved by an AI-driven proof harness (conjecture-harness campaign c/0048) across six revision rounds, twenty independent blind adversarial referee passes over four audited rounds, and four independent triage rulings; the load-bearing chain (Lemmas 1-4, Theorem, Corollary, Corollary B) has never had an upheld finding against it. No human has reviewed the mathematics, and nothing here is formalized in Lean. A separate concurrent session forked the same campaign at round 3 and closed the same scope-commentary gap by a different (but mathematically equivalent) edit; both branches are recorded in the campaign ledger and the fork is not yet reconciled. 6 open	Log Rank Conjecture Sum Of Squaresassumptionresearch-solved
	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
	Best Separable State, constant completeness error Open: whether the paper’s 2^{Otilde(sqrt n)}-time algorithm for Best Separable State extends from perfect (and near-perfect, 1-1/n) completeness to any constant completeness error c < 1. The paper conjectures the affirmative and lists this first among its open questions; no partial result at any intermediate error is reported. 5 open	Quantum Information Sum Of Squaresassumption
	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 Oracle Quantum Query Complexity Quantum Random Oracle Modelqromassumption