Geoffroy Couteau
email: couteau@irif.fr

Peter Rindal
email: peterrindal@gmail.com

Srinivasan Raghuraman

Silver: Silent VOLE and Oblivious Transfer from Hardness of Decoding Structured LDPC Codes

We put forth new protocols for oblivious transfer extension and vector OLE, called Silver, for SILent Vole and oblivious transfER. Silver offers extremely high performances: generating 10 million random OTs on one core of a standard laptop requires only 300ms of computation and 122KB of communication. This represents 37% less computation and ∼ 1300× less communication than the standard IKNP protocol, as well as ∼ 4× less computation and ∼ 14× less communication than the recent protocol of Yang et al. (CCS 2020). Silver is silent: after a one-time cheap interaction, two parties can store small seeds, from which they can later locally generate a large number of OTs while remaining offline. Neither IKNP nor Yang et al. enjoys this feature; compared to the best known silent OT extension protocol of Boyle et al. (CCS 2019), upon which we build up, Silver has 19× less computation, and the same communication. Due to its attractive efficiency features, Silver yields major efficiency improvements in numerous MPC protocols. Our approach is a radical departure from the standard paradigm for building MPC protocols, in that we do not attempt to base our constructions on a well-studied assumption. Rather, we follow an approach closer in spirit to the standard paradigm in the design of symmetric primitives: we identify a set of fundamental structural properties that allow us to withstand all known attacks, and put forth a candidate design, guided by our analysis. We also rely on extensive experimentations to analyze our candidate and experimentally validate their properties. In essence, our approach boils down to constructing new families of linear codes with (plausibly) high minimum distance and extremely low encoding time. While further analysis is of course welcomed in order to gain total confidence in the security of Silver, we hope and believe that initiating this approach to the design of MPC primitives will pave the way to new secure primitives with extremely attractive efficiency features.

Introduction

Secure multiparty computation (MPC) allows n parties to jointly evaluate a function f , while leaking no information on their own input beyond the output of the function. It is a fundamental problem in cryptography, which has received considerable attention since its introduction in the seminal works of Yao [Yao86],and Goldreich,Micali,and Wigderson [GMW87b,GMW87a]. While early feasibility results for MPC were mainly of theoretical interest, MPC protocols have enjoyed tremendous improvements in the past decade.

Oblivious transfers (OT) are perhaps the most fundamental building block for MPC protocols. In a random OT, two parties receive respectively (s 0 , s 1 ) and (s b , b), where (s 0 , s 1 ) are two random strings, and b is a random selection bit. Random OT is a complete primitive for secure computation [Kil88] (in particular, it implies chosen OT, where the sender picks (s 0 , s 1 ) and the receiver picks b themselves), and modern MPC protocols rely on it. Efficiency improvements in protocols for generating OTs directly translate into improvements for a plethora of MPC protocols.

OT Extension. A long line of work, initiated with the breakthrough work of [IKNP03], has therefore sought to develop increasingly efficient protocols for generating a large number of random OTs. At a high level, OT extension protocols [IKNP03, KOS15, KKRT16, OOS17] turns a small number of base OTs into a near-arbitrary number of OTs, using only cheap operations. The latest generation of these protocols, initiated in [BCG + 17], leverages the notion of pseudorandom correlation generators (PCGs) [BCGI18, BCG + 19b] to enable the construction of extremely efficient OT extension protocols. This line of work recently culminated with the protocols of [BCG + 19a, SGRR19, WYKW20, YWL + 20].

Silent OT Extension. While PCGs allow for very efficient constructions of OT extension, this is not their main claim to fame: perhaps their most remarkable feature is that they allow the construction of silent OT extension protocols. A silent protocol has the property that: after a short interaction, with communication and computation essentially independent of the target number of OTs, the parties can locally store small correlated seeds. Then, the parties can later retrieve these seeds, and without any further interaction stretch them into a very large number of OTs. Unfortunately, while the protocols of [BCG + 19a] enjoy the silent feature, the running time improvements in [SGRR19, WYKW20, YWL + 20] were achieved at the cost of sacrificing this crucial property.

Our Results

In this work, we design new protocols for silent oblivious transfer extension and silent vector oblivious linear evaluation (VOLE). The latter is defined over a field F and allows a receiver with input x ∈ F to obtain x • a + b from a sender with input vectors (a, b) over F. VOLE is another important building block in some of the most prominent secure computation tasks; e.g. the current most efficient private set intersection [RS21]. We call our (family of) protocols Silver, which stands for SILent Vole and oblivious transfER. In addition its silent feature, Silver exhibits extremely good performances, significantly outperforming the most efficient OT extension protocols [IKNP03, YWL + 20] on all fronts.

At the heart of our results is a radical departure from previous works on secure computation. To put it bluntly, we decidedly give up on provable security reductions to any well-studied assumption. Instead, our protocols are based on the conjectured hardness of decoding new, heuristically designed linear codes (or, equivalently, the hardness of a new learning parity with noise (LPN) variant). Our approach for building these new linear codes is much closer in spirit to the de facto standard approach for building efficient block ciphers and hash functions in symmetric cryptography: using a general framework that encompasses essentially all known attacks on LPN and syndrome decoding, we identify the core properties that guarantee resistance of our new assumptions against existing attacks. Then, we extract a number of fundamental design criteria which guide the design of codes with these properties. Eventually, we rely on these design criteria together with extensive simulations to experimentally identify, with good confidence, the codes that exhibit the best properties for our constructions, while plausibly leading to very hard instances of the syndrome decoding problem.

Philosophy of our Approach

The construction of a cryptographic primitive or protocol can follow two complementary design strategies: a top-down approach, which starts from well-established cryptographic assumptions and aims at finding the most efficient construction whose security provably reduces to these assumptions, or a bottom-up approach, which tries to find the minimal construction that resists all known attacks, and relies on heuristic design criteria to build an intuition about the concrete security. Traditionally, secure computation has focused on the former, while symmetric cryptography (e.g. block cipher design) followed the latter.

The top-down approach has many attractive features -it deepens our theoretical understanding of the feasibility of cryptographic primitives, enlightens their relation to other primitives, and allows us to spend cryptanalytic efforts on a small set of assumptions. However, this sometimes comes at a huge cost in terms of efficiency: there is often a large gap between the best efficiency which can be achieved from well-established assumptions, and the efficiency which can be achieved with heuristic designs (consider the efficiency gap between SHA-256 and discrete-logarithm-based hash functions). When (our theoretical understanding of) a cryptographic primitive reaches a sufficient level of maturity, it is natural to envision the alternative bottom-up approach, in order to achieve real-world efficiency. This is the position that we advocate for in this work.

In the same way that symmetric cryptography has identified core families of attacks (e.g. linear and differential) and extracted a set of design principles for constructing primitives which plausibly resists them (e.g. substitution-permutation networks), our aim is to initiate the study of the most fundamental MPC primitives, oblivious transfer and its variants, under this angle. Pursuing this approach has the potential of yielding considerable efficiency improvements for MPC and strikes us as a natural next step for putting the efficiency of MPC primitives on par with that of symmetric primitives.

Our work being the first (to our knowledge) to study OT under the lens of heuristic cryptographic design, our constructions should of course be treated with the necessary caution. We invested a considerable effort in developing a rigorous understanding of which design criteria are likely to yield secure and efficient constructions, and relied on extensive experimental simulations to validate that our candidates satisfy these criteria; however, further study is welcomed in order to gain total confidence in their security. Given that Silver withstands the test of time, it will allow for significant improvements for numerous MPC protocols. And if not, we are confident that our analysis will motivate further constructions and analyses from which secure and efficient candidates will emerge.

Overview of our Methodology

Our starting point is the recent line of work on pseudorandom correlation generators (PCG) [BCG + 17, BCGI18, BCG + 19b]. PCGs allow to securely generate long, pseudorandom correlated strings, using minimal communication. Among the most remarkable achievements of this line of work is silent oblivious transfer extensions (SOT extension) [BCG + 19a, SGRR19]. These protocols have two phases:

(1) the two parties interact to distributively generate short correlated seeds with communication and computation essentially independent of the target number of OTs; (2) the parties locally expand the seeds, without any interaction, into a large number of pseudorandom OTs. Afterwards, these OTs can be converted into chosen-input OTs using standard methods. Very recently, efficiency improvements were obtained by [YWL + 20, WYKW20]. However, this came at the cost of sacrificing the silent feature. In practice, the ability to confine the bulk of the computation to an entirely offline phase, is a crucial efficiency feature.

The SOT Protocol of [BCG + 19a]. Our approach builds upon the protocol of [BCG + 19a]. Let us briefly recall its high level intuition:

1. the parties generate additive shares of x • e, where x ∈ F is known to the sender, and e ∈ F n is a random sparse vector, known to the receiver. This can be done with minimal communication using the GGM puncturable pseudorandom function. 2. they multiply the shares of x • e with a public matrix G, obtaining shares of x • a, for a = e • G .

Given a uniform G, a is pseudorandom under LPN. 3. Optionally, the shares can be hashed to generate pseudorandom OTs.

Generating additive shares of x • e is extremely efficient, requiring merely two calls to AES for each entry of the vector. The matrix-vector multiplication, however, is the bulk of the computation: in [BCG + 19a], G is a matrix over F k×n 2 , where k is the target number of OTs and n = c • k for some small constant c > 1. MPC protocols commonly require a number of OTs in the millions (if not more), making this step impractical unless G has some structure that allows for fast matrix-vector multiplication. This leads to a tradeoff between efficiency and confidence in the security: when H is a truly random matrix, the multiplication is impractical, but security reduces to the standard syndrome decoding/LPN assumption. Structured matrices give better efficiency, but security reduces to syndrome decoding variants which are less well-understood.

[BCG + 19a] settled for a reasonable middle ground, by letting G be a random matrix with a quasicyclic structure. On the one hand, this structure allows for matrix-vector multiplication in quasilinear time using fast Fourier transform; on the other hand, the underlying assumption (hardness of decoding quasi-cyclic linear codes) has been used in candidate post-quantum code-based cryptographic primitives submitted to the NIST competition, and are therefore relatively well studied. While this choice leads to a reasonably efficient construction, it remains somewhat unsatisfying: it seems very likely that there exists alternative choices for G which have significantly better efficiency, yet still are secure.

However, the particular set of constraints of silent OT extension is very different from all previous coding theory primitives: typically the dimension of the code is minimized, allow high noise rate, and rely on codes with a hidden structure to enable efficient decoding given a secret. In contrast, in the SOT application, the code dimension scales with the target number of OTs (hence typically millions), the noise rate must remain very low, and no hidden structure or efficient decoding property is required. As a result, there exists no well-established assumption regarding codes tailored for our unusual set of constraints.

Our Approach: a Design Methodology for Constructing G. In this work, we choose to approach the problem differently. Let us call a public matrix G ∈ F k×n 2 SOT-friendly if it satisfies the following two properties:

-Security: it is infeasible to distinguish e • G from uniform (for sparse e).

-Efficiency: the mapping x → x • G can be computed in strict linear time.

We develop a methodology for constructing SOT-friendly matrices by directly identifying some core structural properties of G which guarantee that distinguishing e • G from random cannot be done using essentially all known attacks on LPN and code-based cryptographic primitives. Yet the mapping x → x • G can be computed in strict linear time. Our methodology does not "start from zero": it builds upon well-known results related to breaking these assumptions.

Our Design Criteria

The first property can be stated in one sentence: G should generate a code with large minimum distance. For the second property, we focus on the following sufficient condition: we restrict our attention to matrices G which have a sparse parity-check matrix H (i.e., H is a sparse matrix in F m×n 2 such that H G = 0) such that H are in approximate lower triangular form.

