Short Certificates That a Random Bipartite Graph Has No Small Non-Expanding Set

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

Statement

View PDF · LaTeX source · Formal statement – not yet formalized

An \((n, m, d)\) graph is a bipartite graph with \(n\) left vertices, \(m\) right vertices, and right degree \(d\). Following the source’s Figure 6 (p. 19), call such a graph \(k\)-good if it contains no set \(S\) of \(k\) right vertices whose left-neighbourhood \(\Gamma(S)\) has size \(k - 1\); the planted distribution is the one that inserts exactly such a set.

Conjecture (short certificates for the absence of small non-expanding sets). Let \(d\) be a constant, and let \(m = m(n)\) and \(k = k(n) = O(\log n)\) be the parameters used by the ABW cryptosystem, for which a random \((n,m,d)\) graph is \(k\)-good with probability \(1 - o(1)\). Then for every such \((d, m, k)\) there exists a certification scheme for \(k\)-goodness that is both sound – it never certifies a graph that is not \(k\)-good – and complete on average, certifying a random graph with probability \(1 - o(1)\).

Refuting it means exhibiting parameters in that range for which no sound certification scheme is complete on average.

The reformulation the source supplies, and its direction. Read each right vertex as a linear equation over the variables at its \(d\) left-neighbours. A non-expanding set \(S\) then yields \(|S|\) vectors supported inside a coordinate subspace of dimension \(|S| - 1\), hence a linear dependency among at most \(k\) of the \(m\) vectors, so the search for a small non-expanding set is, in the survey’s phrase, “the task of looking for a short linear dependency”. The implication runs one way only: a short dependency need not arise from a non-expanding set, so the absence of any short dependency would certify \(k\)-goodness, but the converse does not hold and the certificate cannot simply be a dependency count.

Sources

• Barak. The Complexity of Public-Key Cryptography. Cryptology ePrint Archive, Report 2017/365. The question is the second of two bullets closing Section 5.3, p. 20, quoted in full on the problem page; the \((n,m,d)\) graph definition is p. 9; the unbalanced expansion problem and the planted set are p. 19, Figure 6; the linear-dependency observation is p. 20; the remark that no algorithm is known in this parameter range is p. 19; the route to evidence for a negative answer, and the statement that the author does not know whether it holds, are p. 21.

Proof

View PDF – no proof written yet · LaTeX source – no proof written yet · Formal proof – not yet formalized

Open, and the source takes no position on the answer.

Toward a certificate. The linear-algebraic reading gives the target: certify that no \(k\) of the \(m\) sparse vectors are linearly dependent. That is a statement about the minimum distance of the code those vectors generate, and no short certificate for it is known at these parameters either, so the reformulation relocates the difficulty rather than dissolving it. Note this framing is this page’s gloss; the survey stops at the dependency observation and never mentions codes or minimum distance.

Toward a negative answer. The survey’s own suggestion is a worst-case hardness-of-approximation result for unbalanced expansion at parameters matching those the cryptosystem uses, which would be evidence rather than a proof, and it explicitly declines to predict whether such a result holds.

Discussion

Why the question is about structure rather than hardness. A nondeterministic certificate would place the complement of the distinguishing problem in \(\mathbf{NP}\), and the survey’s thesis is that exactly this kind of structure is what separates the schemes it calls geometric from generic one-way function candidates. So an affirmative answer would not break the ABW cryptosystem; it would show that its second assumption is structurally closer to lattices than the combinatorial framing suggests.

The sibling question. The first of the survey’s two closing bullets asks whether public-key encryption can rest on constant-noise planted \(k\)-XOR, tracked at c/0042. The two are independent, and together they ask whether either of ABW’s two assumptions can be improved upon: the first by removing the second assumption entirely, this one by showing the second assumption carries structure.

Direction of the statement. The survey poses a neutral question. The conjecture states the affirmative because an unconditional negative is not attackable; the choice is this page’s, not the source’s.

Open obligations

• The source contradicts itself on the orientation of the planted set, and this page had to choose. Figure 6 on p. 19 plants “a set \(S\) of right vertices of size \(k = O(\log n)\) such that \(|\Gamma_H(S)| = k-1\) where \(\Gamma_H(S)\) denotes the set of left-neighbors of \(S\)”, while the prose bullet on the same page describes “a set \(S\) of size \(k\) of left vertices such that \(S\) has at most \(k-1\) neighbors on the right-hand side”. The statement above follows Figure 6, which is the orientation decryption requires. The paper does not let a reader settle which the author intended.
• Fix the parameter range precisely. The source scopes the question to the parameters ABW uses and gives \(k = O(\log n)\), but does not tabulate the admissible \((m, d)\); the statement above inherits that imprecision rather than inventing bounds.
• Check whether the certification question has been settled since 2017, in the expansion literature rather than the cryptographic one. This page has not surveyed it.