OPTIMAL SMALL-SET EXPANDER GRAPHS AND THEIR CODES
arXiv:2606.23579v1 [math.CO] 22 Jun 2026
TRISTRAM BOGART1 , MARCELO FIORI2 , PEDRO RAIGORODSKY3 , AND MAURICIO VELASCO4 A BSTRACT. A left-regular bipartite graph G of degree d is called a (t, α)-small-set-expander if every subset X of left vertices of size at most t has at least α|X| neighbors. Such a graph is an optimal small-set expander if small subsets have as many neighbors as possible. We characterize optimal expanders combinatorially via girth and prove the existence of s-optimal expanders for every s. We also prove that s-optimality yields new "transfer" lower bounds on the number of neighbors of sets of size h ⩾ s. Finally, as an application, we discuss the use of optimal small-set expanders in building good codes for key exchange protocols in post-quantum cryptography.
1. I NTRODUCTION A bipartite graph G with parts L ⊔ R is left-regular of degree d if every vertex in L has exactly d incident edges. We write n := |L| and m := |R| and associate to any such graph a binary linear code B(G) ⊆ Fn2 defined as ( ) B(G) :=
(x1 , . . . , xn ) ∈ Fn2 :
∑ x j = 0 for all r ∈ R j∈N(r)
where N(z) denotes the set of neighbors of a vertex z ∈ G. Understanding how the combinatorics of the graph G affects the properties of the code B(G) is a very natural question and one of the main sources of interesting subspaces of Fn2 from the point of view of coding theory and its applications. In particular, the following property has played a key role in the development of the interactions between coding theory, theoretical computer science and discrete mathematics since its introduction by Margulis in the late 70s, Definition 1.1. Let α, γ be real numbers. A left-regular bipartite graph G of degree d is called a (γ, α)-expander if every subset X ⊆ L of size at most γn has at least α|X| neighbors. It is known that if G is a suitable expander then B(G) admits extremely efficient decoding algorithms, with decoding radius determined by the expansion parameters. Furthermore it is known that good expander graphs are ubiquitous among sufficiently large graphs. More precisely, it is 1 D EPARTAMENTO DE M ATEMÁTICA , U NIVERSIDAD DE LOS A NDES , B OGOTÁ , C OLOMBIA . ORCID: 0000-
0002-1589-8584 2 I NSTITUTO DE M ATEMÁTICA Y E STADÍSTICA R AFAEL L AGUARDIA , U NIVERSIDAD DE LA R EPÚBLICA , M ONTEVIDEO , U RUGUAY. ORCID: 0000-0002-3732-1778. 3 I NSTITUTO DE E STADÍSTICA (IESTA), U NIVERSIDAD DE LA R EPÚBLICA , M ONTEVIDEO , U RUGUAY 4 C ENTRO DE M ATEMÁTICA , U NIVERSIDAD DE LA R EPÚBLICA , M ONTEVIDEO , U RUGUAY. ORCID : 00000003-4787-7910 E-mail addresses: [email protected], [email protected], [email protected], [email protected]. Key words and phrases. Expander codes, small set expansion, LDPC codes, post-quantum cryptography. 1
2
OPTIMAL SMALL-SET EXPANDER GRAPHS AND THEIR CODES
immediate from our left-regularity assumption that the inequality α ⩽ d holds for every such G and it is natural to ask whether there exist expanders approaching the equality. A Theorem of Sipser and Spielman [5] shows that for every γ ⩽ 1/2 and ε > 0, a uniformly chosen d-regular bipartite graph is a (γ, d(1 − ε))-expander with probability which increases (exponentially) toward one as the number n of left vertices increases to infinity. Furthermore, there exist many deterministic constructions of expander graphs [6, 7], a problem of interest since the earliest works [3, 4]. To the best of our knowledge most constructions aim towards building expander graph families, that is sequences of graphs (Gn )n∈N with vertex size going to infinity which are (γ, α) expanders for fixed parameters γ, α ∈ R. For certain applications, however, this particular asymptotic regime is not necessarily the only useful viewpoint on expanders. We would prefer to vary the number of vertices t in the allowed subsets (letting t be any number, typically smaller than a linear fraction of n) and ask for the smallest number of neighbors any such subset can have, leading to the following finer vector-valued invariant, already featured, although not prominently, in the seminal work [5], Definition 1.2. Let G be a left-regular bipartite graph with parts L ⊔ R. For an integer t ⩽ n we define the t-th expansion constant αG (t) of G as the number |N(X)| : X ⊆ L , 0 < |X| ⩽ t αG (t) := min |X| The aim of this article is to define optimal small-set expanders, those bipartite graphs for which the expansion constants are as large as possible for small sets. We characterize these graphs combinatorially, and give some constraints on the parameter ranges in which they are allowed/guaranteed to exist. As an application we use them to define novel codes potentially useful for code-based cryptography. Our results show that optimality is not only theoretically interesting but also a property capable of yielding some desireable post-quantum security guarantees. More precisely, we begin our investigation by observing that the expansion constants αG (t) satisfy the following simple upper bounds, Lemma 1.3. If G is a left-regular bipartite graph of degree d ⩾ 2 with n ⩾ m then the inequality αG (2) ⩽ d − 1/2 holds. Furthermore if αG (2) = d − 1/2 then for every integer t ⩽ d we have 1 αG (t) ⩽ (d − 1) + . t Motivated by the previous inequality we say that a bipartite d-regular graph G is an s-optimal smallset expander if the expansion constants αG (t) satisfy the opposite inequality αG (t) ⩾ (d − 1) + 1t whenever t ⩽ s, (for a given integer s, which is allowed to be larger than d). Our first Theorem shows that optimality is a surprisingly structural property. Recall that the girth g(G) of a graph is the number of vertices of the shortest simple cycle contained in G. Theorem 1.4. Let G be a left-regular bipartite graph of degree d. For any integer s, with 2 ⩽ s ⩽ n the following properties are equivalent: (1) The inequality g(G) > 2s holds. (2) G is an s-optimal small-set expander, that is αG (t) ⩾ (d − 1) + 1t for every integer t ⩽ s. Requiring for high girth for LDPC Tanner codes has been a well known paradigm in several current constructions (for instance, see [12] for constructions of expanders with girth 8), but the focus
OPTIMAL SMALL-SET EXPANDER GRAPHS AND THEIR CODES
3
tends to be on specific target girths. To the best of our knowledge, the Theorem above formalizes this intuition explicitly for the first time. Further, because girth can be computed in polynomial time, this is a condition that can be checked and even be used as a basis to build expander graphs. It is natural to ask whether s-optimal graphs exist. The following example gives several families of 2-optimal small-set expanders from the line-point incidences of projective spaces over finite fields. Let q denote a pure prime power, let Fq be the unique field of size q and let Pk = Pk (Fq ) be the set of Fq -points in k-dimensional projective space over Fq . By a line in Pk we mean a one-dimensional projective subspace of Pk defined by linear equations with coefficients in Fq . Example 1.5. Fix a positive integer k. Let L be the set of lines in Pk and let R be the set of points in Pk . Let G be the graph with vertex set L ⊔ R and an edge (ℓ, v) if and only if the point v belongs to the line ℓ. The following statements hold: (1) The graph G has the following parameters: symbol value d q+1 k+1 n (q − 1)/(q − 1) k+1 m [(q − 1)(qk − 1)]/[(q − 1)2 (q + 1)] (2) For every t ⩾ 2 the equality αG (t) = (q + 1) − t−1 2 holds and in particular, setting t = 2, we conclude that G is a 2-optimal small-set-expander. The graphs from the previous Example are never 3-optimal. However, our next Theorem gives us a construction of s-optimal small set expanders for every s. Such graphs are obtained by selecting random subgraphs of any sufficiently rich family of 2-optimal expanders such as that of the previous example. The result is an application of the probabilistic method with alterations, which can be implemented computationally: Theorem 1.6. Let (Gk )k∈N be a family of 2-optimal expander graphs with Gk = (Lk ⊔ Rk ; Ek ) having m2
left degree dk and denote nk := |Lk | and mk := |Rk |. Assume nkk is a bounded sequence and mk → ∞. For all s ∈ N, s ⩾ 3 and c ∈ R, c > 1 there is an index k∗ ∈ N such that, for every k ⩾ k∗ the graph Gk contains a bipartite subgraph Ak with parts L(Ak ) ⊔ R(Ak ) satisfying: (1) Ak is left-regular of degree dk (2) |L(Ak )| ⩾ cmk ⩾ c|R(Ak )| (3) Ak is an s-optimal small-set expander. The previous Theorem not only shows existence of s-optimal small-set expanders but also that they are relatively abundant in 2-optimal families. However, the graphs constructed above have a property which is often undesirable for applications: their minimum right-degree is vanishingly small (see Lemma 4.3 for a precise statement). To remediate this problem we study a non-linear selection regime by uniformly choosing a subset of β ⌊cmk ⌋ left-vertices and their right-neighbors (selection phase) and then successively removing all left-vertices of any cycle of length ⩽ s − 1 (alterations phase). We carry out a detailed analysis of the behavior of the minimum right-degree under this process and show in Theorem 4.6 that this β −1 1 quantity is of the same order as the average right-degree mk whenever 1 < β < 1 + s−1 proving
4
OPTIMAL SMALL-SET EXPANDER GRAPHS AND THEIR CODES
a novel concentration result for the right-degrees of such s-optimal expanders with a nonlinear ratio between the left and right parts, which are of interest in applications. Returning to the general theory, it can be shown (see Lemma 3.3) that the number of left vertices n of any s-optimal expander of left-degree d must grow exponentially (at least faster than (d − 1)s ) and therefore s-optimality cannot be expected to hold for too large a value of s for given n. As mentioned earlier, the expansion constants αG (s) control the basic properties of the code B(G) and s-optimality guarantees that they are large when t ⩽ s. With an eye towards applications it is natural to ask whether s-optimality implies lower bounds on the expansion constants αG (h) for larger h. Our next Theorem answers this question affirmatively, allowing us to "transfer" lower bounds on the expansion constants αG (s) for small s to lower bounds for expansion constants αG (h) for larger values of h. This result is especially useful because will be often possible to guarantee s-optimality for small s and then use the Theorem to achieve lower bounds on the expansions constants for h ⩾ s at ranges h in which exhaustive exploration is simply unfeasible. The proof is based on ideas from linear optimization introduced in [2] which we believe are of independent interest. Theorem 1.7 (Transfer bounds on expansion constants). Let G be a left-regular bipartite graph of degree d and let s, h be positive integers with max(s, h) ⩽ n. If h ⩾ s then the inequality h−1 (d − αG (s)) s−1 holds. In particular, if G is an s-optimal small-set expander of left degree d then the inequality αG (h) ⩾ d −
αG (h) ⩾ d −
h−1 s
holds for every h ⩾ s. The graphs of Example 1.5 show that the above inequality is sharp when s = 2 and d = q + 1 for any prime power q. Finally, in Section 6 we discuss an extended application: the usage of s-optimal expander codes for constructing post-quantum key exchange protocols. We give a detailed introduction to the topic and show that s-optimality serves as a guarantee against several common cryptographic attacks on such protocols. The transfer bounds above are used to guarantee the computational feasibility of the exchange procedure in the ranges of interest. These results have convinced us that optimal small-set expanders could be of considerable practical interest. 2. O PTIMAL SMALL SET EXPANDERS AND GIRTH . Proof of Lemma 1.3. Since G is left-regular and has left-degree d, double-counting the total number of edges of G gives the equality dn = ∑r∈R |N(r)|. As a result the average right-degree e satisfies dn/m = e which, because n ⩾ m, implies that there exists a right vertex r∗ for which |N(r∗ )| ⩾ d. Since d ⩾ 2 there must exist a right vertex with at least two distinct left vertices v1 , v2 . A a result |N({v1 , v2 })| ⩽ 2d − 1 and therefore αG (2) ⩽ d − 1/2 as claimed. Assume that αG (2) = d − 1/2 holds. Given t ⩽ d choose t left vertices v1 , . . . , vt among the at least d neighbors of r∗ . Since G is 2-optimal every two left vertices have at most one common neighbor so r∗ is the only intersection point of any subset of the vi of cardinality at least two and we conclude that the number of right-neighbors of the set X := {v1 , . . . , vt } is equal to td − (t − 1). Dividing by |X| = t we conclude that αG (t) ⩽ d − t−1 □ t as claimed.
OPTIMAL SMALL-SET EXPANDER GRAPHS AND THEIR CODES
5
Remark 2.1. The proof shows that the previous inequality holds for all t ⩽ e where e is the largest degree of a right vertex of G. Proof of Theorem 1.4. (1) =⇒ (2) If g(G) > 2s then any nonempty set X of t ⩽ s left vertices defines an induced bipartite subgraph HX with vertices X ⊔ N(X) and having dt edges which connect X with its neighbors in G. Since HX is bipartite, any simple cycle on HX would have at most t vertices contraddicting our assumption on the girth of G. We conclude that HX must have no cycles and thus be a forest. As a result the difference between the number of vertices and edges of HX equals the number of connected components of HX and in particular it is strictly positive because X is nonempty. Explicitly, we have shown that the following inequality holds (|X| + |N(X)|) − d|X| ⩾ 1 or equivalently that 1 |N(X)| ⩾ d −1+ |X| t as claimed proving (2). Conversely, we show (2) =⇒ (1) by verifying that if g(G) ⩽ 2s then G is not s-optimal. If g(C) ⩽ 2s then there exist left vertices X = {v1 , . . . , vt } and right vertices r1 , . . . , rt such that v1 , r1 , v2 , r2 , . . . , vt , rt forms a simple cycle of length 2t for some t ⩽ s. Since each ri is double-counted exactly once when adding the neighborhoods of the vi we conclude that |N(X)| ⩽ dt − t = (d − 1)t so αG (t) ⩽ d − 1 and therefore G is not an s-optimal expander as we wanted to show.
□
Remark 2.2. If G is s-optimal then there may be sets X of size t ⩽ s for which the inequality αG (t) ⩾ d − 1 + 1t is strict. The Euler characteristic computation used in the proof above proves that if the set X has size t and the graph HX has k connected components then the equality k |N(X)| = d −1+ |X| t holds. This observation allows us to compute the expansion constants of s-optimal graphs for t ⩽ s. If G is s-optimal and 0 < t ⩽ s then k t where k is the minimum number of connected components of HX as X ranges over sets of size t. αG (t) = d − 1 +
3. C ONSTRUCTING s- OPTIMAL EXPANDERS FROM 2- OPTIMAL FAMILIES VIA RANDOM SELECTION . We begin by introducing some preliminaries from combinatorics. For a positive integer t, let Dt denote the dihedral group of symmetries of the regular polygon with t vertices labelled 1, . . . ,t. If X is any finite set then the group Dt acts on sequences of t distinct elements of X via σ · (x1 , . . . , xt ) := (xσ (1) , . . . xσ (t) ). The round table orderings of t distinct elements of X, denoted RTO(X,t) is the set of orbits of this action. If we denote the orbit of (x1 , . . . , xt ) by [x1 , . . . , xt ] then [x1 , x2 , . . . , xt−1 , xt ] = [x2 , x3 , . . . , xk , x1 ] and [x1 , x2 , . . . , xt−1 , xt ] = [x1 , xt , xt−1 , . . . , x2 , x1 ]. The class [x1 , . . . , xt ] consists of all placements of
6
OPTIMAL SMALL-SET EXPANDER GRAPHS AND THEIR CODES
x1 , . . . , xt in a round table in such a way that the neighbors of xi are {xi+1 , xi−1 } for every i, where the operations in the subindices are done modulo t. It is immediate that t! |X| |X| (t − 1)! t |RTO(X,t)| = = 2t t 2 because each orbit has the same size as the group since all xi are assumed distinct. We will use round table orderings as a mechanism for cycle counting as follows. Formally, a simple cycle of length t in any graph H is a sequence (v1 , . . . , vt ) of distinct adjacent vertices. However the cycle itself (i.e. the edges) defined by (v1 , . . . , vt ) is the same as the cycle determined by σ · (v1 , . . . , vt ) for σ ∈ Dt and therefore it is natural to count cycles using round table orderings. For an integer t we define the simple cycles of length t in H as Ct (H) := {[v1 . . . vt ] ∈ RTO(V (H),t) : {vi , vi+1 } ∈ E(H)} and the number of simple cycles of length t is the cardinality |Ct (H)| of this set. Lemma 3.1. Let G = (L ⊔ R; E) be a 2-optimal bipartite expander. Fix c ∈ R with c > 1 and n ⩾ ⌊cm⌋. Let H be the random subgraph of G obtained by selecting a set X of ⌊cm⌋ vertices of L uniformly at random and joining them with all their right neighbors in G. If t ⩾ 2 and Z(t) denotes the number of simple cycles of length 2t in H then the following statements hold: (1) The inequality m ⌊cm⌋ (t − 1)! t t E[Z(t) ] ⩽ n 2 t holds, and (2) If both m and n are large when compared to t then the upper bound in (1) has the same asymptotic behavior as t ct m2 2t n Proof. If [ℓ1 , r1 , . . . , ℓt , rt ] ∈ C2t (G) with {ℓ1 , . . . , ℓt } ⊆ L and {r1 , . . . , rt } ⊆ R then both sets have t distinct elements and the class [r1 , . . . , rt ] ∈ RTO(R,t) is well defined. Since G is 2-optimal the vertex ℓi ∈ L is the unique vertex of G simultaneously adjacent to ri and ri+1 (with addition mod t) and therefore the class [r1 , . . . , rt ] determines [ℓ1 , r1 , . . . , ℓt , rt ] uniquely. We conclude that the inequality |C2t (G)| ⩽ |RTO(R,t)| holds. The random variable Z(t) is given by Z(t) =
∑
1{ℓ1 ,...,ℓt }∈X
[ℓ1 ,r1 ,...,ℓt ,rt ]∈C2t (G)
and therefore E[Z(t) ] = |C2t (G)|P{Any fixed t-subset of L belongs to X}. Since the selection of X is done uniformly at random the probability term equals inequality |C2t (G)| ⩽ |RTO(R,t)| proved in the previous paragraph we conclude that m ⌊cm⌋ ⌊cm⌋ (t − 1)! t t t E[Z(t) ] ⩽ |RTO(R,t)| n ⩽ n 2 t t
(⌊cm⌋ t ) . By the n (t )
OPTIMAL SMALL-SET EXPANDER GRAPHS AND THEIR CODES
7
proving (1). For the asymptotics we assume that both n and m are large and t is fixed so we can t approximate binomials via expressions of the form mt ∼ mt! yielding t t m ⌊cm⌋ mt (cm) (t − 1)! t (t − 1)! ct m2 t t! t! ∼ = n nt 2 2 2t n t t! as claimed in (2).
□
We are now ready to prove the main result of this Section. Proof of Theorem 1.6. Let c′ = 2c. Our assumptions on the sequences mk , nk and the asymptotics from Lemma 3.1 part (2) ensure that there exists an index k1 such that k ⩾ k1 implies that the following inequality holds t m ⌊c′ mk ⌋ s s (c′ )t m2k (t − 1)! t k t ⩽2∑ ∑ 2 nk nk t=3 2t t=3 t and that the right-hand side is bounded by a constant M for all such k. Furthermore, because mk → ∞ and c > 1 there exists k2 such that k ⩾ k2 implies c′ mk − sM ⩾ cmk . We claim that if k∗ = max(k1 , k2 ) then for every k ⩾ k∗ there exists an s-optimal expander Ak ⊆ Gk satisfying the conclusions stated in the Theorem, and we will prove it by using the probabilistic method with alterations. If Hk is the random subgraph of Gk obtained by selecting a set Xk of ⌊c′ mk ⌋ vertices of Lk uniformly at random and joining them with all their neighbors in Gk and Y (k) is the random variable counting the number of simple cycles of length 3 ⩽ t ⩽ s in Hk then, using the notation of Lemma 3.1 s we have Y (k) := ∑t=3 Z(t,k) where Z(t,k) denotes the number of simple cycles of length 2t in Hk and therefore m ⌊c′ mk ⌋ s (t − 1)! t k (k) t ⩽M E[Y ] = ∑ nk 2 t=3 t so there must exist at least one realization of Hk which we denote Bk ⊆ Gk having at most M such cycles. Since every cycle has at most t ⩽ s left vertices, we can remove all left-vertices of Bk involved in any such cycle and let Ak be the subgraph of Bk consisting of the remaining left vertices together with all their neighbors in Gk . Since Bk has c′ mk vertices the graph Ak has at least c′ mk − sM ⩾ cmk vertices and each of them has left-degree dk . The graph Ak has no cycles of length ⩽ 2s, because we have removed them, and is therefore s-optimal as claimed. □ The previous proof yields us an algorithm to be used to generate such graphs, as is standard when applying the probabilistic method with alterations. More precisely, Algorithm 3.2. INPUT: G = (L ⊔ R, E) left d-regular, 2-optimal bipartite expander; s ∈ N, s ⩾ 3; N ∈ N with N ⩽ |L|. OUTPUT: G′ = (L′ , R) left d-regular, s-optimal bipartite expander. (1) Generate L′ a random subset of L of size N. (2) G′ := (L′ ⊔ R, EL′ →R ) the induced subgraph. (3) While g(G′ ) ⩽ 2s do: (4) C := shortest cycle of G′ . Denote {ℓ1 , . . . , ℓ j } all left nodes of C.
8
OPTIMAL SMALL-SET EXPANDER GRAPHS AND THEIR CODES
(5) L′ := L′ \{ℓ1 , . . . , ℓ j }. (6) G′ := (L′ ⊔ R, EL′ →R ) (7) Return G′ Naturally, without control of the number of short cycles, our algorithm can completely destroy G. However, we have shown that with high probability - in the context of Theorem 1.6 - this algorithm will generate a desired graph provided k is large enough. Also note that because we are always computing the shortest cycle, we always eliminate chordless cycles, so each iteration will only remove at most sd edges, and the right degree of each node in the cycle will decrease by exactly 2. This gives our algorithm stability properties that will be useful in Section 4. Our next result is about the limits of s-optimality. We show that any s-optimal small-set expander of degree d must have a number of vertices which grows exponentially in s, more precisely j Lemma 3.3. If G is an s-optimal expander of left-degree d with n ⩾ m then n ⩾ ∑s+1 j=0 (d − 1) .
Proof. Double-counting edges we have dn = me where e is the average right-degree and therefore the average degree d of our graph G is at least d. By Theorem 1.4 G is s-optimal implies g(C) ⩾ 2(s + 1) Alon, Horray and Linial prove in [8][Section 2] that if G = (L ⊔ R; E) is a bipartite graph with average degree d and girth g(G) = 2t then the inequality s+1
|L| + |R| ⩾ 2 ∑ (d − 1) j j=0
from which the claimed inequality s+1
2n ⩾ 2 ∑ (d − 1) j j=0
□
follows. 4. O N THE BEHAVIOR OF RIGHT- DEGREES
A right-vertex r ∈ R(G) with e neighbors determines a dual word of weight e, that is an equation satisfied by all words of B(G), namely ∑ j∈N(r) x j = 0. The existence of dual words of small weight is a natural source of cryptographic attacks on B(G) and is therefore natural to ask for lower bounds for the minimum right-degree of any expander. In this Section we focus on deriving such bounds for expanders built via random selection and alteration from 2-optimal families. Our first result generalizes Theorem 1.6. It constructs s-optimal expanders by a random selection β of left vertices which scales like cmk for any value of a new parameter β which satisfies the inequality 1 1 ⩽ β < 1 + s−1 and then modifies the resulting subgraph to remove short cycles. Although the result looks similar to Theorem 1.6, we will see that the behavior of the minimum right-degree of the resulting s-optimal expanders Ak is radically different when β = 1 (linear) and β > 1 (non-linear) case. More precisely it will turn out that as k → ∞, the minimum right-degree goes to zero when β −1
β = 1 while it is bounded below by
dcmk 2
with probability going to one.
Theorem 4.1. Let (Gk )k∈N be a family of 2-optimal expander graphs with Gk = (Lk ⊔ Rk ; Ek ) having m2
left degree dk . Let nk := |Lk | and mk := |Rk |. Assume that the sequence nkk is bounded and that 1 mk → ∞. For all t ∈ N, t ≥ 3, all c ∈ R with c > 1, and all β ∈ R with 1 ⩽ β < 1 + s−1 , there exists
OPTIMAL SMALL-SET EXPANDER GRAPHS AND THEIR CODES
9
an index k∗ ∈ N such that, for every k ≥ k∗ , the graph Gk contains a bipartite subgraph Ak with parts L(Ak ) ⊔ R(Ak ) satisfying: (1) Ak is left-regular of degree dk ; β (2) |L(Ak )| ≥ cmk ≥ c|R(Ak )|β ; (3) Ak is an s-optimal small-set expander. Proof. If G is any 2-optimal graph and H be a random subgraph of G obtained by selecting a set of vertices X ⊆ L with |X| = ⌊cmβ ⌋ and joining them with all their right neighbors in G. If t ⩾ 2 and Z(t) denotes the number of cycles of length 2t in H, then arguing as in Lemma 3.1 we have m ⌊cmβ ⌋ (t − 1)! t (β −1)t t E[Z(t) ] ⩽ = O m n 2 t Where the last equality holds if n ∼ m2 . Now assume the (Gk )k∈N are a 2-optimal family as above. Pick c′ = 2c. Following the same steps of the proof of Theorem 1.6, it suffices to show that there exists k∗ ∈ N such that if k ⩾ k∗ , then c′ mk − sE[Y (k) ] > cmk . β
β
To prove this recall that s
Y (k) = ∑ Z(t,k) t=3
is the total number of cycles of length at most 2s in the random subgraph Hk of Gk obtained by β selecting a set Xk = ⌊c′ mk ⌋ vertices from Lk and joining them with their neighbors in Rk . 1 The condition β < 1 + is equivalent to (s − 1)(β − 1) < 1. Therefore, s−1 s (t−1)(β −1) (s−1)(β −1) β E[Y (k) ] = ∑ O mk = O mk = O mk .
t=3 ∗ Hence, there exists k large enough such that for all k ⩾ k∗ ,
(c′ − c)mk ⩾ sE[Y (k) ], β
□
as claimed.
1 Remark 4.2. We observe that this exponent (β = 1 + s−1 ) is in fact optimal. Following the arguments for Moore bounds in irregular graphs (see [9, pags. 54-57], or laid out explicitly in [11]), it follows that for any family G′k = Lk′ ⊔ R′k of s-optimal, left d-regular bipartite graphs we have that 1
|Lk′ | ≲ |R′k |1+ s−1 . Indeed, if d, dR are the average left and right degrees respectively, the leading-order growth in the Moore bound argument yields d |R′k | ≳ d s dRs−1 = d s ·
s−1 |L′ |s−1 k , |R′k |s−1
and the argument concludes by isolating |Lk′ |. This is relevant because in general we want the left-to-right ratio to be large in the context of coding theory, since for instance it will maximize the average right degree (see section 6). It is also worth noting that the same exponent can be reached by following the cycle removal argument on random left d-regular graphs, although naturally we have less control over the structural properties of these expanders.
10
OPTIMAL SMALL-SET EXPANDER GRAPHS AND THEIR CODES
To capture the behavior of the minimum right-degree we separate our analysis into two parts. In the first Lemma we focus on the behavior of this quantity under random selections and on the key dichotomy between the linear β = 1 and nonlinear β > 1 cases. For each r ∈ Rk let d0 (r) denote the right-degree of the vertex r in the random subgraph obtained by uniformly choosing a subset of left vertices and all their neighbors and let d0∗ := minr∈R d0 (r). First we study the minimum right degree during the left node selection (ignoring, for now, the alterations phase) from a 2-optimal family which is regular on both sides, Lemma 4.3. Let (Gk )k∈N , Gk = (Lk ⊔ Rk , Ek ) be a family of 2-optimal, d-left regular and δ -right 2 2 regular graphs such that j |Lk | k= nk ∼ mk = |Rk | . For each k, let Xk ⊆ Lk be a uniformly chosen β
random subset of size c · mk < nk and let Hk be the induced bipartite subgraph with vertices Xk ⊔ N(Xk ). The following statements hold, (1) If β > 1, then for all a < c · d we have β −1 lim Pr d0∗ ⩾ a · mk =1 k→∞
(2) If β = 1 then the random variable d0∗ converges to zero in probability as k → ∞. Proof. Let r ∈ Rk be any right vertex. Since the set Xk is selected uniformly at random, the random variable d0 (r) will have value j when exactly j of the δ neighbors of r belong to the random subset Xk . Because the set is selected unifornly at random this random variable has hypergeometric β distribution with population size N = nk , having M = ⌊cmk ⌋ successes and D = δ trials. The mean cm
β
β −1
of this distribution is the quantity D(M/N) = δ nkk = c · d(mk ) =: µk To prove (1) recall that the Chernoff bound states that for any positive η > 0 the hypergeometric distribution satisfies η2 P {d0 (r) ⩽ (1 − η)µk } ⩽ exp − µk 2 From this and the union bound, it follows that if β > 1 then for any η > 0 we have η2 k→∞ ∗ P{d0 ≤ (1 − η)µk } ≤ ∑ P{d0 (r) ≤ (1 − η)µk } ≤ mk exp − µk −−−→ 0. 2 r∈Rk proving the claim by an appropriate selection of η. To show (2) observe that if dc < 1, then there must exist some isolated r ∈ Rk following the selection, because dc is precisely the average right degree, so the result holds trivially (in fact, the minimum degree is 0 always). So we assume dc ⩾ 1. Let Ir := 1{d0 (r)=0} be the random variable which indicates that r is an isolated vertex and let χk = ∑r∈Rk Ir . If β = 1 then µk is asymptotically constant to c · d and the random variables d0 (r) have the same distribution for every r ∈ Rk and in particular have a positive probability of being identically zero. This probability can be easily estimated from the poisson approximation to the ˙ hypergeometric distribution to be e−cd and it follows that E[χk ] ∼ mk e−cd so the expected value of χk diverges as k → ∞. However, this is not enough to conclude that d0∗ = 0 in probability because of correlations (for a counterexample imagine the case in which all the random variables d0 (r) not only have the same distribution but are copies of the same random variable). We claim that we can bound k) the covariance terms well enough so as to ensure that the ratio Var(χ → 0 as k → ∞. This is useful E[χ ]2 k
OPTIMAL SMALL-SET EXPANDER GRAPHS AND THEIR CODES
11
because by Chebyshev’s inequality, 1 4 Var(χk ) Pr |χk − E[χk ]| ≥ E[χk ] ≤ → 0. 2 E[χk ]2 Hence with probability tending to 1, χk ≥ 21 E[χk ] ∼ 12 e−cd mk and in particular, P(χk ≥ 1) → 1 as claimed. We now bound Var(χk ). We have Var(χk ) = ∑ Var(Ir ) +
Cov(Ir , Ir′ ). ∑ ′
r∈Rk
r,r ∈Rk r̸=r′
(k)
Since Ir is Bernoulli with parameter p0 we have (k)
∑ Var(Ir ) ≤ mk p0 = E[χk ].
r∈Rk
For the covariance, fix two distinct right vertices r ̸= r′ . The event Ir = 1 means that none of the left neighbors of r are selected in Xk . Let N(r) denote the set of left neighbors of r. Because Gk is 2-optimal, we have |N(r) ∩ N(r′ )| ≤ 1, and hence |N(r) ∪ N(r′ )| = 2δ − y,
y ∈ {0, 1}.
We will show that Cov(Ir , Ir′ ) = O(1/mk ). We will assume that y = 1, and the other case works exactly the same. It is known that the total variation distance between a hypergeometric H (M, D, N) and a binomial distribution Bi(M, D/N) is O(M/N) (see [10, Theorem 1, Lemma 2]) provided M · (D/N)(1 − D/N) ⩾ 1. Here M = cmk , D = dnk /mk and N = nk , so the condition holds for large enough k since dc ⩾ 1. It follows that δ cmk δ cmk + O(cmk /nk ) = 1 − + O(1/mk ) Pr(Ir = 1) = 1 − nk nk Similarly, 2δ − 1 cmk Pr(Ir = 1, Ir′ = 1) = 1 − + O(1/mk ) nk Now we use that (1 + a/x)x = ea + O(1/x). Because c · mk δ /nk = cd, and also nk /δ = d1 · mk we have, (nk /δ )·cmk ·δ /nk 1 Pr(Ir = 1) = 1 − +O(1/mk ) = (e−1 +O(d/mk ))cmk δ /nk +O(1/mk ) = e−dc +O(1/mk ) nk /δ where the last equality holds since dc > 1. Similarly, Pr(Ir = 1, Ir′ = 1) = e−2cd + O(1/mk ) We have thus shown that Cov(Ir , Ir′ ) = Pr(Ir = 1, Ir′ = 1) − Pr(Ir = 1)2 = e−2cd + O(1/mk ) − (e−cd + O(1/mk ))2 = O(1/mk )
12
OPTIMAL SMALL-SET EXPANDER GRAPHS AND THEIR CODES
and therefore, 2 1 ∑′ Cov(Ir , Ir′ ) = O mk · mk = O(mk ). r̸=r Since E[χk ] ∼ mk , combining all of the above we have 1 Var(χk ) = O → 0. E[χk ]2 mk □ 1 Finally, for the nonlinear case 1 < β < 1 + s−1 we show that the alterations do not affect our conclusion too substantially. Recall that the removal of each cycle decreases the degree of the right vertices of the cycle by two and is therefore possible that if a right-vertex r belongs to many such cycles, its degree decreases significantly after cycle removal dragging down the minimum degree. The key point however is that the removal of a cycle implies the removal of all its left vertices and thus the alterations phase of the algorithm will only effectively remove a left-vertex-disjoint subset of all the cycles through r. The following Lemma shows that the probability of removing a fixed fraction of the expected degree from any right vertex vanishes asymptotically,
Lemma 4.4. Let (Gk )k∈N be a family of d-left regular 2-optimal bipartite graphs such that nk ∼ m2k . β 1 Let Xk ⊆ Lk be chosen uniformly at random of size ⌊cmk ⌋ where c > 0 and β > 1. If 1 < β < 1 + s−1 then for any η > 0 the probability that any execution of the alterations phase of Algorithm 3.2 β −1 removes at least 2ηmk edges from any right vertex r vanishes as k → ∞. Proof. For a vertex r ∈ Rk and an integer j let N j (r) be the event that Xk ⊇ A for some set A which is a union of the left-vertices of a collection of j left-vertex disjoint cycles with lengths in the interval [6, 2s]. We study the sets N j (r) because every execution of the algorithm in which the degree of r drops by at least 2 j in the alterations phase requires the removal of a set A of j left-vertex disjoint cycles with A ⊆ Xk . This is because the algorithm removes a cycle by removing its edges and all its left-vertices, so it will only remove other pairs edges coming out of r if their corresponding cycles are left-vertex disjoint. It follows that P(N j (r)) is an upper bound on the probability that our algorithm decreases the right-degree of r by 2 j or more. We will derive an upper bound on its probability via a union bound over the possible A’s. More precisely if bi denotes the number of cycles of size 2i in such a collection then the set A has size a = ∑si=3 ibi , j = ∑si=3 bi and nk −a β
P{Xk ⊇ A} =
cmk −a nk β cmk
and furthermore the number of such collections is bounded above by s i−1 m ∏ bki i=3 because by 2-optimality, the number of cycles of length 2i containing r is bounded above by the number of right-vertex sequences containing r namely mi−1 and we select bi such sequences for k
OPTIMAL SMALL-SET EXPANDER GRAPHS AND THEIR CODES
13
each i. By the union bound we thus conclude that nk −a s i−1 β mk cmk −a j P(N (r)) ⩽ nk bi β i=3 (b3 ,...,bs ):∑i bi = j cmk
∑
∏
β −1
We analyze the asymptotic behavior of this quantity as k → ∞ when j ⩽ ηmk . In particular β s 2 ∑3i=3 bi = j implies that bi ≪ mi−1 k while a = ∑i=3 ibi implies that a ⩽ s max(bi ) ≪ mk ≪ mk . These inequalities allow us to use the following standard approximations to binomial coefficients, nk −a ! i−1 β a bi β (mi−1 cmk mk cmk −a k ) and ∼ ∼ nk bi bi ! m2k β cmk
It turns out the resulting asymptotic expression can be computed explicitly and has a particularly i(β −1)−1 simple form. By letting pi := ci mk for i = 3, . . . , s and pi := pi /p where p = ∑si=3 pi we can write ! β a s bi cmk (mi−1 1 j k ) pbi i = = ∑ ∑ ∏ ∏ 2 b , b , . . . , b b ! j! mk i s 3 4 i=3 (b3 ,...,bs ):∑i bi = j (b3 ,...,bs ):∑i bi = j j pj pj = pi bi = ∑ ∏ j! (b ,...,b ):∑ b = j b3 , b4 , . . . , bs j! 3
s
i i
where the last equality occurs because the sum of the bi runs over all nonnegative indices summing to j and the multinomial is a probability distribution so its probability mass function sums to one. β −1 Finally, we will use the fact that j = ηmk to prove that the probability goes to zero as k → ∞. By Stirling’s inequality 1/ j! ⩽ ( ej ) j !j j pj ep s e (s−1)(β −1)−1 ⩽ ⩽ c mk β −1 j! η ηm k
which decreases exponentially as mk → ∞ because the exponent (s − 1)(β − 1) − 1 < 0 by our 1 assumption that β < 1 + s−1 . Since the decrease is exponential in mk the same is true if one sums 2 over all the mk right vertices r completing the proof of the Theorem. □ Remark 4.5. The previous proof also shows that whenever the stricter condition 1 < β < 1 + 1s holds the probability that likelihood that any right vertex is altered more than once vanishes (case j = 2). Consequently, under this condition, the final degree distribution should be almost identical to the hyper-geometric in the asymptotic case. Theorem 4.6. Let (Gk )k∈N , Gk = (Lk ⊔ Rk , Ek ) be a family of 2-optimal, d-left regular and δ 2 2 right regular graphs such that j |Lk | = k nk ∼ mk = |Rk | . For each k, let Xk ⊆ Lk be a uniformly β
chosen random subset of size c · mk < nk , let Hk be the induced bipartite subgraph with vertices Xk ⊔ N(Xk ) and Tk the subgraph resulting from successively removing all the left-vertices of some cycle of size ⩽ 2s. The minimum right-degree dT∗k of Tk satisfies 1 β −1 ∗ lim Pr dTk < d · cmk =0 k→∞ 2
14
OPTIMAL SMALL-SET EXPANDER GRAPHS AND THEIR CODES
Proof. Follows from combining the conclusions of Lemma 4.3 and Lemma 4.4.
□
5. T RANSFER BOUNDS FOR EXPANSION CONSTANTS Suppose that either from theory or from exhaustive exploration we obtain a lower bound on one expansion constant αG (s) and ask whether this leads to improved lower bounds on αG (h) for larger sets, of size h ⩾ s. Our main result is that this is indeed the case. We call the resulting inequalities transfer bounds since expansion is transferred from smaller to larger sets. We begin with some preliminary notions. If X ⊆ L is any set of size h, we let HX denote the bipartite subgraph of G with vertices X ⊔ N(X) and all edges of G starting at points of X. Each right vertex of HX has a degree ⩽ h and the sequence of right-degrees is summarized by the sequence of integers (β1 , . . . , βh ) with β j := |{r ∈ N(X) : r has degree j in HX }| . It is immediate that |N(X)| = ∑hj=1 β j and, by double-counting the edges of HX , that the equality ∑hj=1 jβ j = dh holds. The results in this Section depend on the crucial insight, introduced in [2] that knowing the expansion constants of smaller sets leads to additional linear inequalities that the β j must satisfy for any set X of size h allowing us to use tools from linear optimization to derive bounds for αG (h). More precisely, Lemma 5.1. Let s, h be positive integers with s ⩽ h and for j = 1, . . . , h define p j := 1 − γ ∗ (h) is the optimal value of the linear optimization problem ( h
min
x∈Rh
then the inequality αG
h
h
(h−s j) . If (hs)
)
∑ xi : x j ≥ 0, ∑ x j p j ≥ sα(s), ∑ jx j = dh .
i=1
j=1
j=1
(h) ⩾ γ ∗ (h)/h holds.
Proof. Suppose X ⊆ L is any subset of size h and let (β1 , . . . , βh ) be the right-degree counts of HX as in the previous paragraph. We want to estimate the average number of right neighbors of a subset S ⊆ X of size s if the set is chosen uniformly at random. So, " # E[|N(S)|] = E
∑ 1r∈N(S) = ∑ P{r ∈ N(S)} r∈N(X)
r∈N(X)
Since S is chosen uniformly at random this probability is completely determined by the right-degree (h− j) of r. If r has right-degree j then the probability is p j := 1 − hs because r ̸∈ N(S) precisely when (s) S is entirely contained in the set of h − j elements of X that are not neighbors of r. We conclude that h
E[|N(S)|] = ∑ p j β j j=1
and, because the average is always bounded below by the minimum, that the inequality h
αG (s)s ⩽ E[|N(S)|] = ∑ p j β j j=1
OPTIMAL SMALL-SET EXPANDER GRAPHS AND THEIR CODES
15
holds proving that (β1 , . . . , βh ) is a feasible point of the above optimization problem. It follows that |N(X)| = ∑hj=1 β j ⩾ γ ∗ (h) proving that αG (h) ⩾ γ ∗ (h)/h since X was an arbitrary set of size h. □ We are now ready to prove the main result of this section. In the proof we will make repeated use of the binomial identity n n−1 n−1 = + . k k−1 k Proof of Theorem 1.7. The dual of the linear programming problem in Lemma 5.1 is equivalent to the following two-dimensional problem max η1 (sα(s)) + η2 (dh) : η1 p j + η2 j ⩽ 1 for j=1,. . . , h (η1 ,η2 )∈R2 ,η1 ⩾0
First we will show that the point (η1∗ , η2∗ ) where the first two inequalities are active, that is the solution of the linear system ( η1∗ p1 + η2∗ 1 = 1 η1∗ p2 + η2∗ 2 = 1
is a feasible point of the dual. Solving the linear system we conclude that η1∗ := 2p11−p2 and that p1 −p2 ∗ = h / h−2 and in particular that it is a η2∗ := 2p . The binomial identity above implies that η 1 s s−2 1 −p2 positive number. Furthermore we claim that for every j ⩾ 2 the inequality η1∗ p j+1 + η2∗ ( j + 1) < η1∗ p j + η2∗ j holds, finishing the proof of feasibility. This inequality is equivalent to the inequality p2 − p 1 = −
η2∗ > p j+1 − p j . η1∗
j−1 h Since p j+1 − p j = h−s−1 / s this inequality is in turn equivalent to h−2 h − ( j + 1) > s−1 s−1
which clearly holds because j ⩾ 2. Since the value of the dual objective function at any feasible point of the dual is a lower bound on the optimal function of the primal we conclude that αG (h)h ⩾ η1∗ (sα(s)) + η2∗ (hd). We complete the proof by evaluating the right-hand side. Simplifying the binomial ratios above we s−h ∗ see that η1∗ = h(h−1) s(s−1) and η2 = s−1 . Dividing both sides of the previous inequality by h we conclude that s−h h−1 h−1 αG (h) ⩾ d + αG (s) = d − (d − αG (s)) s−1 s−1 s−1 as claimed. For the final inequality, if G is s-optimal then we apply the transfer inequality we just showed with αG (s) = d − 1 + 1s obtaining h−1 1 h−1 αG (h) ⩾ d − −1 + =d− s−1 s s as claimed.
□
16
OPTIMAL SMALL-SET EXPANDER GRAPHS AND THEIR CODES
∗ ∗ ∗ t ∗ Remark 5.2. The complementary slackness conditions λi xi = 0, η1 (p x − sα(s)) = 0 and η2∗ ∑ jx∗j − hd = 0 imply that setting x∗j = 0 for j ⩾ 3 and defining (x1∗ , x2∗ ) as the solution of the system of equations ( x1∗ + 2x2∗ = hd x1∗ p1 + x2∗ p2 = sαG (s) leads to an optimal solution of the primal problem with the same objective function as the point (η1∗ , η2∗ ) showing that it is not only feasible but in fact optimal for the dual.
6. P OST- QUANTUM KEY EXCHANGE AND OPTIMAL EXPANDERS In this Section we develop an extended application of small-set expanders. We begin by recalling some preliminaries from coding theory and cryptography. As in the introduction, let B(G) denote the binary code defined by a bipartite graph G = L ⊔ R which is left-regular of degree d. The following Lemma summarizes well-known results of Sipser and Spielman for the code B(G), rephrased in terms of the expansion constants of G. Lemma 6.1. The following statements hold for any integer h with 0 < h < n: (1) If αG (h) > d2 then h is a lower bound on the minimum distance of B(G). h (2) If αG (h) > 3d 4 then the Sipser-Spielman bit flipping algorithm can correct any 2 errors in linear time. Proof. Part (1) is [5][Theorem 7].(2) follows from the proof of [5][Theorem 10].
□
Remark 6.2. The bit-flipping algorithm is so simple that we cannot resist giving a brief description. Given w = (x1 , . . . , xn ) ∈ Fn2 we carry out the following procedure: (1) Find a variable xi ∈ L that has strictly more unsatisfied than satisfied constraints and flip its value (replacing xi by 1 + xi in F2 ). (2) Repeat until no such variable remains. If w = c + e where c ∈ B(G) and e has weight ⩽ h/2 then the algorithm is guaranteed to recove c whenever αG (h) > 3d 4 . Furthermore, this algorithm runs in linear time (a consequence of [5][Theorem 10]). Next we will use transfer inequalities and the above guarantees to argue that the codes derived from s-optimal expanders are potentially useful in code-based cryptography. We begin with a description of the basic problem and then prove Theorem 6.5 which contains the main application. We will now Alice and Bob wish to exchange data securely over an open channel. They can easily do so using established symmetric encryption protocols provided they both know a very large integer K, which we refer to as the shared key, to be used by both parties during symmetric encoding and decoding. Note however that any third party with knowledge of K could easily read the communications between Alice and Bob. A key-sharing protocol is a mechanism through which Alice and Bob generate a shared K securely while communicating only through the open channel. More specifically, the following protocol is a Niederreiter-style code-based KEM, following the general paradigm used in modern code-based cryptography such as BIKE [1]: (1) Alice constructs a left-regular bipartite graph with parameters (n, m, d) via its parity-check m × n matrix H. She also constructs and a random invertible m × m matrix S. Alice publishes the product R := SH and keeps the pair (S, H) secret.
OPTIMAL SMALL-SET EXPANDER GRAPHS AND THEIR CODES
17
(2) Bob generates (uniformly at random) an error vector e with support size t. Bob publishes c := Re and the support size t, and keeps the vector e secret. (3) Alice reads c, computes S−1 c = He and uses the error-correction algorithm for the code H to recover the vector e. (4) If step (3) is successful then both Alice and Bob know c and e and can independently compute the key K := Hash(c; e) where Hash is any previously established hash function. Remark 6.3. An eavesdropper who has access to all communications between Alice and Bob would have to be able to compute e from c and R in order to obtain the key. The eavesdropper must try to do so knowing only the "scrambled" version R of the code H. It is known that finding the nearest vector in a subspace V ⊆ Fnq to a given vector w is a difficult computational problem if V is sufficiently generic [14][Sect-III] . The hope is that the scrambled code resembles, in the eyes of an eavesdropper, a generic code sufficiently so that decoding becomes difficult. The key exchange above reached NIST PQ level three [1] as post-quantum cryptography alternative candidate, meaning that it is currently believed to be safe, for a suitable choice of code, even if the eavesdropper is in possession of a quantum computer. There are a few standard attacks that an eavesdropper could use. Their aim is to recover e from c and R and thus capture the key K. (1) Brute force attack. The attacker selects a possible support set X uniformly atrandom, defines y := ∑ j∈X e j and verifies whether Ry = c. The probability of success is 1/ nh so the expected number of attempts before success is nh ∼ 2h log2 (n/h) . (2) Information set decoding. From the public knowledge of R the attacker can compute the dimension k of the code. The attacker selects a random support set I ⊆ [n], |I| = k and attempts to solve the restricted linear system RI y = s where RI is the restriction of the matrix R to the columns indexed by I. If I is an information set (i.e. if RI is invertible) then supp(e) ⊆ I implies y = e. It follows that the success probability of a given information set I is given by hk / nh ∼ 2−h log2 (n/k) so the expected number of attempts before success of this strategy is of the order of 2h log2 (n/h) . (3) Low weight dual constraints attack. The code is obscured via left multiplication by the random invertible matrix S. This obfuscation method however, leaves the dual code C⊥ exposed, where C⊥ := v ∈ Fn2 : ∀x ∈ C vt x = 0 because C⊥ = rowspan(H) = rowspan(R) (see [13][Ch.5]). If λ t R = v ∈ C⊥ is a dual word of low weight then e must satisfy the linear equation ve = λ t c and it is possible to use such equations to decrease the complexity of brute force attacks by searching exhaustively over the part of e with the same support as the short dual words and then piecing together e gradually from these pieces. Although a useful general theoretical description of the dual code is still lacking, certain general rules are practically advisable to mitigate these attacks: The graph should have comparatively large minimum right-degree and few short cycles, because violating either of these conditions would lead to dual words of small weight. In any case scrambling by S makes finding such short words more difficult.
18
OPTIMAL SMALL-SET EXPANDER GRAPHS AND THEIR CODES
The main result of this section is Theorem 6.5 below which proves that s-optimal codes can be used to simultaneously ensure protection against these standard attacks and Alice’s success in the critical step (3), in the key-exchange procedure above. Lemma 6.4. Let s ⩾ 2 be an integer. For each prime power q there exists j := j(q, s) and an s-optimal left regular bipartite graph with parameters m = q j , d = q + 1 and n ⩾ 2m. Proof. Apply the random selection strategy in the proof of Theorem 1.6 with parameter c = 2 to the line-point correspondences in projective spaces of dimension j from Example 1.5. □ Theorem 6.5. If the s-optimal graphs of Lemma 6.4 are used in the key exchange protocol above then the following statements hold: (1) Alice can recover e in linear time if |supp(e)| ⩽ s(q+1) and 8 s(q+1) (2) If |supp(e)| ⩾ 8 then the work required by an eavesdropper to do either brute force or information set decoding to recover e from c grows exponentially in the product sq. Proof. (1) By Lemma 6.1, we know that bit flipping is capable of correcting h/2 errors in linear time when αG (h) > 3d/4. Since the graphs under consideration are s-optimal the transfer bounds of Theorem 1.7 imply that for any h ⩾ s we have αG (h) ⩾ d − h−1 s . We conclude that Alice can recover h/2 = sd/16 = s(q + 1)/16 errors uniquely and in particular can recover e in linear time whenever its support is of size at most s(q + 1)/16. (2) If the support size h ⩾ s(q+1) then the proof 8 of work inequalities in the previous paragraph imply that a brute force attack requires work in the s(q+1) order of 2 8 . Since for large q the inequality 8q j n ⩾ ⩾ q j−2 h s(q + 1) holds, we also conclude that an information set decoding attack requires work in the order of s(q+1)( j−2) 8 completing the proof. □ 2 Example 6.6. As a concrete instance of the previous construction, fixing q = 2 and k = 10, we are able to generate 3-optimal graphs with minimum right degree 5 (see figure 1) consistently by picking β = 1.25 < 1.5 and a left-to-right constant c = 1.25. This way we are able to gain dual √ code robustness with the minimum right degree growing like ∼ 4 mk . Furthermore, this histogram is consistent with remark 4.5. Remark 6.7. Because of Lemma 3.3, we know the size of the graph will be of the order (q + 1)s = 2s log(q+1) which is quite large as s, q grow. However, note that there is still a significant gap between this and the brute force or information decoding attack ∼ 2Θ(sq) . Increasing q thus provides more security much faster than increasing graph size, although naturally this increases the degree which in turn slows down decoding. Acknowledgments. We thank Valérie Gauthier for stimulating our interest in post-quantum cryptography. We thank Mateo Diaz and César Galindo for useful conversations during the completion of this project. M. Fiori, P. Raigorodsky and M. Velasco are partially supported by the Fondo Clemente Estable (ANII, Uruguay) grant FCE-1-2023-1-176172. Tristram Bogart was supported by internal research grant INV-2025-213-3438 from the Faculty of Sciences of the Universidad de los Andes.
OPTIMAL SMALL-SET EXPANDER GRAPHS AND THEIR CODES
19
F IGURE 1. Histogram of degree distribution. β = 1.25, k = 10, q = 2, c = 1.25. R EFERENCES [1] BIKE Team, BIKE: Bit-Flipping Key Encapsulation, Technical Report Spec v4.0, BIKE Consortium, 2020. Specification document for the QC-MDPC code-based KEM using bit-flipping decoding. [2] Xue and Cheng Chen Kuan and Li, Improved decoding of expander codes, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 215, posted on 2022, 43:1–43:3, DOI 10.4230/LIPIcs.ITCS.2022.43. [3] G. A. Margulis, Explicit constructions of concentrators, Problems of Information Transmission 9 (1973), no. 4, 325–332. , Explicit group-theoretic constructions of combinatorial schemes and their applications in the construction [4] of expanders and concentrators, Problems of Information Transmission 24 (1988), no. 1, 39–46. [5] Michael Sipser and Daniel A Spielman, Expander codes, IEEE transactions on Information Theory 42 (1996), no. 6, 1710–1722. [6] Omer Reingold, Salil Vadhan, and Avi Wigderson, Entropy waves, the zig-zag graph product, and new constantdegree expanders, Annals of Mathematics 155 (2002), no. 1, 157–187. [7] Louis Golowich, New explicit constant-degree lossless expanders, arXiv preprint arXiv:2306.07551 (2024). [8] Shlomo Hoory, Nathan Linial, and Avi Wigderson, Expander graphs and their applications, Bulletin of the American Mathematical Society 43 (2006), no. 4, 439–561. [9] Noga and Hoory Alon Shlomo and Linial, The Moore Bound for Irregular Graphs, Graphs and Combinatorics 18 (2002), 53–57, DOI 10.1007/s003730200002. [10] Werner Ehm, Binomial approximation to the Poisson binomial distribution, Statistics & Probability Letters 11 (1991), no. 1, 7–16, DOI 10.1016/0167-7152(91)90170-V. [11] Shlomo Hoory, The Size of Bipartite Graphs With a Given Girth, Journal of Combinatorial Theory, Series B 86 (2001), DOI 10.1006/jctb.2002.2123. [12] Sheida Rabeti and Mohsen Moradi and Hessam Mahdavifar, Bounds and New Constructions for Girth-Constrained Regular Bipartite Graphs, 2025 IEEE International Symposium on Information Theory (ISIT) (2025), 1-6. [13] F. Jessie MacWilliams and Neil J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland Publishing Company, Amsterdam, 1977. [14] Elwyn R. Berlekamp and Robert J. McEliece and Henk C. A. van Tilborg, On the Inherent Intractability of Certain Coding Problems, IEEE Transactions on Information Theory 24 (1978), no. 3, 384–386.