Elette Boyle

Geoffroy Couteau

Niv Gilboa

Yuval Ishai

Lisa Kohl

Peter Rindal

Peter Scholl

Efficient Two-Round OT Extension and Silent Non-Interactive Secure Computation

We consider the problem of securely generating useful instances of two-party correlations, such as many independent copies of a random oblivious transfer (OT) correlation, using a small amount of communication. This problem is motivated by the goal of secure computation with silent preprocessing, where a low-communication input-independent setup, followed by local ("silent") computation, enables a lightweight "non-cryptographic" online phase once the inputs are known. Recent works of Boyle et al. (CCS 2018, Crypto 2019) achieve this goal with good concrete efficiency for useful kinds of two-party correlations, including OT correlations, under different variants of the Learning Parity with Noise (LPN) assumption, and using a small number of "base" oblivious transfers. The protocols of Boyle et al. have several limitations. First, they require a large number of communication rounds. Second, they are only secure against semi-honest parties. Finally, their concrete efficiency estimates are not backed by an actual implementation. In this work we address these limitations, making three main contributions: -Eliminating interaction. Under the same assumption, we obtain the first concretely efficient 2-round protocols for generating useful correlations, including OT correlations, in the semihonest security model. This implies the first efficient 2-round OT extension protocol of any kind and, more generally, protocols for non-interactive secure computation (NISC) that are concretely efficient and have the silent preprocessing feature. -Malicious security. We provide security against malicious parties (in the random oracle model) without additional interaction and with only a modest concrete overhead; prior to our work, no similar protocols were known with any number of rounds. -Implementation. Finally, we implemented, optimized, and benchmarked our 2-round OT extension protocol, demonstrating that it offers a more attractive alternative to the OT extension protocol of Ishai et al. (Crypto 2003) in many realistic settings.

Introduction

There is a large body of work on optimizing the concrete efficiency of secure computation protocols via input-independent preprocessing. By securely generating many instances of simple correlations, one can dramatically reduce the online communication and computation costs of most existing protocols.

To give just one example, multiple independent instances of a random oblivious transfer8 (OT) correlation can be used for secure two-party computation of Boolean circuits in the semihonest model, with communication cost of only two bits per party per (nonlinear) gate, and with computation cost that is comparable to computing the circuit with no security requirements at all [GMW87, Kil88,Bea91]. Thus, assuming a fast communication network, protocols based on correlated randomness can achieve near-optimal performance.

The main challenge in applying this approach is the high concrete cost of securely generating the correlated randomness. Traditional solutions involve carefully optimized special-purpose secure computation protocols that have a high communication cost for each instance of the desired correlation [BDOZ11,DPSZ12]. This holds even for the case of OT correlations, for which relatively fast OT extension techniques are known [IKNP03,ALSZ13,KOS15]. Moreover, even if offline communication is cheap, the cost of storing large amounts of correlated randomness for each party with whom a future interaction might take place can be significant.

Motivated by the limitations of traditional approaches for generating and storing correlated randomness, the notion of a pseudorandom correlation generator (PCG) was recently proposed and studied by Boyle et al. [BCGI18,BCG + 19]. The goal of a PCG is to compress long sources of correlated randomness without violating security. More concretely, a (two-party) PCG replaces a target two-party correlation, say many independent OT correlation instances, by a pair of short correlated keys, which can be "silently" expanded without any interaction. The process of generating the correlated keys and locally expanding them 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 one of the two keys. Among other results, the aforementioned works of Boyle et al. [BCGI18,BCG + 19] obtain concretely efficient constructions of PCGs for OT correlations and vector oblivious linear evaluation (VOLE) correlations [NP06, IPS09,ADI + 17] based on variants of the Learning Parity with Noise assumption [BFKL93]. These PCG constructions are motivated by the goal of secure computation with silent preprocessing, where a low-communication input-independent setup, followed by local ("silent") computation, enables a lightweight "non-cryptographic" online phase once the inputs are known.

However, towards realizing this goal, one major challenge remains: how can the pair of keys be securely generated? While the keys are short, their sampling algorithm is quite complex and involves multiple invocations of cryptographic primitives. Thus, even applying the fastest general-purpose protocols for generating these keys (e.g., optimized protocols based on garbled circuits [KRRW18]) incurs a very significant overhead.

An alternative approach for distributing the PCG key generation, suggested in [BCGI18, BCG + 19], relies on a recent special-purpose protocol of Doerner and shelat [Ds17] for secure key generation of a distributed point function (DPF) [GI14,BGI16]. This protocol only makes a black-box use of symmetric cryptography and a small number of oblivious transfers, and hence it is also concretely efficient. Using this protocol for distributing the key generation of a PCG for OT correlations, Boyle et al. [BCG + 19] obtained a silent OT extension protocol that generates (without any trusted setup) a large number of pseudo-random OTs from a small number of base OTs, using a low-communication setup followed by silent key expansion [BCG + 19].

While the silent OT extension protocol from [BCG + 19] and other protocols obtained using this approach have good concrete efficiency, they also have several limitations. First, they require a large number of communication rounds that grows (at least) logarithmically with the output length. Second, they are only secure against semi-honest parties. Both of the above limitations are inherited from the DPF key generation protocol of [Ds17]. Finally, their concrete efficiency estimates are not backed by an actual implementation, and ignore possible cache-misses and other system-and network-related sources of slowdown.

Our Contribution

In this work, we address the above limitations by making the following contributions.

Two-Round Silent OT Extension. We present the first concretely efficient two-round OT extension protocol, based on a variant of the LPN assumption. The protocol has a silent preprocessing feature, allowing the parties to push the bulk of the computational work to an offline phase. It can be used in two modes: either a random-input mode, where the communication complexity is sublinear in the output length, or a chosen-input mode, where the communication is roughly equal to the total input length. This applies even to the more challenging case of 1-bit OT, for which standard OT extension techniques that make a black-box use of symmetric cryptography [IKNP03, ALSZ13, KK13, KOS15] have a high communication overhead compared to the input length. A key idea that underlies this improvement is replacing the DPF primitive in the PCG for OT from [BCG + 19] by the simpler puncturable pseudorandom function (PPRF) primitive [KPTZ13,BW13,BGI14]. We design a parallel version of the distributed key generation protocol from [Ds17] that applies to a PPRF instead of a DPF.

Our OT extension protocol bypasses a recent impossibility result of Garg et al. [GMMM18] on 2-round OT extension due to the use of the LPN assumption. While our construction (inevitably) does not fall into the standard black-box framework considered in [GMMM18], it still has a blackbox flavor in that it only invokes a syndrome computation of any error-correcting code for which the LPN assumption holds. We remark that aside from its concrete efficiency, our 2-round OT extension protocol can be based on a conservative variant of (binary) LPN in a noise regime that is not known to imply public-key encryption, let alone oblivious transfer. Concretely, it can be instantiated by binary LPN in which the Hamming weight of the noise is higher than the n 1/2 bound required by the construction of Alekhnovich [Ale03] and its variants.

The technique we use for generating OT correlations in two rounds can also be applied to VOLE correlations, as well as general protocols for non-interactive secure computation (NISC) with silent preprocessing.

Malicious Security. We present simple, practical techniques for secure distributed setup of PPRF keys with a weak form of malicious security. This suffices to upgrade our semi-honest OT and VOLE protocols to malicious security, at a very low cost. Our main protocols in this setting have 4 rounds of interaction, but this can be reduced to 2 rounds using the Fiat-Shamir transform. We can also use this to obtain maliciously secure silent NISC or two-round OT extension on chosen inputs. These protocols are based on slightly stronger variants of LPN, where the adversary is allowed a single query to a one-bit leakage function on the error vector.

Implementation. We demonstrate the efficiency of our constructions with an implementation of our random OT extension protocol. The most costly part of the implementation is a large matrix-vector multiplication, which comes from applying the LPN assumption. We optimize this using a variant of LPN with quasi-cyclic codes, similarly to several recent, candidate postquantum secure cryptosystems [ABB + 19, MBD + 18, AMAB + 19], and present different tradeoffs with parameter choices. Our protocols have a very low communication overhead and perform significantly faster than previous, state-of-the-art protocols [IKNP03, ALSZ13, KOS15] in environments with restricted bandwidth. For instance, in a 100Mbps WAN setting, we are around 5x faster, and this improves to 47x in a 10MBps WAN. This is because, while our computational costs are around an order of magnitude higher, we need around 1000-2000 times less communication than the other protocols. We expect that additional optimizations of our implementation and the underlying error-correcting code will further improve the computational cost.

Applications. As well as the new application to NISC with silent preprocessing, our protocols can be applied to a range of traditional secure computation tasks. Below we mention just a few areas where we expect silent OT extension and VOLE to have an impact.

-Semi-honest MPC for binary circuits. In the semi-honest "GMW protocol" [GMW87], the correlated randomness needed to evaluate a Boolean circuit can be obtained from two random OTs per AND gate. Plugging in our random OT extension, we obtain a practical 2-PC protocol where each party communicates just 2 bits per AND gate on average. This is around 30x less communication than the state-of-the-art [DKS + 17]. -Malicious MPC for binary circuits. Protocols based on authenticated garbling [WRK17a,WRK17b] and BMR [HSS17] are currently the state-of-the-art in maliciously secure MPC for binary circuits in a high-latency network. The main cost in these protocols comes from a preprocessing phase, where the parties use a large number of random, correlated oblivious transfers to produce correlated randomness. Our protocol can produce the same kind of oblivious transfers with almost zero communication, and we estimate this could reduce the overall communication in these protocols by around an order of magnitude. -Malicious MPC for arithmetic circuits. The "SPDZ" family of protocols [BDOZ11, DPSZ12, DKL + 13, KOS16, KPR18] uses information-theoretic MACs to achieve malicious security in MPC based on secret sharing. A large batch of these MACs can be created using a single instance of a long, random VOLE correlation, with essentially optimal communication. Plugging in our maliciously secure VOLE construction will reduce the costs of previous works that use either homomorphic encryption or string-OT to create MACs. -Private set intersection (PSI). In circuit-based PSI, a generic 2-PC protocol is used to first compute a secret-sharing of the intersection of two sets, and then perform some useful computation on the result [HEK12,PSSZ15,PSTY19]. With the improvements to GMW mentioned above, we can expect to obtain a similar reduction in communication for these families of PSI protocols.

Concurrent Work. In recent, concurrent work, Schoppmann et al.

[SGRR19] presented optimizations and an implementation of the VOLE protocol by Boyle et al. [BCGI18]. Similarly to our work, they observe that the distributed setup procedure can be parallelized and performed in only two rounds, although they only apply this to VOLE correlations and not two-round OT extension. They also give a technique for efficient multi-point DPF evaluation, which allows batching t evaluations while avoiding the factor t overhead from a naive approach. This allows for an efficient implementation, without relying on the hardness of LPN for a regular error distribution as in our implementation. Finally, note that their protocols have semi-honest security, whilst we also give maliciously secure protocols with very low overhead.

Technical Overview

We now give an overview of our silent constructions in the semi-honest and malicious settings.

For simplicity, we focus here on the case of 1-out-of-2 oblivious transfer. We start by recalling the high-level idea of the pseudorandom correlation generators for vector-OLE (VOLE) and OT from [BCGI18, BCG + 19]. These constructions distribute a pair of seeds to a sender and a receiver, who can then locally expand the seeds to produce many instances of pseudorandom OT or VOLE. To do so, they use two main ingredients: a variant of the LPN assumption, and a method for the two parties to obtain a compressed form of random secret shares v 0 , v 1 , satisfying

v 1 = v 0 + e • x ∈ F N 2 λ (1)
where e ∈ {0, 1} N is a random, sparse vector held by one party, and x ∈ F 2 λ is a random field element held by the other party.

Given this, the shares can be randomized by taking a public, binary matrix H that compresses from N down to n < N elements, and locally multiplying each share with H. This works because u = e • H is pseudorandom under a suitable variant of LPN. Writing v = v 0 • H and w = v 1 • H, from (1) we then get w = v + ux. This can be seen as a set of random correlated OTs, where u i ∈ {0, 1} are the receiver's choice bits, and (v i , v i + x) are the sender's strings, of which the receiver learns w i . These can be locally converted into random string-OTs with a standard hashing technique [IKNP03].

To obtain a compressed form of the shares in (1), the constructions of [BCGI18, BCG + 19] used a distributed point function (DPF) [GI14, BGI16]. Our first observation is that DPF is an overkill for this application, 9 and can be replaced with the simpler puncturable pseudorandom function (PPRF) primitive. A PPRF is a PRF F such that given an input x, and a PRF key k, one can generate a punctured key k{x} which allows evaluating F at every point except for x, and does not conceal any information about the value F (k, x). A PPRF can be built from any length-doubling pseudorandom generator, using a binary tree-based construction [KPTZ13, BW13, BGI14].

In the setup procedure, we will give the sender a random key k and x, and give to the receiver a random point α ∈ {1, . . . , N }, a punctured key k{α}, and the value z = F (k, α) + x. Given these seeds, the sender and receiver can now define the expanded outputs, for i = 1, . . . , n:

v 0 [i] = F (k, i), v 1 [i] = F (k, i) i = α z otherwise
These immediately satisfy (1), with e as the α-th unit vector. To obtain sharings of sparse e with, say, t non-zero coordinates, as needed to use LPN, we repeat this t times and XOR together all t sets of outputs.

Conceptually, this construction is simpler than using a DPF, and moreover, as we now show, it brings several efficiency advantages.

Two-Round Setup of Puncturable PRF Keys. We present a simple, two-round protocol for distributed the above setup with semi-honest security, inspired by the DPF setup protocol of Doerner and shelat [Ds17]. The core of our protocol is the following procedure. For each of t secret LPN noise coordinates α j ∈ [N ] known to the receiver, the sender generates a fresh PRF key k j , and wishes to obliviously communicate a punctured key k j {α j } and hardcoded punctured output z j = P RF (k j , α) + x to the receiver. Combined, this yields a secret sharing of the vector x • e, as required. To do so, for each k{α}, the parties made use of = log N parallel OT executions: the sender's message pairs correspond to appropriate sums of partial evaluations from a consistent GGM PRF tree and his secret value x, and the receiver's selection bits correspond to the bits of his chosen path α.

Compared with previous works based on distributed point functions [BCGI18, BCG + 19, Ds17], the number of rounds of interaction collapses from O(log N ) to just two, given any tworound OT protocol. This is possible since the punctured point α is known to the receiver, whereas when α is secret-shared as in a DPF, the OTs in the setup procedure seem hard to parallelize. Two-Round OT Extension and Silent NISC. We observe that in the two-round setup, the receiver can already compute part of its output before sending the first round message. In the case of OT, this part corresponds to its random vector of choice bits u. This means that the receiver can already derandomize its OT outputs in the first round, by sending in parallel with its setup message the value u + c, where c is its chosen input vector. Since the sender can compute its random OT outputs after the first round, this leads to a two-round OT extension protocol that additionally enjoys the "silent preprocessing" feature of pushing the bulk of the computation to an offline phase, before the inputs are known. This can be generalized from OT to VOLE and other useful instances of non-interactive secure computation (NISC) [IKO + 11], simultaneously inheriting the silent preprocessing feature from the PCG and the minimal interaction feature from an underlying NISC protocol. See Section 3 for a more detailed discussion of our new notion of NISC with silent preprocessing.

