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

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

Correlated Pseudorandom Functions from Variable-Density LPN

Keywords:

Correlated secret randomness is a useful resource for many cryptographic applications. We initiate the study of pseudorandom correlation functions (PCFs) that offer the ability to securely generate virtually unbounded sources of correlated randomness using only local computation. Concretely, a PCF is a keyed function F k such that for a suitable joint key distribution (k 0 , k 1 ), the outputs (f k0 (x), f k1 (x)) are indistinguishable from instances of a given target correlation. An essential security requirement is that indistinguishability hold not only for outsiders, who observe the pairs of outputs, but also for insiders who know one of the two keys.

We present efficient constructions of PCFs for a broad class of useful correlations, including oblivious transfer and multiplication triple correlations, from a variable-density variant of the Learning Parity with Noise assumption (VDLPN). We also present several cryptographic applications that motivate our efficient PCF constructions.

The VDLPN assumption is independently motivated by two additional applications. First, different flavors of this assumption give rise to weak pseudorandom function candidates in depth-2 AC 0 [⊕] that can be conjectured to have subexponential security, matching the best known learning algorithms for this class. This is contrasted with the quasipolynomial security of previous (higher-depth) AC 0 [⊕] candidates. We support our conjectures by proving resilience to several classes of attacks. Second, VDLPN implies simple constructions of pseudorandom generators and weak pseudorandom functions with security against XOR related-key attacks.

Introduction

Correlated secret randomness is a ubiquitous resource in cryptography. A one-time pad, namely a pair of identical random keys, enables perfectly secure communication. Kilian [Kil88] and Beaver [START_REF] Beaver | Efficient multiparty protocols using circuit randomization[END_REF][START_REF] Beaver | Precomputing oblivious transfer[END_REF] showed that more complex forms of correlated randomness can similarly facilitate secure multiparty computation (MPC)-protocols that enable two or more parties to jointly compute a function of secret inputs revealing nothing beyond the output. A useful example is an oblivious transfer (OT) correlation, where one party is given two random bits (s 0 , s 1 ) and another party gets (b, s b ) for a random bit b. Cryptographic power stems from the fact that the correlation forms a non-product distribution in which neither party can determine the secret of the other party.

Such correlations not only provide feasibility results, but are a central tool in essentially all concretely efficient instantiations of MPC in the setting of a dishonest majority. For example, two honest-but-curious parties can securely evaluate any Boolean circuit with s AND gates (and an arbitrary number of XOR/NOT gates) using 2s independent instances of an OT correlation, and communicating 2s bits per party. Moreover, the local computation of both parties involves just a small constant number of bit-operations per gate [START_REF] Goldreich | How to play any mental game or A completeness theorem for protocols with honest majority[END_REF][START_REF] Goldreich | Foundations of Cryptography: Volume 2, Basic Applications[END_REF]. The efficiency and simplicity of MPC protocols based on correlated randomness gives rise to the following common paradigm. In an offline preprocessing phase, before the inputs are known, the parties use a dedicated protocol to securely generate correlated randomness. Then, once the inputs are available, the parties use a (typically very efficient) online protocol to securely evaluate the target function by consuming the correlated randomness. The main challenge, and the core bottleneck of almost all practically oriented protocols, is to design efficient methods to securely generate correlated randomness, without revealing more information than prescribed by the joint distribution.

A sequence of recent works [BCGI18, BCG + 19b, BCG + 19a, BCG + 20] put forth a new technique for securely generating correlated randomness via pseudorandom correlation generators (PCGs). In the two-party case, a PCG provides a means for locally expanding a short correlated pair of seeds to a longer instance of a pseudorandom correlation. PCGs enable secure computation with "silent" preprocessing, where parties use a small amount of communication to securely generate the correlated seeds and then expand them to the target correlation without any interaction. Moreover, recent PCG constructions achieve this for useful correlations and with good concrete efficiency.

However, PCGs come with a major limitation: The expansion of the correlated seeds is an "all-or-nothing" procedure, where the target correlation is produced all at once without enabling fast random access to the long output.1 This is similar to the limitation of a standard pseudorandom generator (PRG), except that existing PCG constructions do not even support the type of (stateful) incremental evaluation enabled by standard PRGs in a "stream-cipher mode." This limits the use of PCGs to a monolithic form of silent preprocessing that requires parties to generate and store big amounts of correlated randomness they might want to use in the future.

In this work, we initiate the study of the natural desired target: a pseudorandom correlation function2 (PCF), which extends a PCG analogously to the way a pseudorandom function (PRF) [START_REF] Goldreich | How to construct random functions[END_REF] extends a PRG. Concretely, we seek to design short correlations of keys that can be expanded "on the fly" to a virtually unbounded number of pseudorandom correlation instances, and which further enable fast random access to these instances.

A bit more precisely, recall that a PRF is a keyed function f k : {0, 1} n → {0, 1} (n) , such that for a secret random key k, the outputs of f k are computationally indistinguishable from those of a random function. A strong PRF (or just PRF) is secure against distinguishers that query the function on arbitrary inputs x, while for a weak PRF (WPRF) the distinguisher is only given samples (x i , f k (x i )) for uniformly random inputs x i . Generalizing this notion, a (two-party) PCF is a keyed function f k such that for a suitable joint key distribution (k 0 , k 1 ), the outputs (f k 0 (x i ), f k 1 (x i )) are indistinguishable from instances of a given target correlation. An essential security requirement is that indistinguishability hold not only for outsiders, who observe the pairs of outputs, but also for insiders who know one of the two keys. Here too, one can consider both a strong PCF and a weak PCF. We use the weak notion by default, since it is easier to construct and it suffices for our motivating applications.

Traditional techniques for upgrading a PRG to a PRF in the standard setting, such as the tree-based GGM construction [START_REF] Goldreich | How to construct random functions[END_REF], do not apply here. The challenge lies in the requirement of security against insiders. Applying a GGM-style approach would require a PCG that expands its seeds to two instances of its own seed correlation. This seems infeasible for current PCG constructions and calls for a different approach to PCF design.

Overview of Contributions

In this work, we initiate a systematic study of pseudorandom correlation functions, and investigate related primitives and assumptions. We make the following main contributions.

Definition and generic construction. We start by formally defining (weak and strong) PCFs and put forth a natural general template for constructing them. The construction combines a (weak) PRF f k with a function secret sharing (FSS) [START_REF] Boyle | Function secret sharing[END_REF] scheme for either the PRF class itself or closely related function classes. A (two-party) FSS scheme for a function class F enables splitting any function f ∈ F into two succinctly described functions (f 0 , f 1 ), such that f = f 0 + f 1 and each share f i hides f . We show how our template can be instantiated using known FSS schemes for circuits [DHRW16, BGI + 18] together with any PRF. This leads to a general PCF construction for a useful class of "additive" correlations, which includes most of the useful correlations for MPC, under a standard cryptographic assumption, namely the Learning With Errors (LWE) assumption [START_REF] Regev | On lattices, learning with errors, random linear codes, and cryptography[END_REF].

PCFs from VDLPN. While the above LWE-based construction provides a theoretical feasibility result, it has poor asymptotic and concrete efficiency. Moreover, the construction uses the heavy machinery of fully homomorphic encryption and leaves open the possibility of constructing useful PCF instances from other, seemingly weaker, assumptions. We show how to efficiently construct PCFs for a broad class of useful correlations, including oblivious transfer (OT), vector oblivious linear-function evaluation (VOLE) [ADI + 17, BCGI18], and "multiplication triple" correlations [START_REF] Beaver | Efficient multiparty protocols using circuit randomization[END_REF], from a natural variable-density variant of the Learning Parity with Noise (LPN) assumption [START_REF] Blum | Cryptographic primitives based on hard learning problems[END_REF], or VDLPN for short, that we introduce and study in this work. These efficient PCF constructions are motivated by applications to MPC and non-interactive zero knowledge.

Applications of VDLPN. The VDLPN assumption is independently motivated by two additional applications. First, different flavors of this assumption give rise to WPRF candidates in depth-2 AC 0 [⊕] (concretely, XOR of conjunctions of input variables and their negations) that can be conjectured to have subexponential security, matching the best known learning algorithms for this class [START_REF] Hellerstein | On PAC learning algorithms for rich boolean function classes[END_REF]. This is contrasted with the quasipolynomial security of previous (higherdepth) AC 0 [⊕] candidates [ABG + 14, BR17]. We support the VDLPN assumption and related conjectures by proving resilience to several classes of attacks, including linear attacks that use the input samples to find a biased linear combination of the outputs, and algebraic attacks that exploit low rational degree. Finally, we observe that VDLPN implies simple constructions of PRGs and WPRFs with security against XOR related-key attacks. Previous constructions are either heuristic or rely on strong assumptions such as multilinear maps [START_REF] Abdalla | Algebraic XOR-RKA-secure pseudorandom functions from post-zeroizing multilinear maps[END_REF].

The remainder of the Introduction is organized as follows. First, in Section 1.2, we present our main candidate as a low-complexity WPRF, and then (Section 1.3) explain how its conjectured security can be viewed as a variable-density variant of the standard LPN assumption. In Section 1.4, we discuss applications of this candidate WPRF to security against XOR related-key attacks. Then, in Section 1.5, we discuss the construction of PCFs, which relies on the "FSSfriendliness" of our WPRF candidate. We conclude by discussing applications and comparison with alternative approaches and related works. A more detailed discussion of the conjectured security of our main WPRF candidate and its variants is deferred to Section 2.

Our Low-Complexity WPRF Candidate

Motivated by the goals of improving the efficiency of PCFs and diversifying the underlying assumptions, we put forth new WPRF candidates that are "FSS-friendly" in the sense of being compatible with existing PRG-based FSS schemes. Our candidates are in a very low complexity class: the class XOR • AND of polynomial-size, depth-2 boolean circuits with one layer of AND gates at the bottom and a single XOR gate at the top (both of arbitrary fan-in). 3 We also refer to such a circuit as an XNF formula (for XOR Normal Form). This is similar to DNF, except for replacing disjunction (OR) by XOR. We conjecture our candidates to have subexponential security in both the key length and the input length. Concretely, our main candidate f k : {0, 1} n → {0, 1} is of the form

f k (x) = D i=1 w j=1 i h=1 (x i,j,h ⊕ k i,j,h ), (1)
where w, D can be set to the security parameter λ, and n = w • D • (D -1)/2. We conjecture that this candidate is secure against 2 o(n 1/3 ) -time distinguishers. The security of this WPRF candidate is based on a natural variable-density flavor of the well-studied learning parity with noise (LPN) assumption that we will discuss below. A slightly different candidate is plausibly secure against 2 o( √ n) -time distinguishers, matching the best known learning algorithm for this class [START_REF] Hellerstein | On PAC learning algorithms for rich boolean function classes[END_REF].

(For both variants, restricting the distinguisher to 2 D samples and D to be, say, n o(1) , we get plausible security against 2 o(n/ log n) -time distinguishers.) Subexponential security is good enough to support λ bits of security (against 2 λ -bounded adversaries) in poly(λ) time, and is typically the strongest level of security one can hope to obtain from standard cryptographic assumptions. For a more thorough discussion on the security of our main candidate and its variants we refer to Section 2.3.

In contrast to our candidates, previous WPRF candidates in AC 0 [⊕] (namely, of constantdepth polynomial-size circuits with AND/OR/XOR gates of unbounded fan-in) were restricted to quasipolynomial security, which is considered "borderline insecure" and cannot support λ bits of security in poly(λ) time. Thus, our candidates fill a gap in the current landscape of (weak) PRF candidates in low complexity classes. See Section 2 below for related work.

We support the conjectured security of our candidates by analysis that proves their security against several classes of natural attacks, capturing essentially any relevant class of attacks we are aware of. This includes, for instance, linear attacks that try to correlate the outputs via an input-dependent linear combination, as well as algebraic attacks that exploit a low rational degree. The latter yielded a quasipolynomial-time distinguisher for a previous WPRF candidate in AC 0 [⊕] [ABG + 14, BR17].

Assuming our conjectures, the complexity class AC 0 [⊕] does not admit a 2 n o(1) -time learning algorithm, even under the uniform distribution. In fact, the same holds for the class of XNF formulas that can be alternatively viewed as sparse F 2 -polynomials in inputs and their negations. This also implies similar hardness for learning sparse F 2 -polynomials (without negations) in the standard PAC model, which allows for arbitrary input distributions. Our analysis and conjectured hardness assumptions complement the 2 Õ( √ n) -time PAC learning algorithm from [START_REF] Hellerstein | On PAC learning algorithms for rich boolean function classes[END_REF] for sparse polynomials, which also applies to XNF formulas by changing the input distribution. The conjectured hardness should be contrasted with efficient learning algorithms when membership queries are allowed [START_REF] Schapire | Learning sparse multivariate polynomials over a field with queries and counterexamples[END_REF][START_REF] Bshouty | On learning multivariate polynomials under the uniform distribution[END_REF]. This corresponds to our WPRF candidates not being strong PRFs.

Variable-Density LPN

The security hypothesis for our main WPRF candidate from Eq. (1) can be cast as a new natural variant of the standard Learning Parity with Noise (LPN) assumption [START_REF] Blum | Cryptographic primitives based on hard learning problems[END_REF]. We explain this below.

In its dual formulation, LPN asserts that for suitably chosen parity-check matrix H ∈ F N ×M 2 (where M > N ) and noise vector e ∈ F M 2 , the distribution (H, He) is pseudorandom, namely it is indistinguishable from (H, r) for a uniform vector r ∈ F N 2 chosen independently of H. Here H is typically chosen to be a uniformly random matrix and e an i.i.d. noise vector in which each entry is set to 1 with probability 0 < p < 1/2. Many other flavors of LPN have been used for different cryptographic applications. For instance, H can be structured [HKL + 12, MBD + 18] or even of "medium density" [START_REF] Misoczki | Mdpc-mceliece: New mceliece variants from moderate density parity-check codes[END_REF]. The noise vector e is sometimes chosen to have a fixed weight or even a regular structure [START_REF] Augot | A fast provably secure cryptographic hash function[END_REF], where e consists of disjoint blocks and each block contains a single nonzero entry in a random position.

We can interpret our WPRF candidate from Eq. (1) as a variable density version of the dual LPN assumption described above in the following way: For each i, the inner term i h=1 (x i,j,h ⊕ k i,j,h ) can be rephrased as an inner product of two weight-1 vectors H i,j , e i,j ∈ {0, 1} 2 i . 4 Concatenating the vectors H i,j for all i ∈ [D], j ∈ [w] results in one row of the matrix H (corresponding to one input x), and concatenating the vectors e i,j results in the error vector e. Note that the length of each such vector is M = O(w2 D ) and each block has twice the size and half the density of the previous block. Given N inputs x for the WPRF, we obtain a matrix H of dimension N times M , such that one output of our original WPRF construction corresponds exactly to one entry of He.

We refer to the conjectured security of this flavor of variable-density LPN as the VDLPN assumption. The core idea of VDLPN is that it allows the dimension of H and e to be superpolynomial in the input length n (while each entry of He is polynomial-time computable) without introducing too much structure or biasing the output. As outlined above, this assumption is equivalent to the security of the WPRF candidate in Eq. (1). In Section 2 we further motivate this choice and discuss its provable security against a variety of relevant attacks. We also discuss other flavors of the VDLPN assumption that correspond to alternative WPRF candidates.

Application to XOR-RKA Security

Independently of the PCF motivation, our new WPRF candidates are motivated by another cryptographic application: achieving security against related-key attacks (RKA) with respect to XOR functions. RKA security captures a model in which the attacker is allowed to see several instances of a primitive where the keys are not independent, but instead satisfy a relation of its choice. XOR-RKA security captures the setting where the adversary has access to the primitive with keys k, k ⊕ ∆ 1 , k ⊕ ∆ 2 , • • • , for fixed offsets of his choice. The VDLPN assumption that implies the security of our main WPRF candidate actually implies the stronger XOR-RKA security for free. This follows from the fact that the WPRF from Eq. (1) can be written in the form f k (x) = h(k ⊕ x), and so tampering with the key bits is equivalent to tampering with the (random) inputs. For details, see Section 6.5.

XOR-RKA is arguably the most natural flavor of RKA security, capturing fault injection attacks where an adversary can induce bit flips in cryptographic hardware and other forms of tampering (see [GLM + 04] and references therein). However, it is typically very hard to prove -the only "provable" XOR-RKA secure PRF is based on the very strong cryptographic assumption of multilinear maps [START_REF] Abdalla | Algebraic XOR-RKA-secure pseudorandom functions from post-zeroizing multilinear maps[END_REF]. Our main WPRF candidate implies simple PRGs and WPRFs whose XOR-RKA security follows from the VDLPN assumption. These can in turn be used for constructing other types of XOR-RKA secure variants of primitives that can be based on standard WPRF, including identification and authentication schemes, semantically secure encryption schemes [START_REF] Applebaum | Semantic security under related-key attacks and applications[END_REF], and passive XOR-RKA secure strong PRFs [START_REF] Applebaum | Related-key secure pseudorandom functions: The case of additive attacks[END_REF]. Finally, since our WPRF candidate has the form f k (x) = h(k ⊕ x), its security implies that the function h is correlation-robust in the sense of [START_REF] Ishai | Extending oblivious transfers efficiently[END_REF].

We stress that these XOR-RKA primitives depend on a new security assumption that is yet to withstand the test of time. This follows previous theory-oriented works that introduce new simple PRF candidates and study their resistance to concrete classes of attacks [MV12,ABG + 14, BR17, BIP + 18].

From FSS-friendly WPRF to PCF

We start this section by briefly explaining how to obtain a PCF from a WPRF together with a suitable function secret sharing scheme, and then show why our WPRF candidate is "FSSfriendly." Generic construction of PCFs. Recall that an FSS scheme for a function class F allows splitting a function f ∈ F compactly into two functions (f 0 , f 1 ), such that f = f 0 + f 1 and each share f i individually hides f . One example for a useful correlation is vector oblivious linear evaluation (VOLE) over a field F, where one party holds (a, c 0,i ) and the other party holds (b i , c 1,i ) such that c 1,i = c 0,i + a • b i , for fixed a. Now, a WPRF class F over F together with a FSS5 for a • F allows to construct a PCF for VOLE as follows: First an element a $ ← F and a key k for the WPRF are sampled at random, and then compact shares (f 0 , f 1 ) of a • f k are generated via the FSS. Now, a and f 0 are given to one party and k and f 1 to the other party. By the correctness of the FSS, for all x it holds f 1 (x) = -f 0 (x) + a • f k (x), and by the security of the FSS neither party learns about the others parties secrets.

A PCF for random OT can be constructed either directly based on the described approach using the techniques of [BCG + 19b,BCG + 19a], or alternatively, from a WPRF family over F 2 and a corresponding FSS. Both approaches additionally require a correlation-robust hash function (which, as discussed in Section 1.4, does not require any additional assumption in our case). We further show how to construct PCF for oblivious linear evaluation and multiplication triples given an FSS for both the WPRF class F and the square of F, namely

F 2 = {f • f : f, f ∈ F}.
The above constructions only realize our default notion of weak PCF, where inputs are chosen at random. This is good enough in applications where a common source of public randomness is available. Moreover, in the random oracle model, one can easily obtain a strong PCF from a weak one by applying the random oracle to the input.

"FSS-friendliness" of our candidates. The above approach can be instantiated from any WPRF together with a "high-end" FSS from LWE. Our WPRF candidates, on the other hand, are designed to be FSS-friendly, in the sense that they can be evaluated by lightweight function secret sharing schemes based on the existence of one-way functions. The primitive we use is a distributed point function (DPF) [START_REF] Gilboa | Distributed point functions and their applications[END_REF], namely an FSS scheme for the class of point functions {P α } α∈{0,1} * , where the function P α : {0, 1} |α| → F 2 evaluates to 1 on input α, and to 0 on all other inputs. Concretely efficient DPF schemes from any PRG were given in [START_REF] Boyle | Function secret sharing[END_REF][START_REF] Boyle | Function secret sharing: Improvements and extensions[END_REF].

Our main WPRF candidate, described in Eq. (1), is "FSS-friendly" as it can be seen as a sum of w • D point functions: Each AND term i h=1 (x i,j,h ⊕ k i,j,h ) can be viewed as evaluating a point function P α with α = (1 ⊕ k i,j,1 , . . . , 1 ⊕ k i,j,i ). Here we make crucial use of the fact that the identity of the variables in each term of Eq. ( 1) is public and only whether each variable is negated or not is secret.

Additionally, we propose an alternative low-complexity WPRF candidate that is even more FSS-friendly than our main candidate:

f k (x) = D i=1 w j=1 i h=1 (x j,h ⊕ k j,h ).
(2)

This candidate exploits the fact that in the best known DPF constructions [START_REF] Boyle | Function secret sharing: Improvements and extensions[END_REF], sharing the point function P α directly gives a sharing of all P α for α a prefix of α. All of our candidates can also be adapted to have outputs over rings instead of F 2 , with the same level of FSS-friendliness. This leads to PCF constructions for useful correlations over general rings -see Section 6.3. When plugging in our concrete candidate WPRFs we obtain further benefits. We construct a PCF for arbitrary, degree-2 correlations -additive secret shares of a random string X, together with shares of Y = p(X), for some multivariate degree-2 polynomial p -with a universal setup procedure. The latter means that the PCF key generation is independent of the polynomial p, and later during expansion the parties have PCFs for any choice of p. This overcomes the limitation of a previous LPN-based PCG construction from [BCG + 19b], which required computing all N 2 monomials.

Compared to the generic LWE-based construction of PCFs, the LPN-style assumptions that underly our specialized constructions seem qualitatively weaker. For instance, they are not known to imply additively homomorphic encryption or even collision-resistant hashing. VDLPNbased PCFs also have attractive efficiency features that beat the generic alternative both asymptotically and concretely (by several orders of magnitude). Finally, they achieve perfect correctness whereas LWE-based constructions have negligible error probability that we do not know how to remove. See Section 1.7 for a more detailed comparison.

Applications of PCFs

PCFs give rise to a number of interesting cryptographic applications, which we briefly outline here, and in more detail in Section 10.

Secure computation with correlated randomness. The most natural use case, as already mentioned, is their ability to produce a practically unlimited amount of correlated randomness for use in secure computation protocols. Similar to the case of PCGs, this application is not entirely immediate -a PCF cannot substitute for an ideal source of correlated randomness in every protocol, since knowing a short representation of this randomness can in some cases contradict security. We can show, however, that PCFs can be plugged directly into a large class of natural, practical protocols in a secure manner; this holds for any protocol that is secure even when a corrupt party can influence its own correlated randomness. In particular, this property is satisfied by many, standard secure multi-party computation (MPC) protocols in the preprocessing model, so PCFs allow us to transform these protocols to have reusable preprocessing. Here, a one-time setup protocol is first performed to distribute the keys for a PCF. After this setup, the PCF can be used for as many instances of the MPC protocol as is needed, without having to re-run the setup. Two-round MPC. A special class of multi-party computation protocols that have been developed recently [GGHR14, BL18, GS18] is those with just two rounds of interaction, the minimum that is possible. The two-round protocol of Garg et al. [START_REF] Garg | Two-round MPC: Information-theoretic and black-box[END_REF] uses a setup phase for producing a large number of random oblivious transfers, after which the entire protocols makes only blackbox use of a pseudorandom generator. Replacing this oblivious transfer setup with PCFs, we obtain a fully reusable preprocessing phase, which after its setup, can be used for any number of two-round MPC protocols.

Non-interactive zero knowledge with fully reusable preprocessing. Non-interactive zero knowledge (NIZK) allows a prover to convince a verifier of the truth of some statement, by just sending a single message. NIZK with preprocessing allows a setup phase with a trusted third party, who generates secret proving and verification keys, which are given to the prover and verifier, respectively. Preprocessing NIZK can have information-theoretic security given OT or VOLE correlations [KMO89, CDI + 19]. This motivated the use of a PCG-based approach in this context [BCGI18, BCG + 19b, WYKW20]. Using PCFs, we can obtain preprocessing NIZKs with fully reusable preprocessing, where a single setup consisting of PCF keys can be used to prove an arbitrary number of statements. Compared with other recent NIZK constructions in the designated verifier setting [LQR + 19], which can be based on LPN, the PCF approach requires a stronger preprocessing setup, but leads to simpler constructions with better concrete efficiency. These constructions do not require any cryptographic operations after expanding the PCF outputs.

Multi-party PCFs. Some of our two-party PCF constructions can be extended to the multiparty setting, where m parties can obtain correlated randomness, which remains secure even when up to m -1 keys have been corrupted. These extensions are possible by exploiting a programmability feature of the two-party PCFs, which means that some portion of the PCF outputs can be reused as outputs in a separate PCF instance. This allows generically constructing multi-party PCFs, in a similar way to previous constructions of multi-party PCGs [BCG + 19b].

Advantages of the VDLPN-Based PCF Construction

Without an FSS-friendly WPRF such as ours, it seems necessary to rely on general-purpose FSS schemes based on "public-key assumptions." These can be constructed from the LWE assumption using special fully homomorphic encryption (FHE) schemes [START_REF] Dodis | Spooky encryption and its applications[END_REF]. One can also combine a WPRF in NC 1 with an FSS for branching programs, where the latter can be based on the Decisional Diffie-Hellman assumption [START_REF] Boyle | Breaking the circuit size barrier for secure computation under DDH[END_REF]. However, this approach suffers from an inverse polynomial correctness error and has a high computational cost.

Below, we analyze the properties of LWE-based constructions, and compare these with our approach. Specifically, we will consider an FSS construction based on the more efficient ring-LWE assumption, and instantiate this with an exponential ring-LWE modulus q; this allows to obtain FSS and PCFs with an exponentially small error probability [START_REF] Dodis | Spooky encryption and its applications[END_REF], which is comparable to our constructions with perfect correctness.

