Public-Key Encryption from Planted k-XOR at Linear Density and Constant Noise

Statement: AI-written, not yet formalized. Proof: open – no attempt yet.

Statement

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.

Proof

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.

Discussion

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.

Open obligations

• 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.
• Check whether any construction after 2017 reaches constant noise at linear density. This page has not surveyed the literature since the source.