Maliciously Secure Setup. In the above semi-honest setup procedure, a malicious receiver has no cheating space; altered selection bits merely correspond to a different choice of noise coordinate α ∈ [N ]. However, a malicious sender may generate message pairs inconsistent with any correct PRF evaluation tree, or use inconsistent inputs x across the t executions (in which case the outputs are not valid shares of x • u for any single x). For example, by injecting errors into one of the two messages within an OT message pair, the sender can effectively "guess" and learn a bit of α, and will go unnoticed if his guess is correct.

We demonstrate that with small overhead, we can restrict a malicious sender to only such selective-failure attacks. This is formalized via an ideal functionality where the adversarial sender can send a guess range I ⊆ [N ] for α, a "getting caught" predicate is tested as a function of the receiver's true input, and the functionality either aborts or delivers the output accordingly. We then show that paired with an interactive leakage notion for LPN, this suffices to give us PCG setup protocols for VOLE and OT with malicious security.

Our basic maliciously secure protocols have 4 rounds, but this can be compressed to two rounds with the Fiat-Shamir transform, in the random oracle model. Just as in the semi-honest protocols, we can convert the setup protocols into NISC protocols, this time under a slightly stronger variant of LPN with one bit of adaptive leakage on the error vector. This leads to efficient two-round OT extension and VOLE protocols with malicious security.

Preliminaries

Puncturable Pseudorandom Function

Pseudorandom functions (PRF) are keyed functions which are indistinguishable from truly random functions, have been introduced in [GGM86]. A puncturable pseudorandom function (PPRF) is a PRF F such that given an input x, and a PRF key k, one can generate a punctured key, denoted k{x}, which allows evaluating F at every point except for x, and does not conceal any information about the value of F at x. PPRFs have been introduced in [KPTZ13,BW13,BGI14].

Definition 1 (t-Puncturable Pseudorandom Function). A puncturable pseudorandom function (PPRF) 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, S), on input a key 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 1 with non-negligible advantage over the random guess. By F.FullEval(K) we denote the algorithm that on input a key K ∈ K evaluates F on all inputs X and returns the vector of outputs. A PPRF can be constructed from any length-doubling pseudorandom generator, using the GGM tree-based construction [GGM86, KPTZ13, BW13, BGI14]. The construction 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

(i) 0 , K (i)
1 ) ← G(K (i-1) ), and set

K (i) ← K (i)
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)

1-x 1 , . . . , K ( ) 1-x ).
-F.Eval(K{x}, x ), on input a punctured key K{x} and a point x, if x = x , output ⊥.

Otherwise, parse K{x} as (K

(1)

1-x 1 , . . . , K ( ) 1-x ) and start the iterative evaluation procedure from the first

K (i) 1-x i such that x i = 1 -x i .
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.

Learning Parity with Noise

In this work, we rely on variants of the Learning Parity with Noise (LPN) assumption [BFKL93] over either F 2 or a large finite field F, where the noise is assumed to have a small, fixed Hamming weight. In particular, our constructions use the dual form10 of decisional LPN, defined below, where for efficiency reasons we choose the matrix from a family of codes that supports (nearly) linear-time matrix-vector multiplication.

In the following we define the LPN and dual-LPN assumptions over a general finite ring R with error distribution D(R). For the case of OT we will let R = F 2 , and for the case of VOLE R will typically be a big finite field. 11Definition 2 (LPN). Let D(R) = {D k,N (R)} k,N ∈N denote a family of distributions over a ring R, such that for any k, N ∈ N, Im(D k,N (R)) ⊆ R N . Let C be a probabilistic code generation algorithm such that C(k, N, R) outputs a matrix A ∈ R k×N . For dimension k = k(λ), number of samples (or block length) N = N (λ), and ring R = R(λ), the (D, C, R)-LPN(k, N ) assumption states that

{(A, b) | A $ ← C(k, N, R), e $ ← D k,N (R), s $ ← F k , b ← s • A + e} c ≈ {(A, b) | A $ ← C(k, N, R), b $ ← R N }
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 N 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.

LPN with Fixed Weight and Regular Noise. For a finite field F, let HW t (F) be the distribution of uniform, weight t vectors over F N ; that is, a sample from HW t (F) is a uniformly random non-zero field element in t random positions, and zero elsewhere. The corresponding assumption used in our constructions is denoted by (HW t (F), C, F)-LPN(k, N ).

To increase efficiency in our constructions, we also consider a regular noise distribution. This is as in the fixed weight case, except the noise vector in F n is divided into t consecutive sub-vectors of length n/t , where each sub-vector has a single noisy coordinate.

If the block length N and noise weight t are such that k random coordinates will be all noiseless with non-negligible probability (e.g., when t is constant and N = Ω(k 2 )), these structured variants can be broken via Gaussian elimination (cf. [AG11]). This attack does not apply to our constructions, which always have N = O(k).

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

C ⊥ (N, n, R) = {H ∈ R N ×n : A • H = 0, A ∈ C(N -n, N, R), rank(H) = 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 }
We will slightly abuse our notations by omitting to explicitely mention the code C and writing (D, H, R)-dual-LPN(N, n) for above dual-LPN assumption with a matrix H ∈ C ⊥ (N, n, R).

The search version of the dual LPN problem is also known as syndrome decoding. For any fixed family of codes C and error distribution D, the decisional version defined above is equivalent to the primal variant of LPN from Definition 2 with dimension k = N -n and N samples. One direction (transforming an LPN instance into dual-LPN) follows from the simple fact that when H is the parity-check matrix of the code generated by A, we have

(s•A+e)•H = s•A•H +e•H = e • H.
The reverse direction can be shown similarly to, e.g. [MM11, Lemma 4.9].

Attacks on LPN.

We recall here the main attacks on LPN, following the analysis of [BCGI18]. We refer the reader to [EKM17] for a more comprehensive overview. We assume that D is a noise distribution with Hamming weight bounded by some integer t.

-Gaussian elimination. The most natural attack on LPN recovers s from b = s • A + e by guessing n non-noisy coordinates of b, and inverting the corresponding subsystem to verify whether the guess was correct. This approach recovers s in time at least (1/(1 -r)) n using at least O(n/r) samples (r = t/N ). For low-noise LPN, with noise rate 1/n c for some constant c ≥ 1/2, this translates to a bound on attacks of O(e n 1-c ) time using O(n 1+c ) samples. -Information Set Decoding (ISD) [Pra62]. Breaking LPN is equivalent to solving its dual variant, which can be interpreted as the task of decoding a random linear code from its syndrome. The best algorithms for this task are improvements of Prange's ISD algorithm, which attempts to find a size-t subset of the rows of B (the parity-check matrix of the code) that spans e 2 O(n/ log(n/r)) using 2 O(n/ log(n/r)) samples.

-Combinations of the above [EKM17]. The authors of [EKM17] conducted an extended study of the security of LPN, and described combinations and refinements of the previous three attacks (called the well-pooled Gauss attack, the hybrid attack, and the well-pooled MMT attack ). All these attacks achieve subexponential time complexity, but require as many sample as their time complexity. -Scaled-down BKW [Lyu05]. This algorithm is a variant of the BKW algorithm, tailored to LPN with polynomially-many samples. It solves LPN in time 2 O(n/ log log(n/r)) , using n 1+ε samples (for any constant ε > 0) and has worse performance in time and number of samples for larger fields. -Low-Weight Parity Check (cf. [ADI + 17, Zic17]). Eventually, all the previous attacks recover the secret s. A more efficient attack (by a polynomial factor) can be used if one simply wants to distinguish b = s • A + e from random: by the singleton bound, the minimal distance of the dual code of C is at most n + 1, hence there must be a parity-check equation for C of weight n+1. Then, if b is random, it passes the check with probability at most 1/|F|, whereas if b is a noisy encoding, it passes the check with probability at least ((N -n-1)/N ) t .

Example Instantiations. Our constructions will rely on dual-LPN with N = s • n and a fixed, small noise weight t, where s is a small constant and the dimension n is very large; for example, n ≈ 10 6 , s = 2, t ≈ 120. We also use a regular error distribution to improve the efficiency of our implementation. Finally, we instantiate the code family with random, quasi-cyclic codes, which allow fast Õ(n) time syndrome computation. This leads an assumption that is almost the same as was recently used in code-based postquantum cryptosystems [MBD + 18, ABB + 19, AMAB + 19], the only differences being that we use a much larger dimension n and a regular error distribution, which as far as we know does not lead to significantly better attacks. For further discussion on our instantiation, security analysis and example parameters, see Section 7.1.

As discussed in [BCGI18], alternative choices of codes are possible, and can even be lineartime encodable based on [DI14] or LDPC codes. Optimizing and implementing such linear-time implementations is an interesting direction for future work.

Secure Computation and NISC

We use standard definitions of (composable) secure two-party computation. Our protocols can be analyzed and used either in a standalone setting, as formalized in [Can00,Gol04], or in a UC setting [Can01, PVW08, IKO + 11]. It will be convenient to cast our protocols in a hybrid model that allows parallel calls to an ideal oblivious transfer functionality. These calls can be instantiated by any composable OT protocol (e.g., the "PVW protocol" [PVW08] when considering UC security against malicious adversaries in the CRS model). We use λ to denote a computational security parameter, which we view as a public parameter that is available to all algorithms even when not explicitly stated.

We will specifically be interested in 2-round protocols for "sender-receiver functionalities" that take an input x from a receiver R and input y from a sender S, and deliver an output f (x, y) to R. The communication consists of a single message from the receiver to the sender followed by a single message from the receiver to the sender. Such protocols can be viewed as being non-interactive in that the receiver can publish its message x (which depends only on its input x) and then go offline, before even knowing who the sender will be. Then x can be used by any sender S (in fact, in some cases even multiple senders) by sending the encrypted output ẑ to the receiver's mailbox. We use the term non-interactive secure computation from [IKO + 11] (NISC for short) to highlight this qualitative advantage. When described in the OT-hybrid model, NISC protocols involve only one round of parallel OT calls. They can additionally involve a message from R to S and a message from S to R, as long as these messages (in an honest execution) do not depend on outputs of the OT oracle. Such NISC protocols in the OT-hybrid model can be converted into NISC protocols in the plain model (or CRS model for malicious security) using any 2-round (parallel-)OT protocol.

Pseudorandom Correlation Generators

A (two-party) pseudorandom correlation generator (PCG) securely generates long correlated pseudo-randomness from a pair of correlated keys. Defining a PCG requires care, since the natural simulation-based definition is not realizable. Instead, the following relaxed definition has been proposed in [BCGI18, BCG + 19].