Asymptotic efficiency. We first analyze an optimistic variant of a ring-LWE-based PCF, based on a WPRF which can be computed by a circuit of size Õ(λ); note that the only candidates we are aware of satisfying this are our WPRF from VDLPN (in the regime D = polylog(λ)), a permutation-based a candidate PRF by Miles and Viola [START_REF] Miles | Substitution-permutation networks, pseudorandom functions, and natural proofs[END_REF] and an "asymptotically optimal" candidate from [BIP + 18].

Fully homomorphic encryption from the ring-LWE assumption can be carried out with polylogarithmic overhead on top of the cleartext computation [START_REF] Gentry | Fully homomorphic encryption with polylog overhead[END_REF]. However, if we want an exponentially small correctness error in the FSS then the ciphertext modulus q is required to be exponential in the security parameter; this multiplies the overhead of homomorphic evaluation by Õ(λ), translating to a computational cost of Õ(λ 2 ) for each PCF evaluation. Regarding storage costs, the PCF key in this construction consists of Õ(λ) ring-LWE ciphertexts, giving a total key size of Õ(λ 3 ) bits. 6Moreover, the above computational cost only holds for a WPRF with Õ(λ) size circuits. PRF constructions from standard assumptions such as LWE, ring-LWE [START_REF] Banerjee | Pseudorandom functions and lattices[END_REF], number-theoretic assumptions [START_REF] Naor | Number-theoretic constructions of efficient pseudorandom functions[END_REF] or a natural generalization of AES [START_REF] Miles | Substitution-permutation networks, pseudorandom functions, and natural proofs[END_REF] require circuits of size Õ(λ 2 ), and result in Õ(λ 4 ) computation for PCF.

In contrast, our most aggressive candidate has key size Õ(λ 2 ) bits and computational cost Õ(λ) PRG operations, clearly improving over the alternatives in both complexity measures.

Concrete efficiency. Thanks to its simplicity, our constructions should in practice be more concretely efficient than LWE-based approaches. For example, we estimate that in our PCFs for VOLE or OT, each party's PCF key can be around 120kB, or 2MB based on our most conservative assumption, for a target bound of 2 30 samples. The parameters were chosen to achieve 100 bits of security against natural linear attacks such as BKW or the learning algorithm of [START_REF] Hellerstein | On PAC learning algorithms for rich boolean function classes[END_REF], and are based on the optimized PCF construction -see Remark 5.6 in Section 5.2 and Section 6.4. For further discussions and concrete conjectures regarding the exact security of our candidate, we refer the reader to Section 9. For comparison, Boyle et al. [BCG + 19b] considered building a PCG from ring-LWE-based function secret sharing (or homomorphic secret sharing) and a suitable pseudorandom generator. To obtain a reasonable computation time, the resulting PCG keys were larger than 3GB, and the stretch of the PCG was still sub-quadratic. Since a single FHE ciphertext is typically the order of several megabytes, and a PCF key will need many such ciphertexts, it seems inherent that LWE-based PCFs will suffer similarly in terms of concrete key size and/or computational cost.

Conceptually weaker assumption. LWE is a powerful assumption that implies, amongst other things, the existence of (leveled) fully homomorphic encryption. On the other hand, LPNtype assumptions, even in a low-noise regime such as VDLPN, are not known to imply additively homomorphic encryption or even collision-resistant hashing. Despite recent progress towards the latter [BLVW19,YZW + 19], it is still unknown whether we can construct collision-resistant hashing based on the polynomial hardness of LPN. For additively homomorphic encryption, there are negative results showing that any LPN-based construction must make non-black-box use of the underlying ring, which seems to require techniques going beyond existing constructions [START_REF] Applebaum | Arithmetic cryptography: Extended abstract[END_REF]. Therefore, our constructions show that PCFs, although a powerful primitive, can plausibly be realized under qualitatively weaker assumptions than before.

Perfect correctness. Our constructions satisfy perfect correctness for all parameter choices. With LWE, one can achieve negligible error probability by using a superpolynomial modulus, which requires a strong variant of LWE. We do not know how to obtain perfectly correct HSS under any variant of LWE, and when the modulus is restricted to be polynomial, current constructions have an inverse polynomial error probability.

Related Work

The study of secure computation with silent preprocessing is a recent but active research area [BCG + 17, Sch18, BCGI18, BCG + 19b, SGRR19, BCG + 19a]. There is a long line of work which studied constructions of low-bias PRGs and PRFs in low complexity classes [NN90,MST03, LRTV09, Shp09, Vio10, MRRR14, LV17, AK19]. In particular, the work of [START_REF] Gutfreund | Fooling parity tests with parity gates[END_REF] gives an εbiased strong PRF in AC 0 [⊕]; while it only achieves bias ε ≥ 1/superpoly(λ), it was strengthened in [START_REF] Healy | Randomness-efficient sampling within nc[END_REF] to achieve exponentially small bias. Our result is incomparable: we only construct a weak low-bias PRF family, but in the much smaller class XOR • AND. Heuristic constructions of PRFs and weak PRFs with provable security against classes of attacks have been studied in several previous work [MV11, ABG + 14, BIP + 18].

The combination PRFs and FSS (or the dual of homomorphic secret sharing) has been used before in different contexts. In particular, Boyle et al. used it to establish barriers for FSS [START_REF] Boyle | Function secret sharing[END_REF] and to obtain low-communication MPC protocols [START_REF] Boyle | Breaking the circuit size barrier for secure computation under DDH[END_REF], and Bartusek et al. [START_REF] Bartusek | Reusable two-round MPC from DDH[END_REF] used it to obtain two-round MPC protocols with reusable first round.

Technical Overview of our WPRF Candidates

In this section we give a more detailed technical overview of our new WPRF candidates, their design choices, and security analysis. We start with some general background.

The study of low-complexity cryptography has a long and rich history (see e.g. [Kha93, NR97, NRR00, AIK04, IKOS08, AR16, ABG + 14, BIP + 18] and references therein). Beyond the direct goal of minimizing the complexity of useful cryptographic primitives, this line of work is motivated by its relevance to hardness results and barriers in computational complexity theory and learning theory. Another, more recent motivation stems from the fact that many advanced primitives, such as secure computation, zero-knowledge proofs, fully homomorphic encryption (FHE), and indistinguishability obfuscation can induce their own efficiency metrics that motivate new designs of low-complexity primitives. Some relevant works in this direction include [IKOS08, ARS + 15, CCF + 16, MJSC16, LT17].

Our work gives yet another example of this kind: we efficiently realize PCFs by relying on WPRFs with a specific "FSS-friendly" structure. To instantiate this framework, we can use a "heavy hammer" approach, by relying on advanced constructions of FSS for all circuits [START_REF] Boyle | Function secret sharing[END_REF][START_REF] Dodis | Spooky encryption and its applications[END_REF]. However, while such an approach is interesting for establishing feasibility (which we do in Section 5), it is unsatisfactory for several reasons. First, it is unlikely to lead to any concretely efficient candidate (in the same way that hybrid FHE can be achieved by combining any FHE scheme with any standard block cipher, but the resulting scheme will be highly inefficient, hence motivating the design of FHE-friendly ciphers [ARS + 15, CCF + 16, MJSC16]). Second, it requires a strong flavor of "homomorphic cryptography," which implies a severe limitation on the type of assumptions we can realistically hope to rely on and the level of concrete efficiency. Finally, a curious limitation of all known constructions of FSS of circuits is that they cannot achieve perfect correctness.

Therefore, we take the opposite road: rather than starting from advanced FSS for all circuits based of FHE-style assumptions, we ask whether the simplest and most efficient known FSS schemes [START_REF] Boyle | Function secret sharing: Improvements and extensions[END_REF], which can be based on any one-way function, are already sufficiently powerful to instantiate our framework. Namely, we ask:

Is there a weak PRF in the complexity class captured by known FSS schemes based on one-way functions?

The FSS schemes of [START_REF] Boyle | Function secret sharing: Improvements and extensions[END_REF] capture point functions (which are equal to 0 everywhere except on a single point) and other classes of functions, interval functions (which take a fixed value for all inputs from an interval, and 0 otherwise), multi-dimensional generalizations of the latter, decision trees with fixed topology, as well as all linear combinations of the above. All these classes can be expressed as sums of point functions applied to different projections of the inputs. The schemes from [START_REF] Boyle | Function secret sharing: Improvements and extensions[END_REF] achieve better efficiency than that obtained via independent instances of DPF. But from a feasibility point of view, all these functions can be expressed as depth-2 AC 0 [⊕] circuits.

WPRFs with quasipolynomial security are known to exist in complexity classes as low as AC 0 , the class of polysize constant-depth circuits with arbitrary fan-in ∨, ∧ gates, under standard cryptographic assumptions such as factoring and DDH [Kha93,NR97,NRR00] or assuming the existence of random local functions [START_REF] Applebaum | Fast pseudorandom functions based on expander graphs[END_REF]. Furthermore, no weak PRF with better than quasipolynomial security can exist in AC 0 [START_REF] Linial | Constant depth circuits, Fourier transform, and learnability[END_REF]. Strong PRFs with quasipolynomial security are known to exist in AC 0 [⊕] under standard cryptographic assumptions [START_REF] Viola | The communication complexity of addition[END_REF], and quasipolynomial security is the best one can hope for in this class [START_REF] Razborov | Natural proofs[END_REF][START_REF] Carmosino | Learning algorithms from natural proofs[END_REF]. Finally, strong PRFs with exponential security are known in TC 0 [BPR12] and in the "almost constant-depth" variant of AC 0 [⊕] [YS16] under standard cryptographic assumptions, and heuristic constructions (with provable resistance against some classes of attacks) of strong PRFs in ACC 0 have been proposed in [BIP + A natural approach. A natural approach to building weak pseudorandom functions in a low complexity class, which was the starting point of most prior works [BPR12, ABG + 14, YS16, BIP + 18], is to start from (variants of) the learning parity with noise assumption. The LPN assumption postulates that the function family f s,B (x) = s, x + B(x) is a weak PRF, where s ∈ {0, 1} n is a secret random vector, and B(x) is a noise function which associates to each x a random noise coordinate that is biased towards zero. In spite of its low complexity, this weak PRF family is not efficient: the standard formulation of LPN requires entropy for each noise term, which is too much for storing B in the key, unless the number of samples is restricted to some fixed polynomial. An approach followed in several works [BPR12, AKPW13, ABG + 14, BIP + 18] tries to replace this B by a low-entropy and relatively simple function. This was partially successful: in [START_REF] Banerjee | Pseudorandom functions and lattices[END_REF][START_REF] Alwen | Learning with rounding, revisitednew reduction, properties and applications[END_REF], it was shown that, over F q for a large modulus q (superpolynomial in [START_REF] Banerjee | Pseudorandom functions and lattices[END_REF], polynomial in [START_REF] Alwen | Learning with rounding, revisitednew reduction, properties and applications[END_REF]), replacing B(x) by some appropriate rounding of x, s leads to a weak PRF under the LWE assumption. However, the use of larger fields puts the construction in a higher complexity class, namely, TC 0 . On the negative side, it was shown by Akavia et al. [ABG + 14] that no choice of rounding function could possibly allow to base the construction directly on LPN (over F 2 ) by the same approach. A candidate rounding function was suggested in [ABG + 14], and supported by some security analysis against classes of attacks; however, it was later broken in quasipolynomial time [START_REF] Bogdanov | Pseudorandom functions: Three decades later[END_REF]. More recently, a different choice of rounding function, using mod-3 addition, was suggested in [BIP + 18] and conjectured to resist the attack which breaks the candidate of Akavia et al.

Our Approach -the LPN Viewpoint

In this section we provide an intuition of our approach, this time starting from the primal LPN assumption. The final result of this section will be a more general definition of variable-density LPN which in particular captures our main candidate.

A first (unsuccessful) attempt. Assume a LPN-based weak PRF, written in the primal formulation: f s,B (x) = s, x + B(x), where s ∈ {0, 1} n and B is a function corresponding to sampling random noise biased towards 0 (i.e. B(x) = 1 with some fixed probability ε). What makes the description of the function B inherently inefficient (when aiming for superpolynomial security) is the following simple attack: consider an adversary getting N random samples (x (i) , f s,B (x (i) )) i≤N , arranged in a matrix A. Hence, the adversary gets (A, A• s + e), where e is a noise vector such that the i-th entry of e is B(x (i) ). To recover s (which suffices to distinguish all further samples from random), the adversary can attempt to guess a size-n subset of noise-free equations in the noisy linear system A • s + e, and solve it with Gaussian elimination. With noise rate ε (that is, ε = HW(e)/N ), a straightforward calculation shows that the attack succeeds with probability roughly exp(-nε), hence ε cannot be smaller than 1/n, and the description size of B must be at least N/n.

Therefore, the PRF key size is at least n + N/n ≥ √ N , where N is the number of adversarial queries.

However, the above attack scales with the length n of the secret vector s, not with its description complexity (and so do all known attacks on LPN). This suggests that we could rely on a variant of LPN with a secret vector s of much smaller description complexity d(n); this way, the key size would scale as d(n) + N/n, which can potentially be exponentially smaller than N if d(n) is exponentially smaller than n. Fortunately, there is a well-known candidate to instantiate this approach: one can sample the secret vector s from the same Bernouilli distribution as the noise vector e, and the resulting assumption will still be equivalent to the standard LPN assumption (see e.g. [START_REF] Yu | Pseudorandom functions in almost constant depth from low-noise LPN[END_REF] for a formal statement and proof of this equivalence). Hence, we could set n ≈ N , ε ≈ 1/n, and have the key size grow as ε(n) • N , almost independent of N (up to logarithmic terms, which we ignore in this high level discussion).

Unfortunately, this still does not quite work. The issue is that the input x to f s,B (x) = s, x + B(x) has the same length as s: hence, if we make s superpolynomially large by setting n ≈ N , the input x becomes superpolynomially large as well. To implement this approach efficiently, we would need the input x to have a short description as well. In other words, what we need is a variant of LPN which states that it is hard to distinguish A • s + e from random where s, e, and the rows of A, all have a short description (exponentially shorter than their length). Unfortunately, simply sampling A from a sparse (e.g.) Bernouilli distribution cannot work (since A • s + e would be sparse and easily distinguished from random).

A way around. Let us take a step back, and look at the two alternatives: we can set s to be short (and dense), hence allowing A to be relatively narrow, but then A • s + e is easily broken by a Gaussian elimination attack if e is sparse and the adversary gets enough samples. Or we can let s be long (and very sparse), but then A must be comparatively large, and if we make it sparse to reduce the description size of its rows, A • s + e is easily distinguished from random. In fact, any intermediate construction that interpolates between these two approaches falls to an appropriate combination of these simple linear attacks.

Our core observation is that we can defeat all such attacks by simultaneously implementing the above strategy of making x and s larger and more sparse at many different "levels of sparsity", and mixing the outcomes together. Concretely, fix some parameter D, and for i = 1 to D, let x i , e i ∈ {0, 1} w2 i be random sparse vectors of density 1/2 i , such that each x i , e i is twice larger than x i-1 , e i-1 . Then, consider the following candidate weak PRF family:

f e 1 ,••• ,e D (x 1 , • • • , x D ) = D i=1 x i , e i .
(Note that when choosing x i and e i of regular structure, i.e. such that each length-w block contains exactly one non-zero noise coordinate, this corresponds to our main WPRF candidate of Eq. (1).)

In the above, each term x i , e i will play both the role of a sparse noise term for masking the (more dense) previous terms, and the role of a parity term for the next terms. That is, the candidate is obtained as follows: start from A•s+e with dense A and a twice more sparse e, then replace e by a term of the form A • s + e where s , e , and the rows of A are twice more sparse than s, e and the rows of A respectively, and iterate the processus. An adversary collecting many samples must therefore distinguish D i=1 H i •e i from random given

(H 1 , • • • , H D ),
where each H i is a random sparse matrix of density 1/2 i , containing many x i samples as its rows. The sparser terms (with i close to D) defeat Gaussian attacks which attempt to find linear dependencies between the equations, since the corresponding secret vectors e i involve a very large number of unknowns. On the other hand, the more dense terms (with i close to 1) guarantee that the output distribution of f will be dense, and not biased towards 0. More interestingly, as our analysis will show, any possible linear attack, which attempts to distinguish f from a random function by detecting a bias in its output, falls somewhere inbetween these two extremal types of linear attacks, and is defeated by one of the H i •e i terms, for at least one i ∈ [1, D]. Furthermore, since each x i , e i has density 1/2 i and length O(2 i ), they can all be generated from short random strings. This generation process is extremely simple, and (for x i , e i of regular structure) will put our candidate weak PRF family into a very low complexity class: the class XOR • AND of polynomial-size depth-2 circuits consisting of arbitrary negations of the inputs, followed by a layer of AND gates at the bottom and a single XOR gate at the top. This is about the simplest strict subclass of AC 0 [⊕] which can possibly contain weak PRFs.

VDLPN vs. standard LPN.

The assumption underlying the security of the above candidate, which we study in this paper, is that

D i=1 H i • e i = [H 1 || • • • ||H D ] • (e 1 // • • • //e D ) (||
denotes horizontal concatenation, and // vertical concatenation) cannot be distinguished from random. The standard LPN assumption can be formulated in two ways: the primal formulation states that As+e is indistinguishable from random, given a random expanding matrix A; the equivalent dual formulation states that H • e is indistinguishable from random, given a random compressing matrix H. Many variants of this assumption exist, which change the distribution of the rows of H (e.g. to be slightly more sparse [START_REF] Misoczki | Mdpc-mceliece: New mceliece variants from moderate density parity-check codes[END_REF] and/or quasi-cyclic [MBD + 18]) and of the noise vector e (e.g. to have a regular structure [START_REF] Augot | A fast provably secure cryptographic hash function[END_REF]). All these variants follow the general template of postulating the hardness of dual LPN when the rows of H and the noise vector are sampled from some distributions (D row , D noise ). However, all known variants rely on pairs of distributions (D row , D noise ) which output vectors of fixed density.

In contrast, our weak PRF candidate also builds upon a dual-LPN-style assumption, with a matrix

H = [H 1 || • • • ||H D ]
and a noise vector e = (e 1 // • • • //e D ), but where the corresponding distributions (D row , D noise ) have both variable density: vectors sampled from these distributions are divided in D blocks of increasingly smaller density. This variable density structure is the key to allow simultaneously for exponentially many samples, while maintaining a polynomialsize compressed representation of the exponentially long vectors. We call this assumption the variable-density learning parity with noise assumption (VDLPN), and initiate its study in this paper.

Our Approach -the Low-Bias Function Viewpoint

For an alternative perspective, we can view our candidate as a methodology for obtaining a family of functions in a simple complexity class and with low bias, meaning that it provably resists a class of linear attacks. Below, we give some background on this approach, as well as some intuition behind why our candidate has low bias.

A large body of work has been dedicated to the construction of pseudorandom generators in low complexity classes. A common strategy is to PRGs which unconditionally resist restricted class of attacks, and to use them as plausible heuristic candidates for cryptographically secure PRGs. Perhaps the most representative example is the design of ε-biased PRGs, which unconditionally resist all linear distinguishers (see e.g. [NN90, MST03, LRTV09, Shp09, Vio10, MRRR14, LV17, AK19] and references therein). For the reader familiar with the literature on ε-biased PRG, we find it useful to provide an alternative interpretation of our approach as a natural approach to design an unconditionally secure low-bias weak pseudorandom function family (which we then conjecture to be also a cryptographically secure weak PRF family).

An ε-biased PRG is a function G : {0, 1} n → {0, 1} m which maps a short seed s ∈ {0, 1} n to a longer string G(s), such that no linear function L has advantage more than ε in distinguishing G(U n ) from U m (where U n , U m denote the uniform distributions over {0, 1} n and {0, 1} m respectively). A standard strategy to build a low-bias PRG, used for example in [START_REF] Mossel | On e-biased generators in NC0[END_REF][START_REF] Shpilka | Constructions of low-degree and error-correcting ε-biased generators[END_REF], is to design two generators, one secure against "light tests" (linear tests of small Hamming weight), and one secure against "heavy tests" (linear tests of large Hamming weight). Then, the PRG G is constructed as

G(x, y) = G light (x) ⊕ G heavy (y);
it is relatively easy to show that this gives a low-bias PRG since G inherits the security against all possible linear tests from its components.

Our candidate WPRF can be seen as following a generalization of this approach. We define an (ε, N )-biased WPRF to be a family {f k : {0, 1} n → {0, 1}} k of functions such that the restriction of the function k → (f k (x)) x∈{0,1} n to a random size-N subet of its outputs is an ε-biased pseudorandom generator with very high probability.

The work of Naor and Naor [START_REF] Naor | Small-bias probability spaces: Efficient constructions and applications[END_REF] shows that to build low-bias sample spaces, it is useful to restrict our attention to tests whose weight belongs to an interval of the form [2 i , 2 i+1 ], because such tests are provably fooled by random sparse vectors of density 1/2 i . Building upon this observation, we show how to get a low-complexity weak PRF that fools linear tests with weight in [2 i , 2 i+1 ]: we let the random inputs to the PRF define the rows of a random matrix H i of density 1/2 i . Using a Chernoff-type concentration bound for random variables with limited dependency, we prove that any given test with weight in [2 i , 2 i+1 ] is fooled by a constant fraction c of the columns of H i . Therefore, the distribution induced by H i • e i for a random sparse vector e i of weight w (i.e., a random subset-sum of columns of H i ) fools any given test with weight in [2 i , 2 i+1 ] with probability at least c w . We let f i,e i be the function which, on input x, samples a 1/2 i -dense row h of H i using randomness x, and outputs h • e i (by our argument, f i,e i has low bias against all tests with weight in [2 i , 2 i+1 ]). Finally, to get a 2 D -sample WPRF which has low bias with respect to all possible linear tests, we define

f e 1 •••e D (x 1 , • • • , x D ) = f 1,e 1 (x 1 ) ⊕ • • • ⊕ f D,e D (x D ).
Boolean circuit formulation As presented earlier in (1), we can also obtain the equivalent Boolean circuit formulation:

f k (x) = D i=1 w j=1 i h=1 (x i,j,h ⊕ k i,j,h ), (3)
where x, k ∈ {0, 1} wD(D-1)/2 are parsed as D sequences such that the i-th sequence, 1 ≤ i ≤ D is made up of i blocks of i bits. To see that this is equivalent to the VDLPN formulation above, observe that each block of i bits defines a binary unit vector of length 2 i and i h=1 (x i,j,h ⊕k i,j,h ) = 1 exactly when the inner product of the associated binary vectors in the key and in the input is 1. This formulation is conceptually simpler, and highlights that for a fixed key k, it corresponds to an XNF formula, namely a depth-2 circuit computing a single XOR of ANDs of literals (inputs or their negations). In the section below, we also mention several variants of the construction based on this boolean circuit perspective.

On the Security of Our WPRF Candidates

We conjecture that when instantiating our WPRF candidates with w = D = λ, every 2 o(λ) -size adversary can get a distinguishing advantage of at most 2 -Ω(λ) .

Since our main candidate has inputs of size n = O(wD 2 ) = O(λ 3 ), this corresponds to security against 2 o(n 1/3 ) -size adversaries.

For the variant with inputs of size n = O(wD) = O(λ 2 ), this corresponds to security against 2 o( √ n) -size adversaries, which is essentially optimal due to the existence of a 2 Õ( √ n) -time (and -size) learning algorithm for XNF with arbitrary distributions [START_REF] Hellerstein | On PAC learning algorithms for rich boolean function classes[END_REF]. When setting D = polylog(λ), w = λ, and restricting the adversary to polynomially many samples, we conjecture quasiexponential security against adversaries of size 2 o(n/polylog(n)) .

Of course, when defining low-complexity cryptographic primitives, one must be especially careful with security analysis. For example, the candidate WPRF construction in AC 0 [⊕] from [ABG + 14], which initially seemed to have plausible near-exponential security, was shown by Bogdanov and Rosen to be broken in quasipolynomial time via an algebraic "relinearization" attack [START_REF] Bogdanov | Pseudorandom functions: Three decades later[END_REF].

Here we prove resistance against this and a wide range of other attacks considered in the literature. In particular, we identify a large variety of attacks on LPN as special cases of linear distinguishers, as described above (Section 2.2), and provably rule them out for our main candidate, as well as an intermediate variant that has O(wD) input size (but bigger key size compared to our most "FSS-friendly" candidate). We observe that Gaussian elimination attacks [START_REF] Esser | LPN decoded[END_REF], statistical decoding attacks [AJ01, Ove06, FKI06, DAT17, Zic17], information set decoding attacks [Pra62,Ste88,FS09,BLP11,MMT11,BJMM12,MO15], BKW and variants [START_REF] Blum | Noise-tolerant learning, the parity problem, and the statistical query model[END_REF][START_REF] Lyubashevsky | The parity problem in the presence of noise, decoding random linear codes, and the subset sum problem[END_REF] all fall under this umbrella of a linear attack. We also rule out general algebraic attacks, which covers the attack on the Akavia et al. [ABG + 14] candidate, and statistical query attacks based on the learning algorithm of Linial, Mansour and Nisan [START_REF] Linial | Constant depth circuits, Fourier transform, and learnability[END_REF], and prove resistance to linear cryptanalysis as formalized by Miles and Viola [START_REF] Miles | On the complexity of non-adaptively increasing the stretch of pseudorandom generators[END_REF].

For all of the classes of attacks above, we prove that no 2 O(w) -size adversary mounting an attack from one of these classes can have advantage more than 2 -O(w) in distinguishing these candidates from random functions given 2 D samples. Further, we show our construction is (w/D)-wise independent , so resists all AC 0 tests of size 2 (w/D) c for some constant c.

Generalization to arbitrary rings. The VDLPN candidate can be generalized to work over larger rings than Z 2 , as detailed in Section 6.3. Here, we simply modify the VDLPN distributions by replacing ones with random non-zero elements from a ring R, which gives a candidate that is still FSS-friendly, and can be used for PCFs that output correlations over R. For an appropriate choice of parameters, our proof of resistance to linear attacks also extends to this arithmetic setting, and we conjecture its security against general attacks for an arbitrary choice of the ring R.

Variants with smaller inputs and smaller keys. Taking the boolean function definition seen in equation (3), we can consider several variants of the construction by making simplifications. For instance, our first variant reduces the input size from O(wD 2 ) to O(wD) bits by reusing inputs, replacing the variable x i,j,h with x j,h . This modified candidate still provably resists linear attacks, and we conjecture it also resists the other attacks we have considered. We can further modify this variant by XORing an additional triangular function to the weak PRF. Since triangular functions have high algebraic immunity, this allows us to prove resistance to algebraic attacks whilst retaining the benefit of the reduced O(wD) input size.

Finally, we present an aggressive variation which reduces the key size from O(wD 2 ) down to O(wD) bits. Here, the proofs of resistance for linear and algebraic attacks break down, however, we have not found any attacks, and put forward the security of this variant as an interesting direction for future study.

Organization

The remainder of the paper is organized as follows. After some preliminaries in Section 3, we first give definitions of PCFs in Section 4. We then present generic constructions of PCFs, based on function secret sharing for WPRF in Section 5. Section 6 describes our main WPRF candidate, explains why it is FSS-friendly and how it implies XOR-RKA secure PRGs and WPRFs. Section 7 analyzes its security, and Section 8 describes our variants. In Section 9 we propose concrete parameters based on concrete attacks. Finally, in Section 10 we describe further details of the applications of our PCFs.

Preliminaries

Notation

Given a field F and a number p ∈ [0, 1], we let Ber p (F) denote the Bernoulli distribution over F which returns a uniformly random element of F with probability p, and 0 with probability 1 -p. When the field is not specified, we assume F = F 2 by default. Given a vector v, we denote by HW( v) the number of nonzero entries of v. Given two integers (m, n) with 0 ≤ m ≤ n, we let S m,n (F) denote the uniform distribution over the set { v ∈ F n : HW( v) = m}. Here again, we assume F = F 2 when the field is not specified. Given matrices A, B, we denote A//B their vertical concatenation and A||B their horizontal concatenation (assuming the dimensions match).

Preliminaries on Bias

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

bias u (D) = 1 2 -Pr v $ ←D [ u • v = 1] .
The bias of D, denoted bias(D), is the maximum bias of D with respect to any nonzero vector u:

bias(D) = max u =0 n bias u (D).
We recall a number of useful facts about bias. First, observe that when D is the uniform distribution over a multiset S, it holds that

bias u (D) = 1 2 - 1 |S| v∈S u • v . 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 fact about the bias of the exclusive-or of independent distributions (cf. [START_REF] Shpilka | Constructions of low-degree and error-correcting ε-biased generators[END_REF]).

Lemma 3.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 ).

Concentration Bounds

We recall several standard concentration bounds from the literature.

Lemma 3.3 (Bienaymé-Chebyshev Inequality) Let X be a random variable with finite expected value µ and finite nonzero variance σ 2 . Then for any k > 0,

Pr[|X -µ| ≥ kσ] ≤ 1 k 2 . Lemma 3.4 (Chernoff Inequality) Let n ∈ N and let (X 1 , • • • , X n ) be independent random variables taking values in {0, 1}. Let X denote their sum and µ ← E[X]. Then for any δ ∈ [0, 1], Pr[X ≥ (1 + δ)µ] ≤ exp - δ 2 µ 3 .
Bounded Difference Inequality. Eventually, we will need a Chernoff-type concentration bound for dependent random variables. The bounded difference inequality was first proved by McDiarmid in [START_REF] Mcdiarmid | On the method of bounded differences[END_REF]. It is an application of the more general Azuma inequality [START_REF] Azuma | Weighted sums of certain dependent random variables[END_REF] which provides a powerful generalization of the Chernoff-Hoeffding inequality to martingales satisfying some bounded difference condition. Below, we state the bounded difference inequality in a form less general than the one proven in [START_REF] Mcdiarmid | On the method of bounded differences[END_REF], which suffices for our purpose. Let (n, m) ∈ N 2 be two integers. We say that a function Φ : [n] m → R satisfies the Lipschitz property with constant d if for every x, x ∈ [n] m which differ in a single coordinate, it holds that Then

|Φ( x) -Φ( x )| ≤ d.
Pr[Φ(X 1 , • • • , X m ) < E[Φ(X 1 , • • • , X m )] -t] ≤ exp - 2t 2 m • d 2 .

Weak Pseudorandom functions

We consider here weak PRFs, which relax standard PRFs by only considering distinguishers that get the outputs of the function on uniformly random inputs. We require subexponential security by default, namely security against distinguishers of size 2 n for some > 0. This is the typical level of security achieved by constructions based on the strongest plausible versions of standard cryptographic assumptions. We formally define this notion below.

Definition 3.6 ((Weak) pseudorandom function [START_REF] Goldreich | How to construct random functions (extended abstract)[END_REF][START_REF] Naor | Synthesizers and their application to the parallel construction of pseudo-random functions[END_REF]) Let λ ∈ N denote a security parameter and n = n(λ), κ = κ(λ) be monotonically-increasing and polynomiallybounded input length and key length functions, respectively. A (weak) pseudorandom function is syntactically defined by a function family

F = {F λ : {0, 1} κ × {0, 1} n → {0, 1}}
, where the output F λ (K, x) can be computed from (K, x) in polynomial time. Since λ and κ are determined by the input length n, we will sometimes write F K (x) instead of F λ (K, x). For T = T (κ) and ε = ε(κ), we say that F is a (T, ε)-secure strong pseudorandom function (PRF), if for every λ ∈ N and every oracle circuit D of size T (κ), it holds

Pr k [D f k (•) = 1] -Pr R [D R(•) = 1] ≤ ε(κ), where κ = κ(λ), k $ ← {0, 1} κ is chosen at random, and R : {0, 1} n → {0, 1} is a truly random function. A T -secure PRF is a (T, 1/T )-secure PRF.
We say that F is a (T, ε)-secure weak PRF (WPRF) or T -secure WPRF if the above holds when D only gets access to samples (x i , f k (x i )), where x i $ ← {0, 1} n are chosen uniformly and independently. Finally, we say that a (W)PRF F has polynomial security if it is T -secure for every polynomial T , and that it has subexponential (resp., quasipolynomial, exponential) security if there exists c > 0 such that it is T -secure for T = 2 κ c (resp., T = κ log c κ , T = 2 κc ). In this work, when we refer to a (weak) PRF without specifying the level of security, we assume subexponential security by default.

Defining Pseudorandom Correlation Functions

In this section we formally define the notion of pseudorandom correlation functions (PCFs), the new primitive studied in this work. At a high-level, a PCF extends the previous notion of a pseudorandom correlation generator (PCG) [BCG + 19b] analogously to the way a pseudorandom function (PRF) extends a pseudorandom generator (PRG).

Similarly to the notion of a PCG, a PCF should securely realize some ideal target correlation. A simple example for a useful ideal correlation is a random bit-oblivious-transfer (OT) correlation, defined by a pair of random variables (Y 0 , Y 1 ) such that Y 0 = (s 0 , s 1 ) is uniform over {0, 1} 2 and Y 1 = (c, s c ) for a random bit c. This correlation is "finite" in the sense that it has a fixed output length.

It is often useful to consider not only finite correlations, but also infinite families of finite correlations where the output length can grow with the security parameter λ. In order to define a meaningful notion of PCF for such a family of correlations, we require the correlation to satisfy the following "reverse sampleability" property: There exists an efficient algorithm that, given an output y σ in the support of Y σ , reverse-samples the other output y 1-σ from the right conditional distribution, namely [Y 1-σ |Y σ = y σ ]. We formalize this below. Definition 4.1 (Reverse-sampleable correlation) Let 1 ≤ 0 (λ), 1 (λ) ≤ poly(λ) be outputlength 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

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}: λ) , such that for all σ ∈ {0, 1} the following distributions are statistically close:

