Elette Boyle

Geoffroy Couteau

Niv Gilboa

Yuval Ishai

Lisa Kohl

Peter Scholl

Efficient Pseudorandom Correlation Generators: Silent OT Extension and More *

Secure multiparty computation (MPC) often relies on sources of correlated randomness for better efficiency and simplicity. This is particularly useful for MPC with no honest majority, where input-independent correlated randomness enables a lightweight "non-cryptographic" online phase once the inputs are known. However, since the amount of correlated randomness typically scales with the circuit size of the function being computed, securely generating correlated randomness forms an efficiency bottleneck, involving a large amount of communication and storage. A natural tool for addressing the above limitations is a pseudorandom correlation generator (PCG). A PCG allows two or more parties to securely generate long sources of useful correlated randomness via a local expansion of correlated short seeds and no interaction. PCGs enable MPC with silent preprocessing, where a small amount of interaction used for securely sampling the seeds is followed by silent local generation of correlated pseudorandomness. A concretely efficient PCG for Vector-OLE correlations was recently obtained by Boyle et al. (CCS 2018) based on variants of the learning parity with noise (LPN) assumption over large fields. In this work, we initiate a systematic study of PCGs and present concretely efficient constructions for several types of useful MPC correlations. We obtain the following main contributions:

-PCG foundations. We give a general security definition for PCGs. Our definition suffices for any MPC protocol satisfying a stronger security requirement that is met by existing protocols. We prove that a stronger security requirement is indeed necessary, and justify our PCG definition by ruling out a stronger and more natural definition. -Silent OT extension. We present the first concretely efficient PCG for oblivious transfer correlations. Its security is based on a variant of the binary LPN assumption and any correlationrobust hash function. We expect it to provide a faster alternative to the IKNP OT extension protocol (Crypto '03) when communication is the bottleneck. We present several applications, including protocols for non-interactive zero-knowledge with bounded-reusable preprocessing from binary LPN, and concretely efficient related-key oblivious pseudorandom functions. -PCGs for simple 2-party correlations. We obtain PCGs for several other types of useful 2-party correlations, including (authenticated) one-time truth-tables and Beaver triples. While the latter PCGs are slower than our PCG for OT, they are still practically feasible. These PCGs are based on a host of assumptions and techniques, including specialized homomorphic secret sharing schemes and pseudorandom generators tailored to their structure. -Multiparty correlations. We obtain PCGs for multiparty correlations that can be used to make the circuit-dependent communication of MPC protocols scale linearly (instead of quadratically) with the number of parties. * This is a full version of [BCG + 19].

* PRG stands for an arbitrary pseudorandom generator, OT for random oblivious transfer, and OTTT for authenticated one-time truth-table correlation. † Estimated (approximate) cost over one core of a standard laptop, with average communication of 2.6 bits/OT.

.

Introduction

Correlated secret randomness is a valuable resource for secure multi-party computation (MPC). A simple example is a common random key that is given to two parties, who can later use it as a one-time pad for secure message transmission. In the context of MPC, a more useful example is a random oblivious transfer (OT) correlation, in which one party is given a pair of random bits (more generally, strings) (s 0 , s 1 ) and the other party is given the pair (r, s r ) for a random bit r. The OT correlation can serve as a basis for general MPC protocols with no honest majority [GMW87, Kil88,IPS08]. Other kinds of two-party correlations that are useful for MPC include oblivious linear-function evaluation (OLE) correlations [NP06,IPS09,ADI + 17], multiplication triples (also known as "Beaver triples") [Bea91,BDOZ11,DPSZ12], and one-time truth tables [IKM + 13, DNNR17, DKS + 17].

The above types of correlated randomness are commonly used to implement efficient MPC protocols in the preprocessing model. Such protocols consist of an offline, input-independent preprocessing phase, where many independent instances of the correlated randomness are generated, followed by a fast online phase that consumes this correlated randomness for the purpose of securely evaluate a given function of the inputs. In many cases, the online phase is "informationtheoretic"6 and its computational complexity is only a small-constant times higher than that of an insecure function evaluation. Most importantly for the present work, the online phase of such protocols typically outperforms all competing approaches in terms of concrete efficiency.

A major challenge in implementing such offline-online protocols is that the preprocessing phase needs to securely generate and store a large amount of correlated randomness. This is typically done by using a special-purpose interactive MPC protocol, which involves a significant amount of communication and computation for each gate of a circuit that should be evaluated in the online phase. A dream goal would be to replace this source of correlated randomness with short correlated seeds, which can be "silently" expanded without any interaction to produce a large amount of pseudorandom correlated randomness. This process should emulate an ideal process for generating the target correlation not only from the point of view of outsiders, but also from the point of view of insiders who can observe the correlated seeds. We refer to such an object as a pseudorandom correlation generator, or PCG for short.

A bit more precisely, a two-party PCG is defined as follows. Let (R 0 , R 1 ) be a target correlation, defined by some efficient sampling algorithm C that on input 1 λ outputs a pair of correlated strings (r 0 , r 1 ). For instance, C(1 λ ) may output n = λ 3 independent instances of an OT correlation. A PCG is a pair of efficient algorithms (Gen, Expand) such that:

-Gen samples a pair of short correlated seeds (k 0 , k 1 ) $ ← Gen(1 λ ), -Expand is a local deterministic seed expansion algorithm mapping k i to r i ← Expand(i, k i ),

where

|r i | > |k i |.
We would like the outputs (r 0 , r 1 ) resulting from this process to be "indistinguishable" from an ideal sample (R 0 , R 1 ) generated by C(1 λ ), even to a party who receives one of the seeds k b .

A useful special case of PCG was recently considered by Boyle et al. [BCGI18], who constructed (under variants of the Learning Parity with Noise assumption [BFKL93]) a concretely efficient PCG for the vector OLE (VOLE) correlation. The VOLE correlation over a field F samples a random scalar x ∈ F and vectors u, v ∈ F n , and outputs r 0 = (u, v) to one party (the "sender") and r 1 = (x, w = ux + v) to the other party (the "receiver"). The VOLE correlation is useful for secure computation of functions that employ scalar-vector products over large fields, such as ones arising in the context of linear algebra and keyword search [ADI + 17].

Designing efficient PCGs for a wider class of correlations is strongly motivated by the goal of improving the efficiency of general MPC in the preprocessing model, where the preprocessing phase is used to securely generate the PCG seeds. We refer to this as MPC with silent preprocessing. More concretely, such a protocol consists of three phases: (1) an interactive setup phase for securely distributing the seed generation algorithm Gen; in the end of this phase, which involves a small amount of communication, only the short seeds are stored for later use; (2) a silent seed expansion phase, where the seeds are expanded into long correlated randomness via a local computation of Expand and without any interaction; (3) a final online phase where the correlated randomness is consumed to evaluate a given function of the inputs. One could employ Phase 1 when deciding that an MPC interaction might take place in the future, Phase 2 when interaction seems likely to take place in the near future, and Phase 3 to carry out the MPC interaction once the inputs are available. The low communication footprint of silent preprocessing can eliminate traffic analysis attacks that anticipate future MPC plans. Finally, another benefit of the PCG-based approach is that it can help reduce the cost of protecting MPC protocols against malicious parties. Indeed, since Phase 2 does not involve any interaction, it suffices to protect Phase 1 and Phase 3 against malicious parties, which is typically much cheaper.

Several different kinds of PCG constructions are implicit in the MPC literature. These include PCGs for simple multi-party linear correlations from any pseudorandom generator [GI99, CDI05], for general correlations from indistinguishability obfuscation [HW15, HIJ + 16], for socalled "bilinear" correlations from homomorphic secret sharing [BCG + 17], for restricted variants of OT correlations from key-homomorphic pseudorandom functions [Sch18] and, most recently, for VOLE correlation from LPN [BCGI18]. With the exception of linear multi-party correlations [GI99, CDI05] and VOLE correlations [BCGI18], none of these prior constructions seem appealing from a practical point of view. In particular, there was no prior approach (even a heuristic one) for constructing a concretely efficient PCG for OT correlations.

Our Contributions

In this work, we initiate a more systematic study of pseudorandom correlation generators. Our contributions are on both the foundational side, where we present new definitions, impossibility results and connections with other primitives, and the applied side, with concretely efficient constructions for commonly used MPC correlations, including OT correlations and others. Our most practical PCG constructions handle restricted (yet still useful) classes of correlations, while our more general constructions can handle much larger classes of correlations, at the expense of a bigger seed size and higher computational costs (and, for some of them, public-key-style assumptions such as lattice-based or pairing-based cryptography).

We now give a more detailed account of our contributions. Unless noted otherwise, we refer to MPC with computational security against semi-honest (i.e., passive) and static (i.e., nonadaptive) adversaries who may corrupt an arbitrary subset of parties.

Foundations of Pseudorandom Correlation Generators

Our first goal is to present a general security definition for the intuitive notion of PCG described above. As pointed out in [GI99], this is not quite as straightforward as one might imagine, and previous works side-stepped the problem by taking an ad-hoc approach. To motivate our general definition, we start by discussing the most natural alternative.

Ruling Out a Simulation-Based Definition. Recall that the ultimate desire would be that in any protocol, one can securely replace an ideal correlated randomness functionality C with pseudo-randomness obtained from expanding the correlated seeds of a PCG for C. This would indeed follow from a natural simulation-based security definition for PCG as a computationally secure, dealer-assisted protocol for computing the randomized functionality defined by C. Concretely, in the two-party case, the simulation-based definition requires the existence of a simulator S such that the real distribution (k b , Expand(k 1-b )), where (k 0 , k 1 ) are generated by Gen (capturing the view of a corrupted party b jointly with the output of the uncorrupted party 1-b) is computationally indistinguishable from the ideal distribution (S(r b ), r 1-b ), where (r 0 , r 1 ) are sampled by C. Unfortunately, we show (building on [HW15], and extending an informal argument from [GI99]) that such a definition is impossible to realize even for simple correlations. Intuitively, the impossibility follows from the fact that in the real distribution k b "explains" the output of the honest party in an efficiently verifiable way, whereas such an explanation of r 1-b cannot be generated from r b in the ideal distribution.

A General PCG Definition. To get around the above impossibility, we present a relaxed indistinguishability-based definition of PCG security, generalizing the specialized security definition for the VOLE correlation from [BCGI18]. Our definition requires that given its PCG key k b , corrupted party b cannot distinguish the true expanded output of the honest party r 1-b = Expand(1 -b, k 1-b ) from a random output r 1-b consistent with the correlation C and its own expanded output r b = Expand(b, k b ). In other words, we replace the ideal distribution in the above simulation-based definition by (k b , [r 1-b | R b = Expand(k b )]). Note that the latter distribution involves reverse-sampling from R 1-b conditioned on a fixed value for R b , which may not be well-defined. However, in this work we only consider additive correlations, where (R 0 , R 1 ) are additive secret shares (over a finite Abelian group) of a sample from some core distribution. For such additive correlations, the reverse-sampling is well-defined and is computationally efficient. More broadly, our general PCG definition is meaningful when this reverse-sampling is efficient.

Limitations. Our PCG definition is not good enough for generating correlated randomness in all applications. Indeed, the impossibility of the simulation-based definition discussed above implies such simple counterexamples for randomized functionalities. Concretely, for any C to which the impossibility result applies, there is a trivial MPC protocol for C given correlated randomness from C in which each party outputs its correlated randomness. However, the impossibility result shows that using any PCG for C would render this simple protocol insecure. We show, under standard cryptographic assumptions, that a similar impossibility holds even if one restricts attention to MPC for deterministic functionalities. Concretely, we show a protocol which uses correlated randomness C to realize a deterministic functionality with statistical security against malicious parties, but which becomes completely insecure (even against semi-honest parties) when C is replaced by a specific PCG for C that meets our indistinguishability-based definition.

A Plug-and-Play Use of PCG. We complement the above negative results by a positive result, showing that our PCG definition does suffice to imply our "ultimate desire" in the context of most applications. Concretely, we put forward a slightly stronger security requirement for MPC with preprocessing, such that in any protocol satisfying this requirement, a PCG can be used as a drop-in replacement for correlated randomness. The stronger security requirement asserts that security still hold even if the ideal correlation functionality (R 0 , R 1 ) is replaced by a corruptible functionality that allows corrupted party b to pick its own randomness r * b , and then delivers to the uncorrupted party a sample r 1-b from the conditional distribution

[r 1-b | R b = r * b ].
It fortunately turns out that natural MPC protocols in the preprocessing model already satisfy this stronger security requirement. This allows for a plug-and-play use of PCGs in many application scenarios.

Relation with Homomorphic Secret Sharing. A (two-party) homomorphic secret sharing (HSS) scheme [BGI16a, BGI + 18] for a function class F splits a secret x into two shares (x 0 , x 1 ), such that given any f ∈ F one can efficiently evaluate additive shares of f (x) via local computation on the shares. We show a two-way relation between PCG and HSS. First, we show that a PCG for any additive correlation (as defined above) can be reduced to HSS for a related function class F, generalizing and formalizing a previous observation from [BCG + 17]. In particular, HSS for general circuits implies PCG for all additive correlations, which include most of the useful MPC correlations as special cases. (This is only a feasibility result, which does not directly imply concretely efficient constructions.) Second, we show that some converse is also true: a PCG for the degree-d "tensoring" correlation, obtained by picking a random vector X ∈ R n and outputting additive shares of all products of at most d entries of X, implies HSS for the class F of degree-d (n-variate) polynomials over R n , where the share size grows linearly with n and the homomorphic evaluation time grows linearly with n d .

Silent OT Extension

A central contribution of this work is the first concretely efficient construction of PCG for the oblivious transfer (OT) correlation. From an asymptotic point of view, our PCG can achieve an arbitrary polynomial stretch, assuming: (1) The binary Learning Parity with Noise (LPN) assumption [BFKL93] with a conservative choice of parameters, and (2) A correlation-robust hash function [IKNP03]. The hash function primitive, which is only used in a black-box way, can be instantiated in practice by a general-purpose hash function or block cipher. Assuming LPN with a linear number of samples and inverse-polynomial noise rate holds for the dual of a nearlinear time encodable code (such as the codes proposed in [HKL + 12, DI14, ABD + 16, ADI + 17]), which is still a conservative assumption, the computational complexity of Expand is nearly linear in the output length. 7In a nutshell, our efficient PCG for OT applies the PCG for VOLE from [BCGI18] over a large extension field F 2 λ , except for restricting the sender's output u to be over the base field. This yields n correlated instances of random OT that can be converted into standard OT by using a correlation-robust hash function, as in [IKNP03]. See Section 2 for more details.

By applying a secure two-party protocol for distributing Gen, we obtain a silent OT extension protocol that generates n pseudo-random OT instances using a small number of OTs, with a total of O(n ) bits of communication for any > 0. This should be compared with existing OT extension protocols [Bea96,IKNP03] that do not require the LPN assumption but where the communication complexity is bigger than n.

Concrete Efficiency. Our LPN-based PCG for OT is very attractive in terms of concrete efficiency, and we expect it to outperform state-of-the-art OT extension protocols [IKNP03, ALSZ13,KK13] in settings where communication is the bottleneck. To give a few data points, our PCG can expand a pair of seeds of length 10KB into a million instances of random 128-bit string-OT, of total size 16MB (receiver) and 32MB (sender), in an estimated8 time of around a second on a single core of a modern CPU. Alternatively, seeds of length 7KB can be expanded into 65 thousand OTs at roughly half the amortized computational cost. Factoring in the cost of securely distributing Gen (with semi-honest security, building on [Ds17]), the amortized communication complexity of our silent OT extension protocol is 0-3 bits for each random 128-bit string-OT. To put that into context, state-of-the-art OT extension protocols [IKNP03,ALSZ13] require 128 bits of communication per random 128-bit string-OT and can generate around 10 million OTs per second [GKWY19] over a fast network, so the price we pay for the (much) lower communication complexity seems quite modest. Even for the easier case of random bit-OT, the best previous OT extension protocol [KK13] required roughly 80 bits of communication per OT.

Other PCG Constructions

We present an assortment of practically feasible PCGs for other useful two-party correlations, based on a variety of underlying tools and assumptions.

-PCG for Constant-Degree Polynomials from LPN. We show that a generalization of the LPN-based VOLE generator from [BCGI18] can be used to obtain a PCG for any constant-degree additive correlation, namely a correlation that additively secret-shares a vector of degree-d polynomials of a random X ∈ F n for some constant d ≥ 2. This PCG relies on LPN over F in a similar noise regime as the PCG for OT from Section 1.1.2. In fact, by increasing the computation time (but still keeping it polynomial), one can use the LPN assumption in a parameter regime that is not known to imply public-key encryption [Ale03], let alone OT. The main caveat is that even for generating simple degree-d correlations, such as Ω(n) Beaver triples (d = 2), the computational complexity of Expand is bigger than n d . While much slower than our PCG for OT, this construction may still be practically feasible for d = 2 even with reasonably large n. We leave the question of obtaining more efficient variants of this construction to future work.

As discussed in Section 1.1.1, this PCG construction implies (2-party) HSS schemes for constant-degree polynomials from LPN. By additionally assuming a standard OT protocol, it implies secure two-party computation protocols for constant-degree polynomials in which the communication complexity is nearly linear in the input size. Using the techniques from [BGI16a,Cou19], it also implies an "almost-sublinear" general secure computation protocol: for any constant c > 1 and layered boolean circuit of size s (and assuming binary LPN and OT), there is a secure two-party computation protocol with polynomial computation and total communication bounded by s/c. We stress again that these are mainly feasibility results because of the high computational cost of this PCG construction.

-PCG for One-Time Truth Tables from any PRG. One-time truth tables (OTTT) are a type of correlation that allow secure evaluation of a public lookup table in MPC, on a secretshared input [IKM + 13, DNNR17, DKS + 17], and are well-suited to computations such as the S-box of AES. For MPC with active security, the correlation outputs need to be authenticated with information-theoretic MACs, as in the recent TinyTable protocol [DNNR17]. We present a very simple PCG for authenticated OTTT using only a distributed point function (DPF) [GI14, BGI16b], which in turn can be efficiently constructed from any pseudorandom generator (PRG). This PCG follows naturally from a building block of the silent OT extension construction (as we explain in Section 2). It compresses the storage cost of an authenticated OTTT from O(λn) bits down to O(λ log n) bits, for a table of size n, giving a reduction in size of over 20x for a length-256 table such as the AES S-box. There is a concretely efficient protocol to distribute the seed generator Gen with semi-honest security by using the distributed DPF key generation protocol from [Ds17]. While a similar protocol with malicious security is considerably more expensive, even a naive approach based on general-purpose secure computation (e.g., using recent protocols such as [KRRW18]) is feasible in practice, enabling the compressed storage benefit of the PCG-based approach.

-PCGs from Homomorphic Secret Sharing. We give practically feasible PCG constructions for OLE and (authenticated) Beaver triple correlations, which are useful for arithmetic MPC protocols such as SPDZ [DPSZ12]. For these constructions we use HSS based on ring-LWE [BGV12, DHRW16, BKS19] and the BGN (pairing-based) cryptosystem [BGN05, BGI16a, BCG + 17]. To expand the seeds, we rely on a multivariate quadratic (MQ) assumption based PRG, which limits the stretch to sub-quadratic, but allows for reasonable computational efficiency. For example, with our ring-LWE-based PCG we estimate that one should be able to expand a pair of 3GB seeds into 17GB of authenticated Beaver triples in a 128-bit field, at a rate of around 6 thousand triples per second; various tradeoffs are possible between seed size and computation time, and we also explore an iterative variant which produces triples in small batches. Securely computing Gen to distribute the seeds is relatively cheap compared to the expansion phase, and the overall performance should be comparable to recent work on actively secure triple generation with much more interaction [KPR18]. With BGN, we estimate around 200ms for computing an OLE correlation over Z N for small N (say, N < 10). Although much more expensive than our silent OT extension, an advantage of the ring-LWE-based constructions, beyond the richer class of correlations, is that they can be extended to the multi-party setting, as we discuss next.

PCGs for Multi-Party Correlations

Finally, we present a general transformation for extending certain classes of PCGs from the 2-party to the multi-party setting. This can be applied to PCGs for simple bilinear correlations, including VOLE and Beaver triples, giving the first non-trivial, efficient PCG constructions in the multi-party setting. The transformation applies to most of our 2-party PCGs, including the LPN-based PCG for constant-degree correlations.

On top of the silent preprocessing feature, an appealing application of our multi-party PCGs is in obtaining secure M -party computation protocols with total communication complexity O(M s + M 2 • s ) (for circuit size s and constant 0 < < 1). The O(M s) term is the cost of the (information-theoretic) online phase, and the O(M 2 •s ) term is the cost of distributing the PCG seed generation, which is the only part of the protocol requiring pairwise communication. This should be contrasted with OT-based MPC protocols, which have total communication complexity Ω(M 2 s) [GMW87,HOSS18] . Protocols with such communication complexity (without the silent preprocessing feature) could previously be based on different flavors of somewhat homomorphic encryption [FH96, CDN01, DPSZ12]. We get the first such protocol that only relies on LPN and OT, and the first practically feasible protocol that has sublinear-communication offline phase and information-theoretic online phase.

Additional Applications

From our silent OT extension protocol, we obtain the following additional results:

-Oblivious Pseudorandom Functions (OPRFs). An OPRF [FIPR05] is a two-party protocol for securely evaluating a pseudorandom function, whose key is known by one party, on a secret input known by the second party. OPRFs serve as the main building blocks in recent protocols for private set intersection [KKRT16]. Our silent OT construction can be used to obtain a form of batch OPRF with cost as little as 1 bit of communication per OPRF evaluation on a random input, leading to around a factor two reduction in communication for these protocols. -Reusable-Preprocessing NIZK. Consider the following setting for non-interactive zero knowledge (NIZK) with reusable interactive setup: In an offline setup phase, before the statements to be proved are known, the prover and the verifier interact to securely generate correlated random seeds. The seeds can then be used to prove any polynomial number of statements by having the prover send a single message to the verifier for each statement. Such a notion was recently constructed in [BCGI18], building on [CDI + 18], using their PCG for VOLE. Our silent OT extension can be used to obtain an improved reusable-preprocessing NIZK system for NP, under the standard LPN assumption over F 2 . As compared to the reusable NIZK of [BCGI18], our NIZK relies on a more standard assumption (LPN over F 2 versus large F), and the setup cost is independent of both the number of statements and their size (whereas in [BCGI18], the setup cost was independent of the number of statements, but grows linearly with a bound on their size). On the down side, our OT-based NIZK protocols do not have the computational complexity advantages of the VOLE-based constructions from [BCGI18]. -Efficient Secure Matrix Multiplication. As a stepping stone towards silent OT extension, we construct a PCG for a generalization of VOLE called subfield VOLE. This can be seen as a form of batch VOLE where the u value is reused across several instances, and can be applied to compute secret-shared tensor products and matrix multiplication more efficiently.

Compared with naively using a PCG for standard VOLE, we reduce the seed size by at least a O(log n) factor.

Finally, our PCG for OTTT yields the following application.

-Improved 2-PC with Sublinear Online Communication. Standard approaches to secure computation with preprocessing (e.g., SPDZ) still require online communication that is linear in the circuit size. Recently, Couteau [Cou19] demonstrated asymptotic feasibility of information-theoretic secure 2-party computation (2-PC) in the preprocessing model for a natural class of circuits (namely, "layered" circuits), with sublinear online communication, O(s/ log log s) for circuit size s. However, this comes at the cost of generating and storing O(s 2 ) bits of correlated randomness.

Our compressed one-time truth-table (OTTT) construction allows one to match the asymptotic complexity of [Cou19], while reducing the amount of correlated randomness from quadratic to quasilinear in the circuit size, in exchange for settling for computational security and assuming the existence of one-way functions.

Paper Organization

We begin in Section 2 with an overview of our techniques, followed by preliminaries in Section 3.

In Section 4, we present our PCG definition and foundational results. Section 5 contains our silent OT extension construction, and applications to OPRFs and NIZK from LPN. Section 6 provides an LPN-based construction of PCG for general constant-degree correlations. We then present generic constructions of PCGs from specific classes of PRGs (Section 4.4); we instantiate this framework for more complex correlations based on group-based and lattice-based HSS, in Section 7.3 and Section 7.4, respectively. Finally, in Section 8 we construct general, multi-party PCGs for simple bilinear correlations based on any "programmable" 2-party PCG.

Technical Overview of Constructions

In this section we give a high-level overview of the techniques that underly our different PCG constructions.

Background

Our PCG constructions rely on different types of homomorphic secret sharing (HSS) and function secret sharing (FSS) schemes. Informally, HSS is a form of secret sharing that allows a secret x to be split up into shares k 0 , k 1 , such that a party holding k i can locally obtain an additive secret share of f (x), for some function f . FSS is the dual notion: starting with a function f , and splitting into shares f 0 , f 1 such that each share f i hides f , but can be used to obtain an additive sharing of f (x) for some public input x.9 FSS for a class of point functions (i.e., functions f which evaluate to 0 on all but a single input) is called a distributed point function

Overall methodology

At a high level, our constructions can all be seen as examples of the following blueprint: construct an HSS scheme that can homomorphically evaluate the composition of a pseudorandom generator (PRG) with a function f that uses the expanded randomness to compute the desired correlation. This can be used to obtain PCGs for any additive correlation; i.e., that outputs random additive shares of some distribution. Of course, the main challenge lies in instantiating this efficiently, since plugging in even a low-degree PRG to an off-the-shelf HSS scheme is typically not practical. We instead use specialized HSS constructions that pair well with our carefully chosen PRGs. As a stepping stone, our constructions implicitly construct a compressible form of HSS, which allows the sharing of inputs from some distribution D, such that the share size is smaller than an uncompressed output of D, and we can still compute some useful function f on the expanded inputs. We typically choose D to be a sparse distribution on vectors, or another similarly compressible distribution. We then convert these long D-vectors to slightly shorter (but still long) random-looking vectors, by homomorphically multiplying by a compressive linear map. Under a suitable LPN-type assumption, this combination of expanding the compressed D-vector followed by linear compression acts as a PRG in the above blueprint, and we can proceed to homomorphically compute the desired correlation.

For example, when D samples a sparse, low-weight vector e over F 2 , and the linear map is a random matrix H, then distinguishing (H, e • H) from random is as hard as the problem of decoding a random binary linear code, which corresponds to the standard LPN assumption [BFKL93, Ale03]. Another example is when D outputs a tensor product of two short, uniform vectors. Recovering the short vectors given only (x ⊗ y) • H is the problem of solving a random system of multivariate quadratic equations (MQ problem), which is believed to be hard for a suitable choice of parameters [MI88, Wol05, BGP06, AHI + 17]. In particular, the decision version of MQ is polynomially reducible to its search version [BGP06].

We remark that the resulting PRGs do not necessarily conform to standard metrics of simplicity, such as low degree or low locality, and in isolation may appear somewhat unnatural. This exemplifies an interesting observation that "HSS-friendliness" may indeed be a new type of metric that does not directly align with those previously studied.

Silent OT Extension

As a building block for silent OT extension, we start by constructing a PCG for a two-party correlation we call subfield vector oblivious linear evaluation (subfield VOLE). This correlation works over a field F q , and a subfield F p , where q = p r . It first samples a random x ∈ F q , u ∈ F n p , v ∈ F n q , then outputs (u, v) to the sender and (x, w = ux + v) to the receiver. 10 Our construction is a generalization of the vector-OLE construction from [BCGI18]: when p = q the correlation is exactly vector-OLE, but using q > p opens up additional applications. For example, viewing x ∈ F q as a vector x ∈ F r p , subfield VOLE can be seen as computing additive shares of the r × n tensor product x ⊗ u, which can be useful for secure two-party matrix multiplication, and other linear algebra tasks. Compared with using r copies of VOLE [BCGI18] to achieve the same task, we reduce the seed size by a O(log n) factor and obtain more efficient computation.

To build a PCG for subfield VOLE, we consider a compressible distribution D that outputs random sparse vectors of weight t and length n . First, notice that we can compress a secretsharing of the j-th unit vector e j ∈ {0, 1} n , using a distributed point function (DPF) for the point (j, 1): evaluating a DPF key on input i produces a random share of 0 on all inputs except i = j, where it outputs a share of 1. Hence, performing all n evaluations results in shares of the entire vector e j . This easily extends to weight t vectors, by naively using t DPFs and summing up the shares of the t unit vectors (this step can be optimized with a multi-point DPF as described in [BCGI18]).

Although it may appear that this only allows us to compress sparse vectors, and not perform any useful HSS computations afterwards, we observe that with a small tweak we can use this to build HSS for the family of randomized functions

F = {f H : F q → F n q , x → x • e • H | e $ ← HW t , H ∈ F n ×n p } (1)
where HW t is the distribution that outputs a random weight-t vector over F n p (with each entry either 0 or uniform). We remark that a naive description of the class F gives functions with very high degree, which could not be evaluated using simple HSS schemes, which highlights the importance of tailoring a specific solution.

To upgrade the above sketch to get HSS for F, we make one small modification: using t DPFs that output shares over F q , we specify the i-th DPF by the point (j i , y i • x) for some random index j i and y i ∈ F * p , instead of (j i , 1) as before. When evaluating the DPFs, the parties now obtain additive shares of e • x, where e contains all t y i 's in random positions. Since additive secret sharing is linear, any linear map H can then be locally applied on the shares.

If H ∈ F n ×n p is a compressive linear map with n < n , the vector u = e • H is pseudorandom under a suitable form of the LPN (or syndrome decoding) assumption. Concretely, we require that a t-noisy random codeword in the code whose parity check matrix is H is pseudorandom. This immediately yields a subfield VOLE generator, where each party's seed contains a set of DPF seeds, and the sender additionally gets the points (j i , y i ), and the receiver gets x, since additive shares of x • u can be locally converted to the (v, w) components of a VOLE correlation.

Our next observation, inspired by the OT extension protocol of Ishai et al. [IKNP03], is that subfield VOLE already gives as a restricted form of oblivious transfer, known as correlated OT or ∆-OT. If we run subfield VOLE over F 2 , embedded in F 2 r , then the VOLE sender obtains a set of pairs

u i $ ← F 2 , v i $ ← F 2 r , while the VOLE receiver gets x $ ← F 2 r and w i = x • u i + v i , for i = 1, .
. . , n. Now switch the roles of sender and receiver, so the VOLE sender becomes an OT receiver with choice bit u i and string v i . If

u i = 0 then v i = w i , whilst if u i = 1 then v i = w i -x,
hence, this is exactly a 1-out-of-2 OT where the OT sender's (formerly VOLE receiver's) messages are all of the form (w i , w i -x).

On its own, this type of ∆-OT is already useful for many applications such as garbled circuits and secure computation with information-theoretic MACs [WRK17a, NNOB12]. However, most importantly, following [IKNP03], the parties can locally convert such a correlated OT into an OT on random strings, using a hash function that is pseudorandom under correlated inputs. This gives us a PCG for random oblivious transfer, where the seed size is essentially that of t distributed point functions, or O(tλ log n) bits. Combining this with an efficient secure protocol for setting up a pair of DPF keys [Ds17], we obtain our silent OT extension protocol, which produces n pseudorandom string-OTs with o(n) bits of communication.

One-Time Truth Tables

We next show how to adapt the above approach to produce authenticated, one-time truth table correlations, which can be used to efficiently perform table lookups in MPC [IKM + 13,DNNR17, DKS + 17]. This construction is straightforward given the above description of our subfield-VOLE generator, so we informally explain it here and defer the complete description to Section B of the Appendix.

The correlation we want to produce, for a lookup table

T : [n] → {0, 1} m , is an additive secret-sharing of α, {y i , γ i } i∈[n]
where

y i = T (s + i mod n), γ i = y i • α ∈ F 2 λ (2) for α $ ← F 2 λ , s $ ← [n].
Here, the y i 's are equal to T shifted by a random offset s, while the γ i 's are information-theoretic MACs on y i under the key α, used to obtain active security in the MPC protocol.

Our starting point is the observation from [KOR + 17] that the y i 's can be generated locally, given secret-shares of a random unit vector. This is because, if e s ∈ {0, 1} n is the s-th unit vector, then we have

T (s + i mod n) = n j=1 e s [j] • T (i + j mod n)
which is linear in e s . We can further obtain the γ i 's (namely, the authenticated γ i = y i • α) if we additionally have secret-shares of the corresponding scaled vector α • e s .

The core observation is that a DPF gives precisely a compressed secret sharing of such a secret vector (1||α) • e s ∈ ({0, 1} 1+λ ) n : requiring only O(λ log n) bits in the place of O(λn).

