Elette Boyle
email: eboyle@alum.mit.edu

Geoffroy Couteau
email: couteau@irif.fr

Niv Gilboa
email: niv.gilboa@gmail.com

Yuval Ishai
email: yuvali@cs.technion.ac.il

Lisa Kohl
email: lisa.kohl@cwi.nl

Peter Scholl
email: peter.scholl@cs.au.dk

Efficient Pseudorandom Correlation Generators from Ring-LPN *

Secure multiparty computation can often utilize a trusted source of correlated randomness to achieve better efficiency. A recent line of work, initiated by Boyle et al. (CCS 2018, Crypto 2019), showed how useful forms of correlated randomness can be generated using a cheap, one-time interaction, followed by only "silent" local computation. This is achieved via a pseudorandom correlation generator (PCG), a deterministic function that stretches short correlated seeds into long instances of a target correlation. Previous works constructed concretely efficient PCGs for simple but useful correlations, including random oblivious transfer and vector-OLE, together with efficient protocols to distribute the PCG seed generation. Most of these constructions were based on variants of the Learning Parity with Noise (LPN) assumption. PCGs for other useful correlations had poor asymptotic and concrete efficiency.

In this work, we design a new class of efficient PCGs based on different flavors of the ring-LPN assumption. Our new PCGs can generate OLE correlations, authenticated multiplication triples, matrix product correlations, and other types of useful correlations over large fields. These PCGs are more efficient by orders of magnitude than the previous constructions and can be used to improve the preprocessing phase of many existing MPC protocols.

Introduction

Correlated secret randomness is a commonly used resource for secure multi-party computation (MPC) protocols. Indeed, simple kinds of correlations enable lightweight MPC protocols even when there is no honest majority. For instance, an oblivious transfer (OT) correlation supports MPC for Boolean circuits [GMW87,Kil88,IPS08,NNOB12], while oblivious linear-function evaluation1 (OLE), an arithmetic variant of OT, supports MPC for arithmetic circuits [START_REF] Naor | Oblivious transfer and polynomial evaluation[END_REF][START_REF] Ishai | Secure arithmetic computation with no honest majority[END_REF]. Other useful types of correlations include multiplication triples [START_REF] Beaver | Efficient multiparty protocols using circuit randomization[END_REF] and truth-table correlations [IKM + 13,DNNR17,Cou19]. Finally, authenticated multiplication triples serve as a powerful resource for achieving security against malicious parties [START_REF] Bendlin | Semihomomorphic encryption and multiparty computation[END_REF][START_REF] Damgård | Multiparty computation from somewhat homomorphic encryption[END_REF].

A common paradigm in modern MPC protocols is to utilize the above kinds of correlations in the following way. In a preprocessing phase, before the inputs are known, the parties use an offline protocol to generate many instances of the correlation. These instances are then consumed by an online protocol to securely compute a function of the secret inputs. This approach is appealing because of the high efficiency of the online protocol. Indeed, with the above simple correlations, the online communication and computation costs are comparable to the size of the circuit being evaluated. The price one pays for the fast online protocol is a much slower and higher-bandwidth offline protocol. Even simple types of correlated randomness are expensive to generate in a secure way. This high cost becomes even higher when aiming for security against malicious parties.

Recently, a promising approach for instantiating the preprocessing phase of MPC protocols was suggested in [BCGI18, BCG + 19b], relying on a new primitive called a pseudorandom correlation generator (PCG). Consider a target two-party correlation C, typically consisting of many independent instances of a simple correlation as above. A PCG for C consists of two algorithms: Gen(1 λ ), which given a security parameter λ generates a pair of short, correlated seeds (k 0 , k 1 ), and Expand(k σ ), which deterministically stretches a seed k σ to a long output R σ . The intuitive security requirement is that the joint outputs (R 0 , R 1 ) of the above process cannot be distinguished from C not only by an outsider, but also by an insider who learns one of the two seeds. PCGs naturally lead to protocols with an appealing silent preprocessing feature, by breaking the offline phase into two parts:

1. Setup. The parties run a secure protocol to distribute the seed generation of Gen. Since

Gen has low computational cost and short outputs, this protocol only involves a small amount of communication, much smaller than the output of C. Each party stores its own short seed k σ for later use.

2. Silent expansion. Shortly before the online phase, the parties use Expand to generate long pseudorandom correlated strings (R 0 , R 1 ) to be consumed by the online protocol. This part is referred to as silent, since it involves no communication.

Beyond the potential improvement in the total offline communication and computation, this blueprint has two additional advantages. First, it can substantially reduce the storage cost of correlated randomness by enabling efficient compression. Indeed, the parties can afford to generate and store many correlated seeds, possibly with different sets of parties, and expand them just before they are needed. Second, the cost of protecting the offline protocol against malicious parties is "amortized away," since it is only the small setup part that needs to be protected. A malicious execution of Expand is harmless.

The work of Boyle et al. [BCG + 19b] constructed efficient PCGs for several kinds of useful correlations based on different assumptions that include variants of Learning Parity with Noise (LPN) [START_REF] Blum | Cryptographic primitives based on hard learning problems[END_REF] and Learning With Errors (LWE) [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF]. While the LPN-based PCG for OT from [BCG + 19b] has very good concrete efficiency, making it a practically appealing approach for generating many OTs [BCG + 19a], this is not the case for other useful correlations such as OLE or authenticated multiplication triples. For these correlations, two different constructions were proposed in [BCG + 19a]. Both are "practically feasible" but quite inefficient. In the first construction, based on homomorphic secret sharing from ring-LWE [BGI16a, BGI17, BCG + 17, BKS19], the seed expansion can be at most quadratic due to the use of a pseudorandom generator with algebraic degree 2. In concrete terms, the seeds are several GBs long and can only be expanded by around 6x, giving far too much overhead for most applications. Their second construction is based directly on LPN, and has computational cost of at least Ω(N2 ) for output length N , which is impractical for large N .

Our contributions

In this work, we present efficient new PCG constructions for several widely used correlations for which previous techniques had poor concrete efficiency.

Silent OLE and multiplication triple generation. Our main construction gives the first concretely efficient PCG for OLE over big finite fields F. This PCG is based on a variant of the ring-LPN assumption over F, makes a black-box use of F, and has poly(λ) • log N seed size and poly(λ) • Õ(N ) computational cost for expanding the seeds into N instances of OLE. This PCG gives both an asymptotic and concrete improvement over the LPN-based construction from [BCG + 19b].

We also show how to modify our PCG for OLE to produce multiplication triples and authenticated triples, used in maliciously secure MPC protocols like SPDZ [START_REF] Damgård | Multiparty computation from somewhat homomorphic encryption[END_REF]. This incurs an extra overhead of only around a factor of two in seed size, seed generation, and silent expansion time. Finally, we extend the main construction to other types of useful correlations, including matrix products and circuit-dependent correlations.

Technically, one of our main innovations here is showing how to avoid the Ω(N 2 ) blowup from the previous LPN-based PCG for OLE from [BCG + 19b]. Our method of doing this requires switching from unstructured LPN to ring-LPN over a certain kind of polynomial rings. This is analogous to early fully homomorphic encryption schemes, where switching from a construction based on LWE [START_REF] Brakerski | Efficient fully homomorphic encryption from (standard) LWE[END_REF] to one based on ring-LWE [START_REF] Brakerski | Fully homomorphic encryption from ring-LWE and security for key dependent messages[END_REF] reduced the ciphertext expansion in multiplication from quadratic to linear. A key difference between LWE-based constructions and LPN-based constructions over a big field F is the noise distribution: Gaussian in the former and low Hamming weight noise in the latter. With LPN-style noise distribution more care is needed, and some natural PCG candidates based on Reed-Solomon codes can indeed be broken.

Concrete efficiency. Our PCGs have attractive concrete efficiency features. To give a couple of data points, in the case of OLE the parties can store a pair of seeds of size 1.25MB each, and expand them on demand to produce over a million OLEs (of size 32MB, 26x larger than the seeds) in Z q , where q is the product of two 62-bit primes, 2 with 128-bit security. When running on a single core of a modern laptop, we estimate this takes under 10 seconds, resulting in a throughput of over 100 thousand OLEs per second. To produce authenticated triples instead of OLE, the expansion cost roughly doubles, giving 50 thousand triples per second, while the seed size increases to 2.6MB. For comparison, estimates from [BCG + 19b] for their PCG for producing authenticated triples gave a throughput of up to 7 thousand per second, but this was only possible when generating an enormous batch of 17GB worth of triples, with 3GB seeds. See below for comparison with non-silent correlation generation techniques.

Efficient setup protocols. Recall that to avoid a trusted setup, one typically needs a setup protocol to securely distribute the PCG seed generation. We present concretely efficient setup protocols for OLE and authenticated triples, with both semi-honest and malicious security. The protocols make black-box use of lightweight cryptographic primitives, as well as of generic MPC protocols for performing binary and arithmetic computations on secret-shared values.

In practice, our PCGs and setup protocols can be used in a bootstrapping mode, where a portion of the PCG outputs are reserved to be used as correlated randomness for the setup procedure of the next PCG seeds. This means that the vast majority of the setup cost is amortized away over multiple instances. Concretely, we estimate that when bootstrapped in this way, the setup phase for a PCG of one million authenticated triples requires only around 4.2MB of communication per party, to produce 32MB worth of triples. The initial setup protocol for the first PCG (before bootstrapping can take place) requires around 25000 authenticated triples, plus some additional correlated randomness (OT and VOLE). This should be feasible to produce in under a minute (although with high communication cost) using standard protocols such as MASCOT [START_REF] Keller | MASCOT: Faster malicious arithmetic secure computation with oblivious transfer[END_REF] or Overdrive [START_REF] Keller | Overdrive: Making SPDZ great again[END_REF], and previous PCG protocols for OT and VOLE with malicious security [BCG + 19a].

Compared with non-silent secure correlation generation protocols, we expect the overall computational cost of our approach to be comparable with state-of-the-art protocols based on homomorphic encryption [KPR18, JVC18, HIMV19], but with much lower communication costs. For instance, in the case of authenticated multiplication triples, the Overdrive protocol [START_REF] Keller | Overdrive: Making SPDZ great again[END_REF] can produce around 30 thousand triples per second with malicious security. This is similar to our PCG expansion phase (modulo different hardware, environment, and so on), with the significant difference that Overdrive requires almost 2GB of communication to produce the triples. In comparison, our amortized 4.2MB communication complexity is over two orders of magnitude smaller, with the additional benefit that our short correlated seeds can be easily stored for on-demand silent expansion.

Extension to other correlations and multiple parties. Beyond multiplication triples, it can be useful to have more general "degree-two" correlations, such as inner-product triples, matrix-multiplication triples, or circuit-dependent multiplication triples [START_REF] Couteau | A note on the communication complexity of multiparty computation in the correlated randomness model[END_REF][START_REF] Ben-Efraim | Turbospeedz: Double your online SPDZ! Improving SPDZ using function dependent preprocessing[END_REF][START_REF] Boyle | Secure computation with preprocessing via function secret sharing[END_REF]. We use our PCG for OLE to obtain PCGs for these kinds of correlations, by exploiting a special "programmability" feature that enables reusing the same PCG output in multiple instances [BCG + 19b]. This gives us a way to produce many independent instances of any degreetwo correlation (a vast generalization of OLE and multiplication triples), with seed size that grows sublinearly with the total number of instances. Useful special cases include the types of correlations mentioned above. This construction has a bigger overhead than our PCG for OLE, and in practice seems mainly suited for small correlations such as low-dimensional matrix products. However, these can still be useful in larger computations which involve a lot of linear algebra or other repeated sub-computations.

We can also use same programmability feature of our 2-party PCGs to extend them to the multi-party setting. This yields practical multi-party PCGs for multiplication triples that enable an online passively-secure MPC protocol for arithmetic circuits whose cost scales linearly (rather than quadratically) with the number of parties. This transformation to the multi-party case, which originates from [BCG + 19b], does not scale well to correlations with degree higher than 2. As a result, we do not get a multi-party PCG for authenticated triples (a degree-three correlation) with the same level of efficiency.

Security of ring-LPN. Our constructions rely on variants of the ring-LPN assumption over non-binary fields. Binary ring-LPN [HKL + 12] is a fairly standard assumption that withstood a significant amount of cryptanalysis. However, since we also use relatively unexplored variants over different rings, we give a thorough survey of known attacks, and analyze the best strategies that apply to our setting. We find that there are only one or two additional attack possibilities from the additional structure we introduce, and these are easily countered with a small increase in the number of errors.

More precisely, settling for a PCG that generates a single OLE instance over a large ring of degree-N polynomials, our construction can be based on a conservative variant of ring-LPN where the modulus is irreducible. A big ring-OLE correlation can then be converted into N independent instances of standard OLE by communicating O(N ) field elements. For generating silent OLE over F p , we instead rely on a variant of ring-LPN where the modulus splits completely into N linear factors. In practice, this requires using larger parameters and increases the cost of our protocols by around a factor of two, compared with irreducible ring-LPN.

Changes Since Publication at CRYPTO 2020

This article has undergone a major revision since its original publication. As well as various minor improvements and clarifications, there are the following major changes.

• The maliciously secure DPF setup protocol in Section 5.3 has changed, since the original security proof was flawed, as pointed out by Damiano Abram. The protocol now uses a different consistency check to fix the issue.

• The DPF setup protocol has also been generalized to work over any (sufficiently large) finite field, it no longer uses the random oracle model, and the F c-SUV functionality it realizes no longer allows the adversary to guess β.

• The cost analysis has been updated to reflect the new protocol. The resulting efficiency estimates have not changed significantly.

• Some of the security analysis of the ring-LPN assumption has been revised due to minor bugs. We point out that much of this analysis is based on cost estimates for attacks that were recently shown in [START_REF] Liu | The hardness of LPN over any integer ring and field for PCG applications[END_REF] to be overly conservative. We did not adjust our parameters to reflect [START_REF] Liu | The hardness of LPN over any integer ring and field for PCG applications[END_REF], however, according to their cost models (combined with our optimizations for exploiting the structure of cyclotomic ring-LPN), our parameter sets for 80-bit security have between 92-112 bits of security, while our 128-bit parameter sets have 133-171 bits of security. It therefore seems that our parameters have a comfortable security margin.

Technical Overview

Construction from [BCG + 19b]. Before describing our PCG for OLE, it is instructive to recall the PCG for general degree-two correlations by Boyle et al. [BCG + 19b], based on LPN. The goal is to build a PCG for the correlation which gives each party a random vector x i , together with an additive secret share of the tensor product x 0 ⊗ x 1 . They used the dual form of LPN over a ring Z p , which states that the distribution

H, H • e H $ ← Z m×n p , e $ ← Z n p s.t. wt( e) = t
is computationally indistinguishable from uniform, where e is a sparse random vector with only t non-zero coordinates, for some t n, and m < n. The idea of the construction is that the setup algorithm gives each party a random sparse e 0 or e 1 , and computes the tensor product e 0 ⊗ e 1 , which has at most t 2 non-zero coordinates. This product is then distributed to the parties via function secret sharing (FSS), by generating a pair of FSS keys for the function that outputs each entry of the product on its respective inputs from 1 to n 2 . This function can be written as a sum of t 2 point functions, allowing practical FSS schemes based on distributed point functions [START_REF] Gilboa | Distributed point functions and their applications[END_REF][START_REF] Boyle | Function secret sharing[END_REF][START_REF] Boyle | Function secret sharing: Improvements and extensions[END_REF]. Note that unlike the case of PCGs for OT or Vector-OLE [BCG + 19a, SGRR19], here we cannot replace FSS by the simpler punctured PRF primitive.

Given shares of e 0 ⊗ e 1 and either e 0 or e 1 , the parties expand these using LPN, computing:

x 0 = H • e 0 , x 1 = H • e 1 , z = (H • e 0 ) ⊗ (H • e 1 ) = (H ⊗ H) • ( e 0 ⊗ e 1 )
where x i is computed by party P i , while z is computed in secret-shared form, using the shares of e 0 ⊗ e 1 and the formula on the right-hand side.

Notice that both x 0 and x 1 are pseudorandom under LPN, which gives the desired correlation.

Optimizations and additional applications. Boyle et al. state the computational complexity of the above as O(n 4 ) operations, due to the tensor product of H with itself. We observe that the value of (H • e 0 )⊗(H • e 1 ) can be read directly from H •( e 0 • e 1 )•H , which requires much less computation and can be made even more efficient if H is a structured matrix, reducing the computational complexity to Õ(n 2 ). We also describe two variants of the PCG which allow producing large matrix multiplication correlations with different parameter tradeoffs. While much less practical than our main constructions, we present these in Section 10 for completeness.

A first attempt. The problem with the above construction is that it produces an entire tensor product correlation, which inherently requires Ω(n 2 ) computation. Even if we only want to compute the diagonal entries of the tensor product output (that is, n OLEs), we do not see a way to do this any more efficiently. The bottleneck is computing the n 2 entries of e 0 ⊗ e 1 to obtain z. A natural idea to reduce the computational complexity is to replace e 0 and e 1 by degree-n sparse polynomials e 0 and e 1 , and x 0 and x 1 by, say, n/2 evaluations of e 0 and e 1 respectively. Then, z is computable in quasilinear time as evaluations of the polynomial product e 0 • e 1 of degree 2n. This approach does not give a secure PCG candidate, though, because x 0 and x 1 can be efficiently distinguished from random using algebraic decoding techniques.

An efficient PCG for OLE. Our actual approach follows the same idea, but with the underlying code chosen more carefully. Namely, let R p = Z p [X]/F (X) for some degree N polynomial F (X), and let e, f be two sparse polynomials in R p . For a random polynomial a ∈ R p , the pair

(a, a • e + f mod F (X))
is pseudorandom under the ring-LPN assumption [HKL + 12]. Now, given two pairs of sparse polynomials (e 0 , e 1 ) and (f 0 , f 1 ), each product e i • f j (without reduction modulo F ) has degree < 2N and only t 2 non-zero coefficients. These can again be distributed to two parties using FSS, but this time the expanded FSS outputs can be computed in linear time in N , instead of quadratic, since the domain size of the function being shared is only 2N .

Given shares of e i • f j , similarly to the LPN case, the parties compute expanded outputs by defining

x 0 = a • e 0 + f 0 , x 1 = a • e 1 + f 1 , z = ((1, a) ⊗ (1, a)) • ((e 0 , f 0 ) ⊗ (e 1 , f 1 ))
The main difference here is that each tensor product is only of length 2, and can be computed in Õ(N ) time using fast polynomial multiplication algorithms.

This gives a PCG that compresses a single OLE over the ring R p . To obtain a PCG for OLE over Z p , we again take inspiration from the fully homomorphic encryption literature, by using ciphertext-packing techniques [START_REF] Smart | Fully homomorphic simd operations[END_REF]. We can carefully choose p and F (X) such that F (X) splits into N distinct, linear factors modulo p. Then R p is isomorphic to N copies of Z p , and we can immediately convert a random OLE over R p into N random OLEs over Z p . This works particularly well with cyclotomic rings as used in ring-LWE [START_REF] Lyubashevsky | A toolkit for ring-LWE cryptography[END_REF], where we can e.g. use N a power of two and easily exploit FFTs for polynomial arithmetic.

Extending to authenticated multiplication triples. We show that our construction extends from OLE to authenticated multiplication triples, as used in the SPDZ protocol for maliciously secure MPC [DPSZ12, DKL + 13]. This follows from a simple trick, where we modify the FSS scheme to additionally multiply its outputs by a random MAC key α ∈ Z p . Since this preserves sparsity of the underlying shared vector, it adds only at most a factor of two overhead on top of the basic scheme.

Distributed setup. We focus on the case of OLE correlations over R p (the setup for authenticated triples is very similar). Recall that the seed of the PCG for OLE consists of t-sparse degree-N "error" polynomials e 0 , e 1 and f 0 , f 1 , and FSS keys for secret-shares of the products e i • f j , each represented as a coefficient vector via the sum of t 2 point functions f α,β : [2N ] → Z p . Each point function corresponds to a single monomial product from e i and f j . The index α ∈ [2N ] of the nonzero position is the sum of the corresponding nonzero indices, and the payload β ∈ Z p is the product of the corresponding payloads in e i and f j .

In the semi-honest setting, secure computation of this PCG generation procedure can be attained directly, using generic 2-PC for simple operations on the α and β values, as well as black-box use of a protocol for secure computation of FSS key generation, such as the efficient protocol of Doerner and shelat [START_REF] Doerner | Scaling ORAM for secure computation[END_REF].

For the malicious setting, we would wish to mimic the same protocol structure with underlying 2-PC components replaced with maliciously secure counterparts. The simple 2-PCs on α, β can be converted to malicious security with relatively minor overhead. The problem is the FSS key generation, for which efficient maliciously secure protocols currently do not exist. Generic 2-PC of the FSS key generation functionality would require expensive secure evaluations of crytographic pseudorandom generators (PRG). The semi-honest protocol of [START_REF] Doerner | Scaling ORAM for secure computation[END_REF] is black-box in a PRG; but, precisely this fact makes it difficult to ensure consistency between different steps in the face of a malicious party.

Note that this is similar to the problem that Boyle et al. faced in [BCG + 19a] for silent OT generation, but their setting was conceptually simpler: There, one party always knew the position α of the non-zero value of the distributed point function (indeed, for their purpose the simpler building block of a puncturable pseudorandom function sufficed). Further, they did not have to assume any correlation between path values, whereas in our setting we require that the parties behave consistently regarding the path positions and payloads across several instances.

In this work we show how to extend the approach of [BCG + 19a] to the context of distributed point functions, further addressing the mentioned issues.

Our protocol realizes a PCG-type functionality for a scaled unit vector3 with leakage: Given authenticated values for the location of the non-zero position α ∈ [0..N ) and the non-zero payload β ∈ Z p , the functionality allows a corrupt party to choose its output vector y ∈ Z N p and delivers to the honest party the correct corresponding output y -(0, . . . , β, . . . , 0), where β is in the α-th position. The leakage on α can be captured by allowing the adversary a predicate guess on α. 4In the setting of noise generation for (ring-)LPN, as is the case for our PCG constructions (and likely future constructions), such leakage is tolerable as, intuitively, this can be accounted for by slightly increasing the noise rate. Indeed, we prove that this functionality suffices to implement a protocol securely realizing PCG functionalities, such as the corruptible functionality for OLE and authenticated multiplication triples, based on a variant of the ring-LPN assumption that allows small amount of leakage (only 1 bit on average).

Extensions. A downside of the above construction, compared with the one from LPN, is that it is restricted to multiplication triples or OLE. It can be useful to obtain other degree-two correlations such as matrix multiplication triples, which allow multiplying two secret matrices with only O(n 2 ) communication, instead of O(n 3 ) from naively using individual triples. Another technique is preprocessing multiplications in a way that depends on the structure of the circuit, which allows reducing the online cost of 2-PC down to communicating just one field element per party, instead of two from multiplication triples [START_REF] Beaver | Efficient multiparty protocols using circuit randomization[END_REF][START_REF] Damgård | The TinyTable protocol for 2-party secure computation, or: Gate-scrambling revisited[END_REF][START_REF] Couteau | A note on the communication complexity of multiparty computation in the correlated randomness model[END_REF][START_REF] Ben-Efraim | Turbospeedz: Double your online SPDZ! Improving SPDZ using function dependent preprocessing[END_REF][START_REF] Boyle | Secure computation with preprocessing via function secret sharing[END_REF]. This type of circuit-dependent preprocessing can also be expressed as a degree two correlation.

Our PCG for OLE satisfies a useful "programmability" feature, introduced by Boyle et al. [BCG + 19b], allowing certain parts of the PCG output to be reused across multiple instances. This is simply due to the fact that we can reuse the polynomials e 0 , e 1 or f 0 , f 1 in the PCG, without harming security. This allows us to extend the PCG to build more general correlations, by using multiple programmed instances to perform every multiplication in the general correlation.

We in fact present a more general construction, which, loosely speaking, achieves the following. Given a programmable PCG for some bilinear correlation g, let f be another bilinear correlation that is computable using linear combinations of outputs of g applied to its input. Then, we can construct a PCG for f using several copies of the PCG for g, where the number of instances is given by the complexity of f written as a function of g. This gives a general way of combining PCGs to obtain correlations of increasing complexity, while allowing for different complexity tradeoffs by varying the "base" bilinear correlation f . Multi-party PCGs. As discussed earlier, the programmability feature also immediately allows us to extend our PCGs for OLE and degree-two correlations to the multi-party setting, using the construction from [BCG + 19b]. This does not apply to the PCG for authenticated multiplication triples; in Section 7.6, we sketch a possible alternative solution based on three-party distributed point functions, but these are much less efficient than the two-party setting.

Security analysis of ring-LPN. We use the ring R p = Z p [X]/F (X), for some degree N polynomial F (X). There are two main ring-LPN variants we consider, depending on how the parameters are instantiated. The more conservative is when F (X) is either irreducible in R p (hence, R p is isomorphic to a finite field), or at least when F (X) has only very few low-degree factors, so R p has a large subring that is a field. This type of instantiation is similar to previous recommendations for ring-LPN [HKL + 12, GJL15] and post-quantum encryption schemes from quasi-cyclic codes [MBD + 18]. The best known attacks are to solve the underlying syndrome decoding problem, and the additional ring structure does not seem to give much advantage. One exception is when a very large number of samples are available, when the ring structure can in some cases be exploited [START_REF] Daniel | Never trust a bunny[END_REF]. This does not apply to our setting, however, since our constructions only rely on ring-LPN with one sample5 .

The second variant, which is needed for silent OLE in F p , is when F (X) splits modulo p into many distinct factors of low degree. Here, the main attack vector that needs to be considered is that if f i is some degree-d factor of F (X), then reducing a ring-LPN instance modulo f i gives a new instance in smaller dimension d, albeit with a different noise distribution. The best case for the adversary is when f i is of the form X d + c i , when this reduction does not increase the Hamming weight of the noise (although, the corresponding error rate goes up). If such sparse factors exist, then, we must also ensure that the underlying ring-LPN instance in dimension d, with new noise weight, is hard to solve.

One way to counter this attack is to choose F (X) to be a product of N random linear factors, ensuring that any factors of F an adversary can find are likely to be very dense. However, to improve computational efficiency, it is better to use a cyclotomic polynomial such as F (X) = X N + 1 with N a power of two, as is common in the ring-LWE setting. In this case, there are many sparse factors of the form X 2 i + c i which can be exploited, and we must take these into account when choosing parameters. The main advantage of performing this reduction is the vector operations in attacks such as information-set decoding become cheaper, since they are all in a smaller dimension. This only has a small overall effect on attack complexity, though, since these algorithms are all exponential in the noise weight. Therefore, to counter the attack, it suffices to ensure there are enough noisy coordinates in a reduced instance, which requires only a small increase in noise weight.

Note that for p = 2, this strategy was also considered in Lapin [HKL + 12], and it was later shown that an optimized version of this over F 2 reduces security of some Lapin parameter sets by ≈ 10 bits [START_REF] Guo | A new algorithm for solving ring-lpn with a reducible polynomial[END_REF]. Our analysis over F p is roughly consistent with this.

Preliminaries

Notation

We let λ denote a security parameter, and use the standard definitions of negligible functions, computational indistinguishability (with respect to nonuniform distinguishers), and pseudorandom generators. We use [0..n) to denote the index set {0, • • • , n-1}, as well as [0.

.n] = {0, . . . , n} and [n] = {1, . . . , n}.

