Code Based Cryptography

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

Status	Statement	Tags
	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)
	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)
	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)