More concretely, this leads to the following, simple approach for a PCG to generate shares of (2): use the previous DPF-based construction of HSS for the family in (1) over F 2 , with t = 1, x = (1 α) for α $ ← F 2 λ , and H the linear map induced by T in the equation above. The resulting PCG has seed size essentially the same as one DPF, which is O(λ log n) bits. This gives a large compression over the previous, practical approach from [DNNR17], which required O(λn) bits per table. Expanding the PCG is relatively cheap in practice, since in 2-PC applications only a single entry of each table is ever used, and this can be computed on-the-fly with O(n) PRG evaluations.

A downside of this construction is that it seems difficult to produce the necessary PCG seeds with good concrete efficiency in the malicious setting, since the only known approach in this setting requires evaluating a PRG inside 2-PC [Ds17]. However, our result is still interesting for a preprocessing phase with semi-honest security, or when a trusted dealer is present. Alternatively, if one can afford the cost of distributing Gen with malicious security via general-purpose 2-PC, the resulting correlated seeds only require a small amount of storage, and their local expansion is (automatically) secure against malicious parties.

PCGs for Constant-Degree Polynomials from LPN

We construct PCGs for constant-degree polynomials, using again function secret sharing for multi-point functions together with LPN. At a high level, the construction builds upon the fact that given two sparse vectors a, b, their tensor product a ⊗ b is sparse as well, hence shares of a ⊗ b can be compressed using an FSS, as for vector-OLE generators and silent OT extension. Then, a compressive mapping can be applied to obtain x ⊗ y from a ⊗ b, where x = (a • H) and y = (b • H) are pseudorandom under the LPN assumption, thanks to the bilinearity of the tensor product (and linearity of H). This immediately leads to a PCG for bilinear functions, which can be easily generalized to a PCG for constant-degree polynomials. However, the share size grows as O(t d ), where t is the number of noisy coordinates in the LPN instance, and d is the degree of the polynomial. The computation cost grows as O(n 2d ), where n is the input size.

PCGs from Ring-LWE and BGN-based HSS

We construct PCGs for more general two-party correlations, building upon the specific structure of homomorphic encryption-based HSS schemes [DHRW16, BKS19] and group-based HSS schemes [BGI16a, BGI17, BCG + 17]. Our key observation is that in both HSS schemes encodings of large pseudorandom strings can be compressed efficiently using an "HSS-friendly PRG" as described in Section 2.2. For the ring-LWE based construction, we obtain compression with a PRG based on the multivariate quadratic equations problem, and present several ways of optimizing this with batching techniques for homomorphic encryption, which lead to different tradeoffs for seed size and computational cost.

The group-based approach requires more involved techniques: The underlying HSS scheme uses two types of encodings, where so-called level-1 encodings are ElGamal ciphertexts, and level-2 encodings are shares of sk • x for a vector x, where sk is the secret key of the homomorphic encryption scheme. Then, a special HSS operation allows to compute level-2 encodings of bilinear functions applied to a level-1 encoding and a level-2 encoding. Using two parallel instances of the PCG for vector-OLE of [BCGI18] allows us to efficiently compress shares of y and sk • y, where y is a pseudorandom vector and sk is a shared value, to only O(λt log n) bits, under the LPN assumption with t noisy coordinates. Furthermore, encrypting short random sparse vectors suffices for homomorphically evaluating a specific LPN-based PRG directly on the level-1 encodings, as long as they support evaluation of degree-2 functions. This can be ensured by using BGN-style pairing-based encryption for the group-based HSS. Since the HSS comes with an inverse-polynomial error probability, we further develop a new method to efficiently remove the faulty outputs, building upon our silent OT extension protocol.

For both schemes, we discuss various optimizations and provide detailed efficiency estimations.

Multi-Party PCGs

As our final contribution, we construct multi-party PCGs for a useful class of bilinear correlations. Concretely, for a given bilinear map e :

G 1 × G 2 → G T , we consider M -party correlations of the form {(a i , b i , c i )} i∈[M ] , consisting of additive secret shares of random elements a ∈ G 1 , b ∈ G 2 ,
and their image c = e(a, b) ∈ G T . For appropriate choice of groups and bilinear operation, this captures M -party OT, M -party vector OLE, M -party Beaver triples, and more.

Our construction approach provides a semi-generic transformation from any PCG for a corresponding 2-party correlation {(a, c 1 ), (b, c 2 )} for random a, b, and c 1 + c 2 = e(a, b), if the PCG satisfies an additional programmability property. Roughly, this property requires a way of "reusing" the inputs a and b across instances without compromising security.

The M -party construction leverages this structure by executing M (M -1) pairwise instances of the underlying 2-party PCG, for all the "cross-terms." Namely, we think of each a i and b i from the final M -party correlation as playing the role of a or b in the 2-party correlation, with all possible partners. The desired M -party additive shares c i can then be derived by combining c ii = a i b i (computable locally) together with {c ij , c ji } j∈[M ]\{i} resulting from the 2-party correlations for pairs (a i , b j ) and (a j , b i ). The resulting M -party PCG keys consist of M (M -1) keys from the 2-party PCG, together with short expandable shares of 0 for rerandomization.

We observe that the necessary programmability property is satisfied by our subfield VOLE construction and the 2-party VOLE PCG from [BCGI18], as well as the 2-party bilinear PCGs constructed in this work (including OT and Beaver triples) from group-based and lattice-based HSS (Section 7) and from LPN (Section 6). As a corollary, we obtain M -party variants of these correlations with quadratic blowup in computation and share size. Interestingly, our silent OT extension construction does not seem to support the necessary programmability, since the resulting sender message pairs are implicitly defined as a function of the receiver's bit selections.

Preliminaries

We say that a function negl : N → R + is negligible if it vanishes faster than every inverse polynomial. For two families of distributions X = {X λ } and Y = {Y λ } indexed by a security parameter λ ∈ N, we write X c ≈ Y if X and Y are computationally indistinguishable (namely, any family of circuits of size poly(λ) has a negligible distinguishing advantage), X s ≈ Y if they are statistically indistinguishable (namely, the above holds for arbitrary distinguishers), and X ≡ Y if the two families are identically distributed.

Notation. We usually denote matrices with capital letters (A, B, C) and vectors with bold lowercase (x, y). By default, vectors are assumed to be row vectors. We write A| i,j to denote the entry (i, j) of a matrix A. Given a vector x of length |x| = n, the notation HW (x) denotes the Hamming weight x, i.e., the number of its nonzero entries. Given a distribution D, we denote by Im(D) the image of D (i.e., its support set).

Function Secret Sharing

Informally, an FSS scheme for a class of functions C is a pair of algorithms FSS = (FSS.Gen, FSS.Eval) such that:

-FSS.Gen given a function f ∈ C outputs a pair of keys (K 0 , K 1 );, -FSS.Eval, given K b and input x, outputs y b such that y 0 and y 1 form additive shares of f (x).

The security requirement is that each key K b computationally hide f , except for revealing the input and output domains of f . We formalize this below.

Definition 1 (Function Secret Sharing; adapted from [BGI16b]). A 2-party function secret sharing (FSS) scheme for a class of functions C = {f : I → G} with input domain I and output domain an abelian group (G, +), is a pair of PPT algorithms FSS = (FSS.Gen, FSS.Eval) with the following syntax:

-FSS.Gen(1 λ , f ), given security parameter λ and description of a function f ∈ C, outputs a pair of keys (K 0 , K 1 ); -FSS.Eval(b, K b , x), given party index b ∈ {0, 1}, key K b , and input x ∈ I, outputs a group element y b ∈ G.

Given an allowable leakage function Leak : {0, 1} * → {0, 1} * , the scheme FSS should satisfy the following requirements:

-Correctness: For any f : I → G in 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 polynomialsize 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.
Unless otherwise specified, we assume that for f : I → G, the allowable leakage Leak(f ) outputs (I, G), namely a description of the input and output domains of f . Remark 2. In any FSS scheme for a sufficiently rich class of functions (including point functions), each of the two evaluation functions F b K (x) = FSS.Eval(b, K, x) is a pseudorandom function [BGI15]. Some of our constructions will use this property. Some applications of FSS require applying the evaluation algorithm on all inputs. Following [BGI16b, BCGI18], given an FSS scheme (FSS.Gen, FSS.Eval), we denote by FSS.FullEval an algorithm which, on input a bit b, and an evaluation key K b (which defines the input domain I), outputs a list of |I| elements of G corresponding to the evaluation of FSS.Eval(b, K b , •) on every input x ∈ I (in some predetermined order). While FSS.FullEval can always be realized with |I| invocations of FSS.Eval, it is typically possible to obtain a more efficient construction. Below, we recall some results from [BGI16b] on FSS schemes for useful classes of functions.

Distributed Point Functions

A distributed point function (DPF) [GI14] is an FSS scheme for the class of point functions f α,β : {0, 1} → G which satisfy f α,β (α) = β, and f α,β (x) = 0 for any x = α. A sequence of works [GI14, BGI15, BGI16b] has led to highly efficient constructions of DPF schemes from any pseudorandom generator (PRG), which can be implemented in practice using block ciphers such as AES.

Theorem 3 (PRG-based DPF [BGI16b], Theorems 3.3 and 3.4). Given a PRG G : {0, 1} λ → {0, 1} 2λ+2 , there exists a DPF for point functions f α,β : {0, 1} → G with key size

• (λ + 2) + λ + log 2 |G| bits. For m = log |G| λ+2 , the key generation algorithm Gen invokes G at most 2( + m) times, the evaluation algorithm Eval invokes G at most + m times, and the full evaluation algorithm FullEval invokes G at most 2 (1 + m) times.

Note that a naive construction of FullEval from Eval would require 2 ( + m) invocations of G.

FSS for Multi-Point Functions

Similarly to [BCGI18], we use FSS for multi-point functions. A k-point function evaluates to 0 everywhere, except on k specified points. When specifying multi-point functions we often view the domain of the function as

[n] for n = 2 instead of {0, 1} . Definition 4 (Multi-Point Function [BCGI18]). An (n, t)-multi-point function over an abelian group (G, +) is a function f S,y : [n] → G, where S = (s 1 , • • • , s t ) is an ordered sub- set of [n] of size t and y = (y 1 , • • • , y t ) ∈ G t , defined by f S,y (s i ) = y i for any i ∈ [t], and f S,y (x) = 0 for any x ∈ [n] \ S.
We assume that the description of S includes the input domain [n] so that f S,y is fully specified.

A Multi-Point Function Secret Sharing (MPFSS) is an FSS scheme for the class of multipoint functions, where a point function f S,y is represented in a natural way. We assume that an MPFSS scheme leaks not only the input and output domains but also the number of points t that the multi-point function specifies. An MPFSS can be easily obtained by adding t instances of DPF; optimized constructions of MPFSS, using batch codes [IKOS04] to speed up the full domain evaluation algorithm, were presented in [BCGI18].

Homomorphic Secret Sharing

We consider homomorphic secret sharing (HSS), a dual form of FSS introduced in [BGI16a]. HSS can be viewed as the natural secret-sharing analogue of fully homomorphic encryption. In this work, we consider a secret-key variant of HSS in which a common secret key is used to share multiple inputs, and the output is shared additively over an Abelian group. Furthermore, we will be mainly interested in HSS schemes that support the evaluation of low-degree multivariate polynomials on shared input vectors. Informally, a degree-d HSS is a triple of algorithms (Gen, Share, Eval) such that:

-Gen generates a secret key sk and an evaluation key ek, -Share uses the secret key to share an input vector into (s 0 , s 1 ), and -Eval, given share s b , evaluation key ek, and a description of a function f of algebraic degree d, outputs y b such that y 0 + y 1 = f (x).

Security states that a single share s b together with ek computationally hide the input x.

More formally, we consider degree-d HSS over a finite ring R. In this work we will consider rings R that are either finite fields or rings Z m of integers modulo m. We view the ring as being implicitly defined by the security parameter λ, and assume that the bit-length of ring elements is at most polynomial in λ.

Definition 5 (Degree-d Homomorphic Secret Sharing). A (2-party, secret-key) Degree-d Homomorphic Secret Sharing (HSS) scheme over a ring (R = R(λ), +, •) is a triple of PPT algorithms HSS = (HSS.Gen, HSS.Share, HSS.Eval) with the following syntax:

-HSS.Gen(1 λ ): On input a security parameter 1 λ , the key generation algorithm outputs a secret key sk and an evaluation key ek. -HSS.Share(sk, x): Given secret key sk and secret input value x ∈ R n , the sharing algorithm outputs a pair of shares (s 0 , s 1 ). We assume that a description of the ring R and the input length n are included in each of (s 0 , s 1 ). -HSS.Eval(b, ek, s b , P ): On input party index b ∈ {0, 1}, evaluation key ek, share s b of an input vector x ∈ R n , and degree-d arithmetic circuit P over R with n inputs and m outputs, the (deterministic) homomorphic evaluation algorithm outputs y b ∈ R m , constituting party b's share over R of an output y ∈ R m .

The algorithms (HSS.Gen, HSS.Share, HSS.Eval) should satisfy the following correctness and security requirements:

-Correctness: For every polynomial poly(λ) there exists a negligible negl(λ) such that for every λ, input x ∈ R n (where R = R(λ)), and degree-d arithmetic circuit P of size poly(λ) we have:

Pr[y 0 + y 1 = P (x)] ≤ negl(λ),
where probability is taken over (sk, ek) ← HSS.Gen(1 λ ); (s 0 , s 1 ) ← HSS.Share(sk, x); y b ← HSS.Eval(b, ek, s b , P ), b ∈ {0, 1}.

-Security: For any b ∈ {0, 1}, pair of input sequences x λ , x λ ∈ R n of polynomial length n(λ), the distribution ensembles C b (λ, x λ ) and C b (λ, x λ ) are computationally indistinguishable, where C b (λ, z) for z ∈ {x λ , x λ } is obtained by sampling (sk, ek) ← HSS.Gen(1 λ ), sampling (s 0 , s 1 ) ← HSS.Enc(sk, z), and outputting (ek, s b ).

Learning Parity with Noise

Our constructions rely on variants of the Learning Parity with Noise (LPN) assumption [BFKL93] over either F 2 or a large finite field F. Unlike the LWE assumption, in LPN over F the noise is assumed to have a small Hamming weight. Concretely, the noise is a random field element in a small fraction of the coordinates and 0 elsewhere. Similar assumptions have been previously used in the context of secure arithmetic computation [NP06, IPS09, ADI + 17, DGN + 17, GNN17]. Unlike most of these works, the flavors of LPN on which we rely do not require the underlying code to have an algebraic structure and are thus not susceptible to algebraic (list-) decoding attacks.

Definition 6 (LPN). Let D(R) = {D k,q (R)} k,q∈N denote a family of distributions over a ring R, such that for any k, q ∈ N, Im(D k,q (R)) ⊆ R q . Let C be a probabilistic code generation algorithm such that C(k, q, R) outputs a matrix A ∈ R k×q . For dimension k = k(λ), number of samples (or block length) q = q(λ), and ring R = R(λ), the (D, C, R)-LPN(k, q) assumption states that

{(A, b) | A $ ← C(k, q, R), e $ ← D k,q (R), s $ ← F k , b ← s • A + e} c ≈ {(A, b) | A $ ← C(k, q, R), b $ ← R q }
Here and in the following, all parameters are functions of the security parameter λ and computational indistinguishability is defined with respect to λ.

When R = F 2 and D is the Bernoulli distribution over F q 2 , where each coordinate is 1 with probability r and 0 otherwise, this corresponds to the standard binary LPN assumption.

Note that the search LPN problem, of finding the vector can be reduced to the decisional LPN assumption as defined above above when the code generator C outputs a uniform matrix A [BFKL93, AIK09]. However, this is less relevant for us as we are mainly interested in efficient variants with more structured codes. See [DI14] for further discussion of search-to-decision reductions in the general case.

Example: LPN with Fixed Weight Noise

For a finite field F, we denote by HW r (F) the distribution of uniform, weight r vectors over F; that is, a sample from HW r (F) is a uniformly random nonzero field element in r random positions, and zero elsewhere. The (Ber r (F) q , C, F) -LPN(k, q) assumption corresponds to the standard (non-binary, fixed-weight) LPN assumption over a field F with code generator C, dimension k, number of samples (or block length) q, and noise rate r.

When the block length q and noise rate r are such that k random coordinates will be all noiseless with non-negligible probability (e.g., when r is constant and q = Ω(k 2 )), LPN can be broken via Gaussian elimination (cf. [AG11]). This attack does not apply to our constructions, which typically have q = O(k).

Definition 7 (dual LPN). Let D(R) and C be as in Definition 6, n, n ∈ N with n > n, and define

C ⊥ (n , n, R) = {B ∈ R n ×n : A • B = 0, A ∈ C(n -n, n , R), rank(B) = n}. For n = n(λ), n = n (λ) and R = R(λ), the (D, C, R)-dual-LPN(n , n) assumption states that {(H, b) | H $ ← C ⊥ (n , n, R), e $ ← D(R), b ← e • H} c ≈ {(H, b) | H $ ← C ⊥ (n , n, R), b $ ← R n }
The search version of the dual LPN problem is also known as syndrome decoding. The decision version defined above is equivalent to primal variant of LPN from Definition 6 with dimension k = n -n and number of samples q = n . This follows from the simple fact that (s

• A + e) • H = s • A • H + e • H = e • H,
when H is the parity-check matrix of A.

Remark 8. For any code generation algorithm C where dual-LPN is hard, it must hold that for H $ ← C ⊥ (n , n , R), H is full rank with overwhelming probability. If that was not the case, then we could easily distinguish e • H from uniform due to a linear relation between some of its outputs.

Remark 9. As a concrete example of the actual flavor of the dual-LPN assumption we will use, our construction of silent OT from Section 5 relies on the dual-LPN assumption of Definition 6 with respect to a random linear code over the field F 2 . For deriving our concrete parameters, we choose a regular error distribution of weight t, where a length-n error vector has t non-zero coordinates spread across weight-1 blocks of length n /t. This is known as the regular-LPN or regular syndrome decoding problem. When n ≥ 2 16 and n = 4n, a fixed-weight noise of t ≈ 32 suffices to achieve 80-bit security against the best known attacks on this flavor of LPN, which all take time exponential in (n /n) • t. We will also consider alternative choices of linear codes (such as LDPC codes or quasi-cyclic codes) to improve the concrete computational efficiency in our estimates; such codes still lead to plausible variants of LPN and do not significantly improve known attacks compared with random codes.

Pseudorandom Correlation Generators

In this section we put forward a general notion of pseudorandom correlation generator (PCG) and study some of its limitations, capabilities, and relation with other primitives. We start with our formal definition of PCG in Section 4.1. We then prove in Section 4.2 that a simpler and more natural simulation-based definition of PCG, that would suffice for all applications, is not realizable. As a second-best alternative, we show in Section 4.3 that PCGs can be used as a dropin replacement for correlated randomness in every protocol that meets a slightly stronger security requirement, which is indeed met by natural MPC protocols in the correlated randomness model. Finally in Section 4.4 we show a two-way relation between PCGs for a useful class of "low-degree correlations" and HSS for low-degree polynomials as defined in Section 3.2.

Defining Pseudorandom Correlation Generators

At a high level, a pseudorandom correlation generator (PCG) for some relation takes as input a pair of short, correlated seeds and outputs long correlated pseudorandom strings, where the expansion procedure is deterministic and can be applied locally.

For correctness we require that the expanded output of a PCG is indistinguishable from truly random correlated strings.

For security it would be natural and straightforward to require that we can securely replace long correlated strings by short correlated seeds in any secure protocol execution. Unfortunately, as shown in the following section, this security requirement would be impossible to meet. Therefore, we will introduce (and subsequently prove useful) an indistinguishability based security notion. Namely, we require that an adversary given access to one of the short seeds k σ , cannot distinguish the pseudorandom string R 1-σ from a pseudorandom string that is chosen at random conditioned on (R 0 , R 1 ) being correlated (where R σ = PCG(k σ )). In other words, an adversary given access to a short seed cannot learn more about the other party's pseudorandom string than what is obvious given access to its own pseudorandom string.

In order to formally define pseudorandom correlations, we first introduce the concept of a correlation generator as a PPT algorithm outputting correlated elements.