y (i) σ ← PCF.Eval(σ, k σ , x (i) ) b ← A(1 λ , (x (i) , y (i) 0 , y (i) 1 ) i∈[N (λ)] ) return b Figure 1: Pseudorandom Y-correlated outputs of a PCF. y 1-σ ∈ {0, 1} 1-σ (
{(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 σ )}
We would typically like a PCF for a given correlation, say an OT correlation, to output for each input an independent pair sampled freshly from the correlation. However, we will sometimes be interested in PCFs that also have correlations across different inputs. For instance, in a vectoroblivious-linear-evaluation (VOLE) or authenticated multiplication triples correlation there is a secret multiplier that is common to all inputs. To capture this more general case, we introduce a reverse sampleable correlation with setup, which allows all algorithms to depend on a fixed global secret, ensuring consistency across different invocations.

Remark 4.2 A reverse-sampleable correlation with setup consists of an additional algorithm Setup that on input 1 λ samples a master key mk, which the algorithms Y, RSample in Definition 4.1 take as extra input. The reverse sampling property is then required to hold for all mk in the image of Setup. For a formal definition we refer to Definition D.1 in Appendix B.

We are now ready to formalize our main notions of PCF. We start with our default notion of weak PCF, in which security holds for randomly chosen inputs, and then define the notion of strong PCF. As is often done in the context of PRFs, it will be convenient to consider not a single function defined over {0, 1} * but an infinite family of finite functions parameterized by a security parameter λ, where the input length of the λ-th function is polynomial in λ. For simplicity, in the following we focus on correlations without setup, for the full definitions we refer to Appendix B.

Definition 4.3 (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} σ (λ) .7

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

Exp sec A,N,σ,0 (λ) : (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
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 1. 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 2 (again, with N (λ) samples).
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.

Roughly speaking, the above security notion of PCF extends the corresponding security notion for PCGs (see Definitions A.1, A.3 in Appendix A) as follows: (PCF.Gen, PCF.Eval) is a PCF for Y, if for every polynomial N = N (λ), and random ensemble of sets X = (X λ ) λ∈N , where X λ = (x 1 , . . . , x N (λ) ) ⊆ {0, 1} n(λ) , the pair of algorithms PCG = (PCG.Gen, PCG.Expand) defined as

• PCG.Gen(1 λ ) samples (k 0 , k 1 ) ← PCF.Gen(1 λ ). • PCG.Expand(σ, k σ ) computes y (i) σ ← PCF.Eval(σ, k σ , x (i) ) for all i ∈ [N (λ)] and returns (y (i) σ ) i∈[N (λ)] .
is a PCG for Y with overwhelming probability over the choice of X .8 . We turn to define the strong notion of PCF, where pseudorandomness of outputs and security holds for adversarially chosen queries.

Exp s-pr A (λ) : (k 0 , k 1 ) $ ← PCF.Gen(1 λ ) Q = ∅ b $ ← {0, 1} b ← A O b (•) (1 λ ) if b = b return 1 else return 0 O 0 (x) : if (x, y 0 , y 1 ) ∈ Q: return (y 0 , y 1 ) else: (y 0 , y 1 ) ← Y(1 λ ) Q = Q ∪ {(x, y 0 , y 1 )} return (y 0 , y 1 ) O 1 (x) : for σ ∈ {0, 1}: y σ ← PCF.Eval(1 λ , σ, k σ , x) return (y 0 , y 1 ) Figure 3: Strong pseudorandom Y-correlated outputs of a PCF. Exp s-sec A,σ (λ) : (k 0 , k 1 ) $ ← PCF.Gen(1 λ ) b $ ← {0, 1} b ← A O b (•) (1 λ , σ, k σ ) if b = b return 1 else return 0 O 0 (x) : y 1-σ ← PCF.Eval(1 -σ, k 1-σ , x) return y 1-σ O 1 (x) : y σ ← PCF.Eval(σ, k σ , x) y 1-σ ← RSample(1 λ , σ, y σ ) return y 1-σ
Pr[Exp s-pr A (λ) = 1] - 1 2 ≤ ε(λ)
for all sufficiently large λ, where Exp s-pr A (λ) is as defined in Figure 3.

• Strong security. For all σ ∈ {0, 1} and non-uniform adversaries A of size B(λ) asking at most N (λ) queries to the oracle O b (•), it holds

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

From Weak to Strong PCFs

Assuming access to a random oracle we can transform a weak PCF into a strong PCF as described in the following.

Theorem 4.5 Let PCF = (PCF.Gen, PCF, Eval) be an (N, B, ε)-secure PCF for correlation Y with input length n(λ), and let H : {0, 1} n (λ) → {0, 1} n(λ) be a hash function modeled as a programmable random oracle. Then PCF = (PCF.Gen , PCF, Eval ) as defined in Figure 5 is a strong (N, B , ε)-secure PCF for correlation Y with input length n (λ) for any B (λ) ≤ N (λ).

Proof. Let A be an (N, B , ε)-adversary on the strong pseudorandomness of outputs of PCF . We construct an adversary B on the pseudorandomness of outputs of PCF as follows: The adversary B obtains (x (i) , y

(i) 0 , y (i) 1 ) i∈[N (λ)
] via its experiment. Without loss of generality we assume that A always queries the random oracle before asking a query to the experiment oracles. On the i-th query of A to H, B replies x (i) . Note that the number of oracle queries of B is upper bounded by its size B (λ) ≤ N (λ). On an oracle query x, B returns (y

(i) 0 , y (i) 1 )
, where i is such that x (i) = x. Finally, B forwards the output of A to its own experiment. Then, the probability of Transformation from weak to strong PCF

• PCF.Gen (1 λ ): On input 1 λ , return (k 0 , k 1 ) ← PCF.Gen(1 λ ).
• PCF.Eval (σ, k σ , x): On input σ ∈ {0, 1}, key k σ and input value x ∈ {0, 1} n (λ) , return y σ ← PCF.Eval(σ, k σ , H(x)). We omit the of security of PCF as it is almost analogous to the above.

5 PCFs from Function Secret Sharing for a Weak PRF or FSS for short, allows splitting a function f : {0, 1} n → G, where G is an Abelian group, into two functions f 0 , f 1 that add up to f but individually hide f . Each share f σ of f is described by a succinct key that enables its efficient evaluation on an input x ∈ {0, 1} n . We assume that f comes from a public function family F, which is an infinite collection of function descriptions together with an efficient evaluation algorithm. We abuse notation and write f ∈ F to refer to both the function and its description.

Definition 5.1 (Function Secret Sharing) A function secret sharing (FSS) scheme for function family F = {f : {0, 1} n → G}, where (G, +) is a an Abelian group, is pair of PPT algorithms FSS = (FSS.Gen, FSS.Eval) with the following syntax:

• FSS.Gen(1 λ , f ), given security parameter λ and description of a function f ∈ F, where f : {0, 1} n → G, outputs a pair of keys (K 0 , K 1 ); we assume that λ, n, G are determined by each key.

• FSS.Eval(σ, K σ , x), given a key K σ for party σ ∈ {0, 1}, and an input x ∈ {0, 1} n , outputs a group element y σ ∈ G.

The scheme should satisfy the following requirements:

• Correctness: For any f ∈ F with input domain {0, 1} n and x ∈ {0, 1} n , we have

Pr σ∈{0,1} FSS.Eval(σ, K σ , x) = f (x) (K 0 , K 1 ) ← FSS.Gen(1 λ , f ) = 1
• Security: For any σ ∈ {0, 1}, there exists a PPT simulator Sim such that for any sequence f λ ∈ F of polynomial-size function descriptions, the distributions

{(σ, f λ , K σ ) (K 0 , K 1 ) ← FSS.Gen(1 λ , f λ )} and {(σ, f λ , K σ ) K σ ← Sim(1 λ , Leak σ (f λ ))} are computationally indistinguishable.
The default choice for the leakage functions is Leak σ (f ) = (n, G), namely we allow leaking the input and output domains of f .

Note that previous FSS definitions only consider a single leakage function Leak that applies to both parties. Here we will use asymmetric leakage, with distinct functions Leak 0 , Leak 1 , to capture constructions based on puncturable PRFs. When the leakage functions Leak σ are efficiently invertible, which will always be the case in this work, one could replace the above simulation-based security definition by requiring indistinguishability of any pair of functions that have the same leakage. Some of our constructions also require the following property, that outputs of the Eval algorithm on random inputs are pseudorandom. In other words, this means that FSS.Eval is a weak pseudorandom function for a suitable distribution of keys.

Definition 5.2 (FSS with Weak Pseudorandom Outputs) We say that an FSS scheme (FSS.Gen, FSS.Eval) for F has weak pseudorandom outputs if for any σ ∈ {0, 1}, N = poly(λ), and any sequence of polynomial-size function descriptions f λ ∈ F, with domain {0, 1} n and range G = G(λ), for n = n(λ) = poly(λ) and log |G(λ)| = poly(λ), the distribution

(x (i) , y (i) ) N i=1 (K 0 , K 1 ) ← FSS.Gen(1 λ , f λ ), x (i) ← {0, 1} n , y (i) ← FSS.Eval(σ, K σ , x (i) ) λ∈N is computationally indistinguishable from the uniform distribution on ({0, 1} n × G) N .
Boyle et al. [START_REF] Boyle | Function secret sharing[END_REF] showed that FSS schemes for certain classes of 'poly-spanning' function families have pseudorandom outputs. This does not cover the classes of functions we are interested in. However, any FSS scheme can be easily modified to have weak pseudorandom outputs using a weak PRF {F k : {0, 1} n → G} k , by having each party add or subtract F k (x) when running FSS.Eval on input x. Note that our concrete instantiations described in Section 6.4 already have weak pseudorandom outputs, without this modification.

PCF for Vector Oblivious Linear Evaluation

Vector oblivious linear evaluation, or VOLE, is a correlation over a ring R where each pair of samples can be seen as an additive secret sharing of one component in a scalar-vector product. Concretely, define the ideal VOLE correlation over R by the pair of randomized algorithms (Setup, Y), where Setup samples a uniformly random a ∈ R, and Y(1 λ , a) outputs a pair (a, c 0 ), (b, c 1 ), where b, c 0 are uniform in R, and c 1 = c 0 + a • b. The VOLE correlation can be used in secure two-party computation tasks such as secure linear algebra, private keyword search, and computationally efficient zero-knowledge proofs [ADI + 17, BCGI18, WYKW20].

In Fig. 6, we give a simple construction of a PCF for VOLE, from any function secret sharing scheme for scalar multiples of a WPRF family. We remark that for our concrete instantiations given later, FSS for this function family can be obtained with a small tweak to the basic construction of FSS for the WPRF. In the construction, one party is given the WPRF key, while the other party gets the secret scalar a ∈ R, and each party additionally gets an FSS share of a multiplied by the WPRF. This allows an output to be computed with one call to FSS.Eval from each party.

Theorem 5.3 Let R = R(λ) be a finite commutative ring. Suppose there exists an FSS scheme for scalar multiples of a family of weak pseudorandom functions F = {F K : {0, 1} n → R} K∈{0,1} λ . Then, there is a PCF for the VOLE correlation over R, given by the construction in Fig. 6.

Proof. First, note that since we assume the existence of a WPRF, we can assume w.l.o.g. that the scheme FSS = (FSS.Gen, FSS.Eval) satisfies the weak pseudorandom outputs property. We prove the PCF security property for the two separate cases in Definition B.2, and then show that the PCF has pseudorandom correlated outputs.

Security with σ = 0. In the real experiment, Exp sec A,σ,0 (λ), the adversary A is run on input the PCF key k 0 = (K fss 0 , a), and the N random input/output pairs (x (i) , (b i , c 1,i )), where x (i) is uniformly random, b i = F K (x (i) ) and c 1,i = FSS.Eval(1, K fss 1 , x). We show that this is indistinguishable from the ideal experiment, where (b i , c 1,i ) are instead reverse-sampled using (a, c 0,i ) derived from key k 0 . We use the following sequence of hybrid experiments.

In the first hybrid, instead of computing c 1,i from FSS.Eval using key K fss 1 , we compute c 1,i = c 0,i + ab i in R. Note that by the correctness property of the FSS scheme, this hybrid is statistically close to the real experiment.

Next, we switch the FSS key K fss 0 with a simulated key K fss 0 ← Sim(1 λ , n, R) using the FSS simulator Sim. The values c 0,i are then obtained from the new key, and c 1,i computed from this as before. Due to the security property of the FSS, and the fact that c 1,i is independent of K fss 1 , this is computationally indistinguishable from the previous experiment.

In the final hybrid, we replace the b i values with uniformly random elements from R, and again compute c 1,i = c 0,i + ab i but using the new b i . This is identical to the ideal experiment, and indistinguishability holds by a standard reduction to the security of the WPRF.

Security with σ = 1. Security in this case follows immediately from the correctness property of the FSS scheme. We have that in the real experiment, A gets a PCF key k 1 = (K fss 1 , K), and the N random input/output pairs (x (i) , (a, c 0,i )), computed using a random x (i) and (a, c 0,i ) = PCF.Eval(0, k 0 , x (i) ). The only difference between this and the ideal experiment is the way c 0,i is computed, and FSS correctness implies that these are statistically close.

Pseudorandom correlated outputs. We now show that the joint distribution of the N output pairs (a, c 0,i ), (b i , c 1,i ), on random inputs x (i) , is indistinguishable from a set of samples from the VOLE correlation. Starting from the real distribution, we use the following sequence of experiments, which is similar to the hybrids in the security argument when σ = 0; the only difference here is that we need to rely on the weak pseudorandom outputs property of the FSS, instead of its security property.

We first replace c i,1 with c i,0 + ab i , where we get statistical indistinguishability because of the FSS correctness property. Next, we replace each c 0,i with a random element of R; here, we appeal to the weak pseudorandom outputs property of the FSS scheme, which implies this is computational indistinguishable from the previous experiment. Finally, we can replace b i with random elements of R, due to the security of the WPRF.

PCF for Oblivious Transfer

A 1-out-of-2 string-OT correlation is sampled as a pair (s 0 , s 1 ) and (c, s c ), where s 0 , s 1 are the OT sender's random strings in {0, 1} λ , and c is a random choice bit given to the receiver. We construct a PCF for independent instances of string-OT using FSS for a WPRF, together with a correlation-robust hash function [START_REF] Ishai | Extending oblivious transfers efficiently[END_REF]. Note that the security of our WPRF candidates implies a correlation-robust hash function, so instantiating with these candidates does not require the extra assumption.

Definition 5.4 (Correlation robust hash function) Let N = poly(λ). We say that an efficiently computable function H : {0, 1} λ → {0, 1} λ is correlation robust if the distribution

PCF for Vector Oblivious Linear Evaluation

Let F = {F K : {0, 1} n → R} K∈{0,1} λ be a weak PRF, and FSS = (FSS.Gen, FSS.Eval) an FSS scheme for {cF K } c∈R,K∈{0,1} λ with weak pseudorandom outputs.

PCF.Gen(1 λ ):

1. Sample a WPRF key K ← {0, 1} λ and a ← R 2. Sample a pair of FSS keys (K fss 0 , K fss 1 ) ← FSS.Gen(1 λ , aF k ) 3. Output the keys k 0 = (K fss 0 , a) and k 1 = (K fss 1 , K).

PCF.Eval(σ, k σ , x): On input a random x:

• If σ = 0: 1. Let c 0 = -FSS.Eval(0, K fss 0 , x) 2. Output (a, c 0 ) • If σ = 1: 1. Let c 1 = FSS.Eval(1, K fss 1 , x) 2. Let b = F K (x) 3. Output (b, c 1 )
Figure 6: PCF for VOLE over the ring R based on FSS for scalar multiples of a weak PRF {t 1 , . . . , t N , H(t 1 ⊕ s), . . . , H(t N ⊕ s)} where s and t 1 , . . . , t N are independent and uniformly sampled from {0, 1} λ , is computationally indistinguishable from the uniform distribution on {0, 1} 2λN .

Our construction, in Fig. 7, proceeds by first creating correlated OTs, which are OTs where the sender's messages are all of the form q i , q i ⊕s for a single, random s. Then, as in [START_REF] Ishai | Extending oblivious transfers efficiently[END_REF] and later works, the strings are hashed using the public, correlation robust function, which converts them into OTs on random strings. Note that to rely on correlation robustness instead of a stronger notion, we require that each q i is uniform; since this is not the case in our construction, we mask it with a portion of the random, PCF input.

To construct correlated OTs, the setup phase will first sample a key K for a WPRF with range {0, 1}, and random bits s 1 , . . . , s λ . We then create FSS keys for λ functions, each of which is either the WPRF F K or the zero function, depending on the bit s j . Evaluating all λ FSS keys on a public input x (i) , the sender and receiver obtain respective strings q i and t i in {0, 1} λ such that

q i ⊕ t i = s • F K (x (i) )
where s = (s 1 , . . . , s λ ), and • computes the AND of every bit in s with F k (x (i) ).

As well as the FSS keys, we then give out the key K to the receiver and s to the sender. The receiver's values t i satisfy t i = q i ⊕ c i • s, where c i = F K (x (i) ) is its choice bit, which means the values (q i , q i ⊕ s) known to the sender form a correlated OT as required.

The above outline assumes we have FSS for a WPRF family together with the zero function. However, it suffices to have FSS for the WPRF, since any FSS scheme for a family F with outputs in F 2 implies FSS for the class F ∪ {0}, which includes the zero function [START_REF] Boyle | Function secret sharing[END_REF]. This holds because without loss of generality, we can assume that the FSS.Eval function is symmetric

PCF for Oblivious Transfer

Let F = {F K : {0, 1} n → {0, 1}} K∈{0,1} λ be a WPRF, and FSS = (FSS.Gen, FSS.Eval) an FSS scheme for F ∪ {0}.

PCF.Gen(1 λ ):

1. Sample a WPRF key K ← {0, 1} λ and a random s ← {0, 1} λ 2. For j = 1, . . . , λ, sample (K fss 0,j , K fss 1,j ) ← FSS.Gen(1 λ , s j F K ) 3. Output the keys k 0 = (s, K fss 0,1 , . . . , K fss 0,λ ) and k 1 = (K, K fss 1,1 , . . . , K fss 1,λ ).

PCF.Eval(1 λ , σ, k σ , x): On input a random x ∈ {0, 1} n , let x be the first λ bits of x and then:

• If σ = 0:

1. Compute q = (q 1 , . . . , q λ ), where q j = FSS.Eval(0, K fss 0,j , x) 2. Compute y 0 = H(x ⊕ q), y 1 = H(x ⊕ q ⊕ s) 3. Output (y 0 , y 1 ) for both keys, and also that each key hides whether it is the key for party 0 or party 1. The zero function is then shared by sampling a pair (K fss 0 , K fss 1 ) and giving K fss 0 to both parties.

• If σ = 1: 1. Compute c = F K (x) 2. Compute t = (t 1 , . . . , t λ ), where t j = FSS.Eval(1, K fss 1,j , x) 3. Output (c, z), where z = H(x ⊕ t)
Theorem 5.5 Suppose there exists an FSS scheme for a family of weak pseudorandom functions F = {F k : {0, 1} n → {0, 1}} k∈{0,1} λ , and a correlation robust hash function H : {0, 1} λ → {0, 1} λ . Then, there is a PCF for the string-OT correlation, given in Fig. 7.

Proof.

We first prove the security property of the PCF, and then the pseudorandomness property. As in Definition 4.3, we consider N = poly(λ) queries on random inputs x (1) , . . . , x (N ) , where we let (x ) (i) be the first λ bits of x (i) .

Corrupt receiver (σ = 1). In the real experiment, Exp sec A,σ,0 (λ), the adversary A is given k 1 = (K, K fss 1,1 , . . . , K fss 1,λ ) and random input/output pairs (x (i) , (y i,0 , y i,1 )). Here, K fss 1,j is an FSS key for the function s j F K , where s j ∈ {0, 1}, and y i,0 , y i,1 are the OT sender's strings from applying PCF.Eval on the key k 0 . Note that computing (y i,0 , y i,1 ) involves first computing a string q i using FSS.Eval on the keys (K fss 0,1 , . . . , K fss 0,λ ), and then hashing both q i and q i ⊕ s. Consider a hybrid experiment where we replace the strings q i with q i = t i ⊕s•F K (x (i) ), where t i comes from FSS.Eval on the keys (K fss 1,1 , . . . , K fss 1,λ ), and then give A strings y i,0 , y i,1 computed with the new q i . By the correctness of the FSS scheme, this experiment is statistically close to the previous one.

In the next λ experiments, we successively replace each FSS key K fss 1,j given to A, for j = 1, . . . , λ, with a simulated key Sim(1 λ , {0, 1} n+λ , F 2 ), and recompute each t i , q i , y i,0 , y i,1 with the simulated keys. By the fact that the strings y i,0 , y i,1 seen by A are now independent of the other FSS keys K fss 0,j , from the security of the FSS scheme we have that this sequence of hybrids is computationally indistinguishable from the previous one.

In the final experiment, we replace each of the values y i,1-c i with a uniformly random string. Note that this is identical to the ideal experiment, Exp sec A,σ,1 (λ). In the previous experiment, we had y i,1-c i = H((x (i) , s are independently uniform, and s is independent of t i and all other values given to A, these are computationally indistinguishable from the random values in Exp sec A,σ,1 (λ), by a reduction to the correlation robustness of H.

) (i) ⊕ q i ⊕ (1 -c i )s) = H((x ) (i) ⊕ t i ⊕ s). Since (x )
Corrupt sender (σ = 0). In the real experiment, the adversary A is given k 0 = (s, K fss 0,1 , . . . , K fss 0,λ ) and random input/output pairs (x (i) , (c i , z i )), where c i , z i are the OT receiver's choice bit and string computed from key k 1 , for i = 1, . . . , N .

We first define an experiment where z i is replaced with the y i,c i value obtained by running Eval on key k 0 . This is statistically close to the first experiment, by the FSS correctness property.

Similarly to the case of a corrupt receiver, we then replace the FSS keys K fss 0,j , for j = 1, . . . , λ, with simulated keys from the FSS simulator, then recompute (y i,0 , y i,1 ) using the new keys and let z i = y i,c i . This is indistinguishable from the first experiment, by the security of the FSS scheme and a hybrid argument.

Finally, we replace c 1 , . . . , c N with uniformly random bits, and again define z i = y i,c i . This is computationally indistinguishable to the previous experiment, due to the security of the weak-PRF F K , since the key K is uniform and independent of all inputs to A, and the inputs x (i) are uniform. This concludes the proof of the security property.

Pseudorandom correlated outputs. Here, we show that the joint distribution of the PCF outputs (y i,0 , y i,1 ), (c i , z i ) is indistinguishable from a set of independent samples from the OT correlation. First, again by correctness of FSS, we can replace z i with the value y i,c i that comes from the sender's key k 0 . Then, we can replace the FSS outputs q i , which are used to compute y i,0 and y i,1 , with uniform strings, because of the weak pseudorandomness property of FSS. Then, as previously, we can replace the FSS keys K fss 0,j with simulated keys, and use these to compute q i and the outputs (y i,0 , y i,1 ), because of the security property of FSS. Now, since q i are all independent of s, we use the correlation robustness property of H to replace y i,0 , y i,1 with uniformly random strings. Finally, the choice bits c 1 , . . . , c N are now computationally indistinguishable from uniform by the security of the weak-PRF, which completes the proof.

Remark 5.6 The PCF for OT can be optimized if we are instead given FSS for scalar multiples of the WPRF over F 2 λ , namely, the class of functions F K,s (x) = s • F K (x), for all s ∈ F 2 λ . Then, we only need a single pair of FSS keys for this function family, instead of λ sets of keys. This optimization is used in our concrete instantiation of the PCF for OT, in Section 6.4.

PCF for Multiplication Triples

A multiplication triple correlation over some ring R is sampled as a pair (a 0 , b 0 , c 0 ), (a 1 , b 1 , c 1 ), where a 0 , b 0 , a 1 , b 1 are independent and uniform over R, while c 0 , c 1 are uniformly random such that c 0 + c 1 = (a 0 + a 1 )(b 0 + b 1 ).

We can obtain a PCF for multiplication triples, given both FSS for a WPRF family F and its square, namely the function family F 2 = {f 1 f 2 : f 1 , f 2 ∈ F}. The construction simply samples two keys k 1 , k 2 ← {0, 1} λ , and gives out FSS keys for the functions F k 1 , F k 2 and F k 1 F k 2 . To evaluate the PCF, the three FSS keys are evaluated in turn to produce additive secret shares of a, b and c = ab respectively. Similarly to the VOLE correlation in Section 5.1, security of this construction can be proven based on the security of the WPRF, and the weak pseudorandom outputs property of the FSS scheme.

We remark that in this case, our specific WPRF candidate allows going much further than the general construction for multiplication triples. In the coming section, we present a PCF for arbitrary degree-2 correlations based on our WPRF, which comes at the same cost as FSS for the square of the WPRF family.

A Candidate FSS-Friendly WPRF

In this section, we describe candidate weak pseudorandom functions to instantiate the framework developed in Section 5. As outlined in the introduction, our candidates rely on variable-density variants of the LPN assumption, which we introduce below.

Variable-Density Learning Parity with Noise

We first formally introduce the VDLPN assumption. Fix a security parameter λ. VDLPN has three parameters: a sparsity parameter w = w(λ), which corresponds to the number of nonzero coordinates in each secret error vector e i and each row of the public matrix H i ; a block parameter D = D(λ), which corresponds to the number of blocks H i , and a number of samples N = N (λ), which we set to 2 D . For the sake of concreteness, think of w, D as being linear in λ. Given parameters par = (w, D, N ), the assumption can come in three flavors:

• the standard VDLPN assumption (denoted simply VDLPN(par)), in which each s i and each row of H i , of length w • 2 i , is sampled independently from Ber w•2 i 1/2 i ;

• the exact VDLPN assumption (denoted xVDLPN(par)), in which each s i and each row of H i are sampled uniformly from the set of all length-w • 2 i vectors with exactly w nonzero entries;

• the regular VDLPN assumption (denoted rVDLPN(par)), in which each s i and each row of H i are sampled by contatenating w random length-2 i unit vectors (i.e., they are divided into w equal length block with a single random 1 in each block).

The above distinction is analogous to the standard variants of the LPN assumption, which also comes with an exact variant (see e.g. [START_REF] Pietrzak | Cryptography from learning parity with noise[END_REF]) and a regular variant (see e.g. [START_REF] Augot | A fast provably secure cryptographic hash function[END_REF]). These are widely believed to be no less secure than the standard LPN assumption (this can actually be formally proven for the search variant of exact LPN [START_REF] Pietrzak | Cryptography from learning parity with noise[END_REF]). The main difference is that in our setting, the exact and regular variant refer not only to the structure of the noise vector, but also to the structure of the code parity-check matrix, since we always assume that the rows of H follow the same distribution as the noise vector. In the following, we will focus mainly on the regular VDLPN assumption by default. This is motivated by the fact that it leads to a simpler and more efficient WPRF candidate than its standard and exact counterparts.

Distributions. Fix parameters par = (w, D, N = 2 D ). Let R w,i be the distribution of random w-regular vectors over F w•2 i 2 (that is, a sample from R w,i is obtained by concatenating w independent samples from S 1,2 i ). We let H i par denote the distribution over N × (w • 2 i ) matrices over F 2 where each row is sampled independently from R w,i , and H par denote the distribution over

F N ×2N
$ ← H par , e $ ← N par , b ← H • e} ≈ {(H, b) | H $ ← H par , b $ ← F N 2 }.
For any H in the support of H par , we denote by O par (H) the output distribution, i.e., the distribution over F N 2 induced by sampling e $ ← N par and outputting H • e.

A Candidate WPRF in Depth-2 AC 0 [⊕] from rVDLPN

The above rVDLPN assumption immediately implies a weak PRF candidate. Fix parameters par(λ) = (w(λ), D(λ), N (λ) = 2 D(λ) ). To simplify the description of the WPRF family, it is helpful to make explicit the exact number of random bits used to sample from the distribution N par . Recall that a sample from N par is a (vertical) concatenation of D vectors e i , where each vector e i is a (transposed) sample from R w,i . In turn, a sample from R w,i is a concatenation of w random unit vectors over F 2 i 2 , where each can be sampled using i random bits (indicating the position, between 1 and 2 i , of the nonzero entry of the vector). Therefore, sampling from N par requires exactly w • D i=1 i = w • D(D -1)/2 random bits. Given r ∈ {0, 1} w•D(D-1)/2 , we write N par (r) to denote the value sampled from N par using the bistring r as the source of random bits. The construction of the weak PRF family is described below.

• Key size:

K ∈ {0, 1} κ(λ) with κ(λ) = n(λ) = w(λ) • D(λ)(D(λ) -1)/2. • Input size: x ∈ {0, 1} n(λ) with n(λ) = w(λ) • D(λ)(D(λ) -1)/2.
• F K (x) : on input x ∈ {0, 1} n , sample h ← N par (x) and output h, N par (K) . Theorem 6.2 Assume that rVDLPN(par) holds. Then the above construction is an N -query weak pseudorandom function family, with input length and key length n = κ = w • D(D -1)/2. Furthermore, for any fixed choice of key K, the function F K can be implemented with a depth-2 AC 0 [⊕] circuit with a layer of AND gates at the bottom, and a single XOR gate at the top.

Proof. By construction, K is distributed as the noise vector in rVDLPN, and the distribution of h is exactly the same as the distribution each rows of H is sampled from in H par . Hence, distinguishing

(F K ( h 1 ), • • • , F K ( h N )) given random ( h 1 , • • • , h N )
and for a random key K is perfectly equivalent to distinguishing H • e from random given H, where H (whose rows are the h i ) is sampled from H par and K = e is sampled from N par . It remains to show that F K can be implemented with a depth-2 AC 0 [⊕] circuit with a layer of AND gate at the bottom, and a single XOR gate at the top. By construction we have

F K (x) = N par (x), N par (K) .
Let us decompose x as (x i,j ) i≤D,j≤w and K as (K i,j ) i≤D,j≤w , with |x i,j | = |K i,j | = i. The string x i,j (resp. K i,j ) correspond to the portion of x (resp. of K) which is used to sample the j'th unit vector from R w,i when computing N par (x) (resp. N par (K)). That is,

N par (x) = R w,1 ((x 1,j ) j≤w ) // • • • //R w,D ((x D,j ) j≤w ) = (S 1,2 (x 1,1 )|| • • • ||S 1,2 (x 1,w )) // • • • //(S 1,2 D (x D,1 )|| • • • ||S 1,2 D (x D,w )) , N par (K) = R w,1 ((K 1,j ) j≤w ) // • • • //R w,D ((K D,j ) j≤w ) = (S 1,2 (K 1,1 )|| • • • ||S 1,2 (K 1,w )) // • • • //(S 1,2 D (K D,1 )|| • • • ||S 1,2 D (K D,w )) .
Therefore,

F K (x) = N par (x), N par (K) = D i=1 w j=1 S 1,2 i (x i,j ), S 1,2 i (K i,j ) .
Now, by definition of S 1,2 i , the inner product S 1,2 i (x i,j ), S 1,2 i (K i,j ) is equal to 1 if and only if x i,j = K i,j , if and only iff x i,j,k ⊕ K i,j,k = 0 for k = 1 to i. Hence:

F K (x) = D i=1 w j=1 i k=1 (x i,j,k ⊕ K i,j,k ⊕ 1).
Therefore, for any fixed choice of key K, the function F K computes a fan-in-D • w XOR of fan-in-i ANDs of terms, where each term is either an input bit or its complement.

Note that the above characterization gives an alternative description of our candidate WPRF as a function computed by a simple boolean circuit. Omitting the "⊕1" terms in the formula above does not change the function family (since it simply amounts to flipping all the bits of the PRF key, which does not change its distribution), hence an equivalent formulation of our weak PRF candidate is given by

F K (x) = F (K ⊕ x)
where the function F is defined as

F (x) = D i=1 w j=1 i k=1
x i,j,k .

We conjecture that this candidate, which is based on the rVDLPN assumption, achieves exponential security. More precisely, we put forth the following conjecture: Conjecture 6.3 (Subexponential Security) There exists constants (C 1 , C 2 ) such that for every large enough security parameter λ, every distinguisher that runs in time

T (λ) has advantage at most O(T /2 λ ) against the rVDLPN(C 1 • λ, C 2 • λ, 2 C 2 •λ ) assumption.
In Section 7, we will provide support to this conjecture, by analyzing the security of the rVDLPN assumption against a wide variety of distinguishers (including linear and low-degree polynomial distinguisher, algebraic distinguishers, statistical query algorithms, AC 0 circuits, and linear cryptanalysis attacks).

Generalization to Arbitrary Rings

Our WPRF candidate can be naturally generalized to work over an arbitrary ring R, by using the same sparse distributions where the ones are replaced by random nonzero ring elements: given parameters par = (w, D, N = 2 D ), we let R w,i (R) be the distribution of random w-regular vectors over R w•2 i , H i par (R) denote the distribution over n × (w • 2 i ) matrices over R where each row is sampled independently from R w,i (R), and H par (R) denote the distribution over R N ×2N obtained by sampling

H i $ ← H i par (R) for i = 1 to D and outputting H = H 1 || • • • ||H D .
{(H, b) | H $ ← H par (R), e $ ← N par (R), b ← H • e} ≈ {(H, b) | H $ ← H par (R), b $ ← R N }.
This assumption leads to a candidate WPRF over R via the same construction. The candidate can be written as follows: it receives as input a w • D(D -1)/2-bit string x together with w • D ring elements y, and a PRF key has the same form (a w • D(D -1)/2-bit string K together with w • D ring elements L). An element of {0, 1} is interpreted naturally as an element of R in the formula below (0 is the neutral for addition and 1 the neutral for multiplication). The generalized candidate is defined as

F K,L ( x, y) = D i=1 w j=1 (y i,j • L i,j ) • i k=1 (x i,j,k ⊕ K i,j,k ).
Part of our security analysis, most notably the proof of resistance against linear attacks and their natural generalizations, extend to this arithmetic generalization of our candidate if we choose w sufficiently large (in particular, w > D + log |R|). Plugging this generalized WPRF into the VOLE construction of Figure 8 leads to a PCF for VOLE over an arbitrary ring R (see Section 6.4 for more details). We conjecture that this generalization is secure for an arbitrary choice of the ring R, with parameters that only depend on log |R|.

FSS-Friendliness of our WPRF

Recall that as established in Section 5, we have to show that our weak PRF is FSS-friendly, meaning that there exists a light-weight FSS scheme allowing to share the PRF keys between the parties. In the following we will show that our PRF can indeed be viewed as a sum of point functions, which build a function class that is very FSS-friendly, even admitting constructions that only make black-box use of a pseudorandom generator, as elaborated in the following.

Point functions. Let G be an additive group, α ∈ {0, 1} n(λ) and β ∈ G. Let f α,β be the point function where f α,β (x) is zero whenever x = α, and

f α,β (x) = β if x = α. If G = ({0, 1}, ⊕), we simply write f α to denote f α,1 .
Distributed point functions. An FSS scheme for the class of point functions

{f α,β : {0, 1} n(λ) → G | α, β ∈ {0, 1} n(λ) }
is called a distributed point function (DPF) [START_REF] Gilboa | Distributed point functions and their applications[END_REF]. In the following, we will consider distributed point functions with variable input space. More precisely, such a DPF consists of a tuple of algorithms (DPF.Gen, DPF.Eval), where DPF.Gen additionally takes a parameter n = n(λ) specifying the input length. Given a PRG G : {0, 1} λ → {0, 1} 2λ+2 , we can construct a distributed point function with the following complexities [START_REF] Boyle | Function secret sharing: Improvements and extensions[END_REF]: Let m(λ) = log|G| λ+2 , then • the size of each party's key is at most n(λ) • (λ + 2) + λ + log |G| bits,

• the key generation algorithm Gen invokes G at most 2(n(λ) + m(λ)) times,

• the evaluation algorithm Eval invokes G at most n(λ) + m(λ) times.

Note that the DPF of [START_REF] Boyle | Function secret sharing: Improvements and extensions[END_REF] has pseudorandom outputs; in fact, this holds generally for every DPF [START_REF] Boyle | Function secret sharing[END_REF].

FSS-friendliness of our construction. Recall that our construction is of the form

F K,L (x, y) = D i=1 w j=1 (y i,j • L i,j ) • i k=1 (x i,j,k ⊕ K i,j,k )
over general ring R. For the following for all i ∈ [w], j ∈ [D] let x i,j = x i,j,1 . . . x i,j,i ∈ {0, 1} i (and for K i,j accordingly). Then, for all i ∈ [w], j ∈ [D] we have i k=1 (x i,j,k ⊕ K i,j,k ) = 1 for the single point x i,j ∈ {0, 1} i , for which x i,j = K i,j . We can thus rewrite our candidate as

F K,L (x) = D i=1 w j=1 y i,j • f K i,j ,L i,j (x i,j ),

PCF for VOLE from regular VDLPN

Let DPF = (DPF.Gen, DPF.Eval) be an FSS scheme for point functions with variable input length. Recall that f K,L : {0, 1} i → R is the point function with f K,L (x) = L if and only if x = K. PCF.Gen(1 λ ): On input 1 λ : 1. Sample a ← R.

2. For all j ∈ [w] and i ∈ [D]:

• Sample a key K i,j ← {0, 1} i . • Sample payloads L i,j ← R. • Sample a pair of FSS keys (K fss 0,i,j , K fss 1,i,j ) ← DPF.Gen(1 λ , i, a • f K i,j ,L i,j ). 3. Set K := {K i,j } j∈[w],i∈[D] . 4. Output the keys k 0 = ({K fss 0,i,j } j∈[w],i∈[D] , a) and k 1 = ({K fss 1,i,j } j∈[w],i∈[D] , K). PCF.Eval(σ, k σ , (x, y)): On input a random x ∈ {0, 1} w•D(D+1)/2 , y ∈ R w•B : Parse x as x i,j ∈ {0, 1} i , for j ∈ [w], i ∈ [D],
and y as y i,j ∈ F, for j

∈ [w], i ∈ [D].
• If σ = 0:

1. For all j ∈ [w] and i ∈ [D]: Let c 0,i,j ← DPF.Eval(0, K fss 0,i,j , x i,j ).

Compute c

0 = D i=1 w j=1 y i,j • c 0,i,j . 3. Output (a, c 0 ). • If σ = 1:
1. For all j ∈ [w] and i ∈ [D]: Let c 1,i,j ← DPF.Eval(1, K fss 1,i,j , x i,j ). where f K i,j ,L i,j is the point function with f K i,j ,L i,j (x i,j ) = L i,j if and only if K i,j = x i,j . Now, we can share F K,L (x) as the sum of w • D distributed point functions, where f K i,j ,L i,j has input space {0, 1} i . Let κ = w • D(D + 1)/2. Note that any scalar multiple of a point function is a point function again, and thus DPFs are, in particular, an FSS for {a • F K,L } a∈R,K∈{0,1} κ ,L∈R and {F K,L } K∈{0,1} κ ,L∈R ∪{0}. Therefore, by the results of Section 5, they are sufficient to obtain a PCF for VOLE, OT and as we show now, even a universal PCF for general constant-degree correlations.

Compute c

1 = D i=1 w j=1 y i,j • c 1,i,j . 3. Let b = F K (x).
In the following, by negl(λ) we always refer to a negligible function, that is a function that decreases faster than any inverse polynomial: negl(λ) ≤ 1/p(λ) for all polynomials p and all large enough λ ∈ N. Theorem 6.5 (PCF for VOLE from rVDLPN) If DPF = (DPF.Gen, DPF.Eval) is instantiated with the distributed point function from [START_REF] Gilboa | Distributed point functions and their applications[END_REF], then, assuming rVDLPN(w, D, 2 D ) over ring R, PCF = (PCF.Gen, PCF.Eval) as defined in Figure 8 is a (2 D , negl(λ))-secure PCF for VOLE over R with the following complexities: • Each party's key is of size

• If σ = 1: 1. Let c = F K (x). 2. For all j ∈ [w], i ∈ [D]: Let t i,j ← DPF.Eval(1, K fss 1,i,j , x i,j ). 3. Compute t = D i=1 w j=1 t i,j . 4. Compute z = H(x ⊕ t).

Output (c, z).

O(w • D 2 • λ + w • D • log |R|) bits,
• the cost of PCF.Gen and PCF.Eval is dominated by each O(w

• D 2 + w • D • log |R|/λ)
invocations of a pseudorandom generator.

Note that in the following, unlike the generic construction for OT from Section 5, we use the optimization mentioned in Remark 5.6, where the DPFs have output in {0, 1} λ (but the construction is still based on the regular VDLPN assumption over F 2 ). For w(λ) ∈ O(λ) this gives us the following: Theorem 6.6 (PCF for OT from rVDLPN) If DPF = (DPF.Gen, DPF.Eval) is instantiated with the distributed point function from [START_REF] Gilboa | Distributed point functions and their applications[END_REF] and H is a correlation-robust hash function, then, assuming that rVDLPN(O(λ), D, 2 D ) holds, PCF = (PCF.Gen, PCF.Eval) as defined in Figure 9 is a (2 D , negl(λ))-secure PCF for OT with the following complexities:

• Each party's key is of size O(λ 2 • D 2 ) bits,
• the cost of PCF.Gen and PCF.Eval is dominated by each O(λ • D 2 ) invocations of a pseudorandom generator.

For our final construction, a PCF for general degree-2 correlations, first note that we have:

F K (x) • F K (y) = D i,i =1 w j,j =1 f K i,j (x i,j ) ∧ f K i ,j (y i ,j ),
where f K i,j (x i,j ) ∧ f K i ,j (y i ,j ) if and only if K i,j = x i,j and K i ,j = y i ,j . We can thus rewrite the above as

F K (x) • F K (y) = D i,i =1 w j,j =1 f K i,j ⊗K i ,j (x i,j ⊗ y i ,j ).
Based on this observations, in Figure 10 we give a PCF for an arbitrary degree-2 correlation. More precisely, after a one-time setup, this universal PCF allows the parties to compute an arbitrary number degree-2 correlations of the form ((X 0 , Y 0 ), (X 1 , Y 1 )), where X = X 0 ⊕ X 1 ∈ {0, 1} m and Y 0 + Y 1 = p(X) for an arbitrary m-variate polynomial p. Note that the same one-time setup can be used to evaluate many different polynomials. This construction can be generalized to arbitrary degree-d correlation for arbitrary constant d, yielding the following: Theorem 6.7 (Universal PCF for degree-d correlations from rVDLPN) If DPF is instantiated with the distributed point function from [START_REF] Gilboa | Distributed point functions and their applications[END_REF] and assuming rVDLPN(w, D, 2 D ) holds, then PCF = (PCF.Gen, PCF.Eval) as given in Fig. 10 is a universal (2 D , negl(λ))-secure PCF for degree-d correlations over F 2 with the following complexities:

• Each party's key is of size O(λ d+1 • D 2d ) bits,
• the cost of PCF.Gen is dominated by O(λ d • D 2d ) invocations of a pseudorandom generator,

• the cost of eval PCF.Eval of evaluating a degree-d polynomial m-variate polynomial consisting of at most k terms is dominated by

O((m + k) • λ d • D 2d
) invocations of a pseudorandom generator.

Application: XOR-RKA Secure PRGs and Weak PRFs

Our WPRF candidates give rise to simple PRG and WPRF constructions that are naturally secure against related key attacks for XOR relations. Related key attacks [START_REF] Bellare | A theoretical treatment of related-key attacks: RKA-PRPs, RKA-PRFs, and applications[END_REF] are a powerful class of attack, where the adversary is given access to outputs of the cryptographic primitive under several keys which are related, according to some relation known to the adversary. In the model of XOR-RKA security, the adversary is given samples under a key K, as well as under several related keys K ⊕ ∆ (1) , K ⊕ ∆ (2) , . . . , where ∆ (i) are public offsets. This naturally models bit flips that may occur in hardware due to, for instance, fault attacks.

Correlation robust hash function. Recall the notion of a correlation robust hash function (Definition 5.4), a function H such that the distribution of H(K ⊕ ∆ (1) ), . . . , H(K ⊕ ∆ (N ) ), where ∆ (i) are random strings, is computationally indistinguishable from the uniform distribution, even when given the ∆ (i) 's. Note that this can also be seen as a form of XOR-RKA secure pseudorandom generator [START_REF] Applebaum | Semantic security under related-key attacks and applications[END_REF].

As seen in Section 6.2, our WPRF candidate can be written as

F K (x) = F (K ⊕ x)
for some public function F . Assuming that F K is a secure WPRF for N samples, we immediately get that F is a correlation robust function. As shown in [START_REF] Applebaum | Semantic security under related-key attacks and applications[END_REF], this also implies the existence of

Universal PCF for degree-2 polynomials

Let DPF = (DPF.Gen, DPF.Eval) be an FSS scheme for point functions with variable input length. Recall that f K : {0, 1} i → {0, 1} is the point function with f K (x) = 1 if and only if x = K. Note that the following gives a PCF for an arbitary m-variate degree-2 polynomial p(X 1 , . . . , X m ) = c⊕ m α=1 α X α ⊕ m α,β=1 q α,β X α X β (which does not have to be fixed at the time of key generation).

PCF.Gen(1 λ ): On input 1 λ :

1. For all j ∈ [w] and i ∈ [D]:

• Sample a key K i,j ← {0, 1} i .
• Sample a pair of FSS keys (K fss 0,i,j , K fss 1,i,j ) ← DPF.Gen(1 λ , i, f K i,j ). 2. For all j, j ∈ [w] and i, i ∈ [D]:

• Sample a pair of FSS keys (K fss 0,i,j,i ,j , K fss 1,i,j,i ,j ) ← DPF.Gen(1 λ , i • j, f K i,j ⊗K i ,j ).

Set K

1 σ := {K fss σ,i,j } j∈[w],i∈[D] and K 2 σ := {K fss σ,i,j,i ,j } j,j ∈[w],i,i ∈[D] . 4. Output the keys k 0 = (K 1 0 , K 2 0 ) and k 1 = (K 1 1 , K 2 1 ). PCF.Eval(σ, k σ , p, x 1 , . . . , x m ): On input a random x 1 , . . . , x m ∈ {0, 1} w•D(D+1)/2 : Parse x α as x α,i,j ∈ {0, 1} i , for j ∈ [w], i ∈ [D] and each α ∈ [m].
• If σ = 0:

1. For all α ∈ [m]:

-For all j ∈ [w] and i ∈ [D]: Let X α,0,i,j ← DPF.Eval(0, K fss 0,i,j , x α,i,j ). -Compute X α,0 = D i=1 w j=1 X α,0,i,j . 2. For all α, β ∈ [m] with q α,β = 0:

-For all j, j ∈ [w] and i, i ∈ [D]: Let X α,β,0,i,j,i ,j ← DPF.Eval(0, K fss 0,i,j,i ,j , x α,i,j ⊗ x β,i ,j )

-Compute X α,β,0 = D i,i =1 w j,j =1 X α,β,0,i,j,i ,j . 3. Compute Y 0 = m α=1 α X α,0 ⊕ m α,β=1 q α,β X α,β,0 . 4. Output ({X α,0 } α∈[m] , Y 0 ). • If σ = 1: 1. For all α ∈ [m]:
-For all j ∈ [w] and i ∈

[D]: Let X α,1,i,j ← DPF.Eval(1, K fss 1,i,j , x α,i,j ). -Compute X α,1 = D i=1 w j=1 X α,1,i,j . 2. For all α, β ∈ [m] with q α,β = 0:
-For all j, j ∈ [w] and i, i Exp rka-wprf A (λ) :

∈ [D]: Let X α,β,1,i,j,i ,j ← DPF.Eval(1, K fss 1,i,j,i ,j , x α,i,j ⊗ x β,i ,j ) -Compute X α,β,1 = D i,i =1 w j,j =1 X α,β,1,i,j,i ,j . 3. Compute Y 1 = m α=1 α X α,1 ⊕ m α,β=1 q α,β X α,β,1 . 4. Output ({X α,1 } α∈[m] , Y 1 ).
K $ ← {0, 1} λ b $ ← {0, 1} b ← A O rka K,b (•) (1 λ ) if b = b return 1 else return 0 O rka K,b (∆) : x $ ← {0, 1} n(λ) if b = 0 y $ ← {0, 1} λ else y ← F K⊕∆ (x) return (x, y)
Figure 11: XOR-RKA security experiment for a weak PRF RKA-secure one-time symmetric encryption and RKA-secure deterministic encryption schemes with optimal ciphertext sizes, for XOR relations. Previously, such constructions were only known to exist for less natural, additive relations over Z p under a power-DDH assumption [START_REF] Applebaum | Semantic security under related-key attacks and applications[END_REF] or the learning with rounding assumption [START_REF] Applebaum | Related-key secure pseudorandom functions: The case of additive attacks[END_REF], or for XOR relations based on multilinear maps [START_REF] Abdalla | Algebraic XOR-RKA-secure pseudorandom functions from post-zeroizing multilinear maps[END_REF].

RKA-Secure WPRF. As well as giving an RKA-secure PRG, our construction is in fact an XOR-RKA secure WPRF. We consider the definition of RKA-secure WPRF by Bellare et al. [START_REF] Bellare | Cryptography secure against related-key attacks and tampering[END_REF] given below, adapted to the XOR relation. This allows the adversary to choose an arbitrary ∆ for each query, which is added to the fixed key K in the real experiment where the adversary learns PRF evaluations. Definition 6.8 Let {F K : {0, 1} n → {0, 1} λ } K∈{0,1} λ be a family of efficiently computable functions. We say that F is an N -XOR-RKA-secure weak PRF if for every p.p.t. adversary A making at most N (λ) queries to the oracle O rka K,b (•), it holds that

Pr[Exp rka-wprf A (λ) = 1] - 1 2 ≤ negl(λ)
where Exp rka-wprf A (λ) is as defined in Figure 11.

Note that since each query samples a fresh random x, allowing the adversary to choose an arbitrary ∆ induces exactly the same output distribution as with no offset. Therefore, we immediately obtain the following. Theorem 6.9 Suppose the rVDLPN(w, D, N ) assumption holds for some w(λ), D(λ), N (λ). Then, there is an XOR-RKA-secure weak PRF for N (λ) queries.

Security Analysis

In this section, we provide a thorough analysis of our candidate weak PRF family against various classes of attacks.

Resistance Against Linear Tests -Theorem and Corollaries

Our first and main result shows that our candidate weak PRF fools all linear tests. Recall the notations of bias from Definition 3.1 and H par , O par from Section 6.1. More precisely, we prove: Theorem 7.1 (Low-Bias) There exist constants (β, µ, ν) such that for any large enough w,

any D ≤ β • w, n ← 2 D , par ← (w, D, N ), it holds that Pr H $ ←Hpar [bias(O par (H)) > µ w ] ≤ ν w .
In the language of weak PRFs, the above theorem states that, with overwhelming probability (at least 1 -ν w ) over the choice of at most N = 2 D random inputs (x (1) , • • • , x (N ) ), any distinguisher that computes a linear function of the entire output string y = (F K (x (1) ), • • • , F K (x (N ) )) has advantage at most µ w . Note that the choice of the linear function can depend arbitrarily on (x (1) , • • • , x (N ) ). We formalize this by putting forth the notion of (ε, δ, N )-biased weak PRF family: Definition 7.2 ((ε, δ, N )-biased weak PRF family) A function family

{F K : F n(λ) 2 → F 2 } K∈F κ(λ) 2 is (ε, δ, N )-biased if for every large enough λ ∈ N, it holds that Pr x (1) ,••• ,x (N (λ)) $ ←F n(λ) 2 [bias(D λ,N ( x)) > ε(λ)] < δ(λ),
where D λ,N ( x)) denotes the distribution which samples

