Can public-key encryption rest on constant-noise planted k-XOR?

Private-key cryptography uses this hardness freely; every public-key scheme we have needs the noise sub-constant

Motivation

Public-key encryption rests on a famously short list of assumptions. Barak’s survey divides the well-studied schemes into two families: an algebraic one built on Abelian groups (factoring, discrete log, elliptic curves) and a geometric one built on codes and lattices, whose cleanest form is Learning With Errors. Private-key cryptography is in no such position. Candidate one-way functions fall out of almost any sufficiently unstructured average-case problem, and planted constraint satisfaction is the standard example: take random \(k\)-XOR equations over \(n\) variables, plant an assignment satisfying all but an \(\varepsilon\) fraction, and ask for an assignment that does as well.

The question this page tracks is whether that same hardness can carry public-key encryption at constant noise rate and linear density. It matters because the noise level, rather than the algebraic-versus-combinatorial distinction, is where the survey locates the structural weakness of the geometric family: schemes whose noise is small enough are breakable 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 structure that generic one-way function candidates do not have.

Provenance and history

The question is posed in the survey’s own voice, as the first of two bulleted open questions closing its Section 5.3 (p. 20): “Can we base a public-key encryption scheme on the difficulty of solving \(O(n)\) random kXOR equations on \(n\) variables with a planted solution satisfying \(1 - \varepsilon\) of them for some constant \(\varepsilon > 0\)?” Nothing later in the paper returns to it.

The survey’s own reference point is the Applebaum–Barak–Wigderson cryptosystem, which builds public-key encryption from planted noisy linear equations but only when the noise rate is sub-constant: its linear-function variant needs \(\delta k = O(1/\log n)\) for efficient decryption (p. 20). Alekhnovich’s scheme sits at noise \(\approx 1/\sqrt{n}\) (Figure 3, p. 15). So no scheme in the survey reaches the constant-noise regime the question asks about, and the gap is the point of the question rather than an oversight.

Parameter lattice

The axes a resolution could move along, with the cell this page tracks marked.

axis	values	tracked here
noise rate	constant \(\varepsilon\); sub-constant \(O(1/\log n)\); \(\approx 1/\sqrt{n}\)	constant
density	linear \(m = O(n)\); superlinear	linear
arity	\(k \ge 3\) constant; growing \(k\)	constant
goal	public-key encryption; one-way function; commitment	public-key encryption
reduction	single assumption; two or more assumptions	single

The single-assumption cell is what makes the question sharp: ABW’s schemes are explicitly said to rest on two assumptions (pp. 18–19), so a construction leaning on planted \(k\)-XOR plus a second hardness assumption would not settle this.