The ideal output distribution of a PCG is specified by a (long) target correlation (R 0 , R 1 ), e.g., n independent instances of an OT correlation. This target correlation is specified by PPT algorithm C, called a correlation generator, where C(1 λ ) outputs a pair of strings. We furthermore restrict C to be reverse-samplable in the following sense: 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 λ ).
Examples for standard and useful correlations, all of which are reverse-samplable, include Oblivious Transfer (OT) correlation, where R 0 includes n independent pairs of bit-strings (s i 0 , s i 1 ) and R 1 includes (c i , s i c i for random bits c i , and Vector-OLE (VOLE) correlation over a finite field F, where R 0 = (u, v) for random u, v ∈ F n , and

R 1 = (x, ux + v) for random x ∈ F.
Definition 4 (Pseudorandom Correlation Generator (PCG) [BCG + 19]). Let C be a reverse-samplable 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:

-Correctness. The correlation obtained via:

{(R 0 , R 1 ) |(k 0 , k 1 ) $ ← PCG.Gen(1 λ ), R σ ← PCG.Expand(σ, k σ )} is computationally indistinguishable from C(1 λ ).
-Security. For corrupted party σ ∈ {0, 1}, the following two distributions are computationally indistinguishable:

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

As shown in [BCG + 19], a PCG as defined above can be used as a drop-in replacement for ideal correlated randomness generated by C in any application that remains secure even when C is replaced by the following corruptible version C. In C the corrupted party can choose its own randomness, and the randomness of the honest party R 1-σ is obtained by applying RSample. It turns out that in most concretely efficient MPC protocols that consume correlated randomness, security still holds even with this corruptible variant. In particular, this holds for the simple protocols that implement standard (chosen-input) OT or VOLE from the corresponding correlations. However, applying PCGs, the pair of keys (k 0 , k 1 ) to be generated either by a trusted dealer or by a secure protocol realizing PCG.Gen.

PCG Protocols and Silent NISC

We now define two new cryptographic primitives we introduce in this work: A pseudorandom correlation generation protocol (PCG protocol for short) and a non-interactive secure computation protocol with silent preprocessing (silent NISC for short).

PCG Protocols

The above notion of PCG gives a deterministic procedure for securely generating long sources of correlated randomness from short but suitably correlated seeds. It does not explicitly address the question of generating the seeds. In the following we formalize a natural generalization of PCGs to a low-communication protocol for securely generating long sources of correlated randomnness from scratch. By "low communication" we means that the total communication complexity is sublinear in the output length. 12We take the following natural definition approach: a PCG protocol for an ideal correlation C is a secure two-party protocol (in the usual sense) for the corruptible correlated randomness functionality C described below.

Definition 5 (PCG protocol). Let C be a reverse-samplable correlation generator. Define a randomized functionality C that takes from a corrupted party σ a string rσ as input, and outputs to the honest party σ a string r σ sampled by RSample(σ, rσ ). If no party is corrupted, C outputs to both parties a fresh pair of outputs generated by C. A (two-party) PCG protocol is a two-party protocol realizing C in which the communication complexity grows sublinearly with the output length. In the case of security against semi-honest adversaries, we still allow the ideal-model corrupted party (if any) to pick its input rσ for C arbitrarily, whereas the real-model adversary must follow the protocol.

As a simple corollary of an MPC composition theorem, a PCG protocol for C can serve as a substitute for ideal correlated randomness C in any higher-level application that remains secure even when C is replaced by C. Indeed, this is the case for standard MPC protocols that rely on OT correlations or other types of simple correlations, both for semi-honest and malicious security.

A general way of obtaining a PCG protocol is by distributing the randomized key generation functionality PCG.Gen of a PCG (as in Definition 4) via a secure two-party computation protocol, and then locally applying PCG.Expand. Indeed, this is the approach suggested in [BCG + 19] for the purpose of applying PCGs in the context of "MPC with silent preprocessing." However, our notion of a PCG protocol is less stringent than an alternative definition that requires securely emulating PCG.Gen for some PCG, while at the same time being as good for applications. We make use of this extra degree of freedom in our PCG protocols for the malicious model.

A central contribution of this work is the construction of two-round PCG protocols, namely ones involving only a message from R to S followed by a message from S to R. We refer to such a protocol as a non-interactive PCG protocol. We use the following syntax to highlight the fact that the message of R can be published as a "public key" before the sender(s) are known.

Definition 6 (Non-interactive PCG protocol). A non-interactive PCG protocol is defined by 4 algorithms with the following syntax:

-R.Gen(1 λ ) → (sk R , pk R ) -S.Gen(pk R ) → (sk S , m S ) -R.Expand(sk R , m S ) → r R -S.Expand(sk S ) → r S
We say that the above algorithms define a non-interactive PCG protocol for a reverse-samplable correlation C if the two-round protocol they naturally define (where each party outputs the output of Expand) is a PCG protocol for C as in Definition 5.

In a non-interactive PCG protocol as above, the two Gen algorithms can be viewed as defining a cheap setup that results in short, correlated keys. The two Expand algorithms are used to locally perform "silent preprocessing" that generates useful correlated randomness (e.g., many instances of an OT correlation, or few instances of a long VOLE correlation). In the most useful special case of OT correlations, we will refer to a non-interactive PCG that makes a small number of parallel OT calls as a non-interactive (or 2-round) silent OT extension protocol.

Silent NISC

In this section we define our new notion of non-interactive secure computation with silent preprocessing, or silent NISC for short. A silent NISC protocol for f can be viewed as a "best-of-bothworlds" combination of a non-interactive PCG protocol (see Definition 6) and a NISC protocol (see Section 2.3). That is, a 2-round (chosen-input) secure computation protocol that supports "silent preprocessing" followed by a light-weight (and often "non-cryptographic") online phase, without additional interaction.

Combining non-interactive PCG and NISC protocols in a generic way does not achieve the above goal, since it involves 4 rounds: two to generate the correlated randomness, and two to use it. To collapse these 4 rounds into two, we rely on the following feature of our concrete non-interactive PCG constructions. For useful NISC correlations such as OT and VOLE, the receiver's piece of the correlated randomness r R can be split into two parts: r in R , which is used to mask its input, and r out R , used to unmask the output. The key feature is that the construction allows R to locally generate r in R from its public key pk R alone, independently of the sender. This enables R to prepare to a future NISC before the sender is even known.

More concretely, let f (x, y) be a sender-receiver functionality with receiver input x and sender input y. Useful examples for which we get efficient solutions include: (1) n instances of string-OT; (2) bitwise-AND of two n-bit strings; (3) inner product of two length-n vectors over F; (4) a general function f represented by a Boolean circuit, which can be efficiently and non-interactively reduced to (1) via garbled circuits (see [IKO + 11, AMPR14, MR17] for such black-box reductions for the malicious model).

A NISC protocol with silent preprocessing (or silent NISC) for f is defined by 8 algorithms:

-R.Gen(1 λ ) → (sk R , pk R ) -R.Expand in (sk R ) → r in R -S.Gen(pk R ) → (sk S , pk S ) -R.Expand out (sk R , pk S ) → r out R -S.Expand(sk S ) → r S -R.Msg(r in R , x) → x -S.Msg(r S , x, y) → ẑ -R.Dec(r out R , x, ẑ) → z
The security requirement is that the 2-round protocol obtained by executing the above algorithms in any consistent order satisfies the security requirement of a (standard) NISC protocol for f .

To clarify the intended use and the features of our model for non-interactive secure computation protocols with silent preprocessing, we provide on Figure 2 a pictural representation of the protocol flow, illustrating the interdependencies between the algorithms, and we identify the main features of each of the algorithms (whether they require small communication, or only silent computation; whether they require cryptographic or non-cryptographic computation).

The 3 Expand algorithms define the "silent preprocessing" phase, that can be executed before the inputs are known. The last 3 algorithms define the online part of the NISC protocol, which Small Communication pk R , pk S are short.

Silent Computation Non-Cryptographic Computation

From here on, algorithms are input-dependent and can be executed multiple times with fresh portions of (r in R , r out R , rS).

receiver algorithms sender algorithms

= sender-independent R.Gen R.Expand out R.Expand in R.Msg R.Dec S.Gen S.Expand S.
Msg

1 λ skR r in R pk R skS pk S rS ẑ r out R x x z = f (x, y) y Fig. 2.
Pictural representation of the protocol flow for non-interactive secure computation with silent preprocessing. The receiver input is y, the sender input is x, and the target output is z = f (x, y).

is carried out once the inputs are known. Among the four examples given above, this part is "non-cryptographic" in the first three cases, and makes a black-box use of symmetric crypto in the last one.

We will be particularly interested in silent NISC realizing many parallel OTs using few parallel OTs, which can be viewed as a non-interactive, chosen-input variant of silent OT extension. While here one cannot make the communication complexity sublinear in the input length, our goal (which we achieve both in theorem and in practice) to make the communication very close to the total input length. This is the case even for the more challenging case of 1-bit OT, for which standard OT extension techniques that make a black-box use of cryptography [IKNP03, ALSZ13, KK13, KOS15] have a high communication overhead compared to the input length.

4 Improved PCGs for VOLE and OT

Simplified subfield VOLE generator

We provide a construction of a PCG for subfield-VOLE correlations in Fig. 3. Recall that in subfield-VOLE, one party receives random vectors u ∈ F N p and v ∈ F N p r , while the other party gets a random x ∈ F p r , and w = ux + v. The construction follows the informal description from Section 1.2 (where we described the special case p = 2, which is equivalent to correlated OT), and is essentially the same as the construction in [BCG + 19], with a puncturable PRF instead of a DPF. Likewise, the security analysis is essentially identical to the analysis of [BCG + 19].

Instantiating the puncturable PRF

We use a simple puncturable PRF based on the GGM approach [GGM86] (as defined in Section 2). To build a PPRF supporting t punctured points, we simply create t independent GGM PRFs, each punctured once. Evaluation of the final PPRF is defined by adding the evaluations of all t GGM-based PRFs.

More Efficient Puncturing Strategy. The key size for the above t-puncturable PRF is t•λ log(N ). It is possible to reduce this size to t•λ log(N/t) with a more optimized puncturing strategy; however, this alternative construction is not compatible with our optimized distributed generation

eα i ∈ F * p . 2. Sample x $ ← Fpr . 3. Sample k pprf $ ← PPRF.Gen(1 λ ), and k * pprf ← PPRF.Puncture(k pprf , S). 4. For i = 1, . . . , t, let zi ← x • yi -PPRF.Eval(k pprf , αi) 5. Let k0 ← (k * pprf , S, y, {zi} i∈[t]
) and k1 ← (k pprf , x). 6. Output (k0, k1).

Expand: On input (σ, kσ):

1. If σ = 0, parse k0 as (k *
pprf , S, y, {zi}i) and do as follows: (a) Define e ∈ F N p m using y, {zi}i as above. (b) For j ∈ [N ], define the j-th entry of vector v0 as

v0[j] = zi if j = αi ∈ S -PPRF.Eval(k * pprf , j) if j / ∈ S (c) Output (u, v) ← (e • H, -v0 • H). 2. If σ = 1, parse k1 as (k pprf , x) and do as follows: (a) Compute v1 ← PPRF.FullEval(k pprf ) in F N p r . (b) Output (x, w ← v1 • H).
Fig. 3. PPRF-based PCG for subfield vector-OLE protocols of Section 5 and Section 6. It is nonetheless useful in a setting where a trusted dealer is available to distribute the PCG seeds, or where computation is not a bottleneck compared to long-term storage. For a formal treatment, see Appendix B.

PCG for OT Correlation from Subfield-VOLE

In Fig. 4, we recall the construction of a PCG for OT correlations from a PCG for subfield-VOLE, introduced in [BCG + 19]. The PCG produces a set of n random 1-out-of-p OTs based on a correlation robust hash function and the LPN assumption over F p (where p is any prime power, not necessarily prime).

Semi-Honest PCG Protocols and Two-Round OT Extension

In this section, we show how to securely compute the Gen algorithm from Fig. 3, in just 2 rounds (assuming any 2-round OT). Using the construction of Fig. 4, this also leads to a distributed protocol for generating random OT correlations, assuming in addition a correlation-robust hash function. Then, we observe that our protocols satisfy a specific feature, which allows them to be derandomized into chosen-input VOLEs and OTs, without increasing their round complexity; this leads to 2-round OT extension and VOLE extension protocols, with silent preprocessing. Our construction relies on the GGM puncturable PRF [GGM86] constructed from any lengthdoubling pseudorandom generator G (Section 2.1).

On VOLE and reverse VOLE. Note that in a typical (chosen-input) VOLE, the sender inputs (u, v), while the receiver inputs x and gets w = ux + v. In our two-round protocols, however, Construction G OT Parameters:

-Security parameter 1 λ , integers n, r and prime power p with p r = O(2 λ ).

-An Fp-correlation-robust function H : {0, 1} λ × Fpr → {0, 1} λ .

-The subfield-VOLE PCG (G sVOLE .Gen, G sVOLE .Expand) with parameters (n, p, r).

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 λ ).
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. we obtain a variant called reverse VOLE [ADI + 17], where the sender inputs (x, w), while the receiver inputs u and learns v = wux. These two variants are equivalent when the inputs are random, so the distinction does not matter when constructing a PCG. In the chosen-input case, a reverse VOLE can be used to construct standard VOLE with one additional message (as observed in [ADI + 17]), so our protocols give rise to 3-round chosen-input VOLE.

Distributed GGM-PPRF Correlation

We first consider a functionality where a party R holds a PPRF key k pprf ∈ {0, 1} λ for the GGM PPRF [GGM86], and a point α = α 1 • • • α where = (λ) is logarithmic in λ, and a party S holds a value β ∈ {0, 1} λ . The functionality computes and gives k{α}, β -PPRF.Eval(k, α) to R. The functionality is represented on Figure 5.

Functionality F PPRF-GGM :

Parameters: 1 λ , , p, r ∈ N. PPRF is the GGM puncturable PRF with domain {0, 1} , key space {0, 1} λ , and range Fpr .

Inputs:

-S inputs β ∈ Fpr and a PPRF key

k pprf ∈ {0, 1} λ . -R inputs α ∈ {0, 1} .
Functionality: Proof. We represent the protocol Π PPRF-GGM satisfying the requirements of Theorem 7 on Figure 6. At a high-level, our protocol proceeds as follows: at each level i of the GGM tree, the holder of the PRF key k computes the XOR i i R of all odd-numbered nodes, and the XOR t i L of all even-numbered nodes. Using a single 1-out-of-2 OT, the receiver obtains one of (t i L , t i R ). The protocol maintains the invariant that at the level i -1, the receiver can compute (from the previously stored information) all node values except one, implying that at level i, the receiver can compute all node values except two; recovering one of (t i L , t i R ) allows him to compute exactly one of those two values, maintaining the invariant. At the end of the protocol, the receiver has stored intermediate keys ( being the depth of the tree) which allow to compute all PRF outputs, except one. Transmitting a single additional value allow the sender to reveal him this value up to an offset β.

-Compute k * pprf = PPRF.Puncture(k pprf , α). -Send k * pprf and t = β -PPRF.Eval(k pprf , α) to R.
Correctness. We first show that the s i α * i values form a correct PRF key punctured at α. We need that for each i, s i α * i equals the GGM tree value that is sibling to the unique node on level i lying on the path to leaf α. This clearly holds for the first level, i = 1. On subsequent levels, R first computes the 2 i -2 values at level i that it can obtain from the previous values it knows, and then uses these to compute the final missing value s i α * i . It does this by XORing (resp. summing over F p r , for the last level) with the i-th OT output all-but-one of the odd-indexed, or even-indexed, values, depending on the choice α i . Since the sender's OT inputs contain the XOR (resp. sum over F p r , for the last level) of every odd-or even-indexed value, the receiver ends up with the value of the sibling node to s i α i . To see correctness of the final correction value t, a similar reasoning as above shows that t = β -PPRF.Eval(k, α), as required.

Security. We exhibit a simulator Sim that generates a view indistinguishable from an honest run of the protocol as long as a single party is corrupted.

Case 1: S is corrupted. The simulation of R is straightforward, since R does not send any message directly to S in the protocol; R only send inputs to F OT .

Case 2: R is corrupted. Sim receives the input α and the target output

({s i α * i } i∈[ ] , t) of R. Sim defines t 1 • • • t
and the values (s i j ) i,j inductively, starting with t 1 ← s 1 α 1 and following the output procedure of R (see Figure 6). Eventually, Sim computes

c = t -   t + 2 -1 j=0,j =α s 2j+α   .
Then, Sim simulates the OT sender using input (t i , d i ) as input if α i = 0, and (d i , t i ) as input otherwise, where d i is an arbitrary dummy value; Sim also sends c in parallel to the OTs. The indistinguishability of the simulation follows directly from the definition of F OT and by construction of c .

Semi-Honest Non-Interactive PCG Protocol for Subfield-VOLE Correlations

We now construct a semi-honest non-interactive PCG protocol for the subfield-VOLE correlation in the F PPRF-GGM -hybrid model, by describing a 2-message, 2-party protocol to distributively execute the procedure G sVOLE .Gen. This is modelled by the functionality F Gen in Figure 7. When p > 2, the implementation requires in addition a single (subfield-) reverse VOLE on vectors of length t. Reverse VOLE can be implemented in two rounds under an appropriate variant Protocol Π PPRF-GGM :

Parameters: 1 λ , , p, r ∈ N. PPRF is the GGM puncturable PRF with domain {0, 1} , key space {0, 1} λ , and range Fpr , constructed from a length-doubling PRG G : {0, 1} λ → {0, 1} 2λ , and a second PRG G : {0, 1} λ → (Fpr ) 2 used to compute the PRF outputs on the last level of the tree.

Inputs:

-R inputs α ∈ {0, 1} .

-S inputs β ∈ Fpr and a PPRF key k pprf ∈ {0, 1} λ .

Protocol:

1. R and S execute in parallel calls to F OT , where for i = 1 to -1:

-R uses as input the choice bit αi; -S computes the 2 i partial evaluations at level i of the GGM tree defined by k, denoted s i 0 , . . . , s i 2 i -1 (in left-to-right order) and uses the two OT inputs

t i L = j∈[0,2 i-1 ) s i 2j , t i R = j∈[0,2 i-1 ) s i 2j+1 .
and for the last OT, -R uses as input the choice bit α ; -S computes the 2 evaluations of the GGM tree defined by k, denoted s 0 , . . . , s 2 i -1 ∈ (Fpr ) 2 (in left-to-right order) and uses the two OT inputs

t L = 2 -1 j=0 s 2j , t R = 2 -1 j=0 s 2j+1 .
2. In parallel to the OT calls, S sends c = β -(t L + t R ) to R.

Output: R computes its output as follows:

1. Let t 1 be R's output in the first OT. Define s 1 of LPN [ADI + 17] or using linearly homomorphic encryption. We represent the functionality F rev-VOLE on Figure 8. Note that in a reverse VOLE protocol, the sender is the one holding the input x (while in a standard VOLE, x is held by the receiver).

α 1 = t 1 . 2. For i = 2, . . . , -1: (a) Compute (s i 2j , s i 2j+1 ) = G(s i-1 j ), for j ∈ [0, . . . , 2 i-1 ), j = α1 • • • αi-1. (b) Let t i be the output from the i-th OT. (c) Define α * i = α1 • • • αi-1αi. Compute s i α * i = t i ⊕ j∈[0,2 i-1 ), j =α * i s i 2j+α i 3. Compute (s 2j , s 2j+1 ) = G (s i-1 j ), for j ∈ [0, . . . , 2 -1 ), j = α1 • • • α -1 . 4. R receives c, and computes t = c + t + 2 -1 j=0,j =α

Functionality F sVOLE-Gen

Parameters: 1 λ , N, t, p, r ∈ N. PPRF is a puncturable PRF with domain [N ], key space {0, 1} λ , and range Fpr .

Inputs:

-R inputs a weight-t vector e ∈ F N p . Let S = {α1, . . . , αt} ∈ [N ] t be the sorted indices of non-zero entries in e, and yi = eα i ∈ F * p . -S inputs x ∈ Fpr and a PPRF key k pprf ∈ {0, 1} λ . Functionality:

1. Compute k * pprf ← PPRF.Puncture(k pprf , S). 2. For i = 1, . . . , t, let zi ← x • yi -PPRF.Eval(k pprf , αi) 3. Let k0 ← (k * pprf , S, y, {zi} i∈[t]
) and k1 ← (k pprf , x). 4. Output k0 to R and k1 to S. Theorem 8. There exists a 2-message protocol Π sVOLE-Gen which realizes the functionality F sVOLE-Gen (1 λ , N, t, p, r), with semi-honest security in the (F PPRF-GGM , F rev-VOLE )-hybrid model, using t calls to F PPRF-GGM , a single call to F rev-VOLE (t, p), and no further communication. Furthermore, when p = 2, the functionality can be implemented directly using t calls to F PPRF-GGM , and no call to F rev-VOLE .

We present the protocol Π sVOLE-Gen in Figure 9. Correctness follows easily by inspection: for i = 1 to t, we have

z i = w i + c i = (b i -PPRF.Eval(k pprf , α i )) + c i = x • y i -PPRF.Eval(k pprf , α i ).
Security is straightforward. We note that when p = 2, since y is a weight-t vector, it always hold that y i = 1, hence computing a share of x • y i = x is trivial and does not require a call to the VOLE functionality.

Implementing F PPRF-GGM with the protocol Π PPRF-GGM and F OT with any 2-round semihonest OT protocol, this immediately leads to a semi-honest non-interactive PCG protocol Π sVOLE (F q ) for the subfield-VOLE correlation:

-R.Gen(1 λ ) : sets pk R to be the first message of Π sVOLE-Gen and sk R to be the secret state of R. -S.Gen(pk R ) : sets m S to be the second message of Π sVOLE-Gen on first message pk R , and sk S to be the sender output in Π sVOLE-Gen .

-R.Expand(sk R , m S ) : computes the output k 0 of the receiver from the state sk R and the second message m S , and outputs G sVOLE .Expand(0, k 0 ). -S.Expand(sk S ) : outputs G sVOLE .Expand(1, sk S ).

Corollary 9. Assuming the (HW t , H, F q )-dual-LPN(N, n) assumption, Π sVOLE-Gen is a semihonest non-interactive PCG protocol for subfield-VOLE correlations over an arbitrary extension field F q of F 2 , which only makes a black-box use of a 1-out-of-2 semi-honest 2-message OT and a length-doubling PRG G : {0, 1} λ → {0, 1} 2λ . By making additionally a single black-box use of a 2-message length-t semi-honest reverse VOLE, this can be generalized to arbitrary fields.

In the above corollary, Π sVOLE-Gen makes t • log N black-box accesses to the 1-out-of-2 semi-honest 2-message OT, t • N black-box accesses to a length-doubling PRG, and additionally computes one matrix-vector multiplication with H. Regarding communication, the size of pk R is t

• log N • N R and the size of m S is t • (λ + log N • N S )
, where N R (resp. N S ) denote the receiver communication (resp. the sender communication) in the underlying OT protocol; over general fields, there is an additional +M R (t, q, r) term in the size of pk R and +t • M S (t, q, r) in the size of m S , where M R (t, q, r) (resp. M S (t, q, r)) denote the receiver communication (resp. the sender communication) in the underlying length-t reverse subfield-VOLE protocol over F q r .

Protocol Π sVOLE-Gen

Parameters: 1 λ , N = 2 , t, p, r ∈ N. PPRF is a puncturable PRF with domain [N ] and range Fpr .

Inputs:

-R inputs a weight-t vector e ∈ F N p . Let S = {α1, . . . , αt} ∈ [N ] t be the sorted indices of non-zero entries in e, and yi = eα i ∈ F * p . -S inputs x ∈ Fpr and a PPRF key k pprf ∈ {0, 1} λ .

Protocol:

1. S picks b $ ← F t p . 2. R and S call F rev-VOLE (t, p) on respective inputs (y, (b, x)). R receives an output c. 3. For i = 1 to t, R and S call F PPRF-GGM (1 λ , , p, r) on respective inputs αi and (bi, k pprf ). R receives an output (k * pprf , wi). 4. For i = 1 to t, R computes zi ← wi + ci. R outputs (k * pprf , S, y, {zi} i∈[t] ) and S outputs (k pprf , x).

Semi-Honest Non-Interactive Secure Computation with Silent Preprocessing

While the non-interactive PCG protocols of the previous section are interesting in their own right, we observe that they satisfy the features outlined in Section 3.2, and therefore lead to 2-round protocols, and even silent NISC, for the OT and the VOLE functionalities.

Semi-Honest Two-Round OT with Silent Preprocessing As observed in [BCG + 19] (and shown in Fig. 4), a PCG for subfield-VOLE together with a correlation-robust hash function lead to a PCG G OT for the ROT correlation. Using our distributed setup protocol Π sVOLE-Gen (which can be implemented in two rounds, given any two-round OT and two-round subfield-VOLE), together with the standard protocol for chosen-input OT from ROT, directly leads to a two-round OT extension protocol, which performs n OTs on s-bit strings with communication (2s + 1) • n + o(n) (for any s).

Theorem 10. Assuming the (HW t , H, F p )-dual-LPN(N, n) assumption, Π OT is a semi-honest 2-round OT extension with silent preprocessing for generating n 1-out-of-2 OTs, which makes o(n) black-box uses of a 2-round semi-honest 1-out-of-2 OT, and O(n) black-box uses to a lengthdoubling PRG and an F p -correlation robust hash function.

Assuming further any 2-round semi-honest reverse VOLE, there is a 2-round OT extension with silent preprocessing for 1-out-of-p OT with comparable costs, using additionnally one blackbox execution of a reverse-VOLE on length-o(n) inputs.

Proof. In the above theorem, Π OT additionally requires the computation of one matrix-vector multiplication with H. It has total communication (2s + 1) • n + o(n), where s is the bit-length of the sender messages. We represent the protocol for 2-round OT extension on Figure 10.

Correctness. By the correctness of Π sVOLE-Gen and G OT , it holds that

v i = w i,u i for i = 1 to n. Therefore, m i,s i -v i = m i,s i + w i,t i -s i -w i,u i = m i,s i since t i -s i = u i .
Security. We exhibit a simulator Sim that generates a view indistinguishable from an honest run of the protocol as long as a single party is corrupted.

Case 1: S is corrupted. Sim simulates R by constructing (e, u) honestly, participating to Π sVOLE-Gen as R does (note that this does not require any input of R). Sim simulates t by sending t $ ← F n p . Since Π sVOLE-Gen securely emulates F Gen , no information about u leaks to S during the execution of Π sVOLE-Gen . By the security of G OT , u is computationally indistinguishable from random from the viewpoint of S, hence so is t = u + s; therefore, the simulation is indistinguishable from an honest run of the protocol.

Case 2: R is corrupted. Sim receives R's input (s i ) i≤n , R's random tape, and the corresponding target output (m i,s i ) i from the OT functionality. Sim simulates S by sampling k 1 and computing the w i,j honestly (this does not require the input of S). Sim computes the random noise vector e of R using R's random tape, from which he can compute R's output k 0 = (u, v). For i = 1 to n, Sim computes m i,s i as m i,s i + v i , and picks m i,j $ ← {0, 1} λ for each j = s i . Sim sends (m i,j ) i,j to R. By the security of Π sVOLE-Gen and G OT , the m i,j for j = s i are indistinguishable from random from the viewpoint of R, hence the simulation is indistinguishable from an honest run of the protocol.

Protocol Π OT Parameters: 1 λ , n, N = 2 , t, p, r ∈ N. H ∈ F N ×n p .
PPRF is a puncturable PRF with domain [N ] and range Fpr . Dt,N is a weight-t error distribution over F N p .

Inputs:

-R inputs n field elements (si) i≤n ∈ F n p . -S inputs n length-p vectors (mi) i≤n where each mi is over ({0, 1} λ ) p .

Protocol:

1. R picks e $ ← Dt,N . Let S = {α1, . . . , αt} ∈ [N ] t be the sorted indices of non-zero entries in e, and yi = eα i ∈ F * p . R computes the first part u of G OT .Expand(0, k0) (note that u is computed as e • H where e depends solely on e). R sets t ← u + s 2. S samples x $ ← Fpr and k pprf $ ← PPRF.Gen(1 λ ). He sets k1 ← (k pprf , x) and computes {wi,j} i≤n,j≤p ← G OT .Expand(1, k1). 3. R computes and sends to S the first round of Π sVOLE-Gen on input e, together with t. 4. S computes and sends to R the second round of Π sVOLE-Gen on input (x, k pprf ) together with m i,j ← mi,j + wi,t i -j for i = 1 to n and j = 1 to p; R gets an output k0. 5. R computes (u, v) ← G OT .Expand(0, k0) and outputs (m i,s i -vi) i≤n .

Fig. 10. Two-Round OT Extension

NISC for OT with Silent Preprocessing. Our 2-round OT extension protocol directly gives rise to a non-interactive secure computation protocol for the oblivious transfer functionality, with silent preprocessing, as defined in Section 3.2. For the sake of concreteness, we frame our OT extension protocol into the language of NISC with silent preprocessing on Figure 11.

Protocol NISC OT Parameters: 1 λ , n, N = 2 , t, p, r ∈ N. H ∈ F N ×n p .
PPRF is a puncturable PRF with domain [N ] and range Fpr . Dt,N is a weight-t error distribution over F N p . par ← (1 λ , n, N, t, p, r, H).

Inputs:

-R inputs n field elements (si) i≤n ∈ F n p . -S inputs n length-p vectors (mi) i≤n where each mi is over ({0, 1} λ ) p .

Protocol:

-R.Gen(par) : pick e $ ← Dt,N . Compute the first round of Π sVOLE-Gen on input e. Set sk R to be the secret state of R after computing the first round of Π sVOLE-Gen , and pk R be the message computed by R in Π sVOLE-Gen .

-R.Expand in (sk R ) : compute the first part u of G OT .Expand(0, k0) (note that u is computed as e • H where e depends solely on e). Output r in R ← u. -S.Gen(pk R ) : sample x $ ← Fpr and k pprf $ ← PPRF.Gen(1 λ ). Set sk S ← (k pprf , x). Define pk S to be the second round message of S in Π sVOLE-Gen on input (x, k pprf ) after receiving the message pk R from R.

-R.Expand out (sk R , pk S ) : compute the output r out R obtained by R with state sk R upon receiving the message pk S from S in Π sVOLE-Gen .

-S.Expand(sk S ) : compute r S = {wi,j} i≤n,j≤p ← G OT .Expand(1, sk S ).

-R.Msg(r in R , s) : output ŝ ← r in R + s. -S.Msg(r S , ŝ, (mi)i) : parse r S as {wi,j} i≤n,j≤p . Compute m i,j ← mi,j + w i,ŝ i -j for i = 1 to n and j = 1 to p and output ẑ = (m i,j )i,j. -R.Dec(r out R , s, ẑ) : parse ẑ as (m i,j )i,j. Compute (u, v) ← G OT .Expand(0, r out R ) and output z = (m i,s i -vi) i≤n . Semi-Honest NISC for Reverse Subfield-VOLE The same derandomization strategy as above directly implies, starting from the non-interactive PCG protocol for subfield-VOLE of Section 5.2, a NISC protocol for reverse subfield-VOLE with silent preprocessing, with features comparable to that of the NISC for OT extension. We omit the details.

Theorem 11. Suppose the (HW t , H, F p )-dual-LPN(N, n) assumption holds. Then there is a semi-honest NISC protocol for reverse subfield-VOLE with silent preprocessing for generating length-n reverse subfield-VOLEs over an arbitrary field F p , which uses o(n) black-box executions of a 2-message semi-honest 1-out-of-2 OT, O(n) black-box calls to a length-doubling PRG, one black-box call to a 2-message semi-honest reverse VOLE, and additionally computes one matrix-vector multiplication with H. It has total communication (2s + 1) • n + o(n).

Maliciously Secure PCG Protocols

In this section, we present protocols for VOLE, OT extension and NISC with security against malicious parties. Our final protocol for OT extension takes place in four rounds, and can be compressed to two rounds via Fiat-Shamir.

We begin in Section 6.1 by formalizing and describing an augmented PPRF primitive with a "malicious key verification" procedure, corresponding to the event of when a selective-failure attack will (or not) be identified. In Sections 6.2 and 6.3, we describe simple consistency checks that achieve the selective-failure-only security notion for a single GGM PPRF and for a batch of t PPRFs (with consistent x), respectively. Then, in Section 6.4, we build atop this functionality to obtain a PCG protocol for subfield VOLE with standard malicious security. In Section 6.5, we explain how the PCG protocol for subfield VOLE can be converted into a four round PCG protocol for random 1-out-of-p OT correlation. Finally, in Section 6.6 we show how to apply the Fiat-Shamir heuristic to compress the protocol down to just 2 rounds, relying on a slightly stronger assumption and the random oracle model. To obtain silent NISC for the OT functionality, which implies two-round OT extension on chosen inputs, we use the observation (as in our semi-honest protocol) that the receiver and sender can derandomize their inputs in parallel with their protocol messages.

Puncturable PRF with Malicious Keys

In the following sections we will realize a relaxed form of distributed PPRF setup functionality, where a corrupt sender may choose its own "master key," defining a PRF evaluation that need not coincide with any honest GGM tree, provided that it is consistent with the receiver's punctured point. The consistency of the keys will serve as the "getting caught" predicate in our ideal functionality. In this section, we introduce necessary terminology in order for the consistency check to be formulated.

To check consistency of the punctured key, we modify both the range and domain of the GGM construction used previously. We extend the domain from [N ] to [2N ], and the range so that the values of even-indexed leaves lie in (F p r ) 2 , whilst those of odd-indexed leaves are in {0, 1} λ . We will use a pair of PPRF consecutive outputs ((ω, w), γ) ∈ (F p r ) 2 × {0, 1} λ as follows:

The value w will correspond to the actual output of the PPRF. The value γ will be used to ensure consistency within a single PPRF keys. The value ω will be used to ensure consistency across t PPRF keys. To verify a single PPRF key, the punctured point α ∈ [N ] is mapped to an even index in [2N ], so that an honest receiver can verify correctness of a punctured key by computing a hash of all the γ values. The sender computes the same hash and sends this to the receiver to check.

Formally, we can apply this technique to any PPRF which has the following key verification property for a maliciously generated key.

Definition 12 (Verification of malicious PPRF keys). Let (PPRF.Gen, PPRF.Puncture, PPRF.Eval) be a PPRF with keyspace {0, 1} λ , domain X and range Y. We say that PPRF allows verification of malicious keys for a set K, the malicious keyspace, if there exist efficient algorithms (Ver, Puncture * , Eval * ), such that; -Ver takes as input a malicious key K ∈ K and a set I ⊆ X and outputs 0/1. -Puncture * takes as input a malicious key K and an index α ∈ X and outputs a key k * pprf punctured at α. -Eval * takes as input a malicious key K * , a set I ⊆ X and an index in x ∈ X , and outputs a value in Y or ⊥.

Futher, we require for all I ⊆ X and K * ∈ K:

Consistency check. If Ver(K * , I) = 1 then for all α ∈ I, x ∈ X \{α}: PPRF.PuncEval(k * , x) = Eval * (K * , I, α), where k * ← Puncture * (K * , α).

If this holds then we say that K * is consistent with the set I.