Large minimum distance and security. Given a matrix G, the problem of distinguishing e • G from random (for a random sparse vector e) is the decisional syndrome decoding problem with respect to G . The name LPN is commonly used to denote the syndrome decoding assumption in the cryptographic community. As such, we will use both terms interchangeably. It is well-known that distinguishing e•G reduces to the following problem: given a parity-check matrix H of G, distinguish the distribution {b = x • H + e} (where x is a uniformly random vector over F m 2 and e is a random length-n sparse vector) from the uniform distribution (indeed

, if b is indistinguishable from random, then so is b • G = (x • H + e) • G = e • G )
, which is the learning parity with noise assumption, with dimension n and number of samples m, for the code matrix H. Both LPN and the syndrome decoding problem have been heavily studied in the past decades, and many attacks have been developed. A core observation (which is folklore, and was made explicitly e.g. in [BCG + 20]) is that essentially all known attacks share a common high level structure: the distinguisher computes a linear function in the samples b (but can depend arbitrarily on the matrix H). But if the code generated by G has large minimum distance d, the distribution H • x for random x must be d-wise independent, which implies that no weight-t ≤ d linear function v • b of b = x • H + e can possibly distinguish it from random. However, if v has high weight, then the distribution of v • e for a random sparse vector e is close to uniform, and so is v • b. In this work, we formalize this folklore observation, and use it to derive a concrete heuristic for choosing the parameters of an SOT-friendly matrix. Our concrete heuristic is the following:

If two codes have the same minimum distance & dimensions, their decision syndrome decoding problems likely have the same level of security.