Vectors, outer sum and outer product. We use column vectors by default. For two vectors u = (u 1 , . . . , u t ), v = (v 1 , . . . , v t ) ∈ R t , for some ring R, we write u v to mean the outer sum given by the length t 2 vector (u i + v j ) i∈[t],j∈ [t] . Similarly, we define the flattened outer product (or tensor product) to be u

⊗ v = (u i • v j ) i∈[t],j∈[t]
, that is, the vector (v 1 • u, . . . , v n • u). We denote the inner product of two vectors by u, v .

Function Secret Sharing

Function secret sharing [START_REF] Boyle | Function secret sharing[END_REF][START_REF] Boyle | Function secret sharing: Improvements and extensions[END_REF] (FSS) is a succinct secret sharing of functions. More concretely, an FSS scheme randomly splits a secret function f : I → G, where G is some Abelian group, into two or more functions f i , each represented by a key K i , such that: (1) the sum of all function shares f i is equal to f (namely, i f i (x) = f (x) for every input x ∈ I), and (2) each subset of the keys K i hides f . In this work we will use 2-party FSS that we formalize below.

Definition 2.1 (Function Secret Sharing) Let C = {f : I → G} be a class of function descriptions, where the description of each f specifies the input domain I and an Abelian group (G, +) as the output domain. A (2-party) function secret sharing (FSS) scheme for C is a pair of algorithms FSS = (FSS.Gen, FSS.Eval) with the following syntax:

• FSS.Gen(1 λ , f ) is a PPT algorithm that given security parameter λ and description of f ∈ C outputs a pair of keys (K 0 , K 1 ). We assume that the keys specify I and G.

• FSS.Eval(b, K b , x) is a polynomial-time algorithm that, given a key K b for party b ∈ {0, 1}, and an input x ∈ I, outputs a group element y b ∈ G.

The scheme should satisfy the following requirements:

• Correctness: For any f ∈ C and x ∈ I, we have Pr[(K 0 , K 1 )

$ ← FSS.Gen(1 λ , f ) : b∈{0,1} FSS.Eval(b, K b , x) = f (x)] = 1.
• Security: For any b ∈ {0, 1}, there exists a PPT simulator Sim such that for any polynomial-size function sequence

f λ ∈ C, the distributions {(K 0 , K 1 ) $ ← FSS.Gen(1 λ , f λ ) : K b } and {K b $ ← Sim(1 λ , Leak(f λ ))} are computationally indistinguishable.
In the constructions we use, the leakage function Leak : {0, 1} * → {0, 1} * is given by Leak(f λ ) = (I, G), namely it outputs a description of the input and output domains of f . We also define a full-domain evaluation algorithm, FSS.FullEval(b, K b ), which outputs a vector of |I| group elements, corresponding to running Eval on every element x in the domain I. For the type of FSS we consider, FSS.FullEval is significantly faster than the generic solution of running |I instances of Eval.

We will use FSS for point functions and sums of point functions, as defined below.

[n] → G | α ∈ [n], β ∈ G}.
The best known DPF construction [START_REF] Boyle | Function secret sharing: Improvements and extensions[END_REF] can use any pseudorandom generator (PRG) G : {0, 1} λ → {0, 1} 2λ+2 and has the following efficiency features. For m = log|G| λ+2 , the key generation algorithm Gen invokes G at most 2( log n + m) times, the evaluation algorithm Eval invokes G at most log n + m times, and the full-domain evaluation algorithm FullEval invokes G at most n • (1 + m) times. The size of each key is at most log n • (λ + 2) + λ + log 2 |G| bits.

We will use a simple and generic extension of DPF to sums of point functions.

Definition 2.3 (FSS for sum of point functions (SPFSS)) For S = (s 1 , . . . , s t ) ∈ [n] t and y = (y 1 , . . . , y t ) ∈ G t , define the sum of point functions f S, y :

[n] → G by f S, y (x) = t i=1 f s i ,y i (x).
An SPFSS scheme is an FSS scheme for the class of sums of point functions f S, y .

Note that for S = (s 1 , . . . , s t ), the function f S, y non-zero on at most t points. If the elements of S are distinct, f S, y coincides with a multi-point function for the set of points in S; however, in our usage we can have repeated elements in S. A simple realization of SPFSS is by summing t independent instances of DPF. This will typically be good enough for our purposes. Alternatively, asymptotically better constructions for full-domain evaluation can be obtained using hash functions or (probabilistic) batch codes [IKOS04, BCGI18, ACLS18, SGRR19]. To simplify notation, when generating keys for a scheme SPFSS = (SPFSS.Gen, SPFSS.Eval), we write SPFSS.Gen(1 λ , S, y), instead of explicitly writing f S, y .

Pseudorandom Correlation Generators

A pseudorandom correlation generator (PCG) [BCGI18, BCG + 19b] is a primitive with a setup algorithm that generates a pair of seeds, which can then be locally expanded to produce correlated pseudorandomness. To define security, we use the notions of correlation generators, and reversesampleable correlation generators, from [BCG + 19b].

Definition 2.4 (Correlation generator) A PPT algorithm C is called a correlation generator, if C on input 1 λ outputs a pair of elements in {0, 1} n × {0, 1} n for n ∈ poly(λ). Definition 2.5 (Reverse-sampleable correlation generator) Let C be a correlation generator. We say C is reverse sampleable if there exists a PPT algorithm RSample such that for σ ∈ {0, 1} the correlation obtained via:

{(R 0 , R 1 ) |(R 0 , R 1 ) $ ← C(1 λ ), R σ := R σ , R 1-σ $ ← RSample(σ, R σ )} is computationally indistinguishable from C(1 λ ).
The following definition of pseudorandom correlation generators can be viewed as a generalization of the definition of the pseudorandom VOLE generator in [START_REF] Boyle | Compressing vector OLE[END_REF].

Definition 2.6 (Pseudorandom Correlation Generator (PCG)) Let C be a reverse-sampleable correlation generator. A pseudorandom correlation generator (PCG) for C is a pair of algorithms (PCG.Gen, PCG.Expand) with the following syntax:

• PCG.Gen(1 λ ) is a PPT algorithm that given a security parameter λ, outputs a pair of seeds (k 0 , k 1 );

• PCG.Expand(σ, k σ ) is a polynomial-time algorithm that given a party index σ ∈ {0, 1} and a seed k σ , outputs a bit string R σ ∈ {0, 1} n .

The algorithms (PCG.Gen, PCG.Expand) should satisfy the following:

• Correctness. The correlation obtained via:

{(R 0 , R 1 ) | (k 0 , k 1 ) $ ← PCG.Gen(1 λ ), R σ ← PCG.Expand(σ, k σ ) for σ ∈ {0, 1}}
is computationally indistinguishable from C(1 λ ).

• Security. For any σ ∈ {0, 1}, the following two distributions are computationally indistinguishable:

{(k 1-σ , R σ ) | (k 0 , k 1 ) $ ← PCG.Gen(1 λ ),R σ ← PCG.Expand(σ, k σ )} and {(k 1-σ , R σ ) | (k 0 , k 1 ) $ ← PCG.Gen(1 λ ),R 1-σ ← PCG.Expand(σ, k 1-σ ), R σ $ ← RSample(σ, R 1-σ )}
where RSample is the reverse sampling algorithm for correlation C.

Note that to avoid the trivial solution where PCG.Gen simply outputs a sample from C, we are only interested in constructions where the seed size is significantly shorter than the output size.

The Ring-LPN Assumption

In this section, we recall the ring-LPN assumption, which was first introduced (over Z 2 ) in [HKL + 12] to build efficient authentication protocols. Since then, it has received some attention from the cryptography community [BL12, DP12,LP15, GJL15], due to its appealing combination of LPNlike structure, compact parameters, and short runtimes. Below, we provide a definition of module-LPN, which generalizes ring-LPN in the same way that the more well-known module-LWE generalizes ring-LWE. We also discuss several variants depending on the choice of ring, including cyclotomic rings over Z p , which have previously been used for ring-LWE.

Ring-LPN

Definition 3.1 (Ring-LPN) Let R = Z p [X]/F (X) for a prime p and degree-N polynomial F (X) ∈ Z p [X]. (We will write R p when we want to highlight the modulus p.) For t ∈ N, let HW R,t denote the distribution of "sparse polynomials" over R obtained by sampling t noise positions A ← [0..N ) t and t payloads b ← (Z * p ) t uniformly at random, and outputting e(X)

:= t-1 j=0 b[j] • X A[j]
. (We write HW t when R is clear from the context.) For R = R(λ), m = m(λ), t = t(λ), we say that the ring-LPN problem R-LPN R,m,t is hard if for every nonuniform polynomial-time distinguishher A, it holds that

Pr[A((a (i) , a (i) • e + f (i) ) m i=1 ) = 1] -Pr[A((a (i) , u (i) ) m i=1 ) = 1] ≤ negl(λ)
where the probabilities are taken over a (1) , . . . , a (m) , u (1) , . . . , u (m) ← R(λ) and e, f (1) , . . . , f (m) ← HW R,t . We will also use the regular variant of R-LPN R,m,t , which is defined in the same way as above except that HW R,t is obtained by letting A include a single random position from each block of size N/t (where here we assume that t|N ).

Remark 3.1 (Useful parameters) Our constructions will only use Definition 3.1 with m = 1, namely one sample. Bigger values of m will be used for reducing security in this case to a variant where the secret e is uniform (see Lemma 3.4 below). The sparsity parameter t will roughly correspond to a concrete security parameter, the degree N to the length of the target correlation (or number of instances of an atomic correlation), and p to a modulus over which this correlation is defined. Useful choices of the polynomial F (X) will be discussed in Section 3.2 below. Remark 3.2 (Noise distribution) Note that in the default variant of our definition, the distribution over sparse polynomials is obtained by picking the t noise positions with replacement. This can result in collisions, and thus negatively affect the entropy introduced by the payloads. The reason for this choice is that it helps simplify some of our constructions and their analysis. The entropy loss is minor in the regime of parameters we care about, as for t N the probability of collisions is very small. The collisions are entirely avoided in the regular variant of the definition, which also leads to better concrete efficiency in our constructions.

Remark 3.3 (Extension to other rings.) Note that our restriction to prime-order fields Z p is only for simplicity; R-LPN can be defined similarly over other rings (such as extension fields F p d or rings Z 2 k or Z pq for primes p, q). These alternative choices are not known to introduce any significant weakness or structural difference compared to the version over prime-order fields. In fact, we obtain PCGs for OLEs and multiplication triples over extension fields F p d by using rings R p defined over the base field.

Module LPN. We will also use a natural generalization of R-LPN, where we replace a (i) • e by the inner product a (i) , e between length-(c -1) vectors over R, for some constant c ≥ 2. (The parameter c can be viewed as a compression factor in our construction -see more below.) We call this module-LPN, analogously to module-LWE. This will allow for useful efficiency tradeoffs, as according to our security analysis it will be enough to choose the total number of noise positions w such that w = ct ≈ λ, and therefore increasing c allows to choose a smaller t. For the parameter regime in our constructions, increasing c will result in shorter PCG seeds at the expanse of higher running time of Expand. Definition 3.2 (Module-LPN) Let c ≥ 2 be an integer and R, HW R,t be as in Definition 3.1. Then, for R = R(λ), m = m(λ), t = t(λ), we say that the R c -LPN R,m,t problem is hard if for every nonuniform polynomial-time distinguisher A, it holds that

Pr[A(( a (i) , a (i) , e + f (i) ) m i=1 ) = 1] -Pr[A(( a (i) , u (i) ) m i=1 ) = 1] ≤ negl(λ)
where the probabilities are taken over a (1) , . . . , a (m) ← R c-1 , u (1) , • • • , u (m) ← R, e ← HW c-1 R,t , f (1) , . . . , f (m) ← HW R,t . We similarly define the regular variant by modifying HW R,t as in Definition 3.1.

Equivalence to module-LPN with uniform secret. We observe that, by the same argument as for standard LWE [START_REF] Applebaum | Fast cryptographic primitives and circular-secure encryption based on hard learning problems[END_REF], the R-LPN (resp. module-LPN) problem with a secret chosen from the error distribution is at least as hard as the corresponding R-LPN (resp. module-LPN) problem where the secret is chosen uniformly at random, if the adversary is given one additional sample (resp., c -1 additional samples).

Lemma 3.4 For any c ≥ 2, let R c -uLPN denote the variant of R c -LPN where the secret e is sampled uniformly at random. Then, for any

R = R(λ), m = m(λ), t = t(λ), if R c -uLPN R,m+(c-1),t is hard then R c -LPN R,m,t is hard.
Proof. Let m > c. We show how a distinguisher for R c -LPN R,m-(c-1),t can be used to solve an instance of R c -uLPN R,m,t , which implies the statement in the theorem. Let ( a (1) , u (1) , • • • , a (m) , u (m) ) be R c -uLPN samples, where a (i) ∈ R c-1 and u (i) ∈ R for i = 1 to m. Assume that ( a (1) , • • • , a (c-1) ), viewed as a matrix A of dimensions (c -1) × (c -1) over R, is invertible; this happens with high probability (at least constant) over a random choice of the a (i) . Denote by A ∈ R m-(c-1)×(c-1) the matrix whose rows are the remaining ( a (c) , • • • , a (m) ), by u the (vertical) vector (u (1) , • • • , u (c-1) ), and by u the (vertical) vector (u (c) , • • • , u (m) ). With these, the distinguishing game can be rewritten as follows: the adversary must distinguish between the case where

• A e + f = u for some e ∈ R c-1 and sparse f ∈ HW c-1 R,t , and

• A e + f = u for some sparse f ∈ HW m-c+1 R,t , from the case where ( u, u ) are random. But since A is invertible, by multiplying the first equation with B ← A A -1 and denoting v ← B u -u , the first case can be rewritten as

B f -f = v
which is distributed exactly as an instance of the R c -LPN R,m-(c-1),t problem; hence, a distinguisher for R c -LPN R,m-(c-1),t can be used to get a distinguisher for R c -uLPN R,m,t .

Relation to syndrome decoding. Our constructions will use module-LPN with a single sample (m = 1). To simplify notation and emphasize that the secret comes from the error distribution, we often combine the secret and noise value ( e and f in the notation of Definition 3.2) into a single vector e, replacing the previous ( a, a, e + f ) by writing ( a, a, e ), where

a = (1, a ), a $ ← R c-1 , e $ ← HW c R,t
. This formulation of module-LPN is equivalent to a variant of the syndrome decoding problem in random polynomial codes. To see this, let M i be the N × N matrix over Z p representing multiplication with the fixed element a i ∈ R p , for i = 1 to c -1. Define the matrix

H = [Id N ||M 1 || • • • ||M c-1 ].
H is a parity-check matrix in systematic form for a polynomial code defined by the random elements a i ∈ R p . Module-LPN can be seen as a decisional version of syndrome decoding for this code, where we assume that (H, H • e) is pseudorandom for an error vector e = (e 1 , . . . , e c ) with a regular structure, namely where each of the length-N blocks e i have t non-zero entries. The code has length N • c and dimension N • (c -1); the rate of the code is therefore (c -1)/c. With this formulation, c can be viewed as the compression factor of the linear map e → H • e. Therefore, we generally refer to c as the syndrome compression factor.

Choice of the Polynomial F

The ring-LPN assumption (and more generally, the module-LPN assumption) is dependent of the choice of the underlying polynomial F . We discuss possible choices for the polynomial F , and their implications for the security of ring-LPN/module-LPN over the corresponding ring

R p = Z p [X]/F (X).
Irreducible F (X). The most conservative instantiation is when F (X) is irreducible over Z p , and so R p is a field. In this setting, no attacks are known that perform significantly better than for standard LPN.

Reducible F (X). We also consider when F (X) is reducible over Z p , and splits into several distinct factors. Here we have a few different useful instantiations.

