Geoffroy Couteau
email: couteau@irif.fr

Maryam Zarezadeh
email: maryam.zarezadeh@barkhauseninstitut.org

Non-Interactive Secure Computation of Inner-Product from LPN and LWE

We put forth a new cryptographic primitive for securely computing inner-products in a scalable, non-interactive fashion: any party can broadcast a public (computationally hiding) encoding of its input, and store a secret state. Given their secret state and the other party's public encoding, any pair of parties can non-interactively compute additive shares of the inner-product between the encoded vectors. We give constructions of this primitive from a common template, which can be instantiated under either the LPN (with non-negligible correctness error) or the LWE (with negligible correctness error) assumptions. Our construction uses a novel twist on the standard non-interactive key exchange based on the Alekhnovich cryptosystem, which upgrades it to a non-interactive inner product protocol almost for free. In addition to being non-interactive, our constructions have linear communication (with constants smaller than all known alternatives) and small computation: using LPN or LWE with quasi-cyclic codes, we estimate that encoding a length-2 20 vector over a 32-bit field takes less that 2s on a standard laptop; decoding amounts to a single cheap inner-product. We show how to remove the non-negligible error in our LPN instantiation using a one-time, logarithmic-communication preprocessing. Eventually, we show to to upgrade its security to the malicious model using new sublinear-communication zero-knowledge proofs for low-noise LPN samples, which might be of independent interest.

Introduction

In this work, we put forth a new approach for non-interactive secure computation of inner products, one of the most basic and fundamental functionalities in secure computation. Our approach can be instantiated under either the learning parity with noise (LPN) or the learning with error (LWE) assumptions, two of the most important post-quantum assumptions. It builds upon a simple but powerful observation: a well-chosen tweak of the Alekhnovich key exchange [START_REF] Alekhnovich | More on average case vs approximation complexity[END_REF] turns it into a non-interactive secure protocol for approximately computing inner products. Borrowing tools from the recent line of work on pseudorandom correlation generators [START_REF] Boyle | Compressing vector OLE[END_REF][START_REF] Boyle | Efficient two-round OT extension and silent non-interactive secure computation[END_REF][START_REF] Boyle | Efficient pseudorandom correlation generators: Silent OT extension and more[END_REF], we show how to turn this into full fledged secure protocols for inner product, using a small preprocessing phase with communication much smaller than the length of the vectors, both in the semi-honest and in the malicious setting.

Secure Inner-Product Made as Easy as Non-Interactive Key Exchange

To better capture the attractive efficiency features of our protocols, we introduce the notion of non-interactive inner product (NIIP) protocols. At a high level, a NIIP specifies a pair of algorithm, Encode and Decode, where:

-Encode takes an input vector x ∈ F n over some field F, and produces a pair (pk x , sk x ). pk x is the public encoding, and sk x is the secret state. All parties can publicly reveal the encodings pk x , since they computationally hide their vectors x. -Decode takes as input a public encoding pk x , and a secret state sk y , and outputs a value z, such that the following holds: z = Decode(pk x , sk y ) and z = Decode(pk y , sk x ) form additive shares of the inner product x •y = z+z over F.

Therefore, an NIIP provides a very appealing way to compute inner products with a minimalistic interaction pattern: multiple parties can compute and publish encodings of their input ahead of time, locally keeping the secret state. Then, whenever two parties want to securely compute the inner product between their inputs, they can locally and non-interactively decode the other party's public encoding with their own secret state, and obtain additive shares of the output. One can compare this interaction pattern to the interaction pattern of non-interactive key exchange: after broadcasting their public keys, any two individuals from a network can locally compute a shared secret key. We achieve exactly the same interaction pattern, but for the significantly more "advanced" functionality of securely computing (shares of) inner products. We believe that this minimalistic interaction pattern makes our construction very appealing in many natural scenarios, and allow them to scale more efficiently to large networks of users (which is typically a bottleneck for secure computation).

LPN-based Instantiation. Our primary instantiation of this approach relies on the learning parity with noise assumption. There, we only achieve correctness up to a vanishing (but non-negligible) error term ε, which is of the order of λ 2 /n, where λ is a security parameter, and n is the vector dimension. Therefore, our protocol provides non-trivial correctness only for values of n > λ 2 . We note that this is likely to be optimal: an NIIP with a much smaller correctness error would imply an LPN-based key exchange under LPN with noise rate higher than √ n, which is a famous and long-standing open problem. Furthermore, we improve the protocol in two ways:

-Using an input-independent preprocessing phase with sublinear communication O(log n) (where the O(•) hides poly(λ) factors), the protocol can be made perfectly correct. This construction builds upon the recently introduced notion of pseudorandom correlation generators. -By developing new types of zero-knowledge proofs with sublinear communication tailored to our protocol, we show how the security of our protocol can be enhanced from semi-honest to malicious, at a small cost. Our new zero-knowledge proofs, which demonstrate knowledge of a sparse vector in the kernel of a matrix with communication sublinear in the dimension (but linear in the sparsity), are of independent interest.

LWE-based Instantiation. Our second instantiation is based on the learning with error assumption. There, we focus on the semi-honest setting, and directly achieve a full-fledged (negligible error) NIIP, without any preprocessing. This makes our protocol highly versatile in environments where it is desirable to minimize interactions. Furthermore, our LWE-based instantiation can be shown to provide information-theoretic security for one of the two parties.

Efficiency, Discussions and an Open Question

In addition to their optimal interaction pattern, our protocols have linear communication O(n), with concrete small constants. Specifically, the constant is always smaller than 6, and can be asymptotically reduced to 2 + for arbitrarily small when n grows (approaching the -optimal -cost of just exchanging the two vectors in the clear). In terms of computation, using relatively standard variants of LPN (or LWE) with a quasi-cyclic matrix, our protocols have O(n • log n) computational complexity, where the cost is dominated by that of doing a matrix-vector multiplication with a quasi-cyclic matrix (this boils down to computing FFT's in dimension n). For n ≈ 10 7 , using the library of [START_REF] Chen | Multiplying boolean polynomials with frobenius partitions in additive fast fourier transform[END_REF], the full matrix multiplication can be executed in less than 2 seconds on a personal laptop, according to the implementation of [START_REF] Boyle | Efficient two-round OT extension and silent non-interactive secure computation[END_REF].

The LPN assumption with quasi-cyclic codes is relatively well studied [START_REF] Aguilar | Efficient encryption from random quasi-cyclic codes[END_REF][START_REF] Aguilar-Melchor | Efficient encryption from random quasi-cyclic codes[END_REF][START_REF] Boyle | Efficient two-round OT extension and silent non-interactive secure computation[END_REF], and has been used in recent submissions to the post-quantum NIST competition [START_REF] Aguilar-Melchor | Efficient encryption from random quasi-cyclic codes[END_REF][START_REF] Aragon | Bike: bit flipping key encapsulation[END_REF][START_REF] Melchor | Hamming quasi-cyclic (hqc)[END_REF]. There exist other candidate codes which lead to a much greater efficiency and are believed to provide secure variants of LPN; one standard such example is Alekhnovich assumption [START_REF] Alekhnovich | More on average case vs approximation complexity[END_REF], which states that LPN remains hard when instantiated with a sparse code. However, our constructions require LPN to be simultaneously hard with respect to the code and its dual code. Intriguingly, to our knowledge, no code with fast encoding and fast dual encoding is known to provide (plausibly) secure LPN variants with respect to the code and its dual (for example, LPN with respect to the dual of sparse codes, which are LDPC codes, is easy due to the existence of efficient algorithms for LDPC codes). Hence, this raises an intriguing open question: Are there linear-time encodable codes whose dual is also linear time encodable, such that both the code and its dual lead to hard LPN variants? As we will discuss, this question is strongly related to the question of finding linear-time encodable codes where both the code and its dual are good codes (i.e., have linear minimum distance), a problem which seems to be still open in coding theory (but does not seem to have been studied much). A positive answer would provide a linear-time variant of the Alekhnovich cryptosystem, which would lead to significant improvements in LPN-based encryption. Furthermore, it would make our protocol strictly linear time as well. We believe that this question is therefore an important open question, whose study could open the road to strong efficiency improvements in LPN-based public-key cryptography.

Comparison to the State of the Art

Many methods from the literature can be used to securely compute inner products. We go through the main options here, and compare them to our result.

From OT/OLE. A first option is to use generic oblivious-transfer-based secure computation for inner product. This works especially well over F 2 , since the inner product between n bit vectors can be reduced to n oblivious transfers (OT). Using recent advances in silent OT extension [START_REF] Boyle | Compressing vector OLE[END_REF][START_REF] Boyle | Efficient two-round OT extension and silent non-interactive secure computation[END_REF][START_REF] Boyle | Efficient pseudorandom correlation generators: Silent OT extension and more[END_REF], this can be done with asymptotic communication approaching three bits per oblivious transfer.

However, things become significantly more complicated over larger fields. To handle multiplications over a larger field F, the standard OT-based method [START_REF] Gilboa | Two party RSA key generation[END_REF] induces a log |F| overhead in the total number of OTs, which can quickly get prohibitive. A more efficient alternative is to build on recent advances in batch oblivious linear evaluation (OLE) over general fields, since an inner-product between length-n vectors over F can be reduced to a batch of n OLEs over F. To our knowledge, the most efficient protocols for generating many OLEs are the work of [START_REF] Boyle | Efficient pseudorandom correlation generators from ring-LPN[END_REF], which constructs a "silent OLE extension" protocol assuming the hardness of ring-LPN over a fully-splitting ring, and the result of [START_REF] Baum | Efficient protocols for oblivious linear function evaluation from ring-LWE[END_REF]. Being silent, the protocol of [START_REF] Boyle | Efficient pseudorandom correlation generators from ring-LPN[END_REF] achieves an asymptotically optimal communication of 2n + o(n) elements of F, for a computational cost of Õ(n) operations.

Our protocol achieves essentially the same asymptotic communication, and our computational complexity is also essentially on par with theirs. However, we improve on three core aspects:

-Communication Pattern. The protocol of [START_REF] Boyle | Efficient pseudorandom correlation generators from ring-LPN[END_REF] requires running a generic, interactive secure computation protocol to generate the seeds for the silent OLE extension, before running a local expansion and "derandomizing" the pseudorandom OLEs with additional interaction. In contrast, we achieve a minimal interaction pattern, where a single encoding of the input is broadcast simultaneously by all parties. -Underlying Assumption. The protocol of [START_REF] Boyle | Efficient pseudorandom correlation generators from ring-LPN[END_REF] inherently requires a new "ring-LPN with fully splitting ring" assumption. In fact, their starting point is a construction based on a standard variant of LPN (LPN with quasi-cyclic codes, which we use here), which has superquadratic computational complexity Õ(n 2 ). Then, their new assumption is introduced as a way to overcome this quadratic overhead. In contrast, we directly achieve quasilinear overhead, under the standard LPN assumption over quasi-cyclic codes. -Concrete Efficiency. Measuring the concrete efficiency of [START_REF] Boyle | Efficient pseudorandom correlation generators from ring-LPN[END_REF] is relatively complex, but working out the parameters in the paper, the communication complexity of setting up the correlation is around 40 • n for n = 2 20 . For lower values of n, it is much higher, and it drops quickly for higher values of n (e.g. around 3 • n for n = 2 24 ). In contrast, our setup costs are minimal (e.g. around 0.7 • n for n = 2 20 ) In practice, this means that this approach will start to outperform our protocol communication-wise only for n > 2 24 .

As for the protocol of [START_REF] Baum | Efficient protocols for oblivious linear function evaluation from ring-LWE[END_REF], their communication overhead is ∼ 33% larger than ours for short-ish vectors (from 6n to 8n elements of F), and up to 4 times larger asymptotically (from (2 + ε)n to 8n elements of F). In addition, their construction requires a dedicated setup phase (while we only need a common random string). Their dedicated setup can be replaced with a PKI setup, at the cost of sacrificing further some efficiency. Other low-communication OLE protocols have been described in [START_REF] Orlandi | The rise of paillier: Homomorphic secret sharing and public-key silent OT[END_REF], but their concrete computational efficiency is significantly lower than that of [START_REF] Boyle | Efficient pseudorandom correlation generators from ring-LPN[END_REF].

From homomorphic encryption. Another standard solution is to rely on linearly homomorphic encryption, such as Paillier encryption [START_REF] Paillier | Public-key cryptosystems based on composite degree residuosity classes[END_REF]. In these solutions, one party encrypts its vector x and sends it to the other party, who homomorphically computes and sends back a rerandomized encryption of x • y, which the first party decrypts. For extremely large fields (log |F| 2048), one can achieve the smallest communication across all known alternatives, with a communication of only (n + o(n)) log |F| bits (i.e., essentially the cost of sending one of the two vectors in the clear), using a rate-1 homomorphic encryption scheme such as Damgård-Jurik [START_REF] Damgård | A length-flexible threshold cryptosystem with applications[END_REF]. However, this solution is not competitive with the previous approaches for any reasonable field sizes, communication-wise and computation-wise.

Using Ring-LWE-based linearly homomorphic encryption, a recent unpublished work [START_REF] De Castro | Fast vector oblivious linear evaluation from ring learning with errors[END_REF] devised a carefully optimized semi-honest OLE protocol. By tailoring their protocol to inner products, we estimate that their protocol can achieve a communication comparable to our semi-honest protocol. This comes at the cost of using PKI setup and not having a non-interactive communication pattern as we do (furthermore, our protocol can be based on LWE rather than Ring-LWE).

Applications

Inner products are a fundamental operation in many standard privacy-preserving applications. In many of these applications, the non-interactive structure of our new protocol enables a very appealing realization of these applications in a multiparty setting. This includes for example biometric authentication [START_REF] Osadchy | Scifi-a system for secure face identification[END_REF] or pattern matching [START_REF] Hazay | Computationally secure pattern matching in the presence of malicious adversaries[END_REF] (computing the Hamming distance between two strings can be non-interactively reduced to computing an inner product, since the Hamming distance between x and y is HW(x) + HW(y) -2 • x • y, where HW denotes the Hamming weight). With our non-interactive protocol, each user could publish a compact encoding associated to its fingerprint, and each authority could also have a list of public encodings of authorized fingerprints. Then, a user can authenticate himself with an authority with almost zero communication: the authority and the user locally compute shares of the Hamming distance, and the user reveal his share to the authority (a single field element). If the shares reconstruct to a value below the threshold, the authentication is successful.

Other applications can include distributed data mining and machine learning applications such as finding k-nearest neighbors (KNN) [START_REF] Wong | Secure knn computation on encrypted databases[END_REF], rule mining [START_REF] Dong | A fast secure dot product protocol with application to privacy preserving association rule mining[END_REF], decision trees [START_REF] Shuguo | Multi-party privacy-preserving decision trees for arbitrarily partitioned data[END_REF], support vector machine (SVM) classification [START_REF] Yu | Privacy-preserving svm classification on vertically partitioned data[END_REF], or privacy preserving neural network learning [START_REF] Bansal | Privacy preserving back-propagation neural network learning over arbitrarily partitioned data[END_REF][START_REF] Chen | Privacy-preserving backpropagation neural network learning[END_REF].

Inner products are also used in secure similarity measure protocols such as secure multi-keyword searchable schemes [START_REF] Li | A multi-keyword search algorithm based on polynomial function and safety inner-product method in secure cloud environment[END_REF], secure keyword similarity [START_REF] Liu | Prime inner product encoding for effective wildcard-based multi-keyword fuzzy search[END_REF], similar document detection for plagiarism prevention, copyright protection and duplicate submission detection (where similar documents between two entities should be detected while keeping documents confidential [START_REF] Jiang | N-gram based secure similar document detection[END_REF][START_REF] Murugesan | Efficient privacypreserving similar document detection[END_REF]), or secure profile proximity matching in social networks (e.g. in some applications, a user profile is defined as a vector of integers where attributes correspond to an interest; social proximity is defined as dot product of two user's vectors [START_REF] Cheng | A cloud aided privacy-preserving profile matching scheme in mobile social networks[END_REF]. Similar methods are used in secure protocols for friend discovery in mobile social networks [START_REF] Dong | Secure friend discovery in mobile social networks[END_REF]). In many of these applications, the non-interactive nature of our protocols can allow to design scalable, multi-user variants.

Preliminaries

Throughout the paper, we denote the security parameter by λ. We use uppercase letters like M to denote matrices, bold lower-case letters like v to denote row vectors, and for column vectors we use the transpose v . We write u ||v two denote the horizontal concatenations of (horizontal) vectors, and u//v to denote vertical concatenation. Eventually, we write x $ ← X (resp. x $ ← D) to denote that x is uniformly sampled from the set X (resp. randomly sampled according to distribution D). For a finite set S, we denote the uniform distribution on S by U(S). We denote by Ber τ the Bernoulli distribution with parameter τ , i.e., e ∼ Ber τ means that the random variable e evaluates to 1 with probability τ and to 0 with probability 1 -τ . More generally, we write Ber τ (F) to denote the distribution that outputs a uniformly random element of F with probability τ , and 0 otherwise (note that with this definition, Ber τ (F 2 ) = Ber (1+τ )/2 ; we ignore this slight discrepancy). We write D 0 c ≈ D 1 to denote that two (families of) distributions D 0 and D 1 are computationally indistinguishable. Eventually, we recall a standard lemma known in the LPN literature as the piling-up lemma: Lemma 1 (Piling-up Lemma). For any 0 < τ < 1/2 and random variables

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

Learning Parity with Noise

The learning parity with noise (LPN) assumption with dimension k, m noisy samples, and noise rate τ states that it is infeasible to distinguish (A, A • s + e) from random, where A is a random matrix in F m×k 2 , s is a random length-k vector, and e is a length-m vector whose entries are sampled from Ber τ . More generally, the LPN assumption can be formulated with respect to a family of linear codes over an arbitrary field F, in which case it states that it is hard to distinguish a noisy codeword A•s+e from random (where A is a generator matrix for a random code from the family). Formally, given a dimension k, number of samples m, and field F, let Code(m, k, F) be a probabilistic code generation algorithm that outputs a matrix A ∈ F m×k (A is viewed as the generator matrix of a linear code). Furthermore, we let Code ⊥ (m, m -k, F) be a probabilistic code generation algorithm for the dual of Code, which outputs random parity-check matrices B ∈ F m×m-k for a random code A ∈ Code(m, k, F) (i.e., a full-rank matrix B such that B •A = 0; B is a generator for the dual of the code generated by A). We define the LPN assumption over F with respect to a code Code below.

Definition 2 (Learning Parity with Noise). Fix a field F = F(λ), dimension k = k(λ), number of samples m = m(λ), and noise rate τ = τ (λ). The LPN m k,τ assumption with respect to Code states that

{(A, b) | A $ ← Code(m, k, F), e $ ← Ber τ (F) m , s $ ← F k , b ← A • s + e} c ≈ {(A, b) | A $ ← Code(m, k, F), b $ ← F m }
The above LPN assumption has an equivalent dual formulation: The dual-LPN m k,τ assumption with respect to Code ⊥ states that

{(H, b) | H $ ← Code ⊥ (m, m -k, F), e $ ← Ber τ (F) m , b ← H • e} c ≈ {(H, b) | H $ ← Code ⊥ (m, m -k, F), b $ ← F m-k }
The following is standard:

Lemma 4. For any F, k, m, τ and code generation algorithm Code, the LPN m k,τ (F) assumption with respect to Code and the dual-LPN m k,τ (F) assumption with respect to Code ⊥ are equivalent.

Standard codes and noise distributions. The classical LPN assumption is recovered by setting F = F 2 and Code to be the uniform distribution over F m×k 2 . However, the hardness of LPN is commonly assumed for other families of codes in the literature, such as sparse codes [START_REF] Alekhnovich | More on average case vs approximation complexity[END_REF] (often called the "Alekhnovich assumption"), quasi-cyclic codes (used in several recent submissions to the NIST post-quantum competition [START_REF] Aguilar-Melchor | Efficient encryption from random quasi-cyclic codes[END_REF][START_REF] Aragon | Bike: bit flipping key encapsulation[END_REF][START_REF] Melchor | Hamming quasi-cyclic (hqc)[END_REF]), Toeplitz matrices [START_REF] Gilbert | Good variants of HB+ are hard to find[END_REF][START_REF] Lyubashevsky | Man-in-the-middle secure authentication schemes from LPN and weak PRFs[END_REF] and many more. All these variants of LPN generalize naturally to larger fields (and LPN is typically believed to be at least as hard, if not harder, over larger fields).

In addition, it is also relatively common to consider alternative noise distributions beyond the Bernoulli noise. The two most standard choices are exact noise (where the noise is sampled uniformly from the set of all τ • m-sparse vectors of F m ) and regular noise (where the noise is a concatenation of τ • m random unit vectors of length 1/τ ). See [START_REF] Boyle | Compressing vector OLE[END_REF][START_REF] Boyle | Efficient pseudorandom correlation generators: Silent OT extension and more[END_REF] for discussions about these alternative noise distributions. We will denote by XN τ,m (F) (for eXact Noise) the exact noise distribution, and by RN τ,m (F) (for Regular Noise) the regular noise distribution.

Security of LPN and its variants. Numerous attacks on LPN have been devised. Among the most standard attacks are Gaussian elimination, which solves LPN in time and sample complexity Θ(1/(1 -τ ) k ) using Θ(k 2 ) memory, and its variants (e.g. pooled Gauss [START_REF] Esser | Lpn decoded[END_REF], and BKW [START_REF] Blum | Noise-tolerant learning, the parity problem, and the statistical query model[END_REF]), and the Information Set Decoding attacks (introduced by Prange [START_REF] Prange | The use of information sets in decoding cyclic codes[END_REF] and further improved in a long sequence of papers, see e.g. [START_REF] Becker | Decoding random binary linear codes in 2 n/20: How 1+ 1= 0 improves information set decoding[END_REF][START_REF] Bernstein | Smaller decoding exponents: ball-collision decoding[END_REF]). In this work, we will be interested in variants of LPN with a very low number of samples (linear in the dimension) and a very low noise rate. This has several consequences: first, algorithms such as BKW (which require a very large number of samples) do not apply, and using a regular noise distribution has no known effect on security (in contrast, if the number of samples is at least quadratic in the dimension, attacks such as the Arora-Ge attack [START_REF] Arora | New algorithms for learning in presence of errors[END_REF] can take advantage of the noise structure). Second, in the very low-noise regime, all improved variants of ISD become equivalent to the original (much simpler) algorithm of Prange.

We point out that increasing the field size beyond 2 is not known to reduce security (and actually seems to slightly improve security with respect to known attacks), and neither does using a different family of linear code, as long as they are good codes (i.e. a random code from the family has a linear minimum distance with high probability). A small exception to that are quasi-cyclic codes, where the strong structure allows for the DOOM attack [START_REF] Sendrier | Decoding one out of many[END_REF], which slightly reduces security (but can be easily compensated by a small increase in the noise rate). We refer the reader to [START_REF] Boyle | Compressing vector OLE[END_REF][START_REF] Boyle | Efficient two-round OT extension and silent non-interactive secure computation[END_REF][START_REF] Boyle | Efficient pseudorandom correlation generators: Silent OT extension and more[END_REF][START_REF] Boyle | Efficient pseudorandom correlation generators from ring-LPN[END_REF] for more detailed discussions on the security of LPN with various types of noise distributions and code ensembles. As a rule of thumb, though: in our parameter setting, all known attacks will have a complexity of the form 2 O(τ •m) . Hence, fixing the noise rate τ to λ/m for some fixed security parameter λ suffices to achieve exponential security (in λ) against all known attacks.

Learning with Errors

The learning with errors (LWE) assumption is a close variant of the LPN assumption. In essence, and using our generalized definition of LPN, the LWE assumption with dimension k, and m samples, is simply the LPN assumption over Z q (for some large enough prime q) with respect to a different noise distribution, which trades sparsity for small magnitude -i.e., instead of being a distribution over vectors whose entries are mostly zero, the noise distribution samples vectors whose entries are small in magnitude. Multiple choices of such noise distributions are standard in the literature, including discrete Gaussian noise, or noise sampled uniformly from [-B, B], where B q is a bound on the magnitude. We call 'LWE m k (Z q , χ) with respect to Code' the LWE assumption with dimension k, m samples, over Z q , with noise vector sampled from χ m and matrix sampled from Code.

Rounding lemma. Let x denotes the rounding of x ∈ R to the nearest integer. We recall the rounding lemma, from [START_REF] Boyle | Homomorphic secret sharing from lattices without FHE[END_REF]:

Lemma 5 (Rounding of noisy shares). Let (p, q) be two integers with q/p ∈ N. Fix any z ∈ Z p , and (t 0 , t 1 ) be two random elements of Z q subject to t 0 + t 1 = (q/p) • z + e mod q, where e is such that q/(p • |e|) ≥ λ ω(1) (λ is a security parameter). Then with probability at least 1 - (1) , it holds that R(t 0 ) + R(t 1 ) = z mod p, where R is the deterministic rounding function R : x → (p/q)•z mod p and the probability is over the random choice of (t 0 , t 1 ).

(|e| + 1) • p/q ≥ 1 -λ -ω

Non-Interactive Approximate Inner Product from LPN and LWE

In this section, we describe a general non-interactive protocol for securely computing the inner product between two vectors over F n , with ε correctness error (independent of the value of the inputs). Our general protocol can be instantiated either under the LPN assumption, in which case the error will be noticeable (but arbitrarily small), or under the LWE assumption (in which case the error can be made negligible). Our protocol enjoys an attractive key exchange structure: consider two parties Alice and Bob with respective inputs

(u, v) ∈ F n × F n .
The protocol has the following interaction pattern:

-First, Alice and Bob broadcast encodings of their respective vectors (u, v), denoted pk u and pk v , and locally keep a private state, which we denote by sk u and sk v respectively. The encodings have length O(n) (the O(•) hides a small constant) and computationally hide the vector they encode. -Second, Alice (resp. Bob) can locally compute α ← Decode(pk v , sk u ) (resp.

β ← Decode(pk u , sk v )), where Decode is some deterministic decoding algorithm. The values α and β form additive shares of a value w ∈ F, where it holds that w = u • v with probability at least ε (over the random coins of the encoding procedure).

We call a protocol with the above interaction pattern a non-interactive approximate inner-product protocol (NIAIP). We formalize this notion below.

Non-Interactive Approximate Inner Product

Definition 6. A non-interactive ε-approximate inner-product protocol (ε-NIAIP) over a field F is a tuple of probabilistic polynomial-time algorithms (Setup, Encode, Decode) such that Decode is deterministic, and -Setup(1 λ ) : on input the security parameter 1 λ in unary, outputs a common reference string (CRS) crs.

-Encode(crs, b, u) : on input the CRS crs, a bit b, u ∈ F n , outputs a pair (pk b , sk b ); -Decode(crs, pk, sk ) : on input the CRS crs, a public encoding pk and a secret state sk , outputs a value γ ∈ F.

Furthermore, an NIAIP must satisfy two properties:

ε-Correctness. For every common reference string crs in the domain of Setup(1 λ ) and every pair (u 0 , u 1 ) ∈ F n × F n of vectors, it holds that

Pr[Decode(crs, pk 0 , sk 1 ) + Decode(crs, pk 1 , sk 0 ) = u 0 • u 1 ] ≥ ε(λ, n),
where the probability is taken over the joint random coins of both instances of Encode, ((pk b , sk b )

$ ← Encode(crs, b, u b )) b∈{0,1} .
-Indistinguishability. For every b ∈ {0, 1}, the advantage of any (stateful) probabilistic polynomial-time (PPT) adversary A in distinguishing the following two experiments, parametrized by a bit σ, is negligible:

• A receives crs $ ← Setup(1 λ ) and outputs u ∈ F n .
• The challenger samples a pair (pk b , sk b )

$ ← Encode(crs, b, v)
, where v is 0 n if σ = 0, and v = u otherwise. The challenger sends pk b to A.

A note on syntax. We note that in the above definition, the parties have fixed roles. In a multiparty setting, if all pairs of parties want to compute inner products, this means that they must publish two encodings of their input, one with role 0, and one with role 1. In many applications, however, it is natural to have "type-0" and "type-1" parties (e.g. clients and servers), such that secure computations tasks are only carried between a type-0 and a type-1 party.

A (1 -τ 2 m)-NIAIP from LPN

We now proceed with the construction of an ε-NIAIP, from the learning parity with noise assumption. The construction is relatively simple in hindsight, and quite elegant; it is a natural twist on the Alekhnovich cryptosystem. The construction is parametrized by a field F, and a vector length n. We let k(n), m(n) denote respectively a dimension parameter and a number of samples, both to be specified later (but the reader can think of k and m as linear in n, e.g. k = 2n and m = 4n), and t = t(λ, n) denote a noise parameter (the reader can consider t = λ to be a reasonable choice). Let Code be a probabilistic code generation algorithm. The construction is represented on Figure 1.

Before we state the theorem, we introduce some notation: let Code ⊥ right be the code generator that samples a random matrix Proof. We first prove ε-correctness. Observe that for any pair of inputs (u 0 , u 1 ) ∈ F n × F n and every matrix H ∈ F m×k+n , it holds that Decode(crs, pk 0 , sk 1 ) + Decode(crs, pk 1 , sk 0 )

H $ ← Code ⊥ (m, k + n, F) (hence H ∈ F m×k+n
= pk 0 • sk 1 + pk 1 • sk 0 = ((u 0 //0) -H • r 0 ) • (u 1 //s) + (H • (u 1 //s) + r 1 ) • r 0 = (u 0 ||0 ) • (u 1 //s) -r 0 • H • (u 1 //s) + (u 1 //s) • H • r 0 + r 1 • r 0 = u 0 • u 1 -r 0 • H • (u 1 //s) + (r 0 • H • (u 1 //s)) + r 1 • r 0 = u 0 • u 1 + r 1 •
r 0 (since the transpose of a single field element is itself). Now, since r 0 and r 1 are random Bernoulli noise vectors with rate τ , we have

Pr[r 1 • r 0 = 0] ≥ 1 -m • τ 2 , since Pr[r 1 • r 0 = 0] ≥ Pr[r (i) 0 • r (i) 1 = 0∀i ≤ m], which equal to 1 -Pr[∃i, r (i) 0 • r (i) 1 = 1] ≥ 1 -mτ 2 ,
using a straightforward union bound and the fact that Pr[r

(i) 0 • r (i) 1 = 1] = τ 2 for any i.
We now prove indistinguishability, for b = 0 and b = 1. We proceed in a sequence of games of the form G i b,σ :

-Game G 0 0,0 is the initial game, with bits b = 0 and σ = 0. The challenger samples

H $ ← Code ⊥ (m, k + n, F). Upon receiving u ∈ F n from A(crs), the challenger returns pk 0 ← 0 k+n -H • r 0 , where r 0 is a random Bernoulli noise.
-Game G 1 0,0 : the challenger first receives a challenge, denoted (H, c), for the dual-LPN m m-(k+n),τ assumption with respect to Code ⊥ , where c is H • e for some noise vector e. Upon receiving u ∈ F n from A(crs), the challenger returns pk 0 ← 0 k+n -c. This game is perfectly indistinguishable from the previous one. -Game G 2 0,0 is exactly as Game G 1 0,0 , except that c is now a random vector from F m . Observe that distinguishing between G 1 0,0 and G 2 0,0 is exactly solving the dual-LPN m m-(k+n),τ assumption with respect to Code ⊥ . -Game G 3 0,0 : the challenger proceeds as in Game G 2 0,0 , except that it outputs pk 0 $ ← (u//0)-c. Since c is a uniformly random vector, this game is perfectly indistinguishable from the previous one.

-Game G 4 0,0 : as the previous one, except that c is back to being of the form H • e for some noise vector e. Distinguishing this game from G 3 0,0 is exactly solving the dual-LPN m m-(k+n),τ assumption with respect to Code ⊥ . -Game G 0 0,1 : this game is simply the initial game with bits b = 0 and σ = 1. Game G 0 0,1 is perfectly indistinguishable from G 4 0,0 .

From the above, we conclude that the advantage of any polynomial time adversary in the indistinguishability experiment with b = 0 is at most twice its advantage against the dual-LPN m m-(k+n),τ (F) assumption with respect to Code ⊥ . We now address the case b = 1.

-Game G 0 1,0 is the initial game, with bits b = 1 and σ = 0. The challenger samples -Game G 2 1,0 is exactly as Game G 1 0,0 , except that c is now a random vector from F m . Observe that distinguishing between G 1 0,0 and G 2 0,0 is exactly solving the LPN m k,τ assumption with respect to Code ⊥ right . -Game G 3 1,0 : the challenger proceeds as in Game G 2 0,0 , except that it outputs pk 0 $ ← H left •u+c. Since c is a uniformly random vector, this game is perfectly indistinguishable from the previous one.

H $ ← Code(m, k + n, F). Upon receiving u ∈ F n from A(crs), the challenger returns pk 1 ← H • (0 n //s) + r 1 ,
-Game G 4 1,0 : as the previous one, except that c is back to being of the form H right •s+e. Distinguishing this game from G 3 0,0 is exactly solving the LPN m k,τ assumption with respect to Code. -Game G 0 1,1 : this game is simply the initial game with bits b = 1 and σ = 1.

Since H • (u//s) = H left • u + H right • s, Game G 0 0,1 is perfectly indistinguishable from G 4 0,0 .
From the above, we conclude that the advantage of any polynomial time adversary in the indistinguishability experiment with b = 1 is at most twice its advantage against the LPN m k,τ (F) assumption with respect to Code ⊥ right . This concludes the proof.

Non-Interactive Inner Product from LWE

A simple variant of our construction of non-interactive approximate inner-product leads to a construction under the learning with error (LWE) assumption. Unlike its LPN-based counterpart, this variant can actually achieve correctness exponentially close to 1.

Let F p be the prime-order field over which we want to compute a noninteractive inner-product. Fix a bound B on the magnitude of the noise. Let Z q be a ring, for some multiple q of p of size q > (m (1) . The variant is described on Figure 2. Eventually, we let χ denote a noise distribution. The exact choice of χ does not matter much, but we assume that all entries in a random sample from χ m belong to [-B, B] with overwhelming probability. Note that we follow an LPN-style description, by viewing the matrix of the LWE assumption as the generator matrix of some linear code over the ring Z q . While this is not so common in the LWE literature, this viewpoint allows for considerations on the choice of better codes to improve efficiency. -H • r 0 is used to mask (q/p) • (u//0) instead of (u//0), and the output of Decode is fed to the rounding procedure R of the rounding lemma (Lemma 5) which, on input x ∈ Z q , outputs R(x) = (p/q)•x mod p.

• B 2 + 1) • p • λ ω
Using the same analysis as for the correctness of the LPN-based protocol, if (pk 0 , sk 0 ) and (pk 1 , sk 1 ) are encodings of two inputs (u 0 , u 1 ) ∈ F p × F p , we have

pk 0 • sk 1 + pk 1 • sk 0 = (q/p) • u 0 • u 1 + r 1 • r 0 , where |r 1 • r 0 | ≤ m • B 2
. Let e ← r 1 • r 0 denote the output noise and z ← u 0 • u 1 denote the target output. The values pk 0 • sk 1 and pk 1 • sk 0 form random shares of (q/p) • z + e over Z q with |e| ≤ m • B 2 . Therefore, by the rounding lemma (Lemma 5), the outputs of Decode form additive shares of z ∈ Z p with overwhelming probability. This concludes the proof of overwhelming correctness.

For security, the second part of the analysis is identical to the security analysis of the LPN-based protocol, and reduces to the LWE m k (Z q , χ) assumption with respect to Code. The first part of the analysis, however, differs in a crucial way: a standard application of the leftover hash lemma shows that H • r 0 is statistically close to a random vector. Therefore, the NIAIP actually enjoys statistical security for one of the two parties in the LWE setting. The rest of the game hops are identical -one must simply replace invocations of the dual LPN assumption by the statistical argument.

Like its LPN-based counterpart, this protocol leads to an NIAIP over an arbitrary prime order field (and can even be modified to give an inner product protocol over Z); furthermore, it enjoys overwhelming correctness. However, as we will see later, it is possible to upgrade the correctness of the LPN-based NIAIP to perfect correctness, and its security to security against malicious adversaries, at a cost sublinear in n; this means that, asymptotically, the LPN-based protocol can be made perfectly correct and maliciously secure at negligible cost. In contrast, making the LWE-based protocol secure against malicious adversaries is more challenging, and we leave it to future work.

From NIAIP to Secure Computation of Inner Product

The natural usecase for NIAIP is to securely compute inner products: two parties P 0 , P 1 publish encodings of their respective inputs u and v, locally compute shares of the inner product, and exchange their shares to reconstruct the output. An important technicality here is that the NIAIP indistinguishability notion does not directly imply security when revealing the share of P 0 to its opponent P 1 . When correctness is overwhelming (as with our LWE-based instantiation), this is not an issue: given the output u • v and the randomness of P 1 , the simulator can compute P 1 's share γ 1 , and simulate the missing share as u • v -γ 1 . Due to the overwhelming correctness, the simulation is indistinguishable from the honest protocol.

When using ε-NIAIP with non-negligible correctness error (as with our LPNbased instantiation), however, the correctness error translates to a security loss for the protocol: the simulation fails with probability 1 -ε. Yet, this does not directly imply an attack on the protocol. In fact, for our LPN-based instantiation, we can get perfect simulation by giving the the simulator the error term r 1 • r 0 . Concretely, this corresponds to allowing the adversary to learn a single sparse linear equation (given by r 1 ) in the LPN noise vector r 0 . In turn, this means that the security reduces to an appropriate LPN with leakage assumption. Such variants of LPN are relatively standard, and can in particular be reduced to the standard LPN assumption, albeit with some loss [START_REF] Boyle | Efficient two-round OT extension and silent non-interactive secure computation[END_REF][START_REF] Boyle | Efficient pseudorandom correlation generators from ring-LPN[END_REF].

In an multiparty setting, where P 0 wants to compute the inner product of u with many other vectors, the leakage can be accumulated across corrupted parties. This translates to a larger loss for the assumption, and the LPN parameters must be adjusted to compensate, as a function of the maximum number of corrupted parties. An alternative solution is to first remove the error instead, using the sublinear-communication preprocessing phase described in Section 4.

Choosing the Parameters and the Code

Our non-interactive inner-product communicates k + n + m bits (k + n for pk 0 and m for pk 1 ). The security of our protocol relies on a relatively unusual set of parameters: we need to assume dual LPN with dimension m -(k + n), m samples, noise rate τ with respect to the matrix H , as well as primal LPN with dimension k, m samples, noise rate τ with respect to the "right half" of H. We will discuss candidate choices for the underlying code afterwards. Regarding the parameters, we set m -(k + n) = k to ensure that both assumptions achieve the same dimension and number of samples, in order to balance security. This implies m = 2k + n. From there, the choice of k induces a tradeoff between the noise rate (which must be kept low as the error probability of the protocol is τ 2 • m) and the communication of the protocol (which grows with k): picking a very large k n increase communication but achieves asymptoptically a rate 1/2 (as m approaches 2k).

Concrete Parameters. For concrete instantiations, we consider a reasonable middle ground and set k = n (hence m = 3k), leading to codes of rate 1/3. This leads to a protocol with total communication 5n bits, only 2.5 times more than the communication of exchanging u 0 and u 1 in the clear. To estimate the concrete noise rate, we rely on the analysis of [START_REF] Boyle | Compressing vector OLE[END_REF] which provides various formulas to compute lower bounds on the bit complexity of the most standard attacks on LPN. With a rate 1/3 and using their formulas for the cost of ISD, Gaussian elimination, and low-weight parity-check attacks, we get the following (very close) approximation of the security level: choosing τ = λ/m provides λ-20 bits of security (independently of the vector length n). Hence, for example, setting λ = 100 gives 80 bits of security, and an error probability of λ 2 /m = 0.3% for vectors of length n = 2 20 (for smaller vectors, the error probability increases rapidly: e.g. around 10% for n = 2 15 ). Asymptotic Parameters. Asymptotically, letting m = 2k + n as before, the code rate is k/m for both codes. Let ε be an arbitrarily small constant, and set k = ε•n and τ = λ/m for a security parameter λ. The best known attack against LPN with code rate k/m = O(1) and noise rate λ/m run in time 2 O(λ) (where the O(•) hides a 1/ε factor). With these parameters, the protocol communicates 3k + 2n = (2 + 3ε)n bits, which is arbitrarily close to the optimal communication of an insecure NIAIP that simply reveals the inputs in the clear. Settling for subexponential security in λ can further reduce communication to 2n + o(n).

Choosing the Code. It remains to discuss how to choose an appropriate code to instantiate the NIAIP. While the code has no impact on communication, it represents a tradeoff between computation and security. For example, using a uniformly random code leads to a security reduction to the most standard flavor of LPN, but comes at a huge computational cost: the computation scales as O(n 2 ).

Some variants of LPN are conjectured to be secure with respect to linear time encodable codes, where the mapping x → H • x can be computed in linear time (by the transposition principle [START_REF] Bordewijk | Inter-reciprocity applied to electrical networks[END_REF][START_REF] Ishai | Cryptography with constant computational overhead[END_REF], this also implies that the mapping y → H • y can be computed in linear time). This is for example the case of primal LPN instantiated with a sparse matrix H, with a constant number of nonzero entry per row, which corresponds to the Alekhnovich assumption [START_REF] Alekhnovich | More on average case vs approximation complexity[END_REF]. Unfortunately, to our knowledge, for all known linear-time encodable code such that primal LPN is conjectured to hold with respect to H, the dual assumption with respect to H turns out to be insecure. For sparse codes, typically, this is equivalent to the well-known fact that LDPC codes admit an efficient decoding algorithm.

Fortunately, if we settle for quasi-linear time encodable codes, we can circumvent the issue. For example, quasi-cyclic codes can be encoded in time O(n•log n) using Fast Fourier Transform, and given a generator matrix H for a quasi-cyclic code, LPN is widely conjectured to hold both with respect to H right in its primal form, and with respect to H in its dual form. Quasi-cyclic codes have been used in numerous recent works [START_REF] Aguilar | Efficient encryption from random quasi-cyclic codes[END_REF][START_REF] Aguilar-Melchor | Efficient encryption from random quasi-cyclic codes[END_REF][START_REF] Boyle | Efficient two-round OT extension and silent non-interactive secure computation[END_REF] as well as in submissions to the NIST post-quantum competition [START_REF] Aguilar-Melchor | Efficient encryption from random quasi-cyclic codes[END_REF][START_REF] Aragon | Bike: bit flipping key encapsulation[END_REF][START_REF] Melchor | Hamming quasi-cyclic (hqc)[END_REF]. We note that, when using quasi-cyclic codes, one must account for the speedup given by the DOOM attack [START_REF] Sendrier | Decoding one out of many[END_REF], which gives a √ k speedup for the attacker. To compensate for this attack, we must therefore aim at λ + log 2 k "pre-DOOM" bits of security, which can be done by increasing the noise rate from (λ + 20)/m to (λ + 20 + log 2 k)/m with our concrete choice of parameters.

Open Problem: Finding a "Doubly Good" Linear Time Encodable Code

While the above provides a relatively satisfying solution, it remains an intriguing open question whether an appropriate choice of codes could possibly allow to achieve NIAIP with strictly linear computation. Following the recent analysis of LPN variants in [START_REF] Boyle | Correlated pseudorandom functions from variable-density LPN[END_REF][START_REF] Couteau | Silver: Silent VOLE and oblivious transfer from hardness of decoding structured LDPC codes[END_REF], a core necessary requirement to achieve this is to find a linear-time encodable code such that both the code and its dual have linear minimum distance (in the dimension). Indeed, there exists efficient attacks on LPN with codes whose dual have low minimum dimension [START_REF] Applebaum | Secure arithmetic computation with constant computational overhead[END_REF], and furthermore having linear minimum distance suffices to circumvent all known attacks against LPN [START_REF] Boyle | Correlated pseudorandom functions from variable-density LPN[END_REF][START_REF] Couteau | Silver: Silent VOLE and oblivious transfer from hardness of decoding structured LDPC codes[END_REF]. However, although the question appears to be very natural, lineartime encodable code where both the code and its dual are good codes (i.e. exhibit linear minimum distance) have never been exhibited in the literature, and we raise their existence as an interesting theoretical (but also possibly practical, in light of our construction) open question.

Removing Correctness Errors via Sublinear Preprocessing

In this section, we show how to convert the LPN-based ε-NIAIP from the previous section into a two-party secure computation protocol for inner product, without correctness error. While the protocol is not an NIAIP anymore, all additional interactions take place during an input-independent preprocessing phase. Furthermore, the amount of computation and communication during this preprocessing phase is sublinear in n (more precisely, it will be of the form poly(λ) • log n).

The ideal functionality F IP for secure computation of (shares of) an inner product over a field F is described on Figure 4 (setting ε = 1). The intuition behind the protocol of this section is natural: the correctness error in the protocol of Figure 1 is due to an additive term r 1 • r 0 in the shares locally decoded by the parties. Since the r b are sparse vectors, their inner product is zero with high probability ≈ 1 -λ 2 /m. To correct the error, the parties will distributively generate noise vectors (r 0 , r 1 ) together with additive shares of r 1 • r 0 . Crucially, this entire preprocessing requires communication and computation sublinear in the vector length n.

Picking the Right Noise Distribution

While the high level intuition is simple, the (asymptotic and concrete) efficiency of this approach turns out to be extremely sensitive to the noise distribution. In the previous section, we described the protocol using the standard Bernoulli noise distribution, since it allows for a reduction to the most common flavor of LPN. However, Bernoulli noise is a poor choice for allowing efficient preprocessing; using a regular noise distribution insteads allows for a considerably more efficient preprocessing, without harming security.

In a bit more details, setting τ = λ/m, a vector r b $ ← Ber τ (F) m can be written as the sum of ≈ λ unit vectors. Therefore, securely computing (shares of) the inner product between two such vectors reduces to securely computing λ 2 products of elements of F, and λ 2 secure equality tests between log m-size bitstrings. This is already sublinear in m = O(n), but the λ 2 overhead can incur a significant slowdown.

Instead, we sample r 0 and r 1 from the regular noise distribution: r 0 and r 1 are concatenations of λ random unit vectors. The corresponding variant of LPN, regular LPN, is not known to be any weaker than LPN in our regime of parameters. Let us introduce a few notations: we denote r b = (r

(1) b // • • • //r (λ) b ) for b = 0, 1, where the r (i)
b are unit vectors. Furthermore, we denote by j b,i and r b,i the position and the value of the nonzero entry in r (i) b . then, we have

r 1 • r 0 = λ i=1 (r (i) 1 ) • r (i) 0 = λ i=1 EQ(j 0,i , j 1,i ) • (r 0,i r 1,i ),
where EQ(x, y) returns 1 if x = y and 0 otherwise. Therefore, securely distributing shares of r 1 • r 0 reduces (mostly) to performing λ secure equality tests (for the EQ(j 0,i , j 1,i ) terms) between log(m/λ)-bit strings, and secure products over F (for the r 0,i r 1,i terms), which is quadratically reduced compared to the cost for Bernoulli noise.

The Protocol

We describe below a protocol for inner product, following our previous discussion. We use the following building blocks:

-F EQ is an ideal functionality parametrized by a domain [k] which, given two inputs (x, y) ∈ [k] 2 , outputs random shares b A , b B to Alice and Bob of EQ(x, y); -F OLE is an ideal functionality parametrized by a field F which, given two inputs (x, y) ∈ F 2 , outputs random shares z A , z B of x • y to Alice and Bob.

The protocol in the (F EQ , F OLE )-hybrid model is given on Figure 3.

Protocol Π sh IP -Setup. Let F be a prime order field. Sample H $ ← Code ⊥ (m, k + n, F) and output crs = H. -Preprocessing. Alice and Bob each sample random pairs (j0,i, r0,i) $ ← [m/λ] × F * and (j1,i, r1,i) $ ← [m/λ] × F * for i = 1 to λ.
Let r0, r1 denote the corresponding regular noise vectors.

• The parties call F EQ on inputs (j0,i, j1,i) ∈ [m/λ] 2 for i = 1 to λ. Let (b0,i, b1,i) denote Alice's and Bob's outputs. Let c0,i ← (-1) b 0,i and c1,i ← (-1) b 1,i for i = 1 to λ. Note that c0,i • c1,i = (-1) EQ(j 0,i ,j 1,i ) . • If F = F2, the parties call F OLE over F twice, on inputs (r0,i, r1,i) and (c0,i • r0,i, c1,i • r1,i), for i = 1 to λ. Let (α0,i, α1,i) and (β0,i, β1,i) denote their respective outputs in each instance. Note that α0,i + α1,i = r0,i • r1,i, and β0,i + β1,i = c0,ir0,i • c1,ir1,i = (-1) EQ(j 0,i ,j 1,i ) • r0,ir1,i.

• If F = F2, the parties compute z0 = λ i=1 (α0,i -β0,i)/2 and z1 = λ i=1 (α1,i -β1,i)/2. Note that z0 + z1 = λ i=1 r0,ir1,i • (1 - (-1) EQ(j 0,i ,j 1,i ) )/2 = λ i=1 r0,ir1,i • EQ(j0,i, j1,i) = r 0 • r1. • Else, if F = F2, the parties set (z0, z1) ← ( λ i=1 b0,i, λ i=1 b1,i). Note that z0 ⊕ z1 = λ i=1 EQ(j0,i, j1,i) = r 0 • r1 (since r0,i = r1,i = 1 for all i when F = F2).
-Online Phase. Let (u0, u1) be the inputs of Alice and Bob.

• Alice sends pk 0 ← (u0/ /0) -H • r0 and sets sk0 ← r0, while Bob samples

s $ ← F k , sends pk 1 ← H • (u1/ /s) + r1 and sets sk1 ← (u1/ /s). • Alice outputs x0 = pk 1 • sk0 -z0 and Bob outputs x1 = pk 0 • sk1 -z1.
Fig. 3. A non-interactive inner-product protocol with semi-honest security Π sh IP over F for vectors of length n Theorem 9. Let F be a prime order field and Code ⊥ be a nice code. Assume that the regular dual-LPN m m-(k+n),τ (F) assumption with respect to Code ⊥ , and the (primal) regular LPN m k,τ (F) assumption with respect to Code ⊥ right both hold. Then protocol on Figure 3 securely realizes the inner product functionality F IP (F, n) from Figure 4 in the (F EQ , F OLE )-hybrid model with semi-honest security and static corruption.

Functionality F IP (F, n, )
The functionality F IP is parametrized by a field F, and a vector length n. It interacts with two parties Alice and Bob, and an adversary A. On input (Input, u ∈ F n q ) from Alice and (Input, v ∈ F n q ) from Bob, the functionality F IP proceeds as follows:

-If both parties are honest, sample α, β ∈ Fq at random such that u

• v = α + β -If Alice is corrupted, wait for a message (Output, α ∈ Fq) from A and set β = u •v-α.
-If Bob is corrupted, wait for a message (Output, β ∈ Fq) from the adversary and set

α = u • v -β.
The functionality outputs α to Alice and β to Bob, and then halts. Proof. Case 0: both parties are honest. We first consider the case where no party is corrupted. Then, it follows by construction that z 0 + z 1 = r 0 • r 1 . Furthermore, we established previously in the proof of Theorem 7 that pk 1 • sk 0 + pk 0 • sk 1 = u 0 • u 1 + r 0 • r 1 (the online phase of the protocol is identical to an execution of Encode and Decode; only the distribution of r 0 , r 1 changes). It follows that the outputs of Alice and Bob form additive shares of u 0 • u 1 (with probability 1). Case 1: Alice is corrupted. Assume now that Alice is corrupted, with input u 0 . The simulator Sim activates F IP (F, n) on behalf of Alice in the ideal world by sending (Input, u 0 ). In the real world, it plays honestly the role of Bob in the preprocessing phase, emulates the answer of the functionalities F EQ and F OLE by returning either a random bit or a random element of F, and stores the queries of Alice to the functionalities and the output z 0 that she computes from the answers to her queries. Sim extracts the j 0,i from Alice's calls to F EQ and the r 0,i from her calls to F OLE , and reconstructs r 0 = sk 0 . Sim emulates Bob in the online phase by sending pk 1 $ ← F m , and sets

x 0 ← pk 1 • sk 0 -z 0 . Eventually, Sim sends (Output, x 0 ) to F IP (F, n).
It remains to argue why the simulation is indistinguishable from an honest execution of the protocol. Observe that the behavior of Sim is perfectly indistinguishable to that of Bob, except that it sends pk 1 $ ← F m instead of pk 1 ← H • (u 1 //s) + r 1 . Since the preprocessing phase does not leak any information about r 1 (the answers of F EQ and F OLE to Alice being uniformly random by definition) and Sim does not need r 1 to emulate these functionalities, the same sequence of games as in the proof of Theorem 7 shows that the advantage in distinguishing pk 1 from a uniformly random element in F m is negligible under the (regular, primal) LPN m k,λ/m assumption with respect to Code. Case 2: Bob is corrupted. Assume now that Bob is corrupted, with input u 1 . Sim plays in the preprocessing phase and interacts with F IP (F, n) in a symmetrical way, extracting the (j 1,i , r 1,i ) and reconstructing the vector r 1 and the value z 1 . Sim emulates Alice in the online phase by sending pk 0 $ ← F m . Upon receiving pk 1 from Bob, Sim extracts sk 1 = (u 1 //s) by solving pk 1 -r 1 = H • X and parsing the solution X as sk 1 = (u 1 //s) (which is guaranteed to be wellformed since Bob is semi honest). Eventally, Sim sets x 1 ← pk 0 • sk 1 -z 1 and sends (Output, x 1 ) to F IP (F, n).

As above, proving indistinguishability from an honest execution reduces to proving that pk 0 $ ← F m is indistinguishable from setting pk 0 ← (u 0 //0) -H • r 0 , which can be shown (since r 0 is perfectly hidden from Bob), using the same sequence of games as in the proof of Theorem 7, to follow from the (regular) dual-LPN m m-(k+n),λ/m assumption with respect to Code.

Variant:

Replacing λ Calls to F OLE by 2λ Calls to F OT Let F OT (F) be the oblivious transfer functionality over F: on input (s 0 , s 1 ) ∈ F 2 from the sender and a bit b from the receiver, it outputs s b to the receiver and nothing to the sender.

In the protocol of Figure 3, the parties with shares (b 0,i , b 1,i ) of EQ(j 0,i , j 1,i ) and values (r 0,i , r 1,i ) ∈ F 2 must compute additive shares of (b 0,i ⊕ b 1,i ) • r 0,i r 1,i , which they do using two calls to F OLE . We provide an alternative instantiation, which uses one call to F OLE , and two additional calls to F OT :

-Alice and Bob call F OLE on inputs (r 0,i , r 1,i ) ∈ F 2 and obtain additive shares (α 0,i , α 1,i ) of their product. -Alice and Bob perform two oblivious transfers in parallel. In the first OT, Alice plays the sender with inputs (b 0,i • α 0,i + r A , (1 -b 0,i ) • α 0,i + r A ) for a random mask r A , and Bob plays the receiver with input b 1,i . Concretely, Alice and Bob obtain this way shares of (b 0,i ⊕ b 1,i ) • α 0,i (where Alice's share is r A ). In the other direction, Bob plays the role of the sender, using a random mask r B , and Alice of the receiver with input b 0,i ; Alice and Bob obtain additive shares of (b 0,i ⊕ b 1,i ) • α 1,i . Summing their shares, Alice and Bob do indeed obtain shares of (b 0,i ⊕ b 1,i ) • r 0,i r 1,i .

Instantiating F EQ and F OLE

With the above variant, the preprocessing boils down to λ invocations of F EQ on log(m/λ)-bit strings, λ invocations of F OLE over F, and 2λ invocations of F OT on log |F|-bit strings. There exists numerous options to implement the F EQ functionality. In our range of parameters, we estimate that the most efficient solution is the protocol of [START_REF] Couteau | New protocols for secure equality test and comparison[END_REF]. For equality test over -bit strings, it requires + o( ) oblivious transfers of log -bit strings, and O(log * ) rounds of communication. Concretely, setting for example λ = 120 and m = 3n, for an inner product between string of length at most n = 2 20 , the protocol of [START_REF] Couteau | New protocols for secure equality test and comparison[END_REF] can be instantiated either with 15 OTs of 16-bit strings and 14 OTs of bits in two rounds, or with 15 OTs of 16-bit strings, 4 OTs of 4-bit strings, and 2 OTs of bits, in three rounds (and no additional communication beyond the OTs). For F OLE , the protocol of [START_REF] Gilboa | Two party RSA key generation[END_REF] requires log |F| OTs per OLE over F (while recent OLE protocols such as [START_REF] Boyle | Efficient pseudorandom correlation generators from ring-LPN[END_REF] are much more efficient, their efficiency improvement "kicks in" only for a large enough number of OLE). With these choices of protocol, the full preprocessing boils down to λ • (log(m/λ) + log |F| + 2) oblivious transfers.

Overall, setting m = O(n), the communication of the preprocessing phase boils down to O(λ • (log n + log |F|)) oblivious transfer of small strings (O(log n)bit or log |F|-bit strings), which leads to a logarithmic communication in the vector length n. For example, using the standard instantiation for short string oblivious transfer [START_REF] Kolesnikov | Improved OT extension for transferring short secrets[END_REF], computing the inner product between two strings of length 2 20 over a 32-bit field requires about 5•10 5 ≈ 0.5•n bits of communication, adding only a small overhead to the entire communication of the protocol. Using recent advances in silent OT extension [START_REF] Boyle | Efficient two-round OT extension and silent non-interactive secure computation[END_REF][START_REF] Couteau | Silver: Silent VOLE and oblivious transfer from hardness of decoding structured LDPC codes[END_REF], this overhead can be further reduced by a factor four.

Malicious Security

In this section, we enhance our protocol from Section 4 to withstand attacks from malicious adversaries.

Guaranteeing the Success of Extraction

In the malicious model, the parties may not follow the specifications of the protocol; in particular, they may not use their prescribed input. Therefore, to make the protocol from Figure 3 secure against malicious behavior, the simulator must have a mean to extract the input of the corrupted party. When Alice is corrupted, since Sim emulates the preprocessing and stores her noise vector r 0 , the effective input u 0 used by Alice can be extracted by computing pk 0 + H • r 0 , and parsing it as (u 0 //0). However, the success of this extraction is only guaranteed if we can ensure that pk 0 will always be well-formed (i.e. the "bottom half" of pk 0 is of the form M • r 0 for a sparse r 0 , where M is the bottom half of H ). Similarly, if Bob is corrupted, Sim extracts u 1 by solving the linear system H • X = pk 1 -r 1 to get (u 1 //s). However, this is an overdetermined system of equations which is not guaranteed to have a solution, and extraction will again succeed only if we can guarantee that pk 0 is well-formed (i.e., this system has a solution).

To guarantee the success of extraction, we let Alice and Bob add zeroknowledge proofs that their public keys pk 0 , pk 1 are well-formed. With simple manipulations, it is easy to show that in both cases, this reduces to proving that a vector v is of the form M • e, where M is a public compressive matrix, and e is a secret sparse noise vector -i.e., this reduces to proving knowledge of a preimage in an instance of the syndrome decoding problem for the code with parity-check matrix M , which is a well-studied problem [START_REF] Aguilar | A new zero-knowledge code based identification scheme with reduced communication[END_REF][START_REF] Cayrel | A zero-knowledge identification scheme based on the q-ary syndrome decoding problem[END_REF][START_REF] Stern | A new identification scheme based on syndrome decoding[END_REF]. Unfortunately, existing solutions are prohibitively expensive in our setting: they require O(κ•m) communication, where κ is a statistical security parameter (which stems from parallel repetitions of an underlying zero-knowledge proof with constant soundness error, e.g. 2/3 in Stern's scheme [START_REF] Stern | A new identification scheme based on syndrome decoding[END_REF]) and m is the code dimension. Since our protocol operates in the high-dimension, low-noise setting, this causes a huge blowup to the total communication and computation.

A New Almost-Zero-Knowledge Proof for Low-Noise Syndrome Decoding

As a contribution of independent interest, we therefore design a new zeroknowledge proof system for the syndrome decoding problem, which is especially suited for instances with large dimension and low noise. For a syndrome decoding instance of dimension and a noise rate of λ/ , our protocol boils down essentially to O(λ • log ) actively secure oblivious transfers and λ OLE. On the downside, unlike Stern's protocol, our zero-knowledge proof is not an identification scheme: it is private coin and cannot be made non-interactive using the Fiat-Shamir heuristic.

Our approach follows the intuition underlying a recent line of work [START_REF] Baum | Appenzeller to brie: Efficient zero-knowledge proofs for mixed-mode arithmetic and z2k[END_REF][START_REF] Baum | Mac'n'cheese: Zero-knowledge proofs for boolean and arithmetic circuits with nested disjunctions[END_REF][START_REF] Dittmer | Line-point zero knowledge and its applications[END_REF][START_REF] Yang | Quicksilver: Efficient and affordable zero-knowledge proofs for circuits and polynomials over any field[END_REF] on efficient zero-knowledge proofs from pseudorandom correlation generators [START_REF] Boyle | Compressing vector OLE[END_REF][START_REF] Boyle | Efficient two-round OT extension and silent non-interactive secure computation[END_REF][START_REF] Boyle | Efficient pseudorandom correlation generators: Silent OT extension and more[END_REF]. However, our goal is fundamentally different, since these works target linear communication zero-knowledge proofs for general (arithmetic) circuits; on the other hand, we construct a sublinear communication zero-knowledge proof for a specific problem.

Intuition. A recent line of work initiated in [START_REF] Boyle | Compressing vector OLE[END_REF] has developed pseudorandom correlation generators (PCG) for the vector-OLE (VOLE) correlation. At a high level, a PCG for a VOLE correlation allows to distributively generate additive shares of ∆ • v, where ∆ is a (chosen) element of F known to one of the parties, and v is a (long) pseudorandom vector over F, known to the other party. We do not directly build on PCG, but observe that the main component in their construction is a protocol that relies on puncturable pseudorandom functions (PPRF) to distributively generate, with low communication, additive shares of ∆ • e for a sparse, regular noise vector e.

We rely on this PPRF-based protocol to authenticate the regular noise vector e (i.e., the witness of the prover) with low communication overhead, using an information-theoretic MAC ∆ known to the verifier. Due to the regular structure of e, this boils down to distributively generating and locally concatenating shares of ∆ • e i for i = 1 to λ, where the e i are unit vectors (let j i be the index of their nonzero entry, and e i be the corresponding value). Such a protocol is called a single point vector OLE. We briefly recall how such shares are generated with sublinear communication:

-The verifier samples ∆, and a PRF key K for a PRF {PRF K : [ /λ] → F} K .

-The parties execute an interactive protocol to securely generate K{j i } (the key K punctured at j i ). Using variants of the Doerner-shelat protocol [START_REF] Doerner | Scaling ORAM for secure computation[END_REF] on top of the GGM puncturable PRF [START_REF] Goldreich | How to construct random functions (extended abstract)[END_REF], this requires O(log ) invocations of an oblivious transfer protocol. -The prover obliviously receive the value PRF K (j i ) + ∆ • e i , using a single OLE over F. -In the malicious setting, when several instances are executed, additional consistency checks are required to guarantee that ∆ remains the same accross all executions. An efficient protocol for this task was given in [START_REF] Weng | Wolverine: fast, scalable, and communication-efficient zero-knowledge proofs for boolean and arithmetic circuits[END_REF], with minimal overhead compared to the semi-honest protocol.

Let (q 0 , q 1 ) denote the additive shares of ∆ • e generated using the above protocol. To check that v is indeed of the form M • e, the verifier sends a random vector ρ to the prover, who replies with the value ver 0 = -ρ • (M • q 0 ) ∈ F. Then, the verifier sets ver 1 ← ρ • (M • q 1 -∆ • v) and check that ver 0 = ver 1 .

Observe that ver 1 -ver

0 = ρ •(M •q 1 -∆•v+M •q 0 ) = ρ •(M •(∆•e)-∆•v) = 0 if M •e = v.
Soundness will rely on the Schwarz-Zippel lemma to show that when M • e = v, causing ver 0 = ver 1 is as hard as guessing ∆, which can happen only with probability 1/|F| since ∆ is perfectly hidden from the prover. This readily suffices when F is exponentially large. For smaller fields, we simply sample ∆ from an appropriate extension field F of F such that |F | ≥ 2 κ for some statistical security parameter κ; the rest of the protocol is identical, except that the parties must use a PRF from [ /λ] to F , and execute the OLE's over F .

Zero-knowledge versus almost-zero-knowledge. The above blueprint actually leads to a true zero-knowledge proof system with sublinear communication, when instantiated with a maliciously secure sublinear protocol for single point vector OLE. While it is possible to construct such protocols, recent works [START_REF] Boyle | Efficient two-round OT extension and silent non-interactive secure computation[END_REF][START_REF] Weng | Wolverine: fast, scalable, and communication-efficient zero-knowledge proofs for boolean and arithmetic circuits[END_REF] have observed that one can achieve a much greater efficiency by slightly relaxing the single point VOLE functionality. In this relaxation, the verifier is allowed to learn roughly one bit of leakage about the noise vector e. When instantiating our construction with the protocol of [START_REF] Weng | Wolverine: fast, scalable, and communication-efficient zero-knowledge proofs for boolean and arithmetic circuits[END_REF] (the state-of-the-art protocol of this line of work), the protocol we get is therefore not truly zero-knowledge. Nevertheless, it still suffices to construct a maliciously secure inner product protocol, which is our end goal, at the cost of relying on the LPN with static leakage assumption (first put forth in [START_REF] Boyle | Efficient two-round OT extension and silent non-interactive secure computation[END_REF]), which states (informally) that LPN remains secure given one bit of leakage about the noise vector.

The zero-knowledge proof. Since, for better efficiency, we do not achieve fullfledged zero-knowledge but only a relaxed version which suffices in our specific context, we do not provide here an isolated description of the zero-knowledge proof, and directly integrate it into our maliciously secure protocol. However, for the sake of completeness, we provide a description of the proof system in isolation (with and without the relaxation) in the full version of this paper.

Maliciously Secure Inner Product from LPN with Static Leakage

The full protocol, integrating the procedure for checking that pk 0 and pk 1 are well-formed, is described on Figure 6, in the F mal pre -hybrid model. These checks require the parties to have access to authenticated versions of the noise vectors r 0 , r 1 ; this authentication procedure is executed in a preprocessing phase. The ideal functionality F mal pre describing the preprocessing phase is represented on Figure 5. It follows closely the single-point vector-OLE functionality from [START_REF] Weng | Wolverine: fast, scalable, and communication-efficient zero-knowledge proofs for boolean and arithmetic circuits[END_REF], but enhances it to also distribute the inner product between pairs of singlepoint VOLEs. Similarly, our instantiation of this functionality will build upon the protocol of [START_REF] Weng | Wolverine: fast, scalable, and communication-efficient zero-knowledge proofs for boolean and arithmetic circuits[END_REF].

Functionality F mal pre (F, F , n)
The functionality is parametrized by a field F and an extension field F of F, as well as a vector length n, which is assumed to be a power of 2.

Security Analysis

We first recall the LPN with static leakage assumption from [START_REF] Boyle | Efficient two-round OT extension and silent non-interactive secure computation[END_REF][START_REF] Weng | Wolverine: fast, scalable, and communication-efficient zero-knowledge proofs for boolean and arithmetic circuits[END_REF] We note that LPN with static leakage reduces to standard LPN assumption [START_REF] Boyle | Efficient two-round OT extension and silent non-interactive secure computation[END_REF], but the reduction is not tight. Intuitively, the assumption allows the adversary to obtain one bit of leakage on e on average, which should reduce bit security by one bit at most. Since the reduction to LPN induces a much larger loss, we define this assumption as an independent assumption and use it with the same concrete parameter as for LPN.

On the use of a PRF. The checks in the online phase require the parties to exchange long random strings ρ 0 , ρ 1 . To reduce communication, this is done by exchanging short keys, which the parties locally stretch into long pseudorandom strings by evaluating a PRF on a priori fixed inputs: ρ b ← (PRF K b (0), • • • , PRF K b (k/λ)), assuming that PRF has λ-bit outputs. It is a wellknown result that any statistical test that succeeds with high probability for a random string, such as our application of the Schwarz-Zippel lemma, must succeed with comparable probability when evaluating a PRF on inputs fixed before the key was sampled, since any noticeable difference can be turned into an efficient distinguisher against the PRF. Theorem 11. Let Code ⊥ be a nice code. Assume that the dual-LPN m m-(k+n),τ (F) assumption with static leakage with respect to Code ⊥ , and the (primal) LPN m k,τ (F) assumption with static leakage with respect to Code ⊥ right both hold. Then the protocol π mal IP securely computes the inner product functionality F IP with security against malicious adversaries in the F mal pre -hybrid model. Due to lack of space, we defer the proof of Theorem 11 to the full version of this paper.

Efficiency. Compared to the semi-honest protocol, the online phase of Figure 6 adds two rounds of interaction to the protocol, as well as 2λ bits (for exchanging the seeds) and two elements of F (hence, the overall increase in communication is essentially negligible). Regarding computation, the cost of the check that pk 0 is well-formed is dominated by a multiplication by the matrix M • F k×m , which (setting k = n for concreteness) is about twice faster than a multiplication by H. The cost of checking that pk 1 is well-formed is dominated by a multiplication by the parity-check matrix G of H for Bob (resp. two multiplications by G for Alice), which is about the same cost as a multiplication by H. Therefore, the computational cost of the maliciously secure protocol is about twice that of the semi-honest protocol.

Implementing the malicious preprocessing functionality. Due to lack of space, we defer the discussion on how to implement the malicious preprocessing functionality to the full version of this paper.

Definition 3 (

 3 Dual Learning Parity with Noise). Fix a field F = F(λ), dimension k = k(λ), number of samples m = m(λ), and noise rate τ = τ (λ).

  ) and outputs the matrix H right ∈ F m×k which contains the last k columns of H. Furthermore, we say that Code ⊥ is a nice code if given H right , there is an efficient algorithm to sample a random matrixH from Code ⊥ (m, k + n, F) -Setup(1 λ ) : sample H $ ← Code ⊥ (m, k + n,F) and output crs = H. -Encode(crs, b, u) : parse crs as H and sample r b $ ← Ber m τ (F). If b = 0, output pk 0 ← (u/ /0) -H • r0 and sk0 ← r0. If b = 1, sample s $ ← F k , and output pk 1 ← H • (u/ /s) + r1 and sk1 ← (u/ /s). -Decode(crs, pk, sk ) : output pk • sk .

Fig. 1 .

 1 Fig. 1. A non-interactive approximate inner-product over F for vectors of length n

where r 1 $←

 1 is a random Bernoulli noise and s is a random vector from F k .-Game G1 1,0 : the challenger first receives a challenge, denoted (H right , c), for the LPN m k,τ assumption with respect to Code ⊥ right , where c is H right • s + e for some random vector s and some noise vector e. The challenger samples H as H Code ⊥ | H right (m, k + n, F) (which is possible by definition since Code ⊥ is a nice code). Let H left be such that H = H left ||H right . Upon receiving u ∈ F n from A(H), the challenger returns pk 1 ← c. By construction of c, since H • (0 n //s) = H right • s, this game is perfectly indistinguishable from the previous one.

-

  Setup(1 λ ) : sample H $ ← Code ⊥ (m, k + n, Zq) and output crs = H. -Encode(crs, b, u) : parse crs as H and sample r b $ ← χ m . If b = 0, output pk 0 ← (q/p) • (u/ /0) -H • r0 and sk0 ← r0. If b = 1, sample s $ ← Z k q , and output pk 1 ← H • (u/ /s) + r1 and sk1 ← (u/ /s).-Decode(crs, pk, sk ) : output (p/q) • pk • sk mod p.

Fig. 2 .

 2 Fig. 2. An LWE-based non-interactive inner-product over Fp for vectors of length n

Fig. 4 .

 4 Fig. 4. Ideal functionality F IP for inner product between vectors over F n .

Initialize.

  Upon receiving Input from Alice and Bob, sample ∆, ∆ $ ← F if both Alice and Bob are honest. Otherwise, if Bob is corrupted, receive ∆ from the adversary and sample ∆ $ ← F ; if Alice is corrupted, receive ∆ from the adversary and sample ∆ $ ← F . Output ∆ to Alice, ∆ to Bob, and ignore all subsequent Input commands. Extend. Upon receiving (Extend, x) from Alice and (Extend, x ) from Bob, where (x, x ) are unit vectors over F n , do: 1. If Bob is honest, sample y $ ← (F ) n . Otherwise, receive y ∈ (F ) n from the adversary. Similarly, if Alice is honest, sample y $ ← (F ) n . Otherwise, receive y ∈ (F ) n from the adversary. 2. If Alice is honest, compute z ← y + ∆ • x. Otherwise, receive z from the adversary and recompute y ← z -∆ • x. Similarly, if Bob is honest, compute z ← y + ∆ • x . Otherwise, receive z from the adversary and recompute y ← z -∆ • x . 3. If party P ∈ {A, B}, receive a set I ⊆ [1, n] from the adversary. Let j ∈ [1, n] be the index of the nonzero entry of x (if P = B) or x (if P = A). If j ∈ I, send success to P and continue. Otherwise, send abort to both parties and abort. 4. If both parties are honest, set (w0, w1) to be random shares over F of x • x . Otherwise, if Alice (resp. Bob) is corrupted, receive w0 (resp. w1) from the adversary, and set w1 ← x • x -w0 (resp. w0 ← x • x -w1). 5. Send (z, y , w0) to Alice and (y, z , w1) to Bob.Global-key query. If party P ∈ {A, B} is corrupted, receive (guess, ∆) from the adversary with ∆ ∈ F . If ∆ = ∆ and P = A, or if ∆ = ∆ and P = B, send success to P and ignore any subsequent global-key query from P . Otherwise, send abort to both parties and abort.

Fig. 5 .

 5 Fig. 5. Ideal Functionality for the preprocessing step of maliciously secure inner product, parametrized by a field F with extension field F

: 2 ≤

 2 Definition 10 (Regular LPN with static leakage). Fix a field F = F(λ), dimension k = k(λ), number of samples m = m(λ), and noise rate τ = τ (λ). The regular LPN m k,τ assumption with static leakage with respect to Code holds if for every PPT algorithm A, it holds thatPr[LPN-Succ A (λ) = 1] -1 negl(λ),where the experiment LPN-Succ A (λ) is defined as follows:1. Sample A $ ← Code(m, k, F), s $ ← F k , e $ ← RN τ,m(F), and let (α 1 , • • • , α τ m ) ∈ [1/τ ] τ m denote the location of the nonzero entries of e. Send A to A. 2. A outputs τ m subsets (I 1 , • • • , I τ m ) of [1/τ ]. If α i ∈ I i for every i ≤ τ m, output success to A; otherwise, abort the experiment and set the output to 0. 3. If the experiment did not abort, pick a random bit b $ ← {0, 1}. If b = 0, set u ← A • s + e; else, set u $ ← F m . Send u to A. Output 1 if A answers with b, and 0 otherwise.

All known LPN-friendly codes satisfy this property.

Protocol Π mal IP Let F be the smallest extension field of F (possibly equal to F) such that |F | ≥ 2 κ , for a statistical security parameter κ. Fix parameters (k, m) as in the semi-honest protocol. Sample H $ ← Code ⊥ (m, k + n, F) and output crs = H ∈ F m×(k+n) .

Preprocessing. Alice and Bob send Input to F mal pre (F, F , m), and receive respective outputs (∆, ∆ ) ∈ F × F .

-Alice and Bob each sample random pairs (j0,i, r0,i)

for b = 0, 1 denote the corresponding regular noise vectors.

-Alice and Bob call the Extend command of F mal pre (F, F , m/λ) λ times, on respective inputs (r

1 ) for i = 1 to λ. Let (zi, y i , w0,i) and (z i , yi, w1,i) denote their outputs in the i-th instance respectively. Alice constructs q0 by concatenating all the zi, and q 0 by concatenating all the y i . Similarly, Bob constructs -q1 by concatenating all the z i , and -q 1 by concatenating all the yi. Eventually, Alice sets z0 ← i w0,i and Bob sets z1 ← i w1,i. Note that by definition of F mal pre (F, F , m), it holds that (q0, q1) form additive shares of ∆ • r1, (q 0 , q 1 ) form additive shares of ∆ • r0, and (z0, z1) form additive shares of r 0 r1.

Online Phase. Let (u0, u1) be the inputs of Alice and Bob.

-Alice sends pk 0 ← (u0/ /0) -H • r0 and sets sk0 ← r0, while Bob samples s $ ← F k , sends pk 1 ← H • (u1/ /s) + r1 and sets sk1 ← (u1/ /s). The following checks are performed in parallel: -Checking that pk 0 is well-formed:

• Let M ∈ F k×m be the last k rows of H . Note that the statement "there exists a vector u0 and a λ-regular vector r0 such that pk 0 = (u0/ /0) -H • r0" is equivalent to "there exists a λ-regular vector r0 such that the last k coordinates of pk 0 are equal to M • r0". Bob sends K0 $ ← {0, 1} λ and both parties expand

-Checking that pk 1 is well-formed:

• Let G ∈ F (m-k-n)×m be a parity-check matrix of H. Note that the statement "there exists a vector u1/ /s and a λ-regular vector r0 such that pk 1 = H • (u1/ /s) + r1" is equivalent to "there exists a λ-regular vector r1 such that

). -Alice outputs x0 = pk 1 • sk0 -z0 and Bob outputs x1 = pk 0 • sk1 -z1.