Definition 10 (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(λ).

In order to define security, we require the notion of a reverse-sampleable correlation generator introduced in the following.

Definition 11 (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 [BCGI18]. Note though that we do not enforce perfect correctness.

Definition 12 (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 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 the above definition is trivial to achieve in general: We can let PCG.Gen on input 1 λ return (R 0 , R 1 ) ← C(1 λ ), and simply define Expand to be the identity. Typically, we will be interested in non-trivial constructions of PCGs, in which the seed size is significantly shorter than the output size. A pseudorandom generator with image in {0, 1} n is a simple example for an expanding PCG for the equality correlation

{(R, R) | R ∈ {0, 1} n }.
In the following we will be interested in constructing PCGs for a much broader class of correlations, like OT correlations, OLE correlations and (authenticated) Beaver triples.

Remark 13 (PCG with Setup). We sometimes consider an additional algorithm PCG.Setup to sample a secret key, public parameters and a share of evaluation keys (or a subset of the mentioned), which can be reused throughout several instances. More precisely: On input 1 λ , PCG.Setup returns a tuple (pp, sk, {ek σ } σ∈{0,1} ), PCG.Gen receives the secret key sk as additional input (always assumed to include the public parameters pp), and PCG.Expand receives the public parameters pp and the respective evaluation key share ek σ as additional inputs.

Remark 14 (PCG in the Multi-Party Setting). We also consider multi-party PCGs for reverse sampleable multi-correlation generators C M which on input 1 λ outputs elements in ({0, 1} n ) M . In this case, PCG.Gen(1 λ ) returns a M -tuple (k 1 , . . . , k M ). Correctness is defined accordingly and security required against any subset of colluding parties. More precisely: For any T ⊂ {1, . . . , M }, we require the following two distributions to be computationally indistinguishable:

{({k j } j∈T , {R i } i / ∈T ) |(k 1 , . . . , k M ) $ ← PCG.Gen(1 λ ), ∀i / ∈ T : R i ← PCG.Expand(i, k i )} and {({k j } j∈T , {R i } i / ∈T ) |(k 1 , . . . , k M ) $ ← PCG.Gen(1 λ ), ∀j ∈ T : R j ← PCG.Expand(j, k j ), {R i } i / ∈T $ ← RSample(T, {R j } j∈T )}
where RSample is the reverse sampling algorithm corresponding to the multi-correlation C M .

Impossibility of a Simulation-Based Definition

A natural and useful alternative to the security definition we gave in Section 4, is the following:

In any secure protocol (say against semi-honest adversaries), one can replace sampling a pair of strings from the correlation C by generating a pair of seeds (which are later expanded) using a PCG for C without compromising security. Unfortunately, as sketched in [GI99], a non-trivial PCG construction cannot satisfy such a simulation-based definition. Consider the simple protocol, where P 0 samples a pair (R 0 , R 1 ) ← C(1 λ ) and sends R 1 to P 1 , who simply outputs R 1 . This protocol obviously realizes the protocol dictated by C, with one-sided security against P 1 . But, if P 0 instead generates (k 0 , k 1 ) according to the seed generation algorithm of the PCG and sends k 1 to P 1 , a possible simulator runs into the following problem. Simulating the above protocol given only the output R 1 corresponds to finding a short seed k 1 that can be (deterministically) expanded to R 1 . If the entropy in the second output of C exceeds the seed-length |k 1 |, such a compression violates correctness, as it could be used to distinguish R 1 from a string that is indeed chosen via C.

In the following, we present a formal and more general version of the above argument for ruling out a simulation-based definition for non-trivial correlations. Our negative result is based on a lower bound given by Hubáček and Wichs [HW15]. There, the notion of Yao incompressibility entropy, the computational equivalent to Shannon entropy, is employed to establish a lower bound on the required communication in a secure protocol with long outputs. More precisely, Yao incompressibility entropy [HLR07,Yao82] is a measure on how well outputs of a distribution can be compressed on average, when the compressing and decompressing algorithms are required to be efficient. For example, a pseudorandom bit string of length has Yao incompressibility entropy .

Definition 15 (Yao Incompressiblity Entropy

[HLR07] (simplified)). Let = (λ) ∈ N.
A probability ensemble X = {X λ } has Yao incompressibility entropy at least , if for every pair of polynomial sized circuit-ensembles C = {C λ }, D = {D λ } where C has output bit-length at most -1, there exists a negligible function negl : N → R + such that for every sufficiently large positive integer λ we have

Pr [x ← X : D(C(x)) = x] ≤ 1 2 + negl(λ).
One of the main results of [HW15] is that the communication in a secure protocol has to at least meet the Yao incompressibility entropy of the output, when the adversary is allowed to fix the random coins of the corrupted party. Applying this result rules out meaningful PCG instantiations of a simulation-based security definition.

Theorem 16 (Impossiblity of Simulation-Based Definition for Non-Trivial PCGs).

Let C be a reverse-sampleable correlation generator, where the Yao incompressibility entropy of the output is . Then, for every pseudorandom correlation generator PCG = (PCG.Gen, PCG.Expand) satisfying simulation-based security, the output of the seed generation PCG.Gen algorithm must at least have bit-length .

Proof. Let PCG = (PCG.Gen, PCG.Expand) be a pseudorandom correlation generator for C that satisfies simulation-based security. Then, in particular, the following protocol Π PCG has to satisfy one-sided security against P 1 : Party P 0 runs (k 0 , k 1 ) $ ← PCG.Gen(1 λ ) and sends k 1 to P 1 . Finally,

P 1 outputs R 1 ← PCG.Expand(1, k 1 ).
Let 1 be the Yao incompressibility entropy of the output of

C 1 (1 λ ) := {R 1 | (R 0 , R 1 ) ← C(1 λ )}. Further, let C 1 PCG (1 λ ) := {R 1 | (k 0 , k 1 ) $ ← PCG.Gen(1 λ ), R 1 ← PCG.Expand(1, k 1 )}.
By correctness of the PCG, the output of C 1 PCG (and therefore the output of the protocol Π PCG ) must meet the Yao incompressibility entropy 1 , as an efficient pair of compressor and decompressor could be used as a distinguisher between C 1 and C 1 PCG . By [HW15, Theorem 5], for any protocol between two parties P 0 and P 1 with one-sided security against "honest-but-deterministic"11 P 1 , where P 1 has no input, it holds: If the Yao incompressibility entropy of the output of P 1 is 1 , then the communication complexity from P 0 to P 1 must be at least 1 bits.

Therefore, as seed expansion is deterministic, the bit-length |k 1 | of the seed of the second party must be at least 1 . Reversing the roles of P 0 and P 1 together with additivity of Yao incompressibility entropy yields the required.

For the special case, where C outputs pairs of identical random strings (R, R), Gilboa and Ishai [GI99] sketched why pseudorandom pads cannot securely substitute perfectly-random pads returned by C in every secure protocol. We obtain this result as a straightforward corollary of Theorem 16.

Corollary 17. Let C be the correlation generator that on input 1 λ draws a string R $ ← {0, 1} uniformly at random and returns (R, R). Then, there exists no pseudorandom generator with seed length strictly less than , such that sampling a seed (and later expanding via the pseudorandom generator) can securely replace sampling uniformly at random from {0, 1} in every protocol.

Extension to deterministic functionalities. The above negative result gives a general counterexample for randomized functionalities. We add to this by showing that our weaker definition of PCG cannot replace correlated randomness in general, even in protocols that only realize deterministic functionalities. We prove this using public-key type assumptions, since we will use a correlation that produces the public key of a messy cryptosystem, where public keys statistically hide the message. We show that if instantiated with a PCG for C that produces a real public key, we completely break privacy of a (rather contrived) protocol.

Theorem 18. Suppose that the DDH, QR or LWE assumption holds, and let F C corr be a sampling functionality for a correlation C. Then there exists a reverse-sampleable correlation C, a secure PCG for C, and a protocol π for some deterministic functionality F such that: (i) π securely realizes F in the F C corr -hybrid model with malicious, statistical security; and (ii) π is passively insecure when F C corr is replaced by F PCG.Gen corr .

Proof. Let F be a trivial functionality which takes private inputs (x 0 , x 1 ) and outputs zero. Consider a public-key encryption scheme that, in addition to the usual algorithms (Gen, Enc, Dec), supports a messy mode of key generation, Gen * , where public keys output by Gen * are computationally indistinguishable from a real public key, however, ciphertexts produced with a messy public key are not decryptable, and statistically hide the message. This can be constructed from a range of assumptions including DDH, QR or LWE with standard methods, see for instance [PVW08]. Define the reverse-sampleable distribution to output (pk, pk)

$ ← C(1 λ ), where (pk, sk) $ ← Gen * (1 λ ).
In the protocol π, party P i sends Enc pk (x i ) to the other party and outputs zero. This is easily seen to be statistically secure by the messy property of the encryption scheme. We now construct a secure PCG for C. PCG.Gen samples a real key pair (pk, sk) $ ← Gen(1 λ ) and outputs (k 0 , k 1 ) where k 0 = (pk, sk) and k 1 = pk. PCG.Expand for either party simply outputs pk. This is a (computationally) secure PCG, due to the indistinguishability of the two modes of key generation. Nevertheless, the protocol π is now completely insecure when using PCG instead of F C corr , since P 0 can decrypt P 1 's input with the secret key.

Applying PCGs in Protocols with Correlated Randomness

In this section we show that one can use PCGs in a "plug-and-play" fashion in protocols consuming correlated randomness sampled by a given functionality. More precisely, we show that PCGs can be directly applied to any protocol using a weaker form of correlated randomness, where corrupted parties can influence their outputs.

A simple example is random OT, where the weaker functionality we can realize allows a corrupt sender/receiver to choose its outputs, then the other party's outputs are sampled at random correspondingly. When using OT in an MPC protocol, the OT is typically implemented from random OT by masking the actual OT inputs with fresh random OT outputs. Allowing a corrupt party to choose its own OT outputs does not affect the security of these protocols, since (intuitively) this can only weaken security for the corrupt party and not for honest parties. More generally, it turns out that many practical MPC protocols, including those based on preprocessed multiplication triples for arithmetic circuits [BDOZ11, DPSZ12] and binary circuits [NNOB12, WRK17a, WRK17b], use this kind of corruptible, correlated randomness, since it is often easier to design a protocol that realizes this.

More formally, the randomness is modelled by the functionality F C corr * (Fig. 1), where a corrupted party may first choose its own output, and then the honest party's output is computed with the reverse sampling algorithm for C. As we show in the following, PCGs can be used to securely realize F C corr * , opening up many important applications at no extra cost. To realize F C corr * , we use a simple protocol, Π C corr * , that calls F PCG.Gen corr so that each party obtains a seed k σ , which is then expanded to get the output PCG.Expand(σ, k σ ).

Functionality F C corr *
On input 1 λ , the functionality does as follows:

-If no parties are corrupt, sample (R0, R1)

$ ← C(1 λ ). -Otherwise, if Pσ is corrupt, wait to receive Rσ ∈ {0, 1} nσ from A, then sample R1-σ $ ← RSample(σ, Rσ).
The functionality outputs R0 to P0 and R1 to P1, and then halts. Proof. Let A be a static adversary against the protocol π. We construct a simulator Sim, which interacts with A and F C corr * to produce a view for A that is indistinguishable from a real execution of the protocol. When both parties are corrupted, the simulator just runs A internally and security is straightforward. Similarly, when both parties are honest, simulation is trivial and indistinguishability follows from the correctness of PCG. Now suppose that only P σ is corrupted, for σ ∈ {0, 1}. On receiving the input 1 λ , Sim samples a pair of seeds (k 0 , k 1 ) $ ← PCG.Gen(1 λ ), then sends k σ to A as its output of F PCG.Gen corr , computes R σ ← PCG.Expand(σ, k σ ) and sends this to F C corr * . Notice that in the ideal execution, the view of the distinguisher consists of the seed k σ and the honest party's output R 1-σ , which is computed by

F C corr * as R 1-σ $ ← RSample(σ, R σ ).
The only difference in the real execution, is that there the honest party's output is computed with PCG.Expand(1 -σ, k 1-σ ). These two views are computationally indistinguishable, due to the security property of PCG.

Relation Between PCGs and HSS

In this section we elaborate on the two-way relation between pseudorandom correlation generators and homomorphic secret sharing (HSS) schemes.

First, we show how to generically construct a PCG for additive correlations by combining a pseudorandom generator with a suitable HSS scheme. If the correlation is a degree-d polynomial and the PRG has degree d , then the HSS scheme must support evaluation of degree dd polynomials. This can be viewed as a step forward towards the concretely efficient PCG constructions given in Section 7.

Second, in the other direction, we show that a PCG for degree-d additive correlations, for constant d, implies (secret-key) HSS for degree-d multivariate polynomials. By the results of [BGI16a], this has implications for secure multi-party computation. For details we refer to Section 6.1.

Generic Construction of PCG for Additive Correlations from HSS

Our high-level strategy is as follows: We combine a standard pseudorandom generator (PRG), expanding a short seed into a long pseudorandom string, with a suitable HSS scheme, which allows to locally compute the target correlation on shares of a random input. More precisely, we consider the special case of additive correlations, where R 0 , R 1 are uniformly distributed subject to R 0 + R 1 = f (X) for a random input X and fixed function f . Now, consider an HSS scheme with additive reconstruction for f . Recall that given shares of the input X an HSS allows to locally evaluate f on the shares, such that the respective outputs add up to f (X).

This gives rise to the following PCG construction: During key generation a short seed k is shared between the players (as HSS shares). For expansion, the players can then locally evaluate f (PRG(k)) via the HSS operations. By the correctness of the HSS that indeed gives outputs R 0 , R 1 with R 0 + R 1 = f (X), where X = PRG(k). In this section we formally prove that the described construction meets the PCG requirements.

Note that the challenge lies in actually instantiating the described approach efficiently. This is due to the fact that known efficient HSS constructions only apply to limited classes of functions, for instance functions admitting small branching programs. It is therefore crucial to carefully select the underlying PRG and HSS. We will elaborate on how we address these challenges in Section 7.

To formalize the above outline, we first give a generalized definition of a pseudorandom generator, then formally define additive correlations corresponding to a function, before presenting the construction.

Let R be a ring and , n ∈ N. We consider distributions D over a ring R and write

X $ ← D (R) or simply X $ ← D (if R is clear from the context) to denote sampling from R via D .
Note that the following definition of D -pseudorandom generator coincides with the standard definition of a PRG, if we choose D (R) = U (R). We use this more general notion of a PRG, as for our PRG instantiation from LPN the seed is not chosen uniformly at random. Definition 20 (D -Pseudorandom Generator). Let R be a ring (parametrized implicitly by λ) and let D be a distribution on R . We say PRG : R → R n is a D -pseudorandom generator (PRG), if the following two distributions are computationally indistinguishable:

Y | X $ ← D (R), Y := PRG(X) and Y | Y $ ← U n (R) .
We will consider additive correlations corresponding to a family of functions F. Such a correlation is generated by outputting an additive secret-sharing of a function from f ∈ F applied to a source of randomness.

-PCG.Setup(1 λ ): Sample and output (sk, {ekσ} σ∈{0,1} ) ← HSS.Gen(1 λ ).

-PCG.Gen(sk): Sample r ← D and output (k0, k1) ← HSS.Share(sk, r).

-PCG.Expand(σ, ekσ, kσ, f ): Output Rσ ← HSS.Eval(σ, ekσ, kσ, f • PRG).

:= {f • PRG : r → f (PRG(r)) | f ∈ F}.
Definition 21 (Correlation Generators for Additive Correlations). Let R be a ring. Let n, m ∈ N and F ⊆ {f : R n → R m } be a family of functions. Then we define a correlation generator C F for F as follows: On input 1 λ and f ∈ F the correlation generator C F samples X $ ← U n (R), and returns a pair

(R 0 , R 1 ) ∈ R m × R m , which is distributed uniformly at random conditioned on R 0 + R 1 = f (X).
Note that C F is reverse-sampleable for any family of functions F, as given a function f ∈ F and a share R σ , one can draw an input

X $ ← U n (R) and set R 1-σ := R σ -f (X).
Further, note that it is straightforward to includes shares of the inputs in the correlation by considering the family

F := {f : R n → R n+m , X → (X, f (X)) | f ∈ F}.
Definition 22 (HSS satisfying Pseudorandomness of Outputs). We say an HSS HSS = (HSS.Gen, HSS.Share, HSS.Eval) for a function family

F := {f : R n → R m } satisfies pseudoran- domness of outputs, if for all f : R n → R m ∈ F, (sk, {ek σ } σ∈{0,1} ) ← HSS.Gen(1 λ ), X $ ← U n (R), (k 0 , k 1 ) $ ← Share(sk, X), and σ ∈ {0, 1} the output R σ $ ← HSS.Eval(σ, ek σ , k σ , f
) is distributed computationally close to uniformly at random over the output space.

Note that if f (U n (R)) is close to being uniformly random on R m , this property follows from the security of HSS. Proof. Correctness. Let f ∈ F. We have

{(R 0 , R 1 ) |(k 0 , k 1 ) $ ← PCG.Gen(1 λ ), R σ ← PCG.Expand(σ, k σ ) for σ ∈ {0, 1}} c ≈ {(R 0 , R 1 ) |(sk, {ek σ } σ∈{0,1} ) ← HSS.Gen(1 λ ), r $ ← D (R), (k 0 , k 1 ) ← HSS.Share(sk, r), R 0 ← HSS.Eval(0, ek 0 , k 0 , f • PRG), R 1 := f (PRG(r)) -R 0 } c ≈ {(R 0 , R 1 ) |r $ ← D (R), R 0 ← R m , R 1 := f (PRG(r)) -R 0 } c ≈ {(R 0 , R 1 ) |X $ ← U n (R), R 0 ← R m , R 1 := f (X) -R 0 }
as required, where the first transition follow by correctness of HSS, the second by pseudorandomness of outputs of HSS and the last by pseudorandomness of PRG.

Security. Let σ ∈ {0, 1}. We have

{(k 1-σ , R σ ) |(k 0 , k 1 ) $ ← PCG.Gen(1 λ ), R σ ← PCG.Expand(σ, k σ )} c ≈ {(k 1-σ , R σ ) |(sk, {ek σ } σ∈{0,1} ) ← HSS.Gen(1 λ ), r $ ← D (R), (k 0 , k 1 ) ← HSS.Share(sk, r), R 1-σ ← HSS.Eval(1 -σ, ek 1-σ , k 1-σ , f • PRG), R σ := f (PRG(r)) -R 1-σ } c ≈ {(k 1-σ , R σ ) |(sk, {ek σ } σ∈{0,1} ) ← HSS.Gen(1 λ ), r $ ← D (R), r $ ← D (R), (k 0 , k 1 ) ← HSS.Share(sk, r ), R 1-σ ← HSS.Eval(1 -σ, ek 1-σ , k 1-σ , f • PRG), R σ := f (PRG(r)) -R 1-σ } c ≈ {(k 1-σ , R σ ) |(sk, {ek σ } σ∈{0,1} ) ← HSS.Gen(1 λ ), X $ ← U n (R), r $ ← D (R), (k 0 , k 1 ) ← HSS.Share(sk, r ), R 1-σ ← HSS.Eval(1 -σ, ek 1-σ , k 1-σ , f • PRG), R σ := f (X) -R 1-σ },
where the first transition follows by correctness of HSS, the second transition by security of HSS and the last by pseudorandomness of PRG.

Generic Construction of HSS from a PCG

We observe that there is also a connection in the reverse direction. Namely, given a PCG for general, additive degree-d correlations for a constant d, we show how to construct a homomorphic secret sharing scheme for degree-d multivariate polynomials, a primitive which is interesting in its own right. Consider two parties who wish to compute shares of P (x) for some public multivariate polynomial P , given shares of x.

Let ⊗ d x denote the degree-d tensor product x ⊗ • • • ⊗ x. Given a PCG for the additive, degree-d correlation (r, ⊗ 2 r, • • • , ⊗ d r)
, we construct a (secret-key) homomorphic secret sharing scheme HSS = (HSS.Gen, HSS.Share, HSS.Eval) for P as follows.

-HSS.Share(x): generate PCG keys (k 0 , k 1 ) which expand to shares of (r,

⊗ 2 r, • • • , ⊗ d r), set
x ← x + r, and give to each party P σ a share s σ = (k σ , x ). -HSS.Eval(σ, s b , P ): On input party index σ ∈ {0, 1}, share s σ of a size-n input, and a degreed multivariate polynomial P , compute a share P σ of the polynomial P satisfying P (X) = P (X -r). Note that the coefficients of P are public degree ≤ d polynomials in r, hence shares of the coefficients can be locally computed given shares of the monomials r,

• • • , ⊗ d r. Output P σ (x ).
Correctness follows immediately by inspection, and security reduces to the security of the underlying PCG.

Silent Oblivious Transfer Extension From LPN

In this section we present a protocol for silent OT extension, which allows to generate n instances of random OT with sublinear communication complexity. To this end, we first show how to tweak the construction of Boyle et al. [BCGI18] to give correlated OT. Combining this observation with the OT extension technique of Ishai et al. [IKNP03] we obtain a PCG for random OT. Finally, we show how to use the protocol of Doerner and shelat [Ds17] for secure computation of the seed, giving sublinear OT extension.

Subfield Vector-OLE

Here, we introduce the notion of subfield vector oblivious linear evaluation (sVOLE), and show that sVOLE for F q over subfield F p ⊂ F q gives 1-out-of-p correlated OT. More precisely, a single big instance of sVOLE will give many 1-out-of-p OTs at once. Our construction of sVOLE comes with two additional advantages: It enjoys lower computational costs, because matrix multiplications are performed with a matrix over F p , and for p = 2 we can reduce security to the better-studied binary LPN problem, instead of its arithmetic variant over larger fields.

Subfield VOLE is a form of vector oblivious linear evaluation (VOLE) over F q , which computes w = ux + v, where the vector u is restricted to lie over a subfield F p ⊂ F q , for q = p r (and we multiply u with x ∈ F q component-wise, by viewing x as a vector over F p ). It outputs (u, v) to the sender and (x, w) to the receiver.

The construction in Fig. 3 uses the function spread n (S, y), which expands a set S = (s 1 , . . . , s |S| ) ⊂

[n] and a vector y ∈ F |S| p into the vector µ ∈ F n p , where µ s i = y i for i = 1, . . . , |S|, and µ j = 0 for j ∈ [n] \ S. It is a generalization of the VOLE generator from [BCGI18], which follows from the case p = q.

Construction G sVOLE Parameters:

-Security parameter 1 λ , integers n > n, q = p r , and noise weight t.

-A code generation algorithm C and H n ,n $ ← C(n , n, Fp).

-A multi-point FSS scheme (MPFSS.Gen, MPFSS.FullEval).

Correlation: Output (u, v) and (x, w), where x ← Fq, u

$ ← F n p , v $ ← F n q and w = ux + v.
Gen: On input 1 λ :

1. Pick a random size-t subset S of [n ], sorted in increasing order. 2. Pick a random vector y ∈ (F * p ) t and x

$ ← Fq. 3. Compute (K fss 0 , K fss 1 ) $ ← MPFSS.Gen(1 λ , fS,x•y). 4. Let k0 ← (m, n, K fss 0 , S, y) and k1 ← (m, n, K fss 1 , x). 5. Output (k0, k1).
Expand: On input (σ, kσ): Theorem 24. Suppose the (HW t , C, F p )-dual-LPN(n , n) assumption holds, and that MPFSS is a secure multi-point FSS scheme. Then the construction G sVOLE (Fig. 3) is a secure PCG for the subfield vector-OLE correlation.

1. If σ = 0: parse k0 as (m, n, K fss 0 , S, y). Set µ ← spread n (S, y) in F n p . Compute v0 ← MPFSS.FullEval(0, K fss 0 ) in F n q . Output (u, v) ← (µ • H n ,n , -v0 • H n ,n ). 2. If σ = 1: parse k1 as (m, n, K fss 1 , x). Compute v1 ← MPFSS.FullEval(1, K fss 1 ) in F n q , and output (x, w ← v1 • H n ,n ).
Proof. First let σ = 0. Here, in the real distribution, the adversary is given a key k 0 = (m, n, K fss 0 , S, y), where

(k 0 , k 1 ) $ ← G sVOLE .Gen(1 λ ), as well as the expanded output R 1 = (x, w) $ ← G sVOLE .Expand(k 1 ). We need to show that this is indistinguishable from the ideal distribution, where R 1 $ ← RSample(0, R 0 ).
Recall that RSample(0, R 0 ) proceeds by sampling x $ ← F q and outputing (x, w = ux + v). In the real distribution, x is also uniformly random, and from the correctness of MPFSS we have that

w = v 1 • H n ,n = (v 0 + x • spread n (S, y)) • H n ,n = v + x • u
which is identically distributed to the ideal distribution.

Next consider the case of σ = 1. We use the following sequence of games. Game G 0 . This is the real distribution, where the adversary gets

k 1 = (m, n, K fss 1 , x) and R 0 = (u, v) $ ← G sVOLE .Expand(0, k 0 ), that is, u = µ • H n ,n for µ $ ← HW t,n (F p ) and v = v 0 • H n ,n = (v 1 + x • µ) • H n ,n .
Game G 1 . Here, we compute K fss 1 using the MPFSS simulator

Sim(1 λ , • • • ), and v = (v 1 + x • µ) • H n ,n
. This is indistinguishable from G 0 , by the security of the MPFSS.

Game G 2 . Finally, here we compute u

$ ← F n p instead of µ•H n ,n , and let v = v 1 •H n ,n +x•u. Notice that since K fss 1 is independent of µ, any adversary distinguishing G 1 and G 2 can be used to attack (HW t , C, F p )-dual-LPN(n , n).
Game G 2 is identical to the ideal distribution, so this completes the proof of the security property.

Finally, we show the correctness property, namely, that the outputs (R 0 , R 1 ) = (u, v, x, w) are computationally indistinguishable from outputs of D(1 λ ). By the same reasoning as security for σ = 0, R 1 is already identically distributed to the output of RSample(0, R 0 ), so we write w = ux + v. Denoting the uniform distribution on F n p by U n p , we then use the following sequence of hops:

(u, v, x, w) = (µ • H n ,n , (v 1 + x • µ) • H n ,n , x, ux + v) c ≈ (µ • H n ,n , (U n q + x • µ) • H n ,n , x, ux + v) (3) s ≈ (µ • H n ,n , U n q , x, ux + v) (4) c ≈ (U n p , U n q , x, ux + v) (5) ≡ D(1 λ )
where (3) follows from the pseudorandomness of the MPFSS outputs (cf. Remark 2). Hop (4) holds because the LPN assumption implies from Remark 8 that H n ,n must be full-rank with overwhelming probability, so preserves uniformity when multiplying by a uniform vector. Finally, (5) also holds due to the pseudorandomness of the LPN assumption.

Application to Correlated OT

Subfield VOLE immediately gives a PCG for correlated OT (or ∆-OT). This is a batch of 1-outof-2 OTs where the sender's strings are of the form (w i , w i ⊕∆) for some fixed string ∆, and is the main building block in practical MPC protocols such as TinyOT [NNOB12] and authenticated garbling [WRK17a, WRK17b].

To obtain correlated OT, we run subfield VOLE with p = 2 and q = 2 r , so the VOLE sender obtains u i ∈ F 2 , v i ∈ F 2 r , while the VOLE receiver gets x ∈ F 2 r and w i = x • u i + v i , for i = 1, . . . , n. Now switching the roles of sender and receiver, the VOLE sender can be seen as an OT receiver with choice bit u i and string v i . This gives us a correlated OT, since the OT sender (formerly VOLE receiver) can compute the strings (w i , w i + x), and we have

v i = w i if u i = 0 and v i = w i + x if u i = 1.

Application to Matrix Multiplication

Our construction for subfield VOLE can alternatively be seen as a PCG for tensor product:

writing x ∈ F q as x = (x 1 , . . . , x r ) ∈ F r p , and u = (u 1 , . . . , u n ) ∈ F n p , sVOLE computes secret shares of x ⊗ u, that is, x i • u j for every (i, j) ∈ [r] × [n]
. This allows evaluation of secret-shared tensor products in 2-PC, which can in turn be used for matrix multiplication.

The seed size scales linearly in r, but this still improves upon the naive way of using r PCGs for VOLE over F p ; the latter approach (with the VOLE from [BCGI18]) has seed size O(rt • (λ log n + log p)) bits, whereas we reduce this to O(t • (λ log n + r log p)) bits, saving at least a log n factor when log p = O(λ).

PCG for Random Oblivious Transfer

In Fig. 4, we use the G sVOLE PCG to construct a PCG for the random oblivious transfer correlation. Given the above observation that subfield VOLE implies correlated OT, this is straightforward, as we can apply the OT extension technique of Ishai et al. [IKNP03], which converts

Construction G OT Parameters: -Security parameter 1 λ , integers n, q = p r = λ ω(1) . -An Fp-correlation-robust function H : {0, 1} λ × Fq → {0, 1} λ . -The subfield-VOLE PCG (G sVOLE .Gen, G sVOLE .Expand) Correlation: Outputs (R0, R1) = {(ui, wi,u i )} i∈[n] , {wi,j} i∈[n],j∈[p] , where wi,j $ ← {0, 1} λ and ui $ ← {1, . . . , p}, for i ∈ [n], j ∈ [p].
Gen: On input 1 λ , output (k0, k1) ← G sVOLE .Gen(1 λ , n, p, q). Expand: On input (σ, kσ):

1. If σ = 0: compute (u, v ) ← G sVOLE .Expand(σ, kσ), where u ∈ F n p , v ∈ F n q . Compute vi ← H(i, v i ) for i = 1, . . . , n
and output (ui, vi).

2. If σ = 1: compute (x, w ) ← G sVOLE .Expand(σ, kσ), where x ∈ Fq, w ∈ F n q . Compute wi,j ← H(i, w i -j • x) for i = 1, . . . , n, ∀j ∈ Fp
and output {wi,j}i,j.

Fig. 4. PCG for n sets of 1-out-of-p random OT correlated OTs into random OTs using a suitable hash function. We extend this in a natural way to generate 1-out-of-p random OTs using subfield VOLE over F p . Note that for security when applying the hash function, we now need q = λ ω(1) . We use the following generalization of a correlation robust function over F p . As recently shown in [GKWY19], this can be instantiated with fixed-key AES modeled as a random permutation when p = 2.

Definition 25 (F p -correlation robust function). Let n = poly(λ) and t 1 , . . . , t n , x be uniformly sampled from F r p , where p r = λ ω(1) . Then,

H : {0, 1} λ × F r p → {0, 1} λ is F p -correlation robust if the distribution t 1 , . . . , t n , {H(1, t 1 -j • x), . . . , H(n, t n -j • x)} j∈Fp\{0} is computationally indistinguishable from uniform on F rn p × {0, 1} λ(p-1)n .
Theorem 26. Suppose that H is an F p -correlation robust hash function and G sVOLE is a secure PCG. Then the silent OT construction (Fig. 4) is a secure PCG for the random 1-out-of-p OT correlation.

Proof. We start by showing the correctness property. First, from the correctness of G sVOLE we have

v i = H(i, v i ) = H(i, w i -u i • x) = w i,u i
as required. Indistinguishability of the outputs from OT n p follows first from indistinguishability of the VOLE outputs (u i , v i , x, w i ), and secondly by a standard reduction to the F p -correlation robustness property of H.

u i , v i , w i,j = u i , H(i, w i -u i • x) c ≈ (U, H(i, ))
We now consider the security property, for the case σ = 0. Here, the real distribution consists of the seed k 0 and the sender's outputs w i,j , for i = 1, . . . , n and j ∈ F p . From correctness we have that for u, v ← G sVOLE .Expand(0, k 0 ), it holds that H(i, v i ) = w i,u i . From the security property of G sVOLE , we can replace all the sender's outputs w i,j , except for w i,u i , with ones computed using uniform values x, w i , instead of from G sVOLE .Expand. These are then indistinguishable from uniform under the F p -correlation robustness of H.

When σ = 1, the real distribution contains the seed k 1 and the receiver's outputs u i , v i . As before, from the correctness property we have that v i = w i,u i , where w i,j is computed from k 1 via G sVOLE .Expand and the hash function. We only need to show that u i is uniform, which follows directly from the security property of G sVOLE when σ = 1.

From a PCG to Silent OT Extension

To construct an OT extension protocol, we can use 2-PC to securely compute the Gen algorithm of G OT , and then have each party locally expand its output using G OT .Expand. Applying Theorem 19 from Section 4.3, this realizes a corruptible form of the ideal functionality for random oblivious transfer, where corrupt parties may influence their random outputs.

To do this efficiently with semi-honest security, we use the black-box protocol of Doerner and shelat [Ds17] (also used in [BCGI18]) for setting up distributed point function keys. For a single point function of domain size n, this requires O(log n) OTs on O(λ)-bit strings, giving O(t log n) OTs for a multi-bit point function. Implementing each OT with (non-silent) OT extension [IKNP03] costs O(λ) bits of communication, plus a setup phase of λ base OTs. Putting this together, we obtain the following.

Theorem 27. Suppose the (HW t , C, F p )-dual-LPN(n , n) assumption holds, and an F p -correlation robust hash function exists. Then there is a protocol that uses O(λ) 1-out-of-2 OTs to realize n instances of random 1-out-of-p OT with semi-honest security, using O(tλ log n) + poly(λ) bits of communication.

We remark that this gives OT with sublinear communication when t = o(n/(λ log n)), which translates to an instance of LPN with noise rate 1/ω(λ log n). If the matrix H n ,n in G sVOLE is uniformly random, the computational complexity is dominated by O(n •n) arithmetic operations; using more structured matrices based on LDPC codes or quasi-cyclic codes, we get respective costs of O(n ) or Õ(n ) arithmetic and PRG operations.

Concrete Efficiency

In Section A of the Appendix, we analyze these costs more concretely and give a breakdown of the communication complexity, as well as some approximate runtime estimates based on the cost of the main operations. For example, for n ≤ 2 22 OTs, the PCG seed size is under 10kB and requires less than 30kB of communication to create with the distributed setup procedure. After setup, we estimate that these seeds can be expanded into 16MB of OTs on 128-bit strings at a rate of around 1 million per second, or 2 million per second when expanding to 1MB, using a single core of a CPU on a modern laptop. When including the distributed setup procedure, in these two cases we get an amortized communication complexity of just 2.6 and 0.2 bits per OT, respectively.

Applications of Silent OT Extension

Protocols generating (pseudo)random OT have a wide range of applications. In this section we show how our silent OT extension can plugged in to obtain a batch oblivious pseudorandom function (OPRF) with under 1 bit of communication per OPRF evaluation on a random input, which is useful for private set intersection protocols. Further, we sketch how to construct a NIZK proof system in the preprocessing model, where the setup cost is independent of both the number and size of statements.

Batch oblivious PRF. Our random 1-out-of-p OT generator can even be used when p is exponentially large, provided the sender only needs to obtain polynomially many outputs. This type of random OT can be viewed as a form of batch, one-time oblivious PRF: each string w i,j output by the sender can be seen as a PRF evaluation F (k i , j), where k i is a key implicitly defined by the sender's randomness. The receiver learns a random u i and the value w i,u i = F (k i , u i ). We can also allow the receiver to choose its evaluation point u i , with an additional λ = log p bits of communication. In [KKRT16], this type of OPRF was used to improve the efficiency of private set intersection protocols. Applying our PCG, we get a highly efficient batch related key OPRF usable in PSI, where each OPRF evaluation at a chosen point costs around λ bits of communication. This reduces the overall communication in the PSI protocol from [KKRT16] by around a factor of two.

Resuable NIZKs from LPN. In [BCGI18], it was shown how to use a PCG for vector-OLE to build a reusable NIZK in the preprocessing model. NIZK in the preprocessing model relaxes the standard NIZK definition by allowing the prover and the verifier to interact during a preprocessing phase, to generate a respective proving key and verification key. The construction from the vector-OLE PCG obtained a reusable preprocessing NIZK, where the preprocessing cost is independent of the number of theorems to be proven, if this is a priori bounded, under an arithmetic version of LPN.

In Section A of the Appendix, we observe that we can obtain an alternative NIZK construction by using our PCG for random OT, which brings two main advantages:

-It only requires the standard LPN assumption over F 2 , while the NIZK of [BCGI18] must rely on a generalization of LPN to exponentially large fields. -The preprocessing phase is independent of both the number of theorems to be proven, and the size of these theorems. In comparison, the preprocessing phase in [BCGI18] is independent of the number of theorems to be proven, but grows linearly with a bound on the size of each statement. This is because we use OT instead of VOLE, so are no longer restricted to a batch setting where the same query must be reused for many statements.

On the down side, our OT-based NIZK protocols do not enjoy some of the efficiency features of the VOLE-based constructions from [BCGI18]. The latter support NIZK for an NP-relation represented by an arithmetic circuit of size s over F, where the online computation of both the prover and the verifier consists of O(s) arithmetic operations, and with O(1/|F|) soundness error. We do not know how to achieve this using the current OT-based approach.

PCG for Constant-Degree Correlations from LPN

In this section, we describe a pseudorandom correlation generator for arbitrary constant-degree correlations, from the dual LPN assumption over large fields. We first describe the construction for the case of bilinear correlations. More precisely, we consider the following type of additive correlations: the party P σ receives pseudorandom vectors (x σ , z σ ) such that B(x 0 , x 1 ) = z 0 +z 1 , where B is a bilinear function. We note that this type of correlation generalizes naturally to the setting where the entries x 0 and x 1 are additively shared between the parties (instead of being respectively known to one party), see Section C.

Theorem 28. Suppose the (HW t , C, F p )-dual-LPN(n , n) assumption holds, and that MPFSS is a secure multi-point FSS scheme. Then the construction G bil (Fig. 5) is a secure PCG for general bilinear correlations.

Correctness follows by inspection, using the correctness of the MPFSS, and the bilinearity of the tensor product, and the security analysis is essentially indentical to the analysis of the dual vector-OLE generator described in [BCGI18] (see also Section 5.1).

Construction G bil

Parameters: 1 λ , n, n , t, p ∈ N, where n > n. A code generation algorithm C and

H n ,n $ ← C(n , n, Fp). A bilinear function Bc : (α, β) → c • (α ⊗ β)
, where ⊗ denotes the tensor product.

Gen: On input 1 λ :

1. Pick two random size-t subsets (S0, S1) of [n ], sorted in increasing order. 2. Pick two random vector (y0, y1) ∈ (F t p ) 2 . 3. Compute (K fss 0 , K fss 1 ) $ ← MPFSS.Gen(1 λ , fS 0 ×S 1 ,y 0 ⊗y 1 ). 4. Let k0 ← (n, K fss 0 , S0, y0) and k1 ← (n, K fss 1 , S1, y1). 5. Output (k0, k1). Efficiency. Instantiating the MPFSS as in [BCGI18], the setup algorithm of G bil outputs seeds of size t 2 •( log n (λ+2)+λ+log 2 |F|) bits, which amounts to Õ(t 2 ) field elements over a large field (log 2 |F| = O(λ)). Expanding the seed involves (tn ) 2 PRG evaluations and O(n

Expand: On input (σ, kσ), parse kσ as (n, K fss σ , Sσ, yσ). Set µσ ← spread n (Sσ, yσ) in F n p and xσ ← µσ • H n ,n . Compute vσ ← MPFSS.FullEval(σ, K fss σ ) in F (n ) 2 p and set zσ ← -c • (vσ • (H n ,n ⊗ H n ,n )) . Output (xσ, zσ).
• n ) 2 = O(n 4 ) arithmetic operations.
Generalization. The scheme G bil immediately generalizes to a PCG for arbitrary constant-degree polynomials, 13 where the size of the shares grows as Õ(t d ) and the computational complexity is Õ((tn ) d + (nn ) d ). It allows two parties to locally compute, given the shares, additive shares of (r, P (r)), where r is pseudorandom (under LPN) and P is a degree-d multivariate polynomial over F.

To see this, notice that we can replace y 0 ⊗ y 1 in Gen with ⊗ d y = y ⊗ • • • ⊗ y, where ⊗ d y denotes the tensor product of y with itself d times (that is, the list of all degree-d monomials of y). The parties can then compute shares of all degree-d terms in P (r) for a random r; to obtain shares of r and the lower-degree terms, we extend the MPFSS values to include (y, y ⊗ y, • • • , ⊗ d-1 y) as well as ⊗ d y.

Corollary 29. Suppose the (HW t , C, F p )-dual-LPN(n , n) assumption holds, and that MPFSS is a secure multi-point FSS scheme. Then there exists a secure PCG for general constant-degree correlations, with share size Õ(t d ) and computational complexity O((n • n ) d ).

In particular, using n = O(n), we get: Corollary 30. Assuming the standard LPN assumption over F p with noise rate r = o(n 1/d-1 ) and linear number of samples, there exists a PCG for general degree-d polynomials, with sublinear share size (in the output size n) and polynomial computation.

HSS and Secure Computation for Constant-Degree Polynomials from LPN

We observe that by Section 4.4 (Generic Construction of HSS from PCG), the above construction directly gives rise to a homomorphic secret sharing scheme for degree-d multivariate polynomials. Therefore, we get: Corollary 31. Suppose the (HW t , C, F p )-dual-LPN(n , n) assumption holds, and that MPFSS is a secure multi-point FSS scheme. Then there exists a secure HSS for general degree-d multivariate polynomials over F, with share size n + Õ(t d ) and computational complexity O((n • n ) d ).

Plugging this new HSS construction into the result of [BGI16a], we immediately obtain new results regarding secure computation from the LPN assumption:

Corollary 32. Suppose the (HW t , C, F p )-dual-LPN(n , n) assumption holds, and that MPFSS is a secure multi-point FSS scheme. Then there exists a 2-party secure computation protocol with semi-honest security for general degree-d multivariate polynomials over F, with communication

Õ(n + t d ) and computational complexity O((n • n ) d ).
In particular, applying the above corollary to layered circuits, we obtain a generic secure two-party protocol from LPN with communication smaller than the circuit size:

Corollary 33. Suppose the (HW t , C, F p )-dual-LPN(n , n) assumption holds, and that MPFSS is a secure multi-point FSS scheme. Then for any constant c, there exists a 2-party secure computation protocol with semi-honest security for arbitrary layered circuits of size s, with total communication bounded by s/c, and computational complexity bounded by s • λ 2 O(c) .

PCG Constructions from Groups and Lattices

In this section we give PCG constructions for a range of correlations, starting from the generic construction of Section 4.4. In particular, we will describe PCGs for the generation of bilinear correlations from groups, and PCGs for so-called authenticated Beaver triples from lattices.

We start this section by presenting two specialized low-degree PRG constructions that will serve as crucial building blocks for our high-end constructions. Note that a straightforward choice like Goldreich's low-degree PRG [Gol00, MST03] turns out to be not suitable. (For more discussion we refer to Section 7.3.)

In Section 7.3 we deviate from the generic construction by splitting up the evaluation of the PRG and the evaluation of the function f itself, which is captured in the notion of compressible HSS.

To give a high-level idea, note that one can roughly think of the underlying HSS scheme to consist of two levels, where multiplication of a level-1 share with a level-2 share yields a level-2 share. The idea now is to start with compressed level-1 and level-2 shares, which can be expanded to long pseudorandom level-1 and level-2 shares, on which subsequently f is evaluated via the HSS itself. In other words, the PRG is evaluated on the shares directly and not via the HSS operation (see also Section 7.2).

In Section 7.4 we follow the generic construction of Section 4.4 more closely, building on the MQ-based PRG described in the following and several variants of lattice-based HSS schemes.

Pseudorandom Generators from MQ and LPN

Let R be a ring and n ∈ N. By U n (R) we denote the uniform distribution on R n . Recall that we consider distributions D over a ring R and write X ← D (R) or simply X ← D (if R is clear from the context) to denote sampling from R via D . Further, for a matrix distribution M over a ring R n×m we write M(n, m, R) to make the parameters explicit.

Remark 34 (PRG from MQ). Let R be a ring, and , n ∈ N. Let M be a distribution over R 2 ×n and M $ ← M( 2 , n, R). We assume that for an appropriate choice of parameters

PRG MQ : R → R n , r → M • (r ⊗ r)
is a PRG. We say M( 2 , n, R) has sparsity ρ, if for every matrix M in the image of M( 2 , n, R), the number of non-zero entries in any column of M is at most ρ.

Note that if we choose M( 2 , n, R) = U 2 ×n (R), the above assumption equals the MQ assumption of [MI88, Wol05, AHI + 17]. While multivariate public-key cryptography has a long history of schemes being built then broken, we stress that the MQ assumption itself (which states that it is infeasible to solve a random system of quadratic equations) is believed to be a conservative assumption (in particular, the pseudorandomness of the MQ-based PRG reduces to the conjectured one-wayness of solving a random system of quadratic assumptions [BGP06]), and underlies the security of plausible and well-studied primitives in minicrypt (such as signatures scheme, or the stream cipher QUAD [BGP06]). Existing attacks on multivariate public-key cryptosystems all exploited the fact that the security of these systems did not in fact reduce to the MQ assumption. Furthermore, variants of MQ with a sparse matrix were considered several time as a natural optimization of MQ-based schemes [BCJ07, LLY08], and the resistance of the variant with sparse matrix against classical attacks was analyzed in [BCJ07, DyY07].

Remark 35 (D (R)-PRG from LPN). Let R be a ring, and , k, c, τ, n ∈ N, such that = τ ck.

Let M be a distribution on R τ c ×n and

M $ ← M(τ c , n, R). Let PRG LPN : (R τ ) ck → R n , (r 1 , . . . , r ck ) → M • k-1 i=0 r 1+i•c ⊗ • • • ⊗ r c+i•c ,
where r i ∈ {0, 1} τ for all 1 ≤ i ≤ ck. We assume that for appropriate choice of parameters PRG LPN is a D (R)-PRG, where D is the distribution returning vectors that have exactly one non-zero entry (chosen uniformly at random in R\{0}) in every block of length τ .

Note that k-1 i=0 r 1+i•c ⊗ • • • ⊗ r c+i•c yields a random vector in R τ c
with exactly k non-zero entries. Therefore, the above assumption corresponds to the (Ber k (R) τ c , M, R)-dual-LPN(τ c , n) assumption, where Ber k (R) τ c is the distribution returning vectors in R τ c with exactly k non-zero entries.

Semi-Generic PCG Construction from Compressible HSS

As mentioned before, while our group-based constructions described in the following section build upon the generic approach, they exploit the specific structure of the underlying HSS to achieve better parameters: the generic construction would require a degree-4 HSS already to generate bilinear correlations using the LPN-based PRG. In contrast, our constructions achieve the same expressivity starting only from degree-2 HSS, building upon their homomorphic properties. The essence of this approach is captured in the following corollary. For a more formal treatment of compressible HSS we refer to Section C.3.

Corollary 36 (Informal). Let R be a ring and n, m, τ, c, k ∈ N. Let F ⊆ {f : R n → R m } be a family of functions. Let HSS = (HSS.Gen, HSS.Share, HSS.Eval) be an homomorphic secret sharing scheme for F with overhead O HSS that supports degree-c compression of the shares (i.e. compressed shares can be decompressed via degree-c homomorphic operations preserving the respective share-level). Then, under the (Ber k (R) τ c , M, R)-dual-LPN(τ c , n) assumption, there exists a PCG for the correlation generator C F with key-length upper bounded by τ ck • O HSS .

Group-Based PCG for Bilinear Correlations: an Overview

In this section, we describe a construction of a PCG for general bilinear correlations, building upon the group-based HSS scheme of [BGI16a, BGI17, BCG + 17]. Since our construction is quite involved, and the full description would not fit in the body of this paper, we only provide a highlevel overview here; the detailed construction is given in Appendices C, D, and E. The high-level idea of our construction is best explained by the compressible HSS abstraction, outlined in the "Overall Methodology" section of the introduction. To construct a PCG for bilinear correlations, we rely on the group-based HSS of [BGI16a, BGI17, BCG + 17]. While this HSS can support evaluation of arbitrary branching programs, this comes at a very high computational cost, which makes it concretely impractical. Note that the full version of [BCG + 17] describes a construction of PCG (which is called "cryptographic capsule" in their terminology) building upon the groupbased HSS together with Goldreich's low-degree PRG [Gol00,MST03]. While the authors did not provide concrete efficiency estimations for this construction, our rough calculations show that it is entirely impractical: Goldreich's PRG requires very large seeds (at least 2 14 bit long to achieve a stretch of only n 1.45 according to the recent study of [CDM + 18]), and the HSS must be employed in a parameter regime where encoding each bit of the seed requires O(λ) ElGamal ciphertext (e.g. 160 ciphertexts, when targetting 80 bits of security). Furthermore, the group-based HSS has an inverse failure probability per output which scales superlinearly with the encoding size. We estimate that an optimized implementation of their scheme would require a few hours of runtime to generate each output, and the PCG seed remains larger than the total amount of correlation generated (in fact, larger than the cost of a naive interactive generation of the material) for any feasible value of n.

Our improvement stems from two key observations. First, when the HSS is restricted to evaluating only bilinear function (as opposed to general branching programs), the encodings in the group-based HSS can be considerably smaller, a single ElGamal ciphertext per bit of the seed (this was observed in [BCG + 17]). This in itself would not suffice, since generating the bilinear correlation requires first evaluating a PRG, then computing a bilinear function on top of that, which requires HSS of degree at least 4 (since a PRG must have degree at least 2 in its inputs). Our second key observation is that by relying on the BGN cryptosystem instead of ElGamal (which requires pairings but allows homomorphic evaluation of degree-3 functions on the ciphertext), extending the HSS-encoded seed into long pseudorandom encodings can be done directly on the encoding, without requiring any of the HSS operations. More precisely, the group-based HSS requires two types of encodings: a level-1 encoding of a vector x, which is essentially a bitwise ElGamal encryption (when restricting our attention to HSS for degree-2 functions), and a level-2 encoding of a vector y, which is essentially a pair of additive shares of both y and sk • y, where sk is the ElGamal secrey key; the HSS operations allows the parties to locally compute shares of B(x, y) from these encodings, for any bilinear function B.

Using the BGN encryption scheme [BGN05], the level-1 encoding of a pseudorandom vector x of length n can be locally compressed by relying on the LPN-based PRG described in Section 4.4: the compressed encoding contains 2k component-wise BGN encryptions of random length-√ n unit vectors u i , v i , for a total size of 2k √ n BGN ciphertexts, where k is a parameter of ther underlying LPN assumption which denotes the number of noisy coordinates in the error vector. Then, the parties can homomorphically compute BGN encryptions of x = M • k i=1 u i ⊗v i , where M is a public code matrix; security follows from the dual LPN assumption with code matrix M by observing that k i=1 u i ⊗ v i is just a uniformly random k-sparse vector. At the same time, using two parallel instances of the recent LPN-based PCG for vector-OLE of [BCGI18] allows to efficiently compress shares of y and sk • y, where y is a pseudorandom vector and sk is a shared value, to only O(λk log n) bits. Hence, we get a highly optimized PCG for bilinear functions by distributing compressed shares of level-1 and level-2 encodings of pseudorandom vectors to the parties, from which they can locally expand the compressed shares and apply the HSS operation to obtain shares of B(x, y).

In Appendix C, we formally introduce the construction following the above informal overview. In Appendix D, we discuss many optimizations that can be applied to the scheme, in particular by relying on new variants of the LPN assumption, which we introduce and analyze in the same section. Eventually, in Appendix E, we provide detailed concrete efficiency estimations for our PCG, for generating OLE correlations over small fields, together with further optimizations tailored to this setting, and a concrete analysis of the resistance of our new assumption to a variety of attacks. Note that our PCG are already useful for generating OT correlations, since they are programmable, and therefore allow to generate multiparty correlations from pairwise correlations (unlike our silent OT extension protocol) -see Section 8 for the details.

A downside of the group-based HSS is that it only guarantees an imperfect correctness for the output, with an inverse-polynomial failure probability. To use the generated material in a subsequent protocols, the parties must therefore first sanitize the output, converting the faulty correlations into non-faulty correlations. This is non-trivial, since the position of the faulty outputs cannot be simply revealed, as it depends on secret information that should not be leaked. We apply the punctured OT strategy of [BGI17] to describe an efficient sanitization procedure, and we provide detailed concrete estimates of its efficiency in our setting. The strategy only requires adding a negligible amount of material to the PCG seed, and requires less than 3 bits of amortized communication per sanitized correlation. Eventually, building upon our new protocol for silent OT extension from Section 5, we devise an entirely new sanitization procedure, which is much more efficient and is compatible with efficient distributed seed generation.

Concrete Efficiency

Based on our our calculations in Appendices C, D, and E, we estimate that our group-based PCG for bilinear correlations should generate correlations at a rate of a few hundred milliseconds per (sanitized) output (e.g. about 200ms for generating one OLE correlation over a small ring, amortizing over n > 2 20 outputs), with a seed size reaching its breakeven point (where the size in bits of the seed is smaller than the number of outputs generated) for target number of correlations around 2 24 . Since this is a fairly low number (preprocessing phases in standard MPC protocols must already generate billions of correlated values for securely evaluating moderately large functions), we believe that our result is already of practical interest. We stress again that our estimates are based on counting the number of operations and estimating the cost of each operation using benchmarks; the actual running time of an implementation might be somewhat higher due to other costs such as cache misses.

PCG from Lattices

In this section we consider constructing PCGs from lattices for generating a broader range of correlations. One example of useful correlations are authenticated Beaver triples which are used to achieve fast online computation time in multi-party protocols like [DPSZ12]. PCGs based on lattices can replace the preprocessing phase to yield protocols with very fast online time, where the players can exchange a short seed at any point of time and then expand their respective seeds silently before engaging in a secure computation. Thus, even though PCGs from lattices come with an expensive setup and slower expansion time, they are useful to obtain protocols with better overall complexity.

We focus on the use-case of generating 2-party shares of authenticated Beaver triples, that is additive shares of tuples (a, b, ab), (aα, bα, abα), where α is a MAC-key for authentication (not known to any party in the plain). In the following we describe different lattice-based PCG constructions for generating such shared triples and provide efficiency estimates in Figure 2. For details we refer to Section F in the Appendix.

We follow the high-level approach of Section 4.4 based on homomorphic secret sharing (HSS), where the parties first jointly generate a shared PRG seed and for expansion disjointly evaluate f α • PRG on the shares, where f α : (a, b) → (a, b, ab, aα, bα, abα). We instantiate the HSS scheme required in different ways. As underlying encryption scheme we use the BGV encryption scheme [BGV12]. For the most efficient instantiation we use the pseudorandom generator PRG MQ : Z p → Z n p from Remark 34 with n = 2 /24, where we choose a matrix with sparsity ρ = 100. Note that the choice of ρ is somewhat arbitrary and should be taken with some care, but to our knowledge , where R := Z[X]/(X N + 1). The runtime estimates are based on NFLLib [ABG + 16] with log q ≈ 744 and N = 2 14 . Our results: We can expand correlated seeds of size '|key|' to 128-bit authenticated multiplication triples of total size '|triples|'. As PRG we employ PRG MQ : Z p → Z 2 /24 p , based on the M( 2 , 2 /24, Rp)-MQ assumption with sparsity ρ = 100 (here, = 2 9 for all rows w/o packing and = N for the row w/ packing). The number of (maximal) obtained triples is 2 • N/24 for the rows with naive ciphertext packing (including the iterative version) and N 2 /24 for the row with smart packing. Setup requires communication of roughly size |key| per party. We ignore small contributions like setting up the public key and generating suitable shares of the MAC key α, as computation and communication are dominated by generation and distribution of encryptions of the PRG seeds.

does not give rise to any attacks: While algebraic attacks either do not profit from sparsity at all (like the Groebner basis attack) or not significantly (like the XL attack), SAT solvers, which indeed heavily take advantage of sparsity, are still far from feasible for our choice of parameters.

In [DHRW16, BKS19] it is shown how to construct an HSS directly from a somewhat homomorphic encryption scheme, when the underlying encryption scheme additionally supports distributed decryption (i.e. decryption with additive shares of the secret key yields additive shares of the plaintext). We give a more detailed explanation in Theorem 55 in the Appendix. Our first PCG is based on this construction (instantiated with the encryption scheme of Brakerski et al. [BGV12]). On a high level, the resulting PCG is as follows.

Seed generation. The key generation algorithm of the underlying encryption scheme is called and additive shares of the secret key generated. Further, a MAC key α ∈ Z p and PRG seeds r a , r b $ ← Z p are chosen uniformly at random and encrypted (componentwise). The parties each obtain the public key, their respective share of the secret key and all encryptions as PCG seed. Public key and secret key shares of the encryption scheme and the encryption of the MAC key α can be reused across many instances. Expansion. Both parties homomorphically evaluate F α (PRG(r a ), PRG(r b )) on the ciphertexts (via the homomorphic operations of the underlying encryption scheme), where F α : Z n p ×Z n p → (Z n p ) 6 corresponds to evaluating f α componentwise on each of the n input tuples. Finally, each party decrypts the result with their respective share of the secret key.

The described approach would allow expanding 2 ciphertexts into n shares of authenticated Beaver triples (over Z p ). Additionally, we employ naive ciphertext packing [SV14]: Instead of encrypting a single Z p -element at a time one can 'pack' N Z p -elements into each ciphertext (where N = 2 14 is the dimension of the plaintext space over Z). This way, starting with 2 ciphertexts, expansion yields N • n shared authenticated Beaver triples. For more details we refer to Section F in the Appendix.

The second approach is based on the observation that not all authenticated Beaver triples have to be computed at once, employing the sparsity of the MQ-matrix. This is particularly desirable, as it allows computing correlations incrementally, only when needed. Note though that the given iterative approach is somewhat limited, as it is still restricted to sub-quadratic stretch and allows only to compute N Beaver triples at a time (due to naive ciphertext packing).

The third approach uses ciphertext packing more smartly, by letting the different 'slots' of the ciphertexts interact with each other. Here, starting with a single ciphertext (holding 2 14 plaintexts), we achieve almost quadratic stretch to 2 28 /24 triples. The better expansion rate (allowing to go from N to ≈ N 2 instead of from N to ≈ 2 N triples), comes at a cost: Due to the high computational costs introduced by key switching during matrix multiplication, this approach seems currently impractical.

The last approach replaces the homomorphic multiplication with the MAC key α on ciphertexts with the more efficient multiplication operation of the HSS by Boyle et al. [BKS19]. More precisely, during seed generation secret shares of the MAC key α times the secret key sk are generated (instead of an encryption of α). Then, the last level of multiplication (i.e. to obtain aα, bα, abα) can be replaced by a distributed decryption with the shares of α • sk, saving 3 homomorphic multiplications per triple generated. Note that this construction is compatible with the 'iterative' and 'packed' versions of BGV described. It does not seem competitive to use an HSS solely based on [BKS19], as, when handling more than one homomorphic multiplication, their scheme has to account for the plaintext magnitude, which in the described setting would lead to significantly larger parameters.

Multi-Party PCG for Bilinear Correlations

In this section, we construct multi-party PCGs for a useful class of bilinear correlations, capturing M -party OT, M -party vector OLE, M -party Beaver triples, and more. Incorporating into appropriate existing secure computation protocols, this yields secure M -party protocols for corresponding computations, with short correlated randomness, whose online execution requires only lightweight information theoretic operations and communication that scales linearly in the number of parties M .

Our construction approach provides a semi-generic transformation from any PCG for the corresponding 2-party bilinear correlation that satisfies an additional "programmability" property. Roughly, this property requires a way of "reusing" inputs across instances without compromising security. The M -party construction will leverage this structure by executing M (M -1) pairwise instances of the underlying 2-party PCG, for all the "cross-terms."

We obtain M -party PCGs for various bilinear correlations by identifying corresponding 2party PCG constructions that satisfy the required programmability notion. In particular:

-M -party VOLE: From lightweight DPF and LPN, leveraging the 2-party VOLE generator of [BCGI18]. -M -party OT / Beaver triple: From group-based or lattice-based HSS, leveraging our 2-party PCGs from the previous sections.

Interestingly, the lightweight 2-party OT PCG from Section 5 does not seem to support programmability in the necessary manner, since the resulting sender message pairs are implicitly defined as a function of the receiver's bit selections.

We begin by defining the class of bilinear correlations, and the PGC programmability property to which our transformation applies.

Definition 37 (Simple Bilinear Correlation: 2-party). A 2-party correlation C is a simple bilinear relation if there exists Abelian groups G 1 , G 2 , G T and a bilinear map e :

G 1 × G 2 → G T for which C is a distribution over (G 1 , G T ) × (G 2 × G T ) of the form C = {((a, c), (b, d)) | a ← G 1 , b ← G 2 , c ← G T , d = e(a, b) + c} .
Note that the groups G and map e are implicitly parametrized by λ.

C M = (a i , b i , c i ) i∈[M ] a i $ ← G 1 , b i $ ← G 2 ∀i ∈ [M ], c i $ ← G T ∀i ∈ [M -1], c M = e M i=1 a i , M i=1 b i -M -1 i=1 c i Example 39.
Useful specific examples:

-C M -VOLE : Each party holds random (u i , x i , v i ) ∈ F n × F × F n s.t. ( x i ) ( u i ) = ( v i ) -C M -OLE : Each party holds random (u i , v i , w i ) ∈ F n × F n × F n s.t. ( u i ) * ( v i ) = ( w i ) (componentwise)
We consider 2-party PCGs that support the following notion of programmability: loosely, that allow a party to "reuse" a piece of his input (either a ∈ G 1 or b ∈ G 2 ) in multiple instances of the 2-party correlation, while maintaining security.

Definition 40 (Programmability). We will say that a PCG PCG = (PCG.Gen, PCG.Expand) for simple bilinear 2-party correlation C 2 (specified by e : G 1 × G 2 → G T ) support reusable inputs if PCG.Gen(1 λ ) takes additional random inputs a , b ∈ {0, 1} such that:

-Programmability. There exist public efficiently computable functions f a , f b for which

Pr   a , b ← $, (k 0 , k 1 ) $ ← PCG.Gen(1 λ , a , b ) (a, c) ← PCG.Expand(0, k 0 ), (b, d) ← PCG.Expand(1, k 1 ) : a = f a (a ) b = f b (b )   ≥ 1 -negl(λ).
-Security. The distributions In Appendix G, we present and analyze the following general transformation from any programmable 2-party PCG for a simple bilinear correlation to a M -party PCG for the corresponding multi-party correlation.

(k 1 , b , f a (a )) (a , b ) ← $ (k 0 , k 1 ) $ ← PCG.Gen(1 λ , a , b ) and (k 1 , b , f a (ã)) (a , b ) ← $, ã ← $ (k 0 , k 1 ) $ ← PCG.Gen(1 λ ,
Theorem 41 (Multi-party Simple Bilinear PCG). Let PCG 2 = (PCG 2 .Gen, PCG 2 .Expand) be a programmable PCG for simple bilinear 2-party correlation C 2 (specified by e : G 1 ×G 2 → G T ) with key sizes s 0 (λ), s 1 (λ). Then there exists a PCG PCG M = (PCG M .Gen, PCG M .Expand) for the corresponding M -party correlation C M with the following properties.

-PCG M .Gen(1 λ ) runs M (M -1) executions of PCG 2 .Gen; each output key k i , i ∈ [M ], has size (M -1)(s 0 (λ) + s 1 (λ) + λ) bits. -PCG M .Expand(i, k i ) runs 2(M -1) executions of PCG 2 .Expand and makes (M -1) evaluations of a pseudorandom generator.

λ executions of a length-m OT protocol (λ is a security parameter): that is, the receiver with selection bits b = (b i ) i≤m plays the role of the sender with inputs (x j , x j + b) j≤λ , where x j is a random string of length m, and the sender plays the role of the receiver with a random selection vector s of length λ. This allows the sender to reconstruct k i = x i + b i s, where x i is the length-λ vector of the i-th coordinates of the vectors x j . Then, to execute an OT protocol with length -inputs (s 0 i , s 1 i ) from the sender and b i from the verifier, the sender sends

(z 0 i , z 1 i ) = (s 0 i ⊕ H(k i ), s 1 i ⊕ H(k i -s))
. Note that the verifier knows

x i = k i -b i s, hence he can reconstruct s b i i = z b i i ⊕ H(x i )
; sender security follows from the correlation-robustness of the hash function.

In [AHI11], it was observed that a similar construction can be obtained by replacing the correlation-robust hash function by an encryption scheme semantically secure against related-key attack for the class of linear functions under general group. An RKA-secure scheme maintains it's semantic security even if the keys satisfy a known (in fact, adaptively chosen by the adversary) relation. In the above construction, the sender can send

(z 0 i , z 1 i ) = (Enc(s 0 i , k i ), Enc(s 1 i , k i -s))
, where Enc is semantically secure against RKA attacks for linear functions: the sender security reduces to the hardness of distinguishing Enc(s

1-b i i , k i -(1 -b i )s) = Enc(s 1-b i i , x i + (-1) b i s)
from Enc(0 , x i + (-1) b i s), even given the keys x i for each i, which follows from the semantic security of Enc against RKA attacks. Furthermore, [AHI11] provides in particular a construction of an encryption scheme semantically secure against RKA-attacks for linear functions, from the standard LPN assumption over F 2 . Plugging their scheme as a replacement for the correlationrobust hash function in our construction of preprocessing NIZK from silent OT, we obtain a reusable preprocessing NIZK solely under the standard LPN assumption.

Theorem 42. Under the standard LPN assumption over F 2 , with dimension n, number of samples poly(n), and slightly sub-constant noise rate 1/ω(λ log n), there exists a reusable preprocessing NIZK proof system for NP which satisfies adaptive multi-theorem zero-knowledge and adaptive reusable soundness, where the communication and the computation of the preprocessing phase depend solely on the soundness error of the proof system, but are independent of the size and number of statements to be proven.

We note that the flavor of LPN used in our construction is a "minicrypt-style" assumption: it belongs to a parameter regime which is not known to imply the existence of public key encryption (which is only known from LPN with smaller noise rate O(1/ √ n)). Furthermore, the exact flavor of LPN that we need is in fact slightly weaker than the one given in the theorem above. Our NIZK can be based on the assumption that the following two variants of LPN are secure:

-LPN over F 2 with dimension n, very small number of samples n + o(n), and slightly subconstant noise rate 1/ω(λ log n) (this assumption underlies our silent OT extension), and -LPN over F 2 with dimension n, polynomial number of samples poly(n), and constant noise rate O(1) (this assumption underlies the RKA-secure symmetric-key encryption scheme of [AHI11]).

A.1.3 Replacing 1-out-of-2 OT with Rabin OT

While the construction described above relies on 1-out-of-2 oblivious transfer, it is also possible to build preprocessing NIZKs directly from the original Rabin OT primitive (where the sender has a single input, and the receiver learns it with probability 1/2) [GIK + 15]. We note that our silent OT extension can also be used to generate Rabin-type OT correlations, with a factor 2 of savings compared to the 1-out-of-2 silent OT extension protocol.

A.2 Efficiency Analysis

To improve the efficiency, we modify the construction to use the regular version of the syndrome decoding (or dual-LPN) problem, where the error vector e is divided into t equally-spaced blocks, each of weight one. This means the MPFSS scheme can be built by concatenating t DPFs of size n /t, instead of XORing t DPFs of size n .

In Tables 3 and4, we present the communication complexity and estimated runtimes of our Silent OT extension protocol for various choices of parameters. We chose our parameters as in [BCGI18], so that the best known attacks against the regular syndrome decoding problem cost at least 2 80 operations. We always use n = 4n, and values of the noise-weight t as shown in the table. We estimated runtimes based on the costs of the main operations in the Doernershelat [Ds17] protocol for running a distributed DPF setup with semi-honest security, and our own estimates for the cost of matrix multiplication. These are based on a single core of an i7-7600 CPU @2.8GHz with SSE and AES-NI instructions.

Communication complexity. When using the DPF setup protocol of [Ds17], for a single DPF of size N we need log N OTs15 on λ-bit strings, except the last OT which has length 2λ. With the regular LPN variant, we use t DPFs of size N = n /t, with n = 4n. Using OT extension, an OT on -bit strings requires λ + 2 bits of communication [ALSZ13], giving a total of t(log(n /t) + 1)(2λ + 1) bits of communication for these. The base OTs for OT extension can be implemented with the Naor-Pinkas protocol [NP01] based on DDH over a 256-bit elliptic curve group, at a cost of sending 1024 bits per OT.

This gives rough overall costs as follows, shown in detail in Table 3.

(log(N ) -1) • 3λ + 5λ = 3λ • log(N ) + 2λ -Seed size: ≈ t • (λ • log(n /t) + 2λ) bits -Base OTs (one-time cost): 1024 • λ bits -Distributed setup: ≈ 2 • λ • t • (log(n /t) + 1) bits
Encoding method. It seems likely that when n is large the dominating cost is the F n 2 λ × F n ×n 2 matrix multiplication. We consider two different encoding methods, both suggested in [BCGI18].

-Quasi-cyclic codes. H is the parity-check matrix of a random quasi-cyclic code. Multiplication by H can be computed as a length n /n inner product over Z 2 [X]/(X n -1), for which we estimate costs using a state-of-the-art implementation of fast binary polynomial multiplication [CCK + 18]. Security reduces to the quasi-cyclic syndrome decoding problem; note that this requires n to be prime to avoid attacks expoiting the quasi-cyclic structure [LJKS + 16]. -LDPC codes. H is the transpose of the generator matrix for an LDPC (low-density parity check) code, which is defined by a random parity check matrix with constant sparsity d. This implies that we need LPN to be hard for d-local codes, which is the same assumption that was conjectured in [Ale03]. We use d = 10, as suggested in [ADI + 17]. Multiplication by H is essentially the transpose of an LDPC encoding, which can be done in O(n) operations by "transposing" a linear-time LDPC encoding algorithm.

We have not implemented the LDPC encoding algorithm, but instead tested a dummy algorithm which performs the same operation count, with a worst-case access pattern where each operation reads from a random component of the input. As can be seen in Table 4, this becomes much slower beyond inputs of size 2 20 bits, which no longer fit in the L1 cache (128KiB). However, we expect that carefully implementing the algorithm could lead to performance improvements.

Other costs. The other costs involved are a DPF full-domain evaluation, and the cost of distributed setup for the DPFs. We ignore the cost of the OTs in the DPF setup procedure, since for our parameters we always need under 1000 OTs, which take under 1ms using modern OT extension implementations. To simplify estimates, we therefore assume the DPF cost in setup is the same as one full-domain evaluation, and estimate this using the implementation from [DRRT18], which reports a throughput of 2.6 billion bits/s for full-domain evaluation. Since our DPFs output 128 bits instead of one, we scale this down to get around 20 million evaluations per second.

← [n], then computes α = α 0 + α 1 , y i = T (s + i mod n) and γ i = y i • α in F 2 λ , for i ∈ [n],
viewing the outputs of T as elements of the field. It outputs

(R 0 , R 1 ) = (α σ , {y σ i , γ σ i } i∈[n] ) σ∈{0,1}
where y σ i ∈ {0, 1} m , γ σ i ∈ F 2 λ are sampled at random such that y 0 i + y 1 i = y i and γ 0 i + γ 1 i = γ i . Our starting point is the observation from [KOR + 17] that this correlation can be generated locally, given secret-shares of a random unit vector. This is because, if s ∈ [n] is the random mask, and e s ∈ {0, 1} n is the s-th unit vector, then we have

T (i + s mod n) = n j=1 e s [j] • T (i + j mod n)
and this can be computed locally given additive shares of e s , since T is public.

Given a DPF for the function with domain [n] that maps s to 1 and is zero elsewhere, two parties can compute shares of e s by simply evaluating the DPF on every input in [n]. This already allows us to compress a simple, semi-honest version of C TT without MACs. We can extend this to also create the secret-shared MACs at no extra cost, just by choosing the DPF to map s to (1 α), where α is a random MAC key. We remark that, as described in Section 2, this can be seen as an instance of the DPF-based HSS scheme that is implicit in our subfield-VOLE PCG.

The complete construction is given in Fig. 6. Instantiating DPF with [BGI16b], the total PCG seed size is log n • (λ + 2) + 3λ + 1 bits, and note that this is independent of the precise lookup table, or even the length of its values. Compared with the cost of naively storing a 1-bit output one-time truth table with MACs of n • (λ + 1) + λ bits from [DNNR17], we obtain storage savings of over 20x for a length-256 table (as in the AES S-box), and this increases to almost 80x for a table of size 1024. The computational cost of expanding the entire correlation is n calls to DPF.FullEval, however, when using this for 2-PC only a single entry of the table is needed, and this can be computed on-the-fly with just 1 call to FullEval, for a cost of O(n) PRG evaluations.

Construction G TT

Parameters: A lookup table T : [n] → {0, 1} m , and a distributed point function DPF = (DPF.Gen, DPF.FullEval).

Gen: On input 1 λ : 1. Pick a random index s $ ← {1, . . . , n}. 2. Sample α0, α1 $ ← F 2 λ and let α = α0 ⊕ α1. 3. Compute (K fss 0 , K fss 1 ) $ ← DPF.Gen(1 λ , f s,1 α ). 4. Let k0 ← (K fss 0 , α0
) and k1 ← (K fss 1 , α1).

Output (k0, k1).

Expand: On input (σ, kσ):

1. Parse kσ as (K fss σ , ασ). 2. Compute v σ ← DPF.FullEval(σ, K fss σ ) in {0, 1} n•(λ+1) . 3. For each i ∈ [n], write v σ i = (b σ i c σ i ) ∈ {0, 1} × F 2 λ .
Compute, for j ∈ [n]:

y σ j = n i=1 b σ i • T (i + j mod n) ∈ {0, 1} m , γ σ j = n i=1 c σ i • T (i + j mod n) ∈ F 2 λ
and output (ασ, {y σ j , γ σ j } n j=1 ).

Fig. 6. PCG for authenticated, one-time truth table correlations

The following theorem can be proven with a reduction to MPFSS, similarly to (and simpler than) the proof of Theorem 24 for the subfield-VOLE generator.

Theorem 43. Let DPF be a secure distributed point function. Then construction G TT in Fig. 6 is a secure PCG for the correlation G TT .

B.1 Application to Sublinear-Communication MPC in the Preprocessing Model

Secure computation in the correlated randomness model typically requires communicating O(s) values in the online phase, where s is the circuit size. In a recent paper, Couteau [Cou19] showed that this is not inherent: given access to a trusted source of (polynomially many) large one-time truth tables correlations, N parties can securely evaluate arbitrary layered (boolean or arithmetic) circuits (whose nodes can be partitioned into layers such that any edge connects adjacent layers -such circuits capture a variety of circuits that arise in practice) with informationtheoretic security and sublinear communication O(s/ log log s). A downside of this protocol, that strongly limits its partical implications, is that it requires a large amount of preprocessing material: to securely evaluate the circuit in the online phase, the parties need to generate and store O(s 2 log log s) bits of preprocessed material (i.e., O(s/ log log s) one-time truth tables of size O(s) each). Using our PCG for truth table correlations, this can be compressed to a quasilinear amount O(λs log s/ log log s) of preprocessing material, assuming only one-way functions. The preprocessing material can then be locally expanded by the parties, without any interaction, into O(s 2 log log s) bits of (pseudo)random one-time truth tables.

C Group-Based PCG for Bilinear Correlations

In this section, we exhibit a construction of PCG from the (external) DDH assumption over pairing-friendly elliptic curves, for the class of (additive) bilinear correlations. This construction builds upon the group-based HSS developed in [BGI16a, BGI17, BCG + 17]. Note that all these constructions satisfy an imperfect correctness notion, where correctness is only guaranteed to hold except with probability δ, and the evaluation algorithm is allowed to run in time polynomial in 1/δ (it is called a "Las Vegas" HSS in [BGI16a, BGI17, BCG + 17]). Our construction of groupbased PCG will inherit this imperfect correctness. However, the parties can detect when a given output has a high risk of being incorrect; knowing the location of the faulty outputs allows them to use efficient techniques (such as punctured OT [BGI17] or leakage-absorbing pads [BCG + 17]) to securely delete them in a sanitization phase. Hence, we denote PCG with imperfect correctness and detectable failures sanitizable pseudorandom correlation generators.

Our full construction is somewhat technical. Because of the inverse polynomial failure probability, our group-based PCG does not directly fit into the definition of PCG given in Section 4. To simplify the presentation, we therefore first introduce the notion of sanitizable bilinear correlation generators, which are PCG for the class of bilinear correlations with an inverse polynomial failure probability whose incorrect outputs can be detected efficiently. Then, to proceed with the construction, we introduce an intermediate notion: the notion of compressible HSS. Informally, a compressible HSS is an HSS schemes in which the encodings of the inputs can be compressed to a small string when they come from an appropriate distribution. This captures the fact that our construction will build upon the specific homomorphic properties of the group-based HSS of [BGI16a, BGI17, BCG + 17] to show that the encodings of (pseudo)random inputs can be efficiently compressed. Then, we show that a compressible Las Vegas degree-2 HSS for bilinear correlations can be used to construct a sanitizable bilinear correlation generator, assuming the learning parity with noise (LPN) assumption. Afterward, we proceed with a description of a compressible Las Vegas degree-2 HSS for bilinear correlations, which builds upon the homomorphic properties of the group-based Las Vegas HSS of [BGI16a, BGI17, BCG + 17] when instantiated over a pairing-friendly elliptic curves, and upon the VOLE generator of [BCGI18]. Eventually, we discuss optimizations of our construction. Notations. For vectors x i over a multiplicative group, we denote by i x i their component-wise product. Given a multiplicative group G of order q, a length-n vector g = (g 1 , • • • , g n ) ∈ G n , and a length-n vector of exponents

x = (x 1 , • • • , x n ) ∈ Z n q , we denote x • g the "scalar product in the exponent": x • g = n i=1 g x i i ; for any g ∈ G, g x denotes (g x 1 , • • • , g xn ).
A Note on Additive Bilinear Correlations. The general notion of additive correlations which we consider in this paper are those in which the parties receive shares of some input x, as well as shares of C(x) for some correlation C. However, when restricting our attention to bilinear correlations, it is more convenient to consider that each party will know in the clear one of two inputs, x and y, as well as shares of a bilinear function B(x, y). Indeed, letting the parties know part of the output in the clear will allow for several non-trivial optimizations of the construction. Furthermore, in the specific case of bilinear correlation, it turns out that this is without loss of generality: the general case (where the inputs are shared as well) can be obtained in a blackbox way using two parallel calls to the PCG for these restricted forms of bilinear correlations. We demonstrate this with the construction below, where BCG s denotes a pseudorandom correlation generator for general bilinear correlations, and BCG denotes a PCG for restricted bilinear correlations.

-BCG s .Setup(1 λ ) outputs (pp, sk) $ ← BCG.Setup(1 λ ); -BCG s .Gen(sk, B) runs twice BCG.Gen(sk, B), and outputs ((k 0 , k 0 ), (k 1 , k 1 )); -BCG s .Expand(pp, σ, (k σ , k σ )) runs twice BCG.Expand, and outputs

z σ = ((1-σ)x σ +σx σ , σx σ + (1 -σ)x σ , y σ + y σ + B(x σ , x σ )).
Then, it holds that

z 0 + z 1 = (x 0 + x 1 , x 0 + x 1 , B(x 0 , x 1 ) + B(x 0 , x 1 ) + B(x 0 , x 0 ) + B(x 1 , x 1 )) = (x 0 + x 1 , x 0 + x 1 , B(x 0 + x 1 , x 0 + x 1 )) = (x, x , B(x, x )), denoting x = x 0 + x 1 , x = x 0 + x 1 .

C.1 Sanitizable Bilinear Correlation Generator

Since our group-based construction will be inherently limited to generating bilinear correlations, with an inverse polynomial failure probability, we provide a self-contained formal definition of sanitizable bilinear correlation generators. A sanitizable BCG is a PCG for bilinear correlations, where correctness holds except with some inverse polynomial probability. To capture the fact that in our construction, a part of the seed generation can be reused accross several instantiations, we add to the definition a Setup algorithm, which produces the reusable part of the seed (which contains public and secret parameters).

Definition 44 (Sanitizable Bilinear Correlation Generator). A (δ-failure) sanitizable bilinear correlation generator over a ring R is a triple of algorithms (BCG.Setup, BCG.Gen, BCG.Expand) with the following syntax:

-BCG.Setup(1 λ ) is a PPT algorithm that given a security parameter λ, outputs public parameters pp and a secret key sk; -BCG.Gen(sk, B) is a PPT algorithm that given secret key sk and a bilinear map B : R n × R n → R m , outputs a pair of seeds (k 0 , k 1 ); -BCG.Expand(pp, σ, k σ , δ) is an algorithm running in time polynomial in λ and 1/δ that, given party index σ ∈ {0, 1}, a seed k σ , and a failure bound δ, outputs a pair of vectors (x, y) ∈ R n × R m , as well as a list of m confidence flags γ σ,i ∈ {⊥, } for i = 1 to m to indicate full confidence ( ) or a possibility of failure (⊥) for any given output.

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

δ-Correctness. For every i ≤ m and every polynomial p, there is a negligible ν such that for every positive integer λ, bilinear function B : R n × R n → R m , and failure bound δ > 0, where |B|, 1/δ ≤ p(λ), we have:

Pr[(γ 0,i = ⊥) ∧ (γ 1,i = ⊥)] ≤ δ + ν(λ),
and

Pr[((γ 0,i = ) ∨ (γ 1,i = )) ∧ y 0,i + y 1,i = B(x 0 , x 1 ) i ] ≤ ν(λ),
where the probability is taken over

(pp, sk) $ ← BCG.Setup(1 λ ), (k 0 , k 1 ) $ ← BCG.Gen(sk, B)
and where we denote (x 0 , y 0 ) ← BCG.Expand(0, k 0 ), and (x 1 , y 1 ) ← BCG.Expand(1, k 1 ).

-Security. For any σ ∈ {0, 1} and any (stateful, nonuniform) polynomial-time adversary A, it holds that

Pr    (pp, sk) $ ← BCG.Setup(1 λ ), B ← A(pp), (k 0 , k 1 ) $ ← BCG.Gen(sk, B), (x σ , y σ , γ σ ) ← BCG.Expand(pp, σ, k σ ) : A(x σ , k 1-σ ) = 1    ≈ Pr    (pp, sk) $ ← BCG.Setup(1 λ ), B ← A(pp), (k 0 , k 1 ) $ ← BCG.Gen(sk, B), x σ $ ← R n , γ σ $ ← Ber δ ({⊥, }) m : A(x σ , k 1-σ ) = 1    .

C.2 Las Vegas HSS

We recall below the definition of δ-failure HSS (with a Las Vegas correctness guarantee), adapted from [BCG + 17].

Definition 45 (Las Vegas Homomorphic Secret Sharing). A (2-party, secret-key, Las Vegas δ-failure) Degree-d Homomorphic Secret Sharing (HSS) scheme over a ring (R, +, •) is a triple of PPT algorithms HSS = (HSS.Gen, HSS.Share, HSS.Eval) with the following syntax:

-HSS.Gen(1 λ ): On input a security parameter 1 λ , the key generation algorithm outputs a secret key sk and an evaluation key ek. -HSS.Share(sk, x): Given secret key sk and secret input value x ∈ R n , the sharing algorithm outputs a pair of shares (s 0 , s 1 ). We assume that the input length n is included in each of (s 0 , s 1 ). -HSS.Eval(σ, ek, s b , P, δ): On input party index σ ∈ {0, 1}, evaluation key ek σ , share s σ of a size-n input, degree-d arithmetic circuit P with n input bits and m output bits, and a failure bound δ, the homomorphic evaluation algorithm outputs y b ∈ R m , constituting party b's share over R of an output y ∈ R m , as well as a confidence flag γ b ∈ {⊥, } to indicate full confidence ( ) or a possibility of failure (⊥).

The algorithms (HSS.Gen, HSS.Share, HSS.Eval) should satisfy the following correctness and security requirements:

-Correctness: For every polynomial p there is a negligible ν such that for every sufficiently large integer λ, input x ∈ R n , degree-d arithmetic circuit P with input length n, and failure bound δ > 0, where |P |, 1/δ ≤ p(λ), we have:

Pr[(γ 0 = ⊥) ∧ (γ 1 = ⊥)] ≤ δ + ν(λ),
and

Pr[((γ 0 = ) ∨ (γ 1 = )) ∧ y 0 + y 1 = P (x)] ≤ ν(λ),
where probability is taken over (sk, ek) ← HSS.Gen(1 λ ); (s 0 , s 1 ) ← HSS.Share(sk, x);

(y σ , γ σ ) ← HSS.Eval(σ, ek, s σ , P, δ), σ ∈ {0, 1}.

-Security: For any σ ∈ {0, 1}, any pair of inputs x, x of the same length, the distribution ensembles C σ (λ, x) and C σ (λ, x ) are computationally indistinguishable, where C σ (λ, y) for y ∈ {x, x } is obtained by sampling (sk, ek) ← HSS.Gen(1 λ ), sampling (s 0 , s 1 ) ← HSS.Enc(sk, y), and outputting (ek, s σ ).

C.3 (D, comp)-Compressible HSS

In this section, we introduce a variant of homomorphic secret sharing, called compressible HSS for a family of distributions D (CHSS). Intuitively, a CHSS allows to share inputs sampled from a distribution D n , and guarantees that the size of each share is upper-bounded by comp(λ, n), where comp is called the compression ratio of the CHSS.

Definition 46 ((D, comp)-Compressible HSS). A (2-party, secret-key, degree-d) compressible homomorphic secret sharing over a ring R for a family of distributions

D(R) = {D n (R)} n∈N (such that Im(D n (R)) ⊆ R n
) with compression ratio comp, or (D(R), comp)-CHSS, is a (2-party, secret-key, degree-d) homomorphic secret sharing over R whose correctness is relaxed as follows:

-Relaxed Correctness. For every sufficiently large positive integers λ, n and degree-d arithmetic circuit P with input length n, we have:

Pr[y 0 + y 1 = P (x)] ≤ negl(λ),
where probability is taken over

(sk, ek) ← HSS.Gen(1 λ ); x ← D(R) n ; (s 0 , s 1 ) $ ← HSS.Share(sk, x); y b ← HSS.Eval(b, ek, s b , P ), b ∈ {0, 1},
and which satisfies an additional compressibility property:

-Compressibility. A (D, comp)-CHSS is compressible with compression ratio comp if for every sufficiently large integers λ, n, every input x ∈ Im(D n ), every (sk, ek) in the image of HSS.Gen(1 λ ), and every (s 0 , s 1 ) in the image of HSS.Share(sk, x), it holds that |s σ | ≤ comp(λ, n) for σ = 0, 1.

C.4 BCG from LPN and Degree-2 CHSS

Let R be a ring. Let D(R) = {D(R) n } n∈N be a family of efficiently sampleable distributions over R n . Let comp be a compression ratio. Let HSS = (HSS.Gen, HSS.Share, HSS.Eval) be a (2-party secret-key) degree-2 (D(R) × D(R), comp)-CHSS. We describe below a construction of a bilinear correlation generator over R. Note that any bilinear function B : R n × R n → R m can be fully described by a list of m matrices

B 1 • • • B m with B i ∈ R n×n such that for any inputs (x, x ) ∈ R n × R n , B(x, x ) = (x B i x ) i≤m .
Let α be a positive constant.

-BCG.Setup(1 λ ) : output (pp = ek, sk)

$ ← HSS.Gen(1 λ ). -BCG.Gen(sk, B) : let n denote the input size of B and let ← αn. Let M ← C( , -n, R)
be the encoding matrix of a linear code, and let N ∈ R n× denote its parity check matrix (i.e., N is the matrix over R n× which satisfies N M = 0). Pick two vectors (z 0 , z 1 ) ← D (R) × D (R) and let r 0 (resp. r 1 ) denote the random coin used to sample z 0 (resp. z 1 ). Run (s 0 , s 1 ) ← HSS.Share(sk, (z 0 , z 1 )). Output k σ ← (r σ , s σ ) for σ = 0, 1. -BCG.Expand(pp, σ, k σ ) : parse k σ as (r σ , s σ ) and reconstruct z σ from r σ (using the sampling procedure of D n (R)). Define the bilinear function P : R × R → R m as follows: on input

(x, x ) ∈ R × R , P outputs (x • B i • x ) i≤m , where B i is defined as B i ← N B i N . Set x σ ← N z σ .
Compute y σ ← HSS.Eval(σ, pp, s σ , P ), and output (x σ , y σ ).

Theorem 47. Assuming the (D(R), C)-LPN( , -n) assumption, the above construction is a bilinear correlation generator with seed size upper-bounded by 2 • comp(λ, ).

failure probability for the entire vector output, and outputs a single flag in { , ⊥} to indicate correctness of the output, while our definition of sanitizable BCG requires outputting a different flag for each output (with the goal of later removing faulty outputs while keeping correct ones). This is essentially a syntactic difference: existing construction of Las Vegas HSS can easily be modified to output a flag for each output bit. In the formal construction of sanitizable BCG from Las Vegas HSS, it suffices to apply the Las Vegas HSS independently for each functions f i outputting the ith bit of the target bilinear correlation, to get independent failure flags for each output bit.

C.6 Group-Based HSS for Bilinear Functions

In this section, we provide an overview of the group-based homomorphic secret sharing scheme first introduced in [BGI16a], and subsequently optimized in [BGI17, BCG + 17, DKK18]. When restricted to bilinear functions, as observed in [BCG + 17, Section 4.6], the scheme can be considerably simplified and optimized. Below, we briefly recall the HSS scheme of [BGI16a], taking into account the optimizations for bilinear functions of [BCG + 17]. The scheme allows to compute bilinear functions over any ring Z t of polynomial size; it relies on a group G where the discrete log is conjectured to be hard.

C.6.1 Encoding Z q Elements.

Let q be a large prime, and let G be a hard-discrete-log group of order q. Let g denote a generator of G. For any x ∈ Z q , we consider the following 3 types of two-party encodings:

Level 1: "Encryption." For x ∈ Z q , we let [x] denote g x , and

x s denote ([r] , [r • s + x]
) for a uniformly random r ∈ Z q , which corresponds to an ElGamal encryption of x with a secret key s ∈ Z q . All level-1 encodings are known to both parties. We let sk ← (s, -1).

Level 2: "Additive shares." Let x denote a pair of shares x 0 , x 1 ∈ Z q such that x 0 = x 1 + x, where each share is held by a different party. We let ⟪x⟫ s denote ( -s • x , x ) = sk• x ∈ (Z 2 q ) 2 , namely each party holds one share of -s • x and one share of x . Note that both types of encodings are additively homomorphic over Z q , namely given encodings of x and x the parties can locally compute a valid encoding of x + x .

Level 3: "Multiplicative shares." Let {x} denote a pair of shares x 0 , x 1 ∈ G such that the difference between their discrete logarithms is x. That is,

x 0 = x 1 • g x .

C.6.2 Operations on Encodings.

All types of encodings allow to locally evaluate linear functions (they are additively homomorphic). To evaluate degree-2 polynomials, we define a multiplication algorithm Mult which, given a level 1 encoding of an inpuy x and a level 2 encoding of an input y, outputs additive shares of xy. To this end, we consider the following two types of operations, performed locally by the two parties:

1. Pair( x s , ⟪y⟫ s ) → {xy}. This pairing operation exploits the fact that the decryption of an ElGamal ciphertext x s is computed as a scalar product in the exponent:

g x = sk • x s . Therefore, Pair computes ⟪y⟫ s • x s = y •(sk• x s ) = {xy}.
Note that we consider ElGamal ciphertexts for the sake of concreteness only; any encryption scheme whose decryption follows a similar "scalar product in the exponent" structure would suffice. 2. Convert({z} , δ) → z , with failure bound δ. The implementation of Convert is also given an upper bound M on the "payload" z (M = 1 by default), and its expected running time grows linearly with M/δ. We omit M from the following notation.

Let BilinearGen denote a PPT algorithm which, on input 1 λ , outputs a prime q, the description of three cyclic groups (G 1 , G 2 , G t ), elements (g 1 , g 2 ) ∈ G 1 × G 2 , and a map e such that the cyclic groups have the same order q = q(λ); the map e : G 1 × G 2 → G t is an efficiently computable non-degenerate bilinear map, i.e., ∀(u, v) ∈ G 1 × G 2 and (a, b) ∈ Z p , e(u a , v b ) = e(u, v) ab ; g i generates G i for i ∈ {1, 2} (and g t ← e(g 1 , g 2 ) generates G t ).

Note that this captures groups equipped with an asymmetric pairing. To simplify notations, given vectors x ∈ G n 1 , y ∈ G n 2 , we will write e(x, y) to denote (e(x i , y j )) i,j≤n . When it happens that the components of the vector are vectors themselves (e.g. if x, y are vectors of ciphertexts, each ciphertext consisting of several group elements), we apply the notation recursively: e(x, y) = (e(x i , y j )) i,j≤n and for every i, j, e(x i , y j ) = (e(x i,i , y j,j )) i ,j .

We outline below our simplified variant of Freeman's adaptation of the BGN cryptosystem, which we denote BGN-EG.

-BGN-EG.Setup(1 λ ) :

output pp = (q, G 1 , G 2 , G t , g 1 , g 2 , e) $ ← BilinearGen(1 λ ). -BGN-EG.KeyGen(pp) : pick (s 1 , s 2 ) $ ← Z 2 q , compute (h 1 , h 2 ) ← (g s 1 1 , g s 2 2 ). Set sk i ← (s i , -1) for i = 1, 2, and sk t = (s 1 • s 2 , -s 1 , -s 2 , 1). Output pk ← (pp, h 1 , h 2 ) and sk ← (sk 1 , sk 2 , sk t ).
-BGN-EG.Enc i (pk, m; r) : on input the public key pk, a message m ∈ Z q , and a random coin r ∈ Z q , output c i ← (g r i , h r i g m i ) (this corresponds to encryption over G i ).

-BGN-EG.Dec i (sk, c i ): on input the secret key sk and a ciphertext c i , compute c ← sk i • c i and output m ← dlog g i (c).

Correctness follows by inspection; security reduces to the decisional Diffie-Hellman assumption (DDH) in G 1 and G 2 . It is easy to see that the scheme is additively homomorphic over each of G 1 and G 2 . Furthermore, given an encryption c 1 of a message m 1 over G 1 and an encryption c 2 of a message m 2 over G 2 , one can homomorphically construct an encryption of m 1 m 2 over G t as follows: compute c t ← e(c 1 , c 2 ). The resulting ciphertext has four components and remains additively homomorphic over G t (addition of plaintext is computed by component-wise multiplication). Decryption of a ciphertext over G t is performed by computing c ← sk t • c t , and outputting m ← dlog gt (c), where g t = e(g 1 , g 2 ).

C.8 Compressible HSS from BGN-EG

We now show how the group-based HSS of [BGI16a, BGI17, BCG + 17] can be modified to get a compressible HSS. In this section, we will consider compressible HSS over a small (polynomialsize) ring Z t for inputs drawn from the Bernouilli distribution Ber r (Z t ) for some rate r (see Section 3.3); that is, we will consider inputs with a sparse structure, and show how level 1 and level 2 encodings of such inputs can be compressed. Let (G 1 , G 2 , G t ) denote three cyclic groups of order q, and let e : G 1 × G 2 → G t denote a pairing. Observe that the ciphertexts in the target group G t of BGN-EG have a suitable structure to be used as level-1 encodings in the HSS scheme, as decryption of a ciphertext over G t is performed via a scalar product in the exponent.

C.8.1 Modifying the DDH-Based HSS.

We modify the HSS scheme of the previous section as follows: a level 1 encoding x sk of x is a BGN-EG encryption of x in the target group G t . A level 2 encoding ⟪y⟫ sk of a message y is a 4-tuple sk t • y . The Pair algorithm, on input a level 1 encoding x sk and level 2 shares ⟪y⟫ sk , outputs ⟪y⟫ sk • x sk ; a level 3 encoding of a message z is a multiplicative share over G t of g z t ; it follows that Pair( x sk , ⟪y⟫ sk ) = {xy}. Then, the parties can apply the optimized Convert procedure of [DKK18] to obtain additive shares of xy. The security of this modified HSS scheme immediatly reduces to the DDH assumption in G 1 and G 2 , by the same security analysis as for the HSS of [BGI16a] (note that, because we restrict our attention to HSS for bilinear function, we do not need to use circularly-secure variants of ElGamal to get security under DDH; a circularly-secure scheme is needed in [BGI16a] because encryptions of the secret key must be released to allow for the evaluation of more complex functions).

C.8.2 Compressing Level 1 Encodings under BGN-EG.

The modified scheme suggests a natural strategy to reduce the size of level 1 encodings when the input is sparse, by exploiting the homomorphic properties of BGN-EG ciphertexts. Let m be a length-vector over Z q , which has at most k non-zero coordinates. We assume to be a square for simplicity. The compression method works as follows: arrange the coordinates of m in a √ × √ matrix M . Decompose M into k i=1 M i , where each matrix M i has a single non-zero coordinate.

For i = 1 to k, let (u i , v i ) ∈ [ √ ] × [ √ ] denote the coordinate of the non-zero entry of M i . Pick 2 √ elements (α i,j , β i,j ) j≤ √ of Z q as follows: for each pair (u, v) = (u i , v i ), set α i,u = β i,v = 0, and set α i,u i = 1, β i,v i = M i | u i ,v i . Observe that, by construction, it holds that M i | u,v = α i,u • β i,v for any pair (u, v) ∈ [ √ ] × [ √ ]
. Therefore, we have for any

(u, v) ∈ [ √ ] × [ √ ]: M | u,v = k i=1 α i,u • β i,v .
This shows that for any vector m with at most k non-zero entries, one can create a level 1 encoding of m as follows: compute the (α i,u , β i,u ) i≤k,u≤ √ as above, and set the encoding of m

to be k • √ BGN-EG encryptions of (α i,u ) i,u over G 1 , and k • √ BGN-EG encryptions of (β i,u ) i,u over G 2 . Using the homomorphic properties of BGN-EG, any party can then locally reconstruct a BGN-EG encryption of m = ( k i=1 α i,u • β i,v ) u,v over G t . The size of the compressed encoding is 2k • √ • (|G 1 | + |G 2 |).
Note that this strategy corresponds exactly to using the LPN-based PRG introduced in Section 4.4 to stretch the encoded seed.

C.8.3 Compressing Level 2 Encodings using FSS.

We now turn our attention to level 2 encodings ⟪m⟫ sk = (

s 1 s 2 • m , -s 1 • m , -s 2 • m , m ).
Note that if m is a sparse vector, so are s 1 s 2 • m, -s 1 • m, and -s 2 • m. We therefore focus on compressing additive shares of arbitrary sparse vectors over Z q . As was observed recently in [BCGI18], this type of correlation can be efficiently compressed using function secret sharing for multi-point functions (MPFSS). We elaborate below.

Let MPFSS = (MPFSS.Gen, MPFSS.Eval, MPFSS.FullEval) be a multi-point function secret sharing. On input a vector m ∈ Z q with HW (m) ≤ k, let proj m : [ ] → Z q be the function which, on input i ∈ [ ], outputs the i'th coordinate of m. Note that proj m is an ( , k)-multi-point function over Z q . To generate compressed additive shares of m, compute (K 0 , K 1 ) $ ← MPFSS.Gen(1 λ , proj m ). To decompress the string, each party with input K σ computes MPFSS.FullEval(σ, K σ ), obtaining additive shares of (proj m (i)) i∈[ ] = m. Correctness immediately follows from the correctness of the underlying MPFSS. Regarding security, we must show that for any pair (m, m ) (with HW (m) , HW (m ) ≤ k) and any σ ∈ {0, 1}, the distribution of (ek σ , s σ ) obtained by sampling (sk, (ek 0 , ek 1 )) ← HSS.Gen(1 λ ), sampling (s 0 , s 1 ) ← HSS.Enc(sk, m) or (s 0 , s 1 ) ← HSS.Enc(sk, m ), and outputting (ek σ , s σ ), are computationally indistinguishable. This immediately follows from the fact that, by the MPFSS security, there is a simulator which (given Leak(proj m ) = Leak(proj m ), and no further information about m, m ) can output a simulated key s σ = K σ whose distribution is indistinguishable from an honestly generated key.

Using the PRG-based MPFSS of [BGI16b,BCGI18], the size of a compressed encoding using this method is equal to k • ( log • (λ + 2) + λ + log q ). We refer the reader to [BCGI18] for further discussions on this method and optimizations of MPFSS tailored to this application.

D.1 General Optimizations

In the construction of BCG from CHSS of Section C.4, two vectors z 0 and z 1 are sampled and shared between the parties using HSS.Share, and each party gets to know one of these vectors. Using the group-based CHSS, this means that one party knows both z 0 and the level 1 encoding of z 0 . Therefore, we can trivially observe that revealing the random coins of this level 1 encoding to this party does not compromise the security of the BCG (as BGN-EG is only used to encrypt vectors that he knows in the clear anyway). Knowing the BGN-EG random coins of the level 1 encoding allows the party to perform the decompression procedure without computing pairings. To illustrate, consider the task of homomorphically multiplying two ciphertexts

(g r 1 1 , h r 1 1 g m 1 1 ) ∈ G 2 1 and (g r 2 2 , h r 2 2 g m 2 2 ) ∈ G 2 2 .
The party who knows (m 1 , r 1 , m 2 , r 2 ) can simply have precomputed e(g 1 , g 2 ), e(g 1 , h 2 ), e(h 1 , g 2 ), and e(h 1 , h 2 ) in a one-time setup phase, and obtain each term directly by computing exponentiations over G t (e.g., e(g r 1 1 , g r 2 2 ) is computed as e(g 1 , g 2 ) r 1 r 2 , using the precomputed e(g 1 , g 2 ) and the random coins r 1 , r 2 known in the clear). Therefore, for this party, the cost of decompressing a level 1 encoding (still counting all previous optimizations) is reduced from computing 4 pairings to computing 4 exponentiations over G t . Such exponentiations are typically up to an order of magnitude less costly than pairing computations.

It is relatively straightforward to share equally the benefits of this optimization between the two parties: instead of computing the BCG seeds as a (compressed) level 1 encoding of z 0 and a (compressed) level 2 encoding of z 1 , we break each vector z i in two equal length parts

(z 0 i , z 1 i ).
Then, the seed is now computed as level 1 encodings of both z 0 0 and z 1 1 , and level 2 encodings of both z 1 0 and z 0 1 , and each party P j (for j = 0, 1) receives the random coins of one of the two level 1 encodings of half-vectors, and can therefore apply the above optimization to this half-vector. This reduces the number of pairings computed by each party by a factor 2 (in exchange for computing exponentiations over G t ), which results in an improvement of almost a factor two. Note that in a scenario where the parties have very different computational power (e.g. a client and a server), it is better to use the asymmetric version, where the computationally weak devices computes only exponentiations instead of pairings.

We can further reduce the size of level 1 encodings by applying a heuristic PRG-based optimization which was described in [BGI16a]: the algorithm HSS.Share 1 picks a random PRG seed k for a PRG G, and parse G(k) as a sequence of √ group elements over G 1 and √ group elements over G 2 . Each group element is then interpreted as the first component of an ElGamal ciphertext. Given a plaintext m and a first component c, the second component of an encryption of m over G i is computed as c s i •g m i . HSS.Share 1 outputs k together with the list of all second components of ElGamal ciphertexts, which results overall in a factor 2 compression. Note, however, that this optimization cannot be directly cumulated with the previous optimization, as HSS.Share 1 cannot reveal the corresponding random coins to one of the parties.

However, there is another straightforward optimization which does not conflict the optimization based on revealing the random coins to a party: the coins and the plaintexts can be generated as the output of a PRG G on a short seed k, and the party who gets to learn the coins and the plaintexts can be given k instead of the list of all plaintexts and random coins, reducing the storage overhead for this party.

The security of our group-based BCG reduces to the standard LPN assumption, where the linear code is generated uniformly at random, and the noise is a random sparse vector. LPN has a long history in cryptography, and it is a common practice to consider variants of this basic assumption to improve the efficiency of LPN-based primitives (several variants of LPN are by now standard and well-established assumptions; a typical example is Alekhnovich's assumption [Ale03], which underlies his famous LPN-based cryptosystem). Two standard tweaks that can be applied to LPN are the following:

replacing the random linear code by a code with good properties (e.g. efficient encoding) to speed-up the computation of noisy codewords;

reconstructed from the homomorphic properties of BGN-EG by computing the tensor product a⊗b over G t . This amounts to a total of 2 √ n BGN-EG ciphertexts, improving over the method of the previous section by a factor of √ k. Note, in addition, that this alternative noise distribution also reduces the number of pairings to be computed by a comparable factor -as it turns out, in concrete efficiency estimations, the number of pairings is one of the main computational bottleneck. Therefore, this variants also strongly improves the computational efficiency of the BCG.

It remains to discuss the security of LPN with noise vectors drawn from this distribution. Unlike for standard Bernouilli noise, there are specific attacks which are known to apply as soon as the noise distribution satisfies a low-degree relation (in the present situation, the noise distribution satisfies a degree-2 relation). To our knowledge, the only attacks which specifically exploit low-degree relations in the noise distribution are those of Arora and Ge [AG10], which provide a polynomial-time algorithm solving LPN instances using N d samples, where d is the degree of the relation and N is the dimension. Since we consider much more limited number of samples (O(N )), this attack does not apply in our setting. However, the algebraic structure of the noise also implies that, unlike standard LPN, this assumption is sensitive to algebraic attacks (e.g. Gröbner basis attacks); therefore, we will take into account algebraic attacks in addition to standard attacks on LPN when estimating the concrete security level offered by this new assumption.

Relation to MQ and LPN. If the vector x had been sampled from the standard Bernouilli distribution, the above assumption would be exactly LPN. Furthermore, if the vecto x had been computed as the tensor product of a uniformly random (as opposed to sparse) vector a with itself, this assumption would exactly be the multivariate quadratic (MQ) assumption, a wellstudied assumption [MI88, Wol05, AHI + 17] that asserts that it is computationally infeasible to sove a random system of quadratic equations. Hence, the LPN with tensored noise assumption can be seen as a natural strengthening of both the MQ assumption and the LPN assumption.

Cryptanalysis. Since it shares both the algebraic structure of the MQ assumption, and the sparsity of the LPN assumption, the new assumption introduced above is sensitive to the standard cryptanalytic attacks that apply to each of these assumptions. We provide an overview of the existing attacks below.

-The most powerful attacks on LPN (in the setting of a limited number of samples and a low noise rate, which is the case here) are the Gaussian elimination attack (which attempts to guess a noise-free subset of the coordinates of the vector, and use Gaussian elimination to invert the corresponding system of equation), the low-weight parity-check attack [Zic17] (which uses the existence of low-weight codewords in the dual code to establish the existence of a distinguisher), and the information set decoding (ISD) attack (which uses variants of Prange's algorithm [Pra62] to solve the corresponding syndrom decoding problem). We refer the reader to [BCGI18] for a more detailed overview of these attacks, and bounds on their computational efficiency. We note that the structure of the noise pattern in our LPN variant leads to better alternative than the random choice to pick candidate noise-free coordinates of the vector; we will takes this observation into account when evaluating the cost of the above attacks. Furthermore, note that the low-weight parity-check attack only applies to LPN over exponentially large fields (see [Zic17]). Over F 2 , this attack provably fails. -The most powerful attacks on MQ are the algebraic attacks, such as Gröbner basis attacks.

These attacks exploit the algebraic structure of the system of quadratic equations to generate many new equations, until sufficient information was gathered to solve the system efficiently. We note that algebraic attacks such that XL and Gröbner basis attacks do not provide ways to take advantage of the sparsity of the noise pattern.

Note that we could have alternatively used noise vectors constructed as tensor product between vectors sampled from the uniform distribution, leading to an MQ-based construction.

However, bounding the number of nonzero coefficients (here, by k 2 ) is crucial for the efficiency of the Convert operation, which relies on an expensive "distributed discrete logarithm" where the parties must compute a number of multiplications over G t polynomial in the number of nonzero coefficients of the input vectors.

D.3 Changing the Code Matrix

In this section, we describe alternative choices of code matrices which lead to better computational efficiency for the Expand procedure.

D.3.1 Faster Expansion using LDPC Codes.

Constructing BCG from degree-2 CHSS essentially boils down to using the deg-2 CHSS to evaluate N B i N , where B i is the matrix of the ith output for a target bilinear correlation, and N is the parity check matrix of an LPN-friendly code. However, this general method has a downside: in many concrete scenarios, the matrices B i of the target correlation will be highly sparse (for example, for building (pseudo)random oblivious transfers, the corresponding matrices B i have a single nonzero entry). Yet, N cannot be a sparse matrix: using a code whose parity check matrix is sparse would render LPN insecure, since this corresponds to decoding an LDPC code, which can be done in polynomial time. Therefore, the matrices N B i N will be dense even though each B i might be sparse. This makes the computation wastefull: the computation of

z 0 N B i N z 1 requires O(n • ) = O(α • n 2
) operations (recall that this is for computing each output of the correlation), which becomes quickly inefficient for a large target output size n.

We suggest an alternative approach to bring this computational cost from quadratic to linear. The main idea is to set N to be the matrix of a low-density parity check code [Gal62,MN96] (LDPC) instead of a random code. LDPC codes are particularly attractive in our scenario, for two main reasons.

1. First, the conjectured intractability of LPN instances obtained from the parity check matrix of an LDPC code (which is a sparse matrix) is a well-established standard assumption, similar to the assumption made in the seminal work of Alekhnovich [Ale03] on public-key encryption from LPN. 2. Second, LDPC admit a linear-time, data oblivious encoding algorithm over arbitrary fields [LM10, KS12], with very good concrete efficiency: encoding with a binary LDPC whose parity-check matrix has rows requires at most 4 • • ( k -1) XORs, where k denotes the row weight of the parity-check matrix (LPN with highly sparse matrices being conjectured to be intractable, the value k can be taken to be very small, say, lower than 10, in practice; see e.g. [ADI + 17]).

Of course, LDPC codes are expanding, while we need a compressing matrix; therefore, the right approach here is to use the transpose M of the matrix M of an LDPC code. It might not be obvious at first sight that the existence of a linear-time algorithm for computing x → M x implies the existence of a linear-time algorithm for computing x → M x. However, this is the case for linear mappings computed by linear operations: for any such mapping, there is a circuit of the same size computing the transposed mapping [Bor57,IKOS08], which essentially consists in reversing the computation while interchanging XORs and fan-out operations.

The second idea is to use the fact that level 1 and level 2 shares of the CHSS of the previous section directly support homomorphic evaluation of linear functions. Combining the two ideas gives rise to the following approach for speeding up the Expand procedure of a BCG built out of this CHSS:

1. Set N to be the transpose of the encoding matrix of an LDPC code whose parity-check matrix has low row-weight (say, at most 10).

2. Given a level 1 encoding z 0 sk of a vector z 0 (i.e., a BGN-EG encryption of z 0 over G t ) and a level 2 encoding ⟪z 1 ⟫ sk of a vector z 1 (i.e., sk t • z 1 ), homomorphically compute N z 0 sk and ⟪N z 1 ⟫ sk using the transposed version [Bor57] of the linear encoding algorithm of [LM10]. For example, if R = F 2 and k = 5, computing N z 0 sk requires 64 • multiplications over G t (16 for each of the 4 components of a BGN-EG ciphertext). The cost of computing ⟪N z 1 ⟫ sk is negligible in comparison (it involves only additions over Z q , which are cheap). 3. Apply the Mult algorithm on N z 0 sk and ⟪N z 1 ⟫ sk to compute additive shares of the value (N z 0 ) B i (N z 1 ) for each of the matrices B i . Note that this Mult procedure can now take advantage of the sparsity of the B i .

The above alternative method brings down the cost of computing each output of the Expand procedure from O(α • n 2 ) to O(α • n) in the (classical) situation where the B i are sparse. As we will see later in our efficiency estimations for the concrete goal of computing OT correlations, this easily amounts to an improvement by several orders of magnitude of the cost of this step.

D.3.2 Alternative Choices of Code Matrices.

The choice of LDPC-based codes above is motivated by efficiency considerations. However, alternative choices of code matrices can be envisioned, which lead to different tradeoffs between the strength of the assumption and the computational efficiency of the matrix-vector multiplication. . Their construction of linear-time encodable code is essentially a concatenation of good a linear encoding and its transpose, intertwined with random local mixing. This design strategy leads to codes satisfying the combinatorial properties of random linear codes (e.g. meeting the Gilbert-Varshamov bound) and do not support efficient decoding, while having a fast (linear-time) encoding algorithm; this makes it a strong candidate in our scenario. -Other Codes. Many other alternatives can be envisioned: since we do not require the code to have structure, or decoding algorithms. Therefore, any sufficiently good heuristic mixing strategy (e.g. a strategy based on expander graphs, such as the approach developped by Spielman in [Spi96]) will likely lead to a secure LPN instance in our setting.

E Group-Based Silent OT/OLE Extension

In this section, we focus on the task of using PCG to generate (random) oblivious transfer correlations. After motivating the question of computing random OTs with sublinear communication, which we believe to be a task of fundamental interest, we describe various optimizations of PCG tailored to this application, perform extensive efficiency estimations, and analyze techniques to mitigate the inverse-polynomial failure probability of the group-based PCG of the previous section for this application.

E.1 Generating ROT-Correlations with Group-Based PCG

In this section, we study the application of the techniques we developped for the specific (but fundamental) case of random OT correlations. We provide an extensive efficiency analysis of the construction.

E.1.1 Random Oblivious Transfer.

A random (bit) oblivious transfer (ROT) is a two party protocol between a sender and a receiver, both with no input. The sender gets as output two uniformly random bits (r 0 , r 1 ), and the receiver gets (b, r b ), where b is a random bit. Given black-box access to an ROT primitive, any multiparty functionality can be securely evaluated with information-theoretic security (in particular, implementing OT from ROT requires exchanging 3 bits), making ROT a core primitive for multiparty computation. One can easily observe that an equivalent formulation of the ROT functionality is the following: the sender and the receiver both get a respective random bit (s, r), as well as additive shares (over F 2 ) of their product sr. We focus below on the latter formulation. As ROTs correspond to a degree-2 correlation, they can be generated using a PCG.

E.1.2 Optimized Group-Based PCG for ROT Correlations.

We provide below a self-contained description of the group-based sanitizable PCG of the previous section, tailored to ROT correlations, using all optimizations that apply in our setting. The PCG is parametrized with three integers (α, k, n), where α is a parameter of the underlying LPN assumption, n is the target output length, and k is a sparsity parameter. For simplicity, we assume that α • n is a perfect square. To balance the benefits of optimizations based on revealing the ElGamal random coins to one of the parties, the parties (P 0 , P 1 ) will execute two parallel instances of the algorithms Gen and Expand below, exchanging their roles in each instance. To optimize for efficiency, we use an LDPC code matrix, and rely on the LPN with tensored noise assumption, discussed in Section D.

-Output. The two parties get respective outputs (x, w 0 ) ∈ F 2n 2 and (y, w 1 ) ∈ F 2n 2 such that w 0 + w 1 = x • y, where • denotes the component-wise product over F 2 .

-Setup. Sets pp = (q, G 1 , G 2 , G t , g 1 , g 2 , e) $ ← BGN-EG.Setup(1 λ ), and compute (pk, sk) ← BGN-EG.KeyGen(pp ). Compute g t ← e(g 1 , g 2 ). Output pp ← (pp , pk, g t ) and sk. Let MPFSS = (MPFSS.Gen, MPFSS.Eval, MPFSS.FullEval) be a multi-point function secret sharing over Z q , and let G be a PRG.

-Gen. Set ← α • n. Pick a random seed k 0 , and parse G(k 0 ) as (a representation of) a pair of (pseudo)random sparse vectors (a, b) ∈ (Z √ q ) 2 , each with exactly k entries equal to 1 and √ -k entries equal to 0, together with 2

√ (pseudo)random coins (r 1 , r 2 ) ∈ (Z √ q ) 2 . Set c 1 ← BGN-EG.Enc 1 (pk, a; r 1 ), c 2 ← BGN-EG.Enc 2 (pk, b; r 2 ).
Pick another random seed k 1 , and parse the string G(k 1 ) as a (representation of) a (pseudo)random vector d 0 ∈ Z q with exactly k coordinates equal to 1, and -k coordinates equal to 0. We denote proj x (for any vector x ∈ Z n q ) the multi-point function which, on input i ≤ n, outputs the i'th coordinate of x. Parse sk as (sk 1 , sk 2 , sk t ) and parse sk i as (s i , -1) for i = 1, 2. Let proj m,sk ← (proj s 1 s 2 m , proj -s 1 m , proj -s 2 m , proj m ). Compute (K 0 , K 1 ) ← MPFSS.Gen(1 λ , proj d 0 ,sk ). The output of P 0 is (k 0 , K 0 ), and the output of

P 1 is (k 1 , c 1 , c 2 , K 1 ).
-Expand. Let d 1 ← a ⊗ b. P 0 and P 1 expand their respective FSS keys K 0 and K 1 using MPFSS.FullEval, getting sk t • d 0 (i.e., additive shares over Z q of sk t • d 0 ).

• P 1 computes c t ← e(c 1 , c 2 ) ∈ G 4 t .
• P 0 expands k 0 into (a, b, r 1 , r 2 ) using G, and computes c t directly from a, b, r 1 , r 2 as

c t,0 ← e(g 1 , g 2 ) r 1 ⊗r 2 c t,1 ← e(g 1 , h 2 ) r 1 ⊗r 2 • e(g 1 , g 2 ) r 1 ⊗b c t,2 ← e(h 1 , g 2 ) r 1 ⊗r 2 • e(g 1 , g 2 ) r 2 ⊗a c t,3 ← e(h 1 , h 2 ) r 1 ⊗r 2 • e(h 1 , g 2 ) r 1 ⊗b • e(g 1 , h 2 ) r 2 ⊗a • e(g 1 , g 2 ) d 0
Note that all pairings involved can be precomputed in a one-time setup phase. • Let N ∈ Z ×n q be the transpose of the matrix of a binary LDPC code (each entry of N is viewed as a 0 or a 1 over Z q ). Both parties locally compute ( sk t • d i ) i≤n ← sk t • N d 0 and homomorphically multiply the plaintext of c t by N , obtaining a list of n ciphertexts (c i ) i≤n over G 4 t . Note that this multiplication by N can be done by homomorphically evaluating on c t the "transposed version" of the circuit of [LM10], which contains only XOR gates, interpreting all XOR gates as a modular addition over Z q (as no modular reduction occurs, the parties will obtain the correct result by locally reducing their final additive shares modulo 2).

• P 0 locally sets x ← N • d 0 mod 2, and P 1 expands k 1 into d 1 and locally sets y ← N • d 1 mod 2. • For i = 1 to n, the parties compute the Mult algorithm by sequentially evaluating

Pair(c i , sk t • d i ) = {g z i t }
, where z i is an integer value satisfying z i = x i • y i mod 2, and Convert( g x i •y i t , δ) = z i (where the equality holds except with some failure probability δ independently for each share). Finally, the parties locally convert these integer shares into F 2 -shares by reducing z i modulo 2, getting x i • y i mod 2. We denote by w σ the length-n vector of shares obtained by party P σ .

E.2 Efficiency Estimations

We now estimate the concrete efficiency of the group-based bilinear correlation generator, using all the optimizations described in the previous section, for generating a large number of (bit) ROT correlations. Cost estimates for other useful types of correlations (e.g. Beaver triples) can be easily extrapolated from our detailed estimations. We note that, although we will carefully evaluate the resistance to known attacks of the assumptions underlying some of our optimizations, these assumptions remain new and deserve further exploration. The efficiency estimations given in the upcoming sections are based on the concrete parameters designed so that known attacks take at least 2 80 steps to break the underlying assumptions; if improved cryptanalytic methods are discovered, our efficiency estimations should be revised accordingly.

E.2.1 Choices of Curve.

We estimate the costs of sanitizable PCG for random OT using the benchmark numbers of the Miracl library. 16 All benchmarks are executed on one core of a 2.4 GHz Intel i5 520M processor. We consider two pairing-friendly elliptic curves for type-3 pairings:

-An MNT curve with a 160-bit modulus q and an embedding degree equal to 6. A G 1 (resp.

G 2 , G t ) element is 160-bit (resp. 320-bit , 960-bit) long. The Miracl documentation reports the following timings over this curve: 1,9ms for a pairing, and 0,24ms for an exponentiation over G t = F q 6 (which approximately corresponds to 6 * 160 * 1.5 = 1440 multiplications over G t ). This curve is conjectured to provide 80 bits of security and is a good choice of curve to minimize the seed size (as each group element is only 160 bits long).

-A Cocks-Pinch curve with a 512-bit modulus q and an embedding degree equal to 2. A G 1 or G 2 (resp. G t ) element is 512-bit (resp. 1024-bit) long. The Miracl documentation reports the following timings over this curve: 1,14ms for a pairing, and 0,12ms for an exponentiation over G t = F q 2 (which approximately corresponds to 2 * 512 * 1.5 = 1536 multiplications over G t ). This curve is conjectured to provide 80 bits of security and is a good choice of curve to minimize the computational overhead (as pairings and exponentiations are respectively 40% and 50% less expensive than over an MNT curve, for the same security level).

E.2.2 Matrix Multiplication and Gaussian Elimination.

Most attacks on the LPN assumption and its variants require computing matrix multiplications, and solving systems of linear equations, for large matrices and systems. To estimate properly the efficiency of these attacks, we overview in this section the state-of-the-art regarding matrix multiplication and resolution of linear system. It is well known, and was first shown in [BH74], that solving linear systems of equations is reducible to matrix multiplication: if n × n matrix multiplication can be computed in O(n ω ), then solving Ax = y for an n × n matrix A can be done in time O(n ω ). More precisely, if M (n) denotes the time for multiplying two n × n matrices, then solving Ax = y for an n × n matrix A requires less than 2 • M (n) operations. Therefore, we focus in this overview on the cost of multiplying two matrices. We denote by ω the smallest possible value such that the time for multiplying two n × n matrices is in O(n ω ).

Matrix multiplication in subcubic time was believed to be impossible, until the seminal paper of Strassen in 1969 [Str69], which described an algorithm using n log 2 (7) multiplications. This result was followed from decades of improvement, culminating with the Coppersmith-Winograd algorithm [CW90] which established ω ≤ 2.375477, followed by subsequent improvements, with the current record being held by Le Gall's algorithm [LG12] (ω ≤ 2.3728639). However, all the results starting with the work of Coppersmith-Winograd suffer from the curse of recursion: they involve complex nested recursive calls, which make the constant term of the algorithms prohibitively large -so large that no such method has ever be implemented as of today, nor is believed to provide any concrete speedup for matrices of any realistic size [Pan18]. All known implementations of subcubic matrix multiplication algorithms rely on the original algorithm of Strassen, or it's improvement by Winograd (which reduces the number of additions, but leaves the asymptotic complexity unchanged) [Fis74].

It is hard to estimate what exactly is the current optimal algorithm for feasible matrix multiplication, since it largely depends on the specific features of the problem at hand. To our knowledge, the smallest matrix multiplication exponent for which matrix multiplication has feasible constants is 2.7760 [Kap04]. The algorithm of Kaporin [Kap04] was implemented and compared with the algorithms of Winograd and Strassen (which have exponents log 2 (7) ≈ 2.807) for n × n matrices of size up to n = 2 • 10 5 . At these sizes, Kaporin's algorithm had a running time within a factor 1.05 to that of Strassen and Winograd's algorithm. It follows that a sufficiently good upper bound on the running time of a matrix multiplication algorithm is given by the cost n log 2 (7) of Winograd's algorithm (note that over F 2 , where additions cost as much as multiplications, the number of bit operations for Winograd's algorithm is 5 • n log 2 (7) ).

While the previous results establish the best known running time for multiplying two n × n arbitrary matrices, our optimized group-based PCG involves structured matrices -typically, LDPC matrices, which have a sparse parity-check matrix. Multiplying an LDPC matrix with an arbitrary matrix can be done faster than through general matrix multiplication: the linear-time LDPC encoding algorithm of [LM10] allows to compute an LDPC encoding Ax of a vector x with code matrix A in time 4d • n, where d is the maximum number of non-zero elements in the parity check matrix of A. This directly lead to a matrix multiplication algorithm in time 4d • n 2 . While it is not entirely clear wether the linear system solver from matrix multiplication of [BH74] preserves the LDPC structure of the matrix through the algorithm (since the algorithm involves recursive calls to the matrix multiplication functionality on blocks of A), it is plausible that it can be modified to maintain this structure. Therefore, we will conservatively assume below, when estimating the resistance of our scheme to known attacks, that the cost of solving a system of linear equations is lower bounded by 4d • n 2 . E.2.3 Parameters for the LPN with Tensored Noise Assumption.

We discuss choices of parameters for the LPN with tensored noise assumption, by evaluating the efficiency of known attacks on this assumption. We consider LPN with tensored noise with k 2 noisy coordinates, dimension (α -1)n, and number of samples αn. Note that we use LPN with tensored noise over F 2 , therefore the low-weight parity-check attack does not apply to our setting (see [Zic17]).

-Gröbner Basis Attack. We first evaluate the resistance of LPN with tensored noise against Gröbner basis attacks. These attacks to not directly depend on the number of noisy coordinates, but mainly on the compression factor (recall that we extend √ αn bits to αn bits, before compressing the output to n bits). Hence, these attacks will allow us to determine the optimal value of α for a given n.

As is always done to study the complexity of Gröbner basis attacks, we conjecture that the corresponding system of quadratic equations is semi-regular. This conjecture is supported by the fact that the proportion of semi-regular systems goes to 1 when the number of unknown grows [Bar04,Frö85]. By [BFSY05, Theorem 1], the average complexity of a Gröbner basis attack is given by t d reg ω , where t = √ αn is the number of unknowns in the system, ω is the matrix multiplication exponent (which we assume equl to 2.8), and d reg is the regularity degree, which was shown in [BFSY05] to be upper bounded by

-n + t 2 + t 2 2(n/t) 2 -10n/t -1 + 2(n/t + 2) (n/t) • (n/t + 2) .
Solving the above under the condition that the Gröbner basis attacks requires at least 2 80 operations, we get the following:

• For n < 2 26 , the regularity degree d reg is equal to 3, and the smallest value of α which allows to stretch √ αn bits to n bits is α = 24. • For n ≥ 2 26 , the regularity degree d reg is equal to 2, and the smallest value of α which allows to stretch √ αn bits to n bits is α = 16. -Gaussian Elimination Attack. For the standard LPN assumption with k noisy coordinates, the Gaussian elimination attack requires on average (1/(1 -k/(αn))) (α-1)n iterations, where the adversary must invert an ((α -1)n) × ((α -1)n) matrix, which takes time at least ((α -1)n) 2.8 using Strassen's matrix multiplication algorithm. However, since we use an LDPC code, which admits a linear-time encoding algorithm, the linear system can be solved more efficiently: the linear-time encoding algorithm of [LM10] gives matrix-vector multiplication in time (2α -1) • d • n, where d is the sparsity parameter of the parity-check matrix of the code, which we denote d; hence, multiplying and LDPC code matrix with an arbitrary square matrix takes time at most α(2α -1) • d • n 2 . Using the reduction from matrix multiplication to solving systems of linear equations [BH74], this leads to an algorithm for solving the system in time lower-bounded by α(2α -1) • d • n 2 (see the discussion in the previous section).

For LPN with tensored noise, which involves a noise vector with k 2 noisy coordinates, there is a better way to sample the candidate noise-free subvector: as the vector is of the form x = a ⊗ a for a k-sparse vector a, it suffices to divide x into √ αn blocks of √ αn coordinates each. Note that each block is either equal to a or to the all-0 vector. Hence, the adversary can simply guess (α -1)n/ √ αn noise-free blocks (there are √ αn -k such blocks), which requires on average (1/(1 -k/ √ αn)) (α-1)n/ √ αn iterations. Therefore, a lower bound on the bit-security of the LPN with tensored noise instance with respect to the Gaussian elimination attack is given as

log 2 1 1 -k/ √ αn ((α-1)n)/ √ αn • α(2α -1) • d • n 2 .
-Parity-Check Attack. A noisy codeword can be distinguished from random by multiplying it with a parity-check vector. Over F 2 , a random vector will pass the parity-check with probability exactly 1/2. However, a noisy codeword will pass the check with probability 1 conditioned on all the noisy coordinates corresponding to zero-entries of the parity-check vector, and with probability 1/2 otherwise. Therefore, parity-check vectors allows for a nontrivial distinguishing advantage.

Since the dual code has distance at most (α -1)n in our setting, there always exists as parity check vector with at most (α -1)n + 1 non-zero coordinates, which is obtained by writing the dual matrix in systematic form, and using it to encode an arbitrary low-weight vector. This way, up to αn -(α -1)n -1 = n -1 coordinates are guaranteed to be zero; the remaining (α -1)n + 1 coordinates being over F 2 in our setting, they will contain on average ((α -1)n + 1)/2 zeroes. Therefore, we assume that the adversary can compute at no cost (since they can be preprocessed given only the code matrix) a list of parity-check vectors of weight ((α -1)n + 1)/2. Under the heuristic that the k 2 noisy coordinates are randomly spread over the noise vector, a parity-check vector will have only zeroes in positions corresponding to the noisy coordinates with probability αn -((α -1)n + 1)/2 αn

k 2 = αn + n -1 2αn k 2 .
After each iteration, the adversary must compute a parity-check with a vector of weight ((α -1)n + 1)/2, which costs him ((α -1)n + 1)/2 arithmetic operations. Therefore, the (logarithm of the) average computational cost of the parity check attack is given by

log 2 (α -1)n + 1 2 • αn αn + n -1 k 2 .
Finally, observe that the heuristic assumption that the noise is randomly spread is clearly false here: since the noise vector was computed as a tensor product between low-weight vectors, it satisfies a block structure, where each block is of length √ αn, k blocks are noisy and the remaining are noise-free, and the noise pattern is the same accross the noisy blocks. However, to exploit this known structure, the adversary would have to guess the position of noise-free blocks, and then to find a parity check vector with a large number of non-zero coordinates belonging to these noise-free blocks. While this can be done in a preprocessing phase, it requires a prohibitive amount of preprocessing: we estimated that, in our range of parameters, the adversary would need to compute at least 2 200 operations when preprocessing the parity-check vectors to get a noticeable speedup in the online attack. Therefore, we do not consider speedups from preprocessing parity-check vectors in our estimations, but note that finding imoproved preprocessing techniques is a possible direction that deserves further study toward getting a better cryptanalysis of our assumption using parity-check attacks.

-Information Set Decoding Attack. We now turn our attention to the ISD attack. Many variants of the attack have been developed in the past years, and the asymptotic costs of these attacks are often non-trivial to estimate. However, in our parametter setting, the noise rate k 2 /(αn) is small, and the advantages of the variants of the original algorithm of Prange [Pra62] vanish in this situation, as shown in the analysis of [TS16]. We will therefore focus on bounding the cost of the original algorithm of Prange; since we will find this attack to have much worst performances than the Gaussian elimination attack, this leaves a large security gap. To make conservative estimates, we evaluate the cost of the attack against a standard LPN instance with k noisy coordinates; that is, we make the assumption that due to their structure, the k 2 noisy coordinates of LPN with tensored noise do not provide additional security compared to k (random) noisy coordinates. We rely on the detailed concrete efficiency analysis of ISD given in [HOSS18], which shows that the bit-security of the LPN instance with respect to Prange's algorithm is upper-bounded by

log 2 αn k n-1 k • 8d • (n -1) 2 ,
where 4d • (n -1) 2 denotes our conservative estimate of the cost of solving a linear system of equations given by an LDPC code with parity-check matrix of row-weight d (see the discussion in the previous section).

E.2.4 Optimal Parameters.

We use the above analysis to choose optimal parameters to achieve 80 bits of security against Gröbner basis attacks, Gaussian elimination, parity checks, and ISD. The optimal parameters are represented on Table 5. Table 5. Optimal parameters k and α for various choices of n. We consider the cost of attacking the LPN with tensored noise assumption, instantiated with an LDPC code matrix, using either Gaussian elimination, Gröbner basis attacks, ISD, or parity-check attacks. We set the sparsity parameter of the parity-check matrix to d = 10.

E.2.5 Size of the Seeds.

We estimate below the size of the seeds stored by P 0 and P 1 , using the MPFSS of [BCGI18].

For concreteness, we consider an AES-based implementation of the PRGs, and instantiate the elliptic curve with the two candidates described above. The PRG seeds k 0 , k 1 are λ-bit long, while

|K 0 | = |K 1 | = k • ( log • (λ + 2) + λ + log q ) with = α • n. Each c i for i = 1, 2 is of size 2 • √ • |G i |. Therefore:
-The total size of P 0 's seed is λ + k • ( log • (λ + 2) + λ + log q ) bits.

-The total size of P 1 's seed is 2

• √ • (|G 1 | + |G 2 |) + λ + k • ( log • (λ + 2) + λ + log q ) bits.
Concretely, consider a target number of 2 27 ROTs, which are computed using two parallel instances of the above PCG for n = 2 26 where P 0 and P 1 exchange their roles in the two instances (to balance the storage load), and set α = 2 (a smaller α would further reduce the storage, but at the cost of increasing k, which has an impact on the computational efficiency of the Convert procedure). Then, using the MNT curve, each party stores a seed of length 3.76 Megabytes, which on average amounts to 4.3 ROT produced per bit of the seed. Using the Cocks-Pinch curve, the seed size increases to 8 Megabytes (2 ROT produced per bit stored). We represent on where the parties obtain seed of the same length by exchanging their roles in two parallel PCG instances. We set λ to 128, and choose the values of α and k according to Table 5. We provide the size (in Megabytes) of the seeds using both an MNT curve and a Cocks-Pinch curve, whose parameters are described at the beginning of Section E.2. The row ROT/bit (curve) denotes the number of ROT produced per bit of the seed stored, i.e., the bit size of the seed divided by n, using the curve curve.

E.2.6 Efficiency of Expand.

We now estimate the computational cost of each step of the Expand procedure. In this section, we assume that the column-weight d of the parity-check matrix of N is upper bounded by 10, which was shown to be reasonable choice in [ADI + 17]. With this parameters, computing the map m → N • m requires 10 • (2α -1)n XORs using the linear-time algorithm of [LM10, KS12] (see e.g. [BCGI18]). For each of the two parallel executions of Expand, the parties do the following (we ignore some costs which are several orders of magnitude smaller than all other costs, e.g. computing x ← N • d 0 and y ← N • d 1 ):

1. Both parties execute 4 instances of MPFSS.FullEval. 2. P 0 computes 4 pairings (to build c t from c 1 , c 2 ). 3. P 1 computes 9 exponentiations over G t (to build c t from (a, b, r 1 , r 2 )). 4. Both parties compute 40 • (2α -1)n multiplications over G t (to build (c i ) i≤n from c t and N ; the XORs are evaluated as homomorphic additions over Z q , and each such homomorphic addition requires the term-by-term product of two ciphertexts, hence 4 multiplications over G t ). 5. The parties execute n distributed discrete logarithms (the Convert algorithm). The efficiency of this step depends on the average size of the values z i such that Pair(c i , sk t • d i ) = {g z i t }. Concretely, each z i is the product of the i'th coordinates of N • d 0 and N • d 1 . Assuming that N has average row-weight /2, and since d 0 has k non-zero entries (all equal to 1) and d 1 = a ⊗ b has k 2 non-zero entries (all equal to 1), the average size of z i is k 3 /4. Using the optimized DDLOG of [DKK18] with average payload k 3 /4, the failure probability δ of the output is approximately δ = B(T ) • k 3 /(4 • T 2 ), where T is the number of multiplications over G t performed by each party, and B(T ) is a value below 2 10.4 (optimal values of B for various T are given in Table 1 of [DKK18]). We represent on Table 7 the failure δ obtained for various output lengths n and number of multiplications T , using the values B(T ) from Table 1

of [DKK18].

Table 7. Failure probability δ for various choices of n, T and an average size k 3 /4 of the exponent. The value B(T ) is chosen according to Table 1 of [DKK18]. We choose the optimal value of k for each value of n according to Table 5.

We now estimate the average running time of each of the 5 steps outlined above, for both MNT and Cocks-Pinch elliptic curves, using the benchmark values of the Miracl library (which are obtained on one core of a 2.4 GHz Intel i5 520M processor).

1. Using the analysis of [BCGI18] for an evaluation of MPFSS.FullEval on one core of a standard laptop, using either α = 16 or α = 24, the running time of this step per ROT produced is bounded above by 1µs. Note that we use a rough upper bound on the estimations of [BCGI18]; the average cost per ROT of this step being essentially negligible compared to the total average cost, these imprecise estimates have no significant impact on the overall estimated running time. 2. A pairing computation takes 1.9ms on an MNT curve, hence the average cost of step 2 is 4 * 1.9 /n = 7.6α, which amounts to 182.4ms per ROT for α = 24, and 121.6ms per ROT for α = 16. On a Cocks-Pinch curve, where a pairing takes 1.14ms, the cost is reduced to 107ms per ROT with α = 24 (resp. 71.7ms with α = 16). Note that only one of the parties performs this step, hence the cost per party is reduced by a factor 2 when balancing over two parallel instanced of PCG where the parties exchange their roles. 3. An exponentiation over G t takes 0.24ms on an MNT curve (resp. 0.12ms on a Cocks-Pinch curve), hence the average cost of step 3 is 9 * 0.24 /n = 51.8ms using α = 24, or 34.6ms with α = 16 over an MNT curve (resp. 25.9ms or 17.3ms over a Cocks-Pinch curve). As only P 1 executes this step, the same observation as in the previous step applies, and the average cost per party can be reduced by a factor 2. 4. An exponentiation amounts to about 1440 multiplications over G t for the MNT curve, and to about 1536 multiplications over G t for the Cocks-Pinch curve. Therefore, the average cost of step 4 is (1/1440) * 64 * 0.24 /n = 0.26ms or 0.17ms using α = 24, 16 for the MNT curve, and 0.12ms, 0.08ms for the Cocks-Pinch curve. 5. This step requires T multiplications over G t per party, where the choice of T determines the failure probability of each ROT (see In Table 9, we represent the total running time per parties (in millisecond) when averaged over two parallel executions of the PCG (e.g. for a target output size n = 2 21 , the parties execute two parallel instances of PCG with output size 2 20 , exchanging their roles in each instance). We set α = 2. We illustrate the cost on an instance for concreteness: to compute 2 23 ROT, setting α = 2 and T = 2 15 gives an average running time of 15ms per party over an MNT curve, where each ROT is correct except with probability 1 -2 -9.4 (hence, one out of 676 ROT will be faulty on average). The storage overhead (i.e., the size of the seed stored by each party) amounts to 0.35 bits per ROT. However, generalizing to larger rings comes at a cost in terms of computational efficiency. While the number of pairing operations, which is the main efficiency bottleneck for generating OT correlations, remains the same, the cost of the distributed discrete logarithm procedure scales linearly with the increased field size. More precisely, suppose two parties want to generate an OLE correlation over a ring Z t , for some small polynomial t, with a failure probability of δ per output. Executing a distributed discrete logarithm on a value of average size N requires T (δ) steps, where T (δ) is chosen such that δ = B • N/T 2 , with B ≈ 400 [DKK18]. In the group-based PCG for OLE correlations, the target value z for the distributed discrete logarithm is of the form x • y, where x is a value computed as the inner product between an arbitrary vector and a weight-k 2 random vector, and y is a value computed as the inner product between an arbitrary vector and a weight-k random vector (where all vectors are over Z t ). Therefore, the average size of z is N = k 3 • (p -1) 2 /4. Hence, the number of steps T to be performed grows as

T = (p -1) • B • k 3 4δ .
Let us fix for example a target failure probability of δ ≈ 2 -15 per output, and a target number n = 2 26 of OLE correlations (hence k = 12 by Table 5). Using an MNT curve (using the Miracl benchmark to estimate the cost of operations) and solving the above equation for T gives an estimated running time of (t -1) • 12.5 milliseconds over Z t for the distributed discrete logarithm procedure. For the same n, k and using α = 16, the estimated running time of expand, ignoring the distributed discrete logarithm, is about 95 ms. Therefore, the estimated running time to compute OLE correlations over Z t , for n = 2 26 and with failure probability 2 -15 per output, grows as 95 + (t -1) • 12.5 milliseconds.

E.4 Sanitizing the Output: the Punctured OT Approach

While the previous sections gives reasonable estimates of the cost of generating n ROT with a group-based PCG, the ROT computed this way will be faulty, due to the inverse-polynomial failure probability of the group-based PCG. After computing n instances of ROT correlations using group-based PCG, it remains for the parties to securely remove on average δ • n faulty outputs (where δ is the failure probability of the PCG). This failure probability comes from the imperfect correctness of the distributed discrete logarithm procedure. The DDLOG protocols of [BGI16a] and [DKK18] both allow a selected party to detect whether there is a risk of error at a mild cost (e.g. with the scheme of [DKK18], detecting failures requires computing an additional O(M ) number of multiplications, where M is the bound on the input, independently of the failure probability). Unfortunately, we cannot simply let the selected party notify his opponent about the faulty outputs to remove them: knowing that a failure risk was detected would leak informations to this party. 17 To overcome this issue, the works of [BGI16a] and [BCG + 17] developped different strategies, which we briefly outline below.

-Punctured OT [BGI16a]. To allow for secure reconstruction of faulty outputs, the work of [BGI16a] suggest to use a simple erasure-correction code, and to let one of the parties obliviously recover all outputs at positions where he did not detect a failure. By the properties of the erasure code, the recovered outputs suffice to reconstruct the entire output. The core observation of [BGI16a] is that an all-but-few random OT can be constructed efficiently: there is a protocol which securely realizes (n-t)-out-of-n random OT, with a communication proportional to t and log n only. This protocol relies on a puncturable pseudorandom function. -Leakage-Absorbing Pads [BCG + 17]. Alternatively, the work of [BCG + 17] suggests to add some number of level-2 shares of random bits to the BCG seed, and develop methods to perform the computations on values masked with these random bits. This allows to square the leakage probability, as a failure will leak information only if two failures occured with respect to the same random mask. Asymptotically, this strategy has costs comparable to punctured OT, but leads to a considerably simpler distributed seed generation. However, the technique can only be used to mask bit inputs, and does not seem to generalize to larger integers.

Below, we apply the punctured OT approach [BGI16a], which we estimated to be more efficient in our scenario. We provide a detailed overview of an optimized application of this approach to our scenario. To implement this approach, we need two ingredient:

an efficient punctured OT protocol, and a randomized linear code with good erasure-correction properties.

Punctured OT protocols can be built from t-puncturable pseudorandom functions, together with an appropriate two-party computation protocol. We recall the definition of puncturable PRFs below, and describe an optimized algorithm to puncture a PRF at t points efficiently.

E.4.1 Puncturable Pseudorandom Function.

We first recall the definition of puncturable pseudorandom functions (pPRFs), as they are the main primitive involved in the efficient realization of a punctured OT protocol, and describe an improved construction of a t-pPRF from the GGM PRF.

Definition 50 (t-Puncturable Pseudorandom Function). A puncturable pseudorandom function with key space K, domain X , and range Y, is a pseudorandom function F with an additional punctured key space K p and three probabilistic polynomial-time algorithms (F.KeyGen, F.Puncture, F.Eval) such that -F.KeyGen(1 λ ) outputs a random key K ∈ K, -F.Puncture(K, x), on input a ley K ∈ K, and a subset S ⊂ X of size t, outputs a punctured key K{S} ∈ K p , -F.Eval(K{S}, x), on input a key K{S} punctured at all points in S, and a point x, outputs F (K, x) if x / ∈ S, and ⊥ otherwise, such that no probabilistic polynomial-time adversary wins the experiment Exp-s-pPRF represented on Figure 7 with non-negligible advantage over the random guess. Procedure. The labelling proceeds in t steps. Given a leave x and a subtree T of T which contains x, we denote by Label(x, T ) the procedure which outputs all nodes of T which have their parent node in P but are not in P themselves, where P denotes the path from the root of T to x.

-In step 1, set L1 ← Label(s1, T ).

-In step i + 1, let Ti+1 denote the smallest subtree of T which contains si+1 and whose root belongs to Li (Ti+1 exists by construction), and let ri+1 denote its root. Set Li+1 ← (Li \ {ri+1}) ∪ {Label(si+1, Ti+1)}.

After all steps are completed, output Lt.

Fig. 8. Labelling algorithm to compute the indices of a subset of keys in the GGM PRF construction which allows to reconstruct the output of the GGM PRF at all points except exactly t.

1. The parties invoke Π on a randomized functionality that, on input S ⊂ [n] from the receiver, outputs a random PRF key K to the sender, and the key K{[n] \ S} punctured at all points in [n] \ S to the receiver. 2. For i = 1 to n, the sender computes and sends

d i ← d i ⊕ F (K, i). 3. The receiver outputs (i, d i ⊕ F.Eval(K{S}, i)) for all i ∈ [n] \ S.
Plugging in Yao's protocol for Π, and the GGM construction for F , this leads to a protocol with n + (n -t) • log n • poly(λ) bits of communication, which is n + o(n) when n -t is sufficiently small, hence the result.

E.4.3 Erasure-Correcting Code.

The second ingredient we need is a randomized linear code with good erasure-correction properties. Such codes are common in the literature.

Lemma 51 (Lemma 5.2 from [BGI17]

). There is a randomized linear encoding function E r : {0, 1} n → {0, 1} n+n/λ that can correct a 1/λ 2 rate of random erasures, with all but n•negl(λ) probability.

The encoding of an n-bit input x is obtained by appending n/λ bits x 1 , • • • , x n/λ to x, where each x i is the parity of a random subset of λ 2 /2 -1 bits of x. By a standard Chernoff bound, the probability that a given bit of x cannot be recovered (which happens when all subsets containing this bit contain an erasure) is bounded by n • 2 λ/3 , hence the result.

While the above lemma provides an asymptotic statement, in practice computing the parity bit of O(λ 2 ) outputs with the PCG would be too expensive. Instead, we will seek to obtain a good tradeoff between the cost of computing the parity bits (we obtain better computational efficiency when each parity bit is the parity of few bits), and the total size of the encoding (we obtain a smaller size when each parity bit is the parity of many bits). Explicit choices of parameters a discussed in the section Efficiency Estimations below.

E.4.4 Putting the Pieces Together.

Given a punctured OT and an efficient erasure-correcting code, the following protocol gives an asymptotically good method to sanitize the faulty outputs of the group-based PCG: first, instead evaluating the target bilinear correlation B on the input with the PCG, the functionality is modified to evaluate E(B(•)) instead, where E is the encoding function of the above code (note that E is linear, hence E • B is a bilinear function).

Remark 52 (Preprocessing the Sanitizing Phase). It would be desirable, in our context, to preprocess the material needed to execute the sanitization phase (i.e., the punctured OT), so as to include the appropriate material directly in the seed of the PCG. However, the indices of the faulty outputs are not known when the PCG seed is generated. Nevertheless, the parties can preprocess the punctured OT on a uniformly random subset S of the appropriate size t (which adds λt log n bits to the seed). In the sanitization phase, the receiver can first send a permutation σ of [n] that maps all faulty outputs to S, and the sender applies σ to his output before executing the step 2. As S is random, this leaks nothing about which outputs failed. However, this increases the communication of the sanitization phase to n log n, superlinear in the number n of ROT produced.

As observed in [BCG + 17], the cost of the sanitization phase can be reduced to O(n) by executing it on blocks of outputs, rather than on individual outputs. Observe that each output of the GGM PRF is a random-looking λ-bit key; hence, this key can be used to mask up to λ outputs directly (or any larger number of outputs by first feeding this key to a PRG). The parties partition [n] into N = O(n/ log n) blocks (indexed by [N ]), each containing n/N outputs, for some tradeoff parameter N . As there are t faults in total, at most t blocks contain a faulty output. The parties execute a punctured OT on a random size-t subset S of [N ]. In the sanitization phase, the receiver sends a permutation σ of [N ] that maps the indices of all blocks containing at least one faulty output to S. Note that exchanging this permutation requires O(N log N ) = O(n) bits of communication. Note that the erasure code must also be applied directly at the block level.

E.4.5 Efficiency Estimations.

We provide an estimation of the cost of using punctured OT to mitigate the leakage. Consider the task of computing 2 26 ROTs using the group-based PCG, setting α ← 16 and T ← 2 16 . The probability of a failure event for each individual output with these parameters is 2 -14.7 , and these events are independent of each other. By a standard Chernoff bound, for any ε, the probability that the number of failures exceeds n

• 2 -14.7 • (1 + ε) = 2 11.3 (1 + ε) is bounded by Pr[X ≥ 2 11.3 (1 + ε)] ≤ e ε (1 + ε) 1+ε 2 11.3
, solving for the smallest ε such that the above quantity is bounded above by 2 -80 gives ε ≈ 0.217. Therefore, except with probability ≈ 2 -80 , the total number of failures will be bounded by t = 1.217 • 2 11.3 < 2 11.6 .

We set the number of blocks N to be n/128 = 2 19 (hence each block contains 128 consecutive outputs). The size of a PRF key punctured at t points, for a GGM PRF over domain [N ], is upper bounded by tλ log(N/t) < 2 11.6 • 2 7 • (19 -11.6) < 2 21.5 bits. As the seed of the groupbased PCG for n = 2 26 and α = 16 already has size ≈ 2 25 bits (for a Cocks-Pinch elliptic curve), adding the punctured key to the PCG seed does only marginally increase its size.

We now turn our attention to the parameters of the erasure-correcting code. We set the number nb of blocks involved in a parity check to be an arbitrary small number, say, 5 (other choices of nb would lead to a different tradeoff between computation and communication). Suppose that we want to ensure that every punctured block can be reconstructed, except with global probability 2 -40 (we stress that this is a statistical success probability, it has no impact on security). As there is at most 2 11.6 punctured blocks (out of 2 19 blocks in total), this means that every block must be involved in at least -40/ log(5 • (2 11.6 /2 19 )) ≈ 7.9 parities to ensure a 1 -2 40 probability of successful reconstruction. By a standard Chernoff bound, this means that the number of parity-check blocks to be added to the output is approximately 7.9 * n/nb ≈ 1.58n.

To apply the error-correcting code as part of the PCG Expand procedure, the parties executes the steps 1-5 of Expand as previously. Then, for each parity-check block to be computed, the parties retrieve their multiplicative shares of (g ), compute a DDLOG to recover additive shares of 5 i=1 b i , and reduce their shares modulo 2. This adds to the total computation 1.58n DDLOGs on exponents of average size 5 • (k 3 /4) (the cost of the homomorphic multiplications is negligible compared to the other costs). With these parameters, using again the benchmark numbers of the Miracl library, the average running time for computing each sanitized ROT on one core of an Intel i5 processor over a 512-bit Cocks-Pinch curve (n = 2 26 , α = 16, T = 2 16 , nb = 5) is approximately 187ms. The communication involved in the punctured OT protocol consists in exchanging a permutation of [N ] = [n/128], and sending N blocks masked by a PRF output, for a total communication of (1 + 1.58) • (log(n/128) + λ) • n/128 < 3 • 2 26 bits, taking n = 2 26 and λ = 128 (hence on average 3 bits per sanitized ROT). We represent on Table 10 the result of similar calculations for other choices of T and n ≥ 2 26 , with α = 16. The table summarizes the size of the punctured key (which is added to the seed of the PCG), the estimated running time, and the communication required to sanitize the output (per sanitized OT correlation produced).

b 1 t , • • • , g b 5 t ),
Please note that the running time estimates given in the table do not correspond to measured running time of an actual implementation, but are estimated from the number of operations performed, using benchmark data for estimating the running time of each operation. Therefore, these estimates do not take into account additional costs resulting from, e.g., cache-misses, and should only be seen as providing a rough indication of the actual running time rather than an accurate estimation. 10. Punctured key size, estimated running time (for the total computation, including the seed extension plus the sanitization), and communication per sanitized ROT, for various choices of (T, n). We use α = 16 and a Cocks-Pinch curve in the calculations. The security parameter λ is set to 128, and we ensure a statistical probability of 1 -2 -40 of producing at least n sanitized OT correlations. The failure probabilities corresponding to the choice of T are taken from Table 5, and the running time estimates for the non-sanitized OT correlations are taken from Table 9.

E.5 Sanitizing the Output: a New Approach

In this section, we observe that a much more efficient sanitization procedure can be obtained by relying on the silent OT extension protocol introduced in Section 5, demonstrating an interesting and surprising interplay between our techniques for building PCGs. The key idea is that, by choosing an appropriate failure bound per output, it can be ensured that all but a tiny number of blocks of output correlation contain a sufficiently small number of faulty outputs. Then, this tiny number of blocks with too many faults can be safely deleted by simply revealing their position (recall that the failures are detectable, hence one of the parties can know their position). If the number of such block is guaranteed to be sufficiently small with overwhelming probability, this only incurs a leakage of O(1) bits of information about the seed of our group-based PCG. Then, the security of the construction is maintained under the non-standard but plausible assumption that the underlying assumption (LPN or a variant of it) is resilient to a constant amount of leakage. Eventually, since all remaining blocks are guaranteed to contain a sufficient number t of non-faulty outputs, a t-out-of-m oblivious transfer protocol can be used to let one of the parties securely select the t non-faulty correlations. Using the silent OT extension protocol introduced in Section 5, these t-out-of-m oblivious transfers can be locally generated from a short seed (which can be added to the group-based seed with almost no overhead) by the parties. Compared to the punctured OT approach, this method incurs a slightly larger communication (about 4 bits per sanitized outputs, instead of 3 with punctured OT), but is computationally much more efficient, and requires much less preprocessing material (which, in particular, should considerably simplify the task of distributively generate the preprocessing material; note also that our silent OT extension admits a very efficient distributed setup based on the Doerner-shelat protocol). We elaborate below.

E.5.1 Concrete Instantiation.

Assume for simplicity that the parties want to generate n = 2 26 sanitized correlations. The PCG seed is made of the seed of our group-based PCG, together with two seeds for a 1-out-of-4 silent OT extension. To generate n sanitized correlations, the parties P 0 and P 1 first generate 2n faulty correlation (using e.g. two parallel instances of the group-based PCG with n = 2 26 , exchanging their roles to balance the cost), setting the parameters so that each output has a probability bounded by 2 -15 of being faulty (based on our previous estimates, this requires performing about T = 72 • 10 3 multiplications for each distributed discrete logarithm, which takes about 12ms using an MNT curve). At the same time, the parties locally generate n random 1-out-of-4 OTs, using the silent OT extension protocol. We assume that P 0 has detected the position of the potentially faulty outputs.

To sanitize the output, the parties divide the 2n outputs into n/2 blocks of 4 outputs. P 0 first indicate to P 1 the position of all blocks that contain at least three faulty outputs; by a standard Chernoff bound, there will be at most 3 such blocks in total, except with probability bounded by min >0 (1 + 2 -15 • (e -1)) n/2 /e 4 < 2 -70 (note that this is a statistical security guarantee). Therefore, under the plausible assumption that LPN with tensored noise is resilient to 9 bits of random leakage, revealing the position of these blocks does not harm the security of the protocol. Both parties locally delete the corresponding block.

For all remaining blocks, which are guaranteed to contain at most 2 faulty outputs, the parties execute two 1-out-of-4 OT protocol using the preprocessed material from the silent OT extension, where P 1 plays the role of the sender. More precisely, for each 4-tuple of shares (u 0 , u 1 , u 2 , u 3 ), P 1 locally generate new shares (v 0 , v 1 ), and uses (u 0 + v 0 , u 1 + v 0 , u 2 + v 0 , u 3 + v 0 ) and (u 0 + v 1 , u 1 + v 1 , u 2 + v 1 , u 3 + v 1 ) as input to the two 1-out-of-4 OT instances. If the faulty outputs are at positions 0 and 1 (for example), P 0 will securely retrieve (u 2 + v 0 , u 3 + v 1 ), hence the two parties will now have shares of the non-faulty correlations (u 3 , u 4 ). The protocol involves communicating 2 bits and 8 value per block, hence 4 values and 1/2 bit per sanitized correlation. In terms of computation, the main overhead comes from the need of computing twice more correlations in the first place, hence a factor-2 overhead compared with the non-sanitized group-based PCG. Note that this cost has not been optimized: both the communication and the computation of the sanitized PCG can be reduced by generating less faulty outputs, and fine-tuning the size of the blocks and the number of outputs to retrieve per block. We leave the optimization and the fine-tuning of this approach to future work.

F PCG from Lattices

In this section we give a lattice-based PCG construction for any family of polynomials of bounded degree over large finite fields, extending the results of the previous sections to more general correlations. As a use-case we consider the generation of authenticated Beaver triples, that is for the correlation {(a, b, ab, aα, bα, abα) | a, b ∈ Z p } for some fixed MAC α ∈ Z p . We provide efficiency estimates for joint seed generation (with security against semi-honest adversaries) and silent expansion.

The assumptions we build on are the sparse MQ-assumption discussed in Section 7.1 and the ring-version of the learning with errors assumption, recalled in the following.

Definition 53 (Learning With Errors over Rings (RLWE)). Let N ∈ N be a power of two q ∈ N with q ≥ 2, R = Z[X]/(X N + 1) and R q = R/(qR). Let χ be an error distribution over R. Let s ← χ. The RLWE N,q,χ -assumption states that the following two distributions over R 2 q are computationally indistinguishable:

-O χ,s : Output (a, b) where a ← R q , e ← χ and b = a • s + e -U : Output (a, u) ← R 2 q

In the following we instantiate the generic construction from Section 4.4 with variants of RLWE-based homomorphic secret sharing schemes.

F.1 PCG from Somewhat Homomorphic Encryption

As observed in [DHRW16, BKS19], from a somewhat homomorphic encryption scheme which supports distributed decryption one can construct a homomorphic secret sharing scheme. In the following we give a semi-generic definition of properties the underlying encryption scheme has to satisfy. Note that the definition can be instantiated with a variety of lattice-based encryption schemes.

Definition 54 (Depth-d Somewhat Homomorphic Encryption w/ Distributed Decryption). Let PKE := (PKE.Gen, PKE.Enc, PKE.Dec) be an IND-CPA secure public-key encryption scheme. We say that PKE is a secure depth-d public-key encryption scheme with distributed decryption if it further satisfies the following properties:

-Distributed decryption: Let R := Z[X]/(X N +1), for N a power of two, κ ∈ N and the secret key space of PKE contained in R κ q . We say PKE supports distributed decryption, if there exists an algorithm DDec such that for (pk, sk) ← PKE.Gen(1 λ ), sk 0 Notation. We generalize Alg ∈ {Enc, DDec, Eval} to vectors of inputs in a straightforward way: Alg is run independently on each entry of the vector (with independent random coins if Alg is randomized).

Instantiating the generic construction of Section 4.4 with an HSS based on somewhat homomorphic encryption yields a PCG for any degree-d correlation (see Figure 9). As the following Theorem is a straightforward consequence of Theorem 23, we omit the proof.

Theorem 55. Let R be a ring, , n, p, q, m ∈ N, PRG be a degree-c D -PRG PRG : R p → R n p and PKE = (PKE.Gen, PKE.Enc, PKE.Dec) be a depthlog cd somewhat homomorphic encryption scheme with message space R p and secret key space contained in R κ q . If PKE additionally support distributed decryption, then the PCG PCG = (PCG.Setup, PCG.Gen, PCG.Expand) from Figure 9 is a PCG for the family of functions F := {f : R n p → R m p | f is of degree at most d}.

PCG.Gen(1 λ ) :

-Generate the encryption keys. Generate keys (pk, sk) ← PKE.Gen(1 λ ). Choose sk0 $ ← R κ q and set sk1 := sk -sk0.

-Choose and encrypt a PRG-seed. Choose r ← D (Rp). Compute c r = PKE.Enc(pk, r) ∈ (R κ q ) .

-Output k0 := (sk0, c r ), k1 := (sk1, c r ).

PCG.Expand(σ, k σ , f ) :

-Parse kσ =: (skσ, c r ).

- Remark 56. Note that the key generation of the PCG given in Figure 9 can be sourced out to the setup phase and the same secret key shares used across many instances.

Corollary 57. Instantiating the PRG in the construction of Figure 9 with the degree-2 ρsparse PRG PRG MQ : Z p → Z n p from Definition 34 and the somewhat homomorphic encryption scheme with the BGV encryption scheme of Brakerski et al. [BGV12] (chosing parameters R = Z[X]/(X N + 1), p, q and error distribution χ s.t. evaluation of at least degree-5 functions/ depth-3 circuits is supported), we obtain a PCG for the generation of authenticated Beaver triples, assuming ρ-sparse M( 2 , n, R p )-MQ and RLWE N,q,χ .

F.2 Efficiency Estimates

Authenticated Beaver triples are used in multi-party protocols like [DPSZ12] to achieve fast online computation. Our PCG construction can be used as a plug-in to replace the preprocessing in such protocols by a short joint seed generation phase (with little communication) followed by a completely silent expansion phase. As in the described setting a large amount of Beaver triples has to be generated at once, lattice-based PCG constructions are of practical interest, despite the overhead introduced by encryption.

Generating many Beaver triples at once we can use ciphertext packing, as first observed by [SV14].

Remark 58 (Ciphertext packing,[SV14]). Let p be a prime and N ∈ N a power of 2, such that the polynomial X N + 1 splits over Z p into pairwise different degree-1 polynomials. If R := Z[X]/(X N + 1) (similar for general cyclotomic polynomials), this implies R p ∼ = (Z p ) N and enables "packing" N plaintexts into one ciphertext (by encrypting Ψ (z) for some z ∈ Z N p , where Ψ : (Z p ) N → R p ). In the following we will refer to R p as coefficient representation, and to (Z p ) N as CRT representation.

Thus, each ciphertext has room to hold N encryptions. We first consider "naive" ciphertext packing: We start with encryptions of each N seeds r ∈ Z p , perform the expansion homomorphically on the ciphertexts (which corresponds to expanding feach of the N seeds in parallel). This gives an output of nN correlated tuples in total.

In the following we estimate efficiency of the PCG construction given in Corollary 57 with the above described ciphertext packing. We use the parameters given in [CS16] to support depth-4 homomorphic operations (as an upper bound) and plaintext space modulus ≈ 2 128 listed in the following. Here, by T M we denote the time required for multiplication over R q and by T C the time for multiplication of a Z q element with an element in R q .

-Dimension of R (over Z): N ≈ 13688 (we use N = 2 14 ) -Ciphertext modulus: log q ≈ 750 (we use log q = 744) -Parameter for key switching: log T ≈ 140 -Cost of key switching: T KS ≈ 2(log q/ log T )T C -Cost of multiplication on ciphertexts: T Eval ≈ 4T M + T KS -Cost of multiplication of constant with ciphertext: ≈ 2T C -Cost of encryption: T Enc ≈ 2(T M + T C ) -Cost of decryption: T Dec ≈ 2T M For MQ we use parameters n = 2 /24 and ρ = 100. Further, we set = c • 2 9 for c ≥ 1. Later we will see that chosing c = 1 we surpass the breakeven point. In other words, = 2 9 is the smallest choice where the total output size of the correlation generator exceeds the seedlength. Our runtime estimates are based on NFLLib [ABG + 16]: A multiplication over R q requires time ≈ 9.54 ms and a multiplication over R q × Z q requires time ≈ 0.55 ms. For an overview of estimated setup computation and communication complexity (i.e. time and communication required for jointly generating the seed) and estimated expansion times for the described PCG construction and variants we refer to Table 2 in the main body.

Distributed seed generation: We first describe the setup of the keys and MAC α ∈ Z p , which can be reused across many instances. First, the parties jointly generate secret key shares (sk 0 , sk 1 ) and the corresponding public key pk, e.g. by generating secret keys according to a suitable distribution and exchanging shares as well as the corresponding public keys. Next, both parties choose a MAC share α σ $ ← Z p and define α σ ∈ Z N p to be the vector of all α σ entries. Next, the parties each compute and exchange c Ψ (ασ) := Enc(pk, Ψ (α σ )), and set c Ψ (α) := c Ψ (α 0 ) + c Ψ (α 1 ) .

To generate encryptions of N seeds a and b in Z p , both parties repeat 2 times: Sample an element R p at random (corresponding to N random Z p elements), and as for generating an encryption of the MAC key, exchange and add up the corresponding encryption.

As computation and communication is dominated by the last step, a rough estimate in the semi-honest setting are as follows: Generating 2 encryptions takes about c • 20 seconds of computation and exchanging 2 ciphertexts (each of size 2N log q bits) requires c • 3 GB of communication (per party). We estimate that in the dishonest setting communication complexity would roughly double.

Expansion rate: We expand 2 N elements in Z q to nN shared authenticated Beaver triples in Z p (each consisting of 6 Z p elements), which corresponds to expanding roughly c • 3 GB of seed material to authenticated Beaver triples of total size c 2 • 17 GB.

Computational efficiency of expansion: The computational costs add up as follows.

-Expanding the seed: The complexity to evaluate the PRG homomorphically on 2 ciphertexts sums up to 2 2 ciphertext multiplications and 4nρ multiplications of a constant with a ciphertext. -Computing the triples: Evaluation of f α requires 4n ciphertexted multiplications.

-Obtaining the output shares: To obtain the output we have to decrypt n6 ciphertexts.

Altogether, the costs sum up to ≈ 4nρT C + 4(2 2 + 7n)T M + 2( 2 + 2n)T KS . This gives a total computation time of around c 2 • 8.0 hours, which corresponds to an amortized computations time of roughly 0.16 ms per authenticated Beaver triple.

F.3 PCG with Iterative Expansion

As we choose a sparse matrix distribution (namely only ρ = 100 non-zero entries per row) to instantiate MQ, we can locally evaluate the PRG and therefore obtain a way to iteratively generate N Beaver triples at a time. This requires slightly more computational costs (assuming one wants to discard intermediary products), but allows to generate Beaver triples whenever needed instead of having to generate all at once. This can be achieved as follows: To generate shares of N Beaver triples, one needs to compute the scalar product of some i-th column of the M(l 2 , n, R p )-MQ matrix M with the vector of encryptions of r ⊗ r, where r is some seed. As M is sparse by assumption, this requires only to compute a linear combination of ρ products r i • r j on encryptions. With the numbers from above to generate N triples this approach inherits computational costs for expansion of (4 + 2ρ)T Eval + 4ρT C + 12T M = 4ρT C + (28 + 8ρ)T M + (4 + 2ρ)T KS . This corresponds to a computation time of about 10 seconds per iteration (i.e. per N triples of total size 1.6 MB generated), which is amortized 0.57 seconds per triple. Note that this approach is still limited to a total expansion of nN triples.

F.4 PCG with Full Ciphertext Packing

Note that the above approach limits us to go from ≈ N elements to ≈ 2 N elements (where N is the degree of the plaintext space over Z p ). As N is generally quite large that leads to a somewhat limited expansion. To overcome this we investigated into packing more smartly, which allows going from ≈ N elements to ≈ N 2 elements. To do so we build on the techniques of [HS18]. Even though the approach does not look promising in terms of computation due to expensive key switching operations, we believe that it is an interesting direction for future research.

For simplicity assume that R := Z[X]/(X N + 1) such that X N + 1 splits completely over Z p and further, that the Galois group G := Gal(Q(w)/Q) = {X → X j : j ∈ Z m } is cyclic, where w is a primitive N -th root of unity. In this case the automorphisms α ∈ G act on Z N p by rotating the slots. Let r = Ψ (r) ∈ R p be some packed plain text in coefficient representation corresponding to a vector of N plain texts r ∈ Z N p . As shown in [LPR10, HS18], applying an automorphism τ to a ciphertext c $ ← Enc(pk, Ψ (r)) leads to an encryption of Ψ (τ (r)) which can be decrypted with τ (sk) (roughly, the reason is that applying an automorphism does not change the norm of the noise much and therefore one can decrypt with the shifted key to the shifted plaintext). Thus, by applying an automorphism and introducing a key-switching step, we can let plaintexts in different slots interact with each other and thereby achieve truly quadratic expansion.

Again, consider the BGV scheme with depth-4 homomorphic operations and plaintext space modulus ≈ 2 128 . (Note that in order to get exact numbers one would have to make a careful analysis on the the noise growth introduced by applying the automorphisms. As the numbers we use support up to depth-4 homomorphic operations, whereas we only need to compute a circuit of depth-3, we assume that the parameters also apply to the described setting for the following analysis.)

We apply the matrix multiplication technique of [HS14] and assume to be given M $ ← M(N 2 , N 2 /24, R q ) accordingly in CRT-packed form. We can now start with a single ciphertext, i.e. 2N elements in Z q . In the following we provide the numbers for obtaining ≈ N 2 authenticated Beaver triples. Additional costs are N key switching operations during seed generation, and N 2 key switching steps during matrix multiplication (because the matrix multiplication technique requires to permute each part of the vector). Note that one can alternatively only partly expand the ciphertext to generate less triples at a time and thereby saving in terms of computations (at a time). We obtain the following estimated costs: 2N T KS + 2N T Eval + 2N 2 T KS + 2(N 2 /24)ρ + 4T Eval + 6T Dec = (8N + 28)T M + 2(N 2 + 2N + 2)T KS + 2(N 2 /24)ρ.

This adds up to a total expansion time in the order of c 2 • 900 hours and is therefore far from practical. We leave it as an open question to achieve truly quadratic extension at a reasonable time.

F.5 PCG from Somewhat Homomorphic Encryption with Nearly Linear Decryption

In this section we consider a hybrid of the HSS based on somewhat homomorphic encryption and the HSS of Boyle et. al [BKS19] based on encryption schemes which satisfy "nearly linear decryption". Roughly, the idea of [BKS19] is to replace multiplications of ciphertexts c x and c y , by a distributed decryption of the ciphertext c x with shares of y • sk, that is a distributed decryption of y times the secret key sk. This gives an improvement in terms of computation, as in practise distributed decryption can be an order of magnitude faster than homomorphic multiplication.

Our strategy is to replace the last multiplication with an encryption of ψ(α) by a distributed decryption of ψ(α) times the secret key.

In Figure 10 we present the construction for the generation of authenticated Beaver triples for a fixed MAC α ∈ Z p employing naive ciphertext packing. As [BKS19], we require the underlying scheme to additionally support nearly linear decryption. For details on a suitable choice of encryption scheme, we refer to [BKS19].

When choosing the parameters of the underlying encryption scheme, one needs to take into account the noise growth introduced by homomorphic multiplication, as the distributed decryption technique of [BKS19] requires p/ e ∞ q, where e is the noise term in the ciphertext. We estimate that taking the parameters for depth-4 BGV scheme is sufficient in practice. With the scheme of Figure 10 we can save 3n evaluation operations compared to the scheme solely based on somewhat homomorphic encryption, which results in a saving of about c 2 • 0.4 hours. We conjecture that an additional efficiency improvement over the previous scheme can be achieved by choosing the parameters more carefully.

Alternatively, we could employ the techniques of the group-based section building on function secret sharing for multi-point functions to get a compact sharing of one of the expanded seeds (i.e. (r ⊗ r) for one seed r). This would require switching one PRG to PRG LPN to allow for a sparse seed. Note though that in this case the MAC α has to be given in encrypted form again (and the order of multiplication to be switched), due to the structure of [BKS19]: Their scheme only supports a multiplication of an input value (= encryption) with a memory value (= secret share), where the output again is a memory value. Thus, for multiplication of a degree 3-polynomial, two of the factors have to be given as encryptions. Also, this results in significantly larger computation times, as for evaluating the PRG a non-sparse matrix has to be multiplied with a non-sparse vector (as the automorphism Ψ does not preserve sparseness).

We do not switch to the construction of Boyle et. al [BKS19] completely for the evaluation of f α , even though this would save another n evaluation operations, as to evaluate polynomials of degree-3 or higher their construction relies on the so-called modulus-lifting technique, which necessitates the choice of larger parameters for the underlying ring to ensure correctness.

G Multi-Party Simple Bilinear PCG

We begin with the proof of Theorem 41, providing the general transformation from any programmable 2-party PCG for simple bilinear correlation to a corresponding M -party PCG.

Fig. 1 .

 1 Fig. 1. Corruptible correlated randomness functionality for a reverse-sampleable correlation generator, C

Fig. 2 .

 2 Fig. 2. PCG for correlation CF . Here, PRG is a D -PRG and HSS = (HSS.Gen, HSS.Share, HSS.Eval) an HSS for the family of functions F HSS := {f • PRG : r → f (PRG(r)) | f ∈ F}.

  Theorem 23. (PCG for Additive Correlations from HSS). Let R be a ring and n, m, ∈ N. Let F ⊆ {f : R n → R m } be a family of functions. Let PRG be a D -PRG and HSS = (HSS.Gen, HSS.Share, HSS.Eval) an HSS with overhead O HSS 12 for the family of functions F HSS := {f • PRG : R → R m , r → f (PRG(r)) | f ∈ F } that further satisfies pseudorandomness of outputs. Then, PCG = (PCG.Setup, PCG.Gen, PCG.Expand) as defined in Figure 2 is a PCG for the correlation generator C F with key-length upper bounded by • O HSS .

Fig. 3 .

 3 Fig. 3. PCG for subfield vector-OLE

Fig. 5 .

 5 Fig. 5. PCG for Bilinear Correlations

  This captures, for example, Vector OLE (withG 1 = G T = F n and e : F n × F → F n by e(u, x) = xu), n-OLE (with G 1 = G 2 = G T = F n and e : F n × F n → F nby e(u, y) = u * v componentwise multiplication), and String OT and n-OT as special cases for F = F 2 . Definition 38 (Simple Bilinear Correlation: M -party). For simple bilinear 2-party correlation C 2 specified by e : G 1 × G 2 → G T we define the corresponding M -party correlation C M by

  a , b ) are computationally close. A symmetric requirement holds for b , b.

(

  The list given below was taken from [BCGI18]) -MDPC Codes. A more conservative variant of the above is to rely on MDPC codes (mediumdensity parity-check codes), where the parity-check matrix has row weight O( √ n) (instead of constant). MDPC codes have been thoroughly studied, since they are used in optimized variants of the famous McEliece cryptosystem [MTSB12]. -Quasi-Cyclic Codes. A second alternative option is to rely on quasi-cyclic codes, which admit fast (albeit superlinear) encoding algorithms. Quasi-cyclic codes have been recently used to construct optimized variants of the LPN-based cryptosystem of Alekhnovich and the codebased cryptosystem of McEliece [ABD + 16, MBD + 18]. -Druk-Ishai Codes. Another possibility is to rely on the linear-time encodable codes developped by Druk and Ishai in [DI14]

  where b 1 • • • b 5 correspond to the nb = 5 blocks of outputs involved in the parity check, homomorphically multiply their shares (getting multiplicative shares of g 5 i=1 b i t

E

  .4.6 Running Time and Communication of the Sanitization.

$

  ← R κ q , sk 1 := sk-sk 0 , m ∈ R p , and c $ ← Enc(pk, m) it holds DDec(sk 0 , c) + DDec(sk 1 , c) = m with overwhelming probability. -Depth-d somewhat homomorphic encryption: There exists a procedure PKE.Eval such that for any function f : R n → R m that can be evaluated by a circuit of depth at most d, for any λ ∈ N, for any (pk, sk) in the image of Gen(1 λ ), for all messages m 1 , . . . , m n ∈ R p , for all ciphertexts c 1 , . . . c n in the image of PKE.Enc(pk, m 1 ), . . . , PKE.Enc(pk, m n ) and for any c in the image of PKE.Eval(f, (c 1 , . . . , c n )) it holds PKE.Dec(sk, c) = f (m 1 , . . . , m n ).

  Fig. 9. PCG for the family of degree-d functions from degree-c D -PRG PRG and depthlog cd somewhat homomorphic encryption scheme PKE.

Table 1 .

 1 Summary of the New PCG Constructions

	PCG	Section 5 Section B Section 6 Section 4.4	Sections 7.3,C,D,E Sections 7.4,F
	Assumption	LPN	PRG *	LPN	deg-d HSS + MQ/LPN SXDH + LPN	LWE + MQ
	Correlations	OT *	OTTT *	deg-d	degree-d/2	small-ring deg-2	deg-d
	Efficiency	1M OT/s † -	-	-	5 OLE/s ‡	7000 ABT/s **
	Multiparty
	(bilinear corr.)

  [GI14], and can be constructed very efficiently based on a pseudorandom generator (PRG) [BGI16b]. There are HSS constructions for branching programs based on DDH [BGI16a] or lattices [BKS19], or general circuits from strong forms of fully homomorphic encryption [DHRW16].

Table 2 .

 2 Overview of estimated efficiency of lattice-based approach to generate authenticated Beaver triples. The numbers provided are time estimates for joint seed generation (with security against semi-honest adversaries) and expansion. The numbers are based on [CS16], for [BGV12] supporting depth-4 homomorphic operations (note that depth-3 would suffice) and plaintext space modulus p ≈ 2 128 . As underlying encryption scheme we consider [BGV12] with plaintext space Rp ∼ = Z N p and ciphertext space R 2 q

	Underlying HSS	|key| |triples|	setup	expansion exp./triple
	[BGV12]	3 GB 17 GB	≈ 20 s 8.0 h	0.16 ms
	[BGV12] (iterative)	3 GB 1.6 MB/it. ≈ 20 s 10 s/it.	0.57 ms
	[BGV12] (w/ packing) 6 MB 1.1 GB	< 0.1 s 900 h	280 ms
	[BGV12, BKS19]	3 GB 17 GB	≈ 20 s 7.6 h	0.15 ms

Table 3 .

 3 Communication complexity of silent OT for various parameter sets, all with n = 4n. Compression ratio is λn divided by the seed size in bits, with λ = 128.

	n	2 12	2 14	2 16	2 18	2 20		2 22	2 24
	t	39	34	32	31	30		29	28
	Seed size (kB)	5.65	6.02	6.69	7.97	8.67	9.31	9.89
	Comp. ratio	11.6	43.6	157	526	1930 7210 27150
	Base OT comms. (kB)	16.38 16.38 16.38 16.38 16.38 16.38 16.38
	Setup comms. (kB)	18.10 19.04 20.99 24.80 26.88 28.77 30.46
	Bits per OT (exc. base) 35.34 9.30	2.56	0.76	0.21	0.05	0.01
	n	2 12	2 14	2 16	2 18		2 20		2 22	2 24
	Quasi-cyclic	11.3	12.8	53.8	238		1113	5212	21090
	LDPC transpose	0.3	1.18	9.9	74.3	646		4460	47960
	MPFSS full eval	0.8	3.2	12.9	51.6	207		826	3300
	Total time (quasi-cyclic)	12.9	19.2	79.6	341		1527	6864	27690
	Total time (LDPC)	1.9	7.58	35.7	178		1060	6112	54560
	Throughput, QC (million/s)	0.32	0.85	0.82	0.77	0.69	0.61	0.60
	Throughput, LDPC (million/s)	2.16	2.16	1.84	1.47	0.99	0.69	0.31

Table 4 .

 4 Estimated

runtimes (ms) and throughput for n silent OTs. Based on (total time) ≈ 2× (MPFSS full eval) + (encoding time)

B One-Time Truth Table Generator

We define the authenticated, masked truth table correlation, C TT for a lookup table T : [n] → {0, 1} m as follows. C TT first samples MAC key shares α 0 , α 1 $ ← F 2 λ and a mask s $

Table 6 .

 6 Table 6 the seed size (in Megabytes) for generating n ROT correlations, for various values of n. Seed size for generating n ROT correlations. We consider a balanced version of the group-based PCG,

	n	2 17	2 19	2 21	2 23	2 25	2 27	2 29	2 31
	MNT Curve	0.16	0.30	0.59	1.16	2.31	3.76	7.50	15.0
	ROT/bit (MNT)	0.10	0.21	0.42	0.86	1.73	4.25	8.52	17.1
	Cocks-Pinck Curve	0.33	0.63	1.24	2.47	4.91	8.01	16.0	32.0
	ROT/bit (Cocks-Pinch)	0.05	0.10	0.20	0.41	0.81	2.00	4.00	8.00

Table 7 )

 7 . The estimated cost per ROT (in millisecond) of this step for both the MNT and the Cocks-Pinch curve, for various values of T , is represented on Table8.

	T	2 13	2 14	2 15	2 16	2 17	2 18
	MNT	1.4ms	2.7ms	5.5ms	10.9ms	21.8ms	43.7ms
	CP	0.6ms	1.3ms	2.6ms	5.1ms	10.2ms	20.4ms

Table 8 .

 8 Running time in milliseconds of the distributed discrete logarithm for various choices of T and an average size k 3 /4 of the exponent. The value B(T ) is chosen according to Table1 of [DKK18]. We choose the optimal value of k for each value of n according to Table5. The running time of exponentiations is taken from the benchmark of the Miracl library, ran on one core of a 2.4 GHz Intel i5 520M processor. MNT denotes a 160-bit MNT curve, and CP denotes a 512-bit Cocks-pinch curve.

Table 9 .

 9 Average running time per ROT (in milliseconds) of the entire Expand procedure, on one core of a 2.4 GHz Intel i5 520M processor, using the benchmark of the Miracl library. MNT denotes a 160-bit MNT curve, and CP denotes a 512-bit Cocks-pinch curve.E.3 Extension to OLE over Larger RingsOur optimized group-based PCG for OT correlations can be readily used to generate OLE correlations over larger (polynomial size) rings. Since the dominant cost in the seed size comes from the O( √ n) BGN ciphertexts, increasing the ring size (which means increasing the size of the encrypted plaintexts) does not significantly change the seed size.

	T	2 13	2 14	2 15	2 16	2 17	2 18
	MNT, α = 24	118.8ms	120.1ms	122.8ms	128.3ms	139.2ms	161.1ms
	MNT, α = 16	96.5ms	97.8ms	100.5ms	106ms	116.9ms	138.8ms
	CP, α = 24	84.8ms	86.1ms	88.8ms	94.3ms	99.4ms	109.6ms
	CP, α = 16	62.9ms	64.2ms	66.9ms	72.4ms	77.5ms	87.7ms

  Algorithm Puncture-Label Input. A complete binary tree T with n leaves (indexed by [n]), and a size-t subset S of [n]. We denote by s1 < s2 < • • • < st the indices of the leaves in S. Output. A labelling Lt of all nodes of T , such that all nodes of [n] \ S, and only them, belong to a subtree of T whose root belongs to Lt.

  16 , 2 26 ) (2 16 , 2 28 ) (2 17 , 2 28 ) (2 16 , 2 30 ) (2 17 , 2 30 ) (2 18 , 2 30 ) Table

	(T, n) (2 Punct. key size 2 21.5	2 22.4	2 20.7	2 23.9	2 22.4	2 20.7
	Runtime (est.)	187ms	160ms	148ms	154ms	144ms	151ms
	Comm. (bit/ROT) 3	2.6	2.2	2.5	2.2	2.0

This can be formalized by requiring that the joint states of the parties in the end of the offline phase can be swapped by computationally indistinguishable states, given which the online protocol is secure against computationally unbounded parties.

In Section 1.1.3 below we describe an alternative LPN-based approach to constructing PCG for OT that dispenses with assumption (2), but requires at least quadratic computation in the output length n.

We caution that we have not implemented our constructions. Our estimates are based on counting basic operations and estimating their cost; the actual running times may vary due to other costs we neglected such as cache misses. We leave the task of optimizing and implementing our constructions to future work.

FSS is actually equivalent to HSS for a related class of functions, but we differentiate between the two for convenience, depending on the applications.

We view elements of Fp embedded into Fq throughout, so that the multiplication u • x happens over Fq.

A "honest-but-deterministic" adversary has to behave according to the protocol, but is allowed to fix its random coins.

We say a HSS has overhead O HSS , if for every input the share size does not exceed O HSS times the input size.

In fact, assuming that dual-LPN has 2 O(t) security (which is in line with the best known attacks), t can be taken as small as ω(log λ), in which case the degree d(λ) of the polynomial can be larger, up to O(log λ/ log log λ). The shares are still of polynomial size Õ(t d ), although the computational cost O((n•n ) d ) is slightly superpolynomial.

We say that a NIZK has soundness parameter t if the probability for the prover to cause the verifier to accept a proof for an invalid statement is at most 2 -k .

In [Ds17], 2 log N OTs are needed, but in our case all the OTs in one direction can be avoided, since one party knows the secret point.

https://libraries.docs.miracl.com/miracl-explained/benchmarks

Denoting x and y the inputs of the parties, and Ni the ith line of the matrix N , notifying a party of a risk of failure for the output i leaks to this party the value (Nix) • (Niy) over the integers (with high probability). While (Nix) • (Niy) mod 2 is pseudorandom under LPN and leaks nothing about x, y, this is not the case for the product over the integer, and this leakage cannot be allowed in general.

Acknowledgements. We would like to thank Peter Rindal and Melissa Rossi for helpful discussions and pointers, and the anonymous Crypto 2019 reviewers for their comments. E. Boyle, N. Gilboa, and Y. Ishai supported by ERC Project NTSC (742754). E. Boyle additionally supported by ISF grant 1861/16 and AFOSR Award FA9550-17-1-0069. G. Couteau supported by ERC Project PREP-CRYPTO (724307). N. Gilboa additionally supported by ISF grant 1638/15 and a grant by the BGU Cyber Center. Y. Ishai additionally supported by ISF grant 1709/14, NSF-BSF grant 2015782, and a grant from the Ministry of Science and Technology, Israel and Department of Science and Technology, Government of India. L. Kohl supported by ERC Project PREP-CRYPTO (724307), by DFG grant HO 4534/2-2 and by a DAAD scholarship. This work was done in part while visiting the FACT Center at IDC Herzliya, Israel. P. Scholl supported by the European Union's Horizon 2020 research and innovation programme under grant agreement No 731583 (SODA), and the Danish Independent Research Council under Grant-ID DFF-6108-00169 (FoCC).

Appendix

A Details on Silent OT Extension

A.1 Application to Reusable NIZK From LPN We sketch in this section an application of the silent OT extension from subfield vector-OLE given in Section 5 to non-interactive zero-knowledge proofs in the preprocessing model. NIZK in the preprocessing model relaxes the standard NIZK definition by allowing the prover and the verifier to interact during a preprocessing phase, to generate respective proving key and verification key. It is well known that preprocessing NIZKs can be constructed from any oblivious transfer [KMO90, PsV06, IKOS07, GIK + 15]; in fact, these works even imply the existence of information-theoretic preprocessing NIZKs in the OT-hybrid model. However, in all these protocols, the computation and communication of the preprocessing grow with the size (and the number) of the theorems to be proven; in other words, the preprocessing implies an a-priori bound on the size and number of statements to be proven later.

A.1.1 Reusable Preprocessing NIZK from Silent OT

Plugging our random OT PCG given in Section 5 into the construction of preprocessing NIZK from OT, we readily obtain an improved preprocessing NIZK: following a one-time preprocessing phase whose communication and computation grow only with the soundness parameter 14 of the proofs to be sent in the online phase. After this preprocessing phase, the prover and the verifier can locally, without further interaction, extend the preprocessed material into an arbitrary polynomial number of (pseudo)random OTs, leading to a preprocessing NIZK with preprocessing cost independent of the size and number of theorems to be proven. In other word, the same preprocessing material can be reused for an a-priori arbitrary number of proofs. (Adaptive, multi-theorem) zero-knowledge and (adaptive, reusable) soundness readily follow from the security properties of the silent OT extension, and soundness holds even if the prover is allowed to get the answer of the verifier for an arbitrary polynomial number of proofs before trying to prove a false statement.

Using our construction of silent OT extension from LPN and correlation-robust assumption, this readily implies the existence of a reusable preprocessing NIZK from the same assumptions. Compared to the recent reusable preprocessing NIZK of [BCGI18], our preprocessing NIZK has two advantages:

-It only requires the standard LPN assumption over F 2 (together with correlation-robust hash functions), while the NIZK of [BCGI18] must rely on a generalization of LPN to exponentially large fields; -The preprocessing phase is independent of both the number of theorems to be proven, and the size of these theorems. In comparison the preprocessing phase in [BCGI18] is independent of the number of theorems to be proven, but grows linearly with a bound on the size of each statement.

A.1.2 Removing the Correlation-Robust Hash Functions

Our silent OT extension of Section 5 relies on a correlation-robust hash function. Intuitively, this comes from the use of the classical IKNP strategy for OT extension [IKNP03]: to generate m random OTs of strings of length , the sender and the receiver exchange their roles and perform As (z 0 , z 1 ) is sampled from D (R)×D (R), the relaxed correctness property of the CHSS applies, and we get:

C.5.2 Security.

Let A be a (stateful, nonuniform) PPT adversary, and let σ be a bit. We proceed through a sequence of game.

-Game G 0 . In this game, we run (pp, sk)

This corresponds to the first experiment in the security definition of bilinear correlation generators. Let b 0 be the output of A(x σ , k 1-σ ). -Game G 1 . In this game, we modify the execution of BCG.Gen as follows: instead of computing (s 0 , s 1 ) ← HSS.Share(sk, (z 0 , z 1 )), we set (s 0 , s 1 ) ← HSS.Share(sk, 0 2 ). Let b 1 denote the output of A in this game. By the security property of the CHSS, the distribution of (ek, s 1-σ ) in this game is computationally indistinguishable from the distribution of (ek,

In this game, we modify the execution of BCG.Expand as follows: instead of computing x σ as N z σ , we pick x σ $ ← R n . Note that k 1-σ does not depend on z σ , hence distinguishing between the games G 2 and G 1 amounts to distinguishing N z σ from a random vector over R n , where z σ is drawn from D (R). Note also that N z σ = N (M a + z σ ) for any vector a ∈ R n (as N M = 0). Therefore, this amounts to distinguishing M a + z σ from random, for an arbitrary secret vector a ∈ R n , and a noise vector z σ sampled from D (R), which is infeasible under the (D(R), C) -LPN( , -n) assumption. Therefore, denoting b 2 the output of A in G 2 , we have

-Game G 3 . In this game, we revert the change made in G 1 and compute again (s 0 , s 1 ) as HSS.Share(sk, (z 0 , z 1 )). Let b 3 denote the output of A in this game. By the security property of the CHSS, we have Pr[b 2 = b 3 ] = negl(λ). Furthermore, this game is exactly the second experiment in the security definition of a BCG, which concludes the proof.

C.5.3 Efficiency.

The seed size of the BCG is Given a compressible Las Vegas HSS, one immediately gets a sanitizable BCG under the LPN assumption, using the above construction. The security analysis of the construction is almost identical, with the failure probability of Las Vegas HSS translating directly to the failure probability of BCG outputs. Note that the standard formulation of Las Vegas HSS considers a global

The Convert algorithm works as follows. Each party, on input h ∈ G, outputs i mod t, with i the minimal integer i ≥ 0 such that h • g i is "distinguished," where roughly a δ-fraction of the group elements are distinguished. Distinguished elements were picked in [BGI16a] by applying a pseudo-random function to the description of the group element. An optimized conversion procedure from [BGI17, BCG + 17] applies the heuristic of defining a group element to be distinguished if its bit-representation starts with a 1 followed by d ≈ log 2 (M/δ) leading 0's. Note that this heuristic only affects the running time and not security, and thus it can be validated empirically. Correctness of Convert holds if no group element between the two shares {z} ∈ G 2 is distinguished. Finally, Convert signals that there is a potential failure if there is a distinguished point in the "danger zone." Namely, Party b = 0 (resp., b = 1) raises a potential error flag if

The Convert algorithm requires an upper bound M on the multiplicatively shared exponent, and runs in time proportional to M . Concretely, this means that we only consider inputs coming from a set Z t where t is polynomial, so that the product between any two (linear combination of) inputs is polynomially bounded. Note that all operations are performed over Z q , where q is an exponentially large prime; as all inputs are lower than t, which is polynomial, no modular reduction ever occurs, hence the computation of i is performed over the integers; therefore, the parties obtain additive shares of the product over Z t after the final (local) reduction of i modulo t. We refer the reader to [BCG + 17] for a detailed analysis and further optimizations of the Convert procedure.

Given the Pair and Convert algorithms, the multiplication algorithm Mult sequentially executes these two operations: Mult( x c , ⟪y⟫ c , δ) → xy , with error δ. Note that the output of the procedure is not a level 1 or a level 2 encoding. Therefore, this δ-failure HSS allows to evaluate arbitrary bilinear functions B on vectors (x, y) (encodings of level 1 and 2, as well as additive shares, being additively homomorphic) but does not generalize immediately to functions of higher degree; generalizations to branching programs are presented in [BGI16a,BGI17,BCG + 17], but are several orders of magnitude less efficient.

C.6.3 Improved Conversion.

In a recent paper [DKK18], Dinur et al. designed an improved distributed discrete logarithm procedure. Their elegant algorithm is based on a clever random walk with steps of varying length, that bears some resemblance with Pollard's kangaroo method (but requires a considerably more complex and mathematically involved analysis). The improved algorithm requires T multiplications to achieve a failure probability of O(M/T 2 ), where the constant hidden in the O(•) notation is always upper bounded by 2 10.2 , and in practice approximately equal to 400 (the authors provide a table with optimal parameters for various choices of T , that gives the exact constant), improving over the O(M/T ) failure probability of the previous method. Their paper also proves the optimality of this algorithm. In this work, we will rely on their improved conversion algorithm, and refer the reader to [DKK18] for further details on this procedure.

C.7 The BGN-EG Cryptosystem

The Boneh-Goh-Nissim cryptosystem (BGN) was introduced in [BGN05]. It is a variant of the ElGamal cryptosystem over composite-order pairing-friendly elliptic curve, which allows to homomorphically compute any degree-2 polynomial on encrypted plaintexts, provided that the output is of polynomial size (as decryption requires computing a discrete logarithm). An adaptation of BGN to prime-order pairing-friendly elliptic curves was introduced by Freeman in [Fre10]. As it suffices for our purpose, we will rely in this work on a simplified variant of Freeman's cryptosystem, where encryption in any of the pairing-friendly groups will exactly be ElGamal encryption, and where ciphertexts obtained through homomorphic operations are not rerandomized.

C.8.4 Putting the Pieces Together.

Combining the above techniques, we get

Theorem 48. Assuming the DDH assumption over pairing-friendly elliptic curves, for any integer t of polynomial size and any integer k, there exists a (Ber k/ (Z t ), comp(λ, , k))-compressible (Las Vegas, secret-key, degree-2) CHSS, with

For self-containement, we describe below the full CHSS. It has two sharing algorithms, corresponding to level 1 and level 2 shares respectively. The evaluation procedure allows to compute (shares of) any bilinear function B(x, y) where x is level-1-shared and y is level-2-shares between the parties.

-HSS.Gen(1 λ ):

Output ek ← (pp, pk, g) and sk.

-HSS.Share 1 (sk, m): let k denote an upper bound on the sparsity of m, and let denote the length of m.

-HSS.Share 2 (sk, m): let k denote an upper bound on the sparsity of m, and let denote the length of m. Parse sk as (sk 1 , sk 2 , sk t ) and parse sk i as (s i , -1)

, where proj is defined as in Section C.8.3. Compute

Return share 0 ← K 0 and share 1 ← K 1 . -HSS.Eval(σ, ek, share σ , share σ , B, δ): On input party index σ ∈ {0, 1}, evaluation key ek, level 1 share share σ of a size-input, level 2 share share σ of a size-input, a bilinear function B : Z t × Z t → Z m t with B(x, y) = ( i,j b i,j,θ • x i y j ) θ≤m , and failure probability bound δ > 0:

Plugging the above HSS in our LPN-based construction of BCG from compressible HSS, we get:

Theorem 49. Assuming the DDH assumption over pairing-friendly elliptic curves and the LPN((α -1) • n, α • n, k/(αn)) assumption over an integer ring Z t of polynomial size, for a positive constant α > 1, there exists a δ-failure SBCG with seed size k

D Optimizing the Group-Based PCG

While the compressible HSS described in Section C leads to a (sanitizable) PCG for bilinear correlations under the LPN assumption, a direct instantiation from the above group-based CHSS and LPN would remain computationally heavy. Below, we outline several optimizations to reduce the cost of group-based PCG, which significantly reduce the computation and size of the PCG seeds.

modifying the noise distribution, to adapt it to the constraints of the application.

Below, we analyze both types of modifications of the LPN assumption, showing how using variants of LPN (some well-established, some less standard) leads to improved efficiency guarantees for the group-based BCG.

D.2 Optimizing the Noise Distribution

In this section, we discuss alternative choice of distributions from which to sample the noise vector, which are better suited for the encoding algorithms of the group-based BCG.

D.2.1 Regular Syndrome Decoding.

The regular syndrome decoding assumption is a variant of the LPN assumption which was introduced in [AFS03] as the assumption underlying the security of a candidate for the SHA-3 competition, and has been studied at length (see [HOSS18] for a recent survey about the cryptanalysis of the RSD assumption and a detailed discussion about its security). Roughly, it states that LPN remains hard, even if the sparse noise vector is regular, meaning that it is divided into k blocks of size n/k each, each block containing a single random 1, and zeroes everywhere else.

It was shown in [BCGI18] that the RSD can be used to improve the computational effiency of the FSS-based encoding compression method (which correspond to our level-2 encodings): with the LPN-based instantiation, the cost of MPFSS.FullEval is equal to k times the cost of the FullEval algorithm of an FSS for point functions, over a domain of size n. The RSD-based instantiation reduces this cost to k times the cost of the FullEval algorithm of an FSS for point functions, over a domain of size n/k. We refer the reader to [BCGI18] for further details.

Here, we observe that RSD can also be used to reduce the size of a level-1 encoding. Given the block structure of the noise pattern, one can simply apply the compression procedure of Section C.8 separately to each of the k blocks. As each block has length n/k and contains a single 1, its encoding has size 2 n/k. Therefore, the total size of the encoding is k

D.2.2 Learning Parity with Tensored Noise.

We now describe a more agressive choice of pattern, which leads to even better efficiency. Note that unlike LPN or RSD, the assumption that we introduce in this paragraph, although natural, is new. While we will analyze its resistance to standard attacks, further cryptanalysis is required to gain confidence in its security. We stress, however, that our assumption as strong connections to (an can be seen as a natural strenghtening of) well-studied assumptions from the literature; hence, it appears very plausible.

We focus on compressing level 1 shares in group-based HSS, since they form the bottleneck of our scheme. Let ⊗ denote the tensor product between vectors -that is, for length-n vectors a = (a i ) i , b = (b i ) i , a ⊗ b denotes the length-n 2 vector with coordinates a i b j . We suggest the following family of distributions for integers k, n (we assume n to be a perfect square for simplicity): A pPRF can be constructed from any length-doubling pseudorandom generator, using the celebrated GGM construction [GGM86]. It proceeds as follows: On input a key K and a point x, set K (0) ← K and perform the following iterative evaluation procedure: for i = 1 to ← log |x|, compute (K

x i . Output K ( ) . This procedure creates a complete binary tree with edges labeled by keys; the output of the PRF on an input x is the key labeling the leaf at the end of the path defined by x from the root of the tree.

-F.KeyGen(1 λ ) : output a random seed for G.

-F.Puncture(K, z) : on input a key K ∈ {0, 1} k and a point x, apply the above procedure and return K{x} = (K

(1)

Otherwise, parse K{x} as (K

(1)

) and start the iterative evaluation procedure from the first

To obtain a t-puncturable PRF with input domain [n], one can simply run t instances of the above puncturable PRF and set the output of the PRF to be the bitwise xor of the output of each instance. With this construction, the length of a key punctured at t points is tλ log n, where λ is the seed size of the PRG. However, in the context of using a pPRF to design a punctured OT, we observe that we can do better. Intuitively, to obtain a t-puncturable PRF out of the GGM PRF, it suffices to define a key punctured at a subset S of leaves to be the smallest set of intermediate PRG values that allows to reconstruct all leaf values indexed by [n] \ S, and does not allow to reconstruct the leaf values indexed by S. We represent on Figure 8 a labelling algorithm which finds the indices of such a subset of the keys. The correctness of the algorithm follows easily by inspection; with a little more effort, one can also show that this algorithm is optimal (i.e., it produces the smallest possible punctured key satisfying the constraints). The worst-case scenario is easily seen to happen when all the punctured leaves are regularly spaces, with a distance of n/t between every two punctured leaves. This observation allows to upper bound the length of a key punctured at t points by tλ log(n/t), improving over the cost tλ log n of the naive approach.

E.4.2 Punctured OT.

A t-out-of-n oblivious transfer (OT) protocol involves a sender, with a database D = (d 1 , . . . , d n ), and a receiver holding a subset S ⊂ [n] of size |S| = t. The receiver should learn all entries (d i ) i∈S , without learning the entries indexed by [n] \ S, while the sender should not learn which entries the receiver got. Standard t-out-of-n OT protocols involve O(λ • (t + n)) bits of communication. In [BGI17], the authors observed that when t is very close to n (n -t = o(n)), this primitive can be implemented more efficiently, using only n + o(n) bits of communication. We outline the construction below; it relies on a general two-party computation protocol (modeled as an oracle Π, which can be implemented with a trusted setup or any standard protocol, such as Yao's protocol) and a t-puncturable PRF F with domain [n].

PCG.Gen(1 λ ) :

-Generate the encryption keys. Generate keys (pk, sk) ← PKE.Gen(1 λ ). Choose sk0 $ ← R κ q and set sk1 := sk -sk0.

-Generate a share of the MAC key. Choose α $ ← Zp, define α ∈ Z N p to be the vector of all α entries. Choose s0 $ ← R κ q and compute s1 := Ψ (α) • sk -s0.

-Choose and encrypt a PRG-seeds. Choose ra, r b ← R p . Compute and output

-Output k0 := (sk0, s0, c ra , c r b ), k1 := (sk1, s1, c ra , c r b ).

PCG.Expand(σ, k σ , f ) :

-Parse kσ =: (skσ, sσ, c ra , c r b ).

-Evaluate PRG homomorphically on the encrypted seed. Compute

-Evaluate Fα homomorphically on the encrypted input. Compute

-Obtain shares of Y via distributed decryption with skσ . Compute

-Obtain the output shares over Zp. Output Proof. We analyze the following M -party PCG construction:

, 1} λ as specified by programmability property.

For every

1. For every j = i, compute

where [i < j] = 1 if i < j and 0 if j < i.

Correctness:

By assumption, each expanded output from (PCG 2 .Gen, PCG 2 .Expand) is computationally indistinguishable from C 2 . In particular, it must hold whp for all i = j: e(A i , B

. This means with overwhelming probability,

(Note that for all i = j, r ij is added and subtracted exactly once in the sum.) Further, by indistinguishability of the expanded outputs from PCG 2 .Expand to the target correlation C 2 , it holds that each (a i , b j ) pair is pseudorandom. Thus, for M independent samples, a i and b i are jointly pseudorandom. Finally, from the pairwise pseudorandom offsets r ij (independent of the a i and b i ), it holds that the C i are pseudorandom, up to the required constraint. Correctness follows.

Security. We now proceed to prove security of PCG M . Let T ⊂ [M ] corrupted. We wish to show that given {k i } i∈T , the expanded outputs of honest parties

∈T cannot be distinguished from an independent resampling, conditioned on the expanded values (A i , B i , C i ) i∈T of the corrupt seeds.

We first observe that due to the pariwise secret pseudorandom offsets r ij = PRG(s ij ), that even given {k i } i∈T and (A i , B i ) i∈T the joint distribution of (C i ) i / ∈T is indistinguishable from random, up to the preserved sum i / ∈T C i as required. It thus remains to show that given {k i } i∈T , the expanded honest values (A i , B i ) i / ∈T are pseudorandom. By a hybrid argument, we may replace the values of honest A i and B i one at a time. It then suffices to adress an extreme case of this step, where all but one party i ∈ [M ] is corrupted.

We first treat A i ; the argument for B i is symmetric. For any i ∈

where RestOfSeeds is an efficiently sampleable distribution that samples b i ← $, a j ← $ ∀j = i, executes the remaining (2M -1)(M -1) instances of PCG 2 .Gen(1 λ , a , b j ) and outputs

By a direct sequence of (M -1) hybrids over j = i ∈ [M ] we may appeal to the security of (PCG 2 .Gen, PCG 2 .Expand) to iteratively replace the jth key k ij 1 generated by

We thus obtain the above distribution is indistinguishable from

However, in this case A i = f a (a i ) for a i ← $ is completely independent of { kij 1 } j =i , X , generated now as a function in only ãi (not a i ). The claim, and thus security of the construction, follows.

We now explore sample 2-party PCG constructions that support the necessary programmability.

Proposition 59 (Programmability of 2-party PCGs). The following 2-party PCGs are programmable, as per Definition 40.

-The 2-party VOLE generator of [BCGI18], based on DPF and LPN.

-The PCGs for arbitrary simple 2-party bilinear correlations as constructed in this work from somewhat-homomorphic encryption or BGN.

Proof. M -party VOLE. Recall the 2-party VOLE generator of [BCGI18] takes the following form (we describe their "dual" construction). The sender party receives a (short representation of) a sparse random vector y over the field F, the receiver receives a field element x ∈ F, and each receives an FSS share of a multi-point function corresponding to the product xy. The scheme is parameterized by a public matrix H for which the dual-LPN problem is hard (with respect to sparse noise). The sender expands to output (u, v), and the receiver to (x, w). It was already observed in [BCGI18] that the construction was programmable with respect to the receiver's output x. We observe that a similar programmability holds also for the output u of the sender, where in particular u is the output of compressing the value y via the public matrix H. In both cases, the "programming information" (a = u and b = x) is anyway given to the respective party, so the required security notion is directly implied by standard PCG security.

General Simple Bilinear via HSS. One can support 2-party PCG of any simple bilinear correlation via our PCGs for degree-2 correlations (e.g., obtained from lattices and BGN) by giving each party a short seed a , b , respectively, as well as HSS shares of a and b that support homomorphic evaluation of individual PRG expansion a = PRG(a ), b = PRG(b ) and then the multiplication ab. This construction inherently supports programmability, by the initial values a , b .