1. Cyclotomic F (X). Let F (X) be the M -th cyclotomic polynomial, whose degree is N = φ(M ) (Euler's totient function). Then, F (X) splits modulo p into N/d distinct factors f i , where each f i is of degree d, and d is the smallest integer satisfying p d ≡ 1 mod M . The advantage of using a cyclotomic F is that it allows for fast multiplication in R p using FFT. We are particularly interested in the following cases.

• Two-power N , prime p > 2N . Let N be a power of two and p a large prime such that p ≡ 1 mod (2N ) (here, M = 2N ). Then F (X) splits completely into N linear factors modulo p, so R p is isomorphic to Z N p . • p = 2. Here, each degree-d subring Z p [X]/(f i (X)) is isomorphic to the finite field

F 2 d , hence R p ∼ = F N/d 2 d .
Regarding security, we observe that cyclotomic polynomials can introduce an additional weakness, due to sparse factors of F (X). In Section 8.2, we analyze this further and discuss how to adjust parameters accordingly.

2. Random factors. A more conservative option may be to choose an F (X) that splits completely into d distinct, random factors. For instance, for a large prime p we can pick (distinct) random elements α 1 , . . . , α N ← Z p and let

F (X) = N i=1 (X -α i )
Just as with the two-power cyclotomic case, R p is isomorphic to Z N p . Now, however, the problem may be harder since we are avoiding the structure given by roots of unity. On the other hand, the isomorphism is more expensive to compute as we can no longer make a direct use of FFT, and polynomial interpolation algorithms cost O(N log 2 N ) instead of O(N log N ).

PCGs for OLE and Authenticated Multiplication Triples

In this section, we construct PCGs for OLE and authenticated multiplication triples, based on the R c -LPN assumption. The constructions in this section can achieve an arbitrary (a priori bounded) polynomial stretch, where the seed size scales logarithmically with the output length N and the running time of Expand scales nearly linearly with N .

PCG for OLE over R p

We build a PCG for producing a single OLE over the ring R p . When R p splits appropriately, as described in Section 3.2, this can be locally transformed into a PCG for a large batch of OLEs or (authenticated) multiplication triples over a finite field F p d or F p . The OLE correlation over R p outputs a single sample from the distribution

((x 0 , z 0 ), (x 1 , z 1 )) x 0 , x 1 , z 0 $ ← R p , z 1 = x 0 • x 1 -z 0
This can be viewed as giving the two parties additive shares of a product of two random elements x 0 , x 1 of R p , where x σ is known to party P σ .

Below is an informal presentation of the construction, which is described formally in Fig. 1. The high-level idea is to first give each of the two parties a random vector e 0 or e 1 ∈ R c p , consisting of sparse polynomials, together with a random, additive secret sharing of the tensor product e 0 ⊗ e 1 over R p .

We view e 0 , e 1 as R c -LPN error vectors (whose first entry is implicitly the R c -LPN secret), which will be expanded to produce outputs x σ = a, e σ by each party P σ for a random, public a = (1, ˆ a). This defines two R c -LPN instances with independent secrets but the same a value, which are pseudorandom by a standard reduction to R c -LPN with a single sample. To obtain shares of x 0 • x 1 , observe that when a is fixed, this is a degree 2 function in ( e 0 , e 1 ), so can be computed locally by the parties given their shares of e 0 ⊗ e 1 .

The only part that remains, then, is to distribute shares of this tensor product. Recall that each entry of e σ is a polynomial of degree less than N with at most t non-zero coordinates. We write these coefficients as a set of indices A ∈ [0..N ) t and corresponding non-zero values b ∈ Z t p . Taking two such sparse polynomials (A, b) and (A , b ), notice that the product of the two polynomials is given by

  i∈[0..t) b[i] • X A[i]   •   j∈[0..t) b [j] • X A [j]   = i,j∈[0..t) b[i] • b [j] • X A[i]+A [j]
We can therefore express the coefficient vector of the product as a sum of t 2 point functions, where the (i, j)-th point function evaluates to b

[i] • b [j] at input A[i] + A [j]
, and zero elsewhere. This means the parties can distribute this product using a function secret sharing scheme SPFSS for sums of point functions, as defined in Definition 2.3. Recall that an SPFSS takes a sequence of points and associated vector of values, and produces two keys that represent shares of the underlying sum of point functions. If each party locally evaluates its key at every point in the domain, then it obtains a pseudorandom secret-sharing of the coefficients of the entire sparse polynomial.

There are c 2 polynomials in the tensor product, so overall we need c 2 instances of SPFSS, where each SPFSS uses t 2 point functions. Instantiating this naively using t 2 distributed point functions, we get a seed size of Õ(λ(ct) 2 log N ) bits. Note that to achieve exponential security against the best known attacks on R c -LPN, it is enough to choose ct = O(λ). By increasing N , we can therefore obtain an arbitrary polynomial stretch for the PCG, where the stretch is defined as the ratio of its output length to the seed size.

More concretely, we have the following theorem.

Construction G OLE

Parameters: Security parameter λ, noise weight t = t(λ), compression factor c ≥ 2, modulus p = p(λ), degree N = N (λ), and the ring

R p = Z p [X]/F (X) for degree-N F (X) ∈ Z p [X].
An FSS scheme (SPFSS.Gen, SPFSS.FullEval) for sums of t 2 point functions, with domain

[0..2N -1) and range Z p . Public input: random polynomials a 1 , . . . , a c-1 ∈ R p , used for R c -LPN. Correlation: After expansion, outputs (x 0 , z 0 ) ∈ R 2 p and (x 1 , z 1 ) ∈ R 2 p , where z 0 +z 1 = x 0 •x 1 . Gen: On input 1 λ : 1. For σ ∈ {0, 1} and i ∈ [0..c), sample random vectors A i σ ← [0..N ) t and b i σ ← (Z * p ) t . 2. For each i, j ∈ [0..c), sample FSS keys (K i,j 0 , K i,j 1 ) $ ← SPFSS.Gen(1 λ , A i 0 A j 1 , b i 0 ⊗ b j 1 ). 3. Let k σ = (K i,j σ ) i,j∈[0..c) , (A i σ , b i σ ) i∈[0..c) .
4. Output (k 0 , k 1 ).

Expand: On input (σ, k σ ):

1. Parse k σ as (K i,j σ ) i,j∈[0..c) , (A i σ , b i σ ) i∈[0..c) .
2. Define (over Z p ) the degree < N polynomials, for i ∈ [0..c)

e i σ (X) = j∈[0..t) b i σ [j] • X A i σ [j]
3. Compute x σ = a, e σ mod F (X), where a = (1, a 1 , . . . , a c-1 ), e σ = (e 0 σ , . . . , e c-1 σ ).

4. For i, j ∈ [0..c), compute u σ,i+cj ← SPFSS.FullEval(σ, K i,j σ ) and view this as a degree < 2N polynomial, defining the length-c 2 vector u σ mod F (X). Theorem 4.1 Suppose that SPFSS is a secure FSS scheme for sums of point functions (Definition 2.3), and the R c -LPN Rp,1,t assumption (Definition 3.2) holds. Then the construction in Fig. 1 is a secure PCG for OLE over R p .

Compute z

σ = a ⊗ a, u σ mod F (X). 6. Output (x σ , z σ )
When instantiating SPFSS using from PRG : {0, 1} λ → {0, 1} 2λ+2 via the PRG-based DPF construction from [START_REF] Boyle | Function secret sharing: Improvements and extensions[END_REF], we have:

• Each party's seed has size at most (ct) 2 • (( log N + 1) • (λ + 2) + λ + log p ) + ct( log N + log p ) bits.

• The computation of Expand can be done with at most (4 + 2 log p/λ )N (ct) 2 PRG operations, and O(c 2 N log N ) operations in Z p .

Under standard ring-LPN parameters the above can be instantiated with seed size poly(λ)•log N and with Expand running in time O(N 1+ ). This running time can be improved to Õ(N ) using batch codes, as discussed below. Increasing the syndrome compression parameter c allows choosing a smaller noise parameter t, which results in smaller seed side at the expense of increased running time.

Proof. We first argue correctness. Let i, j ∈ [0..c) and consider the polynomials e i 0 , e j 1 defined in Expand. We have,

e i 0 (X) • e j 1 (X) = k, ∈[0..t) b i 0 [k] • b j 1 [ ] • X A i 0 [k]+A j 1 [ ]
Therefore, the coefficients of this product can be obtained by evaluating the sum of point functions used in the (i, j)-th instance of SPFSS. This means that u 0,i+cj + u 1,i+cj equals e i 0 (X) • e j 1 (X), and hence, u = e 0 ⊗ e 1 . Looking at the outputs of expand, we then have

z 0 + z 1 = a ⊗ a, u 0 + u 1 = a ⊗ a, e 0 ⊗ e 1 = a, e 0 • a, e 1 = x 0 • x 1
where the penultimate equality can be seen by inspection of the tensor products. Each a, e σ can be seen as a sample from the R c -LPN distribution with a fixed random a and independent secret e σ . It follows from a standard hybrid argument that (x 0 , x 1 ) is computationally indistinguishable from a random pair in R 2 p , under R c -LPN. Furthermore, by the security of SPFSS, each z σ is individually pseudorandom, so the outputs (x 0 , z 0 , x 1 , z 1 ) are indistinguishable from a random OLE over R.

To show the security property, fix σ = 1 (the case σ = 0 is symmetric). For two keys (k 0 , k 1 ) $ ← PCG.Gen(1 λ ) with associated expanded outputs (x 0 , z 0 ) and (x 1 , z 1 ), we need to show that

{(k 1 , x 0 , z 0 )} ≡ (k 1 , x0 , z0 )|x 0 $ ← R p , z0 = x0 • x 1 -z 1
We use a sequence of hybrids, where first we change z 0 to be computed as x 0 • x 1 -z 1 , and successively replace each FSS key K i,j 1 in k 1 with a simulated key, generated with only the range and domain of the function. This is indistinguishable from the first distribution, by the correctness and security properties of the FSS scheme. Then, since K 1 and z 0 are independent of the R c -LPN secret producing x 0 , we can rely on R c -LPN to sample x 0 at random instead of from the seed k 0 . Finally, we can now switch the FSS keys back to ones generated from SPFSS.Gen, again using the FSS security property. This gives the distribution on the right.

We remark that assuming R c -LPN holds for regular error distributions, the seed size can be reduced to roughly (ct) 2 • ((log N -log t + 1) • (λ + 2) + λ + log p) + ct(log N + log p) bits, and the number of PRG calls in Expand down to (4 + 2 (log p)/λ )N c 2 t. See details below. This eliminates a factor of t from the asymptotic computational cost. Furthermore, implementing SPFSS using batch codes reduces the number of PRG calls to O(N c 2 ). This eliminates another factor of t, making the overall computational overhead logarithmic in N , but comes at a cost of making distributed seed generation more complex.

Obtaining OLEs over F p . As discussed in Section 3.2, when R and p are chosen appropriately, an OLE over R p is locally equivalent to N OLEs over F p or F p d . Hence, this PCG immediately implies PCGs over F p d , with the same seed size and complexity.

If we want to rely on the (apparently) more conservative version of R c -LPN, where F (X) is irreducible in Z p [X], the parties can still use our PCG over R p to obtain OLEs over Z p , but this requires O(N ) interaction. To do this, the parties each sample random polynomials a, b ∈ Z p [X], each of degree < N/2. They then use the OLE over R p to multiply a and b, which can be done by sending N elements of Z p .6 This gives shares of c = ab in R p , which equals ab over Z p [X], since no overflow occurs modulo F (X) (which has degree N ). Each party then locally computes evaluations of its shares of a, b and c at N/2 fixed, distinct, non-zero points, which gives N/2 secret-shared products over Z p (this can be done as long as p > N/2).

Optimizations. We now discuss a few optimizations which apply to the basic scheme.

Optimizing the MPFSS evaluation. Naively, the computational cost of the FSS fulldomain evaluation is O((ct) 2 N ) PRG operations. Using a regular error distribution, we can bring this down to O(c 2 tN ) (see below). With batch codes [START_REF] Ishai | Batch codes and their applications[END_REF][START_REF] Boyle | Compressing vector OLE[END_REF] or probabilistic batch codes [ACLS18,SGRR19], the full evaluation cost can be brought down to O(c 2 N ) operations. However, if the seed generation phase has to be created by a secure distributed protocol, setting up the seeds that support better Expand time can hurt the concrete cost of distributed seed generation.

Using regular errors. Suppose two sparse polynomials e 0 , e 1 ∈ Z N p are regular, that is e b = (e b,1 , . . . , e b,t ), where each e b,j ∈ Z N/t p has weight 1, and defines a coefficient in the range

[(j -1) • (N/t), j • (N/t) -1]. Each pair (e 0,i , e 1,j ) gives rise to an index in [(i + j -2) • (N/t), (i + j) • (N/t) -2]
, so the product of two regular error polynomials can be represented by a t 2 -point SPFSS of domain size 2N/t. This leads to a total expansion cost of O(c 2 tN ) PRG operations.

Extension to multiplication triples. Recall that in an instance of an OLE correlation over Z p , parties P 0 and P 1 each hold a secret random Z p element, and they jointly hold an additive secret-sharing of the product of the two secrets. While OLE correlations can be directly useful for some applications of secure computation [NP99, IPS09, DGN + 17, GN19, CDI + 19, HIMV19], it is often more convenient to use a slightly more complicated variant known as a multiplication triple correlation [START_REF] Beaver | Efficient multiparty protocols using circuit randomization[END_REF]. In a (2-party) multiplication triple, the two parties hold shares of random Z p elements a and b (which are known to neither party), and moreover they hold shares of the product c = a • b. Multiplication triples are useful for 2-PC of arithmetic circuits over Z p with security against semi-honest parties: each multiplication gate can be evaluated by consuming a single multiplication triple and communicating two Z p elements per party. (Addition gates are "for free.") An instance of a multiplication triple correlation can be obtained in a black-box way using two instances of an OLE correlation. Concretely, writing

a = a 0 + a 1 , b = b 0 + b 1 , and c = a 0 b 0 + a 1 b 1 + a 0 b 1 + a 1 b 0 , one can distribute (a σ , b σ )
to party P σ and secret-share the cross-terms a 0 b 1 and a 1 b 0 via two independent OLE instances (the terms a 0 b 0 and a 1 b 1 can be computed locally by P 0 and P 1 respectively and added to the OLE outputs). As a result, a PCG generating N instances of multiplication triples can be obtained from a PCG generating 2N instances of OLE. In the next section we will see how to extend this to authenticated multiplication triples, which serve as a useful resource for 2-PC with security against malicious parties, at a slightly higher cost.

Extension to higher degree correlations. We can naturally extend this construction from OLE over R p to general degree-D correlations (over R p ), for any constant D, by sharing Dway products of sparse polynomials instead of just pairwise products. However, this comes at a high cost: the seed size increases to O((ct) D log N λ), and the computational cost becomes Õ((ct) D • N ).

Authenticated Multiplication Triples

We now show how to modify the PCG for OLE to produce authenticated multiplication triples, which are often used in maliciously secure MPC protocols such as the BDOZ [START_REF] Bendlin | Semihomomorphic encryption and multiparty computation[END_REF] and SPDZ [DPSZ12, DKL + 13] line of work. Note that although OLE can be used to build authenticated triples in a black-box way, doing this requires several OLEs and some interaction, for every triple. This is contrasted with the case of standard multiplication triples, discussed above, that can be reduced to OLE without any interaction. Our PCG avoids this interaction, with only a small overhead on top of the previous construction: the seeds are less than 2x larger, while the expansion phase has around twice the computational cost.

Secret-sharing with MACs. We use authenticated secret-sharing based on SPDZ MACs between n parties, where a secret-sharing of x ∈ Z p is defined as:

x = (α i , x i , m x,i ) n i=1 such that i x i = x, i m x,i = x • i α i
Note that the MAC key shares α i are fixed for every shared x. The MAC shares m x,i are used to prevent a sharing from being opened incorrectly, via a MAC check procedure from [DKL + 13]. An authenticated multiplication triple is a tuple of random sharings ( x , y , z ), where x, y $ ← Z p and z = x • y. Our PCG outputs a single multiplication triple over the ring R p , for n = 2 parties, together with additive shares of the MAC key α ∈ Z p . When using the fully-reducible variant of ring-LPN, this is equivalent to N triples over F p d (where for suitably chosen p we can have d = 1).

PCG construction. The construction, given in Fig. 2, is remarkably simple. Recall that our previous construction for OLE uses FSS keys which are expanded into shares of sparse polynomials u i,j = e i • e j ∈ Z p [X]. The FSS payload was defined by some (column) vector v ∈ Z t 2 p , which defines the t 2 values of the non-zero coefficients in u i,j . We can modify this to produce authenticated OLE by extending the FSS range from Z p to Z 2 p , and letting the payload be v

• (1, α) ∈ Z 2N ×2 p , for a random α ∈ Z p . Evaluating the FSS keys at some input k now produces shares of ( v[k], α • v[k]).
Hence, these can be used to obtain authenticated shares of x 0 • x 1 , as well as the OLE.

To extend the above to authenticated triples, the seed generation phase will now produce three sets of FSS keys. The first two sets, (K i x,0 , K i x,1 ) and (K i y,0 , K i y,1 ), are used to compress shares of the 2c sparse polynomials defined by

(A i 0 , b i 0 ) and (A i 1 , b i 1 )
. These have sparsity t, so can be compressed using t-point SPFSS, and are later expanded to produce shares and MAC shares for R p elements x and y. The third set, (K i z,0 , K i z,1 ), compresses pairwise products of the previous sparse polynomials, so each of these can be defined using t 2 -point SPFSS, as in the previous construction. This gives the shares and MAC shares for the product term z = x • y.

We omit the proof of the following theorem, which is very similar to that of Theorem 4.1. Recall that to achieve exponential security against the best known attacks on R c -LPN, it is enough to choose ct = O(λ), therefore choosing a larger c allows to decrease the size of t. For more details on concrete parameter choices we refer to Section 9.

Construction G triple

Parameters: Security parameter λ, noise weight t = t(λ), compression factor c ≥ 2, modulus p = p(λ), degree N = N (λ), and the ring

R p = Z p [X]/F (X) for degree-N F (X) ∈ Z p [X].
An FSS scheme (SPFSS.Gen, SPFSS.FullEval) for sums of t 2 point functions, with domain [0..2N -1) and range Z 2 p . Public input: random polynomials a 1 , . . . , a c-1 ∈ R p , used for R c -LPN. Correlation: Authenticated triples ( x , y , z ), satisfying z = x • y ∈ R p , and MAC key shares α 0 , α 1 ∈ Z p .

Gen: On input 1 λ : 1. Sample α 0 , α 1 $ ← Z p and let α = α 0 + α 1 . 2. For σ ∈ {0, 1} and i ∈ [0..c), sample random vectors A i σ ← [0..N ) t and b i σ ← (Z * p ) t .
3. Sample the following FSS keys:

• (K i x,0 , K i x,1 ) $ ← SPFSS.Gen(1 λ , A i 0 , b i 0 • (1, α)), for i ∈ [0..c) • (K i y,0 , K i y,1 ) $ ← SPFSS.Gen(1 λ , A i 1 , b i 1 • (1, α)), for i ∈ [0..c) • (K i,j z,0 , K i,j z,1 ) $ ← SPFSS.Gen(1 λ , A i 0 A j 1 , ( b i 0 ⊗ b j 1 ) • (1, α)), for i, j ∈ [0..c) 4. Let k σ = α σ , (K i x,σ , K i y,σ ) i∈[0..c) , (K i,j z,σ ) i,j∈[0..c) .
5. Output (k 0 , k 1 ).

Expand: On input (σ, k σ ), where k σ = α σ , (K i x,σ , K i y,σ ) i∈[0..c) , (K i,j z,σ ) i,j∈[0..c) :
1. Compute the vectors u σ , v σ , w σ and u σ , v σ , w σ as follows:

• u σ,i , u σ,i ← SPFSS.FullEval(σ, K i x,σ ), for i ∈ [0..c) • v σ,i , v σ,i ← SPFSS.FullEval(σ, K i y,σ ), for i ∈ [0..c) • w σ,i+cj , w σ,i+cj ← SPFSS.FullEval(σ, K i,j z,σ ), for i, j ∈ [0..c)
viewing each FullEval output as a pair of degree < 2N polynomials over Z p . Theorem 4.2 Suppose that SPFSS is a secure FSS scheme for sums of point functions (Definition 2.3), and the R c -LPN Rp,1,t assumption (Definition 3.2) holds. Then the construction in Fig. 2 is a secure PCG for two-party authenticated multiplication triples over R p .

Compute

x σ = a, u σ , y σ = a, v σ , z σ = a ⊗ a, w σ and m x,σ = a, u σ , m y,σ = a, v σ , m z,σ = a ⊗ a, w σ all modulo F (X). 3. Output (α σ , x σ , y σ , z σ , m x,σ , m y,σ , m z,σ )
When instantiating SPFSS using from PRG : {0, 1} λ → {0, 1} 2λ+2 via the PRG-based DPF construction from [START_REF] Boyle | Function secret sharing: Improvements and extensions[END_REF], we have a secure PCG for two-party authenticated multiplication triples over R p with the following complexities:

• Each party's seed has size at most 2(2ct+(ct) 2 )•(( log N +1)•(λ+2)+λ+ log p )+ log p bits.

• The computation of Expand can be done with at most (8 + 4 (log p)/λ )N (2ct + (ct) 2 ) PRG operations, and

O(c 2 N log N ) operations in Z p .
As with the PCG for OLE, when using ring-LPN with regular errors the seed size can be reduced, replacing log N + 1 in the formula with log(2N/t), while also reducing the number of PRG operations by a factor t.

DPF Key Generation Protocols

Up to this point, the exposition has focused on how to obtain and use pseudorandom correlation generators (PCG), abstracted in an idealized model where the short PCG seeds are sampled by a third-party trusted dealer. In this section, we give the preliminaries that will be necessary to securely set up these seeds. In particular, we present a protocol for setting up keys for distributed point functions with malicious security (allowing some leakage on the path value). Since these protocol works over any finite field, we will present it over F q for arbitrary q ∈ N.

Reactive 2-PC

In the following, we assume secure computation of simple operations over F 2 and F q , which are depicted in Functionality F 2-PC and -for the malicious setting -in Functionality F ext-2-PC in Figure 3. Note that the arithmetic addition BitAdd is nontrivial, as the parties must hold bitwise additive secret shares, but the sum itself is over Z. This "grade school addition" over bits can be implemented via a binary circuit for integer addition with log N AND gates, similar to previous (e.g., garbled circuit based [START_REF] Kolesnikov | Improved garbled circuit building blocks and applications to auctions and computing minima[END_REF]) protocols. For details on implementation and efficiency considerations we refer to Section 6.3.

Semi-honest DPF Key Generation

Recall that a distributed point function (DPF) allows to generate succinct shares of the point function

f : [0..D) → F q , f α,β (x) = β if x = α 0 else .
We give the functionality for setting up this succinct shares securely in Figure 4. We use the DPF construction of [START_REF] Boyle | Function secret sharing: Improvements and extensions[END_REF] and implement the functionality F DPF using the protocol of [START_REF] Doerner | Scaling ORAM for secure computation[END_REF] (note that the optimized DPF construction used in [START_REF] Doerner | Scaling ORAM for secure computation[END_REF] is not secure, see Remark 5.1 for details).

In the following we give an overview of the underlying DPF construction and the distributed setup protocol.

The DPF construction [START_REF] Boyle | Function secret sharing: Improvements and extensions[END_REF]: We start by outlining the underlying DPF construction.

Parameters: Security parameter 1 λ , a natural number D specifying the domain size, and a pseudorandom generator PRG : {0, 1} λ → {0, 1} 2λ+2 .

Functionality F 2-PC

The functionality operates on elements of F q for q ∈ N and bit-strings F 2 for ∈ N. Each value stored by the functionality is associated with a unique identifier that is given to all parties. Let y Fq denote the identifier for a value x ∈ F q and x F 2 denote the identifier for a bit-string

x ∈ F 2 that is stored by the functionality. Note that for stored bit-strings x F 2 we assume individual access to the i-th bit x i F 2 for all i ∈ [0.. ).

Input(P σ , x): Receive a value x ∈ F q or x ∈ F 2 or from party P σ and store x Fq or x F 2 .

Add( x Fq , y Fq ): Compute z = x + y ∈ F q and store z Fq .

Add( x F 2 , y F 2 ): (for x, y ∈ F 2 ) Compute z = x ⊕ y ∈ F 2 and store z F 2 . BitAdd( x F 2 , y F 2 ): (for x, y ∈ F 2 ) Compute z = x + y ∈ {0, 1}
+1 via arithmetic addition and store z

F +1 2 . Mult( x Fq , y Fq ): Compute z = x • y ∈ F q and store z Fq .
Output( x Fq ): Send the value x ∈ F q to all parties.

Output( x F 2

): Send the value x ∈ F 2 to all parties.

Functionality F ext-2-PC
The functionality contains all the same commands as F 2-PC , as well as the additional commands below.

In the following, x σ is always the input of party P σ .

Inv( x Fq ): Compute z = x -1 ∈ F q and store z Fq .

MixedMult(x 0 , x 1 , α F 2 ): (for x 0 , x 1 ∈ F 2 , α ∈ F 2 ) Compute z = α • (x 0 ⊕ x 1 ) ∈ F 2 . 1. If both parties are honest: Choose z 0 $ ← F 2 at random and set z 1 = z ⊕ z 0 . Output z σ to P σ for σ ∈ {0, 1}. 2. If P σ is corrupt: Wait for input z σ by P σ , set z 1-σ = z ⊕ z σ and output z 1-σ to P 1-σ . PassiveOutput(x 0 , x 1 ): (for x 0 , x 1 ∈ F 2 ) 1. If both parties are honest: Wait for input x 0 , x 1 ∈ F 2 . Output z = x 0 ⊕ x 1 ∈ F 2 to both parties.
2. If P σ is corrupt: Send x 1-σ to P σ and wait for input with domain [0..D) and range F q , where D, q ∈ N. Functionality: The functionality contains the same Input, Add, Mult and Output commands as F 2-PC , as well as the following command. DPF: On input α F 2 , and β Fq :

x σ ∈ F 2 by P σ . Send z = x 0 ⊕ x 1 ∈ F 2 to P 1-σ .
1. Sample keys (K dpf 0 , K dpf 1 ) ← DPF.Gen(1 λ , α, β).

2. For σ ∈ {0, 1} output K dpf σ to P σ . as explained in Figure 3.

Input: A "path" α ∈ [0..D) (in the following usually interpreted as a bit-string ∈ {0, 1} log D ) and a "payload" β ∈ F q .

Goal: The parties hold a compact representation of (pseudorandom) shares y 0 , y 1 ∈ F D q , such that y 0 + y 1 = (0, . . . , β, . . . , 0), where β is in the α-th position. In other words, parties P 0 , P 1 hold an additive secret sharing modulo p of the α-th unit vector scaled by payload β.

Strategy: 1. Each party P σ holds seeds s 0,0 σ , s 0,1 σ ∈ {0, 1} λ . These values define a log D-depth tree following the GGM paradigm: To get from the i-th to i + 1-st level, for all j ∈ [0..2 i ), P σ computes

s i+1,2j σ s i+1,2j+1 σ t i+1,2j σ t i+1,2j+1 σ $ ← PRG( s i,j σ ).
Ignoring the t-values for now, the seeds s 0,0 σ , s 0,1 σ can be viewed as a compact representation of a length-D vector ( s log D,0 σ , . . . , s log D,D-1 σ ).

2. In order to achieve s log D,j 0 = s log D,j 1 for all j ∈ [0..D)\{α} (i.e. shares of a scaled unit vector), the idea is to correct the nodes leaving the position defined by α. If α was known to one party (say P 0 ), this could be achieved by giving a correction word CW i := s i,α 0 α 1 ...α i 0 ⊕ s i,α 0 α 1 ...α i 1 (i.e. the node leaving the path corresponding to α in the i-th level) to party P 0 in every level. In the last level the party additionally receives CW := (s log D,α 0 -s log D,α 1 ) -1 •β, where s log D,α σ corresponds to the value s log D,α σ interpreted as a bit string. (Note that this hides β, as party P 0 as no information on any of the preceding nodes of s log D,α 1 ).

Adding CW i at position α 0 α 1 . . . α i in the i-th level and interpreting the last values in the last level of the GGM tree as F q elements, where P 1 multiplies its shares by -1 and P 0 multiplies the value at the α's position by CW, the parties indeed obtain output shares of the α-th unit vector scaled by β.

3. In the general setting, neither party has knowledge of α. This is, when the t-values come into play. The idea is as follows: For each node s i,j σ at level i, the parties will hold a value T i,j σ (derived from their t-values together with correction bits τ i,0 , τ i,1 hold by both parties) determining whether party P σ adds the correction word or not, such that (a) for children of nodes outside the path corresponding to α, either none or both of the parties add the correction word (b) for children of nodes on the path corresponding to α, exactly one of the parties adds the correction word.

As the parties do not know about the others party's T i,j σ value, α is not leaked by the correction words or bits.

Remark 5.1 (Difference compared with [START_REF] Doerner | Scaling ORAM for secure computation[END_REF]) [START_REF] Doerner | Scaling ORAM for secure computation[END_REF] actually use a modification of the above description, since they choose each bit t i,j σ as the LSB of s i,j σ , instead of as a fresh output from the PRG. We observe that unfortunately, this tweak renders their construction insecure, since the same bits are then used in computation of the correction words CW i . This has the effect of leaking the bit α i whenever LSB(

s i,α 0 ...α i-1 0 0 ⊕ s i,α 0 ...α i-1 0 1 ) = LSB( s i,α 0 ...α i-1 1 0 ⊕ s i,α 0 ...α i-1 1 1
). This occurs with probability 1/2, so on average leaks half of the bits of α, given just one of the two seeds. 7 To avoid this issue, we instead apply the setup protocol of [START_REF] Doerner | Scaling ORAM for secure computation[END_REF] to the original DPF of [START_REF] Boyle | Function secret sharing: Improvements and extensions[END_REF].

The protocol of Doerner and shelat. The setup protocol of Doerner and shelat [START_REF] Doerner | Scaling ORAM for secure computation[END_REF] is based on the observation that the correction words in the i-th level can be derived from the sums of the values of all left (resp. right) leaves in level i, if α i = 1 (resp. α i = 0). This is due to the fact that all left (resp. right) leaves that are not a child of node α| i-1 in level i -1 already agree due to previous corrections. Their protocol can be described as follows:

Input: The position α ∈ [0..D) (in bit-representation) and the payload β ∈ F q .

Setup: Each party (locally) chooses random seeds s 0,0 σ , s 0,1 σ ∈ {0, 1} λ Key generation: For each i ∈ [0..D) the parties input the sums of their right leaves and the sums of their left leaves (as well as the sums of their right t-values and their left t-values) into a secure computation. The secure computation outputs a correction word CW i (computed as the sum of either all left leaves or all right leaves, depending on the i-th bit of alpha) and correction bits τ i,0 , τ i,1 . The parties correct the nodes of the i-th level by adding CW i to the j-th word whenever T i,j σ = 1. Further, both parties derive the values T i+1,2j σ , T i+1,2j+1 σ for the next level using the correction bits. In the last level, each party additionally inputs the sum of all nodes, from which the final correction word CW can be derived.

Working Over a Ring Instead of a Field. Although we described the above protocol only over finite fields, note that it can in fact be adapted to work over Z q for any q ∈ N.

Malicious DPF Key Generation

We now turn focus to malicious adversaries. When transferring the protocol of Doerner and shelat to the malicious setting, one runs into the following problem: In order to achieve a practically efficient protocol, the evaluation of the PRG has to take place locally, i.e. outside any secure evaluation. But this would allow a malicious adversary to provide inconsistent key shares during key generation.

Previous works [BCG + 19a, YWL + 20] solve this issue at very low cost for the simpler setting of puncturable pseudorandom functions, where one party is in knowledge of the position (say P 0 ) and the other party in charge of setting up the key (say P 1 ). The idea is to introduce a consistency check that ensures that P 1 behaved consistently with respect to the input value α. As the check depends on the input value α if P 1 deviates from the protocol, party P 1 can attempt guess partial information on α. If P 1 guesses correctly, it obtains (partial) leakage on α. Otherwise, the protocol aborts. 1. If β = 0 output "β = 0" to both parties and abort.

Sample y

0 $ ← F D
q , and let y 1 ← (0, . . . , 0, β, . . . , 0) -y 0 , where β is in position α (parsed as integer).

3. Output y σ to party P σ , for σ ∈ {0, 1}

If party P σ is corrupted:

1. Allow the adversary to determine its output shares. Wait for input y σ ∈ F D q from the adversary.

2. Allow the adversary an arbitrary guess on α. Wait for input P :

F log D 2 → {0, 1}. If P (α) = 0, abort.
3. If β = 0 output "β = 0" to both parties and abort.

4. Set y 1-σ ← (0, . . . , 0, β, . . . , 0) -y σ ∈ F D q , where β is in position α (parsed as integer).

5. Output (success) to the adversary and y 1-σ to the honest party. We show how to achieve the same in the more general setting of distributed point functions. We do this using a new consistency check for verifying the DPF keys were computed correctly. This check, which is inspired by [YWL + 20], has a similar leakage profile to previous approaches for puncturable PRFs. 8 Compared with the semi-honest protocol, we need a small extra overhead, dominated by two maliciously secure 2-PC multiplications and one inversion in F q , as well as around twice as many PRG evaluations as in the semi-honest case.

In Figure 5 we outline the achieved functionality. Note that this is weaker than the functionality for securely generating keys of a distributed point function for two reasons:

• For the reason elaborated on above, it allows some leakage on the noise α. In the setting of noise generation for LPN, this leakage is tolerable for the following reason: The more the adversary attempts to guess, the higher the probability the protocol aborts, resulting in a leakage of only 1 bit on average. Intuitively, this can be accounted for by slightly increasing the noise rate.

• It gives out additive secret shares of the output (instead of the DPF keys), where the adversary is given full control over its share of the input. To make the resulting restriction to polynomial-size output explicit, we refer to the functionality as a setup functionality for a shared unit vector. Note that combined with our PCGs, this allows implementing the corruptible OLE functionality (Fig. 9) and the corruptible functionality for generating authenticated multiplication triples (Fig. 11), where the adversary is also given control over its share of the output.

Intuition for the Protocol (Fig. 6). The protocol uses the malicious 2-PC functionality F ext-2-PC (Fig. 3), and requires that α is stored in F ext-2-PC bitwise, while β is stored as an element of F q . Next, it starts by running the semi-honest setup protocol, with the difference that in the secure computation used to compute the correction words CW i , we rely on F ext-2-PC to ensure that the correct bits of α are being used. Apart from this, the secure computation stage is only semi-honest: the PassiveOutput command of F ext-2-PC allows corrupt parties to incorrectly open a shared value, while MixedMult only enforces that the bit α i is correct, and not the string it is multiplied with.

The correction words computed in this first stage correspond to a random payload β . Before switching this to β, we perform a consistency check. The parties sample (via coin-tossing) random values r 0 , . . . , r D-1 ∈ F q , and use these to compute a linear combination of the DPF outputs. The result (which is secret-shared) should equal r α • β . To check this, the parties take an additional D outputs of the DPF (by extending the depth of the tree by one), with associated random payload CW R , and take the same linear combination, scaled by (CW R ) -1 , and multiply the result with β (which has been stored in F 2-PC ). The parties then use F 2-PC to verify that these two values are equal.

The idea of the check is that the only way a corrupt party can cheat is by guessing β , which is random in a large field F q , or by guessing (a few bits of) α, which is allowed by the leakage in the functionality. If the check goes through, the parties finally correct the DPF payload to β instead of β , by outputting the relevant correction value CW L = β/β . Remark 5.2 Note that one can use the functionality F c-SUV with larger output spaces F q , by running the same functionality over F q and embedding F q vectors into that field. Alternatively, if q is already large enough for security, a slightly more efficient solution can be obtained by tweaking the protocol as follows. Choose a PRG with larger output length ({0, 1} λ ) +1 on the last level, compute a correction word CW L i for each i ∈ [ ], and check consistency for each component individually. More precisely, for each i ∈ [ ], compute S L,i σ similarly to S L σ in Fig. 6, using the additional PRG outputs, and check that β • S R -S L,i = 0 as required.

In the following, we prove that our protocol Π c-SUV (see Fig. 6) realizes the functionality F c-SUV (Fig. 5) for generating additive secret shares of a scaled unit vector with security against malicious adversaries.

Theorem 5.1 If PRG : {0, 1} λ → {0, 1} 2λ+2 is a secure PRG , then the protocol Π c-SUV (Fig. 6) implements the functionality F c-SUV (Fig. 5) with security against malicious adversaries in the (F ext-2-PC , F coin )-hybrid model.

Proof. We first consider the case that both parties are honest, before giving a simulator for the case that one party is corrupt.

Both parties are honest. We have to show that the outputs in a real execution of the protocol are indistinguishable from the outputs of the ideal functionality (i.e. y 0 $ ← F D q , y 1 ← (0, . . . , β, . . . , 0) -y 0 , where β is in position α), even to an adversary seeing all communication over the network.

Correctness. We have to prove that indeed y j 0 + y j 1 = 0 for all j = α and y α 0 + y α 1 = β. In particular, we have to show that in an honest execution the protocol does not abort. We proceed in a number of steps.

Protocol Π c-SUV (Part I) Parameters:

• Security parameter 1 λ ; output length D = 2 k ; finite field F q (where log q is a statistical security parameter)

• PRG : {0, 1} λ → {0, 1} 2λ+2 , a pseudorandom generator

• Convert Fq : {0, 1} λ → F q , maps a pseudorandom bit string into an F q element

• Functionalities F ext-2-PC (Fig. 3) and F coin (coin-tossing)

Protocol: The framed parts are run in malicious 2-PC (using commands from F ext-2-PC ).

Inputs:

• The parties holds a position α

F log D 2
and a payload β Fq stored in F ext-2-PC . We assume α is shared bitwise, so for each bit α j , for j ∈ [0.. log D), party P σ holds α j,σ with α j,0 + α j,1 = α j .

Key Generation Phase:

1. For σ ∈ {0, 1} party P σ chooses a PRG seed s 0,0 σ ∈ {0, 1} λ and computes

s 1,0 σ s 1,1 σ t 1,0 σ t 1,1 σ := PRG( s 0,0 σ ). Party P σ locally sets T 1,0 σ := T 1,1 σ := σ, and z 1,0 σ := s 1,0 σ , z 1,1 σ := s 1,1 σ , u 1,0 σ := t 1,0 σ , u 1,1 σ := t 1,1 σ .
2. For i = 1 to log D:

• For b ∈ {0, 1}: τ i,b ← PassiveOutput(u i,b 0 ⊕ α i,0 , u i,b 1 ⊕ α i,1 ⊕ 1 ⊕ b) • ( y i 0 , y i 1 ) ← MixedMult( z i,0 0 ⊕ z i,1 0 , z i,0 1 ⊕ z i,1 1 , α i F 2 ) // = α i • ( z i,0 + z i,1
)