K $ ← F κ(λ) 2 and outputs y = (F K (x (1) ), • • • , F K (x (N ) )).
The task of building low-complexity primitives which provably fool all linear tests is a very active area of research, especially in the context of building low-complexity pseudorandom generators with superlinear stretch [START_REF] Mossel | On e-biased generators in NC0[END_REF][START_REF] Shpilka | Constructions of low-degree and error-correcting ε-biased generators[END_REF]. Pseudorandom generators that fool all linear tests are called ε-biased pseudorandom generators, and their complexity is well understood: they exist in a complexity class as low as NC 0 5 , the class of constant-depth fan-in-2 boolean circuits where each output depends on at most 5 input bits, and cannot exist in NC 0 4 [START_REF] Mossel | On e-biased generators in NC0[END_REF]. Regarding the complexity of building low-bias strong PRFs, we are only aware of two results [START_REF] Gutfreund | Fooling parity tests with parity gates[END_REF][START_REF] Healy | Randomness-efficient sampling within nc[END_REF] which show that negligible-bias strong PRFs exist in AC 0 [⊕]. The construction is obtained by relatively involved constructions in AC 0 [⊕] of the various components required in the εbiased sample space construction of Naor and Naor [START_REF] Naor | Small-bias probability spaces: Efficient constructions and applications[END_REF]; although it achieves exponentially small bias, it cannot be a candidate exponentially strong PRF, since no such PRF can exist in AC 0 [⊕] [START_REF] Razborov | Natural proofs[END_REF][START_REF] Carmosino | Learning algorithms from natural proofs[END_REF]. We obtain an incomparable result of independent interest, by showing that a weaker object (an unconditional weak PRF with exponentially small bias) exists in a much smaller complexity class, the class XOR • AND, a subclass of depth-2 AC 0 [⊕].

