Information-Theoretic Cryptography

Status	Statement	Tags
	Balanced Root-n Preprocessing PIR The client-space-times-bandwidth product is settled up to n^{o(1)} by the source’s own matching bounds. What is open is whether client space, bandwidth and per-query server computation can all sit at O~(n^{1/2}) simultaneously; the best known point has client space and server computation O~(n^{2/3}). 4 open	Private Information Retrieval Time Space Tradeoffstight-bound
	Planted-Subgraph Character Sum The source derives the formula governing low-degree detection of a planted subgraph, observes the character sum in it should be small for most graphs, and says it leaves the rigorous study of the question to future work. No bound is proved and none is stated as a target. 5 open	Average Case Hardness Planted Subgraph Problemslower-boundadaptation (ai)
	Perfectly Correct Statistical ARE Statistical security with statistical correctness is settled by the source for every finite function. Perfect correctness is known in the computational setting and, in the statistical setting, only in a relaxed Las Vegas form where the evaluator may declare failure. 4 open	Additive Randomized Encodings Shuffle Modelcharacterizationadaptation (ai)
	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)
	Sources vs Randomness Blowup Conjecture 13 of the source. Its companion question – how many parties must be able to toss coins – is settled exactly by the same paper: t sources for deterministic functionalities, t+1 for randomized ones, even though the adversary may corrupt all of them. What the count costs is not settled. Both halves of the Theta are open. 5 open	Random Sources Randomness Complexitytight-bound
	AVPs Are Lengthy Posed as Hypothesis 1.2 and offered both as a working hypothesis and as an ambitious target. Theorem 1.3 proves it implies super-polynomial lower bounds on sd-PIR, general secret sharing and fully-decomposable randomized encodings – for none of which a super-linear lower bound is currently known. The source adapts counting-based arguments to the model but does not reach the best-known bound for any primitive. 4 open	Garbled Circuits Private Information Retrieval Proof Size Lower Bounds Randomized Encodingslower-boundbarrier (ai)
	Efficient Parity-Tolerance Simulation Feasibility is settled: every circuit can be compiled into a t-parity-tolerant one. What is open is the simulator’s running time, which in the source’s construction is exponential in t; the source gives partial evidence, under LPN, that inefficient simulation may be inherent for a related relaxed notion. 4 open	Leakage Resilient Circuits Learning Parity With Noisecharacterization
	Optimal 2D LPHS Open, and asserted rather than asked: the source prints the algorithm, conjectures the error rate, reports experiments consistent with it, states it could not analyse it, and leaves settling it to future work. The matching lower bound is the source’s own theorem, so a proof would close the two-dimensional case exactly. 7 open	Distributed Discrete Logarithm Generic Group Model Locality Preserving Hashingtight-boundadaptation (ai)
	Optimal martingale gap finders Open for small mu. Settled when mu is bounded away from zero, where the Cleve-Impagliazzo gap finder already gives the conjectured product; for general mu the known bound is a factor mu short and the paper states it does not know the answer. 5 open	Coin Tossinglower-bound
	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)
	Almost k-Wise Locality Gap Settled up to a log n factor at word size 1 and at word size Omega(log^2 n) and above; the source gives no matching construction at all for intermediate word sizes, so the gap is recorded only where both a bound and a construction exist to compare. 4 open	Limited Independence Locally Computable Hashingtight-boundadaptation (ai)
	Conflict Checkable Codes Beyond Half-Singleton Theorem 1.8 proves k <= (n-d+2)/2 for codes that are both comparison-based and local-to-global consistent. Theorem 1.3 gives an almost-MDS conflict checkable code at k >= n-d+1-epsilon which bypasses that bound, but it is neither comparison-based nor known to be local-to-global consistent. The conjecture names comparison-basedness as the culprit. It already holds at d = n-1. 4 open	Code Based Cryptography Locally Testable Codes Threshold Secret Sharingseparationadaptation (ai)
	Constant-Overhead AMD Circuits Polylogarithmic overhead in \|C\| and lambda is achieved by Genkin, Ishai and Weiss; constant overhead is open. The source’s Theorem 43 shows that achieving it would – together with the source’s own constant-overhead OT protocol – settle the main open question on constant-overhead secure computation for general Boolean circuits. 4 open	Fault Tolerant Circuits Oblivious Transfercharacterization
	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
	Degree-2 Statistical RE Question 1.6 of the harvested paper, attributed there to Ishai-Kushilevitz and Applebaum-Ishai-Kushilevitz and described as open for almost 20 years. Degree-3 statistical encodings exist for every finite function; negative results are known for perfectly private degree 2. The harvested paper adds a new consequence, its Proposition 1.7. 4 open	Arithmetic Cryptography Non Interactive Secure Computation Randomized Encodingscharacterizationbarrier (ai)
	Distance from Lines Modulo a Prime Numbered Conjecture 5.37 of the source, described there as a natural but apparently new number-theoretic conjecture whose study may be of independent interest. Nothing is proved about it; the source notes a deterministic variant might be easier to prove and is still useful. 5 open	Oblivious Linear Evaluation Oblivious Transferlower-bound
	Seeded Extractors Are Multi-Instance Posed by the source with both answers live. It proves the property for two code-based extractors via a hinting property it isolates; concurrent independent work of Dinur, Stemmer, Woodruff and Zhou proves it for universal hash functions by a different argument. No extractor is known to fail it and no general proof is known. 4 open	Incompressible Encryption Randomness Extractioncharacterization
	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)
	EA-Code Distance over Rings Theorem 3.10 of the source proves the distance bound over F_2 only. Over a ring of size q its proof technique forces the rate to satisfy R much less than 1/ln q, which the source states it believes is an artefact of the argument, supported by small-parameter weight-distribution experiments over F_17 and Z_16. 5 open	Code Based Cryptography Dual Distance Learning Parity With Noise Pseudorandom Correlation Functionslower-boundadaptation (ai)
	Arithmetic Two-Server PIR Optimality O(n^{1/3}) is achieved by arithmetizing the classical two-server schemes. The source states that whether it can be improved – let alone brought to sub-polynomial – is unknown, and supplies a linear-algebraic characterization of exactly what an improvement would require. 5 open	Arithmetic Cryptography Private Information Retrievaltight-bound
	Polylog Shuffle PIR, Negligible Error Settled in three neighbouring corners: O(n^gamma) communication with inverse-polynomial error and polynomially many queries; polylogarithmic communication with n^{O(log n)} queries; and negligible error with O(n/log n) communication. The polylogarithmic-and-negligible corner with polynomially many queries is open, and is ruled out for inner-outer constructions with an additive inner layer by the source’s own Theorem 6.5. 5 open	Private Information Retrieval Shuffle Modelcharacterizationadaptation (ai)
	RS Proximity Gaps to Capacity Proved up to the Johnson/Guruswami-Sudan bound delta < 1 - sqrt(rho); conjectured up to capacity delta <= 1 - rho - eta. The source records that nothing known contradicts c1 = c2 = 2, and that in characteristic greater than the degree nothing known contradicts c1 = c2 = 1 – while those smaller exponents are provably ruled out in characteristic two. 5 open	Proximity Testing Reed Solomon Codes Snarkstight-boundbarrier (ai)
	PKE from constant-noise planted k-XOR Open: whether public-key encryption can be based on the hardness of planted k-XOR with a linear number of equations and a constant noise rate, as a single assumption. The survey poses it as one of two closing open questions and does not return to it; every combinatorial scheme it surveys needs sub-constant noise.	Average Case Hardness Planted Constraint Satisfactionseparationbarrier (ai)
	Quasi-Abelian GV, Growing Group Named as a conjecture by the source, which says the development is out of reach of the article. It is what makes the choice of group free in the QA-SD line: resistance to every linear test, for any abelian G, reduces to it. Partially advanced in 2026 by concrete non-asymptotic bounds for particular groups, which restate the general question as open. 5 open	Code Based Cryptography Dual Distance Pseudorandom Correlation Functions Syndrome Decodinglower-boundadaptation (ai)
	RM Gap to Capacity for BEC Conjecture 14 of the source. That Reed-Muller codes achieve capacity for the BEC is a theorem of Kudekar et al.; the gap to capacity – a polynomial rate of convergence – is open. The source needs it to strengthen its refutation of the expansion-implies-hardness conjecture for noisy k-XOR from quasi-polynomially many constraints to polynomially many, and notes the question was raised explicitly in three prior works. 4 open	Average Case Hardness Code Based Cryptography Expander Graphs Reed Solomon Codestight-bound
	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
	Statistical Robust ARE The source asks whether all functions admit a statistically secure ARE, robust or non-robust, and strongly conjectures the answer is negative. The non-robust half was refuted: Bitansky, Erabelli, Garg and Ishai construct statistical AREs for all finite functions. The robust half is open, and is re-posed by that later work. 4 open	Additive Randomized Encodings Randomized Encodingscharacterization
	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
	Binary dual-distance bound is the worst case Open, and asserted rather than asked – the source writes that it expects the inequality, gives an intuition covering one of the two competing effects, records that all prior work assumes it, and proves nothing. A probe at small parameters is consistent with it; the parameters the source’s own construction uses are out of computational reach, which is why the source does not check it either. 7 open	Average Case Hardness Dual Distance Learning Parity With Noiselower-boundadaptation (ai)
	Randomness Complexity of XOR The source proves an Omega(t^2) lower bound, matching Kushilevitz and Mansour’s non-explicit O(t^2 log(n/t)) upper bound up to a logarithmic factor, and up to a constant factor when t = Omega(n). It also gives an explicit protocol at O(t^2 log^2 n). It states it leaves the remaining polylogarithmic gaps open. 4 open	Limited Independence Randomness Complexitytight-bound
	Permuted Codes Conjecture A new hardness assumption, printed as Conjecture 3.1 of the source and stated in its most general form deliberately, as a target for cryptanalysis rather than as the minimum its applications need. Implied by the older permuted puzzles conjecture; statistically true for O(log n) samples over constant-size alphabets; false if any one of its three randomizations is dropped. 4 open	Code Based Cryptography Dual Distance Pseudorandom Codes Watermarkingassumptionbarrier (ai)
	MDSD Linear-Test Bias The source proves a non-tight reduction from standard decisional syndrome decoding and separately conjectures that the DOOM algorithm is the best attack; the linear-test bias is the one quantity it states it cannot bound. 5 open	Learning Parity With Noise Shuffle Model Syndrome Decodinglower-bound
	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
	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)
	WP Threshold Share Size The 2-out-of-n case is settled: Beimel and Franklin give 1/n-weakly-private schemes with share size 2, against Theta(log n) for perfect privacy. The source states large thresholds are open and asks specifically about (n-1)-out-of-n at share size o(log n). 5 open	Threshold Secret Sharingcharacterizationadaptation (ai)