• CW i ← PassiveOutput( y 0 ⊕ z i,1 0 , y i 1 ⊕ z i,1 1 ) // CW i = z i,1-α i
• For σ ∈ {0, 1}, j ∈ [0..2 i ), party P σ computes:

-The next level of the GGM tree:

s i+1,2j σ s i+1,2j+1 σ t i+1,2j σ t i+1,2j+1 σ := PRG( s i,j σ ⊕ T i,j σ • CW i )
-If i < log D, the sums of the left/right leaves and left/right correction bits, for b ∈ {0, 1}:

z i+1,b σ := 2 i -1 j=0 s i+1,2j+b σ , u i+1,b σ := 2 i -1 j=0 t i+1,2j+b σ ,
-If i < log D, the next level of choice bits:

T i+1,2j σ := t i+1,2j σ ⊕ T i,j σ • τ i,Parity(j) , T i+1,2j+1 σ := t i+1,2j+1
σ ⊕ T i,j σ • τ i,Parity(j) 3. Convert the output shares to F q : P σ computes:

z L σ := D-1 j=0 s j,L σ , z R σ := D-1 j=0 s j,R σ where s j,L σ = Convert Fq ( s log D+1,2j σ
) and s j,R σ = Convert Fq ( s log D+1,2j+1 σ

). (to be continued) 4. Correct the offset of the left leaves to β and the offset of the right leaves to 0:

• For σ ∈ {0, 1}: z L σ Fq ← Input(P σ , z L σ ), z R σ Fq ← Input(P σ , z R σ ) • β p ← z L 0 Fq -z L 1 Fq • CW L Fq ← β -1 Fq • β Fq , CW R Fq ← z R 0 Fq -z R 1 Fq • Output CW R ← Output( CW R Fq ) to both parties.
Verification Phase: 6. To verify that the sender behaved consistently and the output unit vector has the correct payload β, the parties proceed as follows:

• The parties call F coin to obtain public random values r 0 , . . . , r D-1 ∈ F q .

• Each P σ computes

S L σ = (-1) σ • D-1 j=0 r j • s j,L σ , S R σ = (-1) σ • (CW R ) -1 • D-1 j=0 r j • s j,R σ 7.
The parties check if the check values where computed correctly:

• For σ ∈ {0, 1}:

S L σ Fq ← Input(P σ , S L σ ), S R σ Fq ← Input(P σ , S R σ ) • Compute Z Fq = β Fq • ( S R 0 Fq + S R 1 Fq ) -S L 0 Fq -S L 1 Fq .
• If Z ← Output( Z Fq ) does not equal 0, abort.

Output Phase:

1. Output CW L ← Output( CW L Fq ) to both parties. If CW L = 0, abort. 8. Finally, if all checks passed, party P σ outputs y σ = (y 0 σ , . . . , y D σ -1), where Claim 5.3 If the parties follow the protocol description honestly, then all i ∈ [0.. log D) and j ∈ [0..2 i )\{α| i } we have s i,j 0 ⊕T i,j 0 •CW i = s i,j 1 ⊕T i,j 1 •CW i . Further, for the correction bits we have

y j σ := (-1) σ • s j,L σ • CW L .
T i+1,2j+b 0 = T i+1,2j+b 1 for all j ∈ [0..2 i ) \ {α| i }, b ∈ {0, 1}, as well as T i+1,2α| i +b 0 = T i+1,2α| i +b 1 ⊕ 1 for b ∈ {0, 1}.
We omit the proof of this claim, which closely follows from [START_REF] Boyle | Function secret sharing: Improvements and extensions[END_REF].

Claim 5.4 After an honest execution of the protocol party P σ holds output (y 0 σ , . . . , y D-1 σ ), such that y j 0 + y j 1 = 0 for all j = α, and y α 0 + y α 1 = β.

Proof. For all j = α, by Claim 5.3 we have

s log D-1,j σ ⊕ T log D-1,j σ • CW D-1 = s log D-1,j 1-σ ⊕ T log D-1,j 1-σ • CW D-1 ,
and thus s log D,2j

0 = s log D,2j
1 . This implies s j,L 0 = s j,L 1 , and thus

y j 0 + y j 1 = s j 0 , L • CW L -s j 1 , L • CW L = 0
Further, we have

z L 0 -z L 1 = D-1 j=0 s j,L 0 - D-1 j=1 s j,L 1 = s α,L 0 -s α,L 1 and thus y α 0 + y α 1 = s α,L 0 • CW L -s α,L 1 • CW L = (s α,L 0 -s α,L 1 ) • (s α,L 0 -s α,L 1 ) -1 • β = β. Claim 5.5 If β = 0,
then in an honest execution the protocol does not abort with overwhelming probability.

Proof. First, note that β = 0 implies that CW L = 0. Further, by the same reasoning as above, 5.3 yields s log D,2j+1 0 = s log D,2j+1 1 , and thus s j,R

0 = s j,R 1 , for all j ∈ [0..D)\{α}. This implies CW R = z R 0 -z R 1 = s α,R 0 -s α,R 1 . This implies S R 0 + S R 1 = (CW R ) -1 • D-1 j=0 r j • (s j,R 0 -s j,R 1 ) = (s α,R 0 -s α,R 1 ) -1 • r α • (s α,R 0 -s α,R 1 ) = r α . Further, we have S L 0 + S L 1 = D-1 j=0 r j • (s j,L 0 -s j,L 1 ) = r α • (s α,L 0 -s α,L 1 ) = r α • β which yields Z = 0 as required.
Security. It is left to show that y σ is distributed uniformly for each σ ∈ {0, 1} individually, even given access to all communication between P 0 and P 1 . As an honest execution of our protocol is very similar to an execution of the original protocol of Doerner and shelat (instantiated with the DPF of [START_REF] Boyle | Function secret sharing: Improvements and extensions[END_REF]), in the following we only give a proof sketch. Note that even conditioned on all correction words and correction bits revealed during the protocol, i.e. CW i , τ i,0 , τ i,1 for all i ∈ [0..D) and CW R , it holds that y σ is distributed uniformly at random, because each of the correction values is blinded by an output of the PRG, where the input is known only to P 1-σ (and in particular not revealed during the protocol execution). Further, if β = 0, the same holds true conditioned on CW L . Finally, note that the only value that an adversary sees in the verification step of an honest execution is a 0, therefore security follows.

Party P σ is corrupted. We now proceed to the case that one party is corrupted. We start by giving an intuition for the proof. In the simulation, all the correction values τ i,b , CW i , and the right correction word CW R , will be simulated using random values. In the consistency check, the simulator needs to extract a guess on α ∈ [D] made by the potentially cheating adversary. Since the simulator does not know α, it will define, for each χ ∈ [D], a simulated "honest view" that is consistent with α = χ and the adversary's view so far. Using the S L σ , S R σ values provided by the adversary, the simulator then defines the predicate P (χ), which is 1 if the adversary's behaviour is consistent with the simulated honest view based on χ. It queries this guess to the functionality, if the guess is successful, the consistency check passes. The simulator can then use a consistent value of χ to extract a valid output vector that is known by the adversary. In the proof, we show that due to the random linear combination, every χ that satisfies P (χ) = 1 will lead to the same extracted output, so the simulation is consistent with the real protocol.

The simulator proceeds as follows.

Key generation phase:

• For i ∈ [1.. log D] :
-The simulator sends a random τ i,b 1-σ ∈ {0, 1} to P σ , and waits to receive

τ i,b σ , then defines τ i,b = τ i,b 0 ⊕ τ i,b 1 .
-Next, the simulator awaits input v i σ ∈ {0, 1} λ to MixedMult from the adversary, as well as the adversary to input P σ 's output share y i σ ∈ {0, 1} λ . -Next, to simulate PassiveOutput the simulator sends a random CW i 1-σ ∈ {0, 1} λ to the adversary, then waits to receive CW i σ ∈ {0, 1} λ , and sets

CW i := CW i 0 ⊕ CW i 1 .
• Now, the simulator awaits input z L σ , z R σ ∈ F q from the adversary and returns a random CW R ← F q . It also samples a random CW L ← F q .

• Finally, for each χ ∈ [0..D) (corresponding to all possible values of α) the simulator computes the output of the honest party P 1-σ that is compatible with the correction values and correction bits as sampled above.

-The simulator sets T 1,1-χ 1 1-σ,χ := 1 -σ.

-For i ∈ [1.. log D]: * For b ∈ {0, 1}, the simulator sets u i,b 1-σ,χ := τ i,b 1-σ ⊕ χ i ⊕ α i,σ ⊕ (1 ⊕ σ) • (1 ⊕ b). * The simulator sets z i,1-χ i 1-σ,χ := CW i 1-σ ⊕ y i σ ⊕ χ i • v i σ .
-For the first level, the simulator sets

s 1,1-χ 1 1-σ,χ := z 1,1-χ 1 1-σ,χ . -For i ∈ [1.. log D] : * For j ∈ [0..2 i
), the simulator computes:

• The next level of the GGM tree:

s i+1,2j 1-σ,χ s i+1,2j+1 1-σ,χ t i+1,2j 1-σ,χ t i+1,2j+1 1-σ,χ := PRG( s i,j 1-σ,χ ⊕ T i,j 1-σ,χ • CW i ) if j = χ i . • Next, if i < log D the simulator uses the pre-computed values z i+1,1-χ i+1 1-σ,χ , u i+1,0 1-σ,χ , u i+1,1
1-σ,χ to compute the missing part of the GGM tree -except for the seed value on the χ-path, s i+1,χ| i +χ i+1 1-σ,χ (where by χ| i = i-1 j=0 χ j 2 j we denote the i-bit prefix of χ parsed as a natural number), since we do not need this value to continue. Instead, the already chosen correction word of the next level (together with the other leave values) will implicitly define it.

s i+1,2χ| i +1-χ i+1 1-σ,χ := z i+1,1-χ i+1 1-σ,χ ⊕ 2 i -1 j=0,j =χ| i s i+1,2j+1-χ i+1 1-σ,χ , as well as t i+1,2χ| i +b 1-σ,χ := u i+1,b 1-σ,χ ⊕ 2 i -1 j=0,j =χ| i t i+1,2j+b 1-σ,χ .
• Further, if i < log D, the simulator computes the next level of choice bits:

T i+1,2j 1-σ,χ := t i+1,2j 1-σ,χ ⊕T i,j 1-σ,χ •τ i,Parity(j) , T i+1,2j+1
1-σ,χ

:= t i+1,2j+1 1-σ,χ ⊕T i,j 1-σ,χ •τ i,Parity(j)
• Note that the simulator cannot compute the honest party's output shares at position χ, since this would require knowledge of β. However, the simulator can compute the output share of the dishonest party P σ , such that it is consistent with the shares of

P 1-σ (conditioned on α = χ). s χ,L σ,χ := z L σ - D-1 j=0,j =χ s j,L σ,χ , s χ,R σ,χ := z R σ - D-1 j=0,j =χ s j,R σ,χ
where s j,L σ,χ = Convert Fq ( s log D+1,2j

1-σ,χ
) and s j,R σ,χ = Convert Fq ( s log D+1,2j+1

1-σ,χ

) for j = χ.

Verification phase:

• To simulate F coin , the simulator sends random r 0 , . . . , r D-1 ∈ F q .

• Further, the simulator receives the "real" inputs S L σ , S R σ by the adversary. • Next, for each χ ∈ [0..D) the simulator computes

S L σ,χ = (-1) σ • D-1 j=0 r j • s j,L σ,χ , S R σ,χ = (-1) σ • (CW R ) -1 • D-1 j=0 r j • s j,R σ,χ
• For all j ∈ [0..D) the simulator further computes the (potential) output as

y j σ,χ := (-1) σ • s j σ,χ , L • CW L .
• To extract the adversary's potential guess on α, the simulator defines the predicate

P : F log D 2 :→ {0, 1}, P (χ) = 1 ⇔ S L σ,χ = S L σ ∧ S R σ,χ = S R
σ , picks a χ with P (χ ) = 1 and inputs y σ,χ = (y 0 σ,χ , . . . , y D-1 σ,χ ) and P to the functionality. If such a χ does not exist, the simulator sends y σ = 0 and P = 0 to the functionality.

-If the functionality aborts, then the simulator receives α and sends to the adversary a random Z ∈ F * q and aborts. -Else, the simulator outputs Z = 0 to the adversary. It also learns from the functionality whether or not β = 0.

Output phase. Finally, we simulate the opening of the correction word CW L . If β = 0, the simulator outputs 0 and aborts. Else, it sends CW L as sampled before.

It is left to show that the simulation is indistinguishable from a real protocol execution. To this end, we first switch the real protocol distribution to a randomized distribution (Lemma 5.6), and then show that the simulation is statistically indistinguishable from the randomized distribution (Lemma 5.7).

Hybrid 1: Real behaviour of the honest party: We start by describing the honest party's behavior in a real execution, when the protocol is run with input α.

Key generation phase: • Party P 1-σ chooses a PRG seed s 0,0 1-σ ∈ {0, 1} λ and computes s 1,0 1-σ s 1,1 1-σ t 1,0 1-σ t 1,1 1-σ := PRG( s 0,0 1-σ ). Party P 1-σ locally sets T 1,0 1-σ := T 1,1 1-σ := 1 -σ, and

z 1,0 1-σ := s 1,0 1-σ , z 1,1 1-σ := s 1,1 1-σ , u 1,0 1-σ := t 1,0 1-σ , u 1,1 1-σ := t 1,1 1-σ . • For i = [1.. log D] : -For b ∈ {0, 1}, P 1-σ sends τ i,b 1-σ := u i,b 1-σ ⊕ α i,1-σ ⊕ (1 ⊕ σ) • (1 ⊕ b) to PassiveOutput and receives τ i,b . -P 1-σ sends z i,0 1-σ ⊕ z i,1
1-σ to MixedMult and receives y i 1-σ . -P 1-σ sends y i 1-σ ⊕ z i,1 1-σ to PassiveOutput and receives CW i . -For j ∈ [0..2 i ), party P 1-σ computes:

* The next level of the GGM tree:

s i+1,2j 1-σ s i+1,2j+1 1-σ t i+1,2j 1-σ t i+1,2j+1 1-σ := PRG( s i,j 1-σ ⊕ T i,j 1-σ • CW i ) *
The sums of the left/right leaves and left/right correction bits, for b ∈ {0, 1}:

z i+1,b 1-σ := 2 i -1 j=0 s i+1,2j+b 1-σ , u i+1,b 1-σ := 2 i -1 j=0 t i+1,2j+b 1-σ
, * The next level of choice bits:

T i+1,2j 1-σ := t i+1,2j 1-σ ⊕T i,j 1-σ •τ i,Parity(j) , T i+1,2j+1 1-σ := t i+1,2j+1 1-σ ⊕T i,j 1-σ •τ i,Parity(j)
• Convert the output shares to F q : P 1-σ computes:

z L 1-σ := D-1 j=0 s j,L 1-σ , z R 1-σ := D-1 j=0 s j,R 1-σ
where s j,L 1-σ = Convert Fq ( s log D+1,2j

1-σ

) and s j,R 1-σ = Convert Fq ( s log D+1,2j+1

1-σ

).

• Correct the offset of the left leaves to β and the offset of the right leaves to 0:

-Party P 1-σ sends z L 1-σ and z R 1-σ to Input. -Party P 1-σ receives CW R .

Verification Phase: • The parties call F coin to obtain r 0 , . . . , r D-1 ∈ F q .

• Party P 1-σ computes

S L 1-σ = (-1) 1-σ • D-1 j=0 r j • s j,L 1-σ , S R 1-σ = (-1) 1-σ • (CW R ) -1 • D-1 j=0 r j • s j,R 1-σ • Party P 1-σ inputs S L 1-σ , S R 1-σ to Input. It receives Z. If Z = 0, party P 1-σ aborts.
Output Phase: • Party P 1-σ receives CW L . If CW L = 0, the party aborts.

• Finally, if all checks passed, party P 1-σ outputs y 1-σ = (y 0 1-σ , . . . , y D 1-σ -1), where

y j 1-σ := (-1) 1-σ • s j,L 1-σ • CW L .
Hybrid 2: Randomized behaviour of the honest party. We now describe the honest party's behaviour, where we replace calls to PRG by random values whenever the seed is not known by the adversarial party P σ . Changes to the first hybrid are framed .

Key generation phase:

• Party P 1-σ chooses s 1,0 1-σ s 1,1 1-σ t 1,0 1-σ t 1,1 1-σ $ ← {0, 1} 2λ+2 at random. Party P 1-σ locally sets T 1,0 1-σ := T 1,1 1-σ := 1 -σ, and z 1,0 1-σ := s 1,0 1-σ , z 1,1 1-σ := s 1,1 1-σ , u 1,0 1-σ := t 1,0 1-σ , u 1,1 1-σ := t 1,1 1-σ . • For i = [1.. log D] : -For b ∈ {0, 1}, P 1-σ sends τ i,b 1-σ := u i,b 1-σ ⊕ α i,1-σ ⊕ (1 ⊕ σ) • (1 ⊕ b) to PassiveOutput and receives τ i,b . -P 1-σ sends z i,0 1-σ ⊕ z i,1
1-σ to MixedMult and receives y i 1-σ . -P 1-σ sends y i 1-σ ⊕ z i,1 1-σ to PassiveOutput and receives CW i . -For j ∈ [0..2 i ), party P 1-σ computes:

* The next level of the GGM tree:

s i+1,2j 1-σ s i+1,2j+1 1-σ t i+1,2j 1-σ t i+1,2j+1 1-σ    $ ← {0, 1} 2λ+2 if j = α| i := PRG( s i,j 1-σ ⊕ T i,j 1-σ • CW i ) else *
The sums of the left/right leaves and left/right correction bits, for b ∈ {0, 1}:

z i+1,b 1-σ := 2 i -1 j=0 s i+1,2j+b 1-σ , u i+1,b 1-σ := 2 i -1 j=0 t i+1,2j+b 1-σ
, * The next level of choice bits:

T i+1,2j 1-σ := t i+1,2j 1-σ ⊕T i,j 1-σ •τ i,Parity(j) , T i+1,2j+1 1-σ := t i+1,2j+1 1-σ ⊕T i,j 1-σ •τ i,Parity(j)
• Convert the output shares to F q : P 1-σ computes:

z L 1-σ := D-1 j=0 s j,L 1-σ , z R 1-σ := D-1 j=0 s j,R 1-σ where s j,L 1-σ = Convert Fq ( s log D+1,2j 1-σ
) and s j,R 1-σ = Convert Fq ( s log D+1,2j+1

1-σ

). • Correct the offset of the left leaves to β and the offset of the right leaves to 0:

-Party P 1-σ sends z L 1-σ and z R 1-σ to Input. -Party P 1-σ receives CW R .

Verification Phase: • The parties call F coin to obtain r 0 , . . . , r D-1 ∈ F q .

• Party P 1-σ computes

S L 1-σ = (-1) 1-σ • D-1 j=0 r j • s j,L 1-σ , S R 1-σ = (-1) 1-σ • (CW R ) -1 • D-1 j=0 r j • s j,R 1-σ • Party P 1-σ inputs S L 1-σ , S R 1-σ to Input. It receives Z. If Z = 0, party P 1-σ aborts.
Output Phase: • Party P 1-σ receives CW L . If CW L = 0, the party aborts.

• Finally, if all checks passed, party P 1-σ outputs y 1-σ = (y 0 1-σ , . . . , y D 1-σ -1), where y j 1-σ := (-1)

1-σ • s j,L 1-σ • CW L .
We omit the proof of the following lemma here and refer to [START_REF] Boyle | Function secret sharing: Improvements and extensions[END_REF], since the changes only concern the underlying DPF protocol.

Lemma 5.6 If PRG : {0, 1} λ → {0, 1} 2λ+2 is a secure PRG, then the real behaviour and the randomized behaviour of P 1-σ are indistinguishable to an adversary controlling P σ . Lemma 5.7 Assume q = q(λ) = λ ω(1) . Then, the distribution generated by the simulator is statistically indistinguishable from the randomized protocol execution as described in Hybrid 2.

Proof. Assume to be given the real α ∈ [0..D), β ∈ F q . First, note that we can assume that for CW L as sampled by the simulator it holds that CW L = 0, since this holds except with probability 1/q. Further, we assume that for β as generated in the randomized protocol execution, it holds β = 0, which is also true except with probability 1/q.

We begin the proof by showing that the values s log D+1,2j

1-σ,α and s log D+1,2j+1

1-σ,α

for j = α are perfectly indistinguishable from those generated in a real protocol execution with randomized behaviour of P 1-σ .

• First, we have

T 1,1-α 1 1-σ,α = 1 = T 1,1-α 1-σ .
• Next, recall that for b ∈ {0, 1} the simulator sets

u 1,b 1-σ,α := τ 1,b 1-σ ⊕α 1 ⊕α 1,σ ⊕(1⊕σ)•(1⊕b), where τ 1,b
1-σ is chosen uniformly at random from {0, 1}. This is equivalent to choosing u 1,b 1-σ uniformly at random and setting

τ i,b 1-σ := u i,b 1-σ ⊕ α 1,1-σ ⊕ (1 ⊕ σ) • (1 ⊕ b),
as done in the randomized protocol execution.

• Further, recall that the simulator sets

z 1,1-α i 1-σ,α := CW 1 1-σ ⊕ y 1 σ ⊕ α 1 • v 1 σ ,
where v 1 σ ∈ {0, 1} λ is the adversary's input to MixedMult and y 1 σ ∈ {0, 1} λ is the adversary's output share for P σ . Note that in a randomized execution of the protocol, it holds

CW 1 1-σ = y 1 1-σ ⊕ z 1,1 1-σ , where y 1 σ ⊕ y 1 1-σ = α 1 • ( v 1 σ ⊕ z 1,0 1-σ ⊕ z 1,1 1-σ ). This yields CW 1 1-σ = y 1 σ ⊕ α 1 • v 1 σ ⊕ z 1,1-α 1 1-σ , where z 1,1-α 1 1-σ
is sampled uniformly at random. Thus, as above we obtain that the simulation is perfectly indistinguishable from the randomized protocol execution.

• For i ∈ [1.. log D], observe that again sampling CW i+1 , τ i+1,0 , τ i+1,1 (and thus z i+1,1-α i 1-σ,α and u i+1,b 1-σ,α ) and then defining the missing s

i+1,2α| i +1-α i+1 1-σ,α , t i+1,2α| i 1-σ,α , t i+1,2α| i +1 1-σ,α
is indistinguishable to the randomized protocol execution, where P 1-σ proceeds vice versa.

With the above considerations, we obtain that s log D+1,2j 1-σ,α and s log D+1,2j+1 1-σ,α for j = α are indistinguishable from those generated in a randomized protocol execution as required.

Next, we compute the values s α,L 1-σ , s α,R 1-σ , as would be computed in a randomized protocol execution (conditioned on β = 0), and show that the simulator outputs Z = 0 if and only if the randomized execution outputs Z = 0, except with negligible probability (corresponding to the event that the adversary successfully guessed β ).

• Recall that z L σ , z R σ are the values sent to Input by the adversary. In a randomized protocol execution we would have

(-1) σ • z L σ + (-1) 1-σ • z L 1-σ = β ,
and thus

z L 1-σ = (-1) 1-σ • β + z L σ , as well as z R 1-σ = (-1) 1-σ • CW R + z R σ .
This yields

s α,L 1-σ = z L 1-σ - D-1 j=0,j =α s j,L 1-σ , s α,R 1-σ = z R 1-σ - D-1 j=0,j =α s j,R 1-σ where s j,L 1-σ = Convert Fq ( s log D+1,2j 1-σ
) and s j,R 1-σ = Convert Fq ( s log D+1,2j+1 1-σ

) for j = α.

• Let now S L 1-σ , S R 1-σ be the values as computed by the honest party in a randomized protocol execution, and S L σ,α , S R σ,α the values computed by the simulator. Then, we have

S L 1-σ + S L σ,α = (-1) 1-σ • r α • s α,L 1-σ + (-1) σ • r α • s α,L σ,α = (-1) 1-σ • r α • z L 1-σ + (-1) σ • r α • z L σ = (-1) 1-σ • r α • ((-1) 1-σ • β + z L σ ) + (-1) σ • r α • z L σ = r α • β and S R 1-σ + S R σ,α = (-1) 1-σ • (CW R ) -1 • r α • s α,R 1-σ + (-1) σ • (CW R ) -1 • r α • s α,R σ,α = r α .
We thus have that the randomized protocol execution outputs Z = 0 if and only if S L σ = S L σ,α and S R σ = S σ,α , unless the adversary successfully guessed β . Since β is distributed perfectly uniformly at random from the adversary's point of view in the randomized protocol execution at this point (since it didn't yet learn CW L ), this only happens with probability 1/q. Further, if the simulator aborts and the adversary did not successfully guess β , it perfectly simulates the distribution of Z, since again β is distributed uniformly at random. It is left to show that the output of the honest party induced by the simulation is indistinguishable from the output of the honest party in the randomized protocol execution. To that end, we have to show that 1. y σ,α + y 1-σ = (0, . . . , 0, β, . . . , 0), where y σ,α is as computed by the simulator and y 1-σ is the value computed in the randomized protocol execution, and 2. y σ,χ * = y σ,α for all χ * with P (χ ) = 1.

This can be proven as follows.

1. By the above considerations we have

y j σ,α + y j 1-σ = (-1) σ • s j,L σ,α • CW L + (-1) 1-σ • s j,L 1-σ • CW L =
0 for all j = α. Further, we have

y α σ,α + y α 1-σ = (-1) σ • s α,L σ,α • CW L + (-1) 1-σ • s α,L 1-σ • CW L = (-1) σ • z L σ • CW L + (-1) 1-σ • z L 1-σ • CW L = β • CW L = β,
which yields the required.

2. Since r 0 , . . . , r D-1 are sampled at random over F q , independently of the rest of the protocol execution, we have that if S L 1-σ,χ = S L 1-σ,α and S L 1-σ,χ = S L 1-σ,α , then s j,L σ,α = s j,L σ,χ for all j ∈ [0..D), except with negligible probability. This concludes the proof. 1. Sample (k 0 , k 1 ) ← PCG OLE .Gen(1 λ ).

2. Output k σ to party P σ , for σ ∈ {0, 1}

PCG Setup Protocols

In this section, we present the complete secure two-party setup protocols for our PCGs based on module-LPN, using the protocols from the previous section as building blocks. In Section 6.1, we show how to securely realize (against a semi-honest adversary) the randomized functionality F OLE-Setup that executes the seed generation for our PCG construction PCG OLE from Section 4, and outputs the corresponding PCG seeds to each party. This can in turn be used to realize a functionality for the secure generation of OLE correlations, by having the parties simply expand their received PCG seeds locally.

For the malicious case, we do not directly realize the PCG seed generation functionality, which would be much more challenging. Instead, we realize the random OLE generation functionality F mal-OLE , in which a corrupt adversary can choose his output (x σ , z σ ) ∈ R 2 p and the honest party receives a random consistent value (x 1-σ , z 1-σ ), i.e. for which z 0 + z 1 = x 0 • x 1 (or the parties receive a random sample from the correlation given honest behavior; see Figure 9 for full description). As discussed in [BCG + 19b], such a protocol can directly serve as a substitute for ideal OLE correlations in a wide range of higher-level applications, already proven to remain secure given this functionality. More precisely, in Section 5.3, we address both the secure generation of OLEs and authenticated multiplication triples in the presence of active adversaries, securely realizing the functionality F mal-triple at little extra cost.