Corollary 7.3 There exist constants (β, µ, ν) such that for any large enough w(λ), any D(λ) ≤ β • w, there exists a (µ w , ν w , 2 D )-biased weak PRF family in the class XOR • AND of polynomialsize depth-2 circuits with a layer of AND gates at the bottom, and a single XOR gate at the top.

Resistance Against Standard Attacks. Our candidate weak PRF relies on a variant of the LPN assumption. A large number of attacks against the LPN assumption have been introduced. The main categories of attacks include Gaussian elimination attacks and its variants [START_REF] Esser | LPN decoded[END_REF], statistical decoding attacks [AJ01, Ove06, FKI06, DAT17, Zic17], information set decoding attacks [Pra62, Ste88, FS09, BLP11, MMT11, BJMM12, MO15], and BKW and its variants [START_REF] Blum | Noise-tolerant learning, the parity problem, and the statistical query model[END_REF][START_REF] Lyubashevsky | The parity problem in the presence of noise, decoding random linear codes, and the subset sum problem[END_REF]. Yet another attack against PRF candidates based on LPN-style assumption can be mounted whenever the candidate PRF family satisfies some correlation with a sufficiently low-degree polynomial [ABG + 14, BR17].

We will not provide the details of these many attacks in this section. Rather, we confine ourselves to observing that all the above attacks can be formulated as linear tests in our framework. Therefore, Theorem 7.1 implies that an adversary running in time poly(λ) and performing any of the above attacks can succeed at distinguishing our candidate's output from random with advantage at most poly(λ) • max(µ w(λ) , ν w(λ) ).

Note that this is not a contradiction to the BKW attack [BKW00, Lyu05] of complexity 2 O(N/ log N ) on Learning Parity with Noise, as the N in the BKW attack corresponds to the size of the secret, which in our case is always at least quadratic in the security parameter.

Resistance Against Polynomial Tests. Recall that our candidate weak PRF, with parameters par = (w, D, N ), is of the form

F K (x) = D i=1 w j=1 i k=1 (x i,j,k ⊕ K i,j,k ),
with input size and key size n = κ = w • D(D -1)/2. For any divisor d of w, this can be rewritten as

F K (x) = D i=1 d =1 w/d-1 j=0 i k=1 (x ( ) i,j,k ⊕ K ( ) i,j,k ) where x ( ) i,j,k ← x i,jd+ ,k , K ( ) i,j,k ← K i,jd+ ,k = d =1 F K ( ) (x ( ) )
where each K ( ) , x ( ) belongs to {0, 1} n/d = {0, 1} κ/d . That is, our candidate weak PRF with parameters (w, D, N ) can be rewritten as the XOR of d independent instances (on independent keys and inputs) with parameters (w/d, D, N ). By a result of Viola [START_REF] Viola | The sum of d small-bias generators fools polynomials of degree d[END_REF], the XOR of d low-bias weak PRFs over F 2 fools all degree-d multivariate polynomial tests over F 2 , hence we can show that our candidate further resists all low-degree polynomial tests. We formalize this observation below.

We say that a distribution D over {0, 1} N has degree-d polynomial bias at most ε, and write polybias d (D) ≤ ε, if for every degree-d multivariate polynomial P :

F N 2 → F 2 , it holds that E D (-1) P (D) -E U N (-1) P (U N ) ≤ ε,
where U N is the uniform distribution over {0, 1} N . Combining our above observation with the result of Viola, we get the following corollary:

Corollary 7.4 (Resistance to Polynomial Tests) For any c > 1, there exist constants (β, µ, ν) (the same as in Theorem 7.1) such that for any large enough w, any divisor d of w, any

D ≤ β • w/d, it holds that Pr H $ ←Hpar polybias d (O par (H)) > 16 • µ w/2 d-1 ≤ d • ν w/d .
We further note that this result can be directly plugged into the result of [START_REF] Bogdanov | Pseudorandomness for width-2 branching programs[END_REF]: pseudorandomness against degree-d polynomials implies pseudorandomness against branching programs of width-2 and polynomial length that read d bits of input at a time. Hence, our weak PRF candidate also fools all tests from this class (with probability 16•t•µ w/2 d-1 for width-2 branching programs of length t reading d inputs at a time); this captures any degree-d polynomial, but also space-bounded computation with one bit of memory, or d-DNF formula.

Proof of Resistance Against Linear Tests

In this section, we prove Theorem 7.1. We first set up a few notations: for any i ≤ D, it follows from the definition of H i par (Section 6.1) that a matrix H i sampled from H i par can be written as

H i = H i,1 || • • • ||H i,w , with H i,j ∈ F N ×2 i 2
, where each row of each matrix H i,j for j ≤ w is sampled independently from S 1,2 i (resulting in rows of regular weight w). We let M i par denote the distribution of each H i,j (hence, a sample H i from H i par is a concatenation of w independent samples from M i par ).

Definition 7.5 Given a matrix M ∈ F N ×2 i 2 , we say that M is bad with respect to a vector

v ∈ F N 2 if HW ( v • M ) / ∈ 2 i 5 , 2 i+2 5 . Furthermore, given w matrices (M 1 , • • • , M w ) in F N ×2 i 2 , we let N v (M 1 , • • • , M w ) denote the number of matrices which are bad against v among M 1 • • • M w .
Equipped with the above definition, we can state the lemma which is at the core of the proof of Theorem 7.1: Lemma 7.6 There is a constant C such that for any 1 ≤ i ≤ D, and for any vector

v ∈ F N 2 such that HW( v) ∈ [2 i-1 , 2 i ], it holds that Pr M 1 ,••• ,Mw $ ←M i par N v (M 1 , • • • , M w ) ≥ w 2 ≤ 2 -C•2 i •w .
Proof. The proof of Lemma 7.6 relies on the bounded difference inequality (Lemma 3.5). Fix a vector v of weight

HW( v) = ∈ [2 i-1 , 2 i ].
It will be helpful to reformulate the event "a sample M from M i par is bad" as a balls and bins problem. Consider a sample M from M i par . Recall that by definition of M i par , the rows of M are sampled independently from S 1,2 i . We can cast the problem as a balls and bins problem as follows: we start with 2 i empty bins, correspondings to the columns of M . Sampling a row of M from S 1,2 i can be viewed as throwing a ball in one of the 2 i bins, picked uniformly at random. Then, for any fixed v of weight , the event

HW ( v • M ) / ∈ I i ← 2 i 5 , 2 i+2 5
is equivalent to the following event: after throwing exactly balls at random in 2 i bins, the numbers T of bins containing an odd number of balls satisfies T / ∈ I i . The full experiment can therefore be reformulated as follows: there are 2 i bins, and • w balls are thrown randomly (and sequentially) in these bins, divided into w consecutive phases ( balls are thrown during each phase). Each time balls have been thrown, we check whether the fraction of bins containing an odd number of balls is between 1/5 and 4/5, and empty the bins. At the end of the experiment, we output "failure" if at least w/2 of the w checks failed.

We now bound the probability that the experiment fails. For j = 1 to and k = 1 to w, let X j,k be the random variable corresponding to the bin in which the k-th ball of the j-th phase landed (note that the X j,k are independent). In order to apply McDiarmid's bounded difference inequality, we need to consider a carefully chosen function of the X j,k :

Φ(X 1,1 , • • • , X ,w ) = w k=1   2 i-1 -HW   j=1 X j,k   -2 i-1   . Claim 7.7 Pr M 1 ,••• ,Mw $ ←M i par N v (M 1 , • • • , M w ) ≥ w 2 ≤ Pr Φ(X 1,1 , • • • , X ,w ) < w • 2 i 10 .
Proof. Fix a vector v of weight . Note that sampling a matrix M ← M i par and computing HW( v • M ) is identical to sampling random unit vectors X 1 • • • X and computing HW( j=1 X j ). Now, suppose that the event Φ(X 1,1 , • • • , X ,w ) < w • 2 i /10 happened. This means that there must exist a subset K ⊆ [w] such that

• For every k ∈ K, Y k ← 2 i-1 -HW j=1 X j,k -2 i-1 < 2 i
5 , and

• |K| ≥ w 2 .
Indeed, if this was not the case then at least w -w/2 = w/2 of the k ∈ [w] would satisfy

Y k ≥ 2 i /5, which would imply Φ(X 1,1 , • • • , X ,w ) ≥ (w/2) • (2 i /5), contradicting the hypothesis. The condition Y k < 2 i /5 rewrites to HW   j=1 X j,k   -2 i-1 > 3 • 2 i-1 5 ⇐⇒ HW   j=1 X j,k   / ∈ 2 i 5 , 2 i+2 5 .
Therefore, the event

Φ(X 1,1 , • • • , X ,w ) < w • 2 i /10 implies in particular that at least w/2 of the k ≤ w satisfy HW j=1 X j,k / ∈ 2 i /5, 2 i+2 /5 , which is identical to the event N v (M 1 , • • • , M w ) ≥ w/2 happening when sampling M 1 • • • M w from M i par .
This concludes the proof of the claim.

Claim 7.8 The function Φ is 2-Lipschitz.

Proof. Consider changing a single input X j,k to Φ. This corresponds to moving a single ball to a different bin during one of the phases. But doing so can only change the number of bins with an odd number of balls at the end of this phase by at most 2, hence the value HW( j=1 X j,k ) can change by at most 2. Propagating the change, this implies that the value of Φ(X 1,1 , • • • , X ,w ) changes by at most 2. Since Φ is 2-Lipschitz, we can apply the bounded difference inequality (Lemma 3.5): for any t, we have

Pr[Φ(X 1,1 , • • • , X ,w ) < E[Φ(X 1,1 , • • • , X ,w )] -t] ≤ exp - t 2 2 w . It remains to bound E[Φ(X 1,1 , • • • , X ,w )].
Claim 7.9

E [Φ (X 1,1 , • • • , X ,w )] ≥ w • 2 i 5 .
Proof. First, we prove that for any 1 ≤ k ≤ w (i.e., for each phase of balls thrown),

E   HW   j=1 X j,k     ∈ 2 i 5 , 2 i 2 . Let R 2 i , ← HW j=1 X j,k . We compute the expected value E[R 2 i , ] of R 2 i ,
, by induction over . Clearly, E[R 2 i ,0 ] = 0. Furthermore, by linearity of the expectation,

E[R 2 i , +1 ] = (E[R 2 i , ] -1) • E[R 2 i , ] 2 i + (E[R 2 i , ] + 1) • 1 - E[R 2 i , ] 2 i ,
since adding a ball in a bin which contains initially an odd number of balls reduces the number of bins with an odd number of balls by 1, while adding a ball in a bin with an even number of balls increases the number by 1. Solving the recursive formula gives

E[R 2 i , ] = 2 i 2 • 1 -1 - 2 2 i ∈ 2 i 5 , 2 i 2 for any ≥ 2 i-1 ,
where the inclusion uses the following standard inequality:

1 - 2 2 i ≤ exp - 2 2 i < 2 5 for any ≥ 2 i-1 .
From there, we get

E   HW   j=1 X j,k   -2 i-1   ≤ 3 10 • 2 i =⇒ E [Φ (X 1,1 , • • • , X ,w )] ≥ w • 2 i 5 .
Summing up, we obtain that for any t,

Pr Φ(X 1,1 , • • • , X ,w ) < w • 2 i 5 -t ≤ exp - t 2 2 w ≤ exp - t 2 2 i+1 w ,
where the second inequality uses the fact that ≤ 2 i . Plugging in t = w • 2 i /10, this gives

Pr Φ(X 1,1 , • • • , X ,w ) < w • 2 i 10 ≤ exp - w • 2 i 200 = 2 -C•w•2 i
for some appropriate constant C; this concludes the proof of Lemma 7.6. Equipped with Lemma 7.6, we complete the proof of Theorem 7.1. Observe that the number of vectors v ∈ F N 2 satisfying HW( v) ∈ [2 i-1 , 2 i ] can be bounded by

2 i =2 i-1 N ≤ 2 i =2 i-1 N ! ≤ (2 i -2 i-1 ) • N 2 i (2 i-1 )! ≤ 2 D•2 i .
Hence, setting β ← C/2, if w is such that D ≤ β • w, we obtain by a straightforward union bound over all vectors v of weight in

[2 i-1 , 2 i ], denoting S i,N the set of vectors v over F N 2 with HW( v) ∈ [2 i-1 , 2 i ], Pr M 1 ,••• ,Mw $ ←M i par ∃ v ∈ S i,N , N v (M 1 , • • • , M w ) ≥ w 2 ≤ 2 D•2 i • 2 -C•w•2 i ≤ 2 -α•w (4)
for some constant α = β = C/2. Note that our bounds are quite loose -in particular, the optimal choice of parameters depends on i, while we chose to settle for a worst-case choice of the same parameters for all i. Now, recall that the distribution H i par is exactly the distribution that samples

H i,1 , • • • , H i,w independently from M i par and output H i ← H i,1 || • • • ||H i,w .
We are now almost ready to conclude: recall that a sample from O par (H) with

H = H 1 || • • • ||H D is of the form H • e = D i=1 H i • e i = D i=1 w j=1 H i,j • e i,j
where each e i is a random sample from R w,i (transposed), hence each e i,j is a random sample from S 1,2 i . Now, for any vector

v ∈ F N 2 , v • (H • e) = D i=1 w j=1 ( v • H i,j ) • e i,j .
Returning v •H i,j • e i,j for a vector e i,j sampled from S 1,2 i is equivalent to sampling a uniformly random entry of the vector v • H i,j . Let D i,j be the distribution which returns H i,j • e i,j for a random e i,j $ ← S 1,2 i . Observe that the condition N v (H i,1 , • • • , H i,w ) < w/2 can be restated as follows: for at least half of the values j ∈ [1, w], it holds that

bias v (D i,j ) ≤ 1 2 - 1 5 = 3 10 .
Now, a sample of the form H i • e i for a random e i from R w,i is the XOR of independent random samples from each of the D i,j . Therefore, by Lemma 3.2, whenever N v (H i,1 , • • • , H i,w ) < w/2, the bias of D i with respect to v decrease exponentially with w:

bias v (D i ) ≤ 1 2 • 3 5 w/2
.

Plugging this into Equation 4gives

Pr H i $ ←H i par ∃ v ∈ S i,N , bias v (D i ) > 1 2 • 3 5 w/2 ≤ 2 -α•w . (5)
Therefore, by a union bound again,

Pr H $ ←Hpar ∃i ∈ [0, D -1], ∃ v ∈ S i,N , bias v (D i ) > 1 2 • 3 5 w/2 ≤ D • 2 -αw .
By the rightmost inequality of Lemma 3.2, for any vector v, the bias of O par with respect to v is at most the smallest bias of any of the D i with respect to v (since a sample from O par is the exclusive OR of independent samples from each of the D i ). Now, since the S i,N for i = 0 to D -1 cover all of F N 2 (as N = 2 D ), we get:

Pr H $ ←Hpar ∃ v ∈ F N 2 , bias v (O par (H)) > 1 2 • 3 5 w/2 ≤ D • 2 -αw ,
which concludes the proof.

Generalization to the Arithmetic Setting. The notion of low-bias weak PRF can be generalized from F 2 to arbitrary groups, in the same way that the notion of low-bias pseudorandom generator extends to arbitrary groups: an ε-biased space over a group G is a distribution D such that for any nontrivial character χ :

