Elette Boyle
email: eboyle@alum.mit.edu

Geoffroy Couteau
email: couteau@irif.fr

Niv Gilboa
email: niv.gilboa@gmail.com§technion

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

Lisa Kohl
email: lisa.kohl@cwi.nl

Nicolas Resch
email: nicolas.resch@cwi.nl

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

Correlated Pseudorandomness from Expand-Accumulate Codes

A pseudorandom correlation generator (PCG) is a recent tool for securely generating useful sources of correlated randomness, such as random oblivious transfers (OT) and vector oblivious linear evaluations (VOLE), with low communication cost.

We introduce a simple new design for PCGs based on so-called expand-accumulate codes, which first apply a sparse random expander graph to replicate each message entry, and then accumulate the entries by computing the sum of each prefix. Our design offers the following advantages compared to state-of-the-art PCG constructions:

• Competitive concrete efficiency backed by provable security against relevant classes of attacks;

• An offline-online mode that combines simple parallelization with a cache-friendly offline phase;

• Concretely efficient extensions to pseudorandom correlation functions, which enable incremental generation of new correlation instances on demand, and to new kinds of correlated randomness that include circuit-dependent correlations.

To further improve the concrete computational cost, we propose a method for speeding up a fulldomain evaluation of a puncturable pseudorandom function (PPRF). This is independently motivated by other cryptographic applications of PPRFs.

Introduction

Correlated secret randomness is a powerful and ubiquitous resource for cryptographic applications. In the context of secure multiparty computation (MPC) with a dishonest majority, simple sources of correlated randomness can serve as a "one-time pad" for lightweight, concretely efficient protocols [START_REF] Beaver | Efficient multiparty protocols circuit randomization[END_REF]. As a classical example, consider the case of a random oblivious transfer (OT) correlation, in which Alice and Bob receive (s 0 , s 1 ) and (b, s b ) respectively, where s 0 , s 1 , b are random bits. Given 2n independent instances of this simple OT correlation, Alice and Bob can evaluate any Boolean circuit with n gates (excluding XOR and NOT gates) on their inputs, with perfect semi-honest security, by each sending 2 bits and performing a small constant number of Boolean operations per gate.

The usefulness of correlated randomness for MPC gave rise to the following popular two-phase approach. First, the parties run an input-independent preprocessing protocol for secure distributed generation of correlated randomness. This correlated randomness is then consumed by an online protocol that performs a secure computation on the inputs. Traditional approaches for implementing the preprocessing protocol (e.g., [START_REF] Ishai | Extending oblivious transfers efficiently[END_REF][START_REF] Damgård | Multiparty computation from somewhat homomorphic encryption[END_REF][START_REF] Keller | Overdrive: Making SPDZ great again[END_REF]) have an Ω(n) communication cost that usually forms the main efficiency bottleneck of the entire protocol.

This situation changed in a recent line of work, initiated in [BCG + 17, BCGI18, BCG + 19b], that suggested a new approach. At the heart of the new approach is the following simple observation: by settling for generating a pseudorandom correlation, which is indistinguishable from the ideal target correlation even from the point of view of insiders, the offline communication can be sublinear in n while retaining the asymptotic and concrete efficiency advantages of the online protocol.

The above approach was implemented through the notion of a pseudorandom correlation generator (PCG) [BCGI18,BCG + 19b]. A PCG enables two or more parties to locally stretch short correlated seeds into long pseudorandom strings that emulate a specified ideal target correlation, such as n instances of the OT correlation. This was recently extended to the notion of a pseudorandom correlation function (PCF) [BCG + 20b], which essentially emulates random access to exponentially many PCG outputs, analogously to the way a standard pseudorandom function (PRF) extends a standard pseudorandom generator (PRG). PCGs and PCFs naturally give rise to the paradigm of MPC with silent preprocessing. In MPC protocols following this paradigm, the parties invoke a one-time interactive setup with low communication and computation costs for securely generating the short, correlated seeds. These seeds can later be used, upon demand, for "silently" generating large quantities of the correlated randomness consumed by fast online MPC protocols.

Generating pseudorandom correlations: a template. To construct the PCG and PCF primitives, a general template was put forth in [START_REF] Boyle | Compressing vector OLE[END_REF], and further refined in subsequent works. At a high level, the template combines two key ingredients: a method to generate a sparse version of the target correlation, and a carefully chosen linear code where the syndrome decoding problem is conjectured to be intractable. To give a concrete example, let us focus on the vector oblivious linear evaluation (VOLE) correlation, which is in a sense a minimal step above simple linear correlations. The correlation distributes (⃗ u, ⃗ v) to Alice and (∆, ⃗ w) to Bob; here, ⃗ u, ⃗ v, ⃗ w are length-n vectors over a finite field F and ∆ ∈ F is a scalar, all chosen at random subject to satisfying the correlation ⃗ w = ∆ • ⃗ u + ⃗ v. Among other applications [WYKW21, DIO21, BMRS21, RS21b], VOLE is an appealing target correlation because (a simple variant of) VOLE can be locally converted into n pseudorandom instances of OT correlation using a suitable hash function [IKNP03, BCG + 19b].