Finally, in Section 6.3 we analyze the efficiency of our protocols. For concrete numbers, we refer to Table 3 in Section 9.2.

Semi-Honest Distributed Setup for OLE

We present a protocol for securely executing the seed-generation functionality F OLE-Setup (Figure 7) with respect to our PCG construction PCG OLE from Section 4. Recall that in the PCG OLE .Gen procedure (see Figure 1), each party receives a succinct description

(A i σ , b i σ ) i∈[0.
.c) of t-sparse "noise vectors" e 0 σ , . . . , e c-1 σ each of length N , as well as a collection of (ct) 2 distributed point function (DPF) keys as a compact representation of all possible products e i 0 • e j 1 . Note that the protocols works over the prime field F p , rather than an extension field F q (as in F DPF ). This is because the PCGs we use need to run over R p for a prime p, to be useful for the case where R p fully splits into linear factors (cf. Section 3.2). Theorem 6.1 The protocol Π OLE-Setup (Fig. 8) securely realizes the OLE PCG seed functionality F OLE-Setup (Fig. 7) with security against semi-honest adversaries in the (F 2-PC , F DPF )-hybrid model.

Proof. Observe that the protocol Π OLE-Setup is directly a secure evaluation of the computation steps of F OLE-Setup (see description of PCG OLE .Gen as given in Figure 1 within Section 4), with the exception that the FSS key generation for the sum of point functions SPFSS.Gen(1 λ , A i 0 Protocol Π OLE-Setup Parameters: Security parameter 1 λ , natural number N = 2 k , prime p, distributed point function DPF = (DPF.Gen, DPF.Eval) with domain [0..2N ) and range F p . Further, we assume access to the functionalities F 2-PC (Fig. 3) and F DPF (Fig. 4). Protocol:

1. For σ ∈ {0, 1}, i ∈ [0..c), party P σ samples random vectors A i σ ← [0..N ) t (where each entry of A i σ is viewed as a length-log N bit-string) and b i σ ← (F * p ) t . Note that as outlined in Figure 1, each pair A i σ , b i σ defines a t-sparse polynomial e i σ ∈ R p .

2. For σ ∈ {0, 1}, i ∈ [0..c) and k ∈ [0..t):

//P σ inputs the k-th non-zero position and corresponding payload of e i σ .

A i σ [k] F 2 ← Input(P σ , A i σ [k]) and b i σ [k] p ← Input(P σ , b i σ [k])
3. For every i, j ∈ [0..c) and k, l ∈ [0..t) (in parallel) the parties do the following:

(a) α i,j k,l F +1 2 ← BitAdd( A i 0 [k] F 2 , A j 1 [l] F 2 ) //Compute the k + tl-th position of e i 0 • e j 1 . (b) β i,j k,l p ← Mult( b i 0 [k] p , b j 1 [l] p ) //Compute the k + tl-th payload of e i 0 • e j 1 . (c) For each i, j ∈ [0..c) and k, l ∈ [0..t), call F DPF with domain size [0..2N ) on input α i,j k,l F +1 2
and β i,j k,l p , and let K i,j σ,k,l denote the output to party P σ . //Compute compressed additive secret shares of e i 0 • e j 1 . A j 1 , b i 0 ⊗ b j 1 ) is instantiated directly by the DPF key generation for every individual nonzero component. As discussed in Section 2.2, this is a valid instantiation of SPFSS, and hence the claim holds.

Party

P σ outputs k σ = (K i,j σ,k,l ) i,j∈[0..c),k,l∈[0..t) , (A i σ , b i σ ) i∈[0..c) .

PCG Setup Protocols with Malicious Security

Module-LPN with static leakage. The protocols in this section rely on a stronger variant of module-LPN, where the adversary is allowed to query (on average) one bit of information on the secret error vectors. We need to allow this, because of the leakage in the functionality F c-SUV used to generate DPF keys with malicious security. Note that this style of assumption with leakage is very similar to the assumption of standard LPN with static leakage as used in [HOSS18a, BCG + 19a]. Definition 6.2 (Module-LPN with static leakage) Let R p = Z p [X]/F (X) for some prime p and degree-N polynomial F (X) ∈ Z[X], and let c, t ∈ N with c ≥ 2. Let HW t be the distribution over R p that is obtained via sampling t noise positions A ← [0..N ) t as well as t payloads b ← Z t p uniformly at random, and outputting e(X)

:= t-1 j=0 b[j] • X A[j]
. For b ∈ {0, 1} let G b (λ) be the following game:

• Let e 0 , . . . , e c-1 ← HW t and let A 0 , . . . , A c-1 ∈ [0..N ) t be the corresponding positions of non-zero coefficients.

• Allow the adversary arbitrary guesses on the noise positions before seeing the module-LPN sample. The adversary A can make an arbitrary number of (adaptive) queries, each consisting of indices i ∈ [0..c), k ∈ [0..c) and a predicate P : [0..N ) → {0, 1}.

For each query, if P (A i [k]) = 0 then abort, otherwise, send (success) to the adversary and continue.

• Set u 0 = a, e mod F (X), where e = (e 0 , . . . , e c-1 ) and draw u 1 ← R p at random.

• Return u b to the adversary.

The R c -LPN p,t problem with static leakage for a ∈ R c p is hard if for any PPT adversary A, it holds that

Pr[A G 0 (λ) = 1] -Pr[A G 1 (λ) = 1] ≤ negl(λ)
where the probabilities are taken over e 0 , . . . , e c-1 ← HW t and the randomness of A.

In the above, if the adversary was restricted to querying predicates that either take 1 on all values or 0 on at least half of the values (in other words: if the adversary attempts to guess some noise coordinate, the protocol will abort with probability at least 1/2), then we can reduce the ring LPN with static leakage and noise parameter t + κ to our basic ring LPN assumption with noise parameter t. The idea is that the adversary can attempt a guess on at most κ noise coordinates, where κ is a statistical security parameter, as otherwise the protocol will abort with probability > 1 -2 -κ . This observation would allow to reduce security of a slight tweak of the protocol Π mal-OLE (Figure 10), where our protocol Π c-SUV is used to generate random instances of scaled unit vectors (which are derandomized subsequently), to the standard module-LPN assumption. This is due to the fact that if α is random from the point of the view of the adversary, one can show that in the protocol Π c-SUV an adversary actually can only give a wildcard guess on α, i.e. guess a subset of the bits, which corresponds to giving a predicate which takes 0 on at least half of the inputs.

This said, we want to stress that the described reduction is very loose in the sense that even if the adversary only attempts to guess a single bit on the noise position, the reduction "gives up" the correspoding noise position completely. Indeed, for our concrete protocol, we conjecture that it's not necessary to increase the noise rate in the presence of this limited leakage. For a more detailed discussion regarding attacks on ring LPN with static leakage, see Section 8.6.

Distributed generation of OLEs in the malicious setting. Building on the previous protocols, we now present our PCG protocol for generating OLE correlations with distributed setup (Fig. 10) and show that it securely implements the corruptible OLE functionality (Fig. 9) with security against malicious adversaries. Theorem 6.3 Let R p = Z p [X]/F (X) for some prime p and degree-N polynomial F (X) ∈ Z[X], and let c, t ∈ N. If the R c -LPN p,t problem with static leakage is hard, then the protocol Π mal-OLE (Fig. 10) implements the functionality F mal-OLE (Fig. 9) with security against malicious adversaries in the F 2-PC , F c-SUV -hybrid model.

Proof. We start with considering the case that both parties are honest.

Both parties are honest. Note that all communication of the parties is via ideal functionalities, so we only need to prove that the final output of a real protocol execution is indistinguishable from the output of the ideal functionality.

For

σ ∈ {0, 1}, let e i σ (X) = t-1 k=0 b i σ [k] • X A i σ [k] ∈ R p be the noise polynomial defined by A i σ and b i σ . Then, e i 0 • e j 1 is the polynomial with coefficient b i 0 [k] • b j 1 [l] at position A i 0 [k] + A j 1 [l] for all
Functionality F mal-OLE Parameters: Security parameter 1 λ , modulus p, and the ring R p = Z p [X]/F (X), where F (X) has degree N .

Functionality:

If both parties are honest:

1. Sample x 0 , x 1 ← R p . 2. Sample z 0 $ ← R p , and let z 1 ← x 0 • x 1 -z 0 .
3. Output (x σ , z σ ) to party P σ , for σ ∈ {0, 1}

If party P σ is corrupted:

1. Wait for input (x σ , z σ ) ∈ R 2 p from the adversary.

Sample x

1-σ ← R p and set z 1-σ ← x 0 • x 1 -z σ .
3. Output (x 1-σ , z 1-σ ) to the honest party.

t).

Thus, by the properties of F c-SUV , it holds g 0,i+cj + g 1,i+cj = e i 0 • e j 1 , and therefore x 0 • x 1 = z 0 + z 1 as required.

Finally, R c -LPN p,t implies the indistinguishability of (x 0 , x 1 ), (z 0 , z 1 ) from an OLE triple generated at random similarly to the proof of Theorem 4.1.

Party P σ is corrupted. For the notation in the following we assume σ = 1, the case σ = 0 is obtained by switching (i, k) with (j, l). The simulator proceeds as follows. For j ∈ [0..c) and l ∈ [0..t) it waits for input A j σ , . . . , A j σ ∈ [0..N ) t and b j σ ∈ Z t p of the adversary. Otherwise, the simulator sets e j σ ∈ R p to be degree < N polynomial defined by A j σ , b j σ , and saves e σ := (e 0 σ , . . . e c-1 σ ) ∈ R c p . The simulator proceeds to simulate the calls to F c-SUV as follows. For each j ∈ [0..c), l ∈ [0..t) for which b i σ [k] = 0 it outputs "β = 0" to the adversary and aborts on this instance. Next, for all other instances it awaits a guess B of size at most 2N of the adversary. The simulator replies with "⊥" (regardless of the set B) and continues. Subsequently, for i, j ∈ [0..c) and k, l ∈ [0..t) corresponding to a non-aborting instance the simulator waits for input g i,j σ,k,l and predicate P i,j k,l : [0..2N ) → {0, 1} by the adversary. Now, the simulator chooses random

A 0 , . . . , A c-1 $ ← [0..N ) t , b 0 , . . . , b c-1 $ ← Z t p \{0}
and proceeds as follows:

For each i, j ∈ [0..c), k, l ∈ [0..t), in the (i, j, k, l)-th invocation of F c-SUV , if P i,j k,l (A i [k] + A j σ [l]) = 0,

the simulator aborts on all instances and outputs

(A i [k] + A j σ [l], b i [k] • b j σ [l]
). Otherwise, it outputs (success) and continues. Next, if the simulator did not abort on any instance, for each i, j ∈ [0..c), k, l ∈ [0..t) the simulator defines the vector

g i,j σ = t j,k=1 g i,j σ,k,l .
The simulator interprets each g i,j σ as a degree < 2N polynomial g σ,i+cj over Z p , and sets g σ := (g 0 σ , . . . , g c 2 -1 σ ).

Protocol Π mal-OLE Parameters: Security parameter 1 λ , natural number N = 2 k , prime p, access to functionality F c-SUV with length 2N , prime modulus p, polynomial F (X) ∈ Z[X] of degree N , ring R = Z p [X]/F (X), and parameters c, t ∈ N (corresponding to the syndrome compression factor and noise rate of the LPN assumption, respectively). Public input: random polynomials a 1 , . . . , a c-1 ∈ R p , used for R c -LPN Correlation: After expansion, outputs (x 0 , z 0 ) ∈ R 2 p and (x 1 , z 1 ) ∈ R 2 p , where z 0 +z 1 = x 0 •x 1 . Protocol:

1. For σ ∈ {0, 1}, i ∈ [0..c), party P σ samples random vectors A i σ ← [0.
.N ) t (where each entry of A i σ is viewed as a length-log N bit-string) and b i σ ← (Z * p ) t . Note that each pair

A i σ , b i σ defines a t-sparse polynomials e i σ (X) = t-1 k=0 b i σ [k] • X A i σ [k] ∈ R p . 2. For σ ∈ {0, 1}, i ∈ [0..c) and k ∈ [0..t): A i σ [k] 2 ← Input(P σ , A i σ [k]) and b i σ [k] p ← Input(P σ , b i σ [k]).
3. For every i, j ∈ [0..c) and k, l ∈ [0..t) (in parallel) the parties do the following:

(a) α i,j k,l 2 ← BitAdd( A i 0 [k] 2 , A j 1 [l] 2 ). (b) Compute β i,j k,l p ← Mult( b i 0 [k] p , b j 1 [l] p ). (c) For each i, j ∈ [0..c) and k, l ∈ [0..t), call F c-SUV with length 2N on input α i,j
k,l 2 and β i,j k,l p , and let g i,j σ,k,l denote the output to party P σ . 4. For each i, j ∈ [0..c), P σ defines the vector

g i,j σ = t-1 j,k=0
g i,j σ,k,l .

5. Party P σ computes x σ = a, e σ mod F (X), where a = (1, a 1 , . . . , a c-1 ), e σ = (e 0 σ , . . . , e c-1 σ ). And, interpreting each g i,j σ as a degree < 2N polynomial g σ,i+cj over Z p , and setting g σ := (g 0 , . . . , g c 2 -1 ), party P σ computes z σ = a ⊗ a, g σ mod F (X).

6. Party P σ outputs (x σ , z σ ) 1. Sample γ 0 , γ 1 ← Z p and let γ = γ 0 + γ 1 .

2. Sample x 0 , x 1 , y 0 , y 1 ← R p and let x = x 0 + x 1 , y = y 0 + y 1 .

Compute

z = x • y. 4. Choose m x,0 , m y,0 , m z,0 ← R p and define m x,1 := γ • x -m x,0 , m y,1 := γ • y -m y,0 and m z,1 := γ • z -m z,0 . 5. Output (γ σ , x σ , y σ , z σ , m x,σ , m y,σ , m z,σ ) to party P σ , for σ ∈ {0, 1}
If party P σ is corrupted:

1. Wait for input (γ σ , x σ , y σ , z σ , m x,σ , m y,σ , m z,σ ) ∈ Z p × R 6 p from the adversary.

Sample γ

1-σ ← Z p and x 1-σ , y 1-σ ← R p . Set γ := γ 0 + γ 1 , x := x 0 + x 1 , y := y 0 + y 1 and z := x • y. Compute z 1-σ ← z -z σ , as well as m x,1-σ ← γ • x -m x,σ , m y,1-σ ← γ • y -m y,σ and m z,1-σ ← γ • z -m z,σ . 3. Output (γ 1-σ , x 1-σ , y 1-σ , z 1-σ , m x,1-σ , m y,1-σ , m z,1-σ )
to the honest party.

Efficiency Analysis

In this section we analyze the efficiency of the presented protocols for distributed setup. For an overview of concrete efficiency for the generation of OLEs in the semi-honest and malicious setting, we refer to Table 3 in Section 9. We start this section by providing the costs for implementing the secure functionalities F 2-PC and F ext-2-PC from Section 5. We assume that secret values in these functionalities are additively secret-shared between the two parties. In the case of malicious security, the shares are also authenticated with information-theoretic MACs as in [START_REF] Bendlin | Semihomomorphic encryption and multiparty computation[END_REF][START_REF] Buus Nielsen | A new approach to practical active-secure two-party computation[END_REF], which ensures correct opening of shares.

Input(P σ , x): For semi-honest security, this has no communication cost as the parties define their respective shares to be x and zero. For malicious security, P σ needs to have an authenticated random value, which can be preprocessed, and then sends bits for x ∈ {0, 1} or log p bits for x ∈ Z p , to use the random value to authenticate x.

Add: This is a local operation.

Mult( x M , y M ): Uses one multiplication triple over Z M , with an online communication cost of 2 log M bits per party (from two calls to Output).

BitAdd: Evaluates a binary circuit on inputs of length bits, using AND gates. This consumes multiplication triples over Z 2 , giving an online communication cost of 2 bits per party.

Output( x M ): This requires sending log M bits per party. With malicious security, the parties Protocol Π mal-triple (Part I)

Parameters: Security parameter 1 λ , natural number N = 2 k , prime p, access to functionality F c-SUV with length 2N , prime modulus p, polynomial F (X) ∈ Z[X] of degree N , ring R = Z p [X]/F (X), and parameters c, t ∈ N (corresponding to the syndrome compression factor and noise rate of the LPN assumption, respectively). Public input: random polynomials a 1 , . . . , a c-1 ∈ R p , used for R c -LPN Protocol:

1. The parties jointly setup γ ∈ Z p and t-sparse polynomials e 0 , ..., e c-1 and f 0 , . . . , f c-1 , which will be used to generate x and y, respectively.

(a) For σ ∈ {0, 1}, party P σ chooses γ σ ∈ Z p , and inputs γ σ p ← Input(P σ , γ σ ). The parties compute

γ p ← γ 0 p + γ 1 p . (b) For σ ∈ {0, 1}, i ∈ [0..c), party P σ chooses A i e,σ ← [0..N ) t , b i e,σ ← (Z * p ) t . For k ∈ [0..t): i. A i e,σ [k] 2 ← Input(P σ , A i e,σ [k]) //P σ inputs k-th non-zero position of e i σ ii. b i e,σ [k] p ← Input(P σ , b i e,σ [k]) //P σ inputs the k-th payload of e i σ iii. A i e [k] 2 ← A i e,0 [k] 2 ⊕ A i e,1 [k] 2 //compute k-th position of e i = e i 0 + e i 1 iv. b i e [k] p ← b i e,0 [k] p + b i e,1 [k] p //compute k-th payload of e i = e i 0 + e i 1 v. m i e [k] p ← Mult( b i e [k] p , γ p ) //multiply k-th payload of e i by MAC key γ vi. Call F c-SUV with length N on input A i e [k] 2 and b i e [k], m i e [k] p such that party P σ receives output ( e i σ,k , u i σ,k ) ∈ Z N p × Z N p . //convert to additive shares of e i , γ • e i (c) Repeat step (b) for f 0 , . . . , f c-1 with result ( f i σ,k , v i σ,k ) ∈ Z N p × Z N p .
2. For every i, j ∈ [0..c) and k, l ∈ [0..t) (in parallel) the parties do the following:

(a) α i,j k,l 2 ← BitAdd( A i e [k] 2 , A j f [l] 2 ) //compute (k+tl)-th non-zero position of e i •f j (b) β i,j k,l p ← Mult( b i e [k] p , b j f [k] p ) //compute (k + tl)-th payload of e i • f j (c) m i,j
k,l p ← Mult( β i,j k,l p , γ p ) //multiply (k + tl)-th payload of e i • f j by MAC key γ (d) For each i, j ∈ [0..c) and k, l ∈ [0..t), call F c-SUV with length 2N on input α i,j k,l 2 and β i,j k,l , m i,j k,l p , and let ( g i,j σ,k,l , w i,j σ,k,l ) denote the output to party P σ . //convert to additive shares of e i • f j , γ • e i • f j 3. For each i ∈ [0..c), P σ defines the vectors

e i σ = t-1 k=0 e i σ,k , u i σ = t-1 k=0 u i σ,k , f i σ = t-1 k=0 f i σ,k and v i σ = t-1 k=0 v i σ,k .
4. For each i, j ∈ [0..c), P σ defines the vectors

g i,j σ = t-1 j,k=0
g i,j σ,k,l and w i,j σ = t-1 j,k=0

w i,j σ,k,l . Protocol: (continued)

5.

Interpret each e i σ as a degree < N polynomial e σ,i over Z p , and set e σ := (e 0 , . . . , e c-1 ) (accordingly for u i σ , f i σ and v i σ ).

6. Interpret each g i,j σ as a degree < 2N polynomial g σ,i+cj over Z p , and set g σ := (g 0 , . . . , g c 2 -1 ) (accordingly for w i,j σ ).

Compute

x σ = a, e σ , y σ = a, f σ , z σ = a ⊗ a, g σ and

m x,σ = a, u σ , m y,σ = a, v σ , m z,σ = a ⊗ a, w σ all modulo F (X).
8. Output (γ σ , x σ , y σ , z σ , m x,σ , m y,σ , m z,σ )

Figure 12: PCG protocol implementing the corruptible functionality for authenticated triples (Part II) also need to send and check the MACs on shares, however, this can be amortized for a large batch of openings by checking a random linear combination, so we ignore this.

Inv( x p ): This can be done using one multiplication triple, and two openings.9

MixedMult(x 0 , x 1 , α 2 ): With semi-honest security, this uses two string-OTs of length , plus + 1 bits of communication from each party. With malicious security, when α is already authenticated with MACs, this can be done with bits of communication from each party without any additional preprocessing. To see this, recall that a share α σ is authenticated by giving P σ a MAC M = α σ K + K , where K, K ∈ {0, 1} λ are random MAC keys known to P 1-σ . By hashing M and K respectively, the parties obtain secret shares of α σ • z, where z = H(K ) ⊕ H(K ⊕ K) is known to P 1-σ . These can be converted into shares of α σ • x 1-σ with bits of communication; the complete multiplication is then obtained symmetrically.

PassiveOutput(x 0 , x 1 ): (x 0 , x 1 ∈ {0, 1} log M ) Here, the parties exchange shares by sending log M bits each.

Cost of Preprocessing. We assume that multiplication triples over Z p can be obtained by bootstrapping from a previous PCG instance, so essentially obtained at no cost. Similarly, for the Input phase we can obtain authenticated random values with vector-OLE (over Z p ) or correlated OT (over Z 2 ), using the efficient PCGs from previous works [BCGI18, BCG + 19b, BCG + 19a]. With semi-honest security, we can also obtain multiplication triples over Z 2 using a PCG for OT. However, we cannot do this for malicious security, since we do not have an efficient PCG for authenticated triples over Z 2 . Therefore, we build these from correlated OT using the TinyOT protocol from [FKOS15, HSS17], for a cost of 32 bits of communication per party and 54 correlated OTs, for each triple.

Main Subprotocols. Before stating the complexities of distributed key generation, we give an overview of the complexity of the subprotocols Π DPF (based on [START_REF] Doerner | Scaling ORAM for secure computation[END_REF])/ Π c-SUV (see Figure 6) for implementing F DPF (semi-honest)/ F c-SUV (malicious) with domain size D and output shares in Z p (see Remark 5.2 for obtaining outputs in Z p ). Note that for the following we assume λ > log p, otherwise the parties have to perform an additional D • (log p)λ PRG operations.

Basic protocol: the basic protocol has the following complexity:

• 2D evaluations of PRG //Step 2 • log D Mult/MixedMult over {0, 1} λ × {0, 1} //Step 2 • log D Output/PassiveOutput over {0, 1} λ+2 //Step 2 • + 1 Input (per party) + + 1 Output over Z p //Step 4 • Inv + Mult over Z p //Step 4
Consistency check: (only required for malicious security)

• Mult over Z p //Step 7 • + 1 Input (per party) + Output over Z p //Step 7
With implementing the functionalities for secure 2-party computation as described, this adds up to the following complexity:

Correlated randomness: Consuming correlated randomness in the form of:

• semi-honest: 2 multiplication triples + 2 log D λ-string-OTs 1. ct Input over {0, 1} log N and Z p (per party) //positions + payloads of e i 0 , e i

1 2. (ct) 2 BitAdd over {0, 1} log N + (ct) 2 Mult over Z p //positions + payloads of e i 0 • e j 1 3. (ct) 2 invocations of F DPF / F c-SUV with length 2N over Z p ( = 1) //convert to shares of e i 0 • e j 1
For protocol Π mal-triple (Fig. 12) implementing F mal-triple (malicious)the costs are as follows:

1. 2ct Input over {0, 1} log N and Z p (per party) //positions + payloads of e i 0 , e i 1 , f i 0 , f i 1 2. 2ct + (ct) 2 Mult over Z p //multiply payloads of e i 0 , e i 1 , f i 0 , f i 1 by MAC γ 3. 2ct F c-SUV with length N and output Z 2 p //convert to shares of e i 0 + e i 1 ,

f i 0 + f i 1 4. (ct) 2 BitAdd over {0, 1} log N + (ct) 2 Mult over Z p //positions + payloads of e i • f j 5. (ct) 2 invocations of F DPF / F c-SUV with length 2N over Z 2 p ( = 2) //convert to shares of e i • f j
Altogether, we obtain the following theorems: Theorem 6.5 (OLE Distributed Generation) Assuming hardness of R c -LPN p,1,t (Def. 3.2), there exists a protocol securely realizing functionality F OLE-Setup / F mal-OLE to produce N OLEs against semi-honest adversaries/ malicious adversaries with the following complexity (note that costs not specified in the following apply to both):

Correlated randomness: Consuming correlated randomness in the form of:

1. malicious: 2ct log N correlated OTs + 2× length-ct vector-OLE (in Z p ) 2. • semi-honest: 2(ct) 2 log N bit-OTs + (ct) 2 OLEs over Z p • malicious: 54(ct) 2 log N correlated OTs + (ct) 2 authenticated triples over Z p 3. • 4(ct) 2 OLEs + 2(ct) 2 log(2N ) λ-string-OTs • malicious: 3(ct) 2 authenticated triples + 2× length-4(ct) 2 vector-OLE over Z p
Computation: Computation is dominated by 2(ct) 2 N PRG evaluations.

Communication: Communication (per party) is dominated by: Remark 6.1 (Optimizing efficiency) If N is a power of 2, the above protocols can be optimized by taking the noise positions mod N and therefore reducing the input length to F DPF /F c-SUV from 2N to N . Alternatively, by relying on the hardness of R c -LPN with a regular error distribution (where each noisy coordinate lies in a fixed interval of size N/t), one can replace all occurrences of N in the efficiency estimates above by N/t.

1. malicious: ct(log N + log p) bits 2. • semi-honest: 2(ct) 2 log N + 2(ct) 2 log p bits • malicious: 34(ct) 2 log N + 2(ct) 2 log p bits 3. • (ct) 2 ((2λ + 3) log(2N ) + 5 log p) bits • malicious: additional (ct) 2 • 6 log p) bits
Recall that except for a one-time setup cost the generation of correlated randomness is almost for free in terms of communication: For the generation of OT and vector-OLE with semi-honest and even malicious security, we can build on the silent OT and vector-OLE extensions from [BCG + 19b, BCG + 19a]. Further, for the generation of OLE and authenticated multiplication triples we can bootstrap and therefore only need to generate these correlations from scratch once. For generating OLEs with malicious security one can bootstrap using the PCG for authenticated multiplication triples (at comparatively little extra cost).

Extensions and Applications

In this section we extend our PCG for OLE in several directions. First, we build PCGs for inner product correlations from OLE over R p , with the advantage that we do not need to rely on the full reducibility of F (X), and can also obtain correlations over F 2 . Secondly, we present a method for building PCGs for general bilinear correlations, such as matrix multiplication, in a black-box way from our previous PCG. Finally, we show that all of these PCGs for degree two correlations can be extended in a natural way to the multi-party setting.

Bilinear Correlations

The class of bilinear correlations we consider is as follows.

Definition 7.1 (Simple Bilinear Correlation) Let G 1 , G 2 , G T be Abelian groups and e : G 1 × G 2 → G T be a bilinear map. We define the simple bilinear correlation for e by the distribution

C e over (G 1 × G T ) × (G 2 × G T ) of the form C e = ((r 0 , s 0 ), (r 1 , s 1 )) | r 0 $ ← G 1 , r 1 $ ← G 2 , s 0 $ ← G T , s 1 = e(r 0 , r 1 ) -s 0 .
We denote by C n e the correlation that outputs n independent samples from C e , i.e.