G → C, it holds that | E[χ(D)]| ≤ ε, see e.g. [LRTV09]
. For the special case of F N for a general field F, the characters coincide (are in one-to-one correspondance with) linear functions L : F N → F. Therefore, the natural generalization of the notion of ε-bias of a distribution D N over F N states that for every nonzero vector v, the distribution induced by sampling y $ ← D N and outputting v, y is ε-close to the uniform distribution over F.

Most of the proof of resistance against linear test is oblivious to the choice of the underlying field and extends naturally to the arithmetic generalization of our candidate, given in Section 6.3. We sketch here how to adapt the proof to the general case: as before, we will reduce the problem to a balls and bins problem, but where each ball now corresponds to a uniformly random nonzero field element. Notably, remember that we count the number of bins containing exactly an odd number of balls; in our proof, each bin corresponds to a column m j of a matrix M , and a bin contains an odd number of balls when v and m j have an odd number of nonzero coordinates at the same position -hence in particular, at least one nonzero coordinate at the same position.

Conditioned on this being the case, since the nonzero entries of m j are uniformly random nonzero elements of F, the scalar product v, m j is a uniformly random nonzero element of F. Then, the rest of the proof proceeds identically. Note that over a large field F, the bound on the number of vectors v grows as 2 (log |F|+D)•2 i , hence the condition to be satisfied is that D + log |F| ≤ β • w for some appropriate constant β. Eventually, concluding the proof requires a standard argument to show that a random size-O(w) subset-sum of public random field elements is close to the uniform distribution over F, when w is large enough.

Resistance Against Algebraic Attacks

While linear attacks capture many attacks from the literature, there is an important and widely studied class of attacks which does not fit into the linear test framework: algebraic attacks. Algebraic attacks have been introduced in [Pat95] and were later extended and abstracted in [START_REF] Courtois | The security of hidden field equations (hfe)[END_REF][START_REF] Courtois | Algebraic attacks on stream ciphers with linear feedback[END_REF][START_REF] Courtois | Fast algebraic attacks on stream ciphers with linear feedback[END_REF]. More recently, [START_REF] Applebaum | Algebraic attacks against random local functions and their countermeasures[END_REF] formalized the notion of algebraic attacks in the study of random local functions.

Algebraic attacks start with input/ output pairs (x (1) , F k (x (1) )), . . . , (x (N ) , F k (x (N ) )) and use these to initialize system of -ideally linear -multivariate equations in the input variables, which can then potentially be solved via Gaussian elimination or by using Gröbner basis [START_REF] Courtois | Efficient algorithms for solving overdefined systems of multivariate polynomial equations[END_REF][START_REF] Faugere | A new efficient algorithm for computing gröbner bases (f4)[END_REF][START_REF] Faugère | A new efficient algorithm for computing gröbner bases without reduction to zero (f 5)[END_REF][START_REF] Courtois | General principles of algebraic attacks and new design criteria for cipher components[END_REF].

In its most basic form, an algebraic attack proceeds as follows: given a function F K : {0, 1} n → {0, 1} to be inverted (or distinguished from random), it seeks to find low degree multivariate polynomials (g, h) such that

F K • g = h.
If polynomials (g, h) of degree at most d are found, then the function F K can be inverted given n Õ(d) random samples (x, F K (x)), by solving a linear system in the coefficients of (g, h) given by the equations F K (x (i) ) • g(x (i) ) = h(x (i) ). Note that while the attack proceeds by solving a linear system of equations, the coefficients of this system depend not only on the x (i) , but also on the samples F K (x (i) ), which prevents the attack from being a linear attack according to our definition (where the coefficients are only allowed to depend on the x (i) ).

We note that while algebraic attacks are an important and well-studied class of attacks, they had been missed in the security analysis of the candidate weak PRF of Akavia et al [ABG + 14].9 It turned out that their candidate can be broken (in quasipolynomial time) using exactly the basic algebraic attack of [START_REF] Courtois | Algebraic attacks on stream ciphers with linear feedback[END_REF] described above (this was observed in [START_REF] Bogdanov | Pseudorandom functions: Three decades later[END_REF]). The authors of [BIP + 18] conjectured their weak PRF candidate to be secure against this algebraic attack, but could not prove it. Below, we formally prove that our candidate weak PRF cannot be broken by the above attack: Theorem 7.10 Fix parameters (w, D, N = 2 D ). Let n = κ ← w •D(D -1)/2, and let F K be the candidate weak PRF family of Section 6.2. For any K ∈ {0, 1} κ , the algebraic attack of [START_REF] Courtois | Algebraic attacks on stream ciphers with linear feedback[END_REF] requires a time and number of samples lower bounded by n O(D) = 2 O(D log(D+w)) .

Below, we prove Theorem 7.10 by showing that our candidate weak PRF has high algebraic degree.

Algebraic Immunity. The algebraic immunity of a boolean function F is defined as the following quantity:

AI(F ) = min g =0 {deg(g) | F g = 0 ∨ (F ⊕ 1)g = 0}.
It is relatively easy to see that the smallest d such that there exist polynomials (g, h) of degree at most d satisfying F K • g = h necessarily satisfies d ≥ AI(F K ). Therefore, the algebraic immunity of F K gives a lower bound on the efficiency of the above algebraic attack: attacking a weak PRF family {F K } K with the above attack requires at least min K n O(AI(F k )) samples. We now prove that our candidate weak PRF family has high algebraic immunity, hence cannot be broken by the above algebraic attack (implying Theorem 7.10).

Lemma 7.11 (Algebraic Immunity of rVDLPN) Fix parameters (w, D, N = 2 D ). Let n = κ = w • D(D -1)/2, and let F K be the candidate weak PRF family of Section 6.2. For any K ∈ {0, 1} κ , it holds that AI(F K ) ≥ D.

Proof. The proof is largely taken from [START_REF] Méaux | Towards stream ciphers for efficient FHE with low-noise ciphertexts[END_REF]. First, recall that our weak PRF candidate is given by

F K (x) = F (K ⊕ x)
where the function F is defined as

F (x) = D i=1 w j=1 i k=1 x i,j,k .
Now, it is easy to see that for any K, the algebraic immunity of F K is that of F : for any g such that

F K • g = 0 (resp. (1 ⊕ F K ) • g = 0), the function g K : x → g(K ⊕ x) trivially satisfies F • g K = 0 (resp. (1 ⊕ F ) • g K = 0), since x → K ⊕
x defines a permutation over the input domain (which is its own inverse). The same holds trivially in the reverse direction as well, hence

∀K ∈ {0, 1} κ : AI(F K ) = AI(F ).
It remains to bound the algebraic immunity of F . Observe that F is a direct sum of w independent triangular functions of degree D, each evaluated on distinct portions of the input, where the triangular function of degree D is defined as

T D (x 1 , • • • , x D(D-1)/2 ) = x 1 ⊕ x 2 x 3 ⊕ x 4 x 5 x 6 ⊕ • • • ⊕ D(D-1)/2 =D(D-1)/2-D x .
By Lemma 3 of [START_REF] Méaux | Towards stream ciphers for efficient FHE with low-noise ciphertexts[END_REF], the algebraic immunity of a direct sum of functions (evaluated on independent inputs) is at least the largest algebraic immunity of each of its components, hence Then, it is shown in [ACG + 06] that the fast algebraic attacks takes time at least n O(FAI(F )) to attack a function F with input size n. By [START_REF] Carlet | Boolean Functions for Cryptography and Coding Theory[END_REF], the fast algebraic immunity of a function F is lower bounded by AI + 1. This yields the following Lemma.

AI(F ) ≥ AI(T D ). Now,
Lemma 7.12 (Fast Algebraic Immunity of rVDLPN) Fix parameters (w, D, 2 D ). Let n = κ = w • D(D -1)/2, and let F K be the candidate weak PRF family of Section 6.2. For any K ∈ {0, 1} κ , it holds that FAI(F K ) ≥ D + 1.

Resistance Against Statistical Query Algorithms

Another important approach to ruling out candidate PRFs in low complexity classes is to provide a learning algorithm for the class. This is for example the basis of the approach of Linial, Mansour, and Nisan in [START_REF] Linial | Constant depth circuits, Fourier transform, and learnability[END_REF] which showed that all functions in the class AC 0 can be learned in quasipolynomial time given access to uniformly random samples (hence, there are no weak PRFs with better than quasipolynomial security in AC 0 ), by showing than any AC 0 function is noticeably correlated with a linear function of polylogarithmically many variables. This attack can be generalized to a class of attacks, called "LMN-style attacks" in [ABG + 14], which distinguishes a weak PRF candidate from random by detecting some large enough correlation between F K and a function Φ belonging to a family Φ of functions, where Φ has relatively small size. To resist such LMN-style attacks, any candidate PRF must therefore at least not have high correlation with members of any fixed function family of small size. An even more general class of attacks are those captured by the statistical query model of [START_REF] Kearns | Efficient noise-tolerant learning from statistical queries[END_REF], where random input-output pairs (x, F K (x)) are used to estimate some statistics E Φ = E x [Φ(x, F K (x))] for various functions Φ. A function family {F K } is (ε, δ)-pseudorandom against statistical query algorithms from a class of functions Φ if

Pr K E x [Φ(x, F K (x))] -E x,R [Φ(x, R(x))] ≤ ε ≥ 1 -δ.
Many known algorithms for learning from random samples operate in this manner. In spite of this generality, the work of [BR17, Section 7.7] proves that to achieve (ε, δ)-pseudorandomness against statistical query algorithms from a class of functions Φ, it suffices to have low correlation with a fixed family of functions, of size 2|Φ|. Hence, proving resistance against the seemingly less-general LMN-style attacks actually suffices to prove resistance against all statistical query algorithms. More precisely, given the class Φ, let Φ denote the class of functions Φ(•, b), for Φ ∈ Φ and b ∈ {0, 1} (of size 2|Φ|). Lemma 7.13 (Implicit in [START_REF] Bogdanov | Pseudorandom functions: Three decades later[END_REF]) For any function family {F K } K such that

Pr K $ ←{0,1} κ ∃Φ ∈ Φ , Pr x [F K (x) = Φ(x)] > 1 2 + ε ≤ δ,
then the function family {F K } is (ε, δ)-pseudorandom against statistical query algorithms from the class of functions Φ.

Below, we prove that our candidate resists all statistical query algorithms. More precisely, we show that for any fixed function family Φ of size at most s, with probability at least 1-s/(2 w+2 ε 2 ) over the choice of the PRF key K, the correlation between F K and any function from Φ is at most ε: Lemma 7.14 Fix parameters (w, D, N = 2 D ). Let n = κ = w • D(D -1)/2, and let F K be the candidate weak PRF family of Section 6.2. Let Φ = {Φ : {0, 1} n → {0, 1}} be a collection of functions of size s. Then for any ε,

Pr K $ ←{0,1} κ ∃Φ ∈ Φ, Pr x [F K (x) = Φ(x)] > 1 2 + ε ≤ s 2 w+2 ε 2 .
By Lemma 7.13, this suffices to guarantee (ε, s 2 w+2 ε 2 )-pseudorandomness against statistical query algorithms from any class of function of size s. Proof. The proof follows closely the strategy of [ABG + 14, BR17], but is slightly more involved because our function family is not pairwise independent. Fix a function Φ : {0, 1} n → {0, 1}. Define the random variable

Z(K) = Pr x [F K (x) = Φ(x)] = E x [1(F K (x), Φ(x))],
where 1(u, v) = 1 if u = v, and 0 otherwise. Then,

E K [Z(K)] = E K [E x [1(F K (x), Φ(x))]] = E x [E K [1(F (K ⊕ x), Φ(x))]] = E x [E y [1(F (y), Φ(x))]] = E x [Pr y (F (y) = Φ(x))] = 1/2,
where the last equality follows from the fact that for any b ∈ {0, 1}, Pr y [F (y) = b] = 1/2. The latter is immediate, as F can be written as F (x) = x 0 ⊕ F (x ) where x = x 0 ||x ; in other words, F (x) involves a XOR with with one of its variables that never appear in any other monomial. Now, we bound the variance σ 2 of Z(K):

E K [Z(K) 2 ] = E K [E x [1(F K (x), Φ(x))] 2 ] = E K [E x [1(F (K ⊕ x), Φ(x))] • E y [1(F (K ⊕ y), Φ(y))]] = E x,y [E K [1(F (K ⊕ x), Φ(x)) • 1(F (K ⊕ y), Φ(y))]] = x,y∈{0,1} n Pr K [(F (K ⊕ x) = Φ(x)) ∧ (F (K ⊕ y) = Φ(y))] • 2 -2n .
From there, the standard approach to conclude [ABG + 14, BR17, BIP + 18] is to rely on the pairwise independence of F K to bound E K [1(F K (x), Φ(x)) • 1(F K (y), Φ(y))]. This does not work immediately in our setting, since our candidate weak PRF family is easily seen to not be pairwise independent. Instead, we follow a different approach. Recall that our candidate weak PRF is of the form

F K (x) = D i=1 w j=1 i k=1 (x i,j,k ⊕ K i,j,k ).
The idea of the proof will be to look at the degree-2 component only. Whenever two inputs disagree in the part influencing the degree-2 component, the corresponding key component will show up in exactly one of those, allowing to argue independence. As this is the case for "most" inputs, this will be sufficient to prove the lemma. We isolate the degree-two component w j=1 (x 2,j,1 ⊕ K 2,j,1 ) ∧ (x 2,j,2 ⊕ K 2,j,2 ) from the rest of the above function, and write x 2,k = (x 2,j,k ) j∈[w] ∈ {0, 1} w and K 2,k = (K 2,j,k ) j∈[w] ∈ {0, 1} w for k ∈ {1, 2}, and denote by x R , K R the remaining bits of x and K (i.e. all x i,j,k , K i,j,k for i = 2), respectively. Hence, F K can be rewritten as

F K (x) = x 2,1 ⊕ K 2,1 , x 2,2 ⊕ K 2,2 ⊕ F (K R , x R ),
where F is the function that computes the missing monomials. Now, fix an arbitrary pair of inputs (x, y), decomposed as ((x 2,1 , x 2,2 , x R ), (y 2,1 , y 2,2 , y R )), such that x 2,2 = y 2,2 , and fix arbitrary K 2,2 , K R . Observe that

Pr K 2,1 [(F (K ⊕ x) = Φ(x)) ∧ (F (K ⊕ y) = Φ(y))] = Pr K 2,1 [ x 2,1 ⊕ K 2,1 , x 2,2 ⊕ K 2,2 = Φ(x) ⊕ F (K R , x R ) ∧ y 2,1 ⊕ K 2,1 , y 2,2 ⊕ K 2,2 = Φ(y) ⊕ F (K R , y R ) ].
Now, since x 2,2 = y 2,2 , there is at least one position j such that the jth bits of x 2,2 ⊕ K 2,2 and of y 2,2 ⊕ K 2,2 differ; let us fix such a j and assume without loss of generality that the jth bit of x 2,2 ⊕ K 2,2 is 1. For any bistring s, let us denote s =j the string s without its jth bit. Then, we have

x 2,1 ⊕ K 2,1 , x 2,2 ⊕ K 2,2 = (K 2,1 ) j ⊕ (x 2,1 ) j ⊕ (x 2,1 ⊕ K 2,1 ) =j , (x 2,2 ⊕ K 2,2 ) =j while y 2,1 ⊕ K 2,1 , y 2,2 ⊕ K 2,2 = (y 2,1 ⊕ K 2,1 ) =j , (y 2,2 ⊕ K 2,2 ) =j .
Therefore, the events F (K ⊕ x) = Φ(x) and F (K ⊕ y) = Φ(y) are truly independent:

Pr K 2,1 [(F (K ⊕ x) = Φ(x)) ∧ (F (K ⊕ y) = Φ(y))] = Pr (K 2,1 ) j [ x 2,1 ⊕ K 2,1 , x 2,2 ⊕ K 2,2 = Φ(x) ⊕ F (K R , x R )] • Pr (K 2,1 ) =j [ y 2,1 ⊕ K 2,1 , y 2,2 ⊕ K 2,2 = Φ(y) ⊕ F (K R , y R )] = 1 2 • 1 2 = 1 4 .
Furthermore, when x 2,2 = y 2,2 , it still holds that

Pr K [(F (K ⊕ x) = Φ(x)) ∧ (F (K ⊕ y) = Φ(y))] ≤ Pr K [(F (K ⊕ x) = Φ(x))] = 1 2 .
Let us partition {0, 1} n × {0, 1} n in two disjoint sets, S and S = {0, 1} n × {0, 1} n \ S, where S contains all pairs (x, y) which satisfy, when decomposed as ((x 2,1 , x 2,2 , x R ), (y 2,1 , y 2,2 , y R )), x 2,2 = y 2,2 . Then, the above imply

E K [Z(K) 2,2 ] = x,y∈S Pr K [(F (K ⊕ x) = Φ(x)) ∧ (F (K ⊕ y) = Φ(y))] • 2 -2n + x,y∈ S Pr K [(F (K ⊕ x) = Φ(x)) ∧ (F (K ⊕ y) = Φ(y))] • 2 -2n ≤ |S| • 1 4 • 2 -2n + | S| • 1 2 • 2 -2n . By construction, | S| = 2 2n-w since |x 2,2 | = |y 2,2 | = w, and |S| = 2 2n -2 2n-w . Therefore, E K [Z(K) 2,2 ] ≤ (2 2n -2 2n-w ) • 1 4 • 2 -2n + 2 2n-w • 1 2 • 2 -2n = (1 -2 -w ) • 1 4 + 2 -w • 1 2 = 1 4 • (1 + 2 -w ).
Now, by the definition of variance,

