Code Based Cryptography

Cryptosystems built from error-correcting codes, and the structural cryptanalysis that attacks their hidden algebraic structure.

Status	Problem	Tags
	Conflict Checkable Codes Beyond Half-Singleton Theorem 1.8 proves \(k\le(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\ge n-d+1-\varepsilon\) 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)
	EA-Code Distance over Rings Theorem 3.10 of the source proves the distance bound over \(\mathbb{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 \(\mathbb{F}_{17}\) and \(\mathbb{Z}_{16}\). 5 open	Code Based Cryptography Dual Distance Learning Parity With Noise Pseudorandom Correlation Functionslower-boundadaptation (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
	Hold-Out Soundness, Dirty Coordinates The source’s distinguishing attack is unconditional and proved. Its decryption attack is heuristic, and this is the unproved step: completeness on clean coordinates is its Claim 6.2, while soundness on dirty ones is supported only by a heuristic dimension count and small-parameter experiments. 5 open	Code Based Cryptography Private Information Retrievalcharacterization
	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)