GGM instantiation. In Appendix C.1, we show that the GGM puncturable PRF allows for verification of malicious keys. The malicious keyspace K will correspond to malicious choices of the sender's OT message pairs, while the malicious puncturing algorithm Puncture * computes the same punctured key that an honest receiver would, for some maliciously chosen sender key. For a given malicious key K and subset of the PRF domain I ⊂ [N ], Ver(K, I) evaluates to 1 if the full-domain evaluation vector s = (s 0 , . . . , s N -1 ) of K (as defined by Eval * ) is "well formed" for I: namely, for any possible choice of the receiver's input α ∈ I, then the sender's string s agrees with the corresponding receiver full-domain evaluation string, defined by the received key k * derived from puncturing K (via Puncture * ) at α.

Malicious Setup for Single-Point PPRF

As mentioned in the previous section, in order to achieve malicious security of a single PPRF evaluation, we use the redundancy introduced via the domain extension for checking consistent behaviour, by letting the sender provide a hash of all right leaves of the fully evaluated GGM tree.

The idea is that a sender computing the correct hash value (relative to the receiver's input α), either behaved honestly, or guessed a set I such that α ∈ I. This is captured in the functionality in Figure 12. The functionality is similar to the semi-honest functionality given in Figure 12, but the adversary is additionally allowed to give a set I ⊆ [N ] as guess. If indeed α ∈ I, the sender will successfully finish the protocol and learn some partial information about α (namely, whether α ∈ I). Otherwise, the functionality will abort.

In order for the right leaves of the GGM tree to fix a unique tree, we require the PRG of the last level G : {0, 1} λ → (F p r ) 2 × {0, 1} λ to satisfy the right-half injectivity property below.

Definition 13 (Right-half injectivity). We say a function

f = (f 0 , f 1 ) : {0, 1} λ → Y × {0, 1} λ , x → (f 0 (x), f 1 (x)) is right-half injective, if its restriction to the right-half of the output space f 1 : {0, 1} λ → {0, 1} λ is injective.
Remark 14. Note that the standard construction of a PRG from any one-way permutation is right-half injective [GPS16]. To avoid using a one-way permutation when implementing G , we can relax the half injectivity requirement to just right-half collision resistance, if G is sampled at random from a family of hash functions that are collision-resistant in their right-half output. In practice, if p r = 2 λ , we can define G : {0, 1} λ → F 2 2 λ ×{0, 1} 2λ and instantiate it with a standard counter mode PRG based on any block cipher, under the assumption that it is infeasible to find a collision in the latter 2λ bits of output. Note that here, we extended the latter part of its output from λ to 2λ bits, for 2 λ concrete security against birthday attacks.

Note that the protocol we present implements the functionality for the function PPRF 1 , defined as the GGM PPRF used in the protocol, but where evaluation drops the final λ bits of output (which were used in the consistency check, so are no longer pseudorandom).

We give the protocol for distributed setup of PPRF 1 with security against malicious adversaries in Figure 13. First, in steps 1-6 the parties run the semi-honest protocol, such that the receiver holds a key k * punctured at α 0 and the sender a possibly malicious key K. As the tree is always punctured at an even value, both parties can compute all the right leaves of the GGM tree. The sender additionally sends a hash of all these leaves to the receiver. The receiver checks if this hash is consistent with his view and aborts otherwise.

The following theorem is proven in Appendix C.2.

Theorem 15. Assuming a black-box access to a PRG G : {0, 1} λ → {0, 1} 2λ , a right-half injective PRG G : {0, 1} λ → (F p r ) 2 × {0, 1} λ , and a collision resistant hash function h : {0, 1} λN → {0, 1} λ , there exists a 2-party protocol implementing F mal-PPRF (see Fig. 12) for the puncturable PRF PPRF 1 , with malicious security in the parallel OT-hybrid model, and the following efficiency features. The interaction consists of parallel calls to F OT , and uses additional communication of r log p + λ. The computational complexity is dominated by O(2 ) calls each to G and G .

Functionality F mal-PPRF :

Parameters: 1 λ , N = 2 , p, r ∈ N. PPRF is a puncturable PRF with domain [N ] = {0, 1} , key space {0, 1} λ , and range (Fpr ) 2 , supporting verification of malicious keys.

Inputs:

-R inputs α ∈ {0, 1} .

-S inputs β ∈ (Fpr ) 2 and a PPRF key k pprf ∈ {0, 1} λ .

Functionality:

-If S is honest: 1. Compute k * pprf = PPRF.Puncture(k pprf , α).

Malicious Setup of t PPRFs with Consistent Offset

For the VOLE setup with malicious security, we require a protocol for distributed setup of t PPRFs, where the inputs β j of the sender are consistent across all evaluations. By consistent, we mean that each β j is an additive share of x • y j , where the receiver knows the other share and the noise value y j ∈ F * p . To this end, we introduce a second consistency check, where the sender has to provide a linear combination of the outputs of each PPRF. We show that a cheating sender will fail this final check, unless he managed to guess part of the receiver's input. This guessing is modelled by the functionality F mal-t-PPRF (Fig. 15), which is parameterized by a 1-puncturable PRF with verification of malicious keys.

To carry out this check, we exploit the extended range of the PPRF given by the functionality F mal-PPRF . The extra F p r element from each evaluation serves to check consistency, by taking a random linear combination of all these outputs (for each PPRF), together with a linear combination of the original outputs, and sending these to the receiver to check. Note that without the extended range, sending a linear combination of PPRF outputs to the receiver would leak the sender's input x; with the extra outputs, however, the sender can use a random value χ which serves to mask x.

Since we sacrifice the extended outputs in the consistency check, the functionality F mal-t-PPRF which we realize gives us a PPRF with range F p r , as required, which is defined by simply ignoring the first element output from the one with range F 2 p r . To create the shares of x • y j , when p > 2 we again need a slightly stronger flavor of reverse VOLE, presented in Figure 14. Here, we require the functionality to take two inputs by the sender ((β, χ), (b, x)), and only one input y by the receiver, and return to the sender values γ, c, such that (β, γ) constitute sharings of x × y (and similar for c). Note that it is not enough for our protocol to instead call the basic reverse VOLE functionality twice, as a receiver providing inconsistent inputs in the two calls can learn the input x of the sender in the protocol Π mal-t-PPRF (Figure 16).

For a proof of the following theorem we refer to Appendix C.3.

Protocol Π mal-PPRF :

Parameters: 1 λ , , N = 2 , p, r ∈ N. PPRF GGM is the GGM puncturable PRF with domain {0, 1} +1 = [2N ], key space {0, 1} λ , and range (Fpr ) 2 × {0, 1} λ , constructed from a length-doubling PRG G : {0, 1} λ → {0, 1} 2λ , and a second PRG G : {0, 1} λ → (Fpr ) 2 × {0, 1} λ used to compute the PRF outputs on the last level of the tree.

Inputs:

-R inputs α ∈ {0, 1} .

-S inputs β ∈ (Fpr ) 2 and a PPRF key k pprf ∈ {0, 1} λ .

Protocol:

1. S samples a random seed k pprf ∈ {0, 1} λ . 2. S computes the 2 i partial evaluations at level i of the GGM tree: (a) S sets

s 0 0 = k pprf . (b) For i ∈ {1, . . . , }, j ∈ [0, . . . , 2 i-1 ): S computes (s i 2j , s i 2j+1 ) = G(s i-1 j ). (c) For j ∈ {0, 1} : S computes (s +1 2j , s +1 2j+1 ) = G (s j ) ∈ (Fpr ) 2 × {0, 1}
. 3. S computes the "left" and "right" halves for i ∈ {1, . . . , }:

K i 0 = j∈[0,2 i-1 ) s i 2j , K i 1 = j∈[0,2 i-1 )
s i 2j+1 4. S computes the "right" half for i = + 1:

K +1 1 = j∈{0,1} s +1 2j+1
5. For i = 1, . . . , = log N (in parallel) the parties run OT where in the i-th OT: (a) R inputs the choice bit αi.

(b) S inputs the pair (K i 0 , K i 1 ). 6. S sends to R the key K +1 1 and the correction value

c = β - j∈[N ] s +1 2j .
7. For the consistency check, S sets γj = s +1 2j+1 for all j ∈ [N ] and sends to R the value Γ = h(γ0, . . . , γN-1). 8. Let {K i } +1 i=1 denote the OT outputs received by R together with the key of the ( + 1)-st level. Then, R proceeds as follows. Input: The sender S inputs a pair ((β, χ), (b, x)) ∈ (F t p r × Fpr ) 2 . The receiver R inputs a vector y ∈ F t p .

(a) k * pprf ← Puncture * ({K i } +1 i=1 , α). (b) {sj} j =α 0 ← PPRF GGM .FullEval(k * pprf , α 0). (c) R
Functionality: Compute γ ← yχβ and c ← yxb and output (γ, c) to R. Parameters: 1 λ , N = 2 , t, p, r ∈ N. PPRF is a puncturable PRF with domain [N ], key space {0, 1} λ , and range Fpr , supporting verification of malicious keys.

Inputs:

-R inputs indices α1, . . . , αt ∈ [N ] and weights y1, . . . , yt ∈ F * p . We define S = {α1, . . . , αt}. -S inputs k1 = ({kj} j∈[t] , x), where x ∈ Fpr and kj ∈ {0, 1} λ . Functionality:

-If S is honest: 1. Compute k * j ← PPRF.Puncture(kj, αj), for j ∈ {1, . . . , t}. 2. Let zj ← x • yj -PPRF.Eval(kj, αj) for j ∈ {1, . . . , t}. 3. Let k0 ← ({k * j , zj} j∈[t] , S, y). 4. Output k0 to R. -If S is corrupted: 1. Receive from A t subsets I1, . . . , It ⊆ [N ]
and a set of keys K * 1 , . . . , K * t ∈ K. 2. For each j ∈ {1, . . . , t} check that αj ∈ Ij and that Ver(K * j , Ij) = 1. If any check fails, abort.

Compute k

* j = PPRF.Puncture * (K * j , αj) for each j ∈ {1, . . . , t}. 4. Let zj ← x • yj -PPRF.Eval * (K * j , Ij, αj) for j ∈ {1, . . . , t}. 5. Output k0 ← (k * pprf , S, y, {zj} j∈[t]
) to R and success to S.

Fig. 15. Functionality for malicious distributed setup of t puncturable PRFs

Protocol Π mal-t-PPRF :

Parameters: 1 λ , N = 2 , t, p, r ∈ N. PPRF is a puncturable PRF with domain [N ], key space {0, 1} λ and range (Fpr ) 2 .

Inputs:

-R inputs distinct indices α1, . . . , αt ∈ [N ] and weights y1, . . . , yt ∈ F * p . We define S = {α1, . . . , αt} and y = (y1, . . . , yt) ∈ (F * p ) t . -S inputs x ∈ Fpr .

Protocol:

1. S picks β, b $ ← F t p r and χ $ ← Fpr . 2. R and S call F g-rev-VOLE (t, p, r) on respective inputs y and ((β, χ), (b, x)). R receives (γ, c) ∈ F t p r × F t p r . 3. R and S call F mal-PPRF (1 λ , N, p,
r) t times on respective inputs αj and (βj, bj). R receives k * j and (ωj, wj) for each j ∈ {1, . . . , t}. If any of the runs is not successful, R receives abort from the functionality. 4. R samples τ, τ0, . . . , τN-1 $ ← Fpr and sends these to S. 5. S computes (v j S,2i , v j S,2i+1 ) ← PPRF.Eval(kj, i) for i ∈ [N ], j ∈ {1, . . . , t}, and sends

X = χ + τ • x and VS,j = N -1 i=0 τi • (v j S,2i + τ • v j S,2i+1 ) for j ∈ {1, . . . , t} to R. 6. R computes (v j R,2i , v j R,2i+1 ) ← PPRF.Eval (k * j , i) for i ∈ [N ], j ∈ {1, .
. . , t}, where PPRF.Eval is an algorithm that outputs (ωj, wj) + (γj, cj) on input (k * j , αj), and -PPRF.

Eval(k * j , i) else. 7. R checks if VS,j + N -1 i=0 τi •(v j R,2i +τ •v j R,2i+1 ) = X •τα j •yj for j ∈ {1, . . . , t}.
If any of these checks fail or R received abort from F mal-PPRF in step 3, R aborts. Otherwise, R sends ok to F mal-PPRF and outputs k0 = ({k * j , zj}j, S, y).

Fig. 16. Protocol for malicious distributed setup of t puncturable PRFs

Theorem 16. There exists a 4-message 2-party protocol Π mal-t-PPRF which securely implements the functionality F mal-t-PPRF (1 λ , N, p, r) for the puncturable PRF PPRF in the F g-rev-VOLE -, parallel F mal-PPRF -hybrid model, with malicious security, using t parallel calls to F mal-PPRF , and only one call to F g-rev-VOLE , and further communication of (N + t + 2)r log p bits. Furthermore, when p = 2, the functionality can be implemented in the parallel F mal-PPRF -hybrid model, using no call to F g-rev-VOLE .

Using an additional pseudorandom generator PRG : {0, 1} λ → F N +1 p r , the communication can be reduced to just (t + 1)r log p + λ bits, by sampling τ, τ i using a random seed for PRG. We did not include this in the protocol, to simplify its description and proof of security.

4-Round VOLE and OT Setup with Malicious Security

The F mal-t-PPRF functionality can be immediately used to distribute the setup of the subfield-VOLE PCG from Section 4. To prove this gives secure subfield-VOLE, however, we now need to assume that the dual-LPN assumption remains secure when an adversary is allowed to query (on average) one bit of information on the error vector. This reflects the fact that a malicious sender in F mal-t-PPRF can try to guess subsets containing the receiver's α j inputs, which correspond to non-zero coordinates of the error vector. This assumption with leakage is essentially the same as an assumption recently used for maliciously secure MPC based on syndrome decoding [HOSS18a]. For a formal definition, complete protocol and proof of the following theorem, we refer to Appendix C.4. Theorem 17. Let PPRF be a t-puncturable PRF, and suppose that (HW t , C, F p )-dual-LPN(N, n) with static leakage holds. The protocol in Fig. 20 securely realizes the functionality F sVOLE (Fig. 19).

Corollary 18. Suppose that (HW t , C, F p )-dual-LPN(N, n) with static leakage holds, where N = O(n) and t = o(n/(λ log n). Then there exists a 4-message, maliciously secure PCG protocol for the subfield VOLE correlation, which makes o(n) parallel calls to an oblivious transfer functionality, with communication complexity o(n) bits.

4-Round Random OT PCG Protocol with Malicious Security

Given the PCG protocol for the subfield VOLE correlation, we can easily convert this a PCG protocol for random oblivious transfer using a correlation robust hash function, as in construction G OT (Fig. 4). To perform 1-out-of-2 OT, the parties run subfield VOLE over F 2 λ , where the OT receiver, who acts as VOLE sender, obtains u ∈ F n 2 and v = w + ux ∈ F n 2 λ , while the OT sender / VOLE receiver gets x ∈ F 2 λ , w ∈ F n 2 λ . This can be seen as a correlated OT, where the receiver has choice bits u i and messages v i , which equal either w i or w i + x. To convert these to random OTs, the parties use a hash function H, and output respectively

(u i , H(i, v i )), (H(i, w i ), H(i, w i + x))
We require the hash function to be correlation robust, namely, for any choices of w i , the pairs (w i , H(i, w i + x)) i are indistinguishable from pairs (w i , U ) i , where U is the uniform distribution [IKNP03, BCG + 19]. This then gives a protocol that realizes the corruptible random OT functionality, where corrupt parties may influence their random outputs, in the F sVOLE -hybrid model.

Notice that, as observed in [GKWY19], in order to prove security the index i must be included as an input to H, since otherwise a malicious receiver can break security by choosing its outputs of the corruptible F sVOLE functionality (where it is VOLE sender). 13The theorem below can be proven similarly to the proof of Theorem 17.

Theorem 19. Suppose that there exists an F p -correlation-robust hash function, and (HW t , C, F p )dual-LPN(N, n) with static leakage holds for N = O(n) and t = o(n/(λ log n). Then there exists a 4-message, maliciously secure PCG protocol for the random 1-out-of-p OT correlation, which makes o(n) parallel calls to an oblivious transfer functionality and communicates o(n) bits.

2-Round OT Extension and Silent NISC with Malicious Security

We now show how to compress the above protocols down to just two rounds, by applying the Fiat-Shamir heuristic. Additionally, under a slightly stronger version of the dual-LPN assumption with one bit of adaptive leakage (see Definition 23 in Section C.4), we can convert the random OTs/VOLEs into ones on chosen inputs in parallel with the setup messages. This gives a tworound OT extension protocol with malicious security. First, observe that the only interaction in the malicious secure protocol for distributing t puncturable PRF keys (Fig. 16), besides the parallel calls to F mal-PPRF and F g-rev-VOLE , is the random challenges (τ, τ 0 , . . . , τ N -1 ) from the receiver, and response from the sender. Using the Fiat-Shamir heuristic in the random oracle model, the sender can instead compute the challenges by hashing the transcript. From Theorem 15, F mal-PPRF can be realized with o(n) parallel calls to OT; also, note that F g-rev-VOLE can be efficiently realized using any semi-homomorphic encryption scheme which supports zero-knowledge proofs of knowledge for ciphertext generation and homomorphic multiplication. For instance, [BDOZ11] shows how to instantiate this under the Paillier or LWE assumption. In the random oracle model, the zero-knowledge proofs can be made non-interactive, leading to a two round protocol overall.

Theorem 20. Suppose that (HW t , C, F p )-dual-LPN(N, n) with static leakage holds, where N = O(n) and t = o(n/(λ log n), and a semi-homomorphic encryption scheme exists. Then in the random oracle model, there is a non-interactive, maliciously secure PCG protocol for the subfield VOLE correlation, which makes o(n) parallel calls to an oblivious transfer functionality and communicates o(n) bits.

Additionally assuming an F p -correlation robust hash function, there is a non-interactive PCG protocol for random 1-out-of-p OT with the same complexity.

To obtain silent NISC for the OT functionality, which implies two-round OT extension on chosen inputs, we use the observation (as in our semi-honest protocol) that the receiver and sender can derandomize their inputs in parallel with their protocol messages. In the malicious setting, this requires an adaptive variant of the dual-LPN with leakage assumption (Definition 23), since a corrupt sender can see the masked receiver's inputs before attempting to guess a few of the LPN error positions. We present the complete protocol for 1-out-of-2 OT in Figure 17.

Theorem 21. Suppose that there exists a correlation-robust hash function, and (HW t , C, F 2 )dual-LPN(N, n) with adaptive leakage holds for N = O(n) and t = o(n/(λ log n). Then in the random oracle model, there exists a maliciously secure 2-message protocol for realizing n 1-outof-2 oblivious transfers, which makes o(n) parallel calls to an oblivious transfer functionality and communicates o(n) bits.

The above theorem also extends to 1-out-of-p OT for prime p > 2, by additionally assuming a semi-homomorphic encryption scheme as in Theorem 20.

Implementation

Instantiating LPN with Quasi-Cyclic Codes

Recall that our constructions use the dual-LPN assumption (Def. 3), which requires that given a parity-check matrix H, the syndrome e • H is indistinguishable from random, where e is Fast quasi-cyclic encoding. To efficiently implement multiplication by H, we used the library bitpolymul [CCK + 18] for fast multiplication in Z 2 [X]. Multiplying two degree n polynomials has complexity Õ(n) using additive fast Fourier transforms, with an algorithm following the standard FFT → PointwiseMult → FFT -1 structure. We optimize this by preprocessing FFT(h i ), since the h i values are fixed, and postponing FFT -1 until after summing up the s terms in the multiplication. This reduces computation by around 30-50%.

Noise distribution. To improve the efficiency of the puncturable PRF full-domain evaluation, we use a regular error vector e ∈ F N 2 , which is the concatenation of t random unit vectors, each of length N/t. This means we need to compute t full evaluations of PPRFs of domain size N/t, instead of size N , reducing the computational costs of this step by a factor t.

Security. Recall that for our dual-LPN variant, we require that given H, e•H is indistinguishable from a uniform vector, where e is a weight-t, regular error vector. The reason we truncated the parity-check matrix H to form H, is that with quasi-cyclic codes the parity bit of e • H only depends on H and t, so there is a trivial distinguisher [LP19] which truncating avoids. We also choose n to be prime to ensure that X n -1 does not have any non-trivial factors over Z 2 , apart from X -1, avoiding attacks expoiting the quasi-cyclic structure [LJKS + 16]. As also observed in [HOSS18b], we are not aware of any attacks that exploit a regular error distribution and perform significantly better than usual.

Note that quasi-cyclic codes have been used to construct optimized variants of the LPN-based cryptosystem of Alekhnovich and the code-based cryptosystem of McEliece [ABD + 16,MBD + 18], including several candidates in the ongoing NIST standardization process. Our assumption seems more conservative than these schemes, which need to embed a trapdoor into H that allows efficient decoding.

Choosing Parameters. We evaluate the concrete security of dual-LPN for various parameters (n, N, t), calculating the minimal number of noisy coordinates t such that dual-LPN with dimension n, number of samples N , and noise rate t/N requires 2 κ arithmetic operations to be broken using state-of-the-art attacks, for κ ∈ {80, 128}. The main attacks on LPN which apply in our setting (where the number of samples N is strongly restricted and the noise rate t/N is very low) are the low-weight parity check attack [Zic17], the Gaussian elimination attack and its variants [EKM17], and information set decoding (ISD) [Pra62] and its variants, especially BJMM [BJMM12]. We evaluated the concrete resistance of our LPN instances against all these attacks. For ISD [BJMM12], we relied on the analysis of [TS16] and of the NIST candidate BIKE [ABB + 19, Section 5.2], which identify the BJMM attack as the most efficient, and provide a closed formula. Since we rely on quasi-cyclic codes to improve the computational efficiency, we also take into account the effect of the DOOM (Decoding One Out of Many) attack [Sen11] which provides a √ N computational speedup against variants of LPN relying on quasi-cyclic codes. The results are summarized in Table 1.

Alternative Codes. Our choice of quasi-cyclic codes over alternative fast codes is mainly motivated by the fact that they are well studied, and fast implementations are available. However, as discussed in [BCGI18], we note that alternatives such as Druk-Ishai codes [DI14] or LDPC codes [Ale03, LM10] may be better. Both of these would allow for a linear time syndrome computation (instead of quasilinear), with small constants (less than 3d in the case of LDPC codes, where d is the row-weight of the sparse parity-check matrix). Moreover, these codes are not sensitive to the DOOM attack [Sen11], so might provide stronger resistance to standard attacks on LPN. Therefore, using such codes could potentially improve the efficiency of our implementation; we leave this to future work.

Results

We implement our semi-honest and malicious secure protocols and report their performance in several different settings. The functionality we realize is to produce n ∈ {10 4 , 10 5 , 10 6 , 10 7 } uniformly random OTs of length 128 bits. One distinction between our protocol and [IKNP03,KOS15] is that the choice bits of the receiver are uniformly chosen by our protocol, while [IKNP03, KOS15] allows the receiver to specify them. These random OTs can then be de-randomized with additional communication.

Table 2 contains the running time of our protocol. A fuller table, with alternative choices of parameters (security parameter λ, compression parameter N/n, method for computing the base OTs) is available in Appendix A.1. The primary takeaway is that both of our protocols achieve extremely low communication while the total running time remains competitive with or superior to KOS and IKNP. We report running times with each party having 1 or 4 threads, along with a background IO thread. In the LAN setting with sub-millisecond latency & 10Gbps we observe that the IKNP and KOS protocols achieve significant performance, requiring just 0.26 or 0.33 seconds to compute 10 million OTs with a single thread. While the computational cost of IKNP and KOS does outperform our implementation by roughly one order of magnitude, it also requires between 1000 and 2000 times more communication. This difference means that for more realistic network settings, such as 100Mbps, our implementation achieves a faster running time. With 4 threads and a limit of 100Mbps our implementation is up to 5 times faster (counting total running time, including both local computation and communication costs) and remains faster even for small n where our communication overheads are asymptotically closer together.

For the constrained setting of 10Mbps our protocol truly stands out with a 47 times speedup compared to IKNP with n = 10 7 and t = 4. We see a similar 46 times speedup in the malicious setting compared to KOS. Moreover, when comparing between the across the different network settings our protocol incurs minimal to no perform impact from decreasing bandwidth. For instance, with a 10Gbps connection our semi-honest protocol processes n = 10 7 OTs in 2.4 seconds while with 1000 times less bandwidth the protocol still just requires 2.8 seconds.

This scalability is explained in Table 3 which contains the communication overhead of our protocol. A fuller table, with alternative choices of parameters (security parameter λ, compression parameter N/n, method for computing the base OTs) is available in Appendix A.1. We parameterize our protocols by the desired security level λ ∈ {80, 128} and a tunable parameter s = N/n. The latter controls a trade-off between the number of PPRF evaluations and length of the resulting vectors. To maintain security level of λ bits, increasing s results in fewer PPRF evaluations and less communication. However, it also increases the computational overhead. Our smallest running times were achieved with s = 2. However, we also consider s = 4 which decreases our total communication from 126KB to 80KB for n = 10 7 . In contrast, the IKNP protocol requires 160MB for the same security level. This represents as much as a 2000 times reduction in communication. This low communication overhead results in our protocol requiring as little as 0.038 bits per OT for n = 10 7 and λ = 80. In our worst case of n = 10 4 our protocol still requires between 3 and 6 times less communication than IKNP. Another compelling property of our protocol is that we incur near constant additive communication overhead when comparing our malicious and semi-honest protocols.

8 Acknowledgements 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 18 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.

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. 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. In the following we explain how the GGM construction allows verification of malicious PPRF keys. We set the malicious key space to K = {0, 1} 2λ × ((F p r ) 2 × {0, 1} λ ). We restrict the puncturing algorithm Puncture * to even inputs α 0 ∈ [2N ], as these will later correspond to the actual output values. Note that the key K +1 0 ∈ F 2 p r takes a special role. Namely, with this key we capture a programmibility at the punctured point when it would be undefined otherwise: If I = {α} consists only of a single point, then the output value at this point α is set to be K +1 Puncture * : On input {(K i 0 , K i 1 ) +1 i=1 } and α ∈ [N ], we set α +1 = 0 and proceed as follows: Let α * i = α 1 • • • α i-1 α i for all i ∈ {1, . . . , + 1}. 1. Define s 1 α * 1 = K 1 α 1 . 2. For i ∈ {2, . . . , }:

(a) Compute (s i 2j , s i 2j+1 ) = G(s i-1 j ), for j ∈ [0, . . . , 2 i-1 ), j = α 1 • • • α i-1 and (s +1 2j , s +1 2j+1 ) = G (s j ) for j ∈ [N ], j = α. (b) For i ∈ {1, . . . , + 1} compute:

s i α i = K i α i ⊕ j∈[0,2 i-1 ), j =α * i s i 2j+α i ∈ {0, 1} λ .
3. Output the punctured key k * pprf = {s i α i } +1 i=1 . For better readablity, we overload notation and denote by Puncture * also the procedure taking only the required keys {K i α i } +1 i=1 as input. Eval * : On input K = {(K i 0 , K i 1 ) +1 i=1 },I and x ∈ [2N ] proceed as follows: 1. If Ver(K, I) = 0, return ⊥. where k * ← Puncture * (K * , α). By step (3) in the verification procedure, we have that this value is independent of the choice of α. This yields the required.

C.2 Malicious Setup for Single-Point PPRF

Formally, we define the PPRF PPRF 1 with domain [N ] and range (F p r ) 2 as follows: Let PPRF 1 = (PPRF 1 .Puncture, PPRF 1 .Eval), such that: PPRF 1 .Puncture: On input k pprf ∈ {0, 1} λ , α ∈ [N ], return k * pprf ← PPRF GGM .Puncture(k pprf , α 0). PPRF 1 .Eval: On input k pprf ∈ {0, 1} λ and α ∈ [N ], return (ω, w) ← PPRF GGM .Eval(k pprf , α 0).

We give the protocol for distributed setup of PPRF 1 with security against malicious adversaries in Figure 13.

Note that steps (1) to ( 6) correspond to the protocol in the semi-honest case with an additional level of PRG evaluation, where for the last level always the sum of the right leaves are given to the receiver. This will allow the receiver to check the hash value computed by the sender in step (7).

Theorem 15. Assuming a black-box access to a PRG G : {0, 1} λ → {0, 1} 2λ , a right-half injective PRG G : {0, 1} λ → (F p r ) 2 × {0, 1} λ , and a collision resistant hash function h : {0, 1} λN → {0, 1} λ , there exists a 2-party protocol implementing F mal-PPRF (see Fig. 12) for the puncturable PRF PPRF 1 , with malicious security in the parallel OT-hybrid model, and the following efficiency features. The interaction consists of parallel calls to F OT , and uses additional communication of r log p + λ. The computational complexity is dominated by O(2 ) calls each to G and G .

Proof. When neither party is corrupted, the receiver R will indeed compute the correct punctured key k * pprf and output value w in a protocol execution (the proof is similar to the semi-honest case and will be shown in more detail in the paragraph for security against malicious receiver.) Further, as the tree is punctured at an even value α 0, both parties hold the same values γ 0 , . . . , γ N -1 for all odd leaves. Therefore, Γ = Γ in step (6d) of the protocol execution.

Security against malicious receiver. On input α, the simulator forwards α to the functionality. On output k * pprf = {k i } +1 i=1 and w, the simulator proceeds as follows:

-For i ∈ {1, . . . , } define s i α 1 ,...,α i-1 α i = k i and s +1 α 1 = k +1 . Set K 1 α 1 = s 1 α 1 . -For i ∈ {2, . . . , }: Compute (s i 2j , s i 2j+1 ) = G(s i-1 j ), for j ∈ [0, . . . , 2 i-1 ), j = α 1 , . . . , α i-1 . -Compute (s +1 2j , s +1 2j+1 ) = G (s j ), for j ∈ [0, . . . , 2 ), j = α 0. -For i ∈ {1 . . . , + 1}: Compute

K i α i = j∈[0,2 i-1 ) s i 2j+α i ,
where we set α +1 = 0.

-Compute c = w - j∈[N ]\{α} s +1 2j .
-Set γ j = s +1 2j+1 for j ∈ [N ], and compute Γ = h(γ 0 , . . . , γ N -1 ).

Finally, the simulator forwards {K i α i } i=1 (where the i-th key corresponds to the i-th OT message), K +1 1 , c and Γ to the receiver. Note that the values {K i α i } +1 i=1 and Γ correspond to the values computed by the sender in a real protocol execution. We have to show that the key k * pprf = {s α * i } +1 i=1 ← Puncture * ({K i } +1 i=1 , α) computed by the receiver in a protocol execution corresponds to the key k * pprf = {k i } +1 i=1 returned by the functionality. We have:

s 1

α 1 = K 1 α 1 = k 1 .
-Assume that we have s i-1 j = s i-1 j for all j ∈ [0, . . . , 2 i-1 ), j = α 1 , . . . , α i-1 for some i. Then we have the same for level i, as this is true for all values off the path, and further because of

s i α * i = K i α i ⊕ j∈[0,2 i-1 ), j =α * i s i 2j+α i = s i α * i .
As s i α * i = k i for all i ∈ {1, . . . , 1 }, the keys agree as required.

Further, it holds

c = w - j∈[N ]\{α} s +1 2j = -s +1 α 0 + β - j∈[N ]\{α} s +1 2j = β - j∈[N ] s +1 2j ,
where s +1 α 0 ← PPRF GGM .Eval(k pprf , α 0) (for the key k pprf ∈ {0, 1} λ corresponding to k * pprf ). Security against malicious sender. On input of the OT messages K = {(K i 0 , K i 1 ) i=1 }, key K +1 1 , correction value c and a hash value Γ , the simulator proceeds as follows: First, the simulator computes Γ α for each α ∈ [N ] as follows:

1. Compute k * pprf ← Puncture * ({K i α i } +1 i=1 , α). 2. Compute {s j (α)} j∈[2N ]\{α 0} ← PPRF.FullEval(k * pprf , α 0).

Compute

w = c - j∈[N ]\{α} s 2j (α)
4. Set γ j (α) = s 2j+1 (α) for j ∈ [N ], and compute Γ α = h(γ 0 (α), . . . , γ N -1 (α)).

Note that this is exactly how an honest receiver, on input α, would proceed. If the sender behaved honestly, we should have

Γ 1 = Γ 2 • • • = Γ N = Γ . Let I ⊂ [n]
be the set of α's consistent with Γ , that is

I = {α ∈ [n] | Γ α = Γ }
If I = ∅ then abort. We extract the sender's input β as follows:

-Pick an α ∈ I.

-For all j ∈ [2N ]\α 0, define s j = s j (α).

-If |I| = 1, set s α 0 = 0.

-Otherwise, pick α ∈ I (with α = α), define s α 0 = s α 0 (α ).

-Set β = -s α 0 + w.

-Input β, K * = {K, (0, K +1 1 )}}, I to the functionality.

We have Ver(K, I) = 1 because of the following.

Claim. Except with negligible probability, all choices of α, α ∈ I in the above procedure lead to the same vector s = (s 0 , . . . , s N -1 ).

Proof. The case |I| = 1 is trivial. For |I| > 1, it suffices to show that for all α, α ∈ I and j ∈ [2N ] \ {α 0, α 0 }, s j (α) = s j (α ). Suppose for a contradiction that this does not hold, so there exist j ∈ [2N ], α, α ∈ [N ] such that s j (α) = s j (α ). From the fact that Γ α = Γ α and the collision-resistance of h, we have γ i (α) = γ i (α ) for all i ∈ [N ], except with negligible probability. Recall that for each (s 2i (α), s 2i+1 (α)), (s 2i (α ), s 2i+1 (α )), where i / ∈ {α, α }, we have (s 2i (α), s 2i+1 (α)) = G (ρ) and (s 2i (α ), s 2i+1 (α )) = G (ρ ) , for some ρ, ρ . From the right-half injectivity of G , we have that, if s 2i+1 (α) = γ i = γ i = s 2i+1 (α ) then it must hold that ρ = ρ . Hence, we must have s j (α) = s j (α ) for all j ∈ [2N ] \ {α 0, α 0 }, which completes the claim.

Note that the punctured key returned by the functionality equals the key computed in the real protocol execution. Next, we show that the correction value w corresponds to the one computed in the real protocol execution. For |I| = 1 this follows, as Eval * (K * , I, α) = 0. For |I| > 1, this follows as for all α ∈ I, x ∈ I\{α}, k * pprf ← Puncture * (K, x), it holds PPRF.Eval(k * pprf , α 0) = s α 0 and thus -PPRF.Eval(k pprf , α 0) + β = -s α 0 + β = w as required.

In the real execution the receiver aborts, if Γ = Γ . By previous considerations this is equivalent to α ∈ I. It follows that the functionality aborts if and only if the real protocol execution would have aborted.

C.3 Malicious Setup of t PPRFs with Consistent Offset

Theorem 16. There exists a 4-message 2-party protocol Π mal-t-PPRF which securely implements the functionality F mal-t-PPRF (1 λ , N, p, r) for the puncturable PRF PPRF in the F g-rev-VOLE -, parallel F mal-PPRF -hybrid model, with malicious security, using t parallel calls to F mal-PPRF , and only one call to F g-rev-VOLE , and further communication of (N + t + 2)r log p bits. Furthermore, when p = 2, the functionality can be implemented in the parallel F mal-PPRF -hybrid model, using no call to F g-rev-VOLE .

Experiment

  Exp-s-pPRF Setup Phase. The adversary A sends a size-t subset S * ∈ X to the challenger. When it receives S * , the challenger picks K $ ← F.KeyGen(1 λ ) and a random bit b $ ← {0, 1}. Challenge Phase. The challenger sends K{S * } ← F.Puncture(K, S * ) to A. If b = 0, the challenger additionally sends (F (K, x))x∈S * to A; otherwise, if b = 1, the challenger picks t random values (yx $ ← Y for every x ∈ S * ) and sends them to A.

Fig. 1 .

 1 Fig. 1. Selective security game for puncturable pseudorandom functions. At the end of the experiment, A sends a guess b and wins if b = b.

  Construction G sVOLEParameters: 1 λ , n, N, t, p, r ∈ N, where N > n. A matrix H ∈ F N ×n p and a weight-t error distribution Dt,N over F N p . Correlation: After expansion, outputs (u, v) ∈ F n p × F n p r and (x, w) ∈ Fpr × F N p r , where w = ux + v. We view Fp as a subfield of Fpr , via some fixed embedding and representation of field elements. PPRF is a puncturable PRF with domain [N ] and range Fpr . Gen: On input 1 λ :1. Sample e $ ← Dt,N . Let S = {α1, . . . , αt} ∈ [N ] t be the sorted indices of non-zero entries in e, and yi =

Fig. 4 .

 4 Fig. 4. PCG for n sets of 1-out-of-p random OT

Fig. 5 .

 5 Fig. 5. Functionality for distributing a PPRF correlation

  outputs the punctured key {s i α * i } i∈[ ] , and the final correction value t.

Fig. 6 .

 6 Fig. 6. Protocol Π PPRF-GGM for distributing a GGM-based PPRF correlation with semi-honest security in the F OT -hybrid model

Fig. 7 .

 7 Fig. 7. Functionality for the Generation Procedure of the Subfield-VOLE Generator

Fig. 8 .

 8 Fig. 8. Reverse Vector-OLE Functionality over a Field Fp

Fig. 9 .

 9 Fig. 9. Protocol for the Generation Procedure of the Subfield-VOLE Generator

Fig. 11 .

 11 Fig. 11. Non-interactive secure computation with silent preprocessing for oblivious transfer

  2. Send k * pprf and w = -PPRF.Eval(k pprf , α) + β to R, and k pprf to S. -If S is corrupted: 1. Wait for A to send a guess I ⊆ [N ] and a key K * ∈ K. 2. Check that α ∈ I and that Ver(K * , I) = 1. If either check fails, send abort to R and wait for a response from R. When R responds with abort, forward this to S and halt. 3. Compute k * pprf = Puncture * (K * , α) and w = -Eval * (K * , I, α) + β. 4. Send k * pprf and w to R, and success to S.

Fig. 12 .

 12 Fig. 12. Functionality for malicious distributed setup of single-point PPRF

  receives c, and computes w = c -j∈[N ]\{α} s2j (d) To verify consistency, R sets γj = s2j+1 for all j ∈ [N ], and computes Γ = h(γ0, . . . , γN-1). 9. If Γ = Γ , R outputs the punctured key k * pprf , and the final correction value w. Otherwise, R aborts.

Fig. 13 .

 13 Fig. 13. Protocol for distributed setup of single-point PPRF with consistency check

Fig. 14 .

 14 Fig. 14. Generalized Reverse Vector-OLE Functionality over a Field Fp

Fig. 18 .

 18 Fig.18. 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.

0

  by Eval * (if |I| > 1 this value is ignored).Ver: On input K = {(K i 0 , K i 1 ) +1 i=1 } and I ⊆ [N ], compute k * α ← Puncture * (K, α) for all α ∈ I. Return 1, if and only if for all α, α ∈ I, x ∈ [2N ]\{α 0, α 0} it holds:PPRF GGM .PuncEval(k * α , x) = PPRF GGM .PuncEval(k * α , x).

  2. If Î = {α 0 : α ∈ I} consists of the single point x return K +1 0 ∈ F 2 p r 3. Else, compute k * ← Puncture * (K, α) for some α 0 ∈ Î\{x} and return (ω, w) ← PPRF GGM .PuncEval(k * , x). Again, we overload notation and for α ∈ [N ] denote by Eval * (K, I, α) also the algorithm that calls Eval * (K, I, x) for x = α 0 ∈ [2N ].It is left to show that the algorithms indeed allow verification of malicious keys. Note that if Ver(K * , I) = 1, then for all α ∈ I, x ∈ [2N ]\{α 0} we have:Eval * (K * , I, x) = PPRF GGM .PuncEval(k * , x),

Table 1 .

 1 Dual-LPN parameters for estimated κ-bit security, counted as the minimum logarithm of the number of arithmetic operations for each of the ISD attack[Pra62, BJMM12], the low-weight parity check attack[Zic17] and the Gaussian elimination attack [EKM17]. The attacks take into account a √ N speedup from the DOOM attack [Sen11] which is enabled by our use of quasi-cyclic codes.

	n	t	N/n	κ	n	t	N/n	κ
	10 4	73	2	80	10 4	126	2	128
	10 5	72	2	80	10 5	120	2	128
	10 6	70	2	80	10 6	118	2	128
	10 7	68	2	80	10 7	116	2	128
	10 4	37	4	80	10 4	80	4	128
	10 5	36	4	80	10 5	72	4	128
	10 6	35	4	80	10 6	63	4	128
	10 7	34	4	80	10 7	54	4	128

Table 2 .

 2 The running time in milliseconds of our implementation compared to [ALSZ13] in both the LAN (0ms latency) and WAN (40ms one-way latency) settings, with security parameter λ = 128. λ is the computational security parameter. We set the compression N/n to 2. τ denotes the number of threads. Hybrid refers to doing 128 base OTs followed by IKNP to derive the total required base OTs.

						LAN (10Gbps) times	WAN (100Mbps) times	WAN (10Mbps) times
						n				n	n
	Protocol Base type λ	τ	10 7 10 6 10 5 10 4	10 7	10 6 10 5 10 4	10 7	10 6	10 5 10 4
	This (SH) hybrid	128 4 2,441 208 76 67 2,726 513 422 425	2,756	518 454 422
	IKNP	base	128 4	268 125	94	91 13,728 1,850 493 459 128,954 13,332 1,756 445
	This (SH) hybrid	128 1 7,990 533 130 100 8,252 808 451 422	8,291	815 467 422
	IKNP	base	128 1	573 157 108 98 15,622 2,030 613 341 129,011 13,285 1,672 429
	This (Mal) hybrid	128 4 2,659 280 84 78 2,872 479 457 424	2,846	515 438 422
	KOS	base	128 4	333 121 110 111 13,722 1,933 589 426 129,052 13,391 1,804 536
	This (Mal) hybrid	128 1 8,765 584 141 104 9,055 828 460 423	8,929	831 467 433
	KOS	base	128 1	674 170 113 106 15,741 2088 702 433 129,771 13,389 1,772 518
						Total Comm. (bytes)		Comm./OT (bits)
							n				n
	Protocol		Base type		10 7	10 6		10 5	10 4	10 7	10 6	10 5	10 4
	This (SH/Mal) hybrid			126,658	98,754		83,394 57,806	0.101	0.790	6.672 46.245
	IKNP/KOS	base		160,056,360 16,011,518 1,655,784 168,186 128.045 128.092 132.463 134.549

Table 3 .

 3 The communication overhead of our implementation compared to [IKNP03,KOS15], with N/n = 2 and λ = 4. See Table2.

  The source code can be found at https://github.com/osu-crypto/ libOTe. The benchmark was performed on a single AWS c4.4xLarge instance with network latency artificially limited to emulate a LAN or WAN settings. Specifically, we consider a LAN setting with bandwidth of 10Gbps and 0ms latency and two WAN settings with 100, 10 Mbps & 40ms one-way latency. We compare with the semi-honest OT extension protocol ofIshai et al. [IKNP03] (IKNP) and the malicious secure protocol of Keller et al. [KOS15] (KOS) as implemented by a state-of-the-art library. Both our implementations and that of [IKNP03,KOS15] use the same three round malicious secure base OT protocol of Naor & Pinkas [NP05]. We note that our protocols can be composed with a two round base OT protocol to give a two round OT extension. In the WAN setting this optimization would reduce the running times by approximately 40ms for all protocols.

Table 4 .

 4 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, ERC grant 876110, and a grant by the BGU Cyber Center. Y. Ishai additionally supported by ISF grant 1709/14, NSF-BSF grant 2015782, DARPA SPAWAR contract N66001-15-C-4065, 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) and by DFG grant HO 4534/2-2. 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). The running time in milliseconds of our implementation compared to [ALSZ13] in both the LAN (0ms latency) and WAN (40ms one-way latency) settings. λ is the computational security parameter. s = N/n denotes the compression parameter such that the PPRF output strings are of length N . τ denotes the number of threads. Hybrid refers to doing 128 base OTs followed by IKNP to derive the total required base OTs.

					LAN (10Gbps) times		WAN (100Mbps) times	WAN (10Mbps) times
						n				n				n
	Protocol Base type λ	s τ	10 7	10 6	10 5 10 4	10 7	10 6	10 5	10 4	10 7	10 6	10 5	10 4
	This	base	80 4 4	4,507	548	301 227 4,721	780	487 403	4,662	815	543 463
	(SH)	hybrid	80 4 4	4,261	344	118	65 4,598	616	366 337	4,517	600	375 346
		base	128 4 4 4,861	766	421 357 4,932	938	616 539	5,018	929	646 516
		hybrid	128 4 4 4,233	276	85	90 4,595	551	391 337	4,615	552	408 352
		base	128 2 4 3,373	975	634 528 3,675 1,221	875 687	3,603 1,188	851 747
		hybrid	128 2 4 2,441	208	76 67 2,726 513 422 425	2,756	518 454 422
	IKNP base	128 -4	268 125	94	91 13,728 1,850	493 459 128,954 13,332 1,756 445
	This	base	80 4 1 14,127 1,204	479 305 14,467 1,408	682 505 14,385 1,416	716 534
	(SH)	hybrid	80 4 1 13,772	812	164 102 13,987 1,067	406 344 13,962 1,060	407 353
		base	128 4 1 14,701 1,445	678 480 15,079 1,642	886 681 14,994 1,649	885 685
		hybrid	128 4 1 13,996	787	163 101 14,344 1,061	474 346 14,156 1,056	471 361
		base	128 2 1 9,414 1,747 1,008 761 9,694 1,973 1,220 964	9,750 1,980 1,226 980
		hybrid	128 2 1 7,990	533	130 100 8,252 808 451 422	8,291	815 467 422
	IKNP base	128 -1	573 157 108 98 15,622 2,030	613 341 129,011 13,285 1,672 429
	This	base	128 4 4	5286	879	463 358	5589 1127	787 670	5624	1123	801 670
	(Mal)	hybrid	128 4 4	5030	344	116	69	5141	622	387 339	5292	699	372 354
		base	128 2 4	3674 1018	643 528	3897 1252	891 726	3836	1217	858 777
		hybrid	128 2 4	2659	280	84 78 2872 479 457 424	2846	515 438 422
	KOS	base	128 -4	333 121	110 111 13722 1933	589 426 129052 13391 1804 536
	This	base	128 4 1 16096 1632	707 490 16499 1947 1033 811	16616	1958 1045 813
	(Mal)	hybrid	128 4 1 15656	968	185 110 15999 1205	489 426	15889	1207	490 426
		base	128 2 1 10475 1833 1028 773 10585 2026 1278 1051	10449	2033 1286 1048
		hybrid	128 2 1	8765	584	141 104 9055 828 460 423	8929	831 467 433
	KOS	base	128 -1	674 170 113 106 15741 2088	702 433 129771 13389 1772 518
						Total Comm. (bytes)			Comm./OT (bits)
							n						n
	Protocol	Base type λ	s		10 7	10 6		10 5	10 4		10 7	10 6	10 5	10 4
	This	base	80 4	53,478	45,678		37,878 27,478	0.043	0.365	3.030 21.982
	(SH/Mal) hybrid	80 4	47,690	43,850		40,010 34,890	0.038	0.351	3.201 27.912
		base	128 4	85,482	68,842		56,362 43,882	0.068	0.551	4.509 35.106
		hybrid	128 4	80,238	55,662		49,518 43,374	0.064	0.445	3.961 34.699
		base	80 2	91,470	72,750		58,710 44,418	0.073	0.582	4.697 35.534
		hybrid	80 2	83,322	74,106		50,810 43,910	0.067	0.593	4.065 35.128
		base	128 2	144,558	121,158		89,958 70,986	0.116	0.969	7.197 56.789
		hybrid	128 2	126,658	98,754		83,394 57,806	0.101	0.790	6.672 46.245
	IKNP/KOS base	128 -160,056,360 16,011,518 1,655,784 168,186 128.045 128.092 132.463 134.549

Table 5 .

 5 The communication overhead of our implementation compared to [ALSZ13]. λ stands for the computational security parameter. See Figure2.

In (a single instance of) a random OT correlation, one party obtains a pair of random bits (more generally, strings) (s0, s1) and the other obtains the pair (r, sr) for a random bit r.

In contrast, we do not know how to replace DPF by PPRF in some of the other PCG constructions from [BCG+ 19], including the LPN-based constructions for low-degree correlations and the PRG-based constructions for one-time-truth-table correlations.

We could also use the standard primal form of LPN, but this leads to worse communication complexity in our constructions.

While our current malicious VOLE protocol fails when applied over general non-field rings, the semi-honest variant is secure whenever the LPN assumption is secure. We leave the security analysis of LPN over non-field rings to future work.

In fact, in all protocols presented in this paper, the communication complexity only grows polylogarithmically with the output length, under widely believed variants of the LPN assumption.

In practice, however, we do not know of an attack on our concrete protocol if this is omitted, since a malicious VOLE sender cannot actually choose its v outputs; this is only needed for the security proof.

EletteBoyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, Peter Rindal, and Peter Scholl

Protocol Π m-OT Parameters: 1 λ , n, N = 2 , t, 2, r ∈ N. PPRF is a puncturable PRF with domain [N ] and range F2r , supporting verification of malicious keys. H ∈ F N ×n 2 is a matrix for which dual-LPN is hard. Dt,N is a weight-t error distribution over F N 2 . RO is a random oracle with output space (F2r ) N +1 . H is a correlation robust hash function.

-R inputs n field elements (si) i≤n ∈ F n 2 . -S inputs n length-2 vectors (mi) i≤n where each mi is over ({0, 1} λ ) 2 .

Protocol:

1. R picks e $ ← Dt,N . Let S = {α1, . . . , αt} ∈ [N ] t be the sorted indices of non-zero entries in e. R computes the first part u of G sVOLE .Expand(0, {k * j , zj} t j=1 , e) (note that u is computed as µ • H where µ depends solely on e). R sets t ← u + s. 2. R sends the first message for the protocol Π mal-t-PPRF with input (α1, . . . , αt). Simultaneously to the first message, R sends t to S. Let m R denote the accumulation of receiver messages. 3. S samples x $ ← F2r and kj $ ← {0, 1} λ for j ∈ {1, . . . , t}, and uses (x, k1, . . . , kt) as input to Π mal-t-PPRF . Let m S denote the corresponding accumulation of messages of S in the protocol execution.

-To replace the second message of R, S calls τ, τ1, . . . , τN ← RO(m R , m S ) and computes the last message of Π mal-t-PPRF with these challenges. -S computes (x, w ) ← G sVOLE .Expand(1, k), where k = {k1, . . . , kt}.

-S computes wi,j ← H(i, w i -j • x) for i ∈ {1, . . . , n}, j ∈ {0, 1}, -S sets m i,j ← mi,j + wi,t i -j for i ∈ {1, . . . , n}, j ∈ {0, 1}.

-S sends m S , X, VS,1, . . . , VS,j, {m i,j } i≤n,j≤2 to R. 4. R receives m S containing k * j , (ζj, zj) for each j ∈ {1, . . . , t} and further X, VS,1, . . . , VS,j, and {m i,j } i∈{1,...,n},j∈{1,2} .

-R verifies all checks in Π mal-t-PPRF with τ, τ1, . . . , τN = RO(m R , m S ). If any fails, abort.

-

Fig. 17. Two-Round 1-out-of-2 OT Extension with Malicious Security sampled from some error distribution. Below, we describe how we instantiate the matrix and error distribution to achieve good concrete efficiency, and how we choose parameters for security.

Family of codes.

We construct H based on quasi-cyclic codes. Recall that cyclic codes admit a parity-check matrix where every row is a cyclic shift of the previous row. In a quasi-cyclic code, the parity-check matrix can be written as a block matrix composed of several cyclic matrices.

Let H ∈ F N ×n 2 be the parity-check matrix of a random, quasi-cyclic code in systematic form. Writing N = s • n, where in our case we always choose s ∈ Z, we have

where I n is the n × n identity, and rot(h i ) is the circulant matrix consisting of all n rotations of the random vector h i ∈ F n 2 . Note that multiplication of a vector with rot(h i ) is equivalent to a polynomial multiplication in Z 2 [X]/(X n -1)).

We then define H to be H with its final row removed (see Security below). Computation of the syndrome of a vector e ∈ F s•n 2 , viewed as the coefficients of degree-(n -1) polynomials e 0 (X), . . . , e s-1 (X) ∈ Z 2 [X], can now be written as

where trunc(•) drops the last coefficient from its input.

A Details on Implementation

A.1 Detailed Performance Figures

In this section, we provide more extensive numbers regarding the running time and communication complexity of our implementation, with alternative choices of parameters (security parameter λ, scaling parameter N/n, method for computing the base OTs). Table 4 contains the running time of our protocol. Table 5 contains the communication overhead of our protocol.

B An Improved PPRF for G sVOLE

We describe in this section an improved (yet still relatively simple) puncturing strategy for constructing a t-puncturable PRF from the GGM PRF. This construction is somewhat folklore; it was explicitely presented in [BCG + 19]. Unlike the simple construction presented in Section 4, however, this construction is not compatible with our distributed generation protocol. Still, it is useful in setting where computation is not an issue (hence a more costly distributed generation protocol can be used) but long-term storage is (hence it is important to reduce the size of the PCG keys), or in settings where a trusted dealer is available to distribute the PCG keys (like in the commodity-based model of Beaver [Bea95]).

Proof. If both parties are honest, after execution of the protocol, R and S hold values

and thus

Computing the scalar product with (τ 0 , . . . , τ N -1 ) on both sides of the equation yields the required.

Security against malicious receiver: Receive from A input y = (y 1 , . . . , y t ) ∈ F p to F rev-VOLE and (not necessarily distinct) inputs α 1 , . . . , α t ∈ [N ] to F mal-t-PPRF . For j ∈ [t] we define e α j to be the α j -th unit vector, and u = t i=1 y j e j . The simulator forwards α 1 , . . . , α t and y 1 , . . . , y t to F mal-t-PPRF , and for each j ∈ {1, . . . , t} forwards k * j and z j to A for each j ∈ {1, . . . , t}. On inputs τ, τ 0 , . . . , τ N -1 of A, the simulator draws X $ ← F p r , computes for i ∈ [N ], j ∈ {1, . . . , t}:

and sends X and

It is left to show that this is indistinguishable from a real protocol execution. Let x be the input of the sender to the functionality. We set χ = X -τ • x. For j ∈ {1, . . . , t} we have γ j + β j = χ • y j , c j + b j = x • y j , and (ω j , w j ) = -PPRF.Eval(k j , α j ) + (β j , b j ) (since S is honest). Thus, we have

For PPRF.Eval (as defined in Figure 16) for all i ∈ [N ] this yields

This yields the required, as for each j ∈ {1, . . . , t} we have N -1 i=0 τ i • y j • ∆ i,α j = τ α j • y j . Security against malicious sender: On input ((β, χ), (b, x)) to the functionality F g-rev-VOLE and ( βj , bj ), I j , K * j to F mal-PPRF by A, the simulator draws challenges τ, τ 0 , . . . , τ N -1 ← F p r uniformly at random, and forwards all to A. On input X and V S,1 , . . . , V S,t by A, the simulator proceeds as follows:

1. Set δ j = βj -β j , d j = bj -b for j ∈ {1, . . . , t}. If there exists a j ∈ {1, . . . , t} with

). For each j ∈ {1, . . . , t} with