C n e = ((R 0 , S 0 ), (R

1 , S 1 )) | R 0 $ ← G n 1 , R 1 $ ← G n 2 , S 0 $ ← G n T , S 1 = e(R 0 , R 1 ) -S 0 ,
where we define e : G n 1 × G n 2 → G n T as the bilinear map obtained by applying e componentwise.

This covers several common correlations like OT and OLE, for example, OLE over a ring R can be obtained with G 1 = G 2 = G T = (R, +) and e(x, y) = x • y. Also, note that two independent bilinear correlations can be locally converted to produce an additively secret-shared instance of the correlation -for example, two OLEs are locally equivalent to one multiplication triple.

Inner Product Correlations

An inner product correlation is a simple bilinear correlation with the inner product map over Z p . These can be used to compute inner products in an MPC online phase, in a similar way to using multiplication triples. Inner products are common in tasks involving linear algebra, like privately evaluating or training machine learning models such as SVMs and neural networks, and a single inner product can also be used to measure the similarity between two input vectors.

We remark that given n random OLEs in F p , it is easy to locally convert these into a length-n inner product correlation, so we can build a PCG for inner products of any length using a PCG for OLE. However, the constructions in this section do not rely on the fully-reducible ring-LPN assumption that is needed for OLE in F p ; instead, we use the ring-OLE construction from Fig. 1 over more conservative rings, which do not split completely into linear factors. Further, the constructions in this section generalize to rings Z p for arbitrary p ∈ N (including p = 2). Lemma 7.1 Let R p = Z p [X]/F (X), where F (X) is a degree-N polynomial with non-zero constant coefficient. Then, a single OLE over R p can be locally converted into an inner product correlation over Z N p .

Proof. For a ∈ R p , define the matrix over Z p that corresponds to multiplication by a, as

M a =   a aX • • • aX N -1  
where each aX i is reduced modulo F (X) and represented as a vector of coefficients in Z N p . We have that for any b ∈ R p represented as a vector of coefficients, the coefficient vector of ab is M a • b. Also, it is easy to see that if a is uniformly distributed in R p then the first row of M a , denoted M a [0], is uniform over Z N p , since aX i has a N -i appearing in its constant term. So given an OLE (a, c), (b, d) over R p , where c -d = ab, the parties can define an inner product correlation

(M a [0], c 0 ), (b, -d 0 ), where c 0 -d 0 = M a [0], b .
Note that, for the special case of F (X) = X n + 1, the vector M a [0] can be computed as (a 0 , -a n-1 , . . . , -a 1 ), without any modular reductions.

Corollary 7.2 (Large inner product from irreducible ring-LPN) Suppose the R-LPN p,1,t assumption holds for R = Z p [X]/F (X), where F (X) is degree N and irreducible over Z p . Then there is a PCG for the length-N inner product correlation over Z p , where the seeds have size O(λt 2 log N ) bits, and the computational complexity of the Expand operation is Õ(N ) operations in Z p , plus O(t 2 N ) PRG operations.

Corollary 7.3 (Small inner products from reducible ring-LPN) Suppose the R-LPN p,1,t assumption holds for R = Z p [X]/F (X), where F (X) is degree N and splits into N/d distinct factors of degree d. Then there is a PCG for producing N/d instances of length-d inner product correlation over Z p , with the same seed size and complexity as above.

The latter construction has two benefits over naively using OLE over F p to generate an inner product. Firstly, OLE in F p requires that R splits fully into linear factors, whereas for inner products the factors can be degree-d (and irreducible), which is a much more conservative assumption; in particular, the dimension-reduction attack we consider in Section 8 is less effective. Secondly, we can also use this to generate inner products over small fields such as F 2 , whereas we cannot efficiently obtain OLEs over F 2 with our present constructions.

Bilinear Correlations from Programmable PCG for OLE

We can build a PCG to create a large batch of samples from any simple bilinear correlation, using the PCG for OLE from Section 4. To do this, we exploit the fact that this PCG is programmable, which, roughly speaking, means that one party can "reuse" its input a or b in several instances of the PCG, while maintaining security. Boyle et al. [BCG + 19b] previously used this property to construct multi-party PCGs from several instances of programmable two-party PCGs; unlike their work, we exploit the property for a different purpose in the two-party setting.

In the following, we recall the definition of programmability, and show that our PCG for OLE satisfies this definition. Definition 7.2 (Programmable PCG) A tuple of algorithms PCG = (PCG.Gen, PCG.Expand) following the syntax of a standard PCG, but where PCG.Gen(1 λ ) takes additional random inputs ρ 0 , ρ 1 ∈ {0, 1} , is a programmable PCG for a simple bilinear 2-party correlation C n e (specified by e : G 1 × G 2 → G T ) if the following holds:

• Correctness. The correlation obtained via:

((R 0 , S 0 ), (R 1 , S 1 )) ρ 0 , ρ 1 $ ← $, (k 0 , k 1 ) $ ← PCG.Gen(1 λ , ρ 0 , ρ 1 ), (R σ , S σ ) ← PCG.Expand(σ, k σ ) for σ ∈ {0, 1} is computationally indistinguishable from C n e (1 λ ). • Programmability. There exist public efficiently computable functions φ 0 : {0, 1} → G n 1 , φ 1 : {0, 1} → G n 2 such that Pr   ρ 0 , ρ 1 ← $, (k 0 , k 1 ) $ ← PCG.Gen(1 λ , ρ 0 , ρ 1 ) (R 0 , S 0 ) ← PCG.Expand(0, k 0 ), (R 1 , S 1 ) ← PCG.Expand(1, k 1 ) : R 0 = φ 0 (ρ 0 ) R 1 = φ 1 (ρ 1 )   ≥ 1 -negl(λ),
where e :

G n 1 × G n 2 → G n
T is the bilinear map obtained by applying e componentwise. • Programmable security. The distributions

(k 1 , (ρ 0 , ρ 1 )) ρ 0 , ρ 1 ← $, (k 0 , k 1 ) $ ← PCG.Gen(1 λ , ρ 0 , ρ 1 )
and

(k 1 , (ρ 0 , ρ 1 )) ρ 0 , ρ 1 , ρ0 ← $, (k 0 , k 1 ) $ ← PCG.Gen(1 λ , ρ0 , ρ 1 )
as well as

(k 0 , (ρ 0 , ρ 1 )) ρ 0 , ρ 1 ← $, (k 0 , k 1 ) $ ← PCG.Gen(1 λ , ρ 0 , ρ 1 ) and
(k 0 , (ρ 0 , ρ 1 )) ρ 0 , ρ 1 , ρ1 ← $, (k 0 , k 1 ) $ ← PCG.Gen(1 λ , ρ 0 , ρ1 ) are computationally indistinguishable.
We start by showing that a programmable PCG is a PCG in the standard sense.

Lemma 7.4 Let e : G 1 × G 2 → G T be a bilinear map. Then, a programmable PCG PCG = (PCG.Gen, PCG.Expand) for the bilinear 2-party correlation C n e is also a PCG for C n e in the sense of Definition 2.6 (where the sampling of ρ 0 , ρ 1 happens inside PCG.Gen).

Proof. We have to show that the PCG satisfies standard security. More precisely, we have to prove that if PCG = (Gen, Expand) satisfies correctness, programmability and programmable security, then the distributions

D real := (k 1 , (R 0 , S 0 )) ρ 0 , ρ 1 ← $, (k 0 , k 1 ) $ ← PCG.Gen(1 λ , ρ 0 , ρ 1 ) (R 0 , S 0 ) ← PCG.Expand(0, k 0 )
and

D sim :=      (k 1 , (R 0 , S 0 )) ρ 0 , ρ 1 ← $, (k 0 , k 1 ) $ ← PCG.Gen(1 λ , ρ 0 , ρ 1 ) (R 1 , S 1 ) ← PCG.Expand(1, k 1 ) R 0 $ ← G 1 , S 0 = e(R 0 , R 1 ) -S 1     
are computationally indistinguishable (the case k 0 is symmetric). We proceed the proof via a sequence of hybrid distributions:

D 1 :=      (k 1 , (R 0 , S 0 )) ρ 0 , ρ 1 ← $, (k 0 , k 1 ) $ ← PCG.Gen(1 λ , ρ 0 , ρ 1 ) (R 1 , S 1 ) ← PCG.Expand(1, k 1 ) R 0 = φ 0 (ρ 0 ), S 0 = e(R 0 , R 1 ) -S 1      D 2 :=      (k 1 , (R 0 , S 0 )) ρ 0 , ρ 1 ← $, (k 0 , k 1 ) $ ← PCG.Gen(1 λ , ρ 0 , ρ 1 ) (R 1 , S 1 ) ← PCG.Expand(1, k 1 ) ρ0 ← $, R 0 = φ 0 (ρ 0 ) , S 0 = e(R 0 , R 1 ) -S 1     
The distribution D real and D 1 are computationally close by the programmability and correctness of the PCG.

Next, let A be a distinguisher between the distribution D 1 and D 2 . Then, we can construct an adversary B on the programmable security of PCG as follows. The adversary B obtains (k 1 , (ρ 0 , ρ 1 )) from its experiment. It computes (R 1 , S 1 ) ← PCG.Expand(1, k 1 ), R 0 = φ 0 (ρ 0 ) and S 0 = e(R 0 , R 1 ) -S 1 and forwards (k 1 , (R 0 , S 0 )) to A. Finally, B forwards the reply of A to its own experiment. If B obtained the real ρ 0 from its own experiment, then the resulting distribution is identically to D 1 , whereas if B obtained a simulated ρ 0 , B simulates D 2 . Therefore, B successfully breaks the programmable security, whenever A successfully distinguishes D 1 and D 2 .

Finally, D 2 and D sim are computationally indistinguishable by the correctness of the PCG.

Lemma 7.5 The PCG construction for ring-OLE from Fig. 1 is programmable.

Proof. To allow programmability, we tweak the Gen algorithm as follows. For σ ∈ {0, 1} the additional input ρ σ can be sampled as {A i σ , b i σ } i∈[0..c) in Fig. 1, representing a vector of sparse polynomials e = (e 0 σ , . . . , e c-1 σ ). Notice that the first part (i.e. x σ ) of both expanded outputs can now be obtained from just ρ σ , by first expanding {A i σ , b i σ } i∈[0..c) to e σ and then computing x σ = a, e σ mod F (X). This defines the functions φ 0 and φ 1 , and the correctness property follows in the same way as the proof of correctness in Theorem 4.1. The programmable security property can also be proven similarly to the proof of Theorem 4.1, with a reduction to the FSS scheme and ring-LPN assumption.

Below we describe the main result, and some applications.

Decomposition of bilinear maps.

Let f : G 1 × G 2 → G T and g : G u 1 × G v 2 → G w
T be bilinear maps over the additive groups G 1 , G 2 , G T . We will consider ways of computing g that are restricted to a fixed number of calls to f on the components of the inputs to g, followed by linear combinations in G T of the results of the f evaluations.

Definition 7.3 (Simple f -decomposition) Let G 1 , G 2 , G T be additive abelian groups, viewed as Z-modules. Let f : G 1 ×G 2 → G T and g : G u 1 ×G v 2 → G w T be non-degenerate bilinear maps. We say that g has a simple f -decomposition if there exist γ ∈ N, W ∈ Z w×γ and α

i ∈ [u], β i ∈ [v], for i ∈ [γ], such that for all a = (a 1 , . . . , a u ) ∈ G u 1 and b = (b 1 , . . . , b v ) ∈ G v 2 , it holds that g(x 0 , x 1 ) = W •    f (a α 1 , b β 1 ) . . . f (a αγ , b βγ )   
We say that the f -complexity of this decomposition of g is given by n f (g) := γ.

Note that if G 1 , G 2 , G T are all a (commutative) ring R and f is multiplication in R, then any g has a simple f -decomposition of complexity u • v. However, it can still be useful to find a different f that achieves lower complexity.

We now show that any map g with a simple f -decomposition can be used to construct a PCG for the simple bilinear correlation C g , given a programmable PCG for C f . The construction is given in Fig. 13. The idea is that for each invocation of f used in an evaluation of g, we will use a separate instance of the PCG for f , programmed to use the correct portions of the input to g. Then, we can obtain the expanded g output by applying the linear map W to all the expanded outputs of f . We also use a PRG to randomize the final output shares, to ensure that there are no correlations introduced when multiplying by W .

For the security proof, we use an extension of the programmable security property, which considers several PCG instances, given in the following lemma.

Example parameters. We now give some example parameters for generating matrix triples, based on the analysis in Section 9. For instance, when producing 8-dimensional square matrix triples in a batch of size ≈ 130000, over a 128-bit field, the PCG seeds have size around 83MB. These can be expanded to produce matrix correlations of around 400MB, giving a 5-fold expansion factor. Increasing the dimension to 16, the seed size grows to 330MB, while the PCG output has size 810MB. Going to dimension 32 and beyond, the seeds start to become much larger, although better expansion rates could be obtained when producing a much larger batch of triples. In general, this shows that in practice, the construction is only likely to be useful for small matrix dimensions; however, these could still be used as a building block in performing larger matrix multiplications in applications. For larger matrices, more interactive approaches such as recent work based on homomorphic encryption [CKR + 20] appear to be more practical.

Remark 7.8 Instead of using a PCG for inner product, we could instead directly use a programmable PCG for OLE to build matrix multiplications, by applying Theorem 7.4 with f as Z p multiplication. However, this would require n 1 • n 2 • n 3 instances of the base PCG, giving a much worse expansion factor. This shows the advantage of finding a suitable f such that the desired correlation g has low f -complexity, compared with the naive approach.

Application: Circuit-Dependent MPC Preprocessing

Circuit-dependent preprocessing is a variation on the standard multiplication triples technique, which is based on Beaver's circuit randomization technique [START_REF] Beaver | Efficient multiparty protocols using circuit randomization[END_REF] and extended in more recent works [DNNR17, KKW18, BNO19, BGI19]. The idea is to preprocess multiplications in a way that depends on the structure of the circuit, and leads to an online phase that requires just one opening per multiplication gate, instead of two when using multiplication triples.

With the PCG for general bilinear correlations, we can generate circuit-dependent preprocessing for a large batch of identical circuits. This can be useful, for instance, when executing the same function many times on different inputs, or when a larger computation contains many small, repeated instances of a particular sub-circuit.

Let C be an arithmetic circuit over F consisting of fan-in two addition and multiplication gates.

In the offline phase each wire w in the circuit is assigned a value r w such that:

• if w is an input wire, r w $ ← F is chosen at random

• if w is the output wire of a multiplication gate, r w $ ← F is chosen at random

• if w is the output wire of an addition gate with input wires u and v, then r w = r u + r v .

Further, each multiplication gate is assigned a value s u,v as follows:

• if the multiplication gate has input wires u and v, then

s u,v = r u • r v .
The goal of the offline phase is for the parties to obtain random additive shares of r w for all input wires and output wires of multiplication gates, as well as s u,v for all multiplication gates. Let G denote the set of multiplication gates. Then, for a multiplication gate g ∈ G with input wires u and v, we can write s u,v as i∈Lg r i • j∈Rg r j , where L g and R g are the sets of output wires of multiplication gates that pass only through addition gates before reaching g. All s u,v values can therefore be computed as a bilinear function f C of r, where r consist of the random values assigned to the input wires and the output wires of multiplication gates.

Plugging in the previous construction for general bilinear correlations, we obtain a PCG for f C out of several instances of a PCG for OLE, where the total number of instances is

g∈G |L g | • |R g |.

Application: Multi-Party PCGs for Bilinear Correlations

In [BCG + 19b][Theorem 41], Boyle et al. showed that any two-party, programmable PCG for a simple bilinear correlation can be used to build a multi-party PCG for an additively secret-shared version of the same correlation.

Plugging in Lemma 7.5 and the results of the previous section, we obtain N -party PCGs for (unauthenticated) multiplication triples, matrix triples and circuit-dependent preprocessing over Z p based on ring-LPN, for any polynomial number of parties N . Each party's seed contains 2(N -1) seeds of the underlying two-party PCG, plus N -1 seeds for a PRG. The expansion procedure of the PCG consists of expanding the 2(N -1) PCG seeds, as well as the PRG seeds.

Authenticated triples in the multi-party setting. Unfortunately, the transformation of Boyle et al. only applies to degree-2 correlations, and we do not see a way to directly apply it to our PCG for authenticated multiplication triples, which is a degree-3 correlation. To see the challenge in extending their construction, consider the case of n parties who wish to obtain additive shares of α • (x • y), where α, x, y are additively shared. To do this using pairwise correlations, it seems we need a way to obtain shares of x i • y j • α k , for every i, j, k ∈ [n], where P i holds x i , P j holds y j and P k holds α k . We cannot do this with just a pairwise correlation between P i and P j , since α k must be known only to P k . On the other hand, given a function secret sharing scheme for 3 parties, one could modify our authenticated triples construction from Fig. 2 to make this work. However, known constructions of 3-party distributed point functions are much more expensive, with a seed size of O( √ λN ) rather than O(λ log N ) [START_REF] Boyle | Function secret sharing[END_REF].

Security Analysis

We analyze the security of module-LPN against various attacks. In the following, we consider a R c -uLPN instance over a ring R = F[X]/F (X) (where F (X) is a degree-N polynomial) with c samples, and a regular noise of total weight w (that is, w = t • c, where t is the number of nonzero coordinates of each noise e i ∈ R); therefore, the adversary gets ( a i , a i , s + e i ) c i=1 , where s and each a i are random over R c-1 , and each e i is sampled from HW w/c , and must distinguish ( a i , s + e i ) i≤c from a random element of R c . The corresponding code is a linear code with dimension (c -1) • N and length c • N , whose parity-check matrix H ∈ F N ×c•N is c-compressing. Note that by our reduction from R-LPN to R-uLPN (Lemma 3.4), this effectively reduces to distinguishing ( a , a , s + e ) from random, where a $ ← R c-1 and s $ ← (HW c-1 w/c ) is (c -1)w/c-sparse.

We will consider two alternatives for the underlying field: either F is a very small field (e.g.

F = F 2 )
, or F is a large field (e.g. F = Z p where p is a large prime, for example p ≈ 2 128 ). Eventually, we will consider both the cases where F (X) is an irreducible polynomial over F[X], and the case where F (X) is fully reducible over F[X] (typically, this will be the case when F is a two-power cyclotomic polynomial and F = Z p where p is a large prime). We can also consider two error distributions: the e i can be either random weight-t errors, or regular weight-t errors (where N coordinates of e i are divided into t blocks of length N/t, and a single random noise is added to a random coordinate of each block). Below, we analyze various attacks with respect to the uniform noise distribution. However, none of the attacks we describe in the following sections performs better when using a regular noise distribution.

Bottom Line. To provide a short, high-level summary of the conclusion of this section: when F is irreducible over a large field F, no known attacks perform significantly better than those on standard LPN, with a very limited number of samples O(n), where n is the dimension. In this setting, attacks such as BKW do not apply, but information set decoding (ISD) and statistical decoding (SD) do. Both have complexity exponential in the number of noisy coordinates. When F is reducible, however, the adversary can reduce the instance modulo some factor and get a new LPN instance, which might be easier to solve if the factor is sparse (as it reduces the dimension without increasing the noise). Hence, the cost of ISD and SD must be evaluated for each reduction modulo a sparse factor, and the cost of the attack is the smallest cost accross all factors. Our use of structured matrices means that the DOOM attack might apply, but it only reduces security by about (log N )/2 bits. Eventually, over types of structural attacks, like algebraic decoding attacks, do not seem to apply to our setting.

Generic Attacks on LPN

We denote by

G = [Id N || -A 1 || • • • -A c-1
] the generating matrix of the linear code associated to our R-LPN instance, which generates a code with a c-compressing parity-check matrix

H = [A 1 || • • • A c-1 ||Id N ]
where the A i are the multiplication matrices of a i mod F (X) for independent random a i ∈ R.

Existing Generic Attacks. In spite of its extensive use in cryptography, few cryptanalytic results are known for the general LPN assumption. We outline below the main known attacks.

Attacks on Syndrome Decoding. The problem we consider is best seen as an instance of the syndrome decoding problem, where the goal is to recover s given H • s (where, in our case,

H = [A 1 || • • • A c-1 ||Id N ]
is the parity-check matrix of G). Existing attacks on syndrome decoding rely either on improvements over a natural Gaussian elimination attack, called information set decoding (ISD), or on a parity-check attack exploiting low-weight codewords in the dual code, known as statistical decoding attacks [AJ01, Ove06, FKI06, DAT17], or low-weight parity-check attacks [START_REF] Zichron | Locally computable arithmetic pseudorandom generators[END_REF].

• Gaussian Elimination. For the standard LPN assumption with w noisy coordinates, the Gaussian elimination attack requires on average (1/(1 -w/(cN ))) (c-1)N iterations, where the adversary must invert a (c -1)N × (c -1)N submatrix of G, which takes time O(((c -1)N ) 2.8 ) using Strassen's matrix multiplication algorithm. However, since the special structure of G allows for fast (quasilinear) matrix-vector multiplication, standard techniques allow for solving a linear system of equations defined by a random submatrix of G in time O(((c-1) 2 N 2 log((c-1)N )). Hence, the cost (counted as a number of arithmetic operations over F) of the generic Gaussian elimination attack on R-LPN is (assuming for simplicity that c is a constant, as it will be in all our instantiations):

O 1 1 -w cN (c-1)N • ((c -1)N ) 2 log N = O(e (c-1)w c • ((c -1)N ) 2 log N ),
where the equality holds when N w. Note that the above attack assumes a standard noise distribution. However, using a regular noise distribution does not change the efficiency of the attack: if the noise vector is divided into w blocks of length cN/w with a single noise in each block, the natural adaptation of the above Gaussian elimination attack to this setting works by trying to find (c -1)N/w non-noisy coordinate in each of the w blocks (finding more non-noisy coordinates in a given block can only decrease the success probability of the attack). This means that the success probability of the attack is given by

1 - 1 cN/w (c-1)N/w w = 1 - w cN (c-1)N
which leads exactly to the same cost for the attacker. We note that the same observation applies to all variants of ISD we are aware of.

• Information Set Decoding. Among the best algorithms for syndrome decoding are improvements of Prange's ISD algorithm (which is itself an improvement over the Gaussian elimination attack given above), which attempts to find a size-w subset of the rows of H that spans H • e. When the LPN instance has high dimension (c -1)N , cN samples, and very low error rate (which is the case in our scenario, since we consider a fixed amount w of noisy coordinates and N w), according to the analysis of [START_REF] Canto | Analysis of information set decoding for a sub-linear error weight[END_REF], all known variants of ISD (e.g. [Pra62, Ste88, FS09, BLP11, MMT11, BJMM12, MO15]) have essentially the same asymptotic complexity c w(1+o(1)) (ignoring the O((c -1) 2 N 2 log N ) polynomial cost of solving a linear system). Therefore, their gain compared to the initial algorithm of Prange vanishes in our setting and the cost of these attacks is well approximated by

O c w•(1+o(1)) • (c -1) 2 N 2 • log N .
• Statistical Decoding. Eventually, all the previous attacks recover the secret s. If one simply wants to distinguish b = A • s + e from random, there exists an alternative, incomparable line of attacks, known as statistical decoding attacks [START_REF] Al | A statistical decoding algorithm for general linear block codes[END_REF]. These attacks are based on the following observation: by the singleton bound, the minimal distance of the code generated by H is at most (c -1) • N + 1, hence there must be a parity-check equation for G of weight (c -1) • N + 1. Then, if b is random, it passes the check with probability at most 1/|F|, whereas if b is a noisy encoding, it passes the check with probability at least 1/|F| + ((N -1)/cN ) w . Note that this attack works especially well when F is very large, since then a random b has negligible probability to pass the check. Improved variants of the algorithm describe optimized methods to quickly find a relatively large number of parity-check equations with a sufficiently small weight. For the sake of providing conservative estimates, however, we will assume in our analysis that the adversary has already pre-computed an arbitrary number of parity-check equations (since these equations depend solely on H), and that all such equations have minimal weight N + 1. Under these conservative assumptions, the cost (counted as a number of arithmetic operation) of statistical decoding is lower-bounded by

O cN N -1 w • N ≈ O (c w • N ) .
Here again, the estimations are made using the standard noise distribution. However, it does not seem feasible for an attacker to exploit a regular noise distribution: intuitively, the best the attacker can do to exploit this structure requires finding low-weight codewords in the dual code whose nonzero coordinates are 'equally well-spread' accross all coordinates. But at quick calculation similar to the one we did for Gaussian elimination shows that, even if finding many such optimally low-weight well-spread codewords was feasible (which is not clear), the running time of the attack would still remain identital to our estimate above.

Attacks on LPN (Using Many Samples). When the number of samples can be very large, as is generally the case in the LPN literature, there exist improved attacks based on time-space tradeoffs. Below, we briefly recall existing attacks. However, as our overview below illustrates, all these attacks require a superlinear number of samples ω(D) in the dimension D (even the sampleoptimized variant of BKW of [START_REF] Lyubashevsky | The parity problem in the presence of noise, decoding random linear codes, and the subset sum problem[END_REF]), while the variant we consider has cN = c c-1 • D samples. Hence, none of the attacks below does apply in our scenario. We refer the reader to [START_REF] Esser | LPN decoded[END_REF] for a more comprehensive overview. Given an LPN instance with dimension (c -1)N , w noisy coordinates, and q = cN samples, we let r ← w/q denote the noise rate of the instance.

• The BKW algorithm [START_REF] Blum | Noise-tolerant learning, the parity problem, and the statistical query model[END_REF]. This algorithm is a variant of Gaussian elimination which achieves subexponential complexity even for high-noise LPN (e.g. constant noise rate), but requires a subexponential number of samples: the attack solves LPN over F 2 in time 2 O((c-1)N/ log((c-1)N/r)) using 2 O((c-1)N/ log(c-1)(N/r)) samples.

• Hybrid attacks [START_REF] Esser | LPN decoded[END_REF]. The authors of [START_REF] Esser | LPN decoded[END_REF] conducted an extended study of the security of LPN, and described combinations and refinements of the previous three attacks (called the well-pooled Gauss attack, the hybrid attack, and the well-pooled MMT attack ). All these attacks achieve subexponential time complexity, but require as many sample as their time complexity.

• Scaled-down BKW [START_REF] Lyubashevsky | The parity problem in the presence of noise, decoding random linear codes, and the subset sum problem[END_REF]. This algorithm is a variant of the BKW algorithm, tailored to LPN with polynomially-many samples. It solves LPN in time 2 O((c-1)N/ log log((c-1)N/r)) , using ((c -1)N ) 1+ε samples (for any constant ε > 0) and has worse performance in time and number of samples for larger fields.

Taking Advantage of Reducible F

When F (X) is reducible, the above attacks can be improved if the adversary finds sufficiently sparse polynomial factors f i of F . Indeed, when this is the case, the adversary obtains new LPN instances by computing a • s + e mod f i , where the new noise e mod f i remains sparse since f i is sparse. This reduces the problem to an LPN instance in smaller dimension, which can also be solved by any of the above attacks. Below, we consider the best case (for the adversary), when there is a factor f i of degree n = N/k, for some k, which has sparsity 1. This happens, for example, when F (X) is the m-th cyclotomic polynomial, of degree N = φ(m), p = 1 mod 2N , and N is a power of two. In this case, F (X) = X N + 1 splits completely into N linear factors modulo p, but also has sparse factors of the form X 2 i + c i due to properties of roots of unity.10 Reducing a R-LPN sample mod f i brings the dimension down to N/k, while the total number of noisy coordinates now lies between w/k and w (depending on how many errors are added together). To study the effectiveness of this attack, we need to first analyze the new noise rate, and then the performance of the best known R-LPN attacks for the new set of parameters.