σ 2,2 = E K [Z(K) 2,2 ] -E K [Z(K)] 2,2 ≤ 1 4 • (1 + 2 -w ) - 1 4 = 1 2 w+2 .
Hence, by a straightforward union bound, the probability that there exist any r-tuple of vectors in (x . This implies, for example, that our candidate 2 -w/O(d 2 ) -fools AC 0 circuits of size up to 2 w/O(d 2 ) by setting D ← w t for any constant t < 1. We note that bounded independence also implies security against other classes of circuits beyond AC 0 , such as halfspaces [DGJ + 09] and degree-2 threshold functions [START_REF] Diakonikolas | Bounded independence fools degree-2 threshold functions[END_REF].

Linear Cryptanalysis

Among the standard attacks against PRF, we did not yet investigate linear cryptanalysis [START_REF] Matsui | Linear cryptanalysis method for DES cipher[END_REF] and differential cryptanalysis. Both types of attacks have been formalized in [START_REF] Miles | On the complexity of non-adaptively increasing the stretch of pseudorandom generators[END_REF]. Linear cryptanalysis exploits the correlation of F K with respect to some parity v of its input x (seen as a vector over F n 2 ). Following the formalism of [START_REF] Miles | On the complexity of non-adaptively increasing the stretch of pseudorandom generators[END_REF], we define the correlation of F K with respect to a vector v as

Corr v (F K ) = 2 • Pr x [ v • x = F K (x)] -1.
Then, the attack succeeds given a number of samples proportional to

max v = 0 E K [Corr v (F K ) 2 ] -1
.

We now bound this quantity. First, observe that

E K [Corr v (F K ) 2 ] = E K [(2 • E x [1( v • x, F K (x))] -1) 2 ] = 4 • E K [E x [1( v • x, F K (x))] 2 ] -E K [E x [1( v • x, F K (x))]] + 1
However, we have already shown in Section 7.4 that for any function Φ (hence in particular for the function Φ

: x → v • x), it holds that E K [E x [1(F K (x), Φ(x))]] = 1 2
, and

E K [E x [1(F K (x), Φ(x))] 2 ] ≤ 1 4 • (1 + 2 -w ).
Therefore,

E K [Corr v (F K ) 2 ] ≤ 4 • 1 4 • (1 + 2 -w ) -4 • 1 2 + 1 = 2 -w .
Hence, we get that

max v = 0 E K [Corr v (F K ) 2 ] -1 ≥ 2 w ,
showing that linear cryptanalysis requires exponentially many samples to succeed against our candidate. Differential cryptanalysis, on the other hand, does not apply to weak PRFs, since it requires "programming" inputs to exploit the existence of values ∆, ∆ such that Pr

x,K [F K (x) ⊕ F K (∆ ⊕ x) = ∆ ] is high.
Hence, differential cryptanalysis attacks are only allowed against strong PRFs, where the adversary is allowed to choose the inputs to the PRF. Actually, it is not hard to see our candidate is completely broken by differential cryptanalysis: any ∆ prefixed with sufficiently many zeroes satisfy Pr x,K [F K (x) ⊕ F K (∆ ⊕ x) = 0] with very high probability.

Other Candidate FSS-Friendly WPRFs

In this section, we describe variants of our main candidate weak PRF. These variants are achieved by progressively simplifying our main candidate, and analyzing whether the resulting candidate still resists known attacks. In the discussions of this section, we let w denote a security parameter, and fix parameters D(w) = O(w), and N (w) = 2 D . Observe that with these parameters, our main candidate has input size O(w 3 ), and key size O(w 3 ). Below, we provide two variants of our main construction which achieve smaller input size and/or key size, and discuss their security.

First Variant: Reusing Portions of the Input

Our first variant reduces the input length from w

• D(D -1)/2 to w • D. Recall that F K (x) is of the form F (K ⊕ x)
, where F is a direct sum of w triangular functions T D , which are evaluated on disjoint subsets of D(D -1)/2 bits of the input. The triangular function T D is defined as

T D (x) = D i=1 i j=1
x j+ i k=1 k .

In our first variant, the fan-in-i AND terms in the above triangular function are evaluated on length-i prefixes of a single D-bit string x, instead of being evaluated on independent lengthi strings (x 1 , • • • , x D ). That is, we replace the triangular function by the following simpler function T D : {0, 1} D → {0, 1}:

T D (x) = D i=1 i j=1 x j .
Hence, the new candidate weak PRF is given by

F K (x) = D i=1 w j=1 i k=1 (x j,k ⊕ K i,j,k ).
Security. Our first variant has the exact same security guarantees as our main candidate against linear attacks; that is, there exists constant (β, µ, ν) such that for any w, D(w) ≤ β • w, the first variant is a (µ w , ν w , 2 D )-biased weak PRF family. Indeed, the exact same security analysis applies: the proof never relies on the independence between the blocks H i , but only on the fact that the e i are sampled independently (which is needed to apply Lemma 3.2). In our main candidate, the use of triangular functions suffices to guarantee resistance against algebraic attack, since the degree-D triangular function has algebraic immunity D. However, it is easy to see that this does not hold anymore for the simpler function T D : we have

T D (x) = D i=1 i j=1 x j+ i k=1 k = x 1 •   D i=1 i j=2 x j+ i k=1 k   ,
hence the degree-1 function f : x → 1 + x 1 is an annihilator of T D (i.e., f • T D = 0), meaning that T D has algebraic immunity 1. Yet, we conjecture that the direct sum of w such functions has algebraic immunity min(w, D). We note that we got confirmation, through personal communication with Pierrick Méaux, that this function indeed has the claimed algebraic immunity; however, this result is not yet published to our knowledge.

Immunizing against other attacks with simple tweaks. We note that simple tweaks to the above function actually suffice to get provable resistance against the other attacks we considered, without changing the asymptotic input length. For example, for algebraic attacks, consider the following tweak of the function:

F K,Ky (x, y) = D i=1 w j=1 i k=1 (x j,k ⊕ K i,j,k ) ⊕ T D (y ⊕ K y ).
That is, we XOR the first variant with a term T D (y ⊕ K y ). This variant still has input size O(w 2 ). By Lemma 3.2 (the bias of a direct sum is at least the smallest bias) and Lemma 3 of [START_REF] Méaux | Towards stream ciphers for efficient FHE with low-noise ciphertexts[END_REF] (the algebraic immunity of a direct sum is at least the largest algebraic immunity of each of its components), the above variant inherit both the resistance of the first variant to linear attacks, and the high algebraic immunity of triangular functions. This gives us a candidate weak PRF in the class XOR • AND, with input size O(w 2 ), which provably resists linear attacks and algebraic attacks running in time 2 O(w) . The same holds for statistical query algorithms or AC 0 attacks: all these variants can easily be enhanced to resist these attacks as well, by XORing them with appropriate functions in XOR • AND which provably resist these attacks (e.g. XORing with the linear input size function f K (x) = x, K suffices to resists statistical query algorithms, since this function is pairwise independent). We conjecture that these tweaks are actually not needed (that is, that this variant can be proven to resist all attacks we considered) and only help simplifying the analysis.

Optimality. A crucial feature of this variant is that it actually achieves optimal (conjectured) security as a function of its input size: it has input size n = O(w 2 ) (using D = O(w) and resistance at least 2 O(w) against linear attacks. As we will show in the next section, there actually exists linear attacks which break this candidate (and the first one) in time 2 Õ( √ n) , which is exactly 2 Õ(w) here. Hence, This candidate has the smallest input size possible to achieve Õ(w) bits of security.

Second Variant -Reducing the Key Size

Eventually, we put forth the security of the following candidate as an entirely open question: "smallest" rVDLPN:

F K (x) = D i=1 w j=1 i k=1 (x j,k ⊕ K jk ), where x ∈ {0, 1} w•D and K ∈ {0, 1} w•D .
This candidate retains the optimal input size of our previous candidate, but reduces the key size by a factor (D + 1)/2. This is particularly interesting for our PCF application, as the decision tree construction of [START_REF] Boyle | Function secret sharing: Improvements and extensions[END_REF] gives the FSS for all prefix functions (and therefore all products for a fixed j) at only a factor 2 overhead compared to FSS for a single point function. Therefore, we can save a factor of D/2 in the FSS key size building on our third candidate assumption.

While this modification makes our proof of resistance against linear attacks break down (since the independence between samples from the various distributions we consider is not guaranteed anymore), we could not find any attack on this candidate, and put forth its conjectured security as an interesting challenge to investigate. We summarize the candidates discussed in this section in Table 2.

Resistance against attacks

FK (x)

input size FSS key size Linear Algebraic Correlation AC 0

D i=1 w j=1 i k=1 (x i,j,k ⊕ K i,j,k ) O(w • D 2 ) O(w 2 • D 2 ) D i=1 w j=1 i k=1 (x j,k ⊕ K i,j,k ) O(w • D) O(w 2 • D 2 ) D i=1 w j=1 i k=1 (x j,k ⊕ K j,k ) O(w • D) O(w 2 • D) ? ? ? ?
Table 2: List of candidate weak PRF families, with N (w) = 2 D(w) . One can choose D(w) = polylog(w), if one aims at (quasi)exponential security up to N = w polylogw samples, or D(w) = w for subexponential security up to 2 O(w) samples. For the second row, the provable resistance actually holds w.r.t. minor tweaks of the function which do not change its input and key size in the case of algebraic attacks, statistical query algorithms, and AC 0 attacks.

Concrete Attacks on our WPRF Candidates

In this section, we complement the asymptotic analysis of our candidate's resistance against families of attacks (see Section 7) by analyzing how our candidates behave against concrete attacks, and putting forth conjectures regarding the exact security of our candidates against families of attacks.

Concrete Linear Attacks

Most attacks from the LPN literature are linear attacks. To our knowledge, all state-of-theart attacks (in terms of concrete efficiency) are linear attacks, either from the information set decoding family (for LPN with a linear number of samples) or BKW-style attacks (for LPN with a larger number of samples). In our context, the VDLPN problems with parameters (w, D, N = 2 D ) correspond to an LPN-style problem with dimension (w -1) • 2 D , and w • 2 D samples. Hence, the dimension is extremely close to the number of samples, and BKW-style attacks seem less likely to be particulary powerful, even using the sample-reduction technique of Lyubashevsky [START_REF] Lyubashevsky | The parity problem in the presence of noise, decoding random linear codes, and the subset sum problem[END_REF].

A Concrete Conjecture on Security Against Linear Attacks. The proof of resistance against linear attacks from Section 7 is very loose. However, we conjecture that much tighter bounds actually hold. Here, we put forth a simple combinatorial conjecture, which is a strong strenghtening of the loose bound which we prove in Section 7, and which can potentially be experimentally validated through simulated balls-and-bins experiments. We recall some notation: We fix the number of samples to N = 2 D . For 1 ≤ i ≤ D, M i par samples a random matrix in F N ×2 i 2 with row-weight 1. For any vector v and fixed i, we say that

Y has O(2 σ √ n ) samples and 2 σ √ n ≥ n √
n , the linearization step can be carried out on samples in Y and Q(x) learned.

We complete the description of the algorithm by noting that since P is sparse, Q is a good approximation for P . That is, Pr[M (y) = 0] ≤ 2 - √ n for a monomial M in R and a uniformly chosen sample y. Therefore, Pr[R(y) = 0] ≤ k 2 √ n for a random y and P (x) = Q(x) except with k 2 √ n probability.

Concrete Security Against Other Attacks

To complement the above, we briefly discuss the concrete security of our candidate against other attacks. Regarding algebraic attacks, the natural attack proceeds by using the fact that our candidates are degree-D multivariate polynomials. Therefore, one needs at least n D samples to linearize the system of equations and distinguish the samples from random (the expected number of samples needed is of the order of n D log(n D )). In the first candidate, n = w • D(D -1)/2; in the second candidate, n = w • D. Therefore, the provable resistance against algebraic attacks (which is proven in the case of the first candidate, and can be proven for a simple modification of the second candidate, see the dicussion in Section 8.1) is actually tight, since it matches exactly what is achieved by the straightforward linearization attack.

Regarding statistical query algorithms, fix some ε. Observe that having (1/2 + ε)-correlation with a function from a family of size s with probability s/(2 w+2 ε 2 ) implies an attack which requires about 2 w+2 function evaluations, and succeeds with some constant advantage: simply set s to 2 w+2 ε 2 and go through all functions from the family. For each function Φ, estimate whether Pr x [F K (x) = Φ(x)] by sampling about (1/ε) 2 independent x and counting the number of times that F K (x) = Φ(x). Since the function family contains a function correlated with F K , and this correlation is detected with constant probability using 1/ε 2 samples, this attack succeeds with constant probability, and requires of the order of 2 w function evaluations.

In particular, in the case of our second candidate where n = w • D (and D < w), this implies that every statistical query algorithm also requires at least 2 √ n function evaluations, which is the optimal security one can hope for anyway in light of the restriction attack described above.

Concrete Efficiency Estimations for PCF for VOLE

In light of the above discussions, instantiating the parameters with w ≈ 1.5 • λ, D = w/4, and N = 2 D , both our main candidate and the two variants can plausibly achieve λ bits of security. We note that these are very preliminary estimates, which could be off by a large margin and be either too optimistic or too conservative. Further, we note that our arguments and discussions only support the security claims regarding our main candidate and the first variant; for the second variant, we could not provide any proof of resistance against families of attacks. At the same time, however, we could not find any attack that performs significantly better against the second variant compared to the main candidate and the first variant.

Plugging our second variant (modified to work over rings as in Section 6.3) into the construction of PCF for VOLE of Section 6.4, and using the fact that distributed point functions for all prefixes of a point can be generated "all at once" at only a factor-2 cost compared to generating a single DPF (using the decision tree construction of [START_REF] Boyle | Function secret sharing: Improvements and extensions[END_REF]), leads to a PCF for VOLE over a ring R with N = 2 D samples using key size

≈ 2w • (D • κ + log 2 |R|)
bits, where κ denotes a seed size for a PRG. Using the more conservative variants of our PCF construction (either the main candidate or the first variant), the above size grows by a factor D/2. With λ = 80 and log 2 |R| = 64, setting κ to 128 (as in an AES-based implementation), this gives the numbers of 120kB and 2MB mentioned in the introduction, for the second variant Functionality F Y corr * Initialization. On input 1 λ , the functionality does as follows:

• Set Q = ∅.
• If the correlation requires setup: Sample mk ← Setup(1 λ ).

Invocation. On input x ∈ {0, 1} n(λ) proceed as follows:

• Check if (x, y 0 , y 1 ) ∈ Q.

• Else, if no parties are corrupt, sample (y 0 , y 1 ) ← Y(1 λ , mk).

• Else, if P σ is corrupt, wait to receive y σ ∈ {0, 1} σ from A. Then, sample y 1-σ ← RSample(1 λ , mk, σ, y σ ).

• Set Q = Q ∪ {(x, y 0 , y 1 )} and output y σ to P σ . functionality for two parties against a static, malicious adversary (even if the adversary is given full adaptive control over the choice inputs x ∈ {0, 1} n(λ) ).

Proof. Let A be a static adversary against the protocol Π Y corr * . We construct a simulator Sim, which interacts with A and F Y corr * to produce a view for A that is indistinguishable from a real execution of the protocol. When both parties are corrupted, the simulator just runs A internally and security is straightforward. Similarly, when both parties are honest, simulation is trivial and indistinguishability follows as PCF satisfies pseudorandomness of outputs with adaptive queries (i.e. indistinguishability even holds if the adversary is given full adaptive control over x). Now suppose that only P σ is corrupted, for σ ∈ {0, 1}. On receiving the input 1 λ , Sim samples a pair of seeds (k 0 , k 1 ) ← PCF.Gen(1 λ ) and sends k σ to A as its output of F PCF.Gen . On input x i , the simulator computes y i,σ ← PCF.Eval(σ, k σ , x i ) and sends this to F F corr * . Let N be the number of inputs to F F corr * . Notice that in the ideal execution, the view of the distinguisher consists of the seed k σ and the honest party's output (y i,1-σ ) i∈[N ] , which is computed by F Y corr * as y i,1-σ ← RSample(1 λ , mk, σ, y i,σ ). The only difference in the real execution, is that there the i-th honest party's output is computed as y i,1-σ ← PCF.Eval(1 -σ, k 1-σ , x i ). These two views are computationally indistinguishable, due to the strong security of PCF (even if the adversary has full control over the choice of inputs x ∈ {0, 1} n(λ) after seeing its key k σ ).

Note that in order to establish PCFs as a source for correlated randomness, the parties need to securely distribute the PCF keys, which we will briefly elaborate on in the following. Butdifferent to previous approaches for correlated randomness that were either inherently limited to a one-time use or only allowed limited reusability -once the parties share a PCF key pair, they can engage in arbitrarily many protocol invocations consuming correlated randomness, without the need to perform any further interactive preprocessing.

Realizing distributed key generation. Recall that the ideal key generation F PCF.Gen receives as input 1 λ , sets up a pair of keys (k 0 , k 1 ) ← PCF.Gen(1 λ ) and returns k σ to P σ .

When restricting the input domain to be polynomially bounded, as for previous constructions of pseudorandom correlation generators, one could implement F PCF.Gen with the protocol for distributed setup of point functions by Doerner and shelat [START_REF] Doerner | Scaling ORAM for secure computation[END_REF] (for semi-honest security).

For our PCF for OT with bounded input domain, one could further rely on the optimized protocol of Boyle et al. [BCG + 19a] yielding a 2-round setup. They also give a setup protocol with malicious security, but at the cost of a slightly stronger assumption -translated to our setting, this requires to assume that VD-LPN holds even if the adversary is given small leakage on the key (which we expect to be the case when adapting the parameters accordingly).

As the focus of the work is full reusability and therefore an exponential input domain, we have to resort to an "off-the-shelf" protocol for setting up the keys, such as [START_REF] Katz | Optimizing authenticated garbling for faster secure two-party computation[END_REF]. Note though that this only corresponds to a one-time cost, after which the parties can locally produce correlated randomness for all future computations.

Alternatively, if one is willing to settle for security against one corruption, as remarked in [START_REF] Boyle | Secure computation with preprocessing via function secret sharing[END_REF], this cost can be avoided completely by letting a third party set up the correlated randomness. Note that this is similar to the 3-party framework from [START_REF] Mohassel | ABY 3 : A mixed protocol framework for machine learning[END_REF], but in our setting the third party does not have to take part in the actual computation.

Black-box Two-Round MPC with Fully Reusable Preprocessing

Although the feasibility of MPC protocols has been established more than thirty years ago, there is still a large gap in efficiency between the insecure approach (i.e. each party distributing its private inputs) and the most efficient secure realization. One important measure of complexity is the number of communication rounds between the parties required for the protocol. While the insecure approach gets by with one round, it is easy to see that any secure realization requires at least two rounds. But -even though possible -the construction of secure 2round protocols for secure computation turns out to be much more challenging than protocols for secure computation with arbitrary round complexity. The first proposal of a two-round secure MPC protocol [START_REF] Garg | Two-round secure MPC from indistinguishability obfuscation[END_REF] was published only in 2014 and still relied on assuming the existence of indistinguishability obfuscation. Since then rapid progress in this area has seen a number of proposed protocols based on seemingly weaker assumptions, such as Learning with Errors [MR17, BP16, PS16] and bilinear maps [GS17, BF01, Jou04], and was ultimately based on the minimal assumption that a 2-round oblivious transfer (OT) protocol exists [START_REF] Benhamouda | k-round multiparty computation from k-round oblivious transfer via garbled interactive circuits[END_REF][START_REF] Garg | Two-round multiparty secure computation from minimal assumptions[END_REF].

However, even latter OT-based protocols are still far from being concretely efficient, which can be explained by their inherent non-black box use of the underlying OT protocol [ABG + 20]. Garg et al. [START_REF] Garg | Two-round MPC: Information-theoretic and black-box[END_REF] showed that this black-box impossibility can be circumvented by giving each pair of parties access to random OT correlations. Given this setup, they presented a 2-round protocol making only a black-box use of a pseudorandom generator, and achieving security against a malicious adversary corrupting an arbitrary number of parties. Plugging in our PCF for setting up the correlated randomness results -at a one-time setup cost -in a black-box protocol for two-round MPC with fully reusable preprocessing.

NIZKs with Fully Reusable Preprocessing

Zero-knowledge proofs allow a prover to convince a verifier of a statement without revealing anything beyond this statement. Zero-knowledge proofs, in some sense, can be viewed as a special case of secure computation, where only the prover has a secret input (that is, the witness for the statement being true), and the verifier wants to receive the output (i.e. 1 if the statement is true). While non-interactive zero-knowledge (NIZK) proofs turn out to be impossible to realize in the plain model, they exist when given a common reference string, generated by a trusted third party. There has been great effort in realizing the notion of non-interactive zero knowledge proofs for general NP languages. Remarkably, Peikert and Shiehian [PS19] -following the line of work of [CCRR18, HL18, CCH + 19] -gave a construction of NIZKs from plain Learning with Errors. Brakerski et al. [START_REF] Brakerski | NIZK from LPN and trapdoor hash via correlation intractability for approximable relations[END_REF] recently showed that NIZKs can be constructed based on the hardness of both the learning parity with noise (LPN) assumption and the existence of trapdoor hash functions.

However, we still lack instantiations from Learning Parity with Noise assumption (or any flavors thereof) alone. Further, the results in the recent line of work -instantiating the Fiat-Shamir transform with a suitable correlation intractable hash function family -have a strong non-black-box flavor and are far from being concretely efficient. In order to overcome these limitations and enable further diversification of assumptions several relaxations of NIZKs have been introduced, such as designated verifier NIZKs (DV-NIZKs), where a trusted third party additionally gives a secret verification key to the verifier, or preprocessing NIZKs (PP-NIZKs), in which the trusted party generates -in addition to to the verification key -a secret proving key for the prover.

NIZKs from PCF for OT. Information-theoretic constructions of NIZK are known in the OT-hybrid model [KMO90,PsV06,IKOS07,GIK + 15], i.e. given access to OT correlations, where -similar to secure computation -the number of OT correlations to be used scales with the size (and the number) of the theorems to be proven. Building on this line of work, Boyle et al. [BCG + 19b] showed that from a PCG for OT, one can build a PP-NIZK supporting a form of bounded reusability, where the setup can be used to prove an arbitrary polynomial but a-priori bounded number of theorems. Replacing PCGs by PCFs gives rise to a construction of PP-NIZKs with fully reusable preprocessing, where after a one-time setup the parties can prove and verify an arbitrary number of statements. The downside of this approach is that in order to compute a NIZK for an NP-relation represented by a Boolean circuit of size s, the online phase has a computational cost that scales superlinear with s, typically multiplied by a statistical security parameter.

NIZKs from PCFs for VOLE or OLE over large fields. It turns out that by replacing OT correlation with OLE or even VOLE over F, one can obtain much more efficient NIZK protocols that apply directly to arithmetic circuits over F [BCGI18, CDI + 19, WYKW20]. The recent VOLE-based protocol from [START_REF] Weng | Fast, scalable, and communicationefficient zero-knowledge proofs for boolean and arithmetic circuits[END_REF] has competitive concrete efficiency not only for arithmetic circuits but also for Boolean circuits. From an asymptotic point of view, the distinctive feature of this approach to NIZK is that the statement-dependent online phase of generating and verifying a proof has constant computational overhead in the arithmetic computation model, compared to evaluating the verification circuit in the clear. That is, the protocol achieves soundness error of O(1/F) while only requiring a small constant number of field operations for each arithmetic gate of the computation being verified. This should be contrasted with zk-SNARGs, which have sublinear communication and verifier computation, but on the other hand are much heavier in terms of prover computation.

Related work. Recently, Lombardi et al. [LQR +

19] showed how to construct reusable DV-NIZKs, i.e. where the verifier can reuse the verification key across many verifications, and the stronger notion of malicious DV-NIZKs, based on the generic assumption of public-key encryption together with a weak form of key-dependent secure secret-key encryption. These components can in particular be instantiated from low-noise Learning Parity with Noise. Their result is somewhat orthogonal to ours: While they obtain the stronger notion of reusable DV -NIZKs from a -technically incomparable but "morally" -weaker assumption, the main advantage of constructing PP-NIZKs via the VOLE-hybrid model is that its online phase is very lightweight and does not involve public key cryptography. As discussed above, when evaluating the PCF in a statement-independent offline phase, computing and verifying each VOLE-based proof requires only a small constant-factor overhead compared to evaluating the circuit in the clear. Definition 10.2 (Simple bilinear correlation) Let G 1 , G 2 , G T be Abelian groups and e : G 1 × G 2 → G T be a bilinear map. We define Y e as the algorithm that samples the simple bilinear correlation defined by e. More formally, let Y e be the algorithm, that on input 1 λ samples from the following distribution over (G 1 × G T ) × (G 2 × G T ): {((r 0 , s 0 ), (r 1 , s 1 )) | r 0 ← G 1 , r 1 ← G 2 , s 0 ← G T , s 1 = e(r 0 , r 1 ) -s 0 } .

(Recall that the groups here may depend on λ.) Definition 10.3 (Simple Bilinear Correlation: M -party) Given Y e specified by e : G 1 × G 2 → G T , we define Y M,e as the corresponding M -party correlation Y M,e , obtained by sampling from:

     (a i , b i , c i ) i∈[M ] a i $ ← G 1 , b i $ ← G 2 ∀i ∈ [M ], c i $ ← G T ∀i ∈ [M -1], c M = e M i=1 a i , M i=1 b i -M -1 i=1 c i     
Programmability for a PCF means basically, that a party can reuse its input (e.g. the receiver choice bit or the sender messages) across many instances. This is captured in the following definition.

Definition 10.4 (Programmability) A PCF PCF = (PCF.Gen, PCF.Eval) for Y e (specified by e : G 1 × G 2 → G T ) supports reusable inputs if there exists an algorithm PCF.Gen p that takes additional random inputs ρ 0 , ρ 1 ∈ {0, 1} such that:

• Indistinguishability. The distributions (k 0 , k 1 ) | (k 0 , k 1 ) ← PCF.Gen(1 λ ) and (k 0 , k 1 ) | (ρ 0 , ρ 1 ) ← $, (k 0 , k 1 ) ← PCF.Gen p (1 λ ; ρ 0 , ρ 1 ) are computationally indistinguishable.

• Programmability. There exist public efficiently computable functions f 0 , f 1 for which Pr       ρ 0 , ρ 1 ← $, (k 0 , k 1 ) ← PCF.Gen p (1 λ ; ρ 0 , ρ 1 ) (a, c) ← PCF.Eval(0, k 0 , x), (b, d) ← PCF.Eval(1, k 1 , x)

: a = f 0 (ρ 0 , x) b = f 1 (ρ 1 , x)      
≥ 1 -negl(λ).

• Security. For any σ ∈ {0, 1}, the distributions (k σ , (ρ 0 , ρ 1 )) | (ρ 0 , ρ 1 ) ← $, (k 0 , k 1 ) ← PCF.Gen p (1 λ ; ρ 0 , ρ 1 ) and

(k σ , (ρ σ , ρ)) | (ρ 0 , ρ 1 , ρ) ← $, (k 0 , k 1 ) ← PCF.Gen p (1 λ ; ρ 0 , ρ 1 ), are computationally indistinguishable.

To simplify notation, in the following we will write PCF.Gen when referring to PCF.Gen p . Programmable PCF for OT based on regular VD-LPN Let DPF = (DPF.Gen, DPF.Eval) be an FSS scheme for point functions with variable input length. Recall that f K i,j : {0, 1} i → {0, 1} is the point function with f K i,j (x) = 1 if and only if x = K i,j .

PCF.Gen(1 λ ; ρ 0 , ρ 1 ): On input 1 λ and ρ 0 , ρ 1 ∈ {0, 1} w•D(D+1)/2 :

1. Set K = ρ 0 and K = ρ 1 .

2. Parse K as K i,j ∈ {0, 1} i , for j ∈ [w], i ∈ [D] (and accordingly for K ).

3. For all j, j ∈ [w] and i, i ∈ [D]:

• Sample FSS keys K fss 0,i,j,i ,j , K fss 1,i,j,i ,j ← DPF.Gen(1 λ , i • j, f K i,j ⊗K i ,j ).

4. For σ ∈ {0, 1} set K fss σ := {K fss σ,i,j,i ,j } j,j ∈[w],i,i ∈[D] . 5. Output the keys k 0 = (K, K fss 0 ) and k 1 = (K , K fss 1 ).

PCF.Eval(σ, k σ , x): On input a random x ∈ {0, 1} w•D(D+1)/2 : Parse x as x i,j ∈ {0, 1} i , for j ∈ [w], i ∈ [D].

• If σ = 0:

1. Compute a ← F K (x). 2. For j, j ∈ [w], i, i ∈ [D]: c i,j,i ,j ← DPF.Eval(0, K fss 0,i,j,i ,j , x i,j ⊗ x i ,j ) 3. Compute c = w j,j =1 D i,i =1 c i,j,i ,j . 4. Output (a, c).

• If σ = 1:

1. Compute b ← F K (x). 2. For j, j ∈ [w], i, i ∈ [D]: d i,j,i ,j ← DPF.Eval(1, K fss 1,i,j,i ,j , x i,j ⊗ x i ,j ) 3. Compute d = w j,j =1 D i,i =1 d i,j,i ,j . 4. Output (b, d). For a generic construction of a programmable PCF for VOLE from a weak PRF together with a suitable FSS, we refer to Appendix C.

Secure Multi-Party Computation with Linear Communication. Now, we are ready to give a general transformation from any programmable PCF for a simple bilinear correlation

  Lemma 3.5 (Bounded Difference Inequality) Let Φ : [n] m → R be a function satisfying the Lipschitz property with constant d, and let (X 1 , • • • , X m ) be independent random variables over [n].

Figure 2 :

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

  Definition 4.4 (Strong pseudorandom correlation function (sPCF)) Let Y and (PCF.Gen, PCF.Eval) be as in Definition 4.3. We say that (PCF.Gen, PCF.Eval) is an strong (N, B, ε)-secure PCF (sPCF) for Y if the following conditions hold:

Figure 4 :

 4 Figure 4: Strong security of a PCF. Here, RSample is the algorithm for reverse sampling Y according to Definition 4.1.

Figure 5 :

 5 Figure 5: From weak to strong PCF.

Figure 7 :

 7 Figure 7: PCF for 1-out-of-2 oblivious transfer based on FSS for a weak PRF

2

  obtained by sampling H i $ ← H i par for i = 1 to D and outputting H = H 1 || • • • ||H D . Eventually, we denote by N par the noise distribution obtained by sampling e i $ ← R w,i and outputting e ← ( e 1 // • • • // e D ) ∈ F 2N 2 . Definition 6.1 (rVDLPN(w, D, N )) The regular variable-density learning parity with noise assumption with sparsity w, D blocks, and number of samples N , denoted rVDLPN(w, D, N ), states that {(H, b) | H

  Finally, we denote by N par (R) the noise distribution obtained by sampling e i $ ← R w,i (R) and outputting e ← ( e 1 // • • • // e D ) ∈ R 2N . Definition 6.4 (R-rVDLPN(w, D, N )) The regular variable-density learning parity with noise assumption over a ring R with sparsity w, D blocks, and number of samples N , denoted by R-rVDLPN(w, D, N ), states that

  4. Output (b, c 1 ).

Figure 8 :

 8 Figure 8: PCF for vector oblivious linear evaluation over a ring R based on our weak PRF FK from rVDLPN over R and distributed point function DPF.

Figure 9 :

 9 Figure 9: PCF for oblivious transfer based on our weak PRF FK from rVDLPN and distributed point function DPF.

Figure 10 :

 10 Figure 10: Universal PCF for degree-2 polynomials over F2 based on our weak PRF FK from rVDLPN and distributed point function DPF.

  proof. Plugging the result of Braverman [Bra08] into Theorem 7.15, we get: Corollary 7.16 Our candidate weak PRF ε-fools depth-d AC 0 circuits of size m, with probability at least 1/(w/D)! over the random choice of N = 2 D inputs, for any ε such that w/D = log m ε O(d 2 )

Figure 13 :

 13 Figure 13: Corruptible correlated randomness functionality for reverse-sampleable correlation sampled by Y (with setup algorihm Setup, if required).

  Theorem 10.5 (Programmable PCF for OT) If DPF is instantiated with the DPF from [GI14], then, assuming that rVDLPN(O(λ), D, 2 D ) holds, PCF = (PCF.Gen, PCF.Eval) as defined in Figure 14 is an programmable (2 D , negl)-secure PCF for OT with the following complexities:

Figure 14 :

 14 Figure 14: Programmable PCF for OT based on regular VD-LPN.

  18]. Our work proposes conceptually simple WPRF candidates in AC 0 [⊕] that have depth 2 (the best possible) and are FSS-friendly. See Table 1 for comparison with related work.

			Complexity Class
	Circuit Depth	AC 0	AC 0 [⊕]	ACC 0 †
	Depth 2	Weak PRF [BFKL94] (quasipolynomial * )	Weak PRF (subexponential * ) ‡	Weak PRF [BIP + 18] (exponential * )
	Depth 3	Weak PRF [AR16]	BR17] Weak PRF [ABG + 14,	Strong PRF [BIP + 18]
		(quasipolynomial)	(quasipolynomial * )	(exponential * )
	Depth > 3	Weak PRF [Kha93] (quasipolynomial)	Strong PRF [NR97, Vio13] (quasipolynomial)	-
		No weak PRF with	No strong PRF with
	Negative Results	better than quasipolynomial	better than quasipolynomial	-
		security [LMN89]	security [RR97, CIKK16]
	Table 1: Comparison of positive and negative results for constant-depth PRFs. When measuring depth, we
	consider the complexity of mapping the input to the output when the key is fixed, and do not count negations of
	the input. For each candidate, we denote in parenthesis its conjectured level of security. Different constructions
	in the same class rely on incomparable assumptions. The entry shown in bold is from this work.

  by Lemma 6 of[START_REF] Méaux | Towards stream ciphers for efficient FHE with low-noise ciphertexts[END_REF], the algebraic immunity of the degree-D triangular function is exactly D (the proof is a simple proof by induction, see Appendix C.2 of[START_REF] Méaux | Towards stream ciphers for efficient FHE with low-noise ciphertexts[END_REF]). Therefore, we get ∀K ∈ {0, 1} κ : AI(F K ) ≥ D, which concludes the proof.

	Fast Algebraic Immunity. An improved variant of the above algebraic attack, called fast
	algebraic attack, was introduced by Courtois in [Cou03]. It was shown in [ACG + 06] that it
	suffices, for a candidate F K to withstand this attack, that F K has high fast algebraic immunity
	(denote FAI(F K )), which is defined as
	FAI(F ) = min 2AI(F ),	min
	1≤deg g≤AI(F )

{max{deg(g) + deg(F g), 3 deg g}} .

This applies to the so-called "dual" variant of PCG constructions that can achieve an arbitrary polynomial stretch; settling for at most a quadratic stretch, the "primal" variant allows random access to the output[START_REF] Boyle | Compressing vector OLE[END_REF][START_REF] Schoppmann | Distributed vector-OLE: Improved constructions and implementation[END_REF].

One could alternatively view a PCF as a pair of correlated pseudorandom functions. The term pseudorandom correlation function (similarly to a pseudorandom correlation generator) refers to a single function f k that samples from a pseudorandom correlation given suitably correlated keys.

As is common in the study of constant-depth PRFs, we consider the complexity of mapping the input to the output when the key is fixed, where inputs can be negated without counting towards the depth. The latter is consistent with, for instance, a DNF formula having depth 2. Viewed as a function of both the input and the key, the depth increases to 3.

To see this, one can think of Hi,j as the weight-1 vector with non-zero position (xi,j,1, . . . , xi,j,i) (read as an integer between 0 and 2 i -1), and ei,j the weight-1 vector with non-zero position (1 ⊕ ki,j,1, . . . , 1 ⊕ ki,j,i).

Note that for the case of VOLE, and similarly for random OT correlations, one can in fact replace the FSS primitive by the simpler puncturable pseudorandom function primitive [KPTZ13, BW13, BGI14].

The number of ciphertexts could be reduced using packing techniques[START_REF] Gentry | Fully homomorphic encryption with polylog overhead[END_REF], but this requires storing additional 'key-switching' material, and would not change the overall key size.

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.

More precisely, PCG is a PCG for the correlation generator Y N , where Y N on input 1 λ returns N independent samples from Y.

The analysis of [ABG + 14] is also more restricted than ours in that it considers only resistance against a very specific form of linear attacks (correlation with a low degree polynomial), while we prove security against all possible linear attacks.

Acknowledgements

We would like to thank Nader Bshouty, Rocco Servedio, Jean-Pierre Tillich, Nicolas Sendrier, and Thomas Debris for useful discussions and pointers, and the anonymous FOCS reviewers for helpful suggestions. E. Boyle, N. Gilboa, and Y. Ishai supported by ERC Project NTSC (742754). E. Boyle additionally supported by ISF grant 1861/16, AFOSR Award FA9550-17-1-0069, and ERC Project HSS (852952). G. Couteau supported by ERC Project PREP-CRYPTO (724307). N. Gilboa additionally supported by ISF grant 2951/20, ERC grant 876110, and a grant by the BGU Cyber Center. Y. Ishai additionally supported by NSF-BSF grant 2015782, BSF grant 2018393, ISF grant 2774/20, and a grant from the Ministry of Science and Technology, Israel and Department of Science and Technology, Government of India. L. Kohl is funded by NWO Gravitation project QSC. Most research of L. Kohl was done while at Technion, supported by ERC Project NTSC (742754). Research of L. Kohl was done in part while at Karlsruhe Institute of Technology, supported by ERC Project PREP-CRYPTO (724307) and DFG grant HO 4534/2-2. P. Scholl supported by the Danish Independent Research Council under Grant-ID DFF-6108-00169 (FoCC) and an Aarhus University Research Foundation starting grant.

PCF for OT from regular VDLPN

Let from DPF = (DPF.Gen, DPF.Eval) an FSS scheme for point functions with variable input length. Recall that f K,s : {0, 1} i → {0, 1} λ is the point function with f K,s (x) = s if and only if x = K.

2. For all j ∈ [w] and i ∈ [D]:

PCF.Eval(σ, k σ , x): On input a random x ∈ {0, 1} w•D(D+1)/2 : Let x be the first λ bits of x. Parse x as x i,j ∈ {0, 1} i , for j ∈ [w], i ∈ [D].

• If σ = 0:

1. For all j ∈ [w], i ∈ [D]: Let q i,j ← DPF.Eval(0, K fss 0,i,j , x i,j ). 2. For all k ∈ [λ]: Compute q = D i=1 w j=1 q i,j . 3. Compute y 0 = H(x ⊕ q), y 1 = H(x ⊕ q ⊕ s). 4. Output (y 0 , y 1 ).

To finish the proof, it remains to apply the Bienaymé-Chebyshev inequality (Lemma 3.3), which immediately gives

from which the result directly follows by a union bound.

Resistance Against AC 0 Tests

Fix parameters (w, D, N = 2 D ). Let n = κ = w • D(D -1)/2, and let F K be the candidate weak PRF family of Section 6.2. For any input x ∈ {0, 1} n , let R x denote the random variable distributed as F K (x) for a random K from {0, 1} κ . Theorem 7.15 ((w/D)-Wise Independent) Pr

Proof. As in the proof of Lemma 7.14, we rely on the fact that for any input x, F K (x) can be rewritten as

where (x 2,1 , x 2,2 , x R ) and (K 2,1 , K 2,2 , K R ) form appropriate partitions of x and K. Hence, to prove that the F K (x (i) ) for i = 1 to N are (w/D)-wise independent, it suffices to fix an arbitrary K R and prove that the random variables R x (i) induced by x

2,2 ⊕ K 2,2 for random (K 2,1 , K 2,2 ) are (w/D)-wise independent (with high probability over the choice of x (1) , • • • , x (N ) ).

Furthermore, if the random variable R x (i) induced by K 2,1 , x

2,2 for a random K 2,1 are (w/D)-wise independent (with high probability over the choice of the x (i) ), then the R x (i) are (w/D)-wise independent. Now, it is a well-known results (see for example [START_REF] Naor | Small-bias probability spaces: Efficient constructions and applications[END_REF]) that N random variables ( K 2,1 , z (i) ) i≤N will be (w/D)-wise independent if any size-(w/D) subset of the z (i) , seen as length-n vectors over F 2 , are linearly independent over F 2 . Hence, to prove that the R x (i) are (w/D)-wise independent with high probability over the choice of the x (i) , it suffices to prove that any size-(w/D) subset of the vectors (x (i) 2,2 ) i≤N is linearly independent over F 2 . We now bound the probability, over the random choice of x

2 , that all (w/D)-tuples of vectors x (i) 2,2 are linearly independent over F 2 . First, let us compute the probability that (w/D) random vectors sampled from F w 2 are linearly independent: the probability that the first vector is linearly dependent is 1/2 w (this is the probability that it is the all-zero vector); the probability that the second vector linearly depends on the first one is 1/2 w-1 , and by induction, the probability that the j-th vector linearly depends on the (j -1)-th first vectors is 1 -1/2 w-j+1 . Hence, the overall probability that a random (w/D)-tuple of vector is linearly independent is

Then, we conjecture that the following holds:

a large enough w, and any vector v ∈ F N 2 with hamming weight between 2 i-1 and 2 i . The probability, over the sampling of M 1 , • • • , M w from M i par , that less than w/2 of the M j 's are very good against v is at most 2 -w•2 i-1 .

The above can be formulated as a balls and bins experiment: consider an experiment where one throws t balls into 2 i bins at random, and declares "success" if the fraction of bins with an odd number of balls at the end of the experiment is between 1/3 and 2/3. Then, the above conjecture states that when t ∈ [2 i-1 , 2 i ], if one repeats this experiment w times, the probability that less than w/2 of them are successful is at most 2 -w•2 i-1 . We view experimentally validating or disproving this conjecture as an important direction toward understanding the concrete resistance of VDLPN against linear attacks.

Furthermore, if the above conjecture holds, then it implies in particular (by plugging this into the proof of resistance against linear attacks) that with probability at least 2 -w/2+log w-2 over the sampling of a random VDLPN matrix H with parameters (w, w/4, 2 w/4 ), the distribution of samples has bias at most (1/2) • (2/3) w/2 . Hence, the computational cost of a linear attack against VDLPN parameters, if the conjecture is true, is expected to require about (N/2)•(2/3) w/2 boolean operations.

As a concrete example of a choice of parameters according to the above analysis, we suggest the following as a natural target for cryptanalysis: set w = 120 and D = 30. Is it possible to break VDLPN, with N = 2 30 , using less than 2 80 boolean operations?

A Restriction-Based Linear Attack. Any learning algorithms for the class of sparse polynomials over F 2 with random samples break the security of the proposed WPRF candidates. For example, our first candidate can be viewed as a wD-sparse polynomial over the variables z i,j,h = x i,j,h ⊕k i,j,h , and a learning algorithm with random samples clearly distinguishes between our candidate and a random function. Both Bshouty [START_REF] Bshouty | Pac learning sparse polynomials[END_REF] and Hellerstein and Servidio [START_REF] Hellerstein | On PAC learning algorithms for rich boolean function classes[END_REF] proposed such algorithms. The first algorithm [START_REF] Bshouty | Pac learning sparse polynomials[END_REF] works for uniformly chosen samples, and directly learns the polynomial labeling the samples. Since it hasn't been published we provide a description below. The second algorithm [START_REF] Hellerstein | On PAC learning algorithms for rich boolean function classes[END_REF] is a PAC-learning algorithm, i.e. works over any distribution of the samples, and learns the polynomial via intermediate representations of the function as a generalized decision tree and a generalized decision list.

Both algorithms learn sparse polynomials with Õ(2 √ n ) samples and running time and can be viewed in our context as linear attacks. These algorithms show that our second candidate achieves optimal security against linear attacks in an asymptotic sense.

For the restriction algorithm in [START_REF] Bshouty | Pac learning sparse polynomials[END_REF] use the following notation. Let P be a multivariate polynomial over F 2 with n variables x = (x 1 , . . . , x n ) and k monomials, and let σ = log 2 kn. View P as a sum P (x) = Q(x) + R(x), such that Q(x) includes all monomials of degree at most √ n and R(x) all the other monomials. The algorithm begins by choosing a random subset i 1 , . . . , i σ √ n ∈ {1, . . . , n}, and then analyzing O(2 2σ √ n ) samples (y, P (y), where y = (y 1 , . . . , y n ) is an assignment to x. Let Y include all the samples that satisfy y i j = 0 for all j = 1, . . . , σ √ n. With high probability, there are O(2 σ √ n ) such samples. Let M be some monomial in R. Partition the σ √ n indices into σ sequences I 1 , . . . , I σ of √ n indices each. Then, the probability that none of the variables in M has an index in I j is at most

. Therefore, the probability that M does not have an index in {I 1 , . . . , I j } is at most e -σ implying that M (y) = 0 with probability at most e -σ for any y ∈ Y . Since R has at most k monomials it follows by union bound that Pr[R(y) = 0] ≤ e log kn which is negligible.

Except with negligible probability, P (y) = Q(y) for all y ∈ Y . Since Q is of degree √ n it can be completely learned via linearization given O( n √ n ) samples. Since with high probability Protocol Π Y corr * Initialization. On input 1 λ proceed as follows:

• The parties call F PCF.Gen , where F PCF.Gen is the ideal functionality which samples keys (k 0 , k 1 ) $ ← PCF.Gen(1 λ ) and returns k σ to P σ .

Invocation. On input x ∈ {0, 1} n(λ) proceed as follows:

• P σ outputs y σ ← PCF.Eval(σ, k σ , x). and main candidate, respectively. Based on the performance of AES on a single core of a modern CPU, we expect the computational efficiency of the second variant of the PCF can be as high as 10-20 thousand evaluations per second, and this easily scales with multiple cores. We can also obtain a PCF for OT with roughly the same costs, using the binary form of the WPRF and the optimized PCF from Remark 5.6.

Applications

In this section we motivate the PCF primitive and our constructions by discussing a number of cryptographic applications. At a high level, the power of PCF stems from enabling two parties -at the cost of a one-time distributed setup -to locally generate an effectively unbounded amount of correlated randomness. Correlated randomness is a valuable resource, as in many contexts it gives rise to information-theoretic security and attractive efficiency features. While the information-theoretic security feature is lost when applying a PCF, the efficiency features remain. We discuss several concrete use-cases below.

Secure Multiparty Computation with Fully Reusable Preprocessing

We first turn our attention to secure multiparty computation (MPC), where two or more parties want to securely evaluate a public function on their private inputs, such that the parties learn the function output and nothing beyond this output. Security is typically defined by considering an external adversary who may corrupt a strict subset of the parties. MPC with no honest majority, where the adversary can corrupt any number of parties, is impossible to realize in general with information-theoretic security. This applies in particular to the two-party case. However, MPC with no honest majority can be realized with information-theoretic security given suitable sources of secret correlated randomness, with good concrete efficiency. The most basic notion of correlated randomness in the setting of secure computation are OT correlations, which in fact are sufficient for the secure computation of general functionalities [GMW87,Kil88,IPS08].

In the following we extend the result of [BCG + 19b] to PCFs, showing that PCFs can be used as a plug-in replacement to the pre-processing phase in protocols consuming correlated randomness that allow corrupted parties to influence their share of the correlated randomness. This includes most MPC protocols from the literature, and in concretely efficient protocols such as [BDOZ11, DPSZ12, NNOB12, WRK17a, WRK17b]. We first show the applicability of PCFs in the two-party setting, and then consider applications in multi-party setting in Section 10.5.

More formally, a PCF can be used used (as depicted in protocol Π Y corr * , Figure 12) to securely realize a corruptible functionality F Y corr * (see Figure 13) for the ideal generation of correlated randomness.

Homomorphic Secret Sharing for Constant-Degree Polynomials

Homomorphic secret sharing (HSS) [START_REF] Boyle | Breaking the circuit size barrier for secure computation under DDH[END_REF] is the dual notion to function secret sharing, allowing two (or more) parties to locally evaluate a public function on secret-shared inputs. HSS has many applications, including succinct secure computation in which communication complexity is smaller than the circuit size. It was observed in [BCG + 19b] that a PCG for constant-degree correlations yields a homomorphic secret sharing scheme to evaluate arbitrary constant-degree polynomials. We extend their result as follows:

• The homomorphic secret sharing scheme can build on reusable setup, thereby significantly reducing the cost for sharing an input value.

• The computation time for every evaluation scales in the number of variables and number of terms of the polynomial only (instead of scaling with the number of all possible degree-d terms).

Consider two parties who wish to compute shares of p(x) for some public multivariate polynomial p(X 1 , . . . , X m ) over some ring R, given shares of x = (x 1 , . . . , x m ) ∈ R m . Given a wPRF-based universal PCF for degree-d correlations (as given in Section 6.4 for the case of R = F 2 ), we construct a public-key homomorphic secret sharing scheme with reusable setup HSS = (HSS.Gen, HSS.Share, HSS.Eval) for arbitrary degree-d polynomials as follows.

• HSS.Setup(1 λ ): Generate PCF keys (k 0 , k 1 ) ← PCF.Gen(1 λ ) and let K the corresponding weak PRF key.

, and a degree-d multivariate polynomial p, compute a share p σ of the polynomial p satisfying p (X) = p(X -R), where R = (F K (ρ 1 ), . . . , F K (ρ m )). Note that the coefficients of p are public degree ≤ d polynomials in R, hence shares of the coefficients can be locally computed via the PCF evaluation algorithm. Output p σ (y) = ρ σ (x).

Correctness and security follow from the properties of the underlying PCF.

Programmable PCFs with Applications to MPC with M ≥ 3 parties

In order for a broader range of applications -that is, for example using PCFs to achieve secure computation in the multi-user setting with online communication linear in the number of users -we require the PCF to additionally satisfy programmability, which basically allows the parties to reuse their inputs across different PCF instantiations (compare [BCG + 19b]). Note that similar to the basic construction of PCG for OT in [BCG + 19b], our standard PCF for OT does not support reusability of inputs, because the sender message pairs are implicitly defined by the receiver's choice bits. But, building on the universal PCF for degree-2 correlations (see Figure 10), we will present a programmable PCF for OT in this section.

In order to define the notion of programmability formally, we first recall the definition of a simple bilinear correlation. For this we consider G 1 , G 2 , G T groups and e : G 1 × G 2 → G T be a bilinear map. Note that the size of the groups will for some applications depend on the security parameters, which will be implicit in the following.

Note that any bilinear correlation is reverse sampleable. This includes most of the commonly used correlations such as OT and OLE. For example, OT can be obtained with G 1 = G 2 = G T = ({0, 1}, ⊕) and e(x, y) = x • y Also, note that two independent bilinear correlations can be locally converted to produce an additively secret-shared instance of the correlation -for example, two OLEs can be locally converted to one multiplication triple.

Multi-Party PCF for simple bilinear correlation

• PCF M .Gen(1 λ ) :

1. Sample random ρ 0,1 , . . . , ρ 0,M $ ← {0, 1} λ , ρ 1,1 , . . . , ρ 1,M $ ← {0, 1} λ as specified by programmability property.

For every

1. For every j = i, compute

where [i < j] = 1 if i < j and 0 if j < i. Our approach closely follows [BCG + 19b], who gave a similar transformation for the context of PCGs. But, due to the fact that PCGs are inherently limited to polynomial stretch, in their case the communication complexity of setup scaled in O(M 2 s ε ) for a constant ε. In particular, for their approach an upper bound on the circuit size had to be known at the time of setup. PCFs, on the other hand, allow secure computation with linear communication after a fullyreusable one-time setup. Note that traditional approaches with linear online communication complexity even require an offline communication of O(M 2 s) [FH96, CDN01, DPSZ12].

In the following we present a generic transformation from any programmable PCF for a simple bilinear correlation to a M -party PCF for the corresponding multi-party correlation. For a formal definition of multi-party PCFs, we refer to Appendix D. We omit the proof as it is straightforward.

Theorem 10.6 (Multi-party simple bilinear PCF) Let PCF = (PCF.Gen, PCF.Eval) be a PCF with reusable inputs for Y e (specified by e : G 1 × G 2 → G T ) with key sizes s 0 (λ), s 1 (λ) and let PRF be a weak PRF. Then the PCF M = (PCF M .Gen, PCF M .Eval) as defined in Figure 15 is a PCF for the corresponding M -party correlation Y M,e with the following properties.

• PCF M .Gen(1 λ ) runs M (M -1) executions of PCF.Gen; each output key k i , i ∈ [M ], has size (M -1)(s 0 (λ) + s 1 (λ) + λ) bits.

• PCF M .Eval(i, k i , x) runs 2(M -1) executions of PCF.Eval and makes (M -1) evaluations of PRF.

Appendix A Pseudorandom Correlation Generators

In the following we recall the definition of a pseudorandom correlation generator from [BCG + 19b].

Definition A.1 (Correlation generator) A PPT algorithm C is called a correlation generator, if C on input 1 λ outputs a pair of elements in {0, 1} N (λ) × {0, 1} N (λ) , where N (λ) ≤ poly(λ).

Definition A.2 (Reverse-sampleable correlation generator) Let C be a correlation generator. We say C is reverse sampleable if there exists a PPT algorithm RSample that on input

such that for σ ∈ {0, 1} the correlation obtained via:

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

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

• PCG.Expand(σ, k σ ) is a polynomial-time algorithm that on input σ ∈ {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:

is computationally indistinguishable from C(1 λ ).

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

where RSample is the reverse sampling algorithm for correlation C.

Exp pr A,N,0 (λ) : mk ← Setup(1 λ ) for i = 1 to N (λ):

(y

for σ ∈ {0, 1}:

B Full PCF Definition

In this section we give the full definition of pseudorandom corelation functions for a correlation with setup. Further, we define a non-adaptive PCF, where the adversary is only allowed nonadaptive queries. This definition turns out to be useful, as it is easier to instantiate than a PCF with strong security, but still sufficient for most applications.

Definition B.1 (Reverse-sampleable correlation with setup) Let 0 (λ), 1 (λ) ≤ poly(λ) be output length functions. Let (Setup, Y) be a tuple of probabilistic algorithms, such that Setup on input 1 λ returns a master key mk and Y on input 1 λ and mk returns a pair of outputs (y 0 , y 1 ) ∈ {0, 1} 0 (λ) × {0, 1} 1 (λ) .

We say that the tuple (Setup, Y) defines a reverse sampleable correlation with setup, if there exists a probabilistic polynomial time algorithm RSample that takes as input 1 λ , mk, σ ∈ {0, 1} and y σ ∈ {0, 1} σ (λ) , and outputs y 1-σ ∈ {0, 1} 1-σ (λ) , such that for all mk, mk in the image of Setup and all σ ∈ {0, 1} the following distributions are statistically close:

Definition B.2 (Pseudorandom correlation function (PCF))

Let (Setup, Y) fix a reversesampleable correlation with setup which has 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 );

• 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} σ (λ) .

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

for all sufficiently large λ, where Exp pr A,N,b (λ) for b ∈ {0, 1} is as defined in Figure 16. (In particular, where the adversary is given access to N (λ) samples.)

Exp s-pr

A (λ) :

return (y 0 , y 1 ) else:

for all sufficiently large λ, where Exp s-pr A (λ) is as defined in Figure 18.

• Strong security. For all σ ∈ {0, 1} and non-uniform adversaries A of size B(λ) asking at most N (λ) queries to the oracle O b (•), it holds

for all sufficiently large λ, where Exp s-sec A,σ (λ) for b ∈ {0, 1} is as defined in Figure 19.

Exp na-pr

A,N,0 (λ) : • Pseudorandom correlated outputs with non-adaptive queries. For σ ∈ {0, 1} and non-uniform adversary A = (A 0 , A 1 ) of size B(λ), it holds

Pr[Exp na-pr A=(A 0 ,A 1 ),N,0 (λ) = 1] -Pr[Exp na-pr A=(A 0 ,A 1 ),N,1 (λ) = 1] ≤ ε(λ) for all sufficiently large λ, where Exp s-pr A,N,b (λ) for b ∈ {0, 1} is as defined in Figure 20.

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

for all sufficiently large λ, where Exp na-sec A,N,σ,b (λ) for b ∈ {0, 1} is as defined in Figure 21.

C Programmable PCF for VOLE from WPRF and FSS

Lemma C.1 The PCF construction for VOLE from Figure 22 supports reusable inputs.

Proof.

[Sketch] Indistinguishability is immediate. Programmibility follows with f 0 (ρ 0 , x) = ρ 0 and f 1 (ρ 1 , x) = F ρ 1 (x). Finally, security follows from the security of FSS, similar to the proof of Theorem 5.3.

D Multi-Party PCFs

Definition D.1 (Reverse-sampleable multi-user correlation with setup) Let 1 (λ), . . . , M (λ) ≤ poly(λ) be output length functions. Let (Setup, Y) be a tuple of probabilistic algorithms, such that Setup on input 1 λ returns a master key mk and Y on input 1 λ and mk returns outputs

We say that the tuple (Setup, Y) defines a reverse sampleable M -user correlation with setup, if there exists a probabilistic polynomial time algorithm RSample that takes as input 1 λ , mk, T ⊂ {1, . . . , M } and (y i ) i∈T , and outputs (y j ) j / ∈T , such that for all mk, mk in the image of Setup and all σ ∈ {0, 1} the following distributions are statistically close: • PCF.Gen(1 λ ) is a probabilistic polynomial time algorithm that on input 1 λ , outputs a pair of keys (k 1 , . . . , k M );

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

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

Programmable PCF for VOLE

Let F = {F k : {0, 1} n → R} k∈{0,1} λ be a weak PRF, and FSS = (FSS.Gen, FSS.Eval) an FSS scheme for {cF k } c∈R,k∈{0,1} λ with weak pseudorandom outputs. Let further

PCF.Gen(1 λ ; ρ 0 , ρ 1 ):

1. Set the weak-PRF key k ← ρ 0 and a ← ρ 1 .

2. Sample a pair of FSS keys K fss 0 , K fss 1 ← FSS.Gen(1 λ , aF k ). 3. Output the keys k 0 = (K fss 0 , a) and k 1 = (K fss 1 , k).

PCF.Eval(σ, k σ , x): On input a random x:

• If σ = 0:

1. Let c 0 = -FSS.Eval(0, K fss 0 , x). 2. Output (a, c 0 ).

• If σ = 1:

3. Output (b, c 1 ).

Exp M-pr

A,N,0 (λ) : mk ← Setup(1 λ ) for i = 1 to N (λ):

x (i) $ ← {0, 1} n(λ) (y

M ) ← Y(1 λ , mk) b ← A(1 λ , (x (i) , y

Exp M-sec

A,N,σ,0,T (λ) : (k 1 , . . . , k M ) ← PCF.Gen(1 λ ) for i = 1 to N (λ):

x (i) $ ← {0, 1} n(λ) ∀j / ∈ T : y (i) j ← PCF.Eval(j, k j , x (i) ) b ← A(1 λ , T, (k j ) j∈T , (x (i) , (y

A,N,σ,1,T (λ) : (k 1 , . . . , k M ) ← PCF.Gen(1 λ ) mk $ ← Setup(1 λ ) for i = 1 to N (λ):

x (i) $ ← {0, 1} n(λ) ∀j ∈ T : y