Do short certificates exist that a random bipartite graph has no small non-expanding set?

The second assumption under the ABW cryptosystem, and whether it carries structure the first one does not

Motivation

The Applebaum–Barak–Wigderson cryptosystem is the survey’s main example of an attempt to base public-key encryption on the average-case difficulty of a combinatorial problem, a classification the survey itself flags as not well defined. It rests on two assumptions at once, and the second is the unbalanced expansion problem: distinguishing a random bipartite graph with \(n\) left vertices, \(m\) right vertices and right degree \(d\) from one in which a small non-expanding set has been planted.

The question is whether that second assumption is really structureless, or whether the non-existence of a small non-expanding set can be certified short. It matters because a nondeterministic certificate is exactly the kind of structure the survey identifies as the weakness of the geometric family of schemes: a problem with short certificates for both answers sits in \(\mathbf{NP} \cap \mathbf{coNP}\), and the survey’s argument is that schemes whose hardness has that shape are qualitatively unlike generic one-way function candidates.

Provenance and history

Posed in the survey’s own voice as the second of two bulleted open questions closing Section 5.3 (p. 20): “Does the reliance on the unbalanced expansion problem introduce new structure in the problem? For example, is there a nondeterministic procedure to certify the nonexistence of a short non-expanding subset in a graph?”

The survey supplies the observation that makes the question concrete. Reading each right vertex as a linear equation over the variables at its neighbours, a non-expanding set of right vertices yields a set of linearly dependent equations, so the search for a small non-expanding set can be thought of as “the task of looking for a short linear dependency” (p. 20). The implication runs one way only: a dependency need not come from a non-expanding set.

On what is known, the survey says only that expansion problems have been widely studied and that “at the moment no algorithm is known for this range of parameters” (p. 19). It sketches one route to evidence for a negative answer, a worst-case hardness-of-approximation result at matching parameters, and closes by saying it does not know whether such a result is likely to hold (p. 21). Nothing later in the paper returns to the question.

Parameter lattice

axis	values	tracked here
certificate	nondeterministic, sound and average-case complete; deterministic algorithm	nondeterministic certificate
parameters	those used by ABW; arbitrary \((n,m,d,k)\)	ABW’s range
set size	\(k = O(\log n)\); larger \(k\)	\(k = O(\log n)\)
direction	certificate exists; no certificate exists	exists (the source is neutral)

Two cells are known to be uninteresting rather than open. At large enough \(k\), relative to \(m/n\), the distinguishing assumption becomes unconditionally true, which is what makes the certification question vacuous in that regime. And a deterministic algorithm would be a strictly stronger result than the question asks for.