where τ α * j corresponds to the α * j -th coefficient chosen by the simulator. If such an α * j does not exist or is not unique, abort. 3. For j ∈ {1, . . . , t} set

else .

Define K j = {(K i j,0 , K i j,1 ) i=1 } ∪ {( K +1 j,0 , K +1 j,1 )}. 5. Input x, Î1 , . . . , Ît and K * 1 , . . . , K * t to the functionality F mal-t-PPRF . If the functionality does not reply success, abort.

We have to show that the probability of the simulation aborting is negligibly close to the probability that the receiver would have aborted in a real execution.

As τ is chosen at random from F p r by the simulator, by a union bound over j ∈ {1, . . . , t}, the probability that there exists a j ∈ {1, . . . , t} with δ j = 0 and δ j -τ • d j = 0 is upper bounded by t/p r .

Next, we show that passing the verification check, corresponds to guessing the input α j of the receiver for all j with d j = 0.

For j ∈ {1, . . . , t} it holds (ω j , w j ) = -PPRF.Eval * (K * j , I j , α j ) + (β j , b j ) + (δ j , d j ). Therefore, for the value v j R ∈ [2N ] computed by an honest receiver during the real protocol execution, we have

we see that the sender passes the check in the real execution of the protocol, if and only if he provides V S 1 , . . . , V St , such that V S,j = VS,j -τ α j • (δ j -τ • d j ) for all j ∈ {1, . . . , t} with d j = 0. Thus, if the sender guessed α * j such that α j = α * j for all such j, then the real execution check would have passed. On the other hand, if Equation 2 does not have a solution, the sender would have failed the real world check independent of the choices α 1 , . . . , α t of the receiver. The coefficients τ 0 , . . . , τ N -1 provided by the simulator are distinct except with probability at most N/p r , therefore Equation 2 has a unique solution for each j with d j = 0 except with negligible probability.