Therefore, when choosing concrete parameters, we will use as a baseline the codes underlying wellstudied syndrome decoding variants (e.g. random linear codes in syndrome decoding, or LDPC codes in Alekhnovich's assumption [Ale03]) and set parameters to achieve the same minimum distance that these codes exhibit. We make two additional comments before moving on to the second property:

-In practice, it is generally very hard to compute the minimum distance of a family of codes. We will provide some efficient concrete choices where provable bounds exists. However, in our most efficient instantiations, we will instead rely on extensive simulations to analyze the minimum distance of the code family using an optimized minimum distance estimator, from which we will heuristically derive the minimum distance on large dimensions. -In existing attacks against LPN/syndrome decoding, the number of noisy coordinates plays a crucial role. However, it has a small impact on the overall efficiency of the SOT: scaling the noise by some factor increases the (very small) amount of communication and computation in the first phase, but has no impact on the second phase. Therefore, even if our hypothesis turns out to be too aggressive, we can actually significantly increase the security level, by increasing the number of coordinates, at a minor cost.

Linear-time encodable LDPC codes. Low-density parity-check codes (LDPC) have a sparse parity-check H, were introduced in the seminal work of Gallagher [Gal62], and are among the most well-studied objects in coding theory. Certain random LDPC codes are known to exhibit a good minimum distance [Gal62] and can be decoded efficiently. On the other hand, their encoding time (i.e., the time to evaluate the mapping x → x • G) grows quadratically with the dimension in general. Due to the transposition principle (Section 4), our linear map x → x • G is efficient if and only if LDPC encoding x → x • G is. Hence, finding LDPC codes whose generating matrix is SOT-friendly boils down to finding linear-time LDPC codes with large distance.

The seminal work of Richardson and Urbanke [RU01] identified a sufficient condition for efficient encoding of LDPC codes: if the parity-check matrix of the code can be brought, using row and column permutations only, into an approximate lower triangular form with a gap g (see Figure 9), then the encoding time can be brought down to O(n + g 2 ) (instead of O(n 2 )). Hence, whenever the gap g is below O( √ n), encoding can be done in linear time using the g-ALT encoder of Richardson and Urbanke.

Achieving Fast Encoding and High Minimum Distance. Guided by the above, we therefore seek to construct new families of structured LDPC codes which simultaneously appear to achieve high minimum distance, yet can be encoded extremely efficiently with (our optimized variant of) the g-ALT encoder of Richardson and Urbanke [RU01] as presented in Section 4. Here, we use as a starting point the Tillich-Zémor (TZ) family of codes [TZ06]. TZ codes have appealing features in our setting: they provably achieve almost linear minimum distance, and can be encoded in linear time. However, their structure is also suboptimal in our specific setting: their code is not cache friendly and has sublinear distance due to degree-2 variable nodes. In [TZ06], the presence of these degree-2 variable nodes is motivated by the fact that they allow for high performance iterative decoding. In contrast, our application does not require any decoding property whatsoever. Hence, in Section 6 we refine the TZ codes to tailor them to our setting, improving the concrete minimum distance and encoding time.

We achieve this by iteratively refining our design, using extensive simulations to track the presence of bad local structures which, when they show up, lead to worse minimum distance guarantees. We also develop a method to increase the gap g of the code, which significantly improve the averageminimum distance properties and reduce the minimum distance variance (concretely, TZ codes are in approximate lower triangular form with gap g = 1, while we increase the gap to g = 24 without harming encoding efficiency). We fine-tune the structure of the matrix to minimize the number of cache misses in the encoding algorithm, which have a significant performance impact. To fine-tune the best possible choices of parameters in the low cache-misses setting, we compute, for many randomly generated choices of parameters, the average minimum distance and worst-case minimum distance over 10,000+ random samples of the code matrix.

Efficiency

After performing this iterative sequence of refinements, we end up with a variety of candidate new LDPC codes, which we call Silver codes. We use our Silver codes to instantiate the code matrix in the silent OT extension protocol of [BCG + 19a], which we also generalize to the setting of VOLE. We implemented Silver, our protocol for SILent Vole and oblivious transfER, using our most optimized code; our implementation is available at libOTe [Rin]. We compare Silver to the best existing OT extension protocols: the standard IKNP protocol [IKNP03], which remains to date the most efficient protocol in the "unlimited bandwidth" setting, the recent protocol of Yang et al. [YWL + 20], which provides the best concrete performance in natural bandwidth settings (from 10Mbps to 5Gbps), and the silent OT extension protocol of Boyle et al. [BCG + 19a], which is the most efficient protocol that enjoys the silent feature. When generating 10 7 OTs on one core of a standard laptop, our protocol requires only 300ms of computation and 122KB of communication. In comparison, IKNP requires 58% more computation and ∼ 1300× more communication, [YWL + 20] requires ∼ 4× more computation and ∼ 14× more communication, and [BCG + 19a] requires 19× more computation (since our protocol is essentially their SOT with a Silver code, the communication is identical). In a setting with 100Mbps of bandwidth, Silver is at least 50 times more efficient than IKNP even when ignoring all costs beyond those of communication, and at least 4× and 19× more efficient than [YWL + 20] and [BCG + 19a] respectively, even when ignoring all communication costs.

Preliminaries

Throughout the work we will using [a, b] to denote the set {a, ..., b}.

[n] is shorthand for [1, n]. = will denote mathematical equality while x := y denotes defining x to be equal to y. |v| denotes the Hamming weight of vector v. Matrix and vector horizontal concatenation is denoted as [X|Y ]. Due to space restriction, we defer preliminaries on the silent OT extension protocol of [BCG + 19a] to Appendix A of the Supplementary Material.

Preliminaries on Bias

Definition 1 (Bias of a Distribution). Given a distribution D over F n and a vector u ∈ F n , the bias of D with respect to u, denoted bias u (D), is equal to

bias u (D) = |E x∼D [u • x] -E x∼Un [u • x]| = E x∼D [u • x] - 1 |F| ,
where U n denotes the uniform distribution over F n . The bias of D, denoted bias(D), is the maximum bias of D with respect to any nonzero vector u.

Given t distributions (D 1 , • • • , D t ) over F n 2 , we denote by i≤t D i the distribution obtained by independently sampling v i $ ← D i for i = 1 to t and outputting v ← v 1 ⊕ • • • ⊕ v t .
We will use the following bias of the exclusive-or (cf. [Shp09]).

Lemma 2. Let t ∈ N be an integer, and let

(D 1 , • • • , D t ) be t independent distributions over F n 2 . Then bias( i≤t D i ) ≤ 2 t-1 • t i=1 bias(D i ) ≤ min i≤t bias(D i ).
Eventually, let Ber r (F 2 ) denote the Bernoulli distribution that outputs 1 with probability r, and 0 otherwise. More generally, we denote by Ber r (F) the distribution that outputs a uniformly random element of F with probability r, and 0 otherwise. We will use a standard simple lemma for computing the bias of a XOR of Bernoulli samples: Lemma 3 (Piling-up lemma). For any 0 < r < 1/2 and any integer n, given n random variables

X 1 , • • • , X n i.i.d. to Ber r (F 2 ), it holds that Pr[ n i=1 X i = 0] = 1/2 + (1 -2r) n /2.

Syndrome Decoding and Learning Parity with Noise

Our constructions will rely on new variants of the learning parity with noise (LPN) assumption (more accurately, a variant of the syndrome decoding assumption). The LPN assumption over a field F states, informally, that no adversary can distinguish (A, A • s + e) from (A, b), where A is sampled from the set of generating matrices of some linear code ensemble, s is a uniform secret vector over F, e is a noise vector sampled from some distribution over F-vectors and typically sparse. b is a uniform vector over F. More formally, we define the LPN assumption over a ring R with dimension k, number of samples n, w.r.t. a code generation algorithm C, and a noise distribution D:

Definition 4 (Primal LPN). Let D(R) = {D k,n (R)} k,n∈N denote a family of efficiently sampleable distributions over a ring R, such that for any k, n ∈ N, Im(D k,n (R)) ⊆ R n . Let C be a probabilistic code generation algorithm such that C(k, n, R) outputs a matrix A ∈ R n×k . For dimension k = k(λ), number of samples (or block length) n = n(λ), and ring R = R(λ), the (primal) (D, C, R)-LPN(k, n) assumption states that {(A, b) | A $ ← C(k, n, R), e $ ← D k,n (R), s $ ← F k , b ← A • s + e} c ≈ {(A, b) | A $ ← C(k, n, R), b $ ← R n }.
The above definition is very general, and captures in particular not only the standard LPN assumption and its variants, but also assumptions such as LWE or the multivariate quadratic assumption. However, we will typically restrict our attention to assumptions where the noise distribution outputs sparse vectors with high probability. The standard LPN assumption with dimension k, noise rate r, and n samples is obtained by setting A to be a uniformly random matrix over F n×k 2 , and the noise distribution to be the Bernoulli distribution Ber n r (F 2 ), where each coordinate of e is independently set to 1 with probability r and to 0 with probability 1 -r. The term "primal" in the above definition comes from the fact that the assumption can come in two equivalent form: the primal form as above, but also a dual form: viewing A as the transpose of the parity check matrix H of a linear code generated by G a matrix, i.e. A = H , the hardness of distinguishing H • x + e from random is equivalent to the hardness of distinguishing G • (H

• x + e) = G • e = e • G from random (since G • H = 0).
3 On the Hardness of LPN for Structured LDPC Codes

The learning parity with noise assumption is one of the most fundamental assumptions of cryptography, introduced in the work of [BFKL94]; related problems were used even earlier [McE78]. The hardness of syndrome decoding and its variants (which is equivalent to LPN under our definition -see above) has also been intensely studied in coding theory, starting with the seminal work of Prange [Pra62] (under the name the of syndrome decoding), in learning theory (see e.g. [FGKP09] and references therein), and in random CSP theory (starting with the seminal work of Feige [Fei02]) -all with many follow ups.

Over the past few decades, a tremendous number of attacks against LPN have been proposed. These attacks include, but are not limited to, attacks based on Gaussian elimination and the BKW algorithm [BKW00, Lyu05, LF06, EKM17] and variants based on covering codes [ZJW16, BV16, BTV16, GJL20], information set decoding attacks [Pra62, Ste88, FS09, BLP11, MMT11, BJMM12, MO15, EKM17, BM18], statistical decoding attacks [AJ01, FKI06, Ove06, DAT17], generalized birthday attacks [Wag02,Kir11], linearization attacks [BM97, Saa07], attacks based on finding low weight code vectors [Zic17], or on finding correlations with low-degree polynomials [ABG + 14, BR17].

A Unified Framework for Attacks against LPN. In light of this situation, it would be excessively cumbersome, when introducing a new variant of LPN, to go over the entire literature of existing attacks and analyze their potential impact on the new variant. The crucial observation, however, is that this is not necessary, as all the above attacks (and more generally, essentially all known attacks against LPN and its variants) fit in a common framework, usually denoted the linear test framework. Furthermore, the asymptotic resistance of any LPN variant against any attack from the linear test framework can be deduced from two simple properties of the underlying code ensemble and noise distribution. Informally, if the code generated by G has high minimum distance, and for any large enough subset S of coordinates, with high probability over the choice of e ← D, at least one of the coordinates in S of e will be nonzero, then the LPN assumption with code matrix G and noise distribution D cannot be broken by any attack from the linear test framework. We will formalize this and build on it to analyze the asymptotic security of our new LPN variants. We stress that this crucial observation is not new to our work: a similar observation was explicitly made in previous works [ADI + 17, BCG + 20], where it was also used to analyze the security of new LPN variants. Even long before these works, distributions whose outputs look random to linear tests, called low-bias sample spaces, have been the subject of a rich and fruitful line of work which was initiated in the seminal work of Naor and Naor [NN90], and the relevance of linear tests to the security analysis LPN assumptions seems to have been at least somewhat folklore. Still, we believe that it will be beneficial and instructive to the reader to present this argument in a unified way with explicit bounds.

The Linear Test Framework

The common feature of essentially all known attacks against LPN and its variants is that the distinguisher can be implemented as a (nonzero) linear function of the samples (the linear test), where the coefficients of the linear combination can depend arbitrarily on the code matrix. Therefore, all these attacks can be formulated as distinguishing LPN samples from random samples by checking whether the output of some linear test (with coefficients depending arbitrarily on the code matrix) is biased away from the uniform distribution. Formally, Definition 5 (Security against Linear Test). Let F be an arbitrary finite field, and let D = {D m,n } m,n∈N denote a family of noise distributions over F n . Let C be a probabilistic code generation algorithm such that C(m, n) outputs a matrix A ∈ F n×m . Let ε, δ : N → [0, 1] be two functions. We say that the (D, C, F)-LPN(m, n) assumption with dimension m = m(λ) and n = n(λ) samples is (ε, δ)-secure against linear tests if for any (possibly inefficient) adversary A which, on input a matrix A ∈ F n×m , outputs a nonzero v ∈ F n , it holds that

Pr[A $ ← C(m, n), v $ ← A(A) : bias v (D A ) ≥ ε(λ)] ≤ δ(λ),
where D A denotes the distribution induced by sampling s

$ ← F m
2 , e ← D m,n , and outputting the LPN samples A • s + e.

The following observation is folklore, and was made explicitly e.g. in [BCG + 20]:

Observation 1 Existing attacks against LPN (as listed above) can be cast as instances of the linear test framework. Therefore, none of these attacks can provide a polynomial-time distinguisher against any LPN assumption that is provably (ε, δ)-secure against linear tests, for any negligible functions (ε, δ).

[ADI + 17] went even further and explicitly conjectured that for any LPN variant with a sparse code matrix, the runtime of the best possible attack against LPN is essentially poly(1/ε), i.e., the number of times a linear test attack must be repeated until the bias becomes noticeable. See Assumption 1.

Dual Distance and Security against Linear Tests

Following [ADI + 17], we call dual distance of a matrix M , and write dd(M ), the largest integer d such that every subset of d rows of M is linearly independent. The name "dual distance" stems from the fact that the dd(M ) is also the minimum distance of the dual of the code generated by M (i.e., the code generated by the left null space of M ). The following lemma is folklore:

ε d = max |v|>d bias v (D m,n ),
and

δ d = Pr A $ ←C(m,n) [dd(A) ≥ d].
Proof. The proof is straightforward: fix any integer d. Then with probability at least δ d , dd(A) ≥ d.

Consider any (possibly unbounded) adversary A outputting v. Two cases can occur:

-Either |v| ≤ d ≤ dd(A). In this case, the bias with respect to v of the distribution

{A•s | s $ ← F m } is 0 (since this distribution is d-wise independent)
. Since the bias of the XOR of two distribution is at most the smallest bias among them (see Lemma 2; the same holds for the bias with respect to any fixed v), we get bias

(D A ) = 0. -Or |v| > d; in which case, applying Lemma 2 again, bias(D A ) ≤ bias(D m,n ).
Security of LPN with random codes. An instructive example is to consider the case of LPN with a uniformly random code matrix over F 2 , and a Bernoulli noise distribution D m,n = Ber n r (F 2 ), for some noise rate r. The probability that d random vectors over F m 2 are linearly independent is at least

d-1 i=0 2 m -2 i 2 m ≥ (1 -2 d-1-m ) d ≥ 1 -2 2d-m .
Therefore, by a union bound, the probability that a random matrix

A $ ← F n×m 2 satisfies dd(A) ≥ d is at least 1 -n d • 2 2d-m ≥ 1 -2 (2+log n)d-m
. On the other hand, for any d and any v with |v| > d, we have by Lemma 3:

Pr[e ← Ber n r (F 2 ) : v • e = 1] = 1 -(1 -2r) d 2 , hence bias v (Ber n r (F 2 )) = (1-2r) d ≤ e -2rd .
In particular, setting d = O(m/ log n) suffices to guarantee that with probability at least δ d = 1 -2 -O(m) , the LPN samples will have bias (with respect to any possible nonzero vector v) ε d at most e -O(rm/ log n) . Hence, any attack that fits in the linear test framework against the standard LPN assumption with dimension m and noise rate r requires of the order of e O(rm/ log n) iterations. Note that this lower bound still leaves a gap with respect to the best known linear attacks, which require time of the order of e O(rm) , e O(rm/ log log m) , and e O(rm/ log m) when n = O(m), n = poly(m), and n = 2 O(m/ log m) respectively [BKW00, Lyu05, EKM17].

SOT from Asymptotically Good Linear-Time Encodable Codes

Abstracting out the unnecessary details, recall that the construction of silent oblivious transfer extension introduced in [BCG + 19b, BCG + 19a] and recalled in Appendix A, relies on the following assumption: given a large public matrix G ∈ F k×n 2 , is such that n = c • k for some small constant c > 1 (e.g. c = 2), it should be infeasible to distinguish e • G from random, where e is a uniformly random weight-t vector. This corresponds to the dual-LPN assumption, which is equivalent to the primal-LPN assumption with matrix H ∈ F m×n

2

, where H is the parity check for generator G; i.e., G • H = 0.

A selection principle for LPN with structured code. Based on the previous discussions, for any linear code ensemble C which outputs matrices H $ ← C having a large distance w.h.p., it is reasonable to conjecture that the corresponding primal-LPN assumption will hold (since a contradiction would imply a fundamentally different type of attack than existing ones). This conjecture was formally stated in [ADI + 17] for the case of all sparse code ensembles:

Assumption 1 (Assumption 6 in [ADI + 17]) For every prime-order field F, every polynomial m(λ), n(λ), every constant t, every real r ∈ (0, 1/2), and every t-sparse matrix A ∈ F n×m , the following holds: Any circuit of size

T = exp(Ω r (dd(A))) cannot distinguish (A • s + e) for s $ ← F m
2 , e ← Ber r (F) from the uniform distribution with advantage better than 1/T (Ω r (x) denotes Ω(x), where the hidden constant may depend on the noise rate r).

Noise weight versus minimum distance. The above discussions allows to make a simple, yet powerful observation: for typical noise distributions, including the Bernoulli distribution with parameter t/n, the regular noise distribution (concatenations of t length-n/t unit vectors), and the exact noise distribution (random t-sparse vectors), the running time of linear attacks is lower bounded by a term of the form e c•rd for some constant c, where r = t/n is the noise rate and d is the minimum distance. This suggests the following safeguard : if a SOT code exhibits a much worse typical minimum distance behavior than estimated (which in our case would be very surprising but theoretically possible), say, the true distance d is v times shorter than estimated, then same conjectured security level as before can be obtained by scaling the number of noisy coordinates t by a factor v. Crucially, in our SOT construction, the impact of this scaling vanishes when the number of OTs is large: it only impacts the complexity of distributing the seed (which increases by a factor v), but has no influence whatsoever, neither on the matrix multiplication part (which is the bulk of the computation) nor on the sparse vector expansion (which is the only other component whose cost scales with the target number of OTs).

Our approach: structured LDPC codes. Asymptotically good families of linear-time encodable codes have been studied in the literature, with probabilistic constructions given in [GDP73, Spi96]. However, these works only targeted asymptotic efficiency. Our aim, on the other hand, is to focus on concrete efficiency, and to find codes with a large concrete minimum distance, and extremely efficient encoding. We choose to focus on structured families of LDPC codes (i.e., codes whose parity-check matrix is sparse), which have been widely studied in the coding theory literature. Our rationale is based on the following observations:

-Most LDPC codes have linear minimum distance; -Some structured families of LDPC codes admit efficient encoding algorithms; -Some structured families of LDPC codes provably achieve both fast linear time encoding and almost linear minimum distance;

-Structured families of LDPC codes in the literature which do not exhibit linear or close-to-linear minimum distance typically satisfy a specific constraint: their Tanner graph contains a large number of degree-2 variable nodes. In contrast, we suggest candidates which admit extremely fast encoding, but do not exhibit this structural weakness, and can be experimentally verified to exhibit a very good minimum distance growth. -For random LDPC codes, the corresponding assumption (primal LPN with a random sparse code matrix) is the Alekhnovich assumption [Ale03], an important and well-studied assumption.

Most Sparse Matrices Have Linear Dual Distance

In this section, we show that for any integer t > 2, most matrices in F n×m 2 with rows of Hamming weight t have dual distance linear in m; more precisely, the fraction of such matrices with dual distance at least γ • k (for some constant γ) is at least 1 -m 2.1-t . In coding-theoretic terms, it says that most column-regular LDPC codes have linear minimum distance, where the parity check matrix has fixed column weight. Let W t (F m 2 ) denote the set of all vectors in F m 2 with Hamming weight exactly t; we also denote by W t (F n×m 2 ) the set of all matrices in F n×m 2 with exactly t ones per column.

Theorem 7 (Most sparse matrices have dual distance O(m)). For any constant c > 1 and integer t > 2, there is a constant γ = γ(c, t) such that for any large enough m,

denoting n = c • m, Pr A $ ← W t (F n×m 2 ) : dd(A) m < γ ≤ 1 -m 2.1-t .
For completeness, we provide the proof in Appendix C of the Supplementary Material; the proof is a direct adaptation to our setting of the analysis of [MST03, Section 5.3]. Building upon our analysis, we also make a key observation: random LDPC codes over large fields have linear minimum distance with high probability, even when their parity-check matrix is randomly sampled with {0, 1} entries. We discuss the implications of this observation for one of our applications, as well as its relation to previous assumptions from the literature, in Appendix C.

Fast LDPC Encoding

0 = Hc = H[x|c ] = T x + Sc ⇐⇒ -T x = Sc where H = [T |S] and T ∈ F m×k , S ∈ F m×m . Given x, we can compute y := -T x in O(k) time since T is sparse.
We then solve the sparse system y = Sc . Using Gaussian elimination, this would naively require O(m 3 ) = O(n 3 ) time. However, we can try to leverage the sparsity of H to achieve better efficiency. Our starting point is the somewhat standard LDPC solving technique known as g-Approximate Lower Triangularization (g-ALT) [RU01, DP15, KS12]. The basic intuition is that this system can be solved in linear time if S is a lower triangular matrix. In particular, the entries along the diagonal should all be set to one. Later we will discuss how to ensure this is the case. The system can be solved by solving each row "independently" starting with row 1 and working down. This idea can be generalized to allow all but the last g rows of H to be triangular (see Figure 9 in Appendix D). The last g rows are said to be part of the gap. As discussed in Appendix D, a parity check matrix with this form allows for encoding x as c = xG in O(n + g 2 ) time. Therefore, this remains linear so long as g = O( √ n). Additionally, we present an optimization in Appendix E which reduces this to O(n) at the expense of O(g) communication in the protocol.

Recall that in dual LPN we wish to compute u := e • G which is equivalent to primal LPN where u := x • H + e. Yet, the encoding algorithm described above is for computing x • G. By the transposition principle [Bor57, IKOS08], we can achieve our goal at effectively the same cost. Roughly, the transformation works by first expressing the circuit which computes x • G as a series of matrix multiplication,

s 1 := M 1 • x, s 2 := M 2 • s 1 , ..., e := M n • s n-1
such that e is the final output. Any circuit can be expressed in this way. Then e • G can be computed as

s n-1 := M n • e, s n-2 := M n-1 • s n-1 , ..., x := M 1 • s 1 .
Refer to Appendix D for a detailed description of all the algorithms discussed in this section.

Estimating the Minimum Distance Empirically

Crucial to our construction is the ability to accurately determine the minimum distance of the LDPC matrix H that is employed. Computing the exact minimum distance is known to be NP-Complete [Var97] and typically infeasible for our parameter region, e.g. n = 2 20 . For some LDPC distributions, it is possible to derive an asymptotic bound on the minimum distance; however, many of these have drawbacks in efficiency or distance.

To overcome this, we resort to computational approaches for estimating the minimum distance of an LDPC code ensemble. For relatively small values of n, say less than 200, we compute the exact minimum distance using the approach presented in [HIQO19]. For larger n, say less than 4000, we fall back to a standard heuristic, the noisy impulse method of [BVJD02], for upper bounding the minimum distance (which we have verified does in fact closely agree with exact minimum distance for smaller values of n). We then extrapolate the asymptotic behavior of the minimum distance for larger values of n. The running time remains exponential in the size of the code. With careful optimizations, the implementation of [HIQO19] is capable of computing the minimum distance up to about n = 160. Since this is relatively small compared to the codes our protocol employs, this approach is primarily used to validate the accuracy of the so-called noisy impulse method which we describe next.

Exact Minimum Distance

Upper Bounding the Minimum Distance

Our second approach for evaluating the minimum distance of a LDPC family is known as the noise impulse method [BVJD02]. Very roughly speaking, this approach tries to decode the zero codeword when one or more of the bits have been flipped. The intuition is that if the right bits are flipped, then the next closest codeword will correspond to a close-to-minimum weight codeword.

In more details, and including improvements from [XFE04], this approach considers all vectors c ∈ {0, 1} n with |c| ≤ w for some small constant w, e.g. 1 or 2. Each c is input into a belief propagation decoder, typically Min-Sum, which output the decoders estimates on the likelihood that each bit of c should be error corrected to zero or one. Since at most w bits in c are one and the actually minimum distance d is almost certainly more than twice w, the most likely codeword will in fact be the original all zero codeword.

However, the likelihood information contained in the decoder output can be leveraged to aid in the search of nearby non-zero codewords. Loosely speaking, belief propagation (BP) decoders work by assigning each bit of c a likelihood of being zero or one and updating these likelihoods in an iterative process. The initial likelihood values could be that the decoder is 95% certain that each bit is as specified by c, i.e. an error rate of 0.05. Intuitively, at each iteration the likelihood information for each bit of c is updated based on how many of the corresponding parity checks pass or fail. An interpretation of this is that it reduces the likelihood values for the zero positions of c when they are closely related to the positions of c which were set to one.

The idea is then to sort the positions of c such that the positions which are most confidently zero are to the right. The same permutation is applied to the columns of G. Partial Gaussian elimination is applied to G s.t. the left k × k submatrix is lower triangular with ones along the diagonal. Some of the first k columns are likely linearly dependent, preventing us from making the left k columns of G lower diagonal. In this case, the dependent columns are permuted right and replaced with the next left most column of G. We then consider all (permuted) codewords with the form

c * = [c 1 |c 2 |0 n-k-t ]
where c 2 ∈ {0, 1} t has some maximum weight u, e.g. t = 50, u = 10. For each choice of c 2 , it is possible to compute c 1 ∈ {0, 1} k via the left lower diagonal submatrix of G. The estimated upper bound the distance as the minimum weight over all c * .

Code Design

Designing an efficient LDPC code for large dimension LPN offers many unique challenges. Our primary two design goals are to achieve large minimum distance, ideally linear in n, and linear time encoding. However, unlike many existing codes from the coding community, we do not care about its decoding performance or other error correcting properties. All our codes have rate 1/2, i.e. n/2 = m = k.

In this section we review two existing LDPC codes, namely uniform and Tillich-Zémor Codes. After describing various benefits and drawbacks of each, we design a new highly efficient LDPC code which achieves an extremely fast linear encoding time and plausibly linear minimum distance.

Uniform LDPC

As described in Section 3.4, the family W t (F n×m 2 ) of uniform LDPC codes with fixed column weight t are known to have linear minimum distance with good probability. We consider the family of codes parameters by t ∈ {5, 11}. While the theoretical bound applies to all t > 2, we observe that t = 3 experiences very poor concrete minimum distance performance and often do not correspond to a code that can be made systematic. For t = 5 we observe a concrete linear minimum distance growth rate of d avg = 0.28m, d min = 0.19m over 100 trials. These growth rates were obtained for n ∈ [200,800]. Since we are interested in the worse case performance, we are mostly interested in d min . By increasing the weight to t = 11 we obtain a minimum distance growth rate of d avg = 0.38m, d min = 0.36m.

The hardness of syndrome decoding for uniform LDPC codes was the basis of recent proposals [BCGI18, YWL + 20], and corresponds to the well-established Alekhnovich assumption [Ale03]. While these codes turn out to be inappropriate efficiency-wise in our setting (see below), we will rely on the following heuristic to select the concrete parameters of our new codes: when we experimentally observe, with high confidence, that a distribution over codes achieves a similar average minimum distance, with a similar variance, compared to uniform LDPC codes, we heuristically estimate that the corresponding assumptions should provide a comparable level of hardness. We note that, if it turns out that this heuristic is too optimistic (which would intuitively require finding new attacks radically different from all known attacks), increasing the noise (as described in Section 3.3, Noise weight versus minimum distance) can be used to adjust the hardness level of the underlying assumption without significantly harming efficiency.

Shortcoming of uniform LDPC codes. The choice of basing security on the hardness of decoding uniform LDPC codes was motivated in previous works [BCGI18, YWL + 20] by the fact that they correspond to the relatively well-established Alekhnovich assumption. However, they turn out to be a relatively poor choice in our setting. At a high level, the reason is that for distributions over random LDPC codes which do not enforce any particular structure beyond guaranteeing some conditions on the number of ones per row and column (i.e., which sample the parity-check matrix uniformly conditioned on constraints on the fractions of variable and check nodes from the Tanner graph which must have a given degree), having a high minimum distance with good probability, and being linear-time encodable with the g-approximate lower triangularization algorithm, appear to be at odd, according to a conjecture of Richardson and Urbanke [RU01] (we will discuss this conjecture in more details in Section 6.2). This effectively justifies moving towards structured ensembles of LDPC codes, which also enforce some structure on the shape of the parity-check matrix. A prime example of codes achieving a sweet spot between having high minimum distance with good probability, and very fast encoding, is given by the Tillich-Zémor code ensemble.

Tillich-Zémor Codes

As discussed before, in order to design codes that have efficient encoders as well as good minimum distance, one must move away from random codes and consider more structured codes. As such, structured codes would offer an immediate handle on efficient encoding purely by design. On the other hand, this approaches leaves much for the desire of a more rigorous theoretical understanding of the minimum distance of such structured codes. Such questions have been posed in the past amongst the members of the coding theory and communications communities. One such work is that of Tillich and Zémor [TZ06]. They investigate the minimum distance of structured LDPC codes with two variable nodes of degree-2 per parity-check equation. In the design of LDPC codes with high iterative decoding performance the variable nodes of degree-2 play a very important role, and this is their motivation for investigating the minimum distance of such codes. Concretely, they investigate codes with m × n parity check matrices of the form H = [L|R], where R is the m × m matrix defined by

R =       1 1 1 1 . . . . . . 1 1 1 1      
and L is an m × k matrix such that all of its columns/rows have weight constant t. As such, H is in g-ALT form for g = 1. Tillich and Zémor prove that if H was generated at random subject to these structural constraints, then the minimum distance of the corresponding code is at most αn 1-2 t with probability O(n

2 t -1 ) + O(α t 2
) for even t, and O(n 2 t -1 ) + O(α t ) for odd t. In fact, they also show that for any H that has the aforementioned structure, the corresponding code will have minimum distance upper bounded by a quantity of order O(n 1-1 t ). Thus, such codes always have sub-linear distance. Looking at the structure of H, there are a few observations we can make. Let n 2 denote the number of variable nodes of degree 2. A principal quantity of interest is the ratio n 2 /m. It can be shown that if n 2 /m > 1, then the minimum distance of the corresponding LDPC code cannot be larger than a logarithmic function of n. If n 2 /m < 1, then it is possible for the minimum distance to be a linear function of n. The codes considered by Tillich and Zémor achieve n 2 /m = 1 (for t = 2) and offer readily a simple linear-time encoding algorithm for the corresponding code. Yet, as mentioned before, these codes always have sub-linear (albiet, close to linear) minimum distance. In the next section we will empirically verify that the sub-linear growth is in fact the case.

Other works, e.g. [OTA07, DRU06], have looked at the the sub-graph G 2 of the Tanner graph formed by only the degree-2 variable nodes (columns of H with weight 2) and certain structural properties can lead to poor minimum distance. For example, it is a common practice to ensure that there are no cycles in the Tanner graph involving only variable nodes of degree 2. Also, Otmani, Tillich and Andriyanova [OTA07] proved that if G 2 is slightly dense (has average degree greater than 2), then the minimum distance is only at most logarithmic in n. They also consider several other conditions for ensuring sub-linear distance.

Another work regarding G 2 is that of Di, Richardson and Urbanke [RU01, DRU06] and regard the quantity Q = λ (0)ρ (1) (λ and ρ are polynomials describing specific weight distributions of the rows/columns respectively) and how it impacts the minimum distance. λ (0) is the fraction of edges in the Tanner graph connecting to degree-2 variable nodes. They show that if Q > 1, then the minimum distance grows sub-linearly with n and linear time encoding. A question that is left open and remains to be answered is whether a linear encoding complexity necessarily implies sub-linear minimal distance.

We end this section with a few concluding remarks regarding our new codes and how they compare against the several techniques laid out in this section. Firstly, our codes have designed to ensure fast/linear encoding complexity while also having high (potentially linear) minimum distance. However, the approach to ensure linear encoding complexity is different from the works described in this section, since we actually have zero columns with weight 2. Thus, none the sufficient conditions for sub-linear minimal distance described above are satisfied by our codes. Based on these observations, we conclude that our codes do not provably have sub-linear minimal distance. We leave open the task of formally proving claims regarding the minimum distance of our codes.

LDPC Silver Codes

We now present our new LDPC constructions, which we dub Silver Codes (codes for SILent Vole and oblivious transfER). The goal of these codes is to obtain (plausible) linear minimum distance and extremely efficient encoding. Unlike in the traditional setting, our codes need to perform well (encoding-wise) when n is on the order of millions (but do not need to admit efficient decoding algorithms). Ideally our code would have a very compact representation. If a large preprocessing/sampling procedure must be performed, then the codes will likely need to be stored in memory, possibly requiring more memory than the rest of the protocol. Therefore we aim to design codes with a very succinct description.

Our second goal is to have a very efficient memory access structure. Recall that the encoding algorithm will have to access "memory locations" j and i whenever there is a 1 located at H j,i . Therefore we would ideally like H to have some additional structure which maintains some memory locality. For example, having a bounded distance between sequential memory accesses. In the case of TZ codes, for example, the left matrix is uniformly distributed, which significantly harms the performances in terms of memory access. When n is on the order of millions, performing random access into an array of length n can quickly dominate the running time as we will see in Section 7.

Despite this shortcoming, we take TZ as our starting point and iteratively improve it (sacrificing decoding performance, but trying to optimize minimum distance and encoding time) with the (heuristic) guidance of our minimum distance estimators. It will be useful to partition H into left and right halves [L|R] := H which are each of size m × m. For TZ, L is therefore a uniform column/row weight t matrix while R has column/row weight 2 where all ones are effectively on a diagonal band. Recall that we only consider rate 1/2 codes where k = m = n/2.

It is also a well known phenomenon that odd column weight t LDPC codes achieve better minimum distance performance (for examples, the bounds on the minimum distance achieved in [TZ06] are much better for odd t). Hence, we restrict ourselves to odd values of t. In particular, we focus on t ∈ {5, 11}. Slv1. Our first observations is that the structure of R in TZ plays a crucial role in the proof of sublinear distance. For TZ, this structure was desirable as it enables a very efficient linear time encoder. However, using the more general g-ALT encoder we are still able to have linear time encoding for any g = O( √ n). Our first alteration is then to increase the gap g and ensure all columns of R have weight t. There are several possible values for g and we experimentally settle on g ∈ {24, 32} as they will provide good concrete performance.

The next question is how should the ones be distributed in R. Our g-ALT encoder require ones along the diagonal which leaves t -1 degrees of freedom per column. While one could distribute these uniformly over the lower half of R, we opt to place them uniformly in the g positions below the main diagonal. An example of g = 2, t = 2 is shown in Figure 1a. We consider two choices of these parameters, (g, t) ∈ {(24, 5), (32, 11)}, which are respectively used in our weight 5 and 11 codes. We note that other parameter choices are possible and that we settled on these as a good trade off between efficiency and distance. We denote this code family as Slv1-t. Slv1 immediately gives a significant improvement over TZ as shown in Figure 1b. Consider the structure of minimum codewords in TZ: They are often composed of several columns from L which when added together result in small distances between the non-zero elements, e.g. 1001000...000100010 which has distances 3,4 between the ones. The small distances can then be "bridged" by including the corresponding columns of R, e.g. 7 columns in the case above. However, this strategy does not work for our codes due to R having larger column weight which are randomly distributed.

        1 1 1 0 1 1 . . . . . . . . . 0 0 1 1 1 1 0 1 0         (
Moreover, this code performs remarkably similar to uniform of the same column weight t = 5. With m = n/2 = 200 rows, the average (estimated) minimum distance over 100 trials of this code is 35 while uniform is 45.

Although this code represents a significant improvement over TZ for our particular application, we observe that some samples of the Slv1 code have significantly lower distance that others. In particular, the variance in this code can result in samples with as low as d min ≈ 0.55d avg while uniform has a much smaller variance, with d min ≈ 0.95d avg over 100 samples.

Slv2. Through experimentation and inspecting the Slv1 instances which perform unusually poorly, we identified that key contributors are bad local structures in the main diagonal of R which can at times result in low weight codewords. To prevent this, we observed that adding additional weight one diagonals below the main diagonal prevents these structures. Intuitively they work by increasing the expanding property of each column by guaranteeing they span more than g rows. Moreover, these structures add almost no computational overhead.

Additionally, we remove the first g columns of R such that its a m × m -g matrix and the portion of the band which wraps around is removed. In Appendix E we will use a different technique to restore R to being square. An example of the Slv2 distribution of R is in Figure 2a with g = t = 2 and a single diagonal. Through experimentation we observe that adding two weight 1 diagonal bands at distances 5 and 31 below the main diagonal significantly reduces the variance and improves the average distance. As shown in Figure 2b the performance of the second code which we denote as Slv2. We note that the uniform code also had the n dimension reduced by g in order to maintain a fair comparison. Remarkably, the Slv2 code has average performance almost identical to that of uniform codes. Moreover, the variance of Slv2 is significantly reduced, with d min = 0.88d avg compared to d min = 0.91d avg for uniform over 100 trials.

             1 0 1 1 1 1 . . . . . . . . . 1 0 1 1 . . . 0 0 1 1 1 1 1 0              (
Slv3. Next we turn our attention to the distribution of L after which we will further optimize R. While the current distribution of L gives good minimum distance, its memory locality properties are extremely poor since it is uniform. For each non-zero L i,j , the g-ALT encoder must access two arrays at i, j respectively. This effectively means one of them is always a cache miss and can quickly dominate the running time as see in Figure 5 of Section 7.

We investigated numerous methods of improving the memory locality of L. For instances, an L consisting of random non-zero submatrixes with various dimensions. However, for the most part this line of thinking was ineffective. Core to a high performing L is an expanding property. In particular, each column of L should have non-zero locations which are somewhat unique and spread out. This is particularly important since the distribution of R is more or less a single band along the diagonal. If both L and R consists of clumps of ones, then it is more likely that cancellation can occur.

However, we identified a surprisingly simple and highly efficient structure which can possess the exact properties we desire. In particular, we will distribute L such that each column is a cyclic shift of exactly one over the previous. This effectively results in t weight one diagonals wrapping around L.

We observe that the exact distribution of the diagonal plays a very crucial role in the minimum distance performance of L. For instance, if they are sampled uniformly, then with some noticeable probability the diagonals can be clumped together. In these cases the code can perform extremely poorly due to L and R being too similarly distributed. One also might think that to achieve a good expanding property that distributing the diagonals evenly over L would be optimal. However, in this case it is possible for two columns of L to equal.

We have experimentally identified that a compromise between these two extremes achieves very good minimum distance performance (both in terms of average distance and variance). In particular, the diagonals should be somewhat evenly distributed while still being irregularly spaced. To identify such distributions we sampled many L at random and evaluate the resulting minimum distance over hundreds of trials and various values of n. An instances of a well performing L with weight t = 5 is to distribute the ones of the first column as {0m, 0.049m, 0.43m, 0.60m, 0.73m}. Other well performing instances have a similar distribution where some diagonals are relatively close while overall they are evenly distributed over the range.

Our methodology for selecting the exact parameters was to evaluate 10,000 random choices at m ∈ {40, 60, 80, 100, 150, 200, 300, 400} and select the top 100 best performing. Out of these, we then ran 100 trials for each m ∈ [40, 400] with independently sampled R and selected the parameters which maximized d min /d avg for each m. As such, our selection didn't achieve the highest average distance d avg but instead was "consistently well performing." We note that one has to be careful with the selection of L as a poorly chosen one can result in bad/erratic minimum distance performance. That being said, we observed that most randomly sampled chooses performed well.

The minimum distance performance of this code is depicted in Figure 3a. Interestingly, this code out performs uniform with an average (estimated) minimum distance of d avg = 94 at m = 400 compared to d avg = 91 for uniform. Moreover, the variance of this code is quite low, with d min = 0.94d avg at m = 400 compared to d min = 0.91d avg for uniform over 100 trials.

Slv4. We now return our attention to improving the distribution of R. Generating R is effectively sampling O(m) random sets of g t , which correspond to the location of the ones on the main diagonal. While linear time, this sampling can be quite expensive. We therefore experiment with the idea of letting the diagonal repeat ever p columns. While one has to be careful with repeated structures in a code, for a sufficiently large p we conjecture and experimentally confirm that it should not harm the minimum distance. We consider a repeat of p ∈ {1, 2, 3, ..., g} and observe the repeating structure only introduces a weakness for p ∈ {1, 2}. The case of of p = 1 is clearly problematic due to R now effectively being t + 2 diagonal lines of width one which structurally is too similar to L. Our experiments reflect this with minimum distances being effectively upper bounded by 12 as seen in Figure 4. For p = 2 we observe a similar trend with the distance being upper bounded by 40. However, for p ≥ 3 we observe no negative effects over all of the trials. To be slightly conservative, we opt to set p = g which for our weight 5 code results in p = 24.

We further propose selecting a concrete instance of the diagonal, and validating its performance on the range of experimentally testable values of n. This can in turn give us confidence that the repeating structure does not happen to correspond to a weak instances, e.g. a p = 1 instance. Moreover, by selecting a concrete instance, it is possible to hardcode the indices into the program and get a very significant performance improvement.

Slv5. This leads us to our final modification. For the case of p = g we restrict our selection of R such that each row3 and column has fixed weight t -1 with respect to these random indices. The reason for this alteration is purely to improve the computational efficiency of computing xG via the transposed circuit. In particular, the encoding algorithm will process R in a row by row manner. This alteration allows the weight of each row to be not be hard coded improved the performance of the branch predictor, etc. We observe that restricting R to be row regular does not decrease the minimum distance performs. See Appendix F for a detailed description.

Eventually, we further consider a variant of Slv5, called Slv5'. This variant is entirely identical, with the sole exception that the parity-check matrix is now viewed as the parity-check matrix over a field F which might not be equal to F 2 -while the parity-check matrix still has {0, 1} entries. We do not use this variant in our main application to silent OT, but it can be used to provide strong efficiency improvements for VOLE over larger fields. We provide support for this modification in Appendix C of the Supplementary Material.

Performance Evaluation

We now evaluate the concrete running times of our LDPC codes along with our Silent OT and Vole implementations (available at [Rin]). With respect to our OT protocol we compare with [IKNP03, BCG + 19a, YWL + 20]. We also compare our Vole implementation (a direct generalization of [BCG + 19a] with our LDPC code) with the implementation of [WYKW20]. All implementations target κ = 128 bits of computational security and λ = 40 bits of statistical security.

All performance evaluations were perform on a single consumer laptop with an i7 9750H CPU and 16GB of RAM. Networking is performed via localhost. Each party is restricted to a single thread. We note that due to silent property of our protocol, it is very conducive to a multi-threaded implementation but that we only consider single thread performing for simplicity. All numbers reported exclude a setup phase where 128 base OTs are perform.

LDPC Encoding Performance. In previous protocols for silent OT and Vole, the running time was dominated by the compression of the noisy vectors generated in the setup. We now compare our new algorithms with the bit polynomial multiplication encoding used in [BCG + 19a].

For n = 2 20 , our most optimized code is 31× faster than [BCG + 19a, CCK + 18]. This improved running time is not merely due to using an LDPC code as demonstrate by the running time of TZ, which is only between 1.1 and 2× faster than [BCG + 19a, CCK + 18]. Moreover, the initial strengthening of the TZ minimum distance by the Slv1 code results in a significant running time increase of 1.5×.

The first major performance improvement is achieved by the Slv3 code which changes the distribution of L to have an extremely efficient memory access structure. This change reduces the running time of the L encoding by around 25×. The Slv5 code then optimizes the distribution of R to have a repeating structure along with ensuring that it is row regular. These changes allow for very significant memory and system level optimization. We observe that both our weight 5 and 11 Slv5 codes out perform all existing protocol in terms of computational overhead while matching the best communication overhead of [BCG + 19a]. In particular, our protocol is as much as 1.5× faster than the highly optimized [IKNP03, Rin] protocol which has stood as the most computationally efficient protocol for almost two decades. All this is achieved while communicating exponentially less data. We argue that this is a landmark achievement given the central role OT plays in countless protocols.

The next most efficient protocol is that of Yang et al. [YWL + 20] which also achieves a sub-linear (but not logarithmic) communication overhead. This protocol is based on Primal LPN and therefore requires a one time setup sub-protocol in which correlated randomness is constructed. Given this, their protocol can then generate correlated OTs on demand. In Figure 6 we distinguish their setup and online protocols as x + y respectively. However, even if only the online protocol is considered, our protocol is more than 4× more efficient in terms of running time and communication. If their setup phase is included then our protocol requires 13× less communication for m = 10 7 . What is more, their setup phase requires a relatively complicated parameter select procedure which limited us to only performing m = 10 7 OTs with their implementation. One reason their only implement this size is that their setup phase has a relatively fixed cost regardless of m. On the other hand, our protocol can easily be executed with any value of m with running times that scales proportionally. Vole Performance. We implement the generalization of [BCG + 19a] for performing vole. The protocol is largely the same as the OT variant except that f more OTs on strings of length O(κf ) need to be performed where f is the log of the field size, i.e. f = 128. For our protocol we use the binary Slv5 code while the noise vector is distributed over the while field. The security of this optimization is discussed in Section C.2. We compare with the vole protocol of [WYKW20] (a generalization of [YWL + 20]) which is based on Primal LPN and therefore requires a one time setup sub-protocol. We also compare to the 1-out-of-N OT protocol of [OOS17] due to vole also supporting this functionality via hashing. We observe that our protocol significantly out performs both of these works. Moreover, [WYKW20] performs a vole over a field of size 2 61 -1 while our implementation is for the Galois field of size 2 128 . As such, this effectively halves their communication. Similarly, [OOS17] has an analogous field size of 2 79 . Despite working over a larger field, the running time of our protocol 4× faster than [WYKW20] at m = 4 × 10 7 and 22× faster than [OOS17]. Similarly, at m = 4 × 10 7 our protocols requires between 5 to 8× less communication than [WYKW20] depending on if their setup is include and 6200× less than [OOS17]. Applications. The applications of our new protocol are extremely broad. Two of the most compelling are binary triple generation for the GMW[GMW87b] protocol and private set intersection. The former allows generic secure computation of binary circuit at the expense of performing 2|C| OTs and sending 2|C| bits where |C| is the number of AND gates in the circuit. Due to the extreme efficiency of our protocol, the cost of the OTs is like dominated by the other costs in the GMW protocol, i.e. simply sending the bits. More generally, since our OT protocol is faster than all prior works in effectively all metrics, our protocol should be the de facto choice for generating OTs and binary triples.

The recent semi-hones/malicious secure PSI protocol of [RS21] directly builds on vole and achieved the lowest communication and very fast running times compared to all prior works. This protocol performs a vole of size 2.4n where the sets are of size n. Their implementation makes use of the vole protocol of [SGRR19] along with optimizations of [WYKW20]. As such, integrating our vole protocol gives a good example of the speed ups that can be obtained.

For sets of size n = 2 16 to n = 2 24 we observe that our vole protocol improves the running time of [RS21] by between 40 and 45 percent and 25 to 1 percent reduction in communication. Concretely, the semi-honest variant of their PSI protocol for n = 2 20 with our vole implementation would require 3.1 seconds compared to 2.4 seconds of [KKRT16] while at the same time sending 2.5× less data than [KKRT16]. As such, in effectively all real world situation the PSI protocol of [RS21] with our vole is the optimal protocol to use. Moreover, the malicious variant of [RS21] with our vole achieves the fastest running time and lowest communication by a factor of 1.7× and 4× respectively compared to then next most efficient protocol[PRTY20].

Supplementary Material

A Preliminaries on Silent OT Extension

In this section, we recall the silent OT extension protocol of [BCG + 19a], on top of which our protocol is built (some descriptions are taken almost verbatim from [BCG + 19a]).

A.1 Pseudorandom Correlation Generator for VOLE

First, we recall the high-level idea of the pseudorandom correlation generators (PCG) for vector-OLE from [BCGI18, BCG + 19b]. A PCG is a pair of algorithms (Gen, Expand), where Gen distributes a pair of seeds to a sender and a receiver. Later, the seeds can be locally expanded with Expand into long pseudorandom correlations, for a target class of correlation (here, subfield vector OLE). The construction of [BCGI18, BCG + 19b] uses two main ingredients: a variant of the LPN assumption, and a method for the two parties to obtain a compressed form of (pseudo)random secret shares s 0 , s 1 , satisfying

s 1 = s 0 + e • x ∈ F n 2 λ (1)
where e ∈ {0, 1} n is a random, sparse vector held by one party, and x ∈ F 2 λ is a random field element held by the other party. Given this, the shares can be randomized using a public binary matrix G that compresses from n down to m < n elements, and locally multiplying each share with G . The underlying assumption is that a = G • e is pseudorandom under a suitable variant of LPN. Now, writing b = G • s 0 and c = G • s 1 , from (1) we then get c = b + ax. This can be seen as a set of random correlated OTs, where a i ∈ {0, 1} are the receiver's choice bits, and (b i , b i +x) are the sender's strings, of which the receiver learns c i . These can be locally converted into random string-OTs with a standard hashing technique [IKNP03].

To obtain a compressed form of the shares in (1), the constructions of [BCG + 19a] uses a puncturable pseudorandom function (PPRF) primitive. A PPRF is a PRF F such that given an input x, and a PRF key K, one can generate a punctured key K{x} which allows evaluating F at every point except for x, and does not conceal any information about the value F (K, x). A PPRF can be built from any length-doubling pseudorandom generator, using a binary tree-based construction [KPTZ13, BW13, BGI14]. The construction works as follows: Gen will give the sender a random key K and x, and give to the receiver a random point α ∈ {1, . . . , N }, a punctured key K{α}, and the value z = F (K, α) + x. Given these seeds, the sender and receiver can now define the expanded outputs, for i = 1, . . . , n:

s 0 [i] = F (K, i), s 1 [i] = F (K, i) i = α z otherwise
These immediately satisfy (1), with e as the α-th unit vector. Then, to obtain shares of sparse e with t non-zero coordinates, simply repeat the above t times and XOR together all t sets of outputs.

A.2 Distributing the Setup

To obtain a silent OT out of the above PCG for VOLE and OT correlations, it remains to distributively implement the setup protocol (i.e., securely compute and distribute the outputs of the Gen algorithm). The work of [BCG + 19a] gives a simple two-round protocol for this task. At a high level, it works as follows: for each of t secret LPN noise coordinates α j ∈ [N ] known to the receiver, the sender generates a fresh PRF key K j , and obliviously communicates a punctured key K j {α j } and hardcoded punctured output z j = PRF(K j , α) + x to the receiver. Overall, this gives shares of x • e.

To execute this oblivious communication of the punctured keys, for each K{α}, the parties rely on = log N parallel OT executions: the sender's message pairs correspond to appropriate sums of partial evaluations from a consistent GGM PRF tree and his secret value x, and the receiver's selection bits correspond to the bits of his chosen path α. We defer the reader to [BCG + 19a] for a full description of the exact protocol.

B Preliminaries on Coding Theory

Generator Matrix. Let k < n ∈ N. If G ∈ F k×n is an k × n matrix over the field F, it generates the codewords of a linear code C ⊆ F n given by

C := {c = xG | x ∈ F k }
where c is a codeword of the linear code C, and x is any input k-length vector. G is called the generator matrix of C. Both c and x are assumed to be row vectors. If |F| = q, C is called an [n, k, d] q -code, where d is the minimum distance of the code (the distance of the linear code is the minimum weight of its nonzero codewords, or equivalently, the minimum distance between distinct codewords). It will be useful to define m := n -k.

Standard Form. The standard form for a generator matrix is,

G = [I k |P ]
where I k is the k × k identity matrix and P is a k × m matrix. When the generator matrix is in standard form, the code C is said to be systematic in its first k coordinate positions. In this case, the message can be read directly from the first k positions codeword, i.e. c = Gx = [x|p] for some parity information p ∈ F m . An arbitrary generator matrix G can be placed in standard form by performing elementary row operations. Depending on how G is sampled, it is possible that some columns of G are linearly dependent in which case permuting the columns of G (and the resulting codewords) might be required.

Parity Check Matrix. The matrix H ∈ F m×n representing a linear function φ :

F n → F n-k whose kernel is C is called a parity check matrix of C. Equivalently, H is a matrix whose null space is C, i.e. C = {c | Hc = 0}. It can be verified that H is a m × n matrix. The code generated by H is called the dual code of C, denoted by C ⊥ .
Minimum Distance. The distance d of a linear code C can be defined as the minimum number of linearly dependent columns of the parity check matrix H. Equivalently, it is the minimum number of positions of a codeword c ∈ C which must be modified to produce another codeword c . Due to the linearity of C, it is easy to see that d is equal to the minimum weight non-zero codeword. Computing the minimum distance for an arbitrary linear code C is known to be NP-complete [Var97]. As explained in Section 5, various methods have been proposed for bounding the minimum distance of linear codes.

Relating the Generator and Parity Check Matrices A generator matrix can be used to construct the parity check matrix for a code (and vice versa). If the generator matrix G is in standard form,

G = [I k |P ] then the parity check matrix for C is H = [-P |I n-k ]
where P is the transpose of the matrix P and I n-k is the m × m identity matrix.

B.1 Decoding

Standard Array Decoding

Standard Array. A standard array Arr ∈ F m×k is an array that lists all elements of a particular F n vector space. Standard arrays can be used to decode linear codes over a noisy channel on which errors are made, i.e., to find the corresponding codeword for any received vector. A standard array can be created as follows:

1. List the codewords of C, starting with 0, as the first row Arr 1 = {c | c ∈ C}.

2. Let i index the next row and choose any vector v of minimum weight not already in the array. Then define Arr i = Arr 1 + v. That is, (a) write this as the first entry of the next row i, i.e. Arr i,1 = v. This vector Arr i,j is denoted the coset leader. (b) Fill out the row i by adding the coset leader to the codeword at the top of each column. The sum of the ith coset leader and the jth codeword becomes the entry in row i, column j, i.e. Arr i,j = Arr i,1 + Arr 1,j for j ∈ [2, 2 k ]. Repeat this step until all rows/cosets are listed and each vector appears exactly once.

Standard Array Decoding. To decode a vector using a standard array, for each coset leader Arr i,1 , subtract it from the vector received. For some i, the result will be one of the codewords in C. Decoding via a standard array is a form of nearest neighbour decoding. In practice, decoding via a standard array requires large amounts of storage. Other forms of decoding are more efficient. Decoding via standard array does not guarantee that all vectors are decoded correctly. In such a case some implementations might ask for the message to be resent, or the ambiguous bit may be marked as an erasure and a following outer code may correct it. This ambiguity is another reason that different decoding methods are sometimes used.

Syndrome Decoding

Syndrome. For any row vector c ∈ F n , s = Hc is called the syndrome of c. The vector c is a codeword if and only if s = 0.

Syndrome Decoding. The calculation of syndromes is the basis for the syndrome decoding algorithm. Syndrome decoding is a highly efficient method of decoding a linear code over a noisy channel. In essence, syndrome decoding is minimum distance decoding using a reduced lookup table. Note that linear code C is capable of correcting up to

t ≤ d -1 2
errors made by the channel (since if no more than t errors are made, then minimum distance decoding will still correctly decode the incorrectly transmitted codeword). Now suppose that a codeword c ∈ F n is sent over the channel and the error pattern e ∈ F n occurs. Then z = c + e is received. Ordinary minimum distance decoding would lookup the vector z in a table of size |C| for the nearest match, i.e., an element (not necessarily unique) c ∈ C with

d(c, z) ≤ d(y, z)
for all y ∈ C. Syndrome decoding takes advantage of the property of the parity matrix that Hc = 0 for all c ∈ C. The syndrome of the received z = c + e is Hz = He . To perform ML decoding in a binary symmetric channel, one has to look-up a pre-computed table of size q n-k , mapping He to e. Note that this is already of significantly less complexity than that of a standard array decoding.

Knowing what e is, it is then trivial to decode c as c = ze.

Syndrome Decoding of Binary Codes. For binary codes (q = 2), under the assumption that no more than t errors were made during transmission, the receiver can look up the value He in a further reduced table of size

t i=0 n i < |C|
Another approach to decoding would be the following. If both k and n -k are not too big, and assuming the generating matrix is in standard form, syndrome decoding can be computed using two precomputed lookup tables and two XORs only. Let z be the received noisy codeword, i.e., z = c ⊕ e.

Using the encoding lookup table of size 2 k , the codeword c that corresponds to the first k bits of z is found. The syndrome is then computed as the last n -k bits of s = z ⊕ c . Using the syndrome, the error e is computed using the syndrome lookup table of size 2 n-k , and the decoding is then computed via c = z ⊕ e. The number of entries in the two lookup tables is 2 k + 2 n-k , which is significantly smaller than 2 n required for standard array decoding that requires only one lookup.

Information Set Decoding Information set decoding refers to a family of Las Vegas-probabilistic methods all based on the observation that it is easier to guess enough error-free positions, than it is to guess all the error-positions. The simplest form is the following: Select k columns of G at random, and denote by G the corresponding sub-matrix of G. With reasonable probability G will have full rank, which means that if we let c be the sub-vector for the corresponding positions of any codeword c = xG of C for a message x, we can recover x as x = c G -1 . Hence, if we were lucky that these k positions of the received word z contained no errors, and hence equalled the positions of the sent codeword, then we may decode. If t errors occurred, the probability of such a fortunate selection of columns is given by n

-t k n k = (m -t + 1) . . . (m -t + t) (n -t + 1) . . . (n -t + t)
This method has been improved in various ways. For more on this, consider [CG90, Pet10, BLP11, BJMM12, HS13, MO15, TS16, NPC + 17] and the references therein.

B.2 Tanner Graphs

A Tanner graph is a bipartite graph used to state constraints or equations which specify error correcting codes. Tanner graphs are partitioned into constraint nodes or check nodes and digit nodes or variable nodes. For linear codes, the constraint nodes denote rows of the parity-check matrix H. The digit nodes represent the columns of the matrix H. An edge connects a constraint node to a digit node if a non-zero entry exists in the intersection of the corresponding row and column.

As an example, consider the binary [11, 6, d] 2 code C with generator matrix

G =        
1 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 1 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 1

        = [I 6 |P ]
in its standard form. Its parity check matrix is given by

H =      
1 1 1 0 0 0 1 0 0 0 0 0 0 0 1 1 1 0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1

      = [-P T |I 5 ]
Let us name the rows of H as c 1 , . . . , c 5 referring to the five parity checks that H performs. They will be the constraint nodes in the Tanner graph corresponding to H. Similarly, let us name the columns of H as d 1 , . . . , d 6 , p 1 , . . . , p 5 referring to the eleven variable bits (six data bits and five parity bits) in the codeword that H will perform parity checks on. They will be the digit nodes in the Tanner graph corresponding to H. The Tanner graph corresponding to H is shown in Figure 8.

B.3 LDPC Codes

A low-density parity check code, or LDPC code, is constructed using a sparse Tanner graph. The characteristic of LDPC codes is that H contains very few ones with respect to its total size, i.e., H is sparse (this is where the name low-density comes from). Let H be an (n -k) × n parity check matrix. Let i ∈ [n -k] and j ∈ [n] be indices to index into the rows and columns of H respectively. Let wt row,i denote the number of non-zero entries in the ith row of H and let wt col,j denote the number of non-zero entries in the jth column of H. For LDPC codes, we must have wt row,i n and wt col,i n -k for all i, j. If wt row,i is a constant for all i and wt col,j is a constant for all j, then the code is said to be a regular code. In such a case, it is easy to see that

wt row,i wt col,j = n n -k
Codes whose parity check matrices have a varying number of non-zero entries per row or column are called irregular codes.

C On the Dual Distance of Random Sparse Matrices

In this section, we prove Theorem 7, and discuss an interesting consequence of the proof regarding the minimum distance of LDPC codes over large fields.

C.1 Proof of Theorem 7

We prove Theorem 7, which we recall below:

Theorem 7 (Most sparse matrices have dual distance O(k)). For any constant c > 1 and integer t > 2, there is a constant γ = γ(c, t) such that for any large enough k, denoting n = c • m,

Pr A $ ← W t (F n×m 2 ) : dd(A) m < γ ≤ 1 -m 2.1-t .
The proof is a relatively simple adaptation to our setting of the analysis of [MST03, Section 5.3].

Proof. Given a matrix A ∈ F n×m In the following, we will show that a randomly sampled sparse matrix A will have d-right unique column-neighbor with high probability, for a certain d. This will follow from the fact that A has certain expansion properties. We say that a matrix A is (d, α)-expanding if for every subset S ⊆ To prove Theorem 7, it remains to show that whenever n = c • m for some constant c, a random sample from W t (F n×m

[n] with |S| ≤ d, it holds that |N A (S)| > α • |S|. 4 Lemma 9 ([MST03]). Let A ∈ W t (F n×m 2 ) be a t-sparse matrix. If A is (d, t/2)-

2

) is (m/C, t/2)-expanding with high probability, for some constant C.5 Lemma 10. For any large enough m = m(λ), n = c • m for a constant c, any t > 2, there is a constant C such that

Pr[A $ ← W t (F n×m 2 ) : A is (m/C, t/2)-expanding ] ≥ 1 - 1 O(m) t-2 .
Proof. For any subset S ⊂ [n] and any size t • |S|/2 subset T ⊂ [m], the probability over the random choice of

A $ ← W t (F n×m 2 ) that N c A (S) ⊆ T is clearly at most (t • |S|/2m)
d i=2 c • m i • m t • i/2 • t • i 2m t•i
, where the sum starts at 2 because any single row j always satisfies N c A ({j}) = t > t/2. Using the inequality a b ≤ (ae/b) b , we get

d i=2 ecm i i • em ti/2 ti/2 • ti 2m ti = d i=2 ecm i • em ti/2 t/2 • ti 2m t i = d i=2   c • t 2 t/2 t/2-1 • e t/2+1 t/2-1 • i m   i•(t/2-1) = d i=2 C 2 • i m i•(t/2-1)
,

where C denotes the constant 2c

+ log 2 m • 4C 2 log 4 m m 2 t-2 + m C • 1 m log m t/2-1
, where the first two terms are the terms for i = 2, 3 in the sum, the third term bounds the terms i = 4, • • • , log 2 m in the sum, and the last term bounds the sum of the remaining terms. For a large enough m and any integer t > 2, this sum is therefore dominated by its first term. The lemma follows.

Theorem 7 directly follows from Lemma 8, 9, and 10.

C.2 Dual Distance of Random Binary Sparse Matrices

We now make a crucial observation, which is the core motivation behind our candidate for the silent VOLE application: the previous proof that random sparse matrices have high dual distance over F 2 generalizes directly to arbitrary fields. Even more, it also generalizes to the setting of codes over an arbitrary field, even when the parity-check matrix is sampled over {0, 1} n×m . This is because the analysis relies solely on the expansion properties of the bipartite graph which has A as its adjacency matrix. In our framework, this means that with probability 1 -o(1) over the random choice of A from W t ({0, 1} n×m ), any linear attack against the LPN assumption with code matrix A over F has advantage at most exp(-Ω(t)) when e is randomly sampled from either a Bernoulli distribution over F with rate t/n, the uniform distribution over all t-sparse vectors over F n , or the regular distribution (i.e., the concatenation of t random unit vectors over F n/t ).

In light of known attacks against LPN, this suggests than Alekhnovich's assumption (primal LPN with a random sparse code matrix) remains plausibly hard over arbitrary fields, even when the matrix is restricted to have {0, 1} entries. We note that the hardness of Alekhnovich's assumption over large fields has been conjectured and use in previous works (see e.g. [ADI + 17]), but to our knowledge, we are the first to observe that the underlying analysis extends to the case of binary matrices as well.

Looking ahead, while the protocol of [BCG + 19a] for silent OT extension relies only on LPN over F 2 , it can directly be generalized over arbitrary fields, in which case it provides a silent protocol for vector OLE over F. Silent protocols for vector OLE over large fields have recently found important applications; for example, they lead to the most efficient solutions known to date for private set intersection [RS21], one of the most actively researched areas of secure computation. In our candidate structured LDPC codes over general fields, the use of matrices with {0, 1} entries will result in (very) significant efficiency improvements, while (plausibly) not harming security.

Comparison to binary-matrix LWE. The knowledgeable reader might be aware that a similar proposal was made in [Gal13], in the setting of the learning with error assumption. The end goal for this proposal was superficially similar: increasing efficiency and reducing storage costs, by assuming the hardness of LWE over a field F q with respect to a matrix with {0, 1} entries. Unfortunately, a number of devastating attacks against this proposal have been described in [HM17, SNDM18, SVA + 19], using linear programming algorithms. The reader may wonder, then, why things should be any different in our setting, and whether this does not make our assumption at least highly suspicious.

We argue that, in spite of the superficial similarity, the situations are actually incomparable. In short, attacks against binary-matrix LWE crucially rely on the fact that the LWE error terms are guaranteed to have small magnitude. Since the entries in the matrix are also small, this implies that binary-matrix LWE can be reduced to the hardness of finding an integral solution of a set of equations over the integers, a problem which can be solved efficiently using linear programming. However, the situation is entirely different in our setting, because the nonzero entries of our noise vector are uniformly random over the field F. This effectively prevents reducing the problem to that of solving a system over the integers.

D Detailed Circuit for f (e) = e • G

Recall that for dual LPN, we want to multiply the error vector with the transpose of G ∈ F k×n . This can be handled with the circuit transposition principle [Bor57]. Moreover, we present the generalized algorithm where H ∈ F m×n is approximately triangular with gap g.

Linear time LDPC encoding

We begin by presenting a detailed description of the circuit computing f (m) = m • G as shown in Figure 10. We begin by requiring H to be in approximate lower triangular form consisting of

H = A B C D E F
where C ∈ F σ×σ is a (strict) lower triangular with ones on the diagonal and E ∈ F g×g . We will also require E = -F C -1 B + E to be invertible. Let H = [-P |I m ] be the systematic form of H. We assume no column permutations are required to convert H into H and as such a systematic codewords c = [x|p] for message x ∈ F k is also in the nullspace of H, i.e. Hw = 0. Since C is triangular, we can zero F out by multiply H with [I|0 -F C -1 |I] to obtain In the case that g = 0, then this simplifies to p = -C (Ax ).

A B C D E 0 where D = -F C -1 A + D, E = -F C -1 B + E. Let [p 1 , p 2 ] := p where p 1 ∈ F g . Observe that p 1 = -E -1 (D x ) = -E -1 (-F (C -1 (Ax )) + Dx ) p 2 = -C -1 (Ax + Bp 1 )
Observe that we must compute v = C -1 y for y ∈ {Ax , Ax + Bp 1 }. This is done be leveraging that C is lower diagonal by solving the system y = Cv. For each row starting at row i = 1, observe that y i = j∈Ii v j where I i indexes the non-zero columns of the row C i . Observe that i ∈ I i since C is diagonal. Therefore we can rewrite this as v i = y i -j∈Ii\{i} v j where these v j have all been previously defined, i.e. j ≤ i for j ∈ I i .

The full algorithm is presented in Figure 10 and manipulates the state of the algorithm by multiplying it with a square matrix at each step. This will assist in the explanation of the transposition principle. Note that no operations are requires when something is multiplied by its identity. The algorithm requires O(n + g 2.3 ) or O(n + g 3 ) time to preprocess -E -1 and then the main circuit requires O(n + g 2 ) time. In particular, every step of the protocol requires O(n) time except for step 4 when computing (-E -1 )p which requires O(g 2 ) since E -1 ∈ F g×g and p ∈ F g are dense. We note that when g = 0 the encoding algorithm can be simplified as shown in Figure 11.

Linear time encoding for transposed code We now discuss how to compute f (e) = e • G with the same complexity as computing x • G. The full algorithm is presented in Figure 12 and is a direct application of the circuit transposition principle [Bor57] on Figure 10. We leave the application of the transposition principle on the simplified encoder (Figure 11) to the reader.

The transposition principle states that if you transpose each of the matrix multiplications and apply them in reverse order, then what you get is the overall circuit computation transposed. Therefore, if we have a circuit which compute f (x) = x • G and we compile this into our matrix-multiplication representation (as done is Figure 10), transpose all of the multiplications, apply them in reverse order, then we will get a circuit for f (e) = e • G which has the same complexity as computing x • G.

E Linear-Time LPN Encoding with Gap

We now present an optimization which allows reducing the computational overhead of O(n + g 2 ) for LDPC encoding to O(n + g) at the expense of increasing the communication overhead of the protocol by O(g). Moreover, this optimization reduces the constant term in front of n by a factor two. In the primal setting, we are computing u = H x + e, where H is g-approximate lower triangular. Let H := H 0 I g be the extended matrix where the bottom g rows are the identity matrix. In addition, let e = [e|e * ] where e * ← F g is sampled uniformly. We can then define

u = H x + e .
Observe that u = [u|u * ] where u * = (x 1 , ..., x g ) + e * . Since e * is uniform then u * is uniform that the security of this LPN instance reduces that the original instances.

LDPC encode circuit computing f (x) = •G given H.

Let

H = A B C D E F where E ∈ F g×g , C ∈ F s×s . Abort if C is not lower triangular with ones on the diagonal or if E := -F C -1 B + E is not invertible. Precompute -E -1 . 2. Initialize w ∈ F n s.t. w = [x|p|p |p ], p ∈ {0} g , p , p ∈ {0} s and compute w :=     I k 0 0 0 0 Ig 0 0 A 0 0 0 0 0 0 Is     w i.e. p := Ax . 3. For in order i ∈ [s], w :=     I k 0 0 0 0 Ig 0 0 0 0 Is 0 0 0 U V     w
where U = {0} s×s except for Ui,i = 1 and V = Ci except for Vi,j = -Ci,j for j ∈

[i -1] and Vi,i = 0. That is, p i := p i -j∈[i-1] Ci,jp j = (C -1 Ax )i. 4. Compute w :=     I k 0 0 0 D 0 0 -F 0 0 Is 0 0 0 0 Is     w , w :=     I k 0 0 0 0 -E -1 0 0 0 0 Is 0 0 0 0 Is     w , w :=     I k 0 0 0 0 Ig 0 0 0 B Is 0 0 0 0 Is     w i.e. p := -F p + Dx = (-F C -1 A + D)x , then p := (-E -1 )p = -E -1 (-F C -1 A + D)x ,

Let H

= A B C D E F where E ∈ F g×g , C ∈ F s×s . Abort if C is not lower triangular with ones on the diagonal or if E := -F C -1 B + E is not invertible. Precompute -E -1 . 2. Initialize w := [e||p ] and decompose it as w = [x|p|p |p ] s.t. p ∈ F g , p ∈ F s , p ∈ {0} s . 3. For reverse order i ∈ [s], w := w     I k 0 0 0 0 Ig 0 0 0 0 V 0 0 0 0 Is     where V = Ci except for Vi,j = -Ci,j for j ∈ [i -1] and Vi,i = Ci,i. That is, for j ∈ {j ∈ [i -1] | Ci,j = 0} compute p j := p j -Ci,jp i . 4. Compute w := w     I k 0 0 0 0 Ig 0 0 0 B Is 0 0 0 0 Is     , w := w     I k 0 0 0 0 -E 0 0 0 0 Is 0 0 0 0 Is     , w := w     I k 0 0 0 D 0 0 -F 0 0 Is 0 0 0 0 Is    
i.e. p := p + p B, then p = p (-E -1 ), and finally x := x + pD, p := p -pF . 5. For reverse order i ∈ [s],

w := w     I k 0 0 0 0 Ig 0 0 0 0 Is 0 0 0 U V    
where U = {0} s×s except for Ui,i = 1 and V = Ci except for Vi,j = -Ci,j for j ∈ [i -1] and Vi,i = 0. That is, p i := p i + p i and p j := -Ci,jp i for j ∈

[i -1]. 6. compute w := w     I k 0 0 0 0 Ig 0 0 A 0 Is 0 0 0 0 Is     i.e. x := x + p A. 7. Output x.
Fig. 12: LDPC encoder with running time O(n + g 2 ) where H ∈ F n×(n-k) is that code parity check matrix and approximate lower triangular with gap g. Note that while H might have good minimum distance, there is a chance that H does not. For example, consider the last s < (n -k) columns of H, with some probability on the first k sparse columns has non-zero elements only in the last s rows. As such, this column can be express as a linear combination of the last s columns. Depending on the weight of the columns and how large s is, this can happen with good probability. This leads us to the idea that a bad code (i.e. H ) can be "patched" by setting certain positions of e to be uniform. Each one of these positions effectively allows us to nullify a linear dependency in the rows of H .

In the dual setting, recall that we are computing e G = u , where G is the generator for the parity check matrix H . Again, we simply need to ensure that the last g positions of e are uniformly distributed.

This then gives us a linear time algorithm for computing e G which leveraging the fact that H is strictly lower triangular. However, this comes at the expense of making the vector-OLE and silent-OT key setup slightly more expensive, i.e. g ∈ {24, 32} more base OTs.

For silent OT, recall that we use t instances of a distributed point function to construct e∆, with weight t. Here, e ∈ {0, 1} n is a binary vector with weight t while ∆ ∈ F is a field element, i.e. scaler. The parties will receive secret shares u, v of e∆ while the receiver receives e and the sender receives ∆. From this, they can construct the OT correlations by locally computing uG , eG and v . Silent VOLE is effectively the same except that e has its non-zero elements uniform in F.

Therefore, the added cost of this approach is creating this correlation for e * ∆ ∈ F g and the we do the same computation except with e = [e|e * ] instead of e. In the Silent OT case, e * can be computed with g OTs. Computing shares of e along requires approximately t log 2 n ≈ 1200 OTs. Here, t is the weight of e and depends on the parameters used. Therefore if we set g ≤ t log 2 n, the overall communication overhead is at most 2×.

F Silver Code Details

We node give a concrete instantiating of our Slv5 code with column weight t ∈ {5, 11}. The left m × m submatrix L consists of weight t columns where each is a cyclic shift by 1 of the previous. For t = 5 the first column has non-zero locations rows {0, 0.372071, 0.576568, 0.608917, 0.854475} • m while for t = 11 the first column is {0, 0.00278835, 0.0883852, 0.238023, 0.240532, 0.274624, 0.390639, 0.531551, 0.637619, 0.945265, 0.965874} • m. For small m, if two non-zero locations collide we insert into the next non-zero position.

We define the non-extended version of the right m × m -g matrix R by the following square submatrices. For t = 5 (left) and t = 11 (right) we have

                           
0 4 11 15 0 8 9 10 1 2 10 14 0 5 8 15 3 13 14 15 2 4 7 8 0 9 12 15 1 6 8 14 4 5 6 14 1 3 8 13 3 4 7 8 3 5 9 13 8 11 12 14 6 10 12 13 2 7 8 13 0 6 10 15

                                                                                        6
                                                           
Each row specifies the non-zero locations at a relative offset of g positions left of the main diagonal, where g is 16, 32 respectively. In particular, this will result in each (non-edge case) row/column having exactly t non-zero positions. This is then augmented with the additional width 1 non-zero diagonal located a positions 5, 31 below this main diagonal.For example, with m = 55 and t = 5 we obtain

                                                                                                         
1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 1 1 0 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 1 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 1 1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 1 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 1

                                                                                                         
Alternative instantiations based on our methodology can be obtained from the source code located at [Rin] along with our implementation of the noise impulse method.

Lemma 6 .

 6 Let D = {D m,n } m,n∈N denote a family of noise distributions over F n . Let C be a probabilistic code generation algorithm s.t. C(m, n) → A ∈ F n×m . Then for any d ∈ N, the (D, C, F)-LPN(m, n) assumption with dimension m = m(λ) and n = n(λ) samples is (ε d , δ d )-secure against linear tests, where

  We begin with an overview of how to perform fast encoding of LDPC codes by leveraging the sparsity/structure of H. Let us first review the naive encoding method. Recall H defines the code C = {c | Hc = 0}. As such, define the systematic form H for the same code by performing elementary row operations on H to obtain H = [-P T |I n-k ]. Since elementary row operations do not change the null-space, we have C = {c | Hc = 0} = {c | H c = 0}. Although H is sparse, P ∈ F k×m is likely dense. Let G := [I k |P ] be the symmetric form generator and then encoding can be achieved by computing c := xG for x ∈ F k . The cost of this is O(n 3 ) time to compute P and O(n 2 ) time to compute xP . However, we can also use the fact that Hc = 0 to encode x into c. Recall that c = xG = [x|c ] for c := xP . Therefore we can rewrite this as

For

  computing the exact minimum distance we make use of the so-called Brouwer-Zimmerman algorithm as described in [Gra06], and implemented in [HIQO19]. Loosely speaking, this approach iteratively refines a lower and upper bound until they are equal. First, the generator matrix G is placed in systematic form G = [I k |P ]. Recall that for all x ∈ F k \ {0}, the corresponding codeword is c = [x|xP ] and therefore clearly |c| ≥ |x|. Using this observation, the algorithm proceeds by initializing the lower bound = 1 and upper bound u = m + 1. All x with |x| = are encoded as c = xG and the upper bound u is replaced as the minimum weight over all codewords considered. While u = , is incremented and the process is repeated. See [Gra06, HIQO19] for details.

  a) Sample R matrix for Slv1 with g = t = 2Average minimum distance of weight t = 5 codes.

Fig. 1 :

 1 Fig. 1: Example of R and distance of Slv1, uniform, TZ for weight t = 5.

  a) Sample R matrix for Slv2 with t davg of column weight 5 codes.

Fig. 2 :

 2 Fig. 2: The alterations in Slv2 along with the minimum distance performance.

  The negative effect on average minimum distance of having repeats of p ∈ {1, 2} vs p ≥ 3.

Fig. 3 :

 3 Fig. 3: Performance of Slv3 and Slv4 with p ∈ {1, 2, 3} vs uniform.

Fig. 4 :

 4 Fig. 4: Average minimum distance of uniform, Slv5 and TZ for weight t ∈ {5, 11}.

Fig. 5 :

 5 Fig. 5: Running times (ms) of encoding algorithms for LPN with n length vector.

Fig. 6 :

 6 Fig. 6: Single thread running time (ms) and communication (KB) to perform m correlated oblivious transfers in the LAN setting.Vole Performance. We implement the generalization of[BCG + 19a] for performing vole. The protocol is largely the same as the OT variant except that f more OTs on strings of length O(κf ) need to be performed where f is the log of the field size, i.e. f = 128. For our protocol we use the binary Slv5 code while the noise vector is distributed over the while field. The security of this optimization is discussed in Section C.2. We compare with the vole protocol of [WYKW20] (a generalization of [YWL+ 20]) which is based on Primal LPN and therefore requires a one time setup sub-protocol. We also compare to the 1-out-of-N OT protocol of [OOS17] due to vole also supporting this functionality via hashing.We observe that our protocol significantly out performs both of these works. Moreover, [WYKW20] performs a vole over a field of size 2 61 -1 while our implementation is for the Galois field of size 2 128 . As such, this effectively halves their communication. Similarly, [OOS17] has an analogous field size of 2 79 . Despite working over a larger field, the running time of our protocol 4× faster than [WYKW20] at m = 4 × 10 7 and 22× faster than[OOS17]. Similarly, at m = 4 × 10 7 our protocols requires between 5 to 8× less communication than [WYKW20] depending on if their setup is include and 6200× less than [OOS17].

Fig. 7 :

 7 Fig. 7: Single thread running time (ms) and communication (KB) to perform m voles (or 1-out-of-N OTs for [OOS17]) in the LAN setting.

Fig. 8 :

 8 Fig. 8: Example Tanner Graph

2,

  we denote by (A 1 , • • • , A n ) the rows of A, and by (A 1 , • • • , A m ) its columns. For any subset S ⊆ [n] of the rows of A, we call column-neighbors of S in A, and writeN c A (S) ⊆ [m], the subset of the columns of A which have at least one 1 in a row of S. For any integer d, we say that A has the d-unique column-neighbor property if for any set S ⊆ [n] with |S| ≤ d, there exists a column A j of A such that A j [S] contains exactly a single 1.Lemma 8 ([MST03]). If A ∈ F n×m 2 has d-unique column-neighbor, then dd(A) ≥ d -1.Proof. For any subset S of [n] with |S| ≤ d, there exists a column of A that has exactly one 1 in a row indexed by S, hence i∈S A i = 0 m .

Fig. 9 :

 9 Fig. 9: The structure of an g approximate lower triangular matrix. The diagonal of C should all be ones.

  and finally p := p + Bp = Ax + Bp . 5. For in order i ∈ [s], Ci except for Vi,j = -Ci,j for j ∈ [i -1] and Vi,i = Ci,i. That is, p i := p i -j∈[i-1] Ci,jp j = C -1 (Ax + Bp )i. 6. Output the codeword c := [m|p|p ].

Fig. 10 :

 10 Fig. 10: LDPC encoder with running time O(n + g 2 ) where H ∈ F n×(n-k) is that code parity check matrix and approximate lower triangular with gap g.

Fig. 11 :

 11 Fig. 11: Simplified LDPC encoder with running time O(n) where H ∈ F n×(n-k) is that code parity check matrix and strictly lower triangular.

Table 1 :

 1 The minimum d min , average d avg and maximum d max minimum distance obtained over 100 trials for weight 5 uniform LDPC codes.

	m	method	w	d min	davg	dmax
	20	impulse exact	1 -	2 2	5 5	6 6
	40	impulse exact	1 -	4 4	8.3 8.3	10 10
	60	impulse impulse exact	1 2 -	8 8 8	11.44 11.38 11.38	14 14 14
	80	impulse impulse exact	1 2 -	12 12 12	16.48 14.86 14.86	20 18 18
	100	impulse impulse	1 2	16 14	22.28 18.2	26 20

  expanding, then it has d-unique column-neighbor. Proof. Assume that A does not have d-unique column-neighbor. Let S ⊆ [n] be any subset with |S| ≤ d. Then for every j ∈ N c A (S), A j [S] contains at least two 1's. Since the rows in S contain t • |S| 1's in total, this implies that |N c A (S)| ≤ (t/2) • |S|.

  t•|S| . Since there are n |S| choices for S and m t|S|/2 choices for T , the probability that A fails to be (d, t/2)-expanding is at most

Excluding edge cases for the first and last set of g rows.

While expansion properties are most commonly given over graphs, the extension to matrices is straightforward: our definition simply says that a matrix A is (d, α)-expanding if it is the adjacency matrix of a (d, α)-expanding bipartite graph.

A similar statement actually holds for any c(m) = o( √ m/(log m) 3/4 ) (see [MST03]), but the weaker statement suffices in our context.