Public-Key Encryption from Planted k-XOR at Linear Density and Constant Noise
Statement: AI-written, not yet formalized. Proof: open – no attempt yet.
View PDF · LaTeX source · Formal statement – not yet formalized
The planted \(k\)-XOR problem at arity \(k\), density \(c\) and noise rate \(\varepsilon\): sample \(m = \lceil cn \rceil\) random XOR equations over \(n\) variables, each on \(k\) of them, then plant an assignment satisfying all but an \(\varepsilon\) fraction. The problem is to find an assignment achieving value at least \(1 - \varepsilon\). This is the standard shape from which private-key primitives fall out cheaply, and it carries no group structure and no geometry.
Conjecture (constant-noise planted \(k\)-XOR suffices for public-key encryption). There exist an integer constant \(k \ge 3\), real constants \(c > 0\) and \(\varepsilon \in (0, 1/2)\), and a correct public-key encryption scheme \(\Pi = (\mathsf{Gen}, \mathsf{Enc}, \mathsf{Dec})\) such that: if the planted \(k\)-XOR problem with parameters \((k, c, \varepsilon)\) is hard, then \(\Pi\) is CPA-secure. The three algorithms must be efficient and correctness must hold unconditionally, so that planted \(k\)-XOR at linear density with constant noise is the only assumption carrying the security of \(\Pi\).
Why the single-assumption clause is not a technicality. The survey’s own combinatorial candidates rest on two assumptions at once (pp. 18–19), so a construction leaning on planted \(k\)-XOR together with a second hardness assumption would not answer the question as posed.
Where the difficulty sits. The survey argues that the noise level, rather than the combinatorial-versus-algebraic distinction, is what separates the two families of schemes: the coding and lattice constructions are broken given an oracle for a problem in \(\mathbf{NP} \cap \mathbf{coNP}\), which is not a problem believed to be easy but is a form of computational structure that generic one-way function candidates lack. Constant noise is precisely the regime in which that structure cannot arise, which is what makes the question interesting and also what removes every known decryption technique.
Sources
- Barak. The Complexity of Public-Key Cryptography. Cryptology ePrint Archive, Report 2017/365. The question is the first of two bullets closing Section 5.3, p. 20, quoted verbatim above; the ABW cryptosystem and its two assumptions are pp. 18–19; the \(\delta k = O(1/\log n)\) decryption constraint is p. 20; Figure 3, p. 15, tabulates the candidate schemes with their noise levels, including Alekhnovich at \(\approx 1/\sqrt{n}\) and ABW Scheme 1 at \(n^{-0.1}\); the \(\mathbf{NP} \cap \mathbf{coNP}\) discussion is p. 14.
View PDF – no proof written yet · LaTeX source – no proof written yet · Formal proof – not yet formalized
Open, in both directions, and the survey takes no position on which way it goes.
What a positive answer would need. A decryption procedure that recovers a plaintext despite a constant fraction of the equations being false. Every combinatorial construction in the survey decrypts by exploiting sparse noise, and the ABW bound \(\delta k = O(1/\log n)\) is a statement about exactly that: the noise must be thin enough that the honest party’s structured view survives it. Nothing in the literature decrypts against constant noise without additional structure.
What a negative answer would need. A separation showing no public-key scheme can be based on this problem alone. The survey offers no route to one here, and its discussion of what would count as evidence concerns the other of its two closing questions rather than this one.
Why constant noise is the whole question. The survey’s own framing is that the noise level, not the combinatorial-versus-algebraic split, is what distinguishes the two families of public-key schemes: it observes that both the knapsack and approximating \(k\)-XOR problems are \(\mathbf{NP}\)-hard, so hardness in the worst case is not what separates them. What separates them is that the coding and lattice constructions carry enough structure to be broken by an oracle for a problem in \(\mathbf{NP} \cap \mathbf{coNP}\). A scheme surviving constant noise would have to decrypt without that structure, which is why a positive answer would be a genuinely new kind of construction rather than a parameter improvement on an existing one.
The relationship to the sibling question. The survey’s second closing bullet asks whether the unbalanced expansion problem, the other assumption ABW’s scheme rests on, admits short certificates of non-expansion. That one is tracked separately at c/0043. The two are independent: a certificate for unbalanced expansion would say something about the structure ABW’s assumption carries, whereas this page asks whether a scheme can be built with no second assumption at all.
What this page does not claim. The survey poses a neutral question and takes no side. The conjecture above states the affirmative because an unconditional negative is not attackable, and that choice of direction is this page’s rather than the source’s.
Checked against the literature, 2026-08-19. Found and read Ghosal–Hair–Jain–Sahai, “Using the Planted Clique Conjecture for Cryptography: Public-Key Encryption from Planted Clique and Noisy k-LIN over Expanders” (STOC 2025 / eprint 2025/1501), whose abstract states verbatim that “Our encryption scheme answers an open question in a seminal work by Applebaum, Barak, and Wigderson [STOC’10]” — the exact ABW paper this page’s source builds on. However, the scheme requires two simultaneous conjectures (planted-clique hardness and a separate noisy k-LIN/expander conjecture), stating explicitly that “neither of these well-studied conjectures… were previously known to imply PKE” and that the combination is what is needed; this page’s own source text disqualifies exactly this shape of answer, since “a construction leaning on planted \(k\)-XOR together with a second hardness assumption would not answer the question as posed.” Also checked “Near Optimal Algorithms for Noisy k-XOR under Low-Degree Heuristic” (arXiv 2604.10457), which requires superlinear density and vanishing noise and so does not attack the linear-density/constant-noise regime either way. Verdict: still open — this is a genuine near-miss, not a resolution.
- Decide whether “base a public-key encryption scheme on” is being read correctly as a single-assumption reduction. The reading is supported by the immediate context, where ABW’s schemes are explicitly said to rest on two assumptions, but the survey does not define the phrase.
- Settle the formalization of the planted problem. The survey gives no formal definition where it asks the question, and its own machinery elsewhere differs from the statement above in three respects: its Definition 2 (p. 6) calls a planted problem hard when no efficient algorithm succeeds with probability at least \(0.9\) rather than with non-negligible probability; its planted-CSP problem (p. 7) asks for value at least \(\mu_D/2 + \mu/2\) rather than \(1 - \varepsilon\); and its Definition 3 (p. 7) uses i.i.d. noise rather than a fixed number of falsified equations. The statement above chooses one formalization and the source does not settle which it intends.