The aim of the second ingredient is to transform this sparse correlation into a pseudorandom correlation. To this end, the parties multiply their vectors with a public compressing matrix H, obtaining (H • ⃗ u, H • ⃗ v) and (∆, H • ⃗ w). When H is random, H • ⃗ u is pseudorandom: this is exactly the dual variant of the learning parity with noise (LPN) assumption over F [START_REF] Blum | Cryptographic primitives based on hard learning problems[END_REF][START_REF] Ishai | Secure arithmetic computation with no honest majority[END_REF]. However, computing H • ⃗ v (or H • ⃗ w) takes time Ω(n 2 ). When n is in the millions, as in typical MPC applications, this is clearly infeasible. A better approach is to sample H from a distribution such that (1) H • ⃗ u is still plausibly pseudorandom, and yet (2) the mapping ⃗ v → H • ⃗ v can be computed efficiently, ideally in time Õ(n) or even O(n). For the first ingredient, there is a simple construction that allows generating (from short seeds) pairs (⃗ u, ⃗ v) and (∆, ⃗ w) as above, but where ⃗ u is a random unit vector. This uses a puncturable pseudorandom function (PPRF), a type of PRF where some keys can be restricted to hide the PRF value at a fixed point. A bit more concretely, ⃗ v and ⃗ w will be generated by evaluating the PRF on its entire domain; the missing value will be at the only position i where u i ̸ = 0, and the party with the punctured key will fill it using a share of PRF K (i) + ∆ • u i . Such a PPRF can be efficiently constructed from any length-doubling PRG [GGM86, [START_REF] Kiayias | Delegatable pseudorandom functions and applications[END_REF][START_REF] Boneh | Constrained pseudorandom functions and their applications[END_REF][START_REF] Boyle | Functional signatures and pseudorandom functions[END_REF]. With a t-fold repetition of this process (keeping ∆ the same across all instances), after locally summing their expanded vectors, the parties obtain the target correlation, where ⃗ u is t-sparse. As long as t remains small, the seed size is small as well.

The quest for the right code. In essence, all previous works in this area [BCGI18, BCG + 19b, BCG + 19a, SGRR19, BCG + 20b, YWL + 20, BCG + 20a, CRR21] have built upon this template, sometimes for more general classes of correlations [BCG + 20b], sometimes to achieve the more flexible notion of PCF [BCG + 20a], or trying to strike the best balance between security and efficiency [BCGI18,BCG + 19a, CRR21]. At the heart of all these works is, every time, a careful choice of which linear code to use. In [BCGI18, BCG + 19a], it is suggested that relying on LDPC codes or on quasi-cyclic codes provides a reasonable balance between security (since the underlying LPN assumptions are well studied [Ale03, ABB + 20]) and efficiency. In contrast, [START_REF] Couteau | Silver: Silent VOLE and oblivious transfer from hardness of decoding structured LDPC codes[END_REF] advocates a more aggressive choice, building a new concrete linear code which is highly optimized for correlated randomness generation and is guided by heuristic considerations and extensive computer simulations. Taking a different route, [BCG + 20a] shows how a newly defined family of variable density linear codes allows generating a virtually unbounded amount of correlated randomness on demand, and [BCG + 20b] generates more general correlations using an LPN variant over polynomial rings.

These works demonstrate that with a careful choice of code silent preprocessing can have an extremely high throughput [START_REF] Couteau | Silver: Silent VOLE and oblivious transfer from hardness of decoding structured LDPC codes[END_REF] (as fast as generating tens of millions of pseudorandom oblivious transfers per second on one core of a standard laptop with low communication costs), broad expressiveness [BCG + 20b] (handling richer correlations which are crucial in many MPC protocols [Bea91,BDOZ11, DPSZ12, ANO + 21, RS21a]), and optimal flexibility [BCG + 20a] (generating any amount of correlated randomness on demand). Nonetheless, in several aspects this research area is in its infancy: some important correlations remain frustratingly out of reach (such as circuit-dependent correlations, used e.g. in [DPSZ12,DNNR17,HOSS18,WRK17b,Cou19,BGI19], or authenticated multiplication triples over F 2 , used in [START_REF] Hazay | Low cost constant round MPC combining BMR and oblivious transfer[END_REF][START_REF] Wang | Authenticated garbling and efficient maliciously secure two-party computation[END_REF]); the current fastest construction [START_REF] Couteau | Silver: Silent VOLE and oblivious transfer from hardness of decoding structured LDPC codes[END_REF] is not parallelizable and lacks any clear theoretical security analysis whereas constructions built on firmer grounds are an order of magnitude slower; finally, the PCFs of [BCG + 20a] are only realistically usable in a regime of parameters where they lack any security analysis.

The quest for constructions with clear, rigorous security arguments and very high concrete efficiency remains largely open; its fulfilment, we believe, is one of the most promising paths towards making MPC truly efficient on a large scale.

Our Contributions

In this work, we push forward the study of efficient generation of correlated randomness, significantly improving over the state of the art on several fronts. Our main contributions are threefold.

Expand-accumulate codes. We put forth a new simple family of linear codes, called expand-accumulate codes (EA codes), which are related to the well-studied class of repeat-accumulate codes [START_REF] Divsalar | Coding theorems for" turbo-like" codes[END_REF]. To encode a message with an EA code, a sparse degree-ℓ expander is first applied to the input, effectively replicating each message entry a small number of times; the result is then accumulated by computing the sum of all prefixes. We demonstrate that such an EA code is a particularly appealing choice of linear code in the context of generating correlated pseudorandomness, as it uniquely combines multiple attractive features: firm security foundations, simplicity, high concrete efficiency, and easy parallelization. When an EA-based PCG is implemented in an offline-online mode, the offline phase is both parallelizable and cache-friendly, whereas the online phase requires accessing a small number of memory locations per correlation instance. Finally, the special structure of EA codes allows us to obtain several advanced constructions, including PCFs (with better efficiency and security foundations compared to [BCG + 20a]), and the first practical PCGs for useful correlations such as circuit-dependent correlations. In more detail:

1. We formally prove that the (dual-)LPN assumption for EA codes, denoted EA-LPN, cannot be broken by a large class of attacks, which captures in particular all relevant known attacks on LPN. Our analysis comes with concrete, usable security bounds for realistic parameters. In contrast, previous works either only achieved provable bounds in a purely asymptotic sense [BCG + 20a] (with poor concrete efficiency), or heuristically extrapolated plausible parameters through computer simulations on small instances [START_REF] Couteau | Silver: Silent VOLE and oblivious transfer from hardness of decoding structured LDPC codes[END_REF].

2. We also derive sets of more aggressive parameters through heuristics and simulations to obtain apples-to-apples efficiency comparisons with the work of [START_REF] Couteau | Silver: Silent VOLE and oblivious transfer from hardness of decoding structured LDPC codes[END_REF]. We show that EA codes are highly competitive with the code of [START_REF] Couteau | Silver: Silent VOLE and oblivious transfer from hardness of decoding structured LDPC codes[END_REF], while having a much simpler structure (hence simpler to implement and more amenable to analysis).

3. The PCGs built from EA-LPN are highly parallelizable, allowing for simultaneously achieving low latency and high throughput. This stands in stark contrast with essentially all previous constructions, including the recent high-throughput construction from [START_REF] Couteau | Silver: Silent VOLE and oblivious transfer from hardness of decoding structured LDPC codes[END_REF]. 1 Hence, over multicore architectures, we expect our new PCG to outperform alternative approaches.

4. We obtain the first practical PCG constructions for different kinds of useful correlations. This includes circuit-dependent correlations (which show up in communication-efficient MPC protocols [DNNR17, HOSS18, WRK17b, Cou19, BGI19] and in constant-round MPC protocols based on garbled circuits [START_REF] Wang | Global-scale secure multiparty computation[END_REF]). Generating n bits of correlations with our construction requires O(n log 2 n) work. In contrast, the only known previous approaches either use LPN but incur a prohibitive Ω(n 2 ) cost [BCG + 19b] or require expensive high-end cryptographic primitives, such as multi-key threshold FHE [DHRW16, BCG + 19b].

5. Finally, we construct a pseudorandom correlation function from the EA-LPN assumption, the first such construction to be both concretely efficient and standing on firm security arguments. The only other practically feasible constructions of PCFs are the variable-density construction of [BCG + 20a] (which is much slower, even for aggressive parameters) and the recent construction of [START_REF] Orlandi | The rise of paillier: Homomorphic secret sharing and public-key silent OT[END_REF] (which relies on the standard DCR assumption, but is also slower, is restricted to OT and VOLE correlations -our construction can handle other useful correlations -and is not post-quantumour construction plausibly is).

Offline-online pseudorandom correlation generators. PCGs allow one to expand, in a "silent" fashion (i.e. without any communication), short seeds into long sources of correlated pseudorandomness. This silent expansion largely dominates the overall computational cost of the entire protocol: in the online phase, the computation amounts to a few cheap xor operations per gate, and the limiting factor is communication. Even with a very high bandwidth, the latency of multi-round protocols can form a bottleneck. This implies that, in many settings, some idle computation time is wasted during the online phase. We put forth a new notion of PCG, called offline-online PCG, which seeks to push the vast majority of the offline work back to the online phase, but in an incremental fashion that minimizes latency. In more detail, most of the computational slowdown in the silent expansion of modern PCGs is incurred by cache misses. Indeed, most of the efficiency improvements of the PCG of [START_REF] Couteau | Silver: Silent VOLE and oblivious transfer from hardness of decoding structured LDPC codes[END_REF] come precisely from heuristically building a cache-friendly linear code. However, constructing such cachefriendly codes with firm security foundations remains elusive. Moreover, the cache-friendliness of the construction from [START_REF] Couteau | Silver: Silent VOLE and oblivious transfer from hardness of decoding structured LDPC codes[END_REF] comes at the expense of a fully sequential silent expansion. Instead, we suggest a new approach: using EA codes, cache misses are bound to occur because of their expanderbased structure; however, it is relatively easy to push all these cache misses to the online phase, where they will happen during idle moments (caused by bandwidth limitations or latency within the secure computation application). Concretely, EA codes achieve the following:

• In the offline phase, the sparse version of the correlation is generated using a PPRF; this amounts to computing a few hundred binary trees of hashes (a la GGM), which is highly parallelizable and cache-friendly. In the literature, this is typically referred to as the full evaluation part, because it amounts to evaluating several PRRFs on their entire domain.

• Still in the offline phase, an accumulation step is performed, which converts a vector

(x 1 , x 2 , • • • , x N ) to an accumulated vector (x 1 , x 1 ⊕ x 2 , • • • , N i=1 x i ).
This "prefix sum" computation can be done with N -1 xors of short strings in one pass, which is extremely fast and cache-friendly; furthermore, it is easy to parallelize with a simple two-pass algorithm while still retaining cache-friendliness.

• At the end of the offline phase, a length-N vector ⃗ y of short strings is stored, where N is a small constant factor times the target amount n of correlations (concretely, N ≈ 5•n in our instantiations). Finally, to generate an instance of the target correlation, one must retrieve ℓ random entries of ⃗ y, and xor them, where the output locality parameter ℓ corresponds to the degree of the graph defining the EA code. This is where cache misses can occur; however, this step is still highly parallelizable, and these random accesses can easily be arranged to fill exactly the idle computation time of the online phase. Concretely, for conservative parameters fully within the bound of our theoretical analysis, ℓ can be set to about 40 when producing n ≥ 2 20 correlations; using more aggressive parameters, setting ℓ as low as 7 seems to nonetheless provide a sufficient security level according to our experiments.

Our estimates suggest that relying on offline-online PCGs instead of standard PCGs will likely lead to significant improvements in MPC protocols. The offline part of our EA-based offline-online PCGs is extremely fast -we estimate of the order of 100ms to generate the offline material for 10 million random OTs on a single core of a standard laptop, a runtime which can be sped up by almost a factor of k when k processors are available, even with a few dozen processors.

Further speedups in the offline phase. Up to this point, we discussed the application of a new family of linear codes to speed up PCGs and achieve new advanced constructions. We now turn our attention to the other main component of a PCG: the full evaluation procedure, which boils down to evaluating several PPRFs on their entire domain. Concretely, using the GGM PPRF [GGM86,KPTZ13, BW13, BGI14], generating a length-N vector with this procedure requires 2N calls to a hash function along the leaves of a full binary tree. We obtain new PPRF constructions that aim to reduce the total number of calls to the underlying hash function. Our main construction reduces the number of calls to 1.5N ; we prove its security in the random oracle model. We also put forth a candidate construction with the same 1.5N cost in the ideal cipher model (supporting an implementation based on standard block ciphers such as AES), but leave its security analysis open. We describe several additional optimizations; in particular:

• We show that, by "flattening the GGM tree," the number of calls can be further reduced, at the cost of sightly increasing the seed size (and seed distribution cost). Concretely, we can reduce the total number of calls to 1.17N , only increasing the seed size and seed distribution time by a factor of 1.5 (this is a desirable tradeoff, since these costs vanish when N increases, and are typically marginal with standard parameters).

• We show that, in the specific context of generating OT correlations, the cost can be further reduced to N (without the flattening optimization) or 0.67N (with flattening) calls to the hash function.

We note that these contributions are of a very different nature compared to our previous constructions, and add to the body of work on the analysis in idealized models of symmetric primitives for MPC applications [START_REF] Guo | Efficient and secure multiparty computation from fixed-key block ciphers[END_REF][START_REF] Long | Better security-efficiency trade-offs in permutationbased two-party computation[END_REF]. Since full evaluations of PPRFs have many applications beyond PCGs, to problems such as zero-knowledge proofs [KKW18, CDG + 20, KZ20, FS21], circuit garbling [START_REF] Heath | One hot garbling[END_REF], secure shuffling [START_REF] Chase | Secret-shared shuffle[END_REF] and private information retrieval [CK20, MZRA21], these results are also of independent interest.

Technical Overview

We now survey the technical tools that we use to achieve our results.

EA codes. A generator matrix H for an EA code is of the form H = BA, where B ∈ F n×N 2 is a matrix with sparse rows, and

A ∈ F N ×N 2 is the accumulator matrix, that is, ⃗ x ⊺ A = (x 1 , x 1 +x 2 , . . . , x 1 +• • •+x N ).
We propose the EA-LPN-assumption which states that samples of the form H⃗ e, where ⃗ e ∈ F N 2 is a random sparse vector, are computationally indistinguishable from uniform.

In order to provide evidence for the EA-LPN-assumption, we show that it is not susceptible to linear tests. While this class of tests is very large, they all boil down to the same general strategy: given the vector ⃗ b (which is either uniformly random or H⃗ e with ⃗ e sparse), one looks at the matrix H, chooses some nonzero vector ⃗ x ∈ F n 2 , and then checks if the dot product ⃗ x ⊺ • ⃗ b is biased towards 0. If ⃗ x ⊺ H and ⃗ e are both sufficiently dense then we can rule out the possibility that ⃗ x ⊺ •(H⃗ e) = (⃗ x ⊺ H)•⃗ e has noticeable bias. As we would like to keep ⃗ e as sparse as possible, we need to show that for every nonzero vector ⃗ x ∈ F n 2 , ⃗ x ⊺ H has large weight. In other words, we need to show that the code generated by H has good minimum distance.

We now briefly outline how we show that a random EA code has good minimum distance. It is convenient for us to assume that the coordinates of B are all sampled independently as Bernoulli random variables with probability p. Writing (y 1 , . . . , y N ) := ⃗ x ⊺ H = ⃗ x ⊺ (BA) we can view the sequence of y 1 , . . . , y N as an N -step random walk (over the randomness of B) on a Markov chain with state space {0, 1}, where the transition probabilities are governed by the Hamming weight HW(⃗ x). Furthermore the spectral gap of this Markov chain is easily computable, allowing us to apply an expander Hoeffding bound which tells us that the random walk y 1 , . . . , y N is unlikely to spend too much time on the 0 state; equivalently, it is unlikely that HW(⃗ y ⊺ ) = HW(⃗ x ⊺ H) is too small. By taking a union bound over all nonzero vectors ⃗ x ∈ F n 2 and doing a case-analysis based on HW(⃗ x), we can show that so long as p = Ω(log N/N ), except with probability 1 -1/poly(N ) the code has minimum distance Ω(N ). If one desires negligible in N failure probability this can also be obtained by slightly increasing p: e.g., p = Ω(log 2 N/N ) suffices to guarantee N -Ω(log N ) failure probability. Further, we can show that this analysis is (asymptotically) tight.

Offline-online PCGs from EA codes. We introduce the notion of offline-online PCGs, where an offline and online key are generated. Each party σ uses its offline key to generate a local offline string Y σ from which it can later use its online key to generate a (vector of) samples from the target correlation. We call the length of Y σ the storage cost, and the number of entries that must be read from Y σ to generate a single sample the output locality.

Recall that the goal of VOLE is to obtain correlations ((⃗ u, ⃗ v), (∆, ⃗ w)), where ⃗ u, ⃗ v, ⃗ w are lengthn vectors over a finite field F and ∆ ∈ F is a scalar, all chosen at random subject to satisfying the correlation ⃗ w = ∆ • ⃗ u + ⃗ v. Using PPRFs, during the offline phase the parties expand their keys to obtain strings ⃗ w ′ , ⃗ u ′ , ⃗ v ′ ∈ F N , where ⃗ u ′ is a sparse, EA-LPN noise vector and ⃗ w ′ , ⃗ v ′ are pseudorandom conditioned on satisfying ⃗ w ′ = ∆ • ⃗ u ′ + ⃗ v ′ . Further, the parties already perform the accumulation step and output ⃗ u off = A • ⃗ u ′ and ⃗ v off = A • ⃗ v ′ , and ⃗ w out = A • ⃗ w ′ and ∆, respectively. In the online phase, the

C(•) G 0 (•) G 1 (•)
Figure 1: Pictorial representation of our relaxed DCF construction. In our example the path α = 10 ∈ {0, 1} 2 is marked in blue, the box marked in red corresponds to box where β is added, and the boxes filled in gray correspond to the key of P 0 (in knowledge of α) and P 1 , respectively.

parties can then recover a tuple ((u i , v i ), (∆, w i )) by checking only an expected number of p • N of the offline strings, resulting in an online locality of p • N . We can thereby obtain offline-online PCGs with highly parallelizable and cache-friendly offline phase, and online phase with low locality (recall that we can choose p as low as

p = c • log N/N , thereby resulting in ℓ = c • log N ).
PCFs from EA codes. We have already described a general recipe for using compressing matrices H for which the LPN assumption plausibly holds to construct PCGs; indeed, we even sketched an offlineonline PCG. However, in order to use EA codes to obtain PCFs, more care is required. Recall that a PCF must behave in an incremental fashion, using the short correlated seeds to provide as many pseudorandom instances of the target correlation as required. The main challenge is that to obtain a PCF we need to set N to be superpolynomial in the security parameter, and thus computing matrixvector products of the form A • ⃗ e is too expensive. Fortunately, we can avoid the need to explicitly compute A •⃗ e by appealing to distributed comparison functions (DCFs). DCFs, which can be constructed with PRGs similarly to distributed point functions [BGI16, BCG + 21], allow one to efficiently share a comparison function f β <α : [N ] → F which maps every x < α to β and every x ≥ α to 0. When the noise ⃗ e has a regular structure (i.e., it consists of N/t unit vectors concatenated together) one can naturally view A •⃗ e (after permuting the coordinates) as a concatenation of comparison functions. We furthermore observe that for constructing PCFs for VOLE and OT we can use a relaxed version of a DCF, denoted RDCF, as we only require α to be hidden from one of the two parties.

In the following we give a high-level overview of our RDCF construction. For simplicity we assume we want to share a comparison function with range ({0, 1} λ , ⊕), although our construction generalizes to arbitrary abelian groups (G, +). Our construction follows the spirit of the DCF construction of [BCG + 21], but one party knowing α allows for significant savings. We build on PRGs G 0 , G 1 , C : {0, 1} λ → {0, 1} λ such that the concatenation of the three is a secure PRG. In Figure 1 we give a pictorial representation of the relaxed DCF construction, which we explain in the following.

To evaluate the RDCF on an input x, one traverses the tree and adds up all "C" values on the path from the root to the corresponding leaf and finally adds the "G" value of this leaf. The idea is that P 0 will add β (blinded by a "C" value) to the output, if and only if it leaves the path defined by α to the left (which happens if and only if x < α). For concreteness, say one wants to evaluate the RDCF in Figure 1 on input x = 00. Then, both parties add the first box on the second level (the first "C" value, marked in red), the first box on the third level (the second "C" value) and the second box on the third level (the "G" value of the leaf), which P 1 can both derive from its key. The corresponding output shares add up to β as required, since β is added to the first "C" value held by P 0 . Further, β remains hidden from P 0 by the pseudorandomness of the PRG C.

One of our improvements compared to the DCF construction of [BCG + 21] is that we observe that we only need "C" values on the left children, since only there the β value has to be hidden potentially. This leads to shorter keys and savings on the number of PRG evaluations.

Overall, comparing with the standard DCF construction of [BCG + 21] where each key is of size 2 log N (λ + log |F|), in our RDCF one of the party's keys is only of size λ, and the other is roughly half the size of [BCG + 21]. Further, our construction reduces the number of calls to AES (when using this to implement a PRG) by 25% on average.

Additionally, we show that in the setting where a full evaluation is feasible (i.e., where one is interested in an iterative PCG rather than a full-fledged PCF), the keys of our RDCF can be securely distributed using a simple, 2-round 2-party OT-based protocol following the techniques of [Ds17,BCG + 19a], whereas the corresponding distributed setup protocol for the DCF construction of [BCG + 21] would require log N rounds.

PCF Constructions. Given our relaxed DCF, we readily obtain PCFs for VOLE and subfield VOLE correlations, which also imply a PCF for oblivious transfer when combined with a suitable hash function [BCG + 20a]. We also show how to build a PCF for general degree-2 correlations: in particular, we get a two-party PCF for authenticated multiplication triples over any ring R, and can also support general, circuit-dependent correlations. For this, instead of comparison functions, we need a way to secret share the product of comparison functions. Fortunately, this can be done using function secret sharing for 2-dimensional interval functions [START_REF] Boyle | Function secret sharing: Improvements and extensions[END_REF], based on any PRG.

We show that our EA-LPN-based PCFs can obtain good concrete efficiency. With conservative parameter choices, which our simulated experiments show resist linear attacks, our PCF for VOLE has comparable key size to the most aggressive variant of the PCF from [BCG + 20a] (which did not have any provable security guarantees), while we need around an order of magnitude less computation. For our degree-2 PCFs, to get reasonable concrete efficiency we need to rely on more aggressive EA-LPN parameters with a lower noise weight. With this, our PCFs for VOLE/OT have key sizes of under 1MB, and takes only a few thousand PRG evaluations to compute each output. Our PCF for general degree-2 correlations (including multiplication triples, matrix triples and circuit-dependent correlations) has key sizes of around 200MB, and requires 2-3M PRG evaluations per output.

The degree-2 PCF from [BCG + 20a] do not come close to this level of efficiency, since it is not compatible with the most efficient variant of LPN they use.

Speeding up the offline phase. The final task that we set for ourselves is to improve the runtime of the offline phase for PCGs, where the offline phase requires evaluating several punctured PRFs (PPRFs) on their entire domain, a functionality called FullEval. As alluded to earlier we apply the GGM construction to obtain a PPRF from a hash function. The standard way to do this is as follows: given hash functions H 0 , H 1 (which can be modeled as random oracles (RO)) one generates the GGM tree corresponding to secret key k, that is, the depth m binary tree where the root is labeled by k and the left and right child of a node labeled by x are labeled by H 0 (x) and H 1 (x), respectively.To puncture a key at a point α ∈ {0, 1} m one gives the values of the nodes of the co-path, i.e., the siblings of each node appearing on the path indexed by α.

To save on the calls to the hash function we consider the following definition: given an RO H we define H 0 (x) = H(x) and H 1 (x) = H(x) ⊕ x. Note that this clearly fails to give a PPRF, as given H(x) and H(x) ⊕ x one can recover x and thereby distinguish the value at the punctured point from random. Nonetheless, we can show that the resulting construction yields a weaker primitive that we call a strong unpredictable punctured function (strong UPF), which informally means that given a key punctured at a point α one essentially cannot predict the value at α any better than by randomly guessing. While this primitive is weaker, we note that it already suffices for some applications (such as PCGs for OT), reducing the number of necessary calls to the random oracle for a full evaluation by half. If one subsequently hashes the right child at the leaves, we can further show that this does yield a genuine PPRF. In this way, we require only 1.5N calls to the hash function for a FullEval, whereas the standard GGM approach requires 2N calls, providing us with a 25% cost reduction.

To prove the construction yields a strong UPF, we observe that the punctured key can be equivalently sampled by choosing random values for the co-path and then programming the random oracle so as to be consistent with these choices. Assuming there are no collisions, such a punctured key is then independent of the value of the function at α, so the only way for an adversary to learn the value at α is if it happens to query H at one of m values on the path that it does not see.

To increase our savings, we consider k-ary trees for k > 2, which informally corresponds to "flattening" the GGM tree. This does incur a (k -1) log 2 k factor increase in the size of the punctured key; however, with the standard GGM construction of a PPRF the number of calls to the hash function in an invocation of FullEval now drops to (1 + 1/(k -1))N . By combining this with the first optimization, when k = 3 we can decrease the number of calls to H to 1.33N , and when k = 4 to 1.17N .

Lastly, given the current hardware support of AES, we also put forward a candidate construction of a weaker notion of UPF given an ideal invertible permutation. Recall that the standard strategy to construct a hard-to-invert function from an invertible permutation is via the Davies-Meyer construction, where H is defined as H(k) := P (k) ⊕ k for an invertible permutation P . Unfortunately, instantiating H this way clearly breaks down with our previous construction, as H 1 (k) would become equal to P (k), and hence be invertible. Instead, the idea of the construction is to set H 0 (k) := H(k) ⊕ k and H 1 (k) := H(k) + k mod 2 λ . While on first glance one might seem easy to predict given the other, we show that this is not the case, thereby giving some evidence that the corresponding candidate indeed achieves unpredictability. We cannot hope to achieve the same strong notion of unpredictability as we do with our random oracle construction though, since H(k) ⊕ k does in general leak some information about H 1 (k) := H(k) + k mod 2 λ . Still, by subsequently hashing the right child at all leaves standard unpredictability would be sufficient to obtain a true PPRF, thereby yielding a 25% cost reduction for PPRF constructions implemented with fixed-key AES. We leave the full analysis of the construction to future work.

Roadmap

We start by giving the necessary preliminaries in Section 2. In Section 3 we present EA codes and provide a security analysis of EA-LPN. In Section 4, we introduce the notion of offline-online PCGs and present a construction of offline-online PCGs for subfield VOLE from EA codes. In Section 5 we provide new constructions of PCFs based on the EA-LPN assumption. Finally, in Section 6.1, we describe our optimizations for the offline costs of PCG constructions.

Preliminaries

Preliminaries on Bias

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

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

Given t distributions (D 1 , • • • , D t ) over F n 2 , we denote by i≤t D i the distribution obtained by independently sampling ⃗ v i $ ← D i for i = 1 to t and outputting ⃗ v ← ⃗ v 1 ⊕ • • • ⊕⃗ v t .
We will use the following bias of the exclusive-or (cf. [START_REF] Shpilka | Constructions of low-degree and error-correcting ε-biased generators[END_REF]).

Lemma 2.2 Let t ∈ N be an integer, and let

(D 1 , • • • , D t ) be t independent distributions over F n 2 . Then bias( i≤t D i ) ≤ 2 t-1 • t i=1 bias(D i ) ≤ min i≤t bias(D i ).
Finally, let Ber r (F 2 ) denote the Bernoulli distribution that outputs 1 with probability r, and 0 otherwise. More generally, we denote by Ber r (R) the distribution that outputs a uniformly random nonzero element of a ring R with probability r, and 0 otherwise.

We will use a standard simple lemma for computing the bias of a XOR of Bernoulli samples:

Note that the generator matrix H sampled from C is used in the reverse direction compared to encoding: a codeword is a vector ⃗ x • H, where ⃗ x ∈ R 1×n , while the assumption is about vectors of the form H •⃗ e for ⃗ e ∈ R N . The dual LPN assumption is also called the syndrome decoding assumption in the code-based cryptography literature; in this case, H is typically seen as the parity-check matrix of a code generated by a matrix G such that H • G = 0. The dual LPN assumption as written above is equivalent to the (perhaps more common) primal LPN assumption with respect to G (a matrix G ∈ R N ×N -n such that H • G = 0), which states that G • ⃗ s + ⃗ e is indistinguishable from random, where ⃗ s

$ ← R N -n and ⃗ e $ ← D n,N (R); the equivalence follows from the fact that H • (G • ⃗ s + ⃗ e) = H • ⃗ e.
We say that a family of codes sampled by a code generation algorithm C is LPN-friendly when instantiating the general LPN assumption with these codes leads to a secure flavor of the assumption for standard noise distributions. Of course, when we call a code "LPN-friendly", this implicitly means "plausibly LPN-friendly in light of known cryptanalysis of LPN".

Examples of noise distributions. Several choices of noise distribution are common in the literature. Fix for example R = F 2 (all the distributions below generalize to other structures) and a parameter t which governs the average density of nonzero entry in a random noise vector. Then the following choices are standard:

• Bernoulli noise: the noise vector ⃗ e is sampled from Ber N t/N (F 2 ). This is the most common choice in theory papers.

• Exact noise: the noise vector ⃗ e is a uniformly random weight-t vector from F N 2 ; let us denote HW N t (F 2 ) this distribution. This is the most common choice in concrete LPN-based constructions.

• Regular noise: the noise vector ⃗ e is a concatenation of t random unit vectors from F N/t 2 ; let us denote Reg N t (F 2 ) this distribution. This is a very natural choice in the construction of pseudorandom correlation generators as it significantly improves efficiency [BCGI18,BCG + 19b,BCG + 19a] without harming security.

Examples of LPN-friendly codes. Over the years, many codes have been conjectured to be LPN friendly. Common choices include setting H to be a uniformly random matrix over F 2 (this is the standard LPN assumption), the generating matrix of an LDPC code [START_REF] Alekhnovich | More on average case vs approximation complexity[END_REF] (often called the "Alekhnovich assumption"), a quasi-cyclic code (used in several recent submissions to the NIST post-quantum competition [ABB + 17, AMBD + 18, MAB + 18] and in previous works on pseudorandom correlation generators, such as [BCG + 19a]), Toeplitz matrices [GRS08, LM13] and many more. All these variants of LPN generalize naturally to larger fields (and LPN is typically believed to be at least as hard, if not harder, over larger fields).

When designing new LPN-based primitives, different choices of code lead to different performance profiles. Established codes, such as those listed above, have the advantage of having been analyzed by experts for years or decades; however, it might happen in some applications that all established codes lead to poor performance. Plausibly secure but yet-unstudied codes could yield considerable performance improvements. In light of this, we require a heuristic to select plausibly LPN-friendly codes. Such a heuristic has been implicit in the literature for some time, and was put forth explicitly in recent works [BCG + 20a, CRR21].

From large minimum distance to LPN-friendliness. The core observation is that essentially all known attacks (attacks based on Gaussian elimination and the BKW algorithm [BKW00, Lyu05, LF06, EKM17] and variants based on covering codes [ZJW16, BV16, BTV16, GJL20], information set decoding attacks [Pra62, Ste88, FS09, BLP11, MMT11, BJMM12, MO15, EKM17, BM18], statistical decoding attacks [AJ01, FKI06, Ove06, DAT17], generalized birthday attacks [START_REF] Wagner | A generalized birthday problem[END_REF][START_REF] Kirchner | Improved generalized birthday attack[END_REF], linearization attacks [START_REF] Bellare | A new paradigm for collision-free hashing: Incrementality at reduced cost[END_REF][START_REF] Olavi Saarinen | Linearization attacks against syndrome based hashes[END_REF], attacks based on finding low weight code vectors [START_REF] Zichron | Locally computable arithmetic pseudorandom generators[END_REF], or on finding correlations with low-degree polynomials [ABG + 14, BR17]) fit in a common framework of linear tests which corresponds, roughly, to attacks where an adversary tries to detect a bias in the LPN samples by computing a linear function of these samples. (The choice of the linear function itself can depend arbitrarily on the code matrix.) Then, it is relatively easy to show that for any noise distribution D whose nonzero entries "hit any large subset" with high enough probability, the LPN assumption with respect to a code generator C and D provably resists (exponentially) all linear tests as long as a random code from C has high minimum distance with good probability. This is formalized below. Definition 2.5 (Security against Linear Tests) Let R be a ring, and let D = {D n,N } n,N ∈N denote a family of noise distributions over R N . Let C be a probabilistic code generation algorithm such that C(n, N ) outputs a matrix H ∈ R n×N . Let ε, η : N → [0, 1] be two functions. We say that the (D, C, R)-LPN(n, N ) is (ε, η)-secure against linear tests if for any (possibly inefficient) adversary A which, on input H outputs a nonzero ⃗ v ∈ R n , it holds that

Pr[H $ ← C(n, N ), ⃗ v $ ← A(H) : bias ⃗ v (D H ) ≥ ε(λ)] ≤ η(λ),
where D H denotes the distribution induced by sampling ⃗ e ← D n,N , and outputting the LPN samples H •⃗ e.

The minimum distance of a matrix H, denoted d(H), is the minimum weight of a vector in its rowspan. Then, we have the following straightforward lemma:

Lemma 2.6 Let D = {D n,N } n,N ∈N denote a family of noise distributions over R N . Let C be a proba- bilistic code generation algorithm. Then for any d ∈ N, the (D, C, R)-LPN(n, N ) assumption is (ε d , η d )-
secure against linear tests, where

ε d = max HW(⃗ v)>d bias ⃗ v (D n,N ),
and

η d = Pr H $ ←C(n,N ) [d(H) ≥ d].
For example, using a Bernoulli noise distribution of error rate t/N , for any ⃗ v of weight at least d, it holds that bias ⃗ v (Ber

n t/N (F 2 )) = (1 -2t/N ) d /2 < e -2td
/N ; that is, if the relative distance d/N of the code is a constant (i.e. the code is a good code), the bias will decrease exponentially with t. Similar calculations show that for any

⃗ v of weight at least d, bias ⃗ v (Reg N t ) ≤ (1 -2(d/t)/(N/t)) t < e -2td/N .
When the minimum distance heuristic fails. From the above, one can be tempted to conjecture that any good code, say, together with Bernoulli noise, is LPN-friendly. However, this is known to fail in at least three situations:

1. When the code is strongly algebraic. For example, Reed-Solomon codes, which have a strong algebraic structure, have high minimum distance, but can be decoded efficiently with the Berlekamp-Massey algorithm, hence they do not lead to a secure LPN instance (and indeed, Berlekamp-Massey does not fit in the linear test framework).

2. When the noise is structured (which is the case e.g. for regular noise) and the adversary can see enough samples. This opens the door to algebraic attacks such as the Arora-Ge attack [START_REF] Arora | New algorithms for learning in presence of errors[END_REF]. However, this typically requires a large number of samples: for example, using regular noise, one needs N = Ω((N -n) 2 ) for the attack to apply. In contrast, all our instances will have

N = O(N -n).
3. When R has a subring, one can always project onto the subring before performing a linear attack; this technically does not directly fit in the linear test framework. When analyzing security against linear test, one must therefore account for all subrings the attacker could first project the problem onto. In polynomial rings, the reducible case of cyclotomics is discussed in [BCG + 20b]. In integer rings like Z 2 k , one weakness is that projecting onto Z 2 can make error values become zero with probability 1/2 [START_REF] Liu | The hardness of lpn over any integer ring and field for pcg applications[END_REF], reducing the effective noise rate. To fix this, [START_REF] Liu | The hardness of lpn over any integer ring and field for pcg applications[END_REF] propose an alternative noise distribution that is provably as secure as LPN over F 2 , but with k times the noise rate. Alternatively, a plausible fix without increasing the noise rate is to choose error values to be invertible, which ensures they are non-zero in all subrings.

The above three scenarios are the only exceptions we are aware of. Hence the following natural rule of thumb: if a code is combinatorial in nature (it is not a strongly algebraic code, such as Reed-Solomon or Reed-Müller), and if the code rate is not too close to 1 (e.g. code rate 1/2, i.e. n = N/2), then being a good code makes it a plausible LPN-friendly candidate.

Puncturable Pseudorandom Functions

Pseudorandom functions (PRF), introduced in [GGM86], are keyed functions which are indistinguishable from truly random functions. 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 reveal any information about the value F.Eval(k, x). PPRFs have been introduced in [KPTZ13, [START_REF] Boneh | Constrained pseudorandom functions and their applications[END_REF][START_REF] Boyle | Functional signatures and pseudorandom functions[END_REF]. Definition 2.7 (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 ley K ∈ K, and a subset S ⊂ X of size t, outputs a punctured key K{S} ∈ K p ,

• F.Eval(K{S}, x), on input a key K{S} punctured at all points in S, and a point x, outputs F (K, x) if x / ∈ S, and ⊥ otherwise, such that no probabilistic polynomial-time adversary wins the experiment Exp-s-pPRF represented on Figure 2 with non-negligible advantage over the random guess.

Puncturable PRFs from Length-Doubling PRGs

Here, we recall how a PPRF can be constructed from any length-doubling pseudorandom generator G, 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 ℓ) . 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.

K (i) ← K (i) xi . Output K (
• 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-x1 , . . . , 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-x1 , . . . , K (ℓ)
1-x ℓ ) and start the iterative evaluation procedure from the first

K (i) 1-xi 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.

Pseudorandom Correlation Generators

We recall the notion of pseudorandom correlation generator (PCG) from [BCG + 19b]. At a high level, a PCG for some target ideal correlation takes as input a pair of short, correlated seeds and outputs long correlated pseudorandom strings, where the expansion procedure is deterministic and can be applied locally.

Definition 2.8 (Correlation Generator

) A PPT algorithm C is called a correlation generator, if C on input 1 λ outputs a pair of strings in {0, 1} n × {0, 1} m for n(λ), m(λ) ∈ poly(λ).
The security definition of PCGs requires the target correlation to satisfy a technical requirement, which roughly says that it is possible to efficiently sample from the conditional distribution of R 0 given R 1 = r 1 and vice versa. Definition 2.9 (Reverse-sampleable Correlation Generator) Let C be a correlation generator. We say C is reverse sampleable if there exists a PPT algorithm RSample such that for σ ∈ {0, 1} the correlation obtained via:

{(R ′ 0 , R ′ 1 ) |(R 0 , R 1 ) $ ← C(1 λ ), R ′ σ := R σ , R ′ 1-σ $ ← RSample(σ, R σ )} is computationally indistinguishable from C(1 λ ).
The following definition of pseudorandom correlation generators is taken almost verbatim from [BCG + 19b]; it generalizes an earlier definition of pseudorandom VOLE generator in [START_REF] Boyle | Compressing vector OLE[END_REF].

Definition 2.10 (Pseudorandom Correlation Generator (PCG) [BCG + 19b]) Let C be a reversesampleable correlation generator. A PCG for C is a pair of algorithms (PCG.Gen, PCG.Expand) with the following syntax:

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

• PCG.Expand(σ, k σ ) is a polynomial-time algorithm that given party index σ ∈ {0, 1} and a seed k σ , outputs a bit string R σ ∈ {0, 1} n .
The algorithms (PCG.Gen, PCG.Expand) should satisfy the following:

• Correctness. The correlation obtained via:

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

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

Examples of Correlations.

A random OT correlation is a pair (y 0 , y 1 ) ∈ {0, 1} 2 × {0, 1} 2 , where y 0 = (u, v) for two random bits u, v, and

y 1 = (b, u • b ⊕ v) for a random bit b.
OT correlations is perhaps the most common and fundamental type of correlation in secure computation (though many others -such as Beaver triples, authenticated Beaver triples, or function-dependent correlations -are also standard).

It is known that, to generate n pseudorandom OT correlations, it suffices to generate the following simpler correlation: Alice gets a (pseudo)random pair of length-n vectors (⃗ u, ⃗ v), where ⃗ u

$ ← F n 2 and ⃗ v ∈ F n 2 λ , and Bob gets x $ ← F 2 λ and ⃗ w ← x • ⃗ u + ⃗ v.
This correlation (known as the subfield vector-OLE correlation) can be locally converted by Alice and Bob into n pseudorandom OT correlations using a correlation-robust hash function; see [BCG + 19b] for details.

From PPRFs and LPN-Friendly Codes to PCGs

The general template for building a PCG from an LPN-friendly code was established in [BCGI18, BCG + 19b]. It uses two main ingredients: an LPN-friendly code, and a method for the two parties to obtain a compressed form of (pseudo)random secret shares ⃗ s 0 , ⃗ s 1 , satisfying the following equation (1):

⃗ s 1 = ⃗ s 0 + ⃗ e • x ∈ F n 2 λ ,
where ⃗ e ∈ {0, 1} n is a random t-parse vector held by one party, and x ∈ F 2 λ is a random field element held by the other party. Given this, the parties can locally compute H • ⃗ s 0 and

H • ⃗ s 1 = H • ⃗ s 0 + x • (H • ⃗ e).
Under the LPN assumption with respect to H, those are indeed shares of x • ⃗ u where ⃗ u = H • ⃗ e is pseudorandom. This leads to a PCG for the vector OLE correlation; the shares can also be locally converted into pseudorandom string-OTs with the hashing technique [START_REF] Ishai | Extending oblivious transfers efficiently[END_REF].

To obtain a compressed form of the shares ⃗ s 0 , ⃗ s 1 the constructions of [BCG + 19a] uses a puncturable pseudorandom function. The construction works as follows: Gen will give the sender a random key K and x, and give to the receiver t random points α j ∈ {1, . . . , N }, t punctured keys K{α j }, and the values z j = F K (α j ) + x. Given these seeds, the sender and receiver can now define the expanded outputs, for i = 1, . . . , n:

⃗ s 0 [i] = F K (i), ⃗ s 1 [i] = F K (i) i / ∈ {α 1 , • • • , α t } z j if i = α j .

Pseudorandom Correlation Functions

Pseudorandom correlation generators allow to stretch short correlated seeds into an a priori bounded pair of pseudorandom correlated strings, in a one-time expansion phase. Pseudorandom correlation functions (PCF, [BCG + 20a]), on the other hand, are much more versatile: they allow to locally generate, from a pair of short correlated keys, an arbitrary polynomial amount of pseudorandom correlations on demand, in an incremental way (i.e., the keys are indefinitely reusable). The definitions of this section are taken almost verbatim from [BCG + 20a]. To define PCFs, we must consider an incremental notion of reversesampleable correlations:

Definition 2.11 (Reverse-sampleable correlation) Let 1 ≤ τ 0 (λ), τ 1 (λ) ≤ poly(λ) be output-length functions.
Let Y be a probabilistic algorithm that on input 1 λ returns a pair of outputs (y 0 , y 1 ) ∈ {0, 1} τ0(λ) × {0, 1} τ1(λ) , defining a correlation on the outputs. We say that Y defines a reverse-sampleable correlation, if there exists a probabilistic polynomial time algorithm RSample that takes as input 1 λ , σ ∈ {0, 1} and y σ ∈ {0, 1} τσ(λ) , and outputs y 1-σ ∈ {0, 1} τ1-σ(λ) , such that for all σ ∈ {0, 1} the following distributions are statistically close:

{(y 0 , y 1 ) | (y 0 , y 1 ) $ ← Y(1 λ )} and {(y 0 , y 1 ) | (y ′ 0 , y ′ 1 ) $ ← Y(1 λ ), y σ ← y ′ σ , y 1-σ ← RSample(1 λ , σ, y σ )} It can
also be useful to consider correlations across different inputs, as e.g. in vector oblivious linear evaluation (VOLE). This is captured by the notion of reverse sampleable correlation with setup, which allows all algorithms to depend on a fixed global secret, ensuring consistency across different invocations; we omit this formal definition for conciseness and refer the reader to [BCG + 20a] for more details.

Definition 2.12 (Pseudorandom correlation function (PCF)) Let Y be a reverse-sampleable correlation with output length functions τ 0 (λ), τ 1 (λ) and let λ ≤ n(λ) ≤ poly(λ) be an input length function. Let (PCF.Gen, PCF.Eval) be a pair of algorithms with the following syntax:

• PCF.Gen(1 λ ) is a probabilistic polynomial time algorithm that on input 1 λ , outputs a pair of keys (k 0 , k 1 ); we assume that λ can be inferred from the keys.

• PCF.Eval(σ, k σ , x) is a deterministic polynomial-time algorithm that on input σ ∈ {0, 1}, key k σ and input value x ∈ {0, 1} n(λ) , outputs a value y σ ∈ {0, 1} τσ(λ) .2

We say (PCF.Gen, PCF.Eval) is a (weak) (N, B, ε)-secure pseudorandom correlation function (PCF) for Y, if the following conditions hold:

• Pseudorandom Y-correlated outputs. For every σ ∈ {0, 1} and non-uniform adversary A of size B(λ), it holds

Pr[Exp pr A,N,0 (λ) = 1] -Pr[Exp pr A,N,1 (λ) = 1] ≤ ε(λ)
for all sufficiently large λ, where Exp pr A,N,b (λ) for b ∈ {0, 1} is as defined in Figure 3. In particular, the adversary is given access to N (λ) samples.

• Security. For each σ ∈ {0, 1} and non-uniform adversary A of size B(λ), it holds

Pr[Exp sec A,N,σ,0 (λ) = 1] -Pr[Exp sec A,N,σ,1 (λ) = 1] ≤ ε(λ)
for all sufficiently large λ, where Exp sec A,N,σ,b (λ) for b ∈ {0, 1} is as defined in Figure 4 (again, with N (λ) samples).

Exp pr

A,N,0 (λ) :

for i = 1 to N (λ): x (i) $ ← {0, 1} n(λ) (y (i) 0 , y (i) 1 ) ← Y(1 λ ) b ← A(1 λ , (x (i) , y (i) 0 , y (i) 1 ) i∈[N (λ)] ) return b Exp pr A,N,1 (λ) : (k 0 , k 1 ) ← PCF.Gen(1 λ ) for i = 1 to N (λ): x (i) $ ← {0, 1} n(λ) for σ ∈ {0, 1}: y (i) σ ← PCF.Eval(σ, k σ , x (i) ) b ← A(1 λ , (x (i) , y (i) 0 , y (i) 1 ) i∈[N (λ)] ) return b

Exp sec

A,N,σ,0 (λ) : We say that (PCF.Gen, PCF.Eval) is a PCF for Y if it is a (p, 1/p, p)-secure PCF for Y for every polynomial p. If B = N , we will write (B, ε)-secure PCF for short.

(k 0 , k 1 ) ← PCF.Gen(1 λ ) for i = 1 to N (λ): x (i) $ ← {0, 1} n(λ) y (i) 1-σ ← PCF.Eval(1 -σ, k 1-σ , x (i) ) b ← A(1 λ , σ, k σ , (x (i) , y (i) 1-σ ) i∈[N (λ)] ) return b Exp sec A,N,σ,1 (λ) : (k 0 , k 1 ) ← PCF.Gen(1 λ ) for i = 1 to N (λ): x (i) $ ← {0, 1} n(λ) y (i) σ ← PCF.Eval(σ, k σ , x (i) ) y (i) 1-σ ← RSample(1 λ , σ, y (i) σ ) b ← A(1 λ , σ, k σ , (x (i) , y (i) 1-σ ) i∈[N (λ)] ) return b
The above definition captures a notion of weak pseudorandom function, where security is only required to hold given random adversarial queries. As for PRFs, one can also strengthen the definition to strong PCFs, which allow arbitrary adversarial queries; a formal definition is given in [BCG + 20a]. As shown in [BCG + 20a], any weak PCF can be turned into a strong PCF in the random oracle model, by hashing the input before feeding it to the function.

Expand-Accumulate Codes

In this section we introduce expand-accumulate codes, which are defined by the product H = BA for a sparse expanding matrix B and the accumulator matrix A. We conjecture that the LPN problem is hard to solve for this matrix ensemble and provide theoretical evidence for this conjecture by demonstrating that it resists linear attacks.

Expand-Accumulate Codes, and the EA-LPN Assumption

First, we formally define the accumulator matrix. Definition 3.1 (Accumulator Matrix) For a positive integer N and ring R, the accumulator matrix A ∈ R N ×N is the matrix with 1's on and below the main diagonal, and 0's elsewhere.

In particular, if A⃗ x = ⃗ y with ⃗ x, ⃗ y ∈ R N , we have the following relations:

y i = i j=1 x j ∀i ∈ [N ] y i := x i + y i-1 ∀2 ≤ i ≤ N . (1)
Note in particular that (1) guarantees that the vector-matrix product A⃗ x can be computed with only N -1 (sequential) ring addition operations. In particular, when R is the binary field F 2 , this requires just N -1 xor operations. Furthermore, this can be computed even more efficiently in parallel, which is a major benefit of our construction. For more details, see Section 6.1. We now formally introduce expand-accumulate (EA) codes, which underline our main constructions of offline-online PCGs. Definition 3.2 (Expand-Accumulate (EA) codes) Let n, N ∈ N with n ≤ N and let R be a ring. For a desired density p ∈ (0, 1), a generator matrix for an expand-accumulate (EA) code is sampled as follows:

• Sample row vectors ⃗ r ⊺ 1 , ⃗ r ⊺ 2 , . . . , ⃗ r ⊺ n $ ← Ber N p (R) independently and put B =      ⃗ r ⊺ 1 ⃗ r ⊺ 2 . . . . . . . . . ⃗ r ⊺ n     
.

• Output the matrix-matrix product BA, where A ∈ R N ×N is the accumulator matrix.

We use EA(n, N, p, R) to denote a code sampled from this distribution, and the sampling of the corresponding generator matrix is denoted

H $ ← EAGen(n, N, p, R). When the ring R is omitted it is assumed R = F 2 .
Remark 3.3 While it is more standard in the coding-theoretic literature to use G for a generator matrix of a code, as we are interested in the dual LPN assumption connected to a code, we actually view H as the parity-check matrix for the code for which the EA code is the dual. Thus, as H is the standard notation for a parity-check matrix, we have chosen to use this notation for the generator matrix of an EA code.

Remark 3.4 (Connection to RA codes) Our definition of expand-accumulate codes is heavily inspired by the definition of repeat-accumulate (RA) codes. For a desired rate 1 = 1/ℓ with ℓ ∈ N, such a code has generator matrix R ℓ ΠA, where

• R ℓ ∈ F (N/ℓ)×N 2
is the matrix which repeats each coordinate ℓ times, i.e.,

⃗ x ⊺ R ℓ = (x 1 , x 1 , . . . , x 1 ℓ times , x 2 , x 2 , . . . , x 2 ℓ times , . . . , x N/ℓ , x N/ℓ , . . . , x N/ℓ ℓ times
).

• Π ∈ F N ×N 2 is a uniformly random permutation matrix.

• A is the accumulator matrix as defined in Definition 3.1.

Unfortunately, it is known that such codes cannot be asymptotically good: if the rate is constant, then the minimum distance is at most N -Ω(1) . One solution to this problem is to have multiple rounds of permuting and accumulating: for example, 2 rounds of accumulating (so called RAA codes) already achieve asymptotic goodness, and with a larger (constant) number of rounds we can approach the Gilbert-Varshamov bound. However, for our desired applications having a single accumulation step is desirable. Firstly, this is maximally cache-friendly. Secondly, for our construction of PCFs we crucially rely on the structure of the noise vector after accumulating, and this structure is destroyed if we accumulate twice.

Remark 3.5 (Connection to codes of Tillich and Zémor) Upon completing our work we discovered that EA codes are in fact quite similar to a class of codes studied by Tillich and Zémor [START_REF] Tillich | On the minimum distance of structured ldpc codes with two variable nodes of degree 2 per parity-check equation[END_REF]. They presented their codes via parity-check matrices, but careful observation shows that the codes are indeed a natural variant of a rate 1/2 EA code (the rows of the corresponding matrix B are not independently sampled, but they are chosen to be sparse, which is qualitatively what one wants from an EA code). Applying these codes for cryptographic tasks appears to be a promising avenue for future research.

Markov Chains

In order to analyze EA codes, we will make use of an expander Hoeffding bound. We provide in this subsection the necessary background on the Markov chains and state the bound we use.

A (discrete-time and finite) Markov chain consists of a finite set V called the state space and a transition matrix P ∈ R V×V with the property that all row sums are equal to 1 and the entries are all non-negative. For u, v ∈ V, one interprets P u,v as the probability of transitioning from state u to v, which we denote as P u,v = Pr [ u → v ]. P then naturally describes a random walk in the following sense. Let ⃗ ν ∈ R V denote a distribution over the state space V, so ν v is the probability of sampling state v. Consider the following procedure:

• First, sample a state V 0 ∈ V according to ν.

• Then, sample an N step random walk V 0 , V 1 , . . . , V N according to P . I.e., for i = 1, . . . , N , transition from state V i-1 to state V i with probability

P Vi-1,Vi . A distribution ⃗ π ∈ R V is called a stationary distribution if ⃗ π ⊺ P = ⃗ π ⊺ .
In other words, it is a left eigenvector for P with eigenvalue 1.

In this work, all Markov chains are assumed to be irreducible, which means that any state can be reached from any other any state in a finite number of steps. That is, if one constructs the directed graph with vertex set V with edges (u, v) whenever P u,v > 0, we require this graph to be strongly connected. In this case, it is known that the Markov chain has a unique stationary distribution. Furthermore, an irreducible Markov chain is reversible if

∀u, v ∈ V, π u P u,v = π v P v,u .
In this work, we will make use of tail-bounds for Markov chains. That is, suppose we have a function f : V → [0, 1] and define µ := E V ∼⃗ π [f (V )] to be its expected value under the distribution ⃗ π. We would like to understand the probability that the random variable S N = N i=1 f (V i ) deviates significantly from its expected value N •µ as N grows, where (V 1 , . . . , V N ) is an N -step random walk. This can be quantified via P 's second eigenvalue: by the classical theory of nonnegative matrices, the eigenvalues of

P are 1 = λ 1 > λ 2 ≥ • • • ≥ λ |V| ≥ -1
, where the strict inequality between λ 1 and λ 2 follows from irreducibility. We call λ 2 the second largest eigenvalue of P and, when λ 2 is small (equivalently, the spectral gap 1-λ 2 is large), we find that the random variable S N is very concentrated. This is the topic of "expander Hoeffding/Chernoff bounds." The version which is most suitable for our application is due to Leon and Perron [START_REF] Carlos | Optimal hoeffding bounds for discrete reversible markov chains[END_REF].

Theorem 3.6 (Expander Hoeffding Bound) Let (V, P ) denote a finite, irreducible and reversible Markov chain with stationary distribution ⃗ π and second largest eigenvalue λ.

Let f : V → [0, 1] with µ = E V ∼⃗ π [f (V )]. For any integer N ≥ 1, consider the random variable S N = N i=1 f (V i ), where V 0 is sampled uniformly at random from V and then V 1 , . . . , V N is a random walk starting at V 0 .
Then, for λ 0 = max(0, λ) and any ε > 0 with µ + ε < 1, the following bound holds:

Pr [ S N ≥ N (µ + ε) ] ≤ exp -2 1 -λ 0 1 + λ 0 N ε 2 .
When we apply the above theorem, it will be for 2-state Markov chain with uniform stationary distribution ⃗ π = (1/2, 1/2), and for our function of interest µ = 1/2. However, the initial state will not be uniform; it will be equal to one of the two states with probability 1. We can easily derive from the above theorem a corollary which is sufficient for our purposes, wherein the above probability estimate only degrades by a factor of 2.

Corollary 3.7 Let (V, P ) denote a finite, irreducible and reversible Markov chain with V = {v 0 , v 1 }, stationary distribution ⃗ π = (1/2, 1/2) and second largest eigenvalue λ.

Let f : V → [0, 1] with 1/2 = E V ∼⃗ π [f (V )]. For any integer N ≥ 1, consider the random variable SN = N i=1 f (V i ), where V 0 = v 0 with probability 1 and then V 1 , . . . , V N is a random walk starting at v 0 .
Then, for λ 0 = max(0, λ) and any ε > 0 with 1/2 + ε < 1, the following bound holds:

Pr SN ≥ N (1/2 + ε) ≤ 2 exp -2 1 -λ 0 1 + λ 0 N ε 2 .
Proof. Applying the total probability rule,

Pr [ S N ≥ N (1/2 + ε) ] = Pr [ S N ≥ N (1/2 + ε)|V 0 = v 0 ] • Pr V0∼⃗ π [ V 0 = v 0 ] + Pr [ S N ≥ N (1/2 + ε)|V 0 = v 1 ] • Pr V0∼⃗ π [ V 0 = v 1 ] = Pr [ S N ≥ N (1/2 + ε)|V 0 = v 0 ] • 1 2 + Pr [ S N ≥ N (1/2 + ε)|V 0 = v 1 ] • 1 2 ≥ Pr SN ≥ N (1/2 + ε) • 1 2 .
The result now follows readily from Theorem 3.6. □

The EA-LPN Assumption and Security Analysis

In

{(H, ⃗ b) | H $ ← EAGen(n, N, p, R), ⃗ e $ ← D N (R), ⃗ b ← H • ⃗ e} c ≈ {(H, ⃗ b) | H $ ← EAGen(n, N, p, R), ⃗ b $ ← R N }.
In order to provide evidence for the EA-LPN-assumption, we will show that it is secure against linear tests (Definition 2.5), at least when R = F 2 . To do this, recalling Lemma 2.6, it suffices to show that d(H) is large (with high probability). The technical core of our proof is the following bound on the probability that a message vector ⃗ x ∈ F n 2 of weight r is mapped to a codeword of weight ≤ δN .

Lemma 3.9 Let n, N ∈ N with n ≤ N and put R = n N . Fix p ∈ (0, 1/2) and δ > 0, and put β = 1/2 -δ. Let r ∈ N and let ⃗ x ∈ F n 2 be a vector of weight r. Define ξ r = (1 -2p) r . Then,

Pr HW(⃗ x ⊺ H) ≤ δN | H $ ← EAGen(n, N, p) ≤ 2 exp -2 1 -ξ r 1 + ξ r N β 2 .
To prove this lemma, we imagine revealing the coordinates of the random vector ⃗ x ⊺ H one at a time, and observe that this can be viewed as a random walk on a Markov chain with state space {0, 1} and second eigenvalue ξ r . We can then apply Corollary 3.7 to guarantee that such a random walk is unlikely to spend too much time on the 0 state, which is equivalent to saying that the random vector ⃗ x ⊺ H does not have too small weight. Proof. Denote the columns of B as ⃗ c 1 , ⃗ c 2 , . . . , ⃗ c N ∈ F n 2 , and observe that

H = BA =   • • • ⃗ (c 1 + • • • + ⃗ c N ) (⃗ c 2 + • • • + ⃗ c N ) • • • ⃗ c N • • •   .
Hence, for a fixed vector

⃗ x ∈ F n 2 , if ⃗ y ⊺ = ⃗ x ⊺ H = ⃗ x ⊺ BA, we have (y 1 , y 2 , . . . , y N ) = (⃗ x ⊺ • (⃗ c 1 + • • • + ⃗ c N ), ⃗ x ⊺ • (⃗ c 2 + • • • + ⃗ c N ), . . . , ⃗ x ⊺ • (⃗ c 1 + • • • + ⃗ c N )) .
Note that each entry of B is sampled independently according to Ber p (F 2 ). Hence, the ⃗ c i 's are independently sampled as ⃗ c i ← Ber n p (F 2 ). We furthermore have the following recursive relation:

y N := ⃗ x ⊺ • ⃗ c N , y i := ⃗ x ⊺ • ⃗ c i + y i+1 ∀1 ≤ i ≤ N -1 .
Lastly, as HW(⃗ x) = r the Piling-up Lemma (Lemma 2.3) tells us that each ⃗ x ⊺ • ⃗ c i is distributed as Ber pr (F 2 ) where

p r := 1 -(1 -2p) r 2 = 1 -ξ r 2 .
Defining

z i = y N -i for i ∈ [N ],
we may therefore view the sequence (z 1 , z 2 , . . . , z N ) as the outcome of an N -step random walk on a Markov chain with state space {v 0 , v 1 } (corresponding to 0 and 1, respectively) which starts in state z 0 = v 0 . The transition probabilities are

Pr [ v 0 → v 0 ] = Pr [ v 1 → v 1 ] = 1 + ξ r 2 , Pr [ v 0 → v 1 ] = Pr [ v 1 → v 0 ] = 1 -ξ r 2 .
The transition matrix of this Markov chain is

1+ξr 2 1-ξr 2 1-ξr 2 1+ξr 2 = 1 -ξ r 2 J + ξ r I ,
where J is the 2 × 2 all-1's matrix and I is the 2 × 2 identity matrix. It follows readily that the secondlargest eigenvalue of this matrix is ξ r and that its stationary distribution is uniform, i.e., (1/2, 1/2). It is also immediate that this Markov chain is reversible. We are thus in position to apply Corollary 3.7 with f :

V → [0, 1] defined via f (v 0 ) = 1 and f (v 1 ) = 0. Thus, if V 1 , . . . , V N denotes a N step random walk starting at state V 0 = v 0 and SN = N i=1 f (V i ), we find Pr HW(⃗ x ⊺ H) ≤ δN | H $ ← EAGen(n, N, p) = Pr Sn ≥ (1/2 + β)N ≤ 2 exp -2 1 -ξ r 1 + ξ r N β 2 .
□ We now state the main theorem of this section.

Theorem 3.10 Let n, N ∈ N with n ≤ N and put R = n N , which we assume to be a constant. Let C > 0 and set p = C ln N N ∈ (0, 1/2). Fix δ ∈ (0, 1/2) and put β = 1/2 -δ. Assume the following relation holds:

R < min 2 ln 2 • 1 -e -1 1 + e -1 • β 2 , 2 e (2)
Then, assuming N is sufficiently large we have

Pr d(H) ≥ δN | H $ ← EAGen(n, N, p) ≥ 1 -2 n r=1 n r exp -2 1 -ξ r 1 + ξ r N β 2 (3) ≥ 1 -2RN -2β 2 C+2 .
Informally, the conclusion is that when p = Θ(log N/N ) a constant rate EA code will have distance Ω(N ) with probability 1-1/poly(N ). If one would like the failure probability to be negligible in N this can still be achieved by increasing p: for example, if p = Θ(log 2 N/N ) the failure probability is N -O(log N ) . Proof. By the union bound, we may upper bound

Pr d(H) ≤ δN | H $ ← EAGen(n, N, p) = Pr ∃⃗ x ∈ F n 2 \ { ⃗ 0} s.t. HW(⃗ x ⊺ H) ≤ δN | H $ ← EAGen(n, N, p) ≤ n r=1 ⃗ x∈F n 2 HW(⃗ x)=r Pr HW(⃗ x ⊺ H) ≤ δN | H $ ← EAGen(n, N, p) . (4)
Applying Lemma 3.9, we may upper bound

(4) ≤ k r=1 ⃗ x∈F n 2 HW(⃗ x)=r 2 exp -2 1 -ξ r 1 + ξ r N β 2 = 2 n r=1 n r exp -2 1 -ξ r 1 + ξ r N β 2 , (5)
where we have again set ξ r = (1 -2p) r . We now bound each term in the above sum. We begin by considering the case r = 1.

Case r = 1. For this case, we begin by noting that

1 -ξ 1 1 + ξ 1 = 1 -(1 -2p) 1 + (1 -2p) = 2p 2(1 -p) = p 1 -p ≥ p .
Thus, we may bound

n 1 exp -2 1 -ξ 1 1 + ξ 1 N β 2 ≤ n • exp(-2pN β 2 ) = RN • exp -2 C ln N N N β 2 = RN • exp -2Cβ 2 ln N = RN • N -2Cβ 2 = RN -2Cβ 2 +1 . (6)
We now turn to larger values of r. It is most convenient to look at

- 1 N ln n r exp -2 1 -ξ r 1 + ξ r N β 2 = 2β 2 1 -ξ r 1 + ξ r - 1 N ln n r . ( 7
)
Our target is to lower bound (7) ≥ Ω(log N/N ). We consider two more cases depending on the value of r.

Case 2: 2 ≤ r ≤ N 2C ln N . First, as 1 + ξ r ≤ 2, it suffices to lower bound

β 2 (1 -ξ r ) - 1 N ln n r = β 2 1 -1 - 2C ln N N r - 1 N ln RN r . ( 8
)
We will use the elementary inequality e

-z ≤ 1-z 2 , which is valid for all z ∈ [0, 1]. 3 As r ≤ N 2C ln N we have 1 - 2C ln N N r ≤ e -r 2C ln N N ≤ 1 - Cr ln N N .
Thus, applying also the standard upper bound a b ≤ ea b b , we may lower bound (8) via

β 2 1 -1 - 2C ln N N r - 1 N ln RN r ≥ β 2 1 -1 - Cr ln N N - r N ln eRN r = β 2 Cr ln N N - r N ln eRN r = r N ln N Cβ 2 • r eRN .
Clearly, the above bound decreases as r decreases. Hence, we substitute in r's minimum value r = 2:

2 N ln N Cβ 2 • 2 eRN ≥ 1 N ln N 2Cβ 2 -1 (9)
where the last inequality uses the assumption R ≤ 2/e. This completes the argument in this case.

Case 3: r ≥ N 2C ln N . In this case, we may bound

1 - 2C ln N N r ≤ e -r 2C ln N N ≤ e -1 and 1 N ln n r = 1 N ln RN r ≤ 1 N ln 2 RN = R ln 2 .
Hence, in this case we may lower bound (7) as

2β 2 1 -1 -2C ln N N r 1 + 1 -2C ln N N r - 1 N ln n r ≥ 2β 2 1 -e -1 1 + e -1 -R ln 2 > 0 , (10)
where the strict inequality follows from (2). Note that, for sufficiently large N , the lower bound in (9) is smaller than that in (10). Thus, for each 2 ≤ r ≤ n, we may upper bound

n r exp -2 1 -ξ r 1 + ξ r N β 2 ≤ e -1 N ln N 2Cβ 2 -1 = N -2Cβ 2 +1 .
Returning now to (4), and recalling the bound for r = 1 from (6), we therefore have

2 n r=1 n r exp -2 1 -ξ r 1 + ξ r N β 2 ≤ (2RN ) • N -2Cβ 2 +1 = 2RN -2Cβ 2 +2 .
This completes the proof. □

Other Variants

In our investigation of EA codes we considered many variants. We begin by discussing other models for sampling expand-accumulate codes.

Different expanding matrices. There are other natural ways to choose the matrix for expanding the input prior to accumulating: that is, the B matrix from Definition 3.2. In order to be useful for efficient offline-online PCGs, we need to ensure that every row of B is as sparse as possible.

The following are natural choices for the distribution of the rows of B. We conjecture that the behaviour of any of the random codes generated by BA should be comparable in terms of minimum distance (and hence, in terms of resistance to linear attacks). Let ℓ ∈ N be the row-weight parameter and let R be a ring. We consider the following distributions for independently sampling the rows ⃗ r 1 , . . . , ⃗ r n of the matrix B.

• Sample each ⃗ r i as a uniformly random vector in R N of weight ℓ, i.e., sample ⃗ r i ← HW N ℓ (R). We denote the sampling of the matrix

H = BA ∈ R n×N by H $ ← EAGenExa(n, N, ℓ, R).
• Sample each ⃗ r i as the concatenation of ℓ uniformly random unit vectors from R N/ℓ , i.e., sample ⃗ r i ← Reg N ℓ (R). We denote the sampling of the matrix

H = BA ∈ R n×N by H $ ← EAGenReg(n, N, ℓ, R). 4
The above distributions might be preferable in practice. For example, if the noise is exact we do not have to worry about rows of abnormally large weight, in which case the online phase would be more efficient.

We conjecture that EA codes when the rows of the matrix B are sampled according to the exact distribution or the regular distribution should still be asymptotically good. Formally: Conjecture 3.11 There exist constants R, δ, C > 0 such that the following holds. Let N ∈ N, put n = ⌊RN ⌋ and let ℓ ∈ N be an integer such that ℓ ≥ C ln N . Then

Pr d(H) ≥ δN | H $ ← EAGenExa(n, N, ℓ, F 2 ) ≥ 1 -1/poly(N ) .
Assume further ℓ|N . Then also

Pr d(H) ≥ δN | H $ ← EAGenReg(n, N, ℓ, F 2 ) ≥ 1 -1/poly(N ) .
While we have left the 1/poly(N ) failure probability in the statement unspecified, be do not see any reason that the failure probability should deviate significantly from the O(N -2Cβ 2 +2 ) bound provided in Theorem 3.10.

Unfortunately, the Markov chain-based analysis of Lemma 3.9 does not appear to port over naturally when the rows of B are sampled according to either of these distributions, as the columns of B then fail to be independent.

Nonetheless, we endeavour to provide further evidence for this conjecture. We do this by considering the following matrices: For these small parameters, we are able to explicitly compute the weight distribution of the codes generated by these (randomly sampled) matrices. That is, we can compute the vector (a 0 , a 1 , . . . , a 55 ) ∈ N 56 where a j is the number of ⃗ x ∈ F 11 2 for which HW(⃗ x ⊺ H i ) = j. For each of these sampling procedures, we ran 100 trials and computed the average weight distribution. The results are plotted in Figure 5.

While the broad conclusion is that the weight distributions all appear to be relatively similar, if anything it appears that regular noise is best in the sense that it puts the most mass on heavier weights. Providing theoretical guarantees for these other row distributions remains an open problem meriting further study.

Arbitrary rings. Theorem 3.10 applies only to the case of the binary field, and one can naturally wonder about the distance over arbitrary rings. We conjecture that the minimum distance should at the very least not degrade over larger rings; in fact, we believe that it should increase commensurately. However, the expander Hoeffding bound that we apply does not appear to work well in this case; in particular, we are forced to require the rate R ≪ 1 ln q , where q is the size of the ring R. However, we believe that this is an artifact of the proof. To justify this suspicion, we consider the following:

• H 1 $ ← EAGenExa(4, 20, 4, F 17 ); • H 2 $ ← EAGenExa(4, 20, 4, Z 16 );
Further, we consider the sampling procedure where each row is sampled to be a uniformly random vector of weight ℓ where all the nonzero coordinates take value 1. 5 We denote the sampling procedure as

H $ ← EAGenExa * (k, n, ℓ, R). Let also • H 3 $ ← EAGenExa * (4, 20, 4, F 17 ); • H 4 $ ← EAGenExa * (4, 20, 4, Z 16 ).
For these small parameters, we are able to explicitly compute the weight distribution of the codes generated by these (randomly sampled) matrices. For each of these sampling procedures, we ran 100 trials and computed the average weight distribution, which we subsequently normalized by 100/q 4 where q is the ring size. The results are provided in Figure 6. q 4 where q is the ring size. Blue corresponds to H 1 ; red to H 2 ; yellow to H 3 ; and green to H 4 .

The conclusions we draw are the following. First, the weight distribution only appears to get better (in the sense that more mass moves towards higher weight vectors) as q increases. Secondly, we do not notice too much difference between the case where the nonzero entries are all set to 1, although the effect is more noticeable for Z 16 than F 17 . However, we caution that for codes over Z 2 k the amount of security one gets is no greater than the amount one gets over Z 2 as one can always perform a modular reduction/projection attack to leak one bit at a time (such an attack is not covered by the linear attacks framework).

To put it concisely, our experiments suggest that the concrete time to break the EA-LPN assumption should only increase as the characteristic of the ring increases (at least, assuming one is restricted to modular reduction followed by linear attacks). Proving this theoretically remains an interesting challenge for future work.

Tightness of the Security Analysis

As we are interested in concrete parameters, we are naturally motivated to ask whether or not the analysis of Theorem 3.10 is tight. We now explore certain avenues to potentially improve the above result, especially when dealing with concrete parameters.

Rate-Distance Tradeoff. One aspect of Theorem 3.10 that one could hope to improve is the ratedistance tradeoff (2). Inspecting the proof, we see that this assumption was used in bounding the probability that vectors ⃗ x ∈ F n 2 of weight at least N C ln N have an encoding of weight at most δN . Indeed, if n = RN is too large then we are unable to guarantee that it is not the case that there are exponentially many vectors ⃗ x of weight ≈ n log N that have an encoding of weight at most δN . However, even if such attack vectors exist, it is not clear to us that any efficient adversary could find one. Recall that proving that EA codes have good minimum distance shows that they are not susceptible to linear attacks, without the requirement that the algorithm implementing the linear attack be efficient. On the other hand, the EA-LPN assumption only implies that it is computationally infeasible to find an attack vector whose encoding has low weight.

Therefore, it is reasonable to believe that for values of R = n/N and δ that violate the inequality (2), the code generated by H $ ← EAGen(n, N, p) could still have pseudodistance δ. We provide below a formal definition of pseudodistance. (For concreteness, the definition is specialized to the case of F 2 , although the definition can easily be generalized to other rings.) Definition 3.12 (Pseudodistance) Let C be a probabilistic code generation algorithm such that C(n, N ) outputs a matrix H ∈ F n×N 2 . For a weight parameter δ(λ), we say that C(n(λ), N (λ)) has pseudodistance δ(λ) if for every PPT algorithm A there is a negligible function negl such that

Pr A(H) = ⃗ x s.t. ⃗ x ̸ = ⃗ 0 and HW(⃗ x ⊺ H) ≤ δN | H $ ← C(n, N ) ≤ negl(λ) .
The above definition has appeared previously in the literature, often referred to as the binary shortest vector problem (bSVP) [AHI + 17]. 6 We consider it reasonable to suspect that, so long as R = n/N and δ satisfy δ < (1 -R)/2,7 EAGen(n, N, p) has pseudodistance δ assuming p = Ω(log N/N ).

Density of B, theoretically. As a conceptual question, one can ask how dense the matrix B must be. Note that the density of a row of B greatly influences the efficiency of the online phase of our PCG construction, so this is an important point to understand. Theorem 3.10 requires each row to have (expected) density Ω(log N ), and it is reasonable to wonder if the rows could have constant density.

If we are hoping for the code to be asymptotically good, i.e., both rate and relative distance constant, this is unfortunately not possible. Indeed, in this case we can show that, in expectation, at least δ ℓ n vectors of weight 1 have encodings of weight at most δ. Note that ⃗ e ⊺ 1 B, . . . , ⃗ e ⊺ n B are a collection of n random vectors with distribution Ber N ℓ/N (F 2 ); thus, we analyze the probability that ⃗

x ⊺ A has weight ≤ δN if ⃗ x $ ← Ber N ℓ/N (F 2 ).
Note that if all of ⃗ x's nonzero coordinates land in the interval {N -δN + 1, . . . , N }, then ⃗ x ⊺ A will have weight at most δN , and this event occurs with probability (1 -ℓ/N ) N (1-δ) ≈ e -ℓ(1-δ) ≥ δ ℓ . As there are n unit vectors, this implies in expectation that there will be at least δ ℓ n weight one messages with weight ≤ δN encoding. If 1/ℓ, δ, and R = n/N are all Ω(1), then we find that there are linearly many codewords of weight at most δN . A similar analysis applies for other choices of row distribution: so long as their expected weight is ℓ, the weight of the vector after accumulation will be at most δN with probability roughly δ ℓ .

The above is not too surprising in light of the known impossibility results concerning RA codes. Recalling Remark 3.4, for such a code the matrix B ∈ F N/ℓ×N 2 is chosen so that the rows are all uniformly random of weight ℓ, subject to the constraint that every column has weight 1. For ℓ = O(1), it is know that the minimum distance of such codes is at most O(N 1-1/(ℓ-1) ) [START_REF] Bazzi | The minimum distance of turbo-like codes[END_REF]. Thus, we cannot hope to have an asymptotically good code with just one round of accumulation.

Better parameters with rejection sampling. By the above discussion and, indeed, the proof of Theorem 3.10, low-weight codewords in an EA code are typically obtained as the encodings of low-weight messages. If one is willing to spend a bit more time to check the quality of the code after sampling it by checking the weight of low-weight messages, it is reasonable to expect that this would improve the failure probability.

More specifically, upon sampling the generator matrix H $ ← EAGen(n, N, p), one could run the following tester T : for each nonzero message vector ⃗ x ∈ F n 2 of weight at most a, compute ⃗ x ⊺ H, and verify that it has weight at least δN . When a is a small constant, such a test is feasible. Moreover, heuristically one should expect that if H passes the test then the probability that it fails to have distance δ should be at most

n r=a+1 n r exp -2 1 -ξ r 1 + ξ r N β 2 (11)
which is just the bound in (5) where we have removed the terms for r ≤ a. (Of course, this assumes that the probability HW(⃗ x ⊺ H) ≤ δN for non ⃗ x ∈ F n 2 of weight at least a + 1 does not decrease if we condition on the event HW(⃗ y ⊺ H) > δN for all nonzero ⃗ y ∈ F n 2 of weight at most a. But we feel that this is reasonable to suspect, even if it appears very difficult to prove formally.)

Already when a = 1, we can see some noticeable savings. Indeed, just with a = 1 we extrapolated the value of (11) for n = 2 20 , 2 25 and 2 30 with N = 5n. For C = 2.3 our estimate of the failure probability for the EA code having distance at least 0.005N or 0.02N is noticeably better than the bound from Figure 8. The result is summarized in Figure 7. We see that the failure probability decreases in all cases by a factor of roughly 100.

Concrete Parameter Choices

Conservative parameters. In this section, we consider relatively conservative parameter choices, and compute the failure probability as given by (3). That is, instead of computing the probability that d(H) ≤ δN for H ← EA(n, N, p) as 2RN -2Cβ 2 +2 (where, as in the theorem statement, β = 1/2 -δ, R = n/N and p = C ln N N ) we endeavour to numerically compute the bound

C = 2.3 δ n
2 n r=1 n r exp -2 1 -ξ r 1 + ξ r N β 2 ,
where as before ξ r = (1 -2p) r . For our applications we would like n = 2 20 , 2 25 and 2 30 . It is reasonable to choose R = 0.2, implying N = 5 • n. However, computing (3) for these values of n, N is beyond our computational resources, so we instead computed the failure probability for smaller values n = 29 , 2 10 , . . . , 2 15 , and extrapolated the failure probability.8 . Our results are summarized in Figure 8. For context, we recall Lemma 2.6 which translates minimum distance into security against linear tests. It says that if H $ ← EAGen(n, N, p) has minimum distance δN with probability at least η(λ) and the error vector ⃗ e ∈ F N 2 has (expected) weight t (e.g., ⃗ e $ ← Ber N t/N (F 2 ), HW N t/N (F 2 ) or Reg N t (F 2 )), then if we want (2 -λ , η(λ))-security against linear tests we require e -2tδ ≤ 2 -λ , i.e., t ≥ (ln 2)•λ 2δ . Looking at Figure 8, for n = 2 30 and N = 5n, if t = 664 then we have t > (ln 2)•98 2•0.05 , which implies that

H $ ← EAGen n, N, 3 ln N N is (2 -98-log 2 5 , 0.00402)-secure 9 against linear tests. Decreasing C, if H $ ← EAGen n, N, 2.3 ln N N
then so long as t ≥ 1658 it is (2 -98-log 2 5 , 0.124)-secure against linear tests. For all of the extrapolated values in Figure 8, we provide the necessary number of noisy coordinates for 128 bits of security against linear tests. Density of B, concretely. However, when it comes to concrete parameter choices, it is reasonable to be more aggressive. Our intuition, which is guided by the proof of Theorem 3.10, tells us that if there is to be a low-weight vector in an EA code, then it is likely obtained as the encoding of a low-weight message. In particular, if an EA code has distance d it is probably because H $ ← EAGen has a row of weight d. Furthermore, while there could very well be lower weight vectors in the EA codes, we do not see an easy means to find these vectors. Recalling the discussion of the notion of pseudodistance, this already implies that the construction could be secure against efficient linear attacks. Being aggressive, we consider choosing smaller values of ℓ, and then empirically estimate the minimum (relative) weight of a row of an EA matrix H. For our applications we would like n = 2 20 , 2 25 and 2 30 . It is reasonable to choose R = 0.2, implying N = 5 • n. For ℓ = 7, 9, 11, we endeavour to empirically estimate the minimum row weight of a matrix H $ ← EAGenReg(n, 5 • n, ℓ).10 However, for this value of n this is beyond our computational resources. Instead, we computed the average minimum row weight over 100 trials for smaller values n = 2 9 , 2 10 , . . . , 2 15 , and extrapolated the failure probability. We used exponential regression in log 2 n, which fit the data very well (R values all in excess of 0.99). The results are given in Figure 9b.

These experiments embolden us to make the following sort of conjecture: given a matrix H $ ← EAGenReg(2 30 , 5 • 2 30 , 7), we expect it to be hard to find a vector in the row-span of H with relative weight less than 0.02, even though we expect there to exist (many) such vectors. We leave testing of the validity of this assumption as an interesting challenge for future work.

Aggressive parameters. In the previous section, we could show, e.g., that when C = 3 the minimum distance of the code generated by

H $ ← EAGen(2 30 , 5 • 2 30 , C ln(5•2 30 ) 5•2 30
) is very likely to exceed 0.05 • 5 • 2 30 . But again, recalling our discussion of pseudodistance (Definition 3.12), it seems very difficult to find a codeword of small weight. In particular, assuming δ < (1 -R)/2 it is plausible that it is hard to find a codeword of weight less than δ (at least, assuming C is sufficiently large to guarantee no rows have weight that small). Thus, taking R = 0.2 it is reasonable to suspect that it is hard to find a codeword of weight < 0.4 • N . This implies the following values of t are sufficient for 128 bits of security: for n = 2 20 , t = 94; for n = 2 25 , t = 90; for n = 2 30 , t = 85.

Further, if we make R smaller so that it is plausibly hard to find a codeword of weight less than ≈ 0.5N , the following values of t plausibly yield 128 bits of security: for n = 2 20 , t = 75; for n = 2 25 , t = 72; for n = 2 30 , t = 68.

Relation to Silver. [CRR21] also introduced a new code family, called Silver. However, their security analysis is purely based on computer simulation. Concretely, the authors of [START_REF] Couteau | Silver: Silent VOLE and oblivious transfer from hardness of decoding structured LDPC codes[END_REF] sampled random choices of code parameters, and sampled many instances of the code for small value of n. Then, they approximated the minimum distance for each sample by encoding low-weight vectors, and estimated the variance from the distance distribution. From that, they extrapolated a lower bound on the minimum distance for multiple small values of n, which they further extrapolated, from the curve of these lower bounds, to larger values of n. In the end, they picked the parameters that led to the best extrapolations.

We applied a relatively similar heuristic, by using computer simulations to approximate the minimum distance of our code for small values of n, and extrapolating its behavior for large values of n, with the purpose of enabling an apple-to-apple comparison with Silver. We observed that, already when setting the number of ones per row of B to only 7 and using t ≈ 5000 noisy coordinates, we achieve heuristic security guarantees roughly on par with Silver. Note that the choice of increasing t to lower the row-weight of B is well motivated, since it vanishes when n grows and only influences the seed size, which is Ω(tλ log n).

Offline-Online Pseudorandom Correlation Generators from Expand-Accumulate Codes

In this section, we introduce the notion of offline-online pseudorandom correlation generators (PCGs) and show how to construct offline-online PCGs with a highly cache-friendly and parallelizable offline phase from EA codes. At a high level, the aim of offline-online PCGs is to target a better distribution of the computational effort over time: when using a PCG in a secure computation protocol, the cost of the online phase is largely dominated by communication (since computation typically involves extremely cheap operations, a few XOR per gate). This means that if we can push part of the PCG seed expansion cost to the online phase, it will be absorbed by the communication cost to some extent, allowing to reduce the offline expansion cost without harming the runtime of the online phase. Below, we put forward a formal definition of offline-online PCG which captures this goal.

Definition 4.1 (Offline-Online PCG) Let C be a reverse-sampleable correlation generator, where for n = n(λ), τ σ = τ σ (λ), for σ = 0, 1, the σ-th output of of C is in ({0, 1} τσ ) n . An offline-online PCG for C with storage cost N (λ) and output locality ℓ(λ) is a triple of algorithms (PCG.Gen, PCG.Offline, PCG.Online) with the following syntax:

• PCG.Gen(1 λ ) is a PPT algorithm that given a security parameter λ, outputs a pair of offline and online keys ((k off 0 , k on 0 ), (k off 1 , k on 1 )); • PCG.Offline(σ, k off σ ) is a polynomial-time offline expansion algorithm that given party index σ ∈ {0, 1} and an offline key k off σ , outputs an offline string Y σ ∈ {0, 1} N . When considering arithmetic correlations over F = F(λ), the output of PCG.Offline is a vector Y σ ∈ F N .

• PCG.Online(σ, k on σ , Y σ , x) is a polynomial-time online algorithm that on input σ ∈ {0, 1}, online key k on σ , and index 1 ≤ x ≤ n, outputs a value y σ ∈ {0, 1} τσ , or y σ ∈ F τσ in the arithmetic case. Furthermore, PCG.Online reads at most ℓ(λ) entries of Y σ .

The algorithms (PCG.Gen, PCG.Offline, PCG.Online) should satisfy the following: if we define PCG.Expand that applies PCG.Offline and then concatenates the outputs of PCG.Online with x = 1, 2, . . . , n, the resulting (PCG.Gen, PCG.Expand) is a PCG for C according to Definition 2.10. Definition 4.1 is purely syntactic, and allows to better discuss the concrete efficiency of existing PCG schemes in terms of how their cost is distributed between the offline and the online phase. In particular, we expect the locality parameter ℓ to be small, growing at most logarithmically with n.

Generic Offline-Online PCGs

We start by observing that any PCG gives a direct construction of an offline-online PCG with storage cost n and output locality 1, where the online phase is trivial: PCG.Offline is just PCG.Expand, and PCG.Online takes as input the full pseudorandom string Y σ and the index x, and outputs the x-th bit of Y σ . In a sense, in such a PCG, some idle time of the online part is wasted: in concrete MPC applications, the online runtime is dominated by communication (in essence, we have room for more computation online).

At the other end of the spectrum, a PCF also provides a direct construction of an offline-online PCG: PCG.Gen generates PCF keys (Y 0 , Y 1 ) = (k 0 , k 1 ), PCG.Offline does nothing, and PCG.Online(σ, ⊥, Y σ , x) outputs PCF.Eval(k σ , x). There, the storage cost is small (it only amounts to storing the offline keys) and PCG.Online must access Y σ (which is just the offline key) in full. With this cost distribution, the computation during the online phase is likely to largely overflow the "available idle time" that results from communicating during the online phase. Below, we show that our newly introduced EA codes lead to an offline-online PCG with a much better cost balance.

Offline-Online PCGs from EA Codes

In the following we give offline-online PCGs for subfield VOLE from EA Codes, building on puncturable pseudorandom functions. Let p, q ∈ N, such that q = p r . Recall that the goal of subfield VOLE is to obtain output correlations (w i , ∆), (u i , v i ), such that

w i = ∆ • u i + v i , where u i $ ← F p , v i $ ← F q , ∆ $ ← F q
is the same across all evaluations, and w i := ∆ • u i + v i . As for standard PCGs, one can use a correlationrobust hash function to turn a PCF for subfield-VOLE over F = F 2 λ (where λ is a security parameter) into a PCF for the (one out of two) OT correlation over F. Further, note that for the purpose of offlineonline PCGs for OT, the PPRF can be replaced by a strong unpredictable puncturable function, as we show in Section 6.4 (note though that this change requires a stronger assumption on the hash function used in the transformation from PCGs for subfield VOLE to OT).

Recall that (HW N t , F p )-EA-LPN(n, N ) states that for H $ ← EA(n, N, ρ, F p ) it is hard to distinguish H • ⃗ e from random for sparse vectors ⃗ e, where H is of the form H = BA for an accumulator matrix A ∈ F N ×N p and a matrix B ∈ F n×N p with rows sampled according to Ber N ρ . To simplify the description of the online keys we will slightly deviate from this and sample the rows of the matrix B by choosing ℓ positions p i ∈ [N ] and corresponding weights r i ∈ F p , where ℓ = ρ • N (i.e., instead of having an expected number of ℓ non-zero entries, we will obtain exactly or less than ℓ non-zero entries). Further, we assume a PRF F :

{0, 1} λ × [n] → ([N ] × F p ) ℓ to sample {(r i , p i )} i∈[ℓ]
pseudorandomly, where both parties know the key. We will denote this by EA-LPN ′ (n, N, ℓ) relative to F in the following. Note that while this differs from the EA assumption we analysed in the previous section, the altered assumption remains plausible since the combinatorial distance properties of the generated matrix stay essentially the same. Further note that the construction generalizes to standard EA codes at the cost of storing a matrix B ∈ F n×N p with rows sampled according to Ber N ρ , which can be reused across instantiations. As noise distribution we choose HW N t over F p . Note that building on EA-LPN with regular weight-t noise instead one can achieve a more efficient instantiation, since the domain size of the PPRF shrinks from N to N/t.

Theorem 4.2 Let n, N ∈ N with n < N . Let p, q, ℓ ∈ N with p = q r . Let F : {0, 1} λ × [n] → ([N ] × F p ) ℓ
be a PRF and let (F.KeyGen, F.Puncture, F.Eval) be a puncturable PRF over domain [N ] and range F q . Then, assuming the (HW N t , F p )-EA-LPN ′ (n, N, ℓ) assumption relative to F (as defined above), the construction in Fig. 10 is an offline-online PCG for subfield VOLE to generate n correlations with storage cost N and output locality ℓ.

Note that we ignore the cost for storing and accessing ⃗ u off here, since ⃗ u off is an accumulated unit vector which can be stored and accessed in compact representation and therefore does not affect the overall costs significantly.

Note that the proof that the given strategies is indeed a subfield VOLE is identical to the analysis in [BCG + 19b, BCG + 19a] up to swapping the code to the EA code. We therefore omit it here.

The Offline-Online Balance

Since the point of offline-online PCG is to push some of the offline work back to the offline phase to happen during idle times of the computation, the right choice of balance is of course applicationdependent. Here, we make a few estimations to help the reader getting a high level intuition of what to expect. Concretely, there are two causes of slowdown in the online phase that create available idle time: bandwidth and latency.

Bandwidth limitations. Suppose for example that the parties use the GMW protocol on a circuit with 2 20 and gates; ignoring for now all latency issues (hence the round complexity), they will have to communicate 2 22 bits. Over a 10MB network, this ≈ 1/20 second; for 100MB networks, this becomes ≈ 1/200 seconds. To generate the necessary correlations, the parties have expanded 5 • 2 21 machine words of preprocessing material, which can all fit in the L3 cache of a modern computer. Randomly an entry of the L3 cache takes a few nanoseconds; hence, in the time used to communicate, around 10 6 (with a 100MB bandwidth) to 10 7 (with 10MB) accesses to the cache can be made. With a reasonable parameter (midway between aggressive and conservative) of 20 accesses per output and 2 20 outputs to compute, this is already roughly in the range of the available idle time.

Latency. When latency is involved, the amount of available idle time skyrockets: cross-continent communication can easily incur ≈ 150ms of latency per round, and even same-continent communication can be of the order of a few dozen milliseconds. As soon as the protocol takes a few rounds, this is more than enough idle time to perform the required 20 • 2 20 random memory accesses.

Pseudorandom Correlated Functions from Expand-Accumulate Codes

In this section, we put forth new constructions of pseudorandom correlation functions (PCFs) under the EA-LPN assumption. We show how to obtain PCFs for the subfield VOLE, OT and general degree-two correlations over a ring. We do this by combining EA-LPN with a distributed comparison function, a special type of FSS for comparisons. Below we give a high-level summary of the ideas behind the PCF for subfield-VOLE.

Fix an extension field F of F 2 ; we target PCF for the (subfield) VOLE correlation over F. That is, PCF.Gen outputs a pair (k 0 , k 1 ) of correlated keys such that for any input x, writing (u, v) ← PCF.Eval(0, k 0 , x) and w ← PCF.Eval(1, k 1 , x), it always holds that w = ∆ • u + v, where ∆ ∈ F is the same accross all evaluations, (v, w) ∈ F 2 , and u ∈ F 2 . The security properties of PCF are defined in Section 2.7. As for PCGs, one can use a correlation-robust hash function to turn a PCF for subfield-VOLE over F = F 2 λ (where λ is a security parameter) into a PCF for the (one out of two) oblivious transfer correlation over F.

The main difference between an offline-online PCG and a PCF is that the latter must operate in a fully incremental fashion: given the short correlated keys, the parties should be able to obtain pseudorandom instances of the target correlation on demand, without having to stretch the entire pseudorandom correlation. At a high level, our PCF construction proceeds as follows: given the two keys k 0 , k 1 , the parties will be able to locally retrieve (in time logarithmic in N ) additive shares (over F) of any given position in the vector ∆ • A • ⃗ e, where ∆ ∈ F is a scalar known to P 1 , ⃗ e is a sparse noise vector (over F 2 ) known to P 0 , and A is the accumulator matrix of Definition 3.1.

Suppose we manage to achieve the above. Then, a random input x to the PCF is parsed by both players as defining a random row B x of the sparse matrix B; that is, x is the randomness used to sample a row B x from Ber N p (F 2 ). Let ℓ be the number of ones in the sampled row; with the parameters of our analysis, ℓ = O(log N ) with overwhelming probability. Let ⃗ e ′ = A•⃗ e denote the accumulated noise vector. To evaluate PCF.Eval on x, the parties compute shares of ∆ • e ′ i for all ℓ positions i corresponding to nonzero entries in B x , and locally sum their shares. This procedure takes total time O(ℓ log N ) = O(log 2 N ), polylogarithmic in N : we can therefore set N to be exponential in the security parameter λ to allow for an exponential stretch. Defining u i ← B • e ′ i and (-v i , w i ) to be the shares computed this way, it is easy to check that the relation ∆ • u i + v i = w i holds, and that u i is indeed pseudorandom under the EA-LPN assumption.

It remains to find a way to locally construct these shares of ∆ • e ′ i . Here, observe that we cannot use anymore a puncturable pseudorandom function as in our construction of offline-online PCG: the accumulation step, while very efficient and parallelizable, runs in time linear in N . For a PCF, however, N is necessarily superpolynomial, since a PCF allows to stretch (on demand) an arbitrary polynomial amount of correlated pseudorandomness. Fortunately, we can sidestep this unaffordable accumulation step by relying on a primitive known as a distributed comparison function (DCF), of which very efficient instantiations (from any one-way function) were recently proposed in [BGI19, BCG + 21]. For subfield VOLE, it's enough to use a weaker form of distributed comparison function, where one party knows part of the function, which we show can be constructed more efficiently. We elaborate below.

Distributed Comparison Functions

In this section, as in previous works on PCG and PCF, we assume that the noise ⃗ e has a regular structure. That is, ⃗ e is a concatenation of t unit vectors of length N/t, for some noise parameter t. All our constructions easily extend to the setting where ⃗ e is an arbitrary weight-t vector, albeit at the cost of a loss in efficiency.

Given a regular noise vector ⃗ e, the accumulated noise ⃗ e ′ = A • ⃗ e (over group G)11 has the following structure:

⃗ e ′ = (⃗ e ′ ) (1) ∥(⃗ e ′ ) 2 ∥ • • • = (0, . . . , 0, β, . . . , β)∥(β, . . . , β, 0 . . . , 0), ∥ . . .
where depending on the parity of i, each (⃗ e ′ ) (i) starts with a non-zero β ∈ G or zero. For simplicity, consider the case that i is even (we will later explain how to handle odd cases), then (⃗ e ′ ) (i) can be described as the output of a comparison function:

(⃗ e ′ ) (i) j = β if x < α 0 else for some α ∈ [N/t].
This suggest the following approach: we use t instances of a function secret sharing (FSS) scheme for comparison functions, also known as a distributed comparison function [BGI19, BCG + 21] (DCF). A DCF allows to share a comparison function f β <α into two functions (F 0 , F 1 ) such that F 0 (j) + F 1 (j) = f β <α (j) = β • [j < α] for all j, yet (α, β) remain computationally hidden given F σ (for σ = 0 or 1). Then, we can simply set

k σ = (K 0 σ , • • • , K t-1 σ ) for σ = 0, 1, where the K (i)
σ are independent FSS keys for the comparison functions F ji,β , where each j i denotes the position of the 1 in the i-th block of ⃗ e.

Our construction follows the above outline, with a twist: as in previous works on PCG [BCG + 19a, SGRR19], we observe that we do not need the full power of FSS. Indeed, the latter guarantees that (α, β) remains hidden to both parties, while in our construction it is okay for P 0 to know α; we call such a primitive a relaxed distributed comparison function (RDCF).

Relaxed Distributed Comparison Function

In the following we consider the space {0, 1} m as ordered set, by interpreting bit-strings as numbers in the interval [0, 2 m -1 ] and taking the order induced by < on N.

Definition 5.1 (Relaxed distributed comparison function) Let G be an additive group, m ∈ N, α ∈ {0, 1} m , β ∈ G and f β <α : {0, 1} m → G, f β <α (x) := β if x < α 0 else
be the comparison function defined by α and β.

We say a tuple of PPT algorithms RDCF = (Setup, Eval) is a relaxed distributed comparison function if:

• Setup(1 λ , α, β) on input of 1 λ , α ∈ {0, 1} m , β ∈ G outputs a pair of keys (k 0 , k 1 ) • Eval(σ, k σ , x
) is a deterministic function that on input σ ∈ {0, 1}, key k σ and value x ∈ {0, 1} m outputs a value y ∈ G such that the following holds:

Correctness: For all λ ∈ N, for all α ∈ {0, 1} m , β ∈ G, for all (k 0 , k 1 ) in the image of Setup(1 λ , α, β), and for all x ∈ {0, 1} m it holds:

Eval(0, k 0 , x) -Eval(1, k 1 , x) = f β <α (x).
Security: The security requirement, intuitively, is that the party holding k 0 learns nothing about the payload β and the party holding k 1 learns nothing about the path α and the payload β. More formally, we require:

• For all PPT adversaries A, there exists a negligible function negl such that for all α ∈ {0, 1} m , β, β ′ ∈ G and for all λ ∈ N :

| Pr[A(k 0 ) = 1 | (k 0 , k 1 ) ← Setup(1 λ , α, β)] -Pr[A(k 0 ) = 1 | (k 0 , k 1 ) ← Setup(1 λ , α, β ′ )] ≤ negl(λ).
• For all PPT adversaries A, there exists a negligible function negl such that for all α, α ′ ∈ {0, 1} m , β, β ′ ∈ G and for all λ ∈ N :

| Pr[A(k 1 ) = 1 | (k 0 , k 1 ) ← Setup(1 λ , α, β)] -Pr[A(k 1 ) = 1 | (k 0 , k 1 ) ← Setup(1 λ , α ′ , β ′ )] ≤ negl(λ).
Pseudorandomness: Eval(0, k 0 , •) and Eval(1, k 1 , •) define pseudorandom functions.

Constructing RDCF. In Figure 11, we show our construction based on any PRG that maps a λbit string to an output of 2λ bits plus one element of the group G. Compared with the standard DCF construction from [BCG + 21], where each key is of size 2m(λ+log |G|), one of the party's keys in our RDCF is only of size λ, and the other is around half the size of [BCG + 21]. Further, our construction saves on average m/2 calls to the PRG C : {0, 1} λ → G per Eval operation, since C has only be invoked #{i | x i = 0} times on input x ∈ {0, 1} m (instead of m times for the standard DCF construction). Additionally, we show that in the setting where a full evaluation is feasible (i.e., when one is interested in constructing an incremental PCG) keys can be distributed in 2-PC with a simple, 2-round protocol based on 2-round OT.

Lemma 5.2 If G : {0, 1} λ → {0, 1} ℓ+2λ is a pseudorandom generator, then RDCF = (Setup, Eval) as defined in Figure 11 is a relaxed distributed comparison function.

Let (G, +) be an abelian group and Convert G : {0, 1} λ → G be a map converting a random λ-bit string to a pseudorandom group element in G.

Let G 0 , G 1 : {0, 1} λ → {0, 1} λ and C : {0, 1} λ → G to be such that G(k) := C(k)∥G 0 (k)∥G 1 (k) is a secure PRG.
• Setup on input 1 λ , α ∈ {0, 1} m , β ∈ {0, 1} ℓ proceeds as follows:

-Draw k $ ← {0, 1} λ at random. -For all j ∈ [m] define * k j := G αj (G αj-1 (. . . , G α1 (k) . . . )), * γ j := C(G αj-1 (. . . , G α1 (k) . . . )), * (c j , c j ) := (γ j , 0) if α j = 0 (0, γ j ) else , * S j := c j + j-1 i=1 c i and * B j := S j + α j • β. -Define ỹ := G αm (G αm-1 (. . . , G α1 (k) . . . )) and y := Convert G (ỹ) + m i=1 c i -Set K 0 := (α, {k j } j∈[m] , {B j } j∈[m] , y} and K 1 := k.
-Output (K 0 , K 1 ).

• Eval on input index σ ∈ {0, 1}, key k σ and x ∈ {0, 1} m proceeds as follows.

-If σ = 0: * Parse K 0 as K 0 =: (α, {k j } j∈[m] , {B j } j∈[m] , y}.

* If x = α, output y 0 := y. * Else, let j ∈ [m] be the minimal index such that x j ̸ = α j and proceed as follows:

1. For all i ∈ {j + 1, . . . , m} set

c 0 i := C(G xi-1 (. . . , G xj+1 (k j ) . . . )) if x i = 0 0 else . 2. Compute ỹ0 := G xm (. . . , G xj+1 (k j ) . . . )).

Output y

0 := Convert G (ỹ 0 ) + B j + m i=j+1 c 0 i . -If σ = 1: * Set k := K 1 . * For all i ∈ [m] set c 1 i := C(G xi-1 (. . . , G x1 (k) . . . )) if x i = 0 0 else . * Compute ỹ1 := G xm (. . . , G x1 (k) . . . )). * Output y 1 := Convert G (ỹ 1 ) + m i=1 c 1 i . Figure 11: Relaxed distributed comparison function RDCF = (Setup, Eval) from a PRG G : {0, 1} λ → G × {0, 1} 2λ .
Proof. Correctness. Let x ∈ {0, 1} m and λ ∈ N. We have to show that for all (k 0 , k 1 ) in the image of Setup(1 λ ) it holds that Eval(0, k 0 , x) -Eval(1, k 1 , x) = f β <α (x). We distinguish the following cases:

• Case x < α: Let j ∈ [m] be the smallest index such that x j ̸ = α j . Since x < α, it must hold that x j = 0 and α j = 1. Therefore, for B j as defined in the Setup procedure on input α, we have

B j = S j + α j • β = S j + β = c j + j-1 i=1 c i + β.
Further, it holds c j = c 1 j and c i = c 1 i for all i ∈ [j -1] (where c j , {c i } are as defined in the Setup procedure on input α and c 1 j , {c 1 i } are as defined in the Eval procedure on input 1, k 1 , x). Next, observe that

k j = G αj (G αj-1 (. . . , G α1 (k) . . . ) = G xj (G xj-1 (. . . , G x1 (k) . . . ).
This implies c 0 i = c 1 i for all j + 1 ≤ i ≤ m, as well as ỹ0 = ỹ1 . Altogether, this yields

y 0 = Convert G (ỹ 0 ) + B j + m i=j+1 c 0 i = Convert G (ỹ 0 ) + c j + j-1 i=1 c i + β + m i=j+1 c 0 i = Convert G (ỹ 1 ) + c 1 j + j-1 i=1 c 1 i + β + m i=j+1 c 1 i = y 1 + β, as required.
• Case x = α: In this case, we have c 1 i = c i for all i ∈ [m], as well as ỹ = ỹ1 . This implies

y 0 = y = Convert G (ỹ) + m i=1 c i = Convert G (ỹ 1 ) + m i=1 c 1 i = y 1 .
• Case x > α: This case is similar to the case x < α, except that we have x j = 1 and α j = 0 and thus

B j = S j + α j • β = S j = c j + j-1 i=1 c i .
With the considerations above it follows

y 0 = Convert G (ỹ 0 ) + B j + m i=j+1 c 0 i = Convert G (ỹ 0 ) + c j + j-1 i=1 c i + m i=j+1 c 0 i = Convert G (ỹ 1 ) + c 1 j + j-1 i=1 c 1 i + m i=j+1 c 1 i = y 1 .
Security. Since k $ ← {0, 1} λ is chosen uniformly at random, independent from α and β, the second part of the security requirement (i.e., security against the holder of the key K 1 = k) follows immediately. It is left to show that an adversary holding K 0 cannot distinguish between a key obtained via Setup(1 λ , α, β) and a key obtained via Setup(1 λ , α, β ′ ).

We show this via a sequence of hybrid games, where in the ι-th hybrid, we replace the ι-th level of the tree by random. More precisely, in hybrid H ι we setup the key K 0 as follows:

• Draw k $ ← {0, 1} λ at random and define k 0 := k. • For all j ∈ [m] define -For all i ∈ [m], x ∈ {0, 1} i compute: * k x := G xi (G xi-1 (• • • , G x1 (k) • • • )). * γ x := C(G xi-1 (G xi-2 (• • • , G x1 (k) • • • ))).
-

For all i ∈ [m] compute: * S i,0 := x∈{0,1} i-1 k x∥0 and S i,1 := x∈{0,1} i-1 k x∥1 . * Γ i := x∈{0,1} i-1 γ x∥0 .
• P 0 (α) and P 1 (β) run m OT's in parallel, where P 0 acts as receiver and P 1 acts as sender, and the two parties proceed as follows in the j-th OT instance:

-P 0 inputs α j as choice bit.

-If j < m, P 1 inputs messages M j 0 := (S j,0 , Γ j + β), M j 1 := (S j,1 , Γ j ). -If j = m, P 1 inputs messages M j 0 := Γ m + β, M j 1 := Γ m and sends both S m,0 and S m,1 to P 0 .

• P 0 (α) recovers K 1 as follows: Parse

M j αj = (S * j , Γ * j ) for j ∈ [m -1], as well as M m αm = Γ * m .
-For j = 1:

* Set k 1 := S ⋆ 1 . * Set (c ′ 1 , c ′ 1 ) := (Γ * 1 , 0) if α 1 = 0 (0, Γ * 1 ) else * For all i ∈ [m], x ∈ {0, 1} i with x 1 = α 1 , compute: • k x := G xi (G xi-1 (• • • , G x2 (k 1 ) • • • )). • γ * x := C(G xi-1 (• • • , G x2 (k 1 ) • • • )). * Define B 1 := c ′ 1 . -For 1 < j < m: * Set k j := S ⋆ j -x∈{0,1} j-1 ,x̸ =α1∥...∥αj-1 k x∥αj . * Set γ * j := Γ * j -x∈{0,1} j-1 ,x̸ =α1∥...∥αj-1 γ x∥0 . * Set (c ′ j , c ′ j ) := (γ * j , 0) if α 1 = 0 (0, γ * j ) else . * For all i ∈ [m], x ∈ {0, 1} i with x 1 ∥ . . . ∥x j-1 ∥x j = α 1 ∥ . . . ∥α j-1 ∥α j , compute: • k x := G xi (G xi-1 (• • • , G xj+1 (k j ) • • • )). • γ x := C(G xi-1 (• • • , G xj+1 (k j ) • • • )). * Define B j := c ′ j + j-1 i=1 c ′ i . -For j = m: * Set k m := S m,αm -x∈{0,1} m-1 ,x̸ =α1∥...∥αm-1 k x∥αm . * Set k m := S m,αm -x∈{0,1} m-1 ,x̸ =α1∥...∥αm-1 k x∥αm . * Set γ * m := Γ * m -x∈{0,1} m-1 ,x̸ =α1∥...∥αm-1 γ x∥0 . * Set (c ′ m , c ′ m ) := (γ * m , 0) if α 1 = 0 (0, γ * m ) else . * Define B m := c ′ m + m-1 i=1 c ′ i . * Define ỹ := k m and y := Convert G (ỹ) + m i=1 c ′ i . -Output K 0 := (α, {k j } j∈m , {B j } j∈[m] , y}.
In the following we give a brief sketch of correctness. Note that security against semi-honest adversaries is quite straightforward, since P 0 does not receive more information than it can derive from K 0 . Since the proof of security further closely follows [Ds17, BCG + 19a], we omit it here.

Correctness. First, note that for j = 1 we have

k 1 = S ⋆ 1 = S j,α1 = k 1 = G α1 (k)
and

(c ′ 1 , c ′ 1 ) = (Γ * 1 , 0) if α 1 = 0 (0, Γ * 1 ) else = (C(k), 0) if α 1 = 0 (0, C(k) + β) else .
This implies

B 1 = 0 if α 1 = 0 C(k) + β else
as required. Further, note that k x and γ x for x ∈ {0, 1} i with x 1 = α 1 are computed as by P 1 and

c ′ 1 = C(k) if α 1 = 0 0 else .
For 1 < j < m, we proceed inductively. Assume that k x and γ x are computed as by

P 1 for all i ∈ [m], x ∈ {0, 1} i with x 1 ∥ . . . ∥x j-1 ̸ = α 1 ∥ . . . ∥α j-1 and for all i ∈ [j -1] c ′ i = C(G αi-1 (• • • , G α1 (k) . . . )) if α 1 = 0 0 else .
Then, we have

k j = S ⋆ j - x∈{0,1} j-1 ,x̸ =α1∥...∥αj-1 k x∥αj = x∈{0,1} j-1 k x∥αj - x∈{0,1} j-1 ,x̸ =α1∥...∥αj-1 k x∥αj = k α1∥...∥αj-1∥αj .
Further, we have

γ * j = Γ * j - x∈{0,1} j-1 ,x̸ =α1∥...∥αj-1 γ x∥0 = x∈{0,1} j-1 γ x∥0 + α j • β - x∈{0,1} j-1 ,x̸ =α1∥...∥αj-1 γ x∥0 = γ α1∥...∥αj-1∥0 + α j • β.
This implies

c ′ j = 0 if α 1 = β C(G αj-1 (• • • , G α1 (k) . . . )) + β else and c ′ j = C(G αj-1 (• • • , G α1 (k) . . . )) if α 1 = β 0 else .
We thus obtain B j is of the required form. Further, note that the above considerations imply that k x and γ x computed in the j-th iteration are computed as by

P 1 for all i ∈ [m], x ∈ {0, 1} i with x 1 ∥ . . . ∥x j ̸ = α 1 ∥ . . . ∥α j .
Finally, we have

k m = S m,αm - x∈{0,1} m-1 ,x̸ =α1∥...∥αm-1 k x∥αm = x∈{0,1} m-1 k x∥αm - x∈{0,1} m-1 ,x̸ =α1∥...∥αm-1 k x∥αm = k α1∥...∥αm-1∥αm .
This shows that ỹ is computed as required, and since k m , γ * m , (c ′ m , c ′ m , B m are computed as in case 1 < j < m, correctness follows.

PCFs for VOLE and OT from EA Codes and RDCF

We now show how to combine EA-LPN and RDCF to get a PCF for the subfield VOLE correlation. This also implies a PCF for OT, by applying a correlation-robust hash function [BCG + 20a]. Recall that in subfield VOLE over a base field F p and extension F q with p|q, each output of the correlation gives (r, y 0 ) to one party and (∆, y 1 ) to another party, satisfying y 0 = y 1 + r • ∆. Here, r is uniform in F p , while ∆ and y 0 are uniform over F q , but ∆ is fixed for every output.

To simplify the presentation we will slightly modify the noise distribution used in EA-LPN (without changing the assumption). Recall that the accumulated noise ⃗ e ′ = A • ⃗ e has an alternating structure ⃗ e ′ = (⃗ e ′ ) (1) ∥(⃗ e ′ ) 2 ∥ • • • = (0, . . . , 0, 1, . . . , 1)∥(1, . . . , 1, 0 . . . , 0), ∥ . . . where depending on the parity of i, each (⃗ e ′ ) (i) starts with a one or zero. We tweak this by reversing the order of the odd-indexed sub-vectors, so each (⃗ e ′ ) (i) always begins with a 1 (or, with a random nonzero noise value, for the general assumption over rings). When using EA-LPN with this distribution, this is equivalent to using the original error distribution and permuting the columns of the matrix H. Since the columns are independent, the assumption with the modified error distribution is equivalent.

With this modification, we present a PCF for the subfield VOLE correlation in Fig. 12. Given the relaxed DCF, the construction is very similar to prior LPN-based PCGs and PCFs.

PCF.Gen(1 λ ):

1. Sample ∆ $ ← F q 2. For i ∈ [t], sample α i $ ← {0, . . . , N/t -1}, β i $ ← F p \ {0} 3. For i ∈ [t], sample (K dcf i,0 , K dcf i,1 ) ← RDCF.Setup(1 λ , α i , β i • ∆) 4. Output k 0 = K dcf i,0 , α i , β i i∈[t] and k 1 = ∆, (K dcf i,1 ) i∈[t]
PCF.Eval(σ, k σ , x):

1. Let x define a row B x of B, with ℓ non-zero entries x 1 , . . . , x ℓ ∈ F p at indices i 1 , . . . , i ℓ ∈ {0, . . . , N -1} 2. For each j ∈ [ℓ], write i j = γ j • (N/t) + δ j , for δ j ∈ {0, . . . , N/t -1} and γ j ∈ {0, . . . , t -1}. Proof. (sketch) We first argue that the outputs of the PCF are pseudorandomly correlated according to the VOLE correlation. Let ⃗ e = (⃗ e) (1) , . . . , (⃗ e) (t) be the accumulated noise vector defined by α i , β i , so that (⃗ e) (i) begins with repeated β i 's, until entry α i when it becomes zero. Note that for each i j defined by the input x, γ j + 1 ∈ [t] gives the index of the length-N/t sub-vector in B x which contains the non-zero value x j , while δ j gives the index within this sub-vector where x j lies. It follows that the output r satisfies r = ⟨B x , ⃗ e⟩. This implies that r is pseudorandom under the EA-LPN assumption.

Compute over

Also, by the correctness of RDCF, we have

RDCF.Eval(K dcf γj +1,0 , δ j ) -RDCF.Eval(K dcf γj +1,1 , δ j ) = (δ j ? < α γj +1 ) • β γj +1 • ∆ PCF.Gen(1 λ ): 1. Sample ⃗ α (0) , ⃗ α (1) $ ← {0, . . . , N/t -1} t and ⃗ β (0) , ⃗ β (1) $ ← (R * ) t
2. Sample the following DCF and FSS keys:

• (K a i,j,0 , K a i,j,1 ) ← DCF.Gen(1 λ , (α

(0) i , β (0) i ), for i ∈ [t] • (K b i,j,0 , K b i,j,1 ) ← DCF.Gen(1 λ , (α (1)
i , β

(1)

j ), for i ∈ [t] • (K c i,j,0 , K c i,j,1 ) ← FSS.Gen(1 λ , f α (0) i ,α (1)
j ,β (0) i •β
(1) j

), for i, j

∈ [t] 3. Output k σ = (K a i,σ , K b i,σ ) i∈[t] , (K c i,j,σ ) i,j∈[t]
, for σ = 0, 1 PCF.Eval(k σ , (x, y)):

• Let x, y define two rows B x , B y of B, with ℓ non-zero entries x 1 , . . . , x ℓ ∈ R at indices i 1 , . . . , i ℓ and y 1 , . . . , y ℓ at ι 1 , . . . , ι ℓ (for x, y resp.)

• For each j ∈ [ℓ], write i j = γ j • (N/t) + δ j , for δ j ∈ {0, . . . , n/t -1} and γ j ∈ {0, . . . , t -1}.

Similarly, write ι j = γ j • (N/t) + δ j .

• Compute

a σ = (-1) σ ℓ j=1
x j • DCF.Eval(K a γj ,σ , δ j )),

b σ = (-1) σ ℓ j=1 y j • DCF.Eval(K b γj ,σ , δ j )), c σ = (-1) σ • ℓ j=1 ℓ k=1 x j • y k • FSS.Eval(K c γj , γ k ,σ , (δ j , δ j ))
• Output (a σ , b σ , c σ )

Figure 13: PCF for multiplication triples over R from EA codes, DCF and FSS for 2-dimensional intervals Extensions: Degree-2 Correlations, Authenticated Correlations and Multi-Party. The PCF in Fig. 13 can be easily extended to obtain a PCF for any degree-two correlation. By this, we mean that on input a random nonce to Eval, the two parties obtain shares of a random vector ⃗ y over R, as well as shares of z = P (⃗ y), where P is any degree-two polynomial (with polynomially many terms). In fact, the polynomial P can be chosen adaptively, such that if desired, different y i terms can be reused in later queries.

To do this, the key generation procedure is unchanged from Fig. 13. In Eval, instead of using two public inputs (x, y), we now input a vector (x 1 , . . . , x m ) which will be used to define the pseudorandom vector ⃗ y using m rows of B and the EA-LPN assumption. Each degree two term in P (⃗ y) can now be evaluated by taking a sum of ℓ 2 FSS evaluations, the same way as the shares of ab are computed in Fig. 13. Then, the final share of P (⃗ y) is obtained as a linear combination of these.

The cost of each evaluation is essentially m times that of a single Eval for a multiplication triple, where m is the number of degree-2 monomials in P (⃗ y).

Authenticated Correlations. The above PCFs can also easily be extended to produce authenticated correlations, by applying the technique used for multiplication triples in [BCG + 20b]. Here, in addition to shares of the polynomial P (⃗ y), the parties obtain shares of MACs ∆ • P (⃗ y), where ∆ ∈ R is a random, secret-shared MAC key (fixed for each correlation). This can be done with roughly a factor 2 overhead in computation by extending the output of the FSS scheme from 1 to 2 ring elements, where the 2nd output is multiplied by the fixed value ∆. More generally, if R is small e.g. F 2 , we can pick ∆ ∈ R λ and obtain shares of each component of ∆ multiplied by P (⃗ y); this allows us to increase the size of the MAC key, and obtain PCFs for authenticated boolean triples, as needed for the TinyOT protocol [START_REF] Buus Nielsen | A new approach to practical active-secure two-party computation[END_REF][START_REF] Wang | Authenticated garbling and efficient maliciously secure two-party computation[END_REF].

Multi-Party PCFs. When considering unauthenticated degree-two correlations, our PCF can also be extended to the multi-party setting. This follows from a natural programmability property of the construction, meaning that with multiplication triples, for instance, the a values can be programmed to be the same across two PCF instances. This allows a multi-party degree-two correlation to be produced by splitting it up into a sum of n(n -1) two-party correlations, following the approach used for PCGs in [BCG + 19b].

Efficiency Analysis

VOLE and OT. The PCF for subfield VOLE has a key size dominated by t keys for an RDCF on an m-bit domain, where m = log 2 (N/t), with outputs in R. With our optimized RDCF, we get a total key size of around tm(λ + log |R|) bits. The computational cost in a call to Eval mainly consists of a linear combination of ℓ RDCF.Eval outputs, which has a cost of ℓ • m PRG evaluations.

For instance, plugging in the conservative choice (cf. Fig. 9a) of t = 664, N = 5n and up to n = 2 30 samples over a 64-bit ring R, we get a key size of around 370kB. This is around twice the size of the estimated key size for the more aggressive PCF candidate from [BCG + 20a], however, their aggressive assumption did not have a security analysis against linear attacks. Regarding computational complexity, with row weight ℓ = 3 ln n for the matrix B, we require around 1300 PRG evaluations per PCF output, which is more than 10x cheaper than the PCF of [BCG + 20a]. Increasing the number of samples to 2 48 (in line with the parameters from [BCG + 20a], the number of PRG evaluations is 3900, while the key size becomes 650kB. So we see that even using our conservative parameter estimates, we see significant performance benefits from using EA-LPN compared with previous PCF candidates.

If we use instead aggressive parameters for our construction, we get the following costs (based on parameters from Section 3.6):

• (seed-size optimized, t = 68, ℓ = 62) seed size: 65kB; evaluation time: 3700 PRG calls.

• (evaluation-time optimized, t = 1000, ℓ = 7) seed size: 960kB; evaluation time: 660 PRG calls.

To give a rough runtime estimation, the PRG can be instantiated using two calls to fixed-key AES. Using the AES-NI instructions of modern CPUs, one byte of AES-128 can be computed in ∼ 1.3 cycles. Concretely, using a 3GHz processor and our conservative instantiation with n = 2 30 (1300 PRG calls per evaluation), we estimate around 1.4 • 10 5 evaluations per second. The number doubles with our most aggressive, evaluation-time optimized variant. Since the calls are perfectly independent and therefore parallelizable, these numbers can be scaled up linearly with the number of processors. This shows that our PCF already provide high real world performances.

Multiplication triples and degree-2 correlations. Our degree-2 PCF needs t 2 FSS keys for a 2dimensional interval function on a 2m-bit domain, which gives a main storage cost of around 4(mt) 2 λ bits. Meanwhile, the computation involves ℓ 2 calls to FSS.Eval, which costs a total of ≈ (ℓm) 2 PRG operations. Using the conservative parameters (N = 5n, t = 664, ℓ = 3 ln n) with n = 2 30 outputs, the computation per output is 2M PRG operations, and seeds are around 15GB. However, if we instead use more aggressive parameters, for instance, with a much smaller noise weight of t = 85, the storage cost falls down to around 300MB, while the computation increases by less than a factor of two. So, it seems that with our aggressive parameter choices, EA-LPN gives the first, plausible candidate for a practical PCG and PCF for degree-2 correlations over a ring R. (The PCF from [BCG + 20a] does not have good concrete efficiency, since their degree-2 construction does not seem compatible with their most aggressive LPN candidate, and using their conservative candidate leads to much worse performance.) Distributed setup costs. To setup the PCF keys in a distributed manner, we unfortunately cannot use the efficient, 2-round protocol for our RDCF (and similar protocols for FSS [START_REF] Doerner | Scaling ORAM for secure computation[END_REF], since they require a polynomial-sized domain. The setup therefore involves a more expensive, non-black-box protocol with higher communication. However, importantly, with a PCF this is a cost that only happens once and for all.

Optimizing Offline Cost

Up to now, focus has been placed on optimizing the online portion of the offline-online PCG constructions, corresponding to the choice and analysis of advantageous linear codes. In this section, we turn attention to the offline portion of our construction, consisting of two primary components:

1. Evaluating several punctured PRFs (PPRFs) on their entire domain (a functionality called FullEval), and 2. Performing an accumulation step, which converts a vector (x 1 , • • • , x N ) to an accumulated vector

(x 1 , x 1 ⊕ x 2 , • • • , N i=1 x i ).
Recall that with respect to the general template of PCG construction, the combination of the accumulation step and the online process in our construction jointly play the role of applying a compressing linear map ⃗ x → H • ⃗ x as dictated by the selected linear code.

We remark that all previous works in this line (of constructing PCGs from the linear code plus PPRF template) focused almost exclusively on optimizing this ⃗ x → H • ⃗ x step, which was for a long time the dominant cost of the construction. We now instead focus on reducing the cost of the FullEval (and accumulation) component. Our motivations are threefold:

1. First, in the recent work of [START_REF] Couteau | Silver: Silent VOLE and oblivious transfer from hardness of decoding structured LDPC codes[END_REF], the cost of the mapping is reduced so significantly that, according to their evaluation, the cost of FullEval now accounts for about half of the total computation. Reducing the cost of FullEval has therefore an important impact on the total runtime.

2. Second, using our new notion of offline-online PCGs and instantiating them with expand-accumulate codes, the offline part boils down solely to a FullEval computation and an accumulation. The cost of accumulate is exceptionally small, and dominated by the cost of FullEval (by several orders of magnitude). Hence, reducing the cost of FullEval directly translate to reducing the cost of the offline PCG expansion, by the same factor.

3. Eventually, PCGs are not the sole target: other cryptographic primitives also sometimes rely on the FullEval algorithm of a PPRF. Reducing the cost of FullEval directly translates to improvements for these primitives.

The high-level intuition of our main results in this section correspond to the observation that for PCG construction, in fact a PPRF is a stronger tool than necessary. In doing so, we put forth and explore a weaker notion with the aim of improved efficiency.

The results in this section. In Section 6.1, we begin with high-level optimizations for the offline operations. This includes procedures for parallelizing the accumulation step, as well as methods for improving the computation cost of FullEval for GGM-type constructions such as PPRF in exchange for increased key size, by "flattening" the depth of the GGM tree.

In Section 6.2 we define a relaxed version of PPRF, a (strong) unpredictable punctured function (UPF). We provide constructions of (strong) UPFs in the random oracle (RO) model (ROM) that require half the number of RO calls for FullEval as compared with the standard RO-based PPRF construction. Given the current existence of hardware support for AES, we additionally provide a conjectured construction given access to the Random Invertible Permutation Model (RIPM).

In Section 6.3 we explore conversions from UPF to the (stronger) standard notion of PPRF in the random oracle model, beginning with a generic compiler that simply applies the random oracle to each UPF output. For our specific RO-based UPF construction of the previous subsection, we show that this same goal can be achieved by applying the RO to only half of the UPF outputs. In turn, this provides a construction of standard PPRF in the RO model in which FullEval on a domain of size N requires only 1.5N calls to the random oracle.

In Section 6.4 we prove that for some PCG constructions, strong UPFs already suffice in the place of PPRFs. In particular, this holds for the PCG constructions of subfield VOLE and Silent OT. In these applications, we can thus replace the PPRF by our RO-based strong UPF, in which FullEval on a domain of size N requires only N calls to the random oracle, in comparison to 2N when based on PPRF.

Applications and bottom line. Using the baseline GGM PPRF with domain size N , the cost of FullEval (i.e., evaluating the entire binary tree with N leaves) boils down to 2N calls to the underlying primitives (in concrete instantiations, this can translate to 2N evaluations of fixed-key AES). To reduce this cost, we suggest to replace the GGM PPRF by the PPRF of Section 6.3, instantiated with some of the UPF constructions of Section 6.2. Concretely, computing all leaves of the UPF requires exactly N calls to the underlying primitive (modeled either as a random oracle or as a random invertible permutation) in each of our two constructions. Converting the UPF to a PPRF requires further hashing half of the leaves, leading to a total cost of 1.5N calls to the underlying primitive. This is a 25% cost reduction compared to the GGM PPRF approach.

The "tree-flattening" optimizations from Section 6.1 translate to a 41.5% reduction of the FullEval time, hence of the entire offline time of our offline-online PCG construction. Since FullEval also amounts to roughly 50% of the cost of the full PCG expansion in [START_REF] Couteau | Silver: Silent VOLE and oblivious transfer from hardness of decoding structured LDPC codes[END_REF], plugging our new constructions should directly translate to a reduction of the total cost by about 20% (which is quite significant given how fast the construction already is).

As mentioned, for certain PCG constructions, such as Silent OT, these numbers jump already to 50% cost reduction of FullEval, corresponding to roughly 25% reduction in the overall cost of full PCG expansion.

These results also have further implications beyond PCGs. The FullEval algorithm of PPRFs and related primitives is also used in some zero-knowledge applications, typically in the MPC-in-the-head paradigm. Some examples include Picnic [KKW18, CDG + 20] and its variants [START_REF] Kales | Improving the performance of the picnic signature scheme[END_REF], the signature schemes of [START_REF] Beullens | Sigma protocols for MQ, PKP and SIS, and Fishy signature schemes[END_REF], or the zero-knowledge proof of [START_REF] Fleischhacker | On publicly-accountable zero-knowledge and small shuffle arguments[END_REF]. FullEval is also used in some constructions of private information retrieval, such as [MZR + 13]; the list is not exhaustive. In all these applications, replacing FullEval by our improved variant leads to computational savings (the amount of which depends on how dominant the cost of FullEval is in each application).

High-Level Optimizations

Further reduction using a flatter tree. We observe that for FullEval in GGM tree based constructions of PPRFs and related primitives (such as our weaker unpredictable puncturable functions (UPFs) in the upcoming sections) we can get even better savings in exchange for slightly larger seed sizes (translating, in turn, to slightly larger PCG seed sizes), by "flattening" the GGM tree. Concretely, all constructions (the GGM PPRF, and our two UPF constructions of Section 6.2) compute hashes along the nodes of a binary tree. This can be naturally generalized to a k-ary tree.

When using a k-ary tree instead of a binary tree, the size of a punctured key increases by a factor (k -1) • log k (2) (because the punctured key contains all nodes on the co-path to the target point). For example, using k = 3 leads to a factor 1.26 increase in the punctured key, and using k = 4 leads to a factor 1.5 increase. However, in exchange for this mild key size increase (which leads to an increased runtime of the distributed seed generation by a comparable factor), the running time of FullEval drops from 2N calls to (1 + 1/(k -1))N calls to the hash function (a 25% reduction for k = 3, and a 33% reduction for k = 4).

Looking ahead, this optimization can be combined with our UPF constructions, leading to further savings. Concretely, setting k = 3 (hence increasing the seed size by a factor 1.26), the cost of our RIPMbased UPF drops to 1.33N , and our ROM-based UPF drops to 1.17N . Going to k = 4 (a factor 1.5 increase in the seed size), the cost of the RIPM-based UPF further drops to 1.17N .

Accumulating in Parallel. We now turn our attention to the accumulation step. Here, a single-pass algorithm can perform this step using n -1 xor in total; however, this cannot benefit from multicore architectures. When multiple processors are available, a much better strategy consists in using a simple two-pass algorithm, which we describe below.

Let c be the number of cores available. Suppose that the array size N is divisible by c + 1. The algorithm proceeds as follows: partition the array into c + 1 blocks of size N/(c + 1) and compute in parallel prefix-sums of each block except the last one; this takes N/(c + 1) parallel time. Then, compute the sum of each interval [1, N ′ ] for N ′ = c ′ N/(c + 1) + 1, where c ′ = 1, . . . , c, by computing the prefixsum of the c sums computed before; this takes c parallel time. Eventually, add to the internal prefix sum of each block (except the first) the sum of all values to the left of this block, which was computed before. This again takes N/(c + 1) parallel time. Overall, the above algorithm takes ≈ 2N/(c + 1) parallel time. Concretely, this translates to a 1.5x speedup with 2 cores, 8.5x with 16 cores, or a 32.5x with 64 cores.

We note that more cache-friendly variants of this two-pass algorithm have been studied in the literature, to benefit from GPU architectures. For example, the work of [ZWR] provides such an optimized variant variant. Using 48 threads, they report extremely impressive number, around 2 • 10 10 values processed per second. The bottom line is, implementing the accumulation with a simple parallelizable algorithm suffices to makes its cost completely negligible compared to the rest of the computation.

Unpredictable Puncturable Functions

We begin by defining a weakened version of punctured PRFs (PPRF), where the pseudorandomness requirement is relaxed to unpredictability. • Puncture on input of key k and value α ∈ X λ outputs a punctured key k * .

• Eval on input of key k and value x ∈ X λ outputs value y ∈ Y λ .

• PuncEval on input of punctured key k * , restriction α ∈ X λ and value x ∈ X λ outputs value y ∈ Y λ or ⊥.

Further, the following properties are required to hold:

Correctness: For all λ ∈ N, for all keys k in the image of Setup(1 λ ), for all α ∈ X λ and for all k * in the image of Puncture(k, α) it holds:

Eval(k, x) = PuncEval(k * , α, x)
for all x ∈ X λ with x ̸ = α.

Unpredictability: For all PPT adversaries A, there exists a negligible function negl : N → R ≥0 such that for all λ ∈ N:

Pr[Exp unp UPF,A (λ) = 1] ≤ negl(λ)
, where Exp unp UPF,A (λ) is as defined in Figure 14. For the purpose of using the UPF as a plug-in replacement for a puncturable PRF in the Silent OT extension, we require a stronger definition, where we capture that except with some small probability, the adversary has no information about Eval(k, α) on the punctured point α. We capture this in the following definition of strong unpredictability. Note that strong unpredictability in particular implies unpredictability, it therefore suffices to show that our constructions satisfy the notion of strong unpredictability. Definition 6.2 (Strong unpredictability) Let H : {0, 1} * → {0, 1} * be modeled as a random oracle and let UPF = (Setup, Puncture, Eval, PuncEval) be an UPF over domain X = {X λ } λ∈N and range Y = {Y λ } λ∈N having access to H. We say UPF satisfies strong unpredictability relative to H, if for every PPT adversary A the following holds: There exists an event bad = bad λ over the random choice of the random oracle H, the random choice of α $ ← X λ , as well as the random coins of k ← Setup(1 λ ) and A H(•) (1 λ , α, k * ), where k * ← Puncture(α, k), such that the following holds:

Exp unp UPF,A (λ) : α $ ← X λ k ← Setup(1 λ ) k * ← Puncture(k, α) y ← A(k * , α) If y = Eval(k, α) return 1
Else return 0. • For all λ ∈ N, α ∈ X λ , k in the image of Setup(1 λ ) and k * ← Puncture(k, α) it holds that conditioned on ¬bad λ , Eval(k, α) strongly unpredictable from the view of A H(•) (1 λ , α, k * ), that is,

Pr[A H(•) (1 λ , α, k * ) = Eval(k, α) | ¬bad λ ] ≤ 1 |Y λ | -Q(λ) ,
where Q is the number of oracle queries by A to H (and the randomness is taken over the choice of the random oracle H and the choice of k * ).

To give some intuition behind these definitions, suppose H is a bijection on {0, 1} λ → {0, 1} λ , and consider a randomly chosen x $ ← {0, 1} λ . Then x is strongly unpredictable given z := H(x), in the sense that unless an adversary is lucky enough to have x among its Q queries to H, then its ability to predict x is no better than uniform among the remaining 2 λ -Q possible values. More formally, the corresponding event bad λ in the definition above is an adversary that on input z queries x to H. Since z does not reveal any information about x, the probability of this event can be upper bounded by

Pr[bad λ ] ≤ Q(λ) 2 λ
, where Q corresponds to the number of queries asked by A. Further, the adversary cannot gain any more information about x than potentially ruling out the Q(λ) previously asked values. It therefore holds

Pr[A H(•) (z) = x | ¬bad λ ] ≤ 1 2 λ -Q(λ) ,
as desired. Note, however, that even strong unpredictability does not imply that x is indistinguishable from random from the view of the adversary. This is because given a candidate value x, the adversary can efficiently check whether H(x) = z.

An important difference between unpredictability and strong unpredictability is that for an unpredictable value x ∈ {0, 1} λ giving out x ⊕ r for r $ ← {0, 1} λ uniformly at random could potentially leak, e.g., half the bits of r (since one half of x might be predictable), therefore giving out x ⊕ r and x ′ ⊕ r for two unpredictable values x and x ′ could potentially leak r completely. If x is strongly unpredictable, on the other hand, giving out x ⊕ r, the adversary obtains almost no information about r (except with negligible probability). Therefore, even given x i ⊕ r for polynomially many strongly unpredictable values x i , r remains unpredictable to an adversary. This will be a necessary condition to prove that a strong UPF suffices to instantiate Silent OT extension, in Section 6.4.

Strong unpredictable punctured function in the random oracle model. We present in Figure 15 a generic template for a a strong unpredictable punctured function, parameterized by two lengthpreserving functions H 0 , H 1 . For an appropriate choice of H 0 , H 1 , this construction is exactly the standard GGM construction of puncturable pseudorandom function; for example, instantiating H 0 and H 1 as two independent random oracles gives a PPRF in the ROM. In the following, we will put forth alternative choices for the functions H 0 , H 1 such that:

• on an input x, H 0 (x) and H 1 (x) can be simultaneously computed using a single call to a lengthpreserving cryptographic primitive, and

• with this instantiation, the construction of Figure 15 is indeed a strong unpredictable punctured function.

• Setup on input 1 λ outputs a key k $ ← {0, 1} λ .

• Puncture on input of a key k and a value α = (α 1 , . . . , α m ) ∈ {0, 1} m outputs the punctured key k

* = (k * 1 , . . . , k * m ),
where

k * i := H αi (H αi-1 (H αi-2 (. . . (H α1 (k)) . . . ))).
• Eval on input of a key k and a value x ∈ {0, 1} m outputs

y := H xm (H xm-1 (. . . (H x1 (k)) . . . )) ∈ {0, 1} λ .
• PuncEval on input of a key k * = (k * 1 , . . . , k * m ) ∈ ({0, 1} λ ) m , restriction α and value x ̸ = α sets j ∈ {1, . . . , m} as the minimal index such that x j ̸ = α j and outputs Our first theorem shows that instantiating H 0 , H 1 as H 0 (k) := H(k) and H 1 (k) := H(k) ⊕ k, where H is modeled as a random oracle, indeed leads to a strong unpredictable punctured function (note that evaluating H 0 and H 1 on a common input k requires a single call to the random oracle). Theorem 6.3 Let N be a power of 2. For all λ ∈ N, let H : {0, 1} λ → {0, 1} λ be modeled as a random oracle, and define H 0 (k) := H(k) and H 1 (k) := H(k) ⊕ k for all k ∈ {0, 1} λ . Then, UPF as defined in Figure 15 with domain [N ] and range {0, 1} λ , instantiated with H 0 , H 1 is a strong unpredictable punctured function, where for any PPT adversary A asking at most Q queries to H the probability of the bad event bad = bad λ occurring is bounded by

y := H xm (H xm-1 (. . . (H xj+1 (k * j )) . . . )) ∈ {0, 1} λ .
Pr[bad λ ] ≤ 2 • log 2 N + • log N 2 λ + 2 • Q • log N 2 λ
for all sufficiently large λ ∈ N. Claim 1: If bad does not occur, then Eval(k, x) is strongly unpredictable. That is,

Pr[A H(•) (1 λ , α, k ⋆ ) = Eval(k, α) | bad λ ] ≤ 1 2 λ -Q(λ) ,
Unpredictable punctured function in the random permutation model. When instantiating the construction of Figure 15 in the real world, it might be desirable to build upon an invertible permutation rather than a random oracle: this is because fixed-key AES provides such an invertible permutation, and the current Intel support for AES (the AES-NI instructions) make the use of this primitive significantly faster than most alternatives. The standard strategy to construct a hard-to-invert function from an invertible permutation is via the Davies-Meyer construction, where H is defined as H(k) := P (k)⊕k for an invertible permutation P . Unfortunately, instantiating H this way clearly breaks down with our previous construction, as H 1 (k) would become equal to P (k), and hence be invertible. We believe, nonetheless, that our construction from Theorem 6.3 remains the most natural efficient construction. Its inefficiency compared to an AES-based construction is an unfortunate artifact of the fact that AES has hardware support while hash functions do not; but were hash functions to have hardware support in a not-sodistant future, they would likely be even faster than AES, since invertible permutations are a much more structured object. Still, given the current state of hardware support, it is interesting to investigate whether one can construct an unpredictable punctured function with the same efficiency gains (a single call to the primitive for computing the two children of a node) in the random invertible permutation model; this question is also a natural question of theoretical interest. We bring forward a candidate construction which we believe to satisfy unpredictability. In the following we describe the candidate and give an explanation why we believe it secure. We leave a full analysis for future work.

The idea of the construction is to set H 0 (k) := H(k) ⊕ k and H 1 (k) := H(k) + k mod 2 λ . While on first glance one might seem easy to predict given the other, we show that this is not the case, thereby giving some evidence that the corresponding candidate indeed achieves unpredictability.

Note though that we cannot hope to show strong unpredictability for this candidate. To see this, suppose that H(x) ⊕ x equals 1 at the i-th position. By the property of the ⊕-operation, we know that in this case either H(x) i = 1 and x i = 0, or H(x) i = 0 and x i = 1 must hold. Therefore, whenever there is a length-ℓ sequence of 1's, we know that there has to be a length-(ℓ -1) sequence of 1's in H(x) + x mod 2 λ , contradicting strong unpredictability of H(x) + x mod 2 λ . It is therefore not secure to use this candidate directly within the Silent OT extension, but by applying the transformation of Section 6.3 as done for the RO candidate (where we implement the hash functions to hash the left leaves of the last level with H 0 ) we conjecture that one can achieve a 25% improvement compared to the standard PPRF construction based on AES. Conjecture 6.4 Let N be a power of 2. For all λ ∈ N, let H : {0, 1} λ → {0, 1} λ be modeled as a random invertible permutation oracle, and define H 0 (k) := H(k) ⊕ k and H 1 (k) := H(k) + k mod 2 λ for all k ∈ {0, 1} λ (where k is also viewed as an integer between 0 and 2 λ -1). Then, UPF as defined in Figure 15 with domain [N ] and range {0, 1} λ , instantiated with H 0 , H 1 is an unpredictable punctured function. 1. Show that given the punctured key (k * 1 . . . k * m ) except with negligible probability it is hard to predict the root key k with probability ε A using significantly less than 2 λ-log 1 ε A queries to H.

2. Show that given the punctured key (k * 1 . . . k * m ) if there was an adversary who could predict Eval(k, α) with probability ε A using at most Q hash queries, then there is an adversary A ′ which can predict k with probability at least ε A using on average (over the randomness of k and H) ≪ 2 λ-log 1 ε A queries to H.

In the following we provide a proof of the latter claim and leave it for future work to provide a proof of the former. (Note that for a depth-1 tree the former is obviously true, since both H(k) ⊕ k and H(k) + k mod 2 λ individually reveal no information about k.)

Claim: If an adversary A can predict p * m with probability ϵ A using at most Q hash queries, then there is an adversary A ′ which can predict k with probability ϵ A using on average (over the randomness of k and H) Q + m • 2 c•λ-log 1 ε A hash queries, where c ≈ 0.58 is a constant.

Proof. We show that given {p * m , k * m } = {x ⊕ H(x), x + H(x) mod 2 λ }, it is possible to recover x = p * m-1 using on average 2 λ/2 queries; the claim will follow directly by traversing the tree back to its root, spending 2 λ/2 to recover the parent node from two children nodes. Let y = H(x), z = x ⊕ H(x), a = x + H(x) mod 2 λ , and define carry 0 = 0. Then for any i ∈ {1, • • • , λ}, it holds that a i = x i ⊕ y i ⊕ carry i-1 , and carry i = majority(x i , y i , carry i-1 ). Now, given (a, z), A ′ can reconstruct carry i-1 = a i ⊕ z i . Whenever z i = 0, observe that x i ⊕ y i = 0, hence either x i = y i = 1 or x i = y i = 0; in both cases, it holds that carry i = majority(x i , y i , carry i-1 ) = x i . Therefore, for all positions where z i = 0, A ′ recovers x i = carry i . To recover the missing bits, A ′ can query the 2 HW(z) possible inputs x to H until it finds an input that matches z and a.

By linearity of expectation, when traversing the entire tree, A ′ can recover the root key k using on average m • E[2 HW(z) ] queries. Given a uniformly random key k and a random permutation H, each k * i (resp. p * i ) is individually distributed as a uniformly random bitstring -in particular, z is. However, some care must be taken with the expectation in this formula, since the random variable z is conditioned on A succeeding (which happens with probability ε A ). We can bound E A wins [2 HW(z) ] as follows:

E A wins [2 HW(z) ] = λ i=0 2 i • Pr[HW(z) = i | A wins] = ε A • λ i=0 2 i • Pr[HW(z) = i ∧ A wins] ≤ ε A • λ i=0 2 i • Pr[HW(z) = i] = ε A • E[2 HW(z) ] = ε A • λ i=1 E[2 zi ] = ε A • 1.5 λ = 2 cλ+log ε A ,
where the third to last equality is because the bits z i of z are independently random and equal to 1/2 (when we do not condition anymore on A winning the game), and c = log(1.5) is a constant. This concludes the proof of the claim. □

From UPF to Puncturable Pseudorandom Functions

In the following we show that a UPF implies a PPRF in the random oracle model by hashing the outputs of the Eval algorithm, if the size of the input domain X is polynomially bounded (i.e., |X λ | ≤ poly(λ) for some polynomial poly ∈ N[X]).12 This general approach will render the optimizations of the previous section in general ineffective (since it requires |X λ | extra RO calls for a full evaluation), but we will show that using a more careful tailored reduction we obtain PPRFs with a 25% and more improvement regarding the RO calls required for a full evaluation.

PPRF from Generic UPF

• F on input of a key k and x ∈ X λ , computes y ← Eval(k, x) and outputs z := H(y).

• F.KeyGen on input 1 λ outputs k ← Setup(1 λ ).

• F.Puncture on input of a key k and a singleton set {α}, computes k * ← Puncture(k, α) and outputs (k * , α).

• F.Eval on input of a punctured key (k, α) and input value x, computes y ← PuncEval(k * , α, x) and outputs z := H(y). Proof. Note that since the input domain X is polynomially bounded, it suffices to show that (F.KeyGen, F.Puncture, F.Eval) satisfies selective security. From this it automatically follows that F is a PRF, since one can transform an adversary on the PRF security of F into an adversary on the selective security of (F.KeyGen, F.Puncture, F.Eval) by guessing the point x * on which the adversary wants to be challenged ahead of time and answering all oracle queries of the adversary by the key punctured on x * . This incurs a loss of 1 |X λ | ≤ 1 poly(λ) for some polynomial poly ∈ N[X], yielding the required. It is left to show that (F.KeyGen, F.Puncture, F.Eval) indeed satisfies selective security. To that end, let A be a PPT adversary on the selective security of (F.KeyGen, F.Puncture, F.Eval) with success probability ε A . Then, we construct an adversary B breaking the unpredictability of UPF as follows. The adversary B obtains α, k * by its own security experiment and awaits input {α ′ } by A. If α ̸ = α ′ it aborts. Otherwise, it forwards k * to A and additionally a value y $ ← Y λ sampled at random. Further, B records all queries to H by A and answers consistently by keeping a list of queries and sampling a fresh value from Y λ uniformly at random for each fresh query. When A outputs its guess after, say, Q hash queries, B samples a random index i $ ← [Q] and outputs the i-th query of B to H as its guess on Eval(k, α). First, note that since α is sampled at random, the probability that B aborts can be upper bounded by 1 -1/|X λ |. Further, the probability that B aborts is independent of the behaviour of A, we thus have

Pr[A breaks PPRF ∧ α = α ′ ] ≥ ϵ A (λ) |X λ | .
If A is successful in distinguishing the case b = 0 (i.e., obtaining y = H(Eval(k, α))) and b = 1 (i.e., obtaining y $ ← {0, 1} λ ) with probability at least ε A , given k * it must query H on Y := Eval(k, α) with at least probability ε A (since otherwise the two distributions are identical from the view of A). Further note that up to the point where A potentially queries Y , the adversary B perfectly simulates the selective security game for PPRFs.

Overall, we thus obtain that B succeeds with probability at least Since Pr[B breaks UPF] is negligible by assumption, |X λ | ≤ poly(λ) for some polynomial poly ∈ N[X], and Q ∈ N[X], we obtain that also ϵ A has to be negligible, which concludes the proof. □ We next show that our specific UPF construction from the previous section (Theorem 6.3) can be converted into a PPRF by applying the random oracle to only half the output evaluations (instead of all), thus saving 0.5N calls from the generic transformation. Theorem 6.6 Let N = N (λ) be a power of 2, such that N (λ) ≤ poly(λ) for some polynomial poly ∈ N[X]. For all λ ∈ N, let H : {0, 1} λ → {0, 1} λ be modeled as a random oracle. Let UPF = (Setup, Puncture, Eval, PuncEval) be the UPF with over domain [N ] and range {0, 1} λ from Theorem 6.3. Then, F together with the tuple of algorithms (F.KeyGen, F.Puncture, F.Eval) as given in Figure 17 defines a 1-puncturable pseudorandom function.

Proof.

Again, we only have to show that (F.KeyGen, F.Puncture, F.Eval) satisfies selective security. Let A be an adversary on the selective security of (F.KeyGen, F.Puncture, F.Eval) that succeeds with probability ε A and let {α ′ } denote the input by A. Again, we construct an adversary B that receives

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 (y x $ ← Y for every x ∈ S * ) and sends them to A.

Figure 2 :

 2 Figure 2: Selective security game for puncturable pseudorandom functions. At the end of the experiment, A sends a guess b ′ and wins if b ′ = b.

Figure 3 :

 3 Figure 3: Pseudorandom Y-correlated outputs of a PCF.

Figure 4 :

 4 Figure 4: Security of a PCF. Here, RSample is the algorithm for reverse sampling Y as in Definition 2.11.

  Definition 3.8 (EA-LPN Assumption) Let D(R) = {D N (R)} N ∈N denote a family of efficiently sampleable distributions over R, such that for any N ∈ N, Im(D N (R)) ⊆ R N . For a dimension n = n(λ), number of samples N = N (λ), ring R = R(λ) and parameter p = p(λ) ∈ (0, 1) the (D, R)-EA-LPN(n(λ), N (λ), p(λ)) assumption states that

Figure 5 : 3 $←

 53 Figure 5: Plots of the average weight distributions for the 3 row sampling procedures: exact rows, regular rows, and Bernoulli rows. Blue corresponds to exact; red corresponds to regular; and orange corresponds to Bernoulli.

Figure 6 :

 6 Figure6: In this graphic we have plotted the average weight distributions for 4 of the sampling procedures outlined in this section, normalized by 100 q 4 where q is the ring size. Blue corresponds to H 1 ; red to H 2 ; yellow to H 3 ; and green to H 4 .

Figure 8 :

 8 Figure8: In this table, we list the (extrapolated) failure probabilities for various parameter choices. The rate is set to 1/5, i.e., N = 5n. If the cell is empty it is because the extrapolated value exceeds 1.

F q : y σ = ℓ j=1 xqFigure 12 :

 j=112 Figure 12: PCF for subfield VOLE from EA codes and RDCF

  Definition 6.1 (Unpredictable punctured function) An unpredictable punctured function (UPF) over domain X = {X λ } λ∈N and range Y = {Y λ } λ∈N consists of a tuple of PPT algorithms UPF = (Setup, Puncture, Eval, PuncEval) such that • Setup on input 1 λ outputs a key k.

Figure 14 :

 14 Figure 14: Unpredictability experiment

Figure 15 :

 15 Figure 15: General template for a strong unpredictable punctured function UPF = (Setup, Puncture, Eval, PuncEval) over domain [N ] and range {0, 1}, based on public functions H 0 , H 1 , where [N ] is interpreted as {0, 1} m for m := log N .

Proof.

  Let m := log N and let α $ ← [N ] denote the value sampled by the experiment interpreted as bitstring α = α 1 ∥ . . . ∥α m ∈ {0, 1} m . By the path of α in the tree defined by k we denote the values p * := (p * 1 , . . . , p * m ), wherep * i := H αi (H αi-1 (H αi-2 (. . . (H α1 (k)) . . . )) ∈ {0, 1} λ(recall that m = log N ) on the path of α. Note that k * = (k * 1 , . . . , k * m ) as defined in Figure15is equal to the co-path of α, that is all values in the tree defined by k neighboring the path of α.By the event bad we denote the event bad := bad 1 ∨ bad 2 , where • bad 1 : There is a collision on the values k, p * 1 , . . . , p * m-1 , k * 1 , . . . k * m . • bad 2 : The adversary A queries H on any of the values k, p * 1 , . . . , p * m-1 .

  Underlying intuition. As before, let m := log N , let α ∈ [N ] denote the value sampled by the experiment interpreted as bitstring α = α 1 ∥ . . . ∥α m ∈ {0, 1} m , let p * = (p * 1 • • • p * m ) the path of α defined by the key k, and let (k * 1 • • • k * m ) the co-path of α. A possible strategy to prove unpredictability is as follows:

Figure 16 :

 16 Figure 16: Puncturable PRF (F.KeyGen, F.Puncture, F.Eval) from UPF UPF = (Setup, Puncture, Eval, PuncEval) and hash function H : Y λ → Y λ modeled as a random oracle.

  Pr[B breaks UPF] ≥ ϵ A (λ) |X λ | • Q(λ) and thus ϵ A (λ) ≤ |X λ | • Q(λ) • Pr[B breaks UPF].

  α, k * by its own security experiment. If α ̸ = α ′ , B aborts. Else, B proceeds as follows. If α log N = 1, B proceeds as in the proof of Theorem 6.5. Else, B parses k * =: (k * 1 , . . . , k * log N ) and forwardsK * := (k * 1 , . . . , k * log N -1 , H(k * log N ))together with a random value y $ ← {0, 1} λ to A. Recall that A attempts to distinguish p * log N = H(p * log N -1 ) from random, where p * log N -1 is such that H(p * log N -1 ) ⊕ p * log N -1 = k * log N . Similar to the

  this work, we provide a new (dual) LPN-type assumption connected to EA codes which we term EA-LPN. It is obtained by specializing Definition 2.4 to the case where the code generation algorithm samples H For the noise distribution D(R), we can consider Bernoulli noise Ber N t/N (R), exact noise HW N t (R), and regular noise Reg N t (R).

$

← EAGen.

A notable exception is the "primal" PCG construction of[START_REF] Boyle | Compressing vector OLE[END_REF], which is also parallelizable. However, this PCG is limited to quadratic stretch; in practice, this makes it less efficient than other alternatives, even when using the bootstrapping approach from [YWL

+ 20].

Note that it would be sufficient for PCF.Eval to take as input kσ and x by appending σ to the key kσ. This corresponds to the view of a PCF as a single keyed function.

This inequality may be readily verified using calculus.

This distribution can be naturally extended when ℓ ∤ N : in this case, if a = M mod ℓ we sample a unit vectors in R ⌈N/ℓ⌉ and ℓ -a unit vectors from R ⌊N/ℓ⌋ .

Of course, this notion is not interesting if R = F 2 .

In [AHI + 17] the code is presented in terms of a parity-check matrix. In our case, presenting a code via a generator matrix is more convenient. As one can efficiently pass between the two representations the definitions are equivalent.

This assumption implies that the standard information set decoding attack does not succeed.

We used exponential regression in log 2 n, which fit very well: R values in excess of .99.

Note that as computing a dot-product requires 5 • 2 30 time, this is sufficient for 128 bits of security.

The regular distribution appears to us to be the most reasonable in practice; however, other distributions appear to behave similarly.

For concreteness, one can assume G is the additive group of a field, but as this will be useful later we state it in this generality.

Note that while this is a limitation, it constitutes the only regime where computing a full evaluation is feasible.

7 Acknowledgements E. Boyle supported by AFOSR Award FA9550-21-1-0046, ERC Project HSS (852952), and a Google Research Award. G. Couteau supported by the ANR SCENE. N. Gilboa supported by ISF grant 2951/20, ERC grant 876110, and a grant by the BGU Cyber Center. Y. Ishai supported by ERC Project NTSC (742754), BSF grant 2018393, and ISF grant 2774/20. L. Kohl is funded by NWO Gravitation project QSC. N. Resch is supported by ERC H2020 grant No.74079 (ALGSTRONGCRYPTO). P. Scholl is supported by the Danish Independent Research Council under project number 0165-00107B (C3PO) and an Aarhus University Research Foundation starting grant.

Parameters:

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

• A PPRF scheme (F.KeyGen, F.Puncture, F.Eval) over domain [N ] and range Fq to share the noise vector.

• A PRF F : {0, 1} λ ×[n] → ([N ]×Fp) ℓ to generate a pseudorandom sparse matrix B defining the EA code.

Correlation: Outputs ((u i , v i ), (w i , ∆)), such that

Gen:

• Pick a random size-t set S = {s 1 , . . . , st} ⊂ [N ], sorted in increasing order.

• Pick a random vector ⃗ y = (y 1 , . . . , yt) ∈ (F * p ) t and ∆ $ ← Fq.

• For i ∈ [t] proceed as follows:

-Draw k i ← F.KeyGen(1 λ ).

-

-Set K i 0 := (k * i , ∆ i ) and K i 1 := k i .

• Let k off 0 := (n, N, {K i 0 } i∈[t] , S, ⃗ y), k off 1 := (n, N, {K i 1 } i∈[t] , ∆) and k on 0 := k on 1 := k. • Output ((k off 0 , k on 0 ), (k off 1 , k on 1 )). Offline: On input (σ, k off σ ): 1. If σ = 0, parse k off 0 as (n, N, {K i 0 } i∈[t] , S, ⃗ y) and proceed as follows:

• Define ⃗ µ ∈ F N p to be the vector with

• For all i ∈ [t], define ⃗ v i 0 ∈ F N p to be the vector with v i 0,j := F.Eval(k * i , {s i }, j) if j ̸ = s i ∆ i else .

, ∆) and proceed as follows:

• Define ⃗ w i 0 ∈ F N p to be the vector with w i 0,j := F (k i , j) for all i ∈ [t].

Online: On input (σ, k on σ , Yσ, x): 1. If σ = 0, parse k on 0 as k and Y 0 as (⃗ u off , ⃗ v off ) and proceed as follows:

2. If σ = 1, parse k on 0 as k and Y 1 as ( ⃗ w off , ∆) and proceed as follows: -If j ≤ ι: * (γ j , κ j,0 , κ j,1 ) $ ← {0, 1} ℓ+2λ .

-If j > ι: * (γ j , κ j,0 , κ j,1 ) := G(k j-1 ).

-(k j , k j ) := (κ j,αj , κ j,αj ),

We have the following:

• Hybrid H 0 : Note that the hybrid H 0 corresponds to the standard setup algorithm, since in this case it holds k 0 = k as well as k j = κ j,αj = G αj (k j-1 ) and thus

Together with k j = κ j,αj = G αj (k j-1 ) this implies

as required.

• Hybrid H ι-1 ⇝ H ι : We have to show that if G is a pseudorandom generator, then the hybrids H ι-1 and H ι are computationally indistinguishable for all ι ∈ [m]. This is straightforward, since an adversary attacking the pseudorandomness of G can embed its input as (γ ι,0 , κ ι,0 , κ ι,1 ) (and otherwise follow the setup algorithm of game H ι-1 ). If it obtained a pseudorandom input, then it perfectly simulates H ι-1 . If it obtained a truly random input, then it perfectly simulates H ι . A distinguisher between the two games could thus be used to break pseudorandomness of the underlying PRG G, yielding a contradiction as required.

• Hybrid H m . In hybrid H m the parts {k j } j∈[m] , {B j } j∈[m] , y of K 0 are distributed independently uniformly at random and are therefore in particular independent of β. This concludes the proof.

Pseudorandomness. Note that since correctness holds, it is sufficient to show Eval(σ, k σ , •) for either σ = 0 or σ = 1, since the pseudorandomness of the other follows immediately. Since the proof for σ = 1 follows the proof of [START_REF] Goldreich | How to construct random functions[END_REF] very closely, we omit it here. □ Distributed setup protocol. Following the strategy of [Ds17, BCG + 19a] for setting up the GGMbased PPRF in 2 rounds in the semi-honest setting, we describe a setup protocol for setting up our RCDF in 2 rounds, given a 2-round OT protocol, if the domain size 2 m is polynomially bounded (i.e., a full evaluation is feasible to compute). For simplicity, we assume that party P 1 knows the offset β ∈ G (as is the case in our PCF constructions). Since the protocol follows the protocol of [BCG + 19a] very closely, we only give a sketch here. Recall that the underlying idea is for the party P 1 to prepare the sum of all left leaves and the sum of all right leaves for each level, and P 0 will learn one of these sums via OT. Since for each level, P 0 can already compute all but one of either the left or right leaves from information about previous levels, the OT allows recovering the missing node corresponding to the key k j .

• P 1 (β) proceeds as follows:

Then, we have y 0 -y 1 = j x j • (δ j ? < α γj +1 ) • β γj +1 • ∆ = r • ∆, as required. Finally, from the pseudorandom outputs property of RDCF, it holds that each individual share y σ is also pseudorandom.

To argue security, we need to show that given one of the keys k σ , the other party's outputs are indistinguishable from an ideal VOLE output that is sampled conditioned on the VOLE outputs from k σ .

We start by considering the case when party 0 is corrupted. In this case, the reverse-sampled outputs of party 1 are the pairs (∆, y 1 ), where ∆ ← F q and y 1 is computed as y 0 -r • ∆ (using y 0 , r from k 0 ). The only difference between this experiment and the real outputs is that the real output of party 1 uses a random ∆ which is also used to generate the RDCF keys in k 0 . These two cases are indistinguishable due to security property of RDCF, which guarantees that k 0 hides ∆.

When party 1 is corrupted, the reverse-sampled outputs of party 0 are defined by sampling are random r, and computing y 0 using r and the outputs from key k 1 . To argue security, we start with the experiment where the distinguisher gets the key k 1 together with the real outputs of party 0, derived from k 0 . We then consider a hybrid where instead of computing y 0 from k 0 , we use y 0 = y 1 + r • ∆; from the correctness of RDCF, this is indistinguishable from the first experiment. Next, we switch to a hybrid where the RDCF keys in k 1 are replaced with ones generated with independent α i values; this is indistinguishable due to the RDCF security property. Finally, we replace the r values, which are computed from the EA-LPN distribution, with uniformly random ones. This is identical to the reversesampled distribution, and indistinguishable from the previous hybrid under EA-LPN. □

PCF for Degree-2 Correlations

In our PCF for VOLE, each random output r is obtained by taking a random row of B defined by x, and computing r = j x j β γj • ((δ j ? < α γj )). The RDCF was used to compute shares of ((δ j ? < α γj )) multiplied by ∆. To generate multiplication triples in a ring R, we want to sample two such random values a, b ∈ R, and output shares of these together with shares of c = ab. Computing shares of a, b can be done by defining them similarly to r, and using (non-relaxed) DCFs. Computing shares of c then boils down to being able to compute shares of values of the form

where x and y are public while α, α ′ , β are secret. This can be seen as the product of two comparison functions, or a two-dimensional interval function.

On its own, a distributed comparison function is not sufficient to obtain shares of a two-dimensional interval. However, function secret-sharing for two-dimensional intervals has been constructed using the FSS for decision tree construction from [START_REF] Boyle | Function secret sharing: Improvements and extensions[END_REF], based on any PRG. Formally, we define the function class of two-dimensional N × N intervals over a ring R, where each function in the class is specified by a pair of indices α 1 , α 2 ∈ [N ] and β ∈ R, and defined by

The FSS construction from [START_REF] Boyle | Function secret sharing: Improvements and extensions[END_REF] has a key size bounded by 2 |V | (λ + 1) bits, where V is the set of nodes in the binary decision tree; a 2 m × 2 m interval function can be expressed as a decision tree with 2m(m + 1) + 1 nodes, giving a key size of roughly 4m 2 λ bits for the FSS scheme. In our construction, we use m = log 2 (N/t).

PCF for Multiplication Triples. Given these tools, we present a PCF for the multiplication triple correlation in Figure 13. Correctness of the construction follows from the explanation above, and its security follows from the pseudorandomness of both DCF and FSS outputs, together with the EA-LPN assumption. Note that the noise values ⃗ β (0) , ⃗ β (1) are sampled from R * , the set of invertible elements, to prevent the subring projection attacked mentioned in Section 2.2. The proof of the following is similar to the previous lemma, except instead of RDCF, we rely on the security of standard DCF and FSS.

Lemma 5.4 If DCF is a secure distributed comparison function with pseudorandom outputs and FSS is a secure function secret-sharing scheme with pseudorandom outputs, then the construction in Fig. 13 is a PCF for multiplication triples over R under the EA-LPN assumption with regular, weight-t noise.

where Q is the number of oracle queries by A to H (and the probability is taken over the random choice of H and k * ).

Proof.

We change the setup procedure as follows. Instead of sampling k ← Setup(1 λ ) and setting k * ← Puncture(k, α), the experiment now proceeds as follows:

We will first show that the distribution of the experiment above is identical to the original experiment if bad 1 does not occur, i.e., if there is no collision on the values k, p * 1 , . . . , p * m-1 , k * 1 , . . . , k * m . To this end, note that for all j ∈ [m -1] we have Proof. For all j ∈ [m] let L j := {k, p * 1 , . . . , p * j , k * 1 , . . . , k * j }. Then, we define the event bad j as follows:

• bad j : The set L j does not contain 2j + 1 distinct values.

For Pr[ bad 1 ] it holds

For all j ∈ [m] with j ≥ 2 in the following we will bound Pr[ bad j | ¬ bad j-1 ]. Since we condition on the event that L j-1 contains 2j + 1 distinct values, we have that H(p * j-1 ) is distributed uniformly at random (independently from all values in L j-1 ). It thus follows • 2 λ for all sufficiently large λ ∈ N. Note that the choice of 3 4 here is somewhat arbitrary, but allows that even after Q attempts, the set of possible values is still of size at least 1 2 • 2 λ , since Q ≪ 1 4 • 2 λ for all sufficiently large λ ∈ N.

Therefore, the adversary A that cannot do better than guessing from this restricted set of values. The probability that bad 2 occurs, i.e. A queries any of the m = log N values k, p * 1 , . . . , p * m-1 to H, therefore happens at most with probability Q • log N • 2/2 λ by a union bound. This yields

□ This concludes the proof. □ PPRF from UPF Construction of Theorem 6.3

• F on input of a key k and x ∈ X λ , computes y ← Eval(k, x) and outputs z := y if x log N = 0 H(y) else .

• F.KeyGen on input 1 λ outputs k ← Setup(1 λ ).

• F.Puncture on input of a key k and a singleton set {α}, computes k * = (k * 1 , . . . , k * log N ) ← Puncture(k, α) and outputs (k * , α), where

• F.Eval on input of a punctured key (k, α) and input value x, computes y ← PuncEval(k * , α, x) and outputs proof of Theorem 6.5, we have that if A is successful in distinguishing the case b = 0 (i.e., obtaining y = H(p * N -1 )) and b = 1 (i.e., obtaining y $ ← {0, 1} λ ) with probability at least ε A , it must query H on p * N -1 with at least probability ε A . Further, again we have that up to the point where A queries p * N -1 , the adversary perfectly simulates the selective secuirty game for PPRFs. The adversary B thus proceeds by guessing a query q i for i $ ← [Q(λ)] and for this query outputting H(q i ) to its own experiment. Note that B succeeds if indeed q i = p * N -1 . We thus obtain that B succeeds with probability at least

which concludes the proof. □ Corollary 6.7 Let H : {0, 1} λ → {0, 1} λ be modeled as a random oracle. Then, there exists a puncturable pseudorandom function over domain [N ] and range {0, 1} λ , which requires 1.5N calls to the random oracle for a full evaluation.

Instantiating the construction in Figure 17 with the candidate construction of Conjecture 6.4 we obtain the following. Corollary 6.8 Let H : {0, 1} λ → {0, 1} λ be modeled as a random permutation (with publicly accessible inverse). If Conjecture 6.4 is true, then there exists a puncturable pseudorandom function over domain [N ] and range {0, 1} λ , which requires 1.5N calls to the random permutation for a full evaluation.

From UPF to Silent OT Extension

In this section we show that for some applications a strong unpredictable pseudorandom functions can serve as a replacement for a puncturable pseudorandom functions, thereby reducing the costs required for a full evaluation from 2N to N (where N is the domain size).

More precisely, we show that the protocol for silent OT extension of [BCG + 19b, BCG + 19a], which allows to generate n instances of random OT with sublinear communication complexity, can directly be instantiated with a strong UPF instead of a PPRF.

Construction G OT

Parameters:

• Security parameter 1 λ , integers N > n, q = p r = λ ω(1) , and noise weight t.

• A code generation algorithm C and H n,N $ ← C(n, N, F p ) returning matrices in F n×N p .

• A UPF scheme UPF = (Setup, Puncture, Eval, PuncEval) over domain [N ] and range F q .

• A hash function H : [n] × F q → {0, 1} λ modeled as a random oracle.

Gen:

• Pick a random size-t subset S = {s 1 , . . . , s t } of [N ], sorted in increasing order.

• Pick a random vector ⃗ y = (y 1 , . . . , y t ) ∈ (F * p ) t and x $ ← F q .

• For i ∈ [t] proceed as follows:

-

Expand: On input (σ, k σ ):

, S, ⃗ y) and proceed as follows: • Define ⃗ µ ∈ F N p to be the vector with

• For all i ∈ [t], define ⃗ v i 0 ∈ F N p to be the vector with

x) and proceed as follows:

Figure 18: PCG for n sets of 1-out-of-p random OT Theorem 6.9 Suppose H : [n] × F q → {0, 1} λ is a hash function modeled as a random oracle, the (HW N t , C, F p )-dual-LPN(n, N ) assumption holds, and UPF = (Setup, Puncture, Eval, PuncEval) is a UPF over domain [N ] and range F q that satisfies strong unpredictability relative to oracle H. Then the silent OT construction G OT (Fig. 18) is a secure PCG for the random 1-out-of-p OT correlation.

Proof.

Correctness. We first have to show that the correlation (R 0 , R 1 ) obtained via the PCG is computationally indistinguishable from (R 0 , R 1 ) sampled truly at random conditioned on satisfying the OT correlation.

First, note that ⃗ µ is sampled as a random vector over F N p conditioned on having exactly t non-zero entries, which corresponds exactly to the distributed HW t . The choice vector ⃗ u = H n,N • ⃗ µ ∈ F n p is thus computationally indistinguishable to a truly random vector by the (HW N t , C, F p )-dual-LPN(n, N ) assumption.

It is left to show that the following holds:

• {w i,j } i∈[n],j∈[p] are computationally indistinguishable from values drawn uniformly at random from {0, 1} λ , and

• for all i ∈ [n]: w ′ i = w i,ui . The former is a straightforward consequence from assuming H is modeled as a random oracle. If x ̸ = 0, then we have v i -j • x ̸ = v i -j ′ • x for all j ̸ = j ′ ∈ F p . Since additionally i is an input to H, we have that {w i,j } i∈[n],j∈[p] corresponds to the output on H on n • p pairwise distinct values (unless x = 0) and is therefore even perfectly indistinguishable from chosen uniformly at random. Since by assumption we have q = λ ω(1) , the case x = 0 only occurs with negligible probability, therefore yielding the required.

Further, by the correctness of UPF, for all i ∈ F p , j ̸ = s i we have that

as well as

since µ j = 0 for all j ∈ [N ]\S. Altogether, we obtain

Security. First, consider the case (k 0 , R 1 ). Here, in the real distribution, the adversary is given a key k 0 = (n, N, {K i 0 } i∈[t] , S, ⃗ y) as well as the expanded output

, where w i,j = H(i, v 1,i -j • x). We need to show that this is indistinguishable from the ideal distribution, where R 1 $ ← RSample(0, R 0 ). Recall that RSample(0, R 0 ) proceeds by setting w i,ui := w ′ i (where w ′ i is as specified in Expand(0, k 0 )) and sampling the remaining values {w i,j } i∈[n],j∈[p]\{ui} uniformly at random. By correctness, we have w i,ui := w ′ i , it is thus left to show that the remaining values are distributed uniformly at random from the view of the adversary, even given k 0 .

We first assume x ̸ = 0, which happens except with probability 1 q . Further, for simplicity we will assume the t UPF instances to be t independent instances punctured at a random position s i . Note that in typical instances we have t ≪ √ N and therefore expect no collision to occur for positions s 1 , . . . , s t chosen uniformly at random (instead of uniformly at random conditioned on being distinct). For the general case, note that we can consider the UPF punctured at a chosen instead of random point add the cost of an additional loss of factor N in the bad event of the strong unpredictability definition.

Let bad = bad λ be the bad event from the strong unpredictability definition relative to UPF. Then, by assumption there exists a negligible function negl : N → R ≥0 such that Pr[bad λ ] ≤ negl(λ) for all λ ∈ N. By a union bound, we thus obtain that except with probability at most t • negl(λ), it holds that

where by bad i λ we denote the bad λ event relative to the i-th instance of the UPF. Thus, we have that except with negligible probability, Eval(k i , s i ) is strongly unpredictable for all i ∈ [t], i.e.,

.

Recall that

← F q is chosen uniformly at random, the above implies

.

Phrased differently, for each i the adversary can rule out at most Q H(λ) out of q potential values for x.

Altogether, the adversary can thus rule out at most t • Q H(λ) out of q potential values for x. This implies

.

Since x is independent from all other values of the protocol, we obtain that the probability that A queries H on (i, v 1,i -j • x) for some j ̸ = s i if bad λ does not occur is bounded by

where Q H is the number of queries by A to H. Altogether, we obtain that {w i,j } i∈[n],j∈[p]\{si} is distributed perfectly uniformly at random from the view of A H(•),H(•) (1 λ , k 0 ) except with probability at most

which is negligible as required.

It is left to consider the case (k 1 , R 0 ). Here, in the real distribution the adversary is given a key k 1 = (m, n, {K i 1 } i∈[t] , x) as well as the expanded output {(u i , w ′ i )} i,j∈ [n] , where ⃗ u = H n,N • ⃗ µ and w ′ i = w i,ui . Therefore, it suffices to show that the distribution of ⃗ u is computationally indistinguishable from uniformly at random even given k 1 . First note that k 1 does not leak any information about S, ⃗ y, since the distribution of k i ← Setup(1 λ ) is independent of s i , y i . It therefore follows that ⃗ u is distributed computationally indistinguishable from uniformly at random by the (HW N t , C, F p )-dual-LPN(n, N ) assumption, as in the proof of correctness.

□ Together with the two-round distributed setup for a PPRF scheme of [BCG + 19a] which directly applies to our UPF constructions given in 6.2, we obtain the following corollary, reducing the random oracle calls to H from 2 • t • n to t • n per party. Corollary 6.10 Assuming the (HW N t , C, F p )-dual-LPN(n, N ) assumption, there exists a semi-honest 2round OT extension with silent preprocessing for generating n 1-out-of-p OTs, which makes o(n) blackbox uses of a 2-round semi-honest 1-out-of-2 OT, and t•n black-box calls to a random oracle H•{0, 1} λ → {0, 1} λ and n • (p -1) calls to a random oracle H • [n] × F q → {0, 1} λ per party.