Finally, by the definition of Eval * , we have -PPRF.Eval * (K * j , I j , α j ) + (β j , b j ) + (δ j , d j ) = -PPRF.Eval * ( K * j , I j , α j ) + (β j , b j ), therefore the output to R corresponds to the output in the real protocol execution.

Note that for p = 2, we extract x by finding j ∈ {1, . . . , t} such that χ j + c • x j = X and set The assumption states that Pr Functionality: 3. S and R call F mal-t-PPRF (with the roles of sender and receiver reversed) on inputs (y, α1, . . . , αt)

and (k pprf , x). 4. R receives a punctured key k * j and value zj ∈ Fpr , for j ∈ {1, . . . , t}. 5. S receives the master keys k1, . . . , kt. The assumption states that Pr

Theorem 17. Let PPRF be a t-puncturable PRF, and suppose that (HW t , C, F p )-dual-LPN(N, n) with static leakage holds. The protocol in Fig. 20 securely realizes the functionality F sVOLE (Fig. 19).

Proof. The case where both parties are corrupted is straightforward. When neither party is corrupted, by inspection, the outputs of the honest parties satisfy w = ux + v, so we just need to show that these values are uniform subject to this constraint. The VOLE sender's u output is pseudorandom under the dual-LPN assumption, since we have u = e • H, and the receiver's x is uniformly random. Finally the sender's v = v 1 • H value is pseudorandom, since v 1 consists of pseudorandom PPRF outputs, and the matrix H has full rank.

R is corrupted. The simulator Sim S proceeds as follows.

1. Sim S receives the malicious R's inputs to F mal-t-PPRF , y, S = (α 1 , . . . , α t ), and defines the weight ≤ t error vector e. 2. Sim S samples a PPRF key k pprf $ ← {0, 1} λ and computes the key k * pprf = PPRF.Puncture(k pprf , S) punctured at S.

It sends k *

pprf to R, along with random z j $ ← F p r , for j ∈ {1, . . . , t}. 4. Sim S computes u, w = G sVOLE .Expand(0, k * pprf , {z j } t j=1 , e) and then sends u, w to F sVOLE .

Notice that the only difference between the simulation and the real execution is the way the z j values are computed. In the protocol, z j masks the sender's inputs with PPRF evaluations at the punctured points, whereas in the simulation z j is random. These two views are indistinguishable, by the security of PPRF; any adversary that distinguishes the two executions can be used to win the PPRF selective security game, Exp-s-pPRF, with exactly the same advantage.

S is corrupted.

1. Sim R receives from S x ∈ F p r , the subsets I 1 , . . . , I t and keys K * 1 , . . . , K * t ∈ K 2. Sample α 1 , . . . , α t $ ← [N ], and for each j ∈ {1, . . . , t}, check that (i) α j ∈ I j , and (ii) Ver(K * j , I j ) = 1. If any check fails, abort. 3. Sim R computes the PPRF outputs v 1 using Eval * (K * j , I j , x), for all x, j, and uses these to compute w = v 1 • H that is sent to F sVOLE , along with x.

Notice that the probability of abort is identical in both executions, since Sim R samples a noise vector just as in the real protocol. Also, the outputs of the corrupt VOLE receiver, computed by Sim R , are identically distributed to those in the protocol. The only difference between the two executions is the way the honest sender's outputs (u, v) are computed; here, we rely on the leaky variant of dual-LPN to argue that u is pseudorandom.

In particular, we show that any distinguisher D, who distinguishes the real and ideal executions, can be used against the dual-LPN assumption with static leakage. We construct an adversary for game G as follows: Invoke D with an execution of Π sVOLE , and, running Sim R , receive the adversary's guesses I 1 , . . . , I t . Instead of sampling α j as Sim R does, forward the guesses to game G. If G aborts, send abort to D, otherwise, continue running Sim R . At the end of the execution (if it did not abort) send to D the honest sender's output (u, v), where u is set to the y vector received from G, and v = wux. Output whatever D outputs.

When b = 1, the view of D is as in the real protocol, whereas when b = 0 it is exactly as in the simulation, hence, our advantage against the game G is exactly the same as the advantage of D against the protocol.