Estimating the reduced error rate. Suppose each of the t = w/c errors in one entry of e = (e 1 , • • • , e c ) is chosen independently and uniformly from [N ] (this is only a small change from the original distribution. Then, reducing an error polynomial modulo some 1-sparse f i of degree n = N/k just means each error ends up in a random position in the reduced length-n vector. For each j ∈ [n], define the random variable E j to be 1 if position j in the reduced polynomial has zero errors, and 0 otherwise. It follows that the expected the number of errorfree positions is

j E[E j ] = n • Pr[E j = 1] = n • (1 -1/n) t .
Therefore, summing up across the c error polynomials, we get a total of

cn(1 -(1 - 1 n ) t )
expected errors in the reduced LPN instance.

Analysis for Two-Power Cyclotomics. In our estimations below, we will focus on the important case where F (X) is a two-power cyclotomic, which is one of our main candidates for building a pseudorandom correlation generator for OLE correlations over F = Z p , and which is also the best-case scenario for the attacker: for i = 1 to log N , there exists 1-sparse factors of F (X) of degree 2 i , and each of them gives rise to an LPN instance of dimension n i = (c -1) • 2 i , with q i = c • 2 i samples, and with an expected number of errors

w i = cn i (1 -(1 -1 n i ) w/c ).
Gaussian Elimination. By picking an optimal choice of i, this R-LPN instance can be solved in time

O min 1≤i≤log N 1 1 -w i q i n i • n 2 i log n i .
Information Set Decoding. When F (X) is reducible, we cannot generally assume that the dimension is much larger than the number of noisy coordinates, since the adversary can reduce the dimension. By picking an appropriate i, the adversary can therefore find an LPN instance where some of the improved ISD algorithm perform better than Prange's original algorithm.

Due to the extended literature on ISD, it is difficult to evaluate precisely all existing attacks on a given instance. However, a simplified and general estimation of the efficiency of ISD algorithms was given in [START_REF] Hazay | TinyKeys: A new approach to efficient multi-party computation[END_REF], based on similar analysis given in [START_REF] Finiasz | Security bounds for the design of codebased cryptosystems[END_REF][START_REF] Sendrier | Decoding one out of many[END_REF][START_REF] Hamdaoui | A non asymptotic analysis of information set decoding[END_REF][START_REF] Canto | Analysis of information set decoding for a sub-linear error weight[END_REF]. This general analysis builds upon the fact that most state-of-the-art ISD algorithms share a common structure, from which a general lower bound on the cost of the attack can be derived. Here, we simply reproduce the conclusions of [START_REF] Hazay | TinyKeys: A new approach to efficient multi-party computation[END_REF], restricted to our specific setting, and refer the reader to [START_REF] Hazay | TinyKeys: A new approach to efficient multi-party computation[END_REF] for details on the analysis. We note that [START_REF] Hazay | TinyKeys: A new approach to efficient multi-party computation[END_REF] does not aim at precisely estimating the cost of the attacks, but at providing a reasonably sharp and general lower bound on their costs. In general, the cost of modern ISD algorithms for a parity-check matrix H i , with dimension n i = (c -1) • 2 i , q i = c • 2 i samples, and w i noisy coordinates, is lower bounded by

min p,q    min 2 n i , q i w i n i -q w i -p • K 1 + K 2 n i +q p + w i • (n i -q) 2 q    ,
where the values (p, q) satisfy 0 ≤ q ≤ 2 i and 0 ≤ p ≤ n i +q, K 1 denotes the cost of performing a Gaussian elimination on a submatrix of H i with n i -q columns, and K 2 denotes the running time of a specific sub-algorithm, which varies accross different attacks. Since H is well structured, we assume to be conservative that performing Gaussian elimination on the submatrix of H i can be done in time (n i -q) 2 log(n i -q). Regarding K 2 , according to the analysis of [START_REF] Hazay | TinyKeys: A new approach to efficient multi-party computation[END_REF], it can be lower bounded by (n i + q)/2 p/8 when using the algorithm of [START_REF] Becker | Decoding random binary linear codes in 2 n/20 : How 1 + 1 = 0 improves information set decoding[END_REF], which seems to provide the best efficiency on the instances we consider (more recent algorithms improve over [START_REF] Becker | Decoding random binary linear codes in 2 n/20 : How 1 + 1 = 0 improves information set decoding[END_REF], but at the cost of large hidden constants that render them less practical, or only for very high noise rates). Putting everything together, a lower bound on the cost of ISD algorithm for a two-power cyclotomic F is given by

min 1≤i≤log N 0≤q≤n i 0≤p≤n i +q    min 2 n i , q i w i n i -q w i -p •   (n i -q) 2 log(n i -q) + (n i +q)/2 p/8 n i +q p + w i • (n i -q) 2 q      .
Statistical Decoding. By picking an optimal choice of i, a reducible R-LPN instance can be solved with a statistical decoding algorithm in time

O min 1≤i≤log N q i n i -1 w i • 2 i .
Changing the Structure of the Noise. In our analysis above, we rely on an estimation of the expected amount of noise after reduction modulo a 1-sparse factor f i of F . However, this ignores the possibility that, in some rare cases, the reduction modulo f i might lead to an instance with a much smaller amount of noise than the expected number, in which case the attacks above will work much more efficiently. We note that there is a natural approach to avoid these "weak parameters", by sampling the noise such that its reduction modulo any 1-sparse factor f i has weight at least the expected quantity t i . Typically, when F = X N + 1, the 1-sparse factors are all of the form X 2 i + c i , and sampling the noise in this way is very easy; one can for example use a simple rejection sampling approach. Note that it is sufficient to consider a single factor X 2 i + c i for the smallest i which the adversary can consider (typically, i = 6 or 7 in our instances), because reducing the noise modulo X 2 i + c i amounts to computing a linear combination of the consecutive length-2 i subvectors of the noise vector. Hence, reducing modulo any factor with a larger i amounts to computing a linear combination of concatenations of 2 i -i of these subvectors, which implies that the total noise cannot decrease more than when reducing modulo X 2 i + c i . Since a random noise vector will have more than t i noisy coordinates after reduction modulo f i with probability ≈ 1/2, this rejection sampling approach reduces by a single bit the total entropy of the noise vector.

We note that there might possibly be other, less sparse factors, which the adversary could use. For such factors, the sampled noise vector is not guaranteed to maintain a target expected number of nonzero coordinates after modular reduction. However, the noise reduction achieved by modular reduction comes from collisions between the noisy coordinates in the reduced instance, but this number of collision (as shown in our computation of the expected number t i of collisions) is typically quite small. On the other hand, reducing modulo a d-sparse factor increases the amount of noise by a factor d; when d > 1, we expect that this will systematically lead to an increased total amount of noise, and is not a viable adversarial strategy. Therefore, reductions modulo 1-sparse factors seems to be the main concern, and sampling the noise vector as we suggest eliminates the unlikely event of a weak noise with respect to one of these factors.

Algebraic Attacks on Fully-Reducible F

Another type of attacks are the algebraic attacks that exploit the structure of the underlying code. Many such algebraic decoding attacks have been devised in the literature, and fall in a unified framework developed in [START_REF] Pellikaan | On decoding by error location and dependent sets of error positions[END_REF][START_REF] Kotter | An unified description of an error locating procedure for linear codes[END_REF] of distinguishing attacks based on componentwise product of codes. Examples of such attacks include [PMCMM11,MCP12,FGUO + 13,CGGU + 13, MCMMP14] (and many more), and were often used to break some variants of the McEliece cryptosystem. Assume again that F (X) = X N + 1 is a 2-power cyclotomic polynomial, with N linear factors f i (X) = X + c i . In this setting, the generating matrix associated to

( s → a, s mod f i ) i≤N is of the form G = V • [Id N || -A 1 || • • • -A c-1 ]
, where V is a Vandermonde matrix (since Vandermonde matrices capture polynomial evaluation, and reducing a polynomial modulo a linear factor of the form X + c i is equivalent to evaluating the polynomial at c i ). Algebraic decoding attacks would allow to break the reducible R-LPN assumption if G is strongly multiplicative (roughly, G generates a strongly multiplicative code if the entry-wise product of each pairs of columns of G spans a vector space of dimension d < (cN ) 2 ). However, with G as above, it is easily seen that the pointwise products of pairs of columns of G span the whole F (cN ) 2 with overwhelming probability over the choice of A 1 , • • • , A c-1 , because the pointwise products of two columns in each A i are distinct to each other with overwhelming probability. Therefore, algebraic decoding attacks do not seem to apply to our LPN variant.

Attacks Using the Quasi-Cyclic Structure of the Code

When the underlying code has a quasi-cyclic structure, there is an additional attack which must be accounted for, which enhances the ISD family of attacks with a (c -1)N computational speedup: the DOOM (Decoding One Out of Many) attack [START_REF] Sendrier | Decoding one out of many[END_REF]. We note that the structure of our codes is not exactly a quasi-cyclic structure; however, they have a structure that closely resemble the structure of quasi-cyclic codes (e.g. when F = X N + 1, our code matrix is quasi-of e i . If any P i k returns 0, we abort and the adversary looses the game. Otherwise, we sens "success" to the adversary, and he can now attempt to distinguish whether he got a random vector or a noisy codeword.

As outlined in 5.3, R-LPN with static leakage can be reduced to R-LPN without leakage. However, this comes at a strong loss in the reduction, and updating parameters to reflect this reduction would decrease the efficiency of our schemes. While the resulting efficiency would still be acceptable, we observe that all the attacks described in this section do not perform significantly better against the R-LPN with static leakage assumption. The reason is that in all the attacks mentioned in this section, the choices made by the adversary when trying to distinguish b = A s + e from random (e.g. picking candidate non-noisy coordinates in the Gaussian elimination attack, or choosing low-weight parity-check vectors in the statistical decoding attack) are made independently of b. Therefore, in all these attacks, the success probability of the adversary can be computed by sampling the noise vector e after the adversary made his choices; indeed, this is exactly how we estimate the complexity of the attack in our asymptotic estimations.

This implies that, for all the above attacks, the success probability of the adversary can be obtained by fixing his choice of predicates P i k , his choice of attack parameters (e.g. candidate non-noisy coordinates in the Gaussian elimination attack, low-weight parity-check vectors in the statistical decoding attack) and computing p 0 p 1 with • the probability p 0 that all P i k return 1, over a random choice of e; • the probability p 1 that the attack succeeds when e is sampled conditioned on all P i k returning 1. However, the above probability is upper bounded by the probability that the attack succeeds for a random noise vector not conditioned on the output of the predicates. The takeway message is that any attack that selects its attack parameters without using b (but possibly using A and all other parameters of the system) cannot succeed better at breaking R-LPN with static leakage than at breaking the standard non-leaky R-LPN. In light of the fact that all known attacks that apply to our setting have this feature, it seems that, for the same parameters, R-LPN with static leakage offers the same concrete level of security as R-LPN without leakage.

Efficiency Analysis

In this section, based on our security analysis from Section 8, we discuss concrete choices of parameters for which the corresponding ring-LPN problems are secure against the attacks we considered. We then analyse the concrete efficiency of our PCGs in terms of seed size, communication complexity of the setup protocol, and estimated computational costs of seed expansion.

We focus on the case of a large finite field F = Z p , for a prime p with log p ≈ 128, as is commonly used in MPC implementations [START_REF] Keller | MASCOT: Faster malicious arithmetic secure computation with oblivious transfer[END_REF][START_REF] Keller | Overdrive: Making SPDZ great again[END_REF]. Further, for improved efficiency, we always choose the ring-LPN noise vectors to have a regular structure (as was done e.g. in [BCGI18, BCG + 19b, BCG + 19a]), which does not introduce any known weaknesses.

Estimating Attack Costs. For large fields, we focus on the statistical decoding and information set decoding (ISD) families of attacks (the latter being always at least as efficient as the Gaussian elimination attack), combined with the speedup obtained with the DOOM attack against quasi-cyclic codes. For statistical decoding, we compute our estimations with a conservative lower bound of n • (cN/(N -1)) w arithmetic operations. For ISD, we used the parameter estimation tool developed for the LEDA candidate [BBC + 19] in the NIST post-quantum competition 11 . This software takes as input the parameters (dimension, number of sample, number of noisy coordinates, block-size of the quasi-cyclic matrices) of the instance, and outputs the Table 1: Concrete parameters and seed size (per party, counted as equivalent number of field elements) for our PCG for OLE over Zp from reducible ring-LPN, where p = 1 mod 2N , log p ≈ 128, for various λ, N , syndrome compression factor c, and number of noisy coordinates w. 'Stretch', computed as 2N/(seed size), is the ratio between storing a full random OLE (i.e., 2N field elements) and the smaller PCG seed. #PRG calls is computed as 4 • N cw. Parameters are chosen to achieve λ-bits of security against known attacks (see Section 9.1 for the details on how the bit-security is estimated). This setting is useful for generating batches of N OLE correlations or authenticated triples over Zp, or small inner-product correlations (Section 7.2). See Section 9.1 for estimations of how to update the table for smaller field sizes. Irreducible Case. We consider a field F = Z p of size |F| ≈ 2 128 . We consider various choices of parameters (N, c, w), such that the time complexity of the best attack, with statistical decoding or any attack from the ISD family, takes time at least 2 λ (using all the optimizations discussed previously). As with the reducible case, our analysis in Section 8 (which may be too pessimistic) shows the statistical decoding attack to have the best complexity. The computational complexity of the expansion algorithm is dominated by c 2 multiplications over R, and 4N cw calls to a PRG for evaluating FullEval in the underlying SPFSS. The results are represented on Table 2. When using a smaller field F , the size of the seed, as it is counted as a number of group elements, grows roughly by a factor log 2 |F|/ log 2 |F |, the stretch and the number of PRG calls decrease by the same factor (e.g. about a factor 2 when using F with log 2 |F | ≈ 64, meaning that the running time for generating N OLEs over F decrease by a factor 2 compared to OLEs over F). The reduction in the number of PRG calls requires encoding multiple field elements into a PRG output; for example, using AES, a single PRG call produces 128 pseudorandom bits, which suffices to "pack" two elements over a 64-bit field using an appropriate encoding.

Compared with the reducible case in Table 1, notice that when N = 2 20 , using an irreducible F (X) allows the noise weight w to be around 10-40% smaller, for the same level of security. This saving is slightly more pronounced for larger N , since in the reducible version, an increase in N does not allow any reduction in the noise weight.

Table 2: Size of the seed (per party, counted as an equivalent number of field elements) for generating an OLE correlation over R = F[X]/F (X), where F is irreducible, log 2 |F| = 128 and deg F = N for various λ, N , syndrome compression factor c, and number of noisy coordinates w. 'Stretch' is computed as 2N/(seed size), and refers to the ratio between storing a full random OLE (i.e., 2N field elements) and storing the smaller seed. #PRG calls is computed as 4 • N cw. Parameters are chosen to achieve λ-bits of security against known attacks (see Section 9.1 for the details on how the bit-security is estimated). Note that increasing c always decreases the seed size, but increases the running time of the expansion algorithm. This setting is useful for generating large OLE correlations or authenticated triples over R, inner-product correlations (Section 7.2), or batch matrix product correlations (Section 7.4). See Section 9.1 for estimations of how to update the table for smaller field sizes. We now look more closely at the concrete costs of setting up and expanding the PCG seeds.

Here, we consider the task of producing N = 2 20 OLEs or triples over Z p , using reducible ring-LPN. (For smaller numbers of outputs, see the discussion in Section 9.3.)

Methodology. We estimate both the computational cost of expanding a PCG seed, as well as the communication cost required to distribute the PCG seeds with either passive or active security. When measuring communication, we do not include the one-time setup phase for bootstrapping the protocol with an initial batch of OLEs or multiplication triples (in practice, these can be created with a non-PCG based protocol such as ring-LWE).

For computation, the main costs in the expansion step are the DPF full-domain evaluations, and polynomial operations over R p . We separately benchmarked these using the DPF code from [BCG + 19a], and NFLLib [ABG + 16] for polynomial arithmetic with a 124-bit modulus p, which is a product of two 62-bit primes (such that R p splits completely into linear factors, by the CRT). The benchmarks were run on a single core of an Intel i7-7600U 2.8GHz processor.

To estimate the communication complexity of setting up the seeds, we first assume that as a one-time setup, the parties already have access to a single pair of PCG seeds (for multiplication triples). We then measure the cost of bootstrapping this to produce another seed, based on the analysis from Section 6.3.

Cost Estimates for N = 2 20 Correlations. The results are in Table 3 for OLE, and Table 4 for authenticated triples. Note that compared with Table 1, the noise weight w has been rounded so it is divisible by c, so that t = w/c is an integer. We see that as the module-LPN compression factor c increases, the polynomial arithmetic gets more expensive, while the DPF cost first decreases at c = 4, and then goes back up at c = 8. This is because the DPF complexity scales with c 2 t, so doubling c only reduces its cost if t can be reduced by more than a factor of 4. The best choice for speed seems to be c = 4, where we are able to silently expand over 100 thousand OLEs per second at the 128-bit security level, with a seed size of around 1MB. When generating authenticated triples instead of OLEs, the seed size and runtimes increase by roughly a factor of two, while the setup communication cost is only slightly larger.

Comparison with OLE From Ring-LWE

In Table 5, we compare the cost of our OLE protocol from ring-LPN with the passively secure OLE protocol from ring-LWE by Baum et al [BEPU + 20]. For a 120-bit plaintext modulus, the protocol implemented in [BEPU + 20] has an average communication cost of 420 bits per party, for each OLE. Excluding the one-time setup, our ring-LPN based protocol with c = 4 improves upon the communication complexity of ring-LWE when producing N = 65536 or more OLEs. With c = 2, when N is 32768 or 65536, the ring-LPN protocol requires more OLEs as preprocessing than it produces as output, so is not beneficial; instead, the asymptotic improvement in communication starts to take effect when N is half a million or more.

PCG for OLE from Standard LPN

In this section, we provide new constructions of PCG for OLE and matrix product correlations. Unlike the other PCG constructed in this work, the PCGs of this section do not rely on the R-LPN assumption, but on the standard LPN assumption (or alternatively, some variant of it with a structured parity-check matrix H allowing for fast multiplication with H). The PCG for OLE we obtain is typically less efficient than those based on R-LPN, but rely on more

Construction G bil

Parameters: 1 λ , m, n, t, ∈ N, where n > m; a field F. A parity-check matrix H ∈ F m×n for a code of dimension n -m and number of samples m over F. A bilinear function B c : F n × F n → F, ( α, β) → c, ( α ⊗ β) .

Gen: On input 1 λ :

1. Pick two random sparse vectors e 0 , e 1 $ ← F n with wt( e 0 ) = wt( e 1 ) = t. Define f to be the sum of t 2 point functions whose evaluation on its entire domain is e 0 ⊗ e 1 .

2. Compute (K 0 , K 1 ) $ ← SPFSS.Gen(1 λ , f ).

3. Let k 0 ← (K 0 , e 0 ) and k 1 ← (K 1 , e 1 ).

4. Output (k 0 , k 1 ).

Expand: On input (σ, k σ ), parse k σ as (K σ , e σ ). Set x σ ← H • e σ . Compute u σ ← SPFSS.FullEval(σ, K σ ) in F n 2 p , and set z σ ← c, (H ⊗ H) • u σ . Output ( x σ , z σ ). The tensor product between noise vectors e 0 ⊗ e 1 is compressed using SPFSS. Then, the O(n 4 ) overhead comes from multiplying this length-n 2 vector with an m 2 × n 2 matrix. However, computing the above can be done much more efficiently by observing that the n × n square matrix x 0 • x 1 contains exactly the same entries as the tensor product between x 0 and x 1 . Hence, any bilinear function of ( x 0 , x 1 ) can be trivially computed as a linear combination between the components of x 0 • x 1 . Furthermore, we can compute x 0 • x 1 much more efficiently using the following identity:

x 0 • x 1 = (H • e 0 ) • (H • e 1 ) = H • ( e 0 • e 1 ) • H .
As before, e 0 • e 1 can be generated from an O(t 2 log n)-long seed using SPFSS. But now, computing H • ( e 0 • e 1 ) • H requires only O(n ω ) operations, where ω is the matrix multiplication exponent. Furthermore, if H is a structured matrix, this can be computed even more efficiently; for example, taking H to be a Toeplitz matrix or a quasi-cyclic matrix leads to a computation cost of O(n 2 log n) for generating m = O(n) OLEs, under well-established variants of the LPN assumption. This provides a less efficient, but still feasible more conservative alternative to our construction based on the splittable variant of R-LPN. Hence, we directly get: Theorem 10.2 Suppose the dual-LPN m,n,t assumption holds relative to random Toeplitz matrices, and that SPFSS is a secure SPFSS scheme. Then the construction described in this section is a secure PCG for general bilinear correlations with seeds of size Õ(t 2 log n) field elements over a large field (log 2 |F| = O(λ)). Expanding the seed involves O((tn) 2 ) PRG evaluations and O(n 2 log n) arithmetic operations.

3. Let k 0 ← (K 0 , e 0 ) and k 1 ← (K 1 , e 1 ).

4. Output (k 0 , k 1 ).

Expand: On input (σ, k σ ), parse k σ as (K σ , e σ ). Set X σ ← mat(H • e σ ). Compute U σ ← SPFSS.FullEval(σ, K σ ) in F n 2 ×n 2 and set

Z σ ← m i=1 H i • U σ • H i .
Output (X σ , Z σ ).

Security follows from the same argument as previously. For correctness, note that by definition we can write

X σ = [H 1 • e σ | • • • | H m • e σ ], which implies X 0 • X 1 = m i=1 H i • e 0 • (H i • e 1 ) = m i=1 H i • ( e 0 • e 1 )
• H i and thus correctness follows.

The seed size is now much smaller, O(t 2 log n); however, the computational complexity is dominated by the matrix product H • U σ , which takes time O(n 4 log n) if H is a structured matrix. This provides a much better tradeoff than when generating OLEs: the cost of generating m = O(n) OLEs with (our improved version of) G bil is Õ(n 2 ), quadratically larger than the cost of generating them in the clear. However, the cost of generating a large random matrix multiplication correlation is M (n) = O(n ω ), meaning that the cost of our algorithm is below O(M √ M ) when the matrix multiplication algorithm is implemented with e.g. Strassen's algorithm.

Definition 2. 2 (

 2 Distributed Point Function (DPF) [GI14, BGI15]) For an Abelian group G, α ∈ [n], and β ∈ G, the point function f α,β is the function f α,β : [n] → G defined by f α,β (x) = 0 whenever x = α, and f α,β (x) = β if x = α. A distributed point function (DPF) is an FSS scheme for the class of point functions {f α,β :

Figure 1 :

 1 Figure 1: PCG for OLE over the ring Rp, based on ring-LPN

Figure 2 :

 2 Figure 2: PCG for authenticated triples over the ring Rp, based on Ring-LPN

Figure 3 :

 3 Figure 3: Functionality F 2-PC and extended functionality F ext-2-PC for reactive 2-PC over Fq and F2

Figure 4 :

 4 Figure 4: Functionality for semi-honest setup of a distributed point function. Here, we parse α ∈ [0..D) as bit-string α ∈ {0, 1} log 2 D , and assume to be given a secret sharing of α over F log 2 D 2

Functionality

  F c-SUV Parameters: Length D ∈ N, and a prime modulus p Functionality: The functionality contains the same Input, Add, Mult and Output commands as F 2-PC , as well as the following command. SUV: On input α F log D 2 and β Fq : If both parties are honest:

Figure 5 :

 5 Figure 5: Functionality for the malicious distributed setup of a scaled unit vector

Figure 6 :

 6 Figure 6: Protocol for the malicious distributed setup of scaled unit vectors (Part I)

Figure 6 :

 6 Figure 6: Protocol for the malicious distributed setup of scaled unit vectors (Part II)

FunctionalityF

  OLE-Setup Parameters: Security parameter 1 λ , PCG OLE = (PCG OLE .Gen, PCG OLE .Expand) as per Figure 1. Functionality:

Figure 7 :

 7 Figure 7: Generic functionality for the distributed setup of OLE PCG seeds

Figure 8 :

 8 Figure 8: Distributed setup of PCG seeds for OLE in the (F 2-PC , F DPF )-hybrid model, against semi-honest adversaries. x F 2 , x p denote additive shares of bit-strings or Fp elements.

Figure 9 :

 9 Figure 9: Corruptible OLE Functionality

Figure 10 :

 10 Figure 10: PCG protocol securely implementing the corruptible OLE functionality

Figure 11 :

 11 Figure 11: Corruptible functionality for authenticated triples

Figure 12 :

 12 Figure 12: PCG protocol implementing the corruptible functionality for authenticated triples (Part I)

• malicious: 3

 3 multiplication triples + 2× length-(2 + 2) vector-OLE (both over Z p ) Computation: Computation is dominated by 2D PRG evaluations. Communication: Communication (per party) is dominated by: • (2λ + 3) log D + 5 log p bits • malicious: extra (4 + 2) log p bits Cost of distributed setup. The complexities of our protocol Π OLE-Setup (Fig. 8/ Π mal-OLE (Fig. 10 implementing F OLE-Setup (semi-honest)/ F mal-OLE (malicious) to produce N OLEs are as follows:

Theorem 6. 6 (

 6 Authenticated Triples Distributed Generation) Assuming hardness of the R c -LPN p,1,t assumption (Def. 3.2), there exists a protocol securely realizing functionality F mal-triple to produce N authenticated triples against malicious adversaries with the following complexity: Correlated randomness: Consuming correlated randomness in the form of: 1. 4ct log N correlated OTs + 2× length-2ct vector-OLE (in Z p ) 2. & 4. 54(ct) 2 log N bit OTs + 2(ct + (ct) 2 ) authenticated triples over Z p 3. & 5. 6(2ct + (ct) 2 ) authenticated triples over Z p + 2× length-6(2ct + (ct) 2 ) vector-OLE over Z p Computation: Computation is dominated by 2(2ct + (ct) 2 )N PRG evaluations. Communication: Communication (per party) is dominated by: 1. 2ct(log N + log p) bits 2. & 4. 34(ct) 2 log N + 4(ct + (ct) 2 ) log p bits 3. & 5. (2ct + (ct) 2 ) • ((2λ + 3) log(2N ) + 10 log p) bits

  λ

  Given parameters (λ, N, c, w), our PCG for generating one pseudorandom OLE correlation over R has seeds of size equivalent to w • (1 + log N/ log |F|) + w 2 • ((log N + 1)(λ + 2) + λ + log |F|)/ log |F| elements of F. When the error distribution is regular, the seed size can be reduced to w • (1 + log N/ log |F|) + w 2 • (log(2N c/w) • (λ + 2) + λ + log |F|)/ log |F|.

  # R-mults #PRG calls

Figure 14 :

 14 Figure 14: PCG for Bilinear Correlations

  N c w (i, w i ) Seed size Stretch # R-mults #PRG calls

	80 2 20 2 97 (6, 74) 2 17.4	12	4	2 29.6
	80 2 20 4 40 (6, 37) 2 15.0	65	16	2 29.3
	80 2 20 8 26 (6, 25) 2 13.9	139	64	2 29.7
	128 2 20 2 152 (7, 121) 2 18.6	5	4	2 30.2
	128 2 20 4 64 (7, 60) 2 16.3	27	16	2 30.0
	128 2 20 8 41 (7, 40) 2 15.1	59	64	2 30.4
	80 2 25 2 97 (6, 74) 2 17.7	306	4	2 34.6
	80 2 25 4 40 (6, 37) 2 15.3	1654	16	2 34.3
	80 2 25 8 26 (6, 25) 2 14.2	3623	64	2 34.7
	128 2 25 2 152 (7, 121) 2 19.0	130	4	2 35.2
	128 2 25 4 64 (7, 60) 2 16.6	673	16	2 35.0
	128 2 25 8 41 (7, 40) 2 15.4	1513	64	2 35.4

Table 3 :

 3 Estimated costs for our PCG for producing N = 2 20 OLEs in Zp, with log p ≈ 124. Seed size is the size of one party's seed, setup comm. measures the per-party communication required to setup the PCG seeds (ignoring costs for correlated randomness that can come from a previous PCG).

	λ	c	w	Seed size (MB)	Setup comm. (MB)		Runtimes for Expand (s)
					passive	active	R-mult (s) DPF eval. (s) Total (s)
	80	2	96	2.69	6.14	6.69	0.4	9.8	10.2
	80	4	40	0.52	1.17	1.28	1.4	7.5	8.9
	80	8	32	0.35	0.78	0.86	5.3	9.3	14.6
	128 2 152	6.37	14.63	15.92	0.4	12.6	13.0
	128 4	64	1.26	2.86	3.12	1.4	8.6	10.0
	128 8	40	0.55	1.22	1.34	5.3	14.4	19.7

Table 4 :

 4 Estimated costs for our PCG for producing N = 2 20 authenticated triples in Zp, with log p ≈ 124. Seed size is the size of one party's seed, setup comm. measures the per-party communication required to setup the PCG seeds (ignoring costs for correlated randomness that can come from a previous PCG).

	λ	c	w	Seed size (MB) Setup comm. (MB)	Runtimes for Expand (s)
						R-mult (s) DPF eval. (s) Total (s)
	80	2	96	5.49	8.77	0.8	19.6	20.4
	80	4	40	1.09	1.68	2.8	15.0	17.8
	80	8	32	0.74	1.13	10.6	18.6	29.2
	128 2 152	12.91	20.97	0.8	25.2	26.0
	128 4	64	2.60	4.09	2.8	17.2	20.0
	128 8	40	1.14	1.75	10.6	28.8	39.4

An OLE correlation over a finite field F is a two-party correlation (r0, r1) where r0 = (a, b) is uniform over F

and r1 = (x, ax + b) for x ∈R F.

Our construction works in any sufficiently large finite field, or modulus that is a product of primes via the CRT. We estimated costs with a product of two primes due to better software support.

Note that this corresponds to a distributed point function where we do not require the key setup on its own to be secure, but only require the protocol to securely implement the FSS functionality including expansion, as this suffices for using PCGs in the context of secure computation (see also[BCG + 19a]).

In fact, the leakage can be characterized by predicates corresponding to bit-matching with wildcards.

Or, two samples if security is based on ring-LPN with a uniform (not sparse) secret.

This can be reduced to N/2, by defining a, b to be the first N/2 coefficients of the polynomials x0, x1 produced by the OLE, so that only the second half of the coefficients need to be sent in the multiplication protocol.

In the notation of [Ds17, Fig.1], whenever τ j,0 = τ j,1 ⊕ 1, you can read off αj by XORing τ j,1 with LSB(σ j ).

The original version of this paper used a hash-based consistency check similar to [BCG + 19a], however, as observed by Damiano Abram, that check was not sufficient in this setting.

Given a triple a , b , c with c = ab, first open x + a, then compute xb = (x + a) b -c , open xb and finally compute z = b (xb) -1 .

For example, if c is a square root of -1 modulo p (which exists, since with two-power cyclotomics, p ≡ 1 mod 4) then X N + 1 = (X N/2 + c)(X N/2 -c).

https://github.com/LEDAcrypt/LEDAtools

Acknowledgements

We would like to thank Vadim Lyubashevsky, Chris Peikert, Ronny Roth and Jean-Pierre Tillich for helpful discussions and pointers. We also thank Damiano Abram for various corrections, including pointing out a security flaw in a previous version of the malicious DPF protocol. E. Boyle, N. Gilboa, and Y. Ishai supported by ERC Project NTSC (742754). E. Boyle additionally supported by ISF grant 1861/16, AFOSR Award FA9550-17-1-0069, ERC Project HSS (852952), and a Google Research Award. G. Couteau supported by ERC Project PREP-CRYPTO (724307) and ANR SCENE. N. Gilboa additionally supported by ISF grant 1638/15, ISF 2951/20, ERC grant 876110, and a grant by the BGU Cyber Center. Y. Ishai additionally supported by NSF-BSF grant 2015782, BSF grant 2018393, ISF grant 2774/20, and a grant from the Ministry of Science and Technology, Israel and Department of Science and Technology, Government of India. L. Kohl is funded by NWO Gravitation project QSC. Most research of L. Kohl was done while at Technion, supported by ERC Project NTSC (742754). Research of L. Kohl was done in part while at Karlsruhe Institute of Technology, supported by ERC Project PREP-CRYPTO (724307) and DFG grant HO 4534/2-2. P. Scholl supported by the Danish Independent Research Council under Grant-IDs 6108-00169 (FoCC) and 0165-00107B (C3PO), and an Aarhus University Research Foundation starting grant.

Finally, the simulator forwards x σ := a, e σ mod F (X) and z σ := a ⊗ a, g σ mod F (X)

to the functionality. We conclude the proof by showing that an adversary A distinguishing the simulated protocol execution from a real execution can be turned into an adversary B on the module-LPN assumption with static leakage. Adversary B proceeds exactly as the simulation until the point, where it receives the predicate guesses P i,j k,l from the adversary within the call of F c-SUV . Instead of choosing A 0 , . . . , A c-1 $ ← [0..N ) t , b 0 , . . . , b c-1 $ ← Z t p \{0}, for each i, j ∈ [0..c), k, l ∈ [0..t) the simulator defines the predicate Q i,j k,l : [0..N ) → {0, 1} via Q i,j k,l (A) = 0, iff P i,j k,l (A + A j σ [l]) = 0 and forwards indices i, k and predicate Q i,j k,l to the module-LPN game. If the game aborts on some index i , j ∈ [0..c), k , l ∈ [0..t), B samples A 0 , . . . , A c-1 $ ← [0..N ) t such that Q i ,j k ,l (A i [k ]) = 0 and Q i,j k,l (A i [k]) = 1 for all previously queried tuples (i, j, k, l). Further, B samples b 0 , . . . , b c-1 $ ← Z t p \{0}, returns

) to A and aborts. Note that B can sample A 0 , . . . , A c-1 as required by sampling fresh tuples A 0 , . . . , A c-1 $ ← [0..N ) t until the predicates take the values as required. For all events that happen with noticeable probability, this yields an adversary in expected polynomial time.

If the module LPN game does not abort, B receives u ∈ R p from the experiment and sets x 1-σ := u. The adversary B computes z 1-σ = x 0 • x 1 -z σ (where x σ and z σ are computed as in the simulation). Finally, B outputs 0 if and only if the adversary A returns "real".

Note that in case b = 0 (i.e. the module-LPN game returns a real module-LPN sample), adversary B simulates the real protocol execution except with negligible probability: First, note that the probability that the adversary gets any of the guesses B to the functionality F c-SUV right is negligible, since p is superpolynomial and |B| ≤ 2N . Next, observe that the output distribution simulated by B corresponds to the real output distribution, and the module-LPN game aborts if and only if the functionality F c-SUV would have aborted on at least one of its calls. Therefore, B simulates the real protocol execution except with negligible probability. In case b = 1, B perfectly simulates the simulation, since the probability that the module-LPN game aborts equals the probability that the simulation aborts in an ideal execution. This concludes the proof.

Distributed generation of authenticated multiplication triples in the malicious setting. We finally present the distributed setup for our PCG protocol to generate authenticated multiplication triples Π mal-triple (Fig. 12). To additionally generate shares of the MACs, the protocol uses F DPF with outputs in F 2 p ; this can be done using the modification in Remark 5.2. Note that the corruptible functionality F mal-triple (similar to F c-SUV ) gives the adversary full control over its share of the output. Recall that this is sufficient to use our PCG construction as a "plug-in" replacement in a wide range of natural MPC protocols that use correlated randomness, such as [START_REF] Damgård | Multiparty computation from somewhat homomorphic encryption[END_REF]. As the proof of the following is very similar to the proof of Theorem 6.3, we omit it here. Theorem 6.4 Let R = Z p [X]/F (X) for some prime p and degree-N polynomial F (X) ∈ Z[X], and let c, t ∈ N. If the R c -LPN p,t problem with static leakage is hard, then the protocol Π mal-triple (Fig. 12) implements the functionality F mal-triple (Fig. 11) with security against malicious adversaries in the F 2-PC , F c-SUV -hybrid model.

Construction G prog bil

Parameters: Security parameter 1 λ , a programmable PCG (PCG f .Gen, PCG f .Expand) for the simple bilinear correlation C n f with programmibiliy maps

T has an f -decomposition with parameters (γ, α 1 , . . . , α γ , β 1 , . . . , β γ , W ). Correlation: C n g produces n instances of the simple bilinear correlation for g. That is,

, where by

we denote the transpose of the map g applied to X 0 and X 1 row-wise.

Gen: On input 1 λ : 1. Sample random ρ 1 0 , . . . , ρ u 0 and ρ 1 1 , . . . , ρ v 1 according to the programmability property of PCG f . // This choice will define the j-th column of X 0 as φ 0 (ρ j 0 ) for all j ∈ [u], and the k-th column of

2. Sample a PRG seed k prg ← {0, 1} λ .

3. For i = 1, . . . , γ, sample seeds (k i 0 , k i 1 ) ← PCG f .Gen(1 λ , ρ α i 0 , ρ β i 1 ).

Output k

Expand: On input (σ, k σ ):

, where A j = R i 0 for some i where α i = j (if more than one α i matches, pick arbitrarily) a 3. If σ = 1, define the matrix

, where B j = R i 1 for some i where

a Note that such an αi always exists, otherwise g would be degenerate. Further, if αi = α i = j, then k i 0 and k i 0 were sampled using the same seed ρ j 0 , and thus R i 0 = R i 0 = φ0(ρ j 0 ) by programmability of PCG f . Figure 13: PCG for general bilinear correlations defined by the map g Lemma 7.6 (Multi-instance programmability) Let PCG = (PCG.Gen, PCG.Expand) be a programmable PCG as in Definition 7.2. Then, for any d = poly(λ), the distributions

are computationally indistinguishable. A symmetric property holds for k i 0 .

Proof. This follows a standard hybrid argument, where the reduction loses a factor of d in advantage. In the j-th hybrid, pick randomness ρ 0 , ρ i 1 ← $ and for i ≤ j also ρi 0 ← $, for i ≤ j compute the key as

, and for i > j compute the key as

Given a distinguisher for any two hybrids j and j + 1, it is straightforward to construct a distinguisher for the programmable security property of PCG, with the same advantage.

Theorem 7.4 Let f and g be bilinear maps as above, and suppose that g has a simple fdecomposition with f -complexity n f (g). Furthermore, let PCG f = (PCG f .Gen, PCG f .Expand) be a programmable PCG for C n f . Then there exists a programmable PCG PCG g = (PCG g .Gen, PCG g .Expand) for C n g , with the following properties:

• PCG g .Gen runs n f (g) executions of PCG f .Gen, and its key sizes are n f (g) times that of PCG f .

• PCG g .Expand runs n f (g) executions of PCG f .Expand, and n evaluations of the linear map W from the f -decomposition of g.

Proof.

We give an explicit consturction of PCG g in Figure 13. We consider separately the correctness and security properties of the PCG definition.

Correctness. Let (X 0 , Y 0 ) and (X 1 , Y 1 ) be a pair of outputs from PCG g .Expand. Let φ 0 , φ 1 be the programmibility maps, and ρ 1 0 , . . . , ρ u 0 and ρ 1 1 , . . . , ρ v 1 as chosen by Gen on input

Then, by the programmibility property of PCG f it holds that (R 1 0 , . . . , R γ 0 ) = (A α 1 , . . . , A αγ ) and (R 1 1 , . . . , R γ 1 ) = (B β 1 , . . . , B βγ ) with overwhelming probability. Also, by construction in PCG g , we have X 0 = (A 1 . . . A u ) and X 1 = (B 1 . . . B v ). From the correctness of PCG f , with overwhelming probability

where f is considered to be applied entry-wise to the inputs. Furthermore, X 0 and X 1 are both pseudorandom by the correctness property of PCG f , and any individual Y σ is pseudorandom due to the security of PRG; hence, the outputs of PCG g are computationally indistinguishable from random outputs of the correlation C n g .

Programmability. The programable randomness can be defined as ρ 0 = (ρ 1 0 , . . . , ρ u 0 ) and ρ 1 = (ρ 1 1 , . . . , ρ v 1 ). The programmability maps are defined by applying φ 0 and φ 1 for PCG f componentwise. The programmability property then follows directly from the programmability of PCG f . Programmable Security. We first consider the case σ = 1. Recall that by Lemma 7.4 programmable security together with correctness and programmability automatically implies standard PCG security. We need to show indistinguishability of the two distributions

and

. We use a hybrid argument, where the j-th experiment is as follows.

Hybrid distribution D 0 . Give out (k 1 , (ρ 0 , ρ 1 )) as computed in the actual construction.

Hybrid distribution D j , for j = 1, . . . , u. Sample randomness ρ 1 0 , . . . , ρ u 0 , ρ 1 1 , . . . , ρ v 1 as in the construction, as well as random ρ1 0 , . . . , ργ

Note that D 0 is identical to D real and D u is identical to D sim . It is left to consider the difference between hybrids D j and D j+1 . For any i ∈ [γ] such that α i = j + 1, in hybrid distribution D j+1 we use fresh randomness ρi 0 to sample k i 1 , whereas in D j we use the real randomness ρ α i 0 . However, any adversary who distinguishes these can be used to break the multi-instance security property (Lemma 7.6) of the programmable PCG, where the d keys are defined to be those of the indices where α i = j + 1. Finally, notice that the case of σ = 0 proceeds symmetrically, with a sequence of v hybrids argued in the same way.

Application: Matrix Multiplication Triples

We can use the general bilinear construction to build a PCG for generating a large batch of matrix multiplication triples. For matrices of dimensions n 1 × n 2 and n 2 × n 3 , the PCG seed size is around n 1 • n 3 times larger than the PCG for OLE. This means it will likely be practical for small-to-medium matrices.

Let g : Z n 1 ×n 2 p ×Z n 2 ×n 3 p → Z n 1 ×n 3 p be the matrix multiplication map, and let f : Z n 2 p ×Z n 2 p → Z p be the inner product map over Z p . These maps fit the requirements of Theorem 7.4, by using

• n 3 and appropriately flattening matrices into one-dimensional vectors.

Multiplication of n 1 × n 2 and n 2 × n 3 matrices is easily decomposed as a sequence of n 1 • n 3 inner products of length n 2 , where each inner product is taken from a consecutive portion of the two inputs. This shows that the matrix multiplication map g has a linear f -decomposition with f -complexity n 1 • n 3 .

To obtain a PCG for g, we use the PCG for the length-n 2 inner product correlation f , which can be based on R-LPN when F (X) splits into degree-n 2 factors (Corollary 7.3).

Corollary 7.7 Suppose R-LPN p,1,t holds for R = Z p [X]/F (X), where F (X) is degree N and splits into N/n 2 distinct factors of degree n 2 . Then there is a PCG for producing n = N/n 2 correlations for (n 1 × n 2 ) × (n 2 × n 3 ) matrix multiplication over Z p . The PCG requires n 1 • n 3 copies of the PCG for n inner products of length n 2 , and has seed size and computational cost around n 1 • n 3 times that of the PCG for inner product. cyclic up to the fact that the odd-numbered blocks are multiplied by a factor -1). Therefore, even though we are not aware of an extension of the DOOM attack to the kind of structured codes we consider, we assume to be conservative that the DOOM attack can be extended to work in our setting, and take into account the corresponding speedup for the ISD attacks in our estimations. Similarly, when F is reducible, we assume that the DOOM attack speeds up the ISD attacks by a √ n i factor over the reducted instance of dimension n i .

Attacks over Small Fields

In this section, we assume the F = F 2 , which is the setting we consider in our applications that rely on R-LPN small fields. The attack we describe works also over larger fields, but performs more poorly, since it requires to brute-force over all possible secrets. A natural approach to attack R-LPN over a small field is to brute-force over all possible choices of s ∈ HW c-1 w/c . For each candidate vector s, the attacker checks whether a, s + b is a regular w/c-sparse vector. The number of sparse secrets from HW c-1 w/c over F 2 is

, and grows to

|F|-1 over arbitrary fields. Each a, s for some candidate secret s requires O((c-1)•N log N ) multiplications over F, hence the running time of the attack is lower bounded by

Note that when F = F 2 , the smallest integer d such that 2 d = 1 mod m (where m is such that φ(m) = N , i.e., F is the m-th cyclotomic polynomial) is at least log N , hence F splits into at most N/d factors and when this is the case,

When applying the brute-force attack to a reduced instance, the cost grows as

Since N will be very large (e.g. about 2 20 ) in our instantiations, this attack is never feasible.

Improved Small Field Attacks. We note, however, that when F = F 2 and F is reducible, one can significantly refine the naive brute-force attack which we described above. Since this setting is exactly the setting of the Lapin authentication protocol [HKL + 12], which is perhaps the flagship application of R-LPN, it has been the subject of extensive cryptanalysis in [START_REF] Daniel | Never trust a bunny[END_REF][START_REF] Guo | A new algorithm for solving ring-lpn with a reducible polynomial[END_REF], which managed to break some candidate parameters of the original proposal. We will not cover their attacks in detail, but note that parameters which were conjectured to provide 80 bits of security in the original proposal (where the estimation was based on standard attacks on LPN, ignoring the ring structure), were shown to provide only 70 bits of security in [START_REF] Guo | A new algorithm for solving ring-lpn with a reducible polynomial[END_REF]. Therefore, when using F = F 2 and a reducible F , the state-of-the-art attack of [START_REF] Guo | A new algorithm for solving ring-lpn with a reducible polynomial[END_REF] should be taken into account and the security margin must be increased by at least a comparable factor.

Attacks on R-LPN with Static Leakage

Eventually, our malicious distributed setup protocol in Section 5.3 relies on the R-LPN assumption with static leakage (Definition 6.2). In this variant, security is based on the following game: after the c noise vectors e 0 , • • • e c-1 sampled, the adversary is allowed to submit c • t arbitrary predicates P i k : [0, N ) → {0, 1}, where P i k takes as input the position of the k-th nonzero entry complexity of attacking the instance with several ISD variants, namely those of Prange [START_REF] Prange | The use of information sets in decoding cyclic codes[END_REF], Lee and Brickell [START_REF] Pil | An observation on the security of mceliece's public-key cryptosystem[END_REF], Leon [START_REF] Jeffrey S Leon | A probabilistic algorithm for computing minimum weights of large error-correcting codes[END_REF], Stern [START_REF] Stern | A method for finding codewords of small weight[END_REF], Finiasz and Sendrier [START_REF] Finiasz | Security bounds for the design of codebased cryptosystems[END_REF], May, Meurer, and Thomae [START_REF] May | Decoding random linear codes in Õ(2 0.054n )[END_REF], and Becker, Joux, May, and Meyer [START_REF] Becker | Decoding random binary linear codes in 2 n/20 : How 1 + 1 = 0 improves information set decoding[END_REF], while taking into account the speedup of the DOOM attack when the code is quasi-cyclic. Furthermore, observing that the C++ code of the software implements matrix inversion using standard (cubic time) Gaussian elimination, we modified the matrix inversion used in the code to account for polynomial speedups obtained by using fast (quasi-quadratic time) algorithms for inversion of structured matrices.

Comparing Reducible and Irreducible Ring-LPN

We start by comparing parameters for the PCGs based on the reducible and irreducible variants of ring-LPN. Recall that in the reducible case, F (X) splits completely into linear factors modulo p, so we can obtain OLEs or triples over Z p (or an extension field F p d ). To improve computational efficiency, we use the cyclotomic polynomial F (X) = X N + 1, for N a power of two. In the case where F (X) is irreducible, we only produce a single, large OLE/triple over Z p [X]/F (X).

Reducible Ring-LPN Parameters. We consider a field F = Z p of size |F| ≈ 2 128 . As in our applications, we focus on the case where there is a factor f i of degree n = N/k, for some k, which has sparsity 1, such as when N is a power of two and F (X) = X N + 1 splits completely into N linear factors modulo p. From the analysis in Section 8.2, we can reduce an instance modulo a 1-sparse factor f i of degree n = 2 i , reducing the expected number of noisy coordinates to

, the dimension to n i = (c-1)•2 i , and the number of samples to q i = c•2 i . In our experiments, we found that the optimal behavior for the adversary was always to pick the smallest i such that the new weight w i of the noise is not higher than the dimension n i (such that the reduced instance is still uniquely decodable and is not statistically close to random). For security parameter λ = 80 (resp. λ = 128), the smallest such i is i = 6 (resp. i = 7). In Table 1, we provide various choices of parameters (λ, N, c, w) such that the best attack on any reduced instance requires at least 2 λ multiplications over a field F of size |F| ≈ 2 128 . Observe that increasing N does not allow increasing the noise weight, since the best attack always exploits the structure of F (X) by reducing to a much smaller dimension. The table also presents the concrete seed sizes and computational requirements for our PCG for OLE, based on Theorem 4.1 (and with optimizations due to the regular error distribution).

Our conservative estimates of the running time of the statistical decoding attack have better asymptotic complexity than the ISD attacks, according to our analysis in Section 8; and indeed, we found statistical decoding to always give the best available attack. Given that statistical decoding should not generally perform better than ISD [START_REF] Debris | Statistical decoding[END_REF], this suggests that our estimation of the cost of statistical decoding might be overly conservative, meaning that our parameters might be slightly pessimistic. When using a smaller field F , the parameters in Table 1 change as follows: the size of the seed, as it is counted as a number of group elements, grows roughly by a factor log 2 |F|/ log 2 |F |, the stretch and the number of PRG calls decrease by the same factor (e.g. about a factor 2 when using F with log 2 |F | ≈ 64, meaning that the running time for generating N OLEs over F decrease by a factor 2 compared to OLEs over F). The reduction in the number of PRG calls requires encoding multiple field elements into a PRG output; for example, using AES, a single PRG call produces 128 pseudorandom bits, which suffices to "pack" two elements over a 64-bit field using an appropriate encoding. ], over an arbitrary field F, which we recall below. In [BCG + 19b], this construction was estimated to be mainly of theoretical interest: generating m = O(n) OLEs with this PCG requires O(n 4 ) arithmetic operations, and a seed of size O(t 2 log n). When n is large enough for the seed to provide a nontrivial compression factor, the computational overhead is already impractical. In this section, we will give an optimized variant of this construction which requires O(n ω ) arithmetic operations, where ω is the matrix multiplication exponent. This cost can be further reduced to O(n 2 log n) by relying on any variant of LPN with structured parity-check matrices allowing for fast (o(n 2 )) matrix-vector products, such as a Toeplitz or a quasi-cyclic parity-check matrix.

The Construction of [BCG + 19b]

Theorem 10.1 (From [BCG + 19b], Section 6) Suppose the dual-LPN m,n,t assumption holds relative to H, and that SPFSS is a secure sum of point function secret sharing scheme. Then the construction G bil (Fig. 14) is a secure PCG for general bilinear correlations.

Efficiency. Instantiating the SPFSS as in [START_REF] Boyle | Compressing vector OLE[END_REF], the setup algorithm of G bil outputs seeds of size t 2 • ( log n (λ + 2) + λ + log 2 |F|) bits, which amounts to Õ(t 2 log n) field elements over a large field (log 2 |F| = O(λ)). Expanding the seed involves (tn) 2 PRG evaluations and O(m•n) 2 = O(n 4 ) arithmetic operations.

Optimized Construction

The main source of inefficiency in the above construction stems from the fact that to compute a bilinear function of two (pseudo)random strings, the expansion algorithm must obtain the tensor product between the pseudorandom strings ( x 0 , x 1 ). In the construction, it holds that x σ = H • e σ for σ = 0, 1

LPN-Based PCG for Matrix Multiplication

In this section, we describe two new variants of the PCG described in the previous section, which allow to generate large matrix multiplication triples over F (with different parameters tradeoffs across the two constructions).

First Construction. The first construction directly generalizes the construction above to generating pseudorandom correlations (X 0 , Z 0 ) ∈ F m×m × F m×m and (

Parameters: 1 λ , m, n, t, p ∈ N, where n > m. A parity-check matrix H ∈ F m×n for a code of dimension n -m and number of samples m over F.

Gen: On input 1 λ : 1. Pick two random matrices E 0 , E 1 ∈ F n×m such that each column of E 0 , E 1 contains exactly t nonzero entries.

2. Compute SPFSS keys (K 0 , K 1 ) which generate shares of E 0 • E 1 .

3. Let k 0 ← (K 0 , E 0 ) and k 1 ← (K 1 , E 1 ).

4. Output (k 0 , k 1 ).

Expand: On input (σ, k σ ), parse k σ as

The correctness and security of the construction follows by the same argument as for G bil (Section 10.2). Regarding efficiency, the expansion cost is optimal, O(n ω ) using random paritycheck matrices, or O(n 2 • log n) using Toeplitz or quasi-cyclic matrices. Note that this means that generating a pseudorandom m × m matrix multiplication triples via this method is even faster than computing the product of random m × m matrices in the clear (for m = O(n)). On the downside, the size of the seed grows now as O(t 2 n 2 log n); i.e., the expansion is limited to subquadratic in the seed size. The next construction allows to achieve much better seed size (logarithmic in n), but has a higher computational complexity.

Second Construction. The second construction is similar in spirit to the previous one; it achieves a much smaller seed size, albeit with a larger computational cost O(n 4 log n). The high level idea is to generate each m × m matrix X σ by constructing a length-m 2 vector x σ = H • e σ , where H is an m 2 × n 2 parity-check matrix (e.g. a Toeplitz or quasi-cyclic matrix), and e σ is a length-n 2 t-sparse vector. Let H i ∈ F m×n 2 the matrix comprising the rows (i -1) • m + 1 to i • m of the matrix H, i.e. H is horizontally parsed as (very flat) matrices H 1 , . . . H m ∈ F m×n 2 . Then, we define X σ to be the m × m matrix whose i-th column is equal two H i • e σ . In other words, the i-th column of X σ contains the entries (i -1) • m + 1 to i • m of x σ . We let mat : F m 2 → F m×m denote the operator mapping an m 2 -vector to an m × m matrix.

Parameters: 1 λ , m, n, t, p ∈ N, where n > m. A parity-check matrix H ∈ F m 2 ×n 2 for a code of dimension n 2 -m 2 and number of samples m 2 over F.

Gen: On input 1 λ : 1. Pick two random vectors e 0 , e 1 ∈ F n 2 with exactly t nonzero entries.

2. Compute SPFSS keys (K 0 , K 1 ) which generate shares of e 0 • e 1 .