arXiv CSopen access

Distributed Point Functions and Function Secret Sharing

1

Distributed Point Functions and Function Secret Sharing Elette Boyle (Senior Member, IEEE), Niv Gilboa, Yuval Ishai, and Peter Scholl (Member, IEEE)

arXiv:2607.27696v1 [cs.CR] 30 Jul 2026

Abstract—A distributed point function (DPF) is a cryptographic primitive that enables compressed additive sharing of a secret weight-1 vector (equivalently, a point function) across two or more parties. The appealing lightweight structure of DPF constructions has enabled a wide range of applications. These include private information retrieval, anonymous messaging, secure computation with preprocessing, and pseudorandom correlation generators for expanding small correlated seeds into large pseudorandom instances of cryptographic correlations. In this article, we survey definitions, constructions, and applications of DPFs. We also discuss the extension of DPF to function secret sharing (FSS), which generalizes point functions to support richer function classes. Efficient FSS schemes yield a similar generalization for most of the applications of DPFs.

I. I NTRODUCTION Secret sharing is a central tool in cryptography. In its simplest form, a secret-sharing scheme splits a secret s into a random pair of shares (s0 , s1 ) such that s0 + s1 = s. This kind of additive secret sharing is typically done over a finite Abelian group G. In this case, each share perfectly hides s ∈ G if we pick s0 uniformly at random from G and let s1 = s−s0 . Considering additive sharing over GN , we can similarly split a secret vector s ∈ GN into a pair of uniformly random share vectors (s0 , s1 ) such that s = s0 + s1 . Can we compress the secret shares s0 , s1 of a long vector s while still ensuring that each individual share hide s? If we insist on perfect hiding, then the above solution can be easily shown to be optimal: namely, each share must be uniformly random and therefore cannot be compressed. However, if we settle for computational hiding and assume the existence of a pseudorandom generator (PRG), or equivalently a one-way function [1], then a limited amount of compression becomes possible. Letting r be a seed for a PRG G that stretches a random λ-bit seed r to a pseudorandom element of GN , where λ ≪ N , we can split s ∈ GN into (r, s − G(r)). By locally expanding the first share to G(r), we obtain additive secret-sharing of s with computational (rather than perfect) secrecy. This can make the first share much shorter than s, but (inevitably) yields at most a 2x reduction in the total share size, since the two shares together should allow recovering s. For general s, the required description size—and thus combined secret share size—must necessarily be at least N ⌈log |G|⌉ bits. E. Boyle is with the Cryptography and Information Security (CIS) Lab at NTT Research, Sunnyvale (e-mail: [email protected]). N. Gilboa is with the Faculty of Computer and Information Sciences, Ben Gurion University, Be’er Sheva, Israel (e-mail: [email protected]). Y. Ishai is with the Department of Computer Science, Technion Institute of Technology, Haifa, Israel, currently on a sabbatical at AWS, New York. Supported by ISF grant 3527/24 and BSF grant 2022370. This article is not associated with Amazon. (e-mail: [email protected]). P. Scholl is with the Department of Computer Science, Aarhus University, Aarhus, Denmark (e-mail: [email protected]).

Function secret sharing (FSS). The barrier for compressing the shares of a general long vector s is its large description size. But what if s is taken from a small set of vectors, so that s has a short description? For example, suppose the entries sx of s, for x ∈ [N ], are given by an efficiently computable function f (x) = sx , whose description size is much smaller than the size of s. In this case, we can hope to “split” s into two compressed shares, describing functions f0 and f1 , for which sx = f (x) = f0 (x) + f1 (x) for each x ∈ [N ], and where the description of each fi on its own computationally hides f from within the class. This is precisely the notion of function secret sharing (FSS) [2]. Distributed point functions (DPF). It turns out that many cryptographic applications of FSS apply to functions with a small number of nonzero outputs. Such an FSS scheme provides a compressed additive secret-sharing of sparse vectors s. In the extreme version, s contains at most one nonzero entry. Providing efficient, compressed secret shares of such a “onehot vector” is captured by the notion of a distributed point function (DPF) [3], [4], which will serve as the core focus of this article. A. DPF Definition It will be useful to consider the case where N = 2n and view a maximally-sparse vector s ∈ GN as the truth-table of a point function fα,β : {0, 1}n → G defined by ( β if x = α fα,β (x) = 0 if x ̸= α. The above functional view allows us to consider efficient random access to an output of a point function with an exponential input domain size N . This is enabled by allowing a succinct representation of the additive shares of fα,β by a pair of keys (k0 , k1 ), generated by an efficient randomized key generation algorithm Gen(1λ , α, β), where λ is a security parameter (typically λ = 128 in practice). Random access to the additive shares of fα,β (x) is enabled by another efficient algorithm Eval(i, ki , x), where i ∈ {0, 1} is the key identity. This DPF syntax naturally gives rise to the following correctness and security requirements: • Correctness: For any input x, the reconstruction of the shares yields the function value: Eval(0, k0 , x) + Eval(1, k1 , x) = fα,β (x) •

Security: A single key ki reveals essentially nothing about the secret index α or the output value β, in the sense that for any two pairs (α, β) and (α′ , β ′ ), the corresponding keys ki and ki′ are computationally indistinguishable.

2

It is convenient to view the keys (k0 , k1 ) as succinctly representing additive function shares (f0 , f1 ), such that f0 + f1 = fα,β and each fi computationally hides fα,β . B. Known Bounds on DPF Key Size A trivial DPF construction that provides perfect (rather than computational) security is to additively share the truth-table of fα,β . This yields a DPF in which each key contains N = 2n group elements. It turns out that significantly improving over this bound is impossible in the information-theoretic setting, and moreover implies a PRG in the computational security setting [3]. Perhaps more surprisingly, a PRG is also sufficient for exponential compression. Concretely, using a PRG with a λ-bit seed, the best known DPF construction has keys of size ≈ n · λ + log |G| bits [4]. Construction at a glance. The state-of-the-art PRG-based DPF construction [4] uses additive secret sharing over F2 , where a bit-string s is split into two random strings whose XOR is s. It employs two simple ideas. First, additive secret sharing is linearly homomorphic. This implies that parties can locally add public corrections to shared values conditioned on shared control bits, viewing them as F2 -affine functions of the shared bits. Second, in the two-party case, equal PRG seeds expand to equal strings, which cancel under XOR, while independent seeds expand to pseudorandom-looking shares. The tree-based DPF combines these ideas level by level: all paths away from the secret point are forced to cancel, while the unique path to the secret point keeps independent pseudorandom seeds until a final correction installs the payload β. See Section III-A for more details. C. Application: PIR by Keywords To give a simple example for the usefulness of DPFs, consider the following keyword-search variant of 2-server private information retrieval (PIR) [5], [6], [7]. There are two servers S0 and S1 who each hold a database D of keywords xj ∈ {0, 1}n (e.g., hashes of breached passwords). A client, holding a search word α ∈ {0, 1}n , wants to learn whether α ∈ D without revealing α to any server and while minimizing communication cost. A DPF gives rise to the following simple solution: The client views its search query as a point function fα,β : {0, 1}n → Z2 , where α is the secret search word and β = 1. The client then uses Gen to split fα,β into additive shares fα,β = f0 + f1 , sending the corresponding keys P to the two servers. Each server i uses Eval to compute xj ∈D fi (xj ), returning the one-bit sum yi ∈ Z2 to the client. The client concludes that α ∈ D if y0 +y1 = 1, and that α ̸∈ D otherwise. Note that the above application crucially relies on the additive representation of the output shares produced by Eval to aggregate the shared outputs over many inputs xi . This application also demonstrates the importance of the random access provided by Eval. When n is large, as in the breached passwords example, scaling linearly with the domain size N = 2n would be infeasible. We will later see additional applications of DPF that benefit from the above features.

D. Multi-Party DPF DPF can also be generalized from two parties to m ≥ 3 parties. The efficiency landscape depends strongly on the corruption threshold t. In the full-threshold setting, t = m − 1, security requires that any strict subset of the m keys hide the point function. This is the natural analogue of two-party DPF security, but it is much less well understood: the best known PRG/OWF-based constructions have square-root dependence on the domain size [2], [8], and beating this barrier is open even for three parties. A different and more efficient regime is obtained when there is a gap between the number of parties and the corruption threshold, namely t < m−1. In this setting one can sometimes obtain the stronger notion of multiplicative DPF, where the output shares support local multiplication of several DPF outputs [9], [10]. More precisely, an (m, t)-multiplicative DPF supports local evaluation of polynomials of degree ⌊(m−1)/t⌋ in the shared DPF outputs; for t = 1 this gives degree m − 1. Finally, in honest-majority-like regimes there are nontrivial information-theoretic multi-party DPF constructions, discussed in Section III-E. Section III-B gives a more detailed comparison of the full-threshold, gapped-threshold, and multiplicative multi-party settings. E. Function Secret Sharing As mentioned above, a powerful generalization of DPF considers additively sharing functions f from an arbitrary function class F, rather than just point functions. This is referred to as a function secret sharing (FSS) scheme for F [2]. FSS schemes can naturally extend the functionality of most DPF applications. For example, in the above keyword search example, if we interpret each keyword as an n-bit integer, then FSS for the class of intervals (namely, functions that return 1 on an interval [a, b] and 0 elsewhere) can be used to privately search for a database entry containing a number in a secret interval. While for this simple class F an efficient PRG-based FSS scheme is known [4], [11], extending this to more general classes is a challenging open problem. Such extensions are known under different assumptions that imply public-key cryptography [2], [12], [13], [14], [15], [16], [17], [18], though the resulting FSS schemes are typically much worse than PRG-based FSS in terms of concrete efficiency. We will discuss the general landscape of known FSS constructions in Section III-F. F. Homomorphic Secret Sharing When considering FSS schemes for rich function classes, it is often useful to reverse the role of the function f and the input x. This is captured by the notion of homomorphic secret sharing (HSS) [19], [12], [20]. In an HSS scheme, a secret input x is split between two or more parties, such that additive shares of f (x) can be locally computed from the shares of x for any (publicly known) function f ∈ F . This dual form of FSS is more useful for some applications, and can be viewed as a natural distributed analogue of fully homomorphic encryption.

3

G. Pseudorandom Correlation Generators Finally, an increasingly popular application of DPFs is for compressing useful sources of correlated randomness. Consider first the simple case of encryption. Using a trusted dealer that distributes to a sender P0 and a receiver P1 the same secret random string R ∈ {0, 1}N , we enable P0 to securely communicate a message M ∈ {0, 1}N to P1 by sending M ⊕R over a public channel. Settling for computational security, this simple two-party correlation can be compressed by having the dealer send to both parties a short PRG seed s, which can be expanded to R. But what if we consider more general two-party correlations, such as ones that can be used for secure two-party computation? For example, we can consider an ideal target correlation (R0 , R1 ) consisting of N independent instances of random oblivious transfer (OT), where for each instance R0 includes a pair of random bits and R1 includes a random selection of one of these bits. Can we securely compress such a two-party correlation by having the dealer generate a pair of short correlated seeds (s0 , s1 ) that can be locally expanded into outputs that are indistinguishable from the target correlation? Note that here security means that knowing one seed si does not reveal more information than is implied by the target correlation. In the random OT example, this means that s0 should hide the selections of P1 , and s1 should hide the bits of R0 that were not selected. This type of compression is captured by the notion of a pseudorandom correlation generator (PCG) [21], [17]. It turns out that DPFs can be used to build practical PCGs for useful correlations, including the above random OT correlation, based on different flavors of the learning parity with noise (LPN) assumption. The high level idea is to use DPF for compressing a variant of the correlation that involves sparse random vectors, and then use a public linear mapping to convert the sparse correlation into a pseudorandom correlation. See Section IV-E for further discussion of the current landscape of PCG constructions. H. Organization This survey provides an introduction to distributed point functions and related primitives, as well as an overview of the state of the art within this research domain. Section II establishes the formal definitions and security models. Section III discusses constructions of DPFs and their variants. Section IV discusses different applications of DPFs in cryptography and beyond. Finally, Section V presents a collection of open problems in the area. Table I gives a high-level map of the FSS landscape, including the general FSS abstraction, common concrete function classes that instantiate it, and related primitives, such as HSS and PCGs.

then discuss useful extensions, including variants with more than two parties; programmable DPF, where one key can be generated before the secret point function is selected; and extractable DPF, providing tighter guarantees on the wellformedness of DPF keys. Notation and algebraic conventions. We use λ for the security parameter throughout, and write probabilities as Pr[·]. All output groups are Abelian and written additively unless stated otherwise. Thus 0 denotes the identity element and −a denotes the additive inverse of a. We write + for the general group operation and reserve ⊕ for bitwise XOR over groups such as Zℓ2 . A ring R is a set equipped with addition and multiplication, such as Zq . An R-module is the analogue of a vector space in which scalars come from R rather than necessarily from a field. ForP example, Zdq is a module over Zq . Thus an expression such as i αi gi (x) means that coefficients αi ∈ R multiply public values gi (x) in an R-module, and the results are added using the module addition. A. Function Secret Sharing We follow the definition of function secret sharing (FSS) from [4]. Intuitively, a (2-party) FSS scheme is an efficient algorithm that splits a function f ∈ F into two additive shares f0 , f1 , such that: (1) each fi hides f beyond some allowable leakage information Leak(f ); and (2) for every input x, f0 (x) + f1 (x) = f (x). The main challenge is to make the descriptions of f0 and f1 compact, while still allowing their efficient evaluation. Definition 2.1 (FSS: Syntax): A (2-party) function secret sharing (FSS) scheme is a pair of algorithms (Gen, Eval) such that: λ • Gen(1 , f ) is a PPT key-generation algorithm that given security parameter 1λ and description of a function f ∈ {0, 1}∗ outputs a pair of keys (k0 , k1 ). We assume that f explicitly contains descriptions of input and output groups Gin , Gout of f : Gin → Gout . • Eval(i, ki , x) is a polynomial-time evaluation algorithm that given party index i ∈ {0, 1}, key ki (defining fi : Gin → Gout ), and input x ∈ Gin outputs a group element yi ∈ Gout (the value of fi (x)). Definition 2.2 (FSS: Correctness and Security): Let F be a function family and Leak be a function specifying the allowable leakage about f ∈ F. When Leak is omitted, it is understood to output only a description of Gin and Gout . We say that (Gen, Eval) as in Definition 2.1 is an FSS scheme for F (with respect to leakage Leak) if it satisfies the following requirements. • Correctness: For all f ∈ F describing f : Gin → Gout , and every x ∈ Gin , if (k0 , k1 ) ← Gen(1λ , f ), then Pr [Eval(0, k0 , x) + Eval(1, k1 , x) = f (x)] = 1.

II. D EFINITIONS We begin by giving a formal definition of two-party function secret sharing (FSS). We then zoom into the corresponding special case of two-party distributed point functions (DPF), which serves as the predominant focus of this survey. We

•

Security: For each i ∈ {0, 1}, there is a PPT algorithm Simi (simulator), such that for every sequence (fλ )λ∈N of polynomial-size function descriptions from F, the outputs of the following experiments Real and Ideal are computationally indistinguishable:

4

TABLE I H IGH - LEVEL MAP OF THE FSS LANDSCAPE . E FFICIENT DPF, DCF, DMPF, M ULTIPLICATIVE DPF, AND VERIFIABLE / EXTRACTABLE DPF EXIST FROM ANY PSEUDORANDOM GENERATOR (PRG). G ENERAL FSS, OFFSET- FUNCTION FSS, HSS, PCG/PCF S EXIST FROM A RANGE OF ASSUMPTIONS , DEPENDING ON THE COMPLEXITY OF FUNCTIONS SUPPORTED . M ANY USEFUL EFFICIENT PCG S RELY ON THE L EARNING PARITY WITH N OISE (LPN) ASSUMPTION AND VARIANTS . Primitive / notion

Secret object

Reconstruction (input x)

Core technique

Representative uses

General FSS notion FSS for function class F (§II-A)

A secret function f ∈ F

Additive shares of f (x) for each public input x

Key generation splits f into compact function shares f0 , f1 such that f0 (x) + f1 (x) = f (x), while each key hides f up to allowed leakage

Generic abstraction for private evaluation of secret-shared functions; specialized efficient schemes exploit the structure of F

Additive shares of fα,β (x)

PRG tree with level-by-level correction words; off-path branches cancel Prefix-DPF structure or optimized tree-based comparison construction

PIR, private writes, histograms, equality tests Range queries, interval functions, comparisons in secure computation Pseudorandom correlation generators, unbalanced PSI, sparse-vector sharing Conjunctive queries, low-depth products of DPF outputs, unit-vector correlations

Examples of FSS function classes and variants DPF (§II-B, III-A) Point function fα,β , equivalently a weight-one vector fα,β (α) = β < DCF (§II-C, III-C) Comparison function fα,β , where < fα,β (x) = β for x < α

< Additive shares of fα,β (x)

Multi-point (sparse) function fA,B , with up to t nonzero points (t is revealed) Point function, but where output shares support local multiplication (requiring gap between corruption threshold and number of servers) Offset gate function for public gate g and secret masks rin , rout : grin ,rout (x̂) = g(x̂ − rin ) + rout

Additive shares of fA,B (x)

Additive shares of the masked gate output

FSS for structured offset classes induced by equality, comparison, truncation, ReLU, splines, and related gates

Secure computation with preprocessing, secure mixed-mode computation, private ML inference

Secret input x evaluated under a public function f

Additive or structured shares of f (x)

Dual view of FSS: the input is secret-shared and the function is public

PCG / PCF (§I-G, IV-E)

Large correlated randomness expanded from short correlated seeds

Verifiable / extractable DPF (§IV-C)

A well-formed point function, even against maliciously generated keys

Local expansion to correlated outputs such as Oblivious Transfer (OT), or Beaver triples Additive shares plus a validity or extractability guarantee

DPF/DMPF sharing of sparse errors followed by public linear maps from LPN-style assumptions; PCFs give a function-like analogue Arithmetic sketching, hash-based consistency checks, or random oracle-based extractability of the DPF tree

Secure computation, public-key-style FSS, richer function classes Silent OT extension, Beaver triples, preprocessing for secure computation

DMPF (§II-C, III-D)

Multiplicative DPF (§II-C, III-B)

Offset-function FSS (§IV-D)

Related concepts HSS (§I-F, III-F)

Multiplicative secret sharing, followed by additive reconstruction of products

– Realλ : (k0 , k1 ) ← Gen(1λ , fλ ); Output ki . – Idealλ : Output Simi (1λ , Leak(fλ )). Simulation vs. indistinguishability security. In contrast to the simulation-based security requirement above, the original FSS definition from [2] was formulated as a semanticsecurity notion of indistinguishability. Namely, security required that for each party i ∈ {0, 1}, for any two sequences (fλ )λ∈N , (fλ′ )λ∈N of polynomial-size function descriptions from F , then party i’s key share ki as generated from (k0 , k1 ) ← Gen(1λ , fλ ) is indistinguishable from its key as generated from (k0 , k1 ) ← Gen(1λ , fλ′ ). Interestingly, the two flavors of definition are equivalent for any function family F and leakage function Leak for which Leak can be efficiently inverted. More concretely, suppose given Leak(f ) one can efficiently find f ′ ∈ F such that Leak(f ′ ) = Leak(f ). Then the required simulator Simi (1λ , z = Leak(fλ )) can be attained by choosing an arbitrary fλ′ ∈ F for which Leak(fλ′ ) = z, honestly generating keys (k0′ , k1′ ) ← Gen(1λ , fλ′ ), and outputting the corresponding key ki′ as its simulation. If the FSS scheme has indistinguishability security, then this simulated key ki′ is indistinguishable from the true key ki generated from fλ , as desired. In the other direction, the simulation requirement

Sum of DPFs; big-state DPF; probabilistic batch codes; OKVS encodings Tree-based DPF combined with CNF, replicated, or Shamir-style output sharing

Malicious-client private aggregation, heavy hitters, anonymous messaging

automatically implies indistinguishability of party i’s key from any choice of secret function f with the same value of Leak(f ). Such an inversion algorithm exists for all instances of F and Leak considered in this survey—including distributed point functions and extensions—and essentially all from the literature. Post-quantum security. While in this survey we focus on classical security, one can naturally consider FSS with postquantum security. Almost all of the constructions we discuss (with the exception of group-based FSS schemes discussed in Section III-F) are plausibly post-quantum secure. B. Distributed Point Function We next give a formal definition of distributed point functions (DPF), as formulated in [4]. Roughly speaking, DPF is an instance of function secret sharing as in the previous section, for the class F of point functions, and with Leak(f ) revealing the input and output space of the corresponding point function f. Definition 2.3 (Point Functions): A point function fα,β , for α ∈ {0, 1}n and β ∈ G, is defined to be the function f : {0, 1}n → G such that f (α) = β and f (x) = 0 for x ̸= α. Here, 0 represents the identity of the abelian group G.

5

Definition 2.4 (DPF): A (2-party) distributed point function (DPF) scheme is a pair of efficient algorithms (Gen, Eval) with the following syntax: λ • Gen(1 , fα,β ) is a key generation algorithm that given security parameter 1λ and description of a point function fα,β : {0, 1}n → G outputs a pair of keys (k0 , k1 ). We assume that fα,β explicitly contains the input length n and the output group G. • Eval(i, ki , x) is an evaluation algorithm that given party index i ∈ {0, 1}, key ki , and x ∈ {0, 1}n in the domain of fα,β , outputs a group element yi ∈ G. The algorithms (Gen, Eval) should satisfy the following two properties: n • Correctness: For every fα,β : {0, 1} → G and input n x ∈ {0, 1} , if (k0 , k1 ) ← Gen(1λ , fα,β ) then the corresponding evaluated output shares satisfy: Pr [Eval(0, k0 , x) + Eval(1, k1 , x) = f (x)] = 1. •

Security: For every i∗ ∈ {0, 1}, there exists a PPT algorithm Sim (simulator), such that for every polynomialsize point function fα,β , the outputs of the following experiments Real and Ideal are computationally indistinguishable: – Real(1λ ): (k0 , k1 ) ← Gen(1λ , fα,β ); Output ki∗ . – Ideal(1λ ): Output Sim(1λ , (1n , G)).

Additional syntax. Besides the usual Gen and Eval algorithms, DPF schemes are sometimes equipped with the following additional syntax, for use in applications: λ • DistGen(1 , fα,β ): A distributed key generation protocol, which securely realizes the functionality that takes from P0 and P1 shares of α, β as inputs, evaluates Gen(1λ , fα,β ), and outputs key ki to party Pi . We will give examples of such protocols in Section IV-A. • FullEval(i, ki ): A full-domain evaluation algorithm that given a party index i ∈ {0, 1} and key ki , outputs a vector of group elements (yix )x∈{0,1}n s.t. y0x + y1x = f (x) for all x ∈ {0, 1}n . It can be seen as an enhanced form of the Eval algorithm which, instead of evaluating at a chosen input x ∈ {0, 1}n , evaluates at all inputs in {0, 1}n . This algorithm is feasible only when the DPF has polynomialsize input domain, and is beneficial whenever there is a way to amortize the costs of multiple Eval instances. In the usual client-generated PDF setting, Gen is run locally by a client who knows (α, β). By contrast, DistGen is needed when α and/or β are themselves secret-shared among parties. This is the case, for example, when jointly generating seeds of a pseudorandom correlation generator (PCG), or performing secure computation of RAM programs [22]. In such case, the parties must run an interactive secure protocol for the relevant Gen functionality. A generic secure computation of the Gen circuit is possible, but is usually unattractive because it is non-black-box in the underlying cryptographic tools (e.g., pseudorandom generators). Section IV-A discusses the standard black-box alternative based on local PRG calls and oblivious transfer. Full-domain evaluation is useful for applications such as private information retrieval, where the domain size N = 2n

corresponds to the (polynomial-size) database size, and secret shares of the full expanded unit vector are required for functionality. For the tree-based DPF construction, FullEval expands the full construction tree once and costs O(N ) PRG calls plus O(N ) output writes; it can be implemented with O(N ) memory if all leaves are materialized, or with small working memory if leaves are streamed. This is in contrast to N individual calls to Eval, which would require larger cost O(N log N ). C. Extensions Beyond 2-Party DPF The above definition of 2-party DPF can be generalized in several orthogonal ways. This includes, in particular: • To m > 2 parties: FSS, including DPF, can be generalized to m ≥ 2 parties with t < m corruptions, where security requires that any subset of t keys reveal no information beyond the specified leakage Leak(f ). • Non-additive reconstruction: The additive reconstruction property Eval(0, k0 , x) + Eval(1, k1 , x) = f (x) of FSS (more generally, its linear structure) is what enables many of its applications. Linearity of reconstruction provides convenient shareP compressibility; for example, P x∈S Eval(0, k0 , x) and x∈S Eval(1, k1 , x) automatiP cally form shares of x∈S f (x). Further, output shares must themselves be elements of the function output space, immediately guaranteeing share succinctness. Nontrivial notions of FSS can be considered with relaxed requirements on reconstruction, which may suffice for certain applications. For example, a natural requirement is that the output length of Eval is short, depending only on the output length of f and not on the input length of f . We refer the reader to [2], [20] for a formal treatment of these and further extensions. In this survey, we consider only additive reconstruction. We will focus predominantly on the two-party setting, addressing the case with more parties only briefly (see Section III-B). And, we will mostly consider the case of DPF as well as the following highly related variants. Distributed Comparison Function (DCF). A DCF is an FSS < for the class of comparison functions fα,β : {0, 1}n → G, < n where α ∈ {0, 1} , β ∈ G, and fα,β (x) = β for x < α and 0 ∈ G for x ≥ α (where ordering on {0, 1}n is given by integer interpretation, i.e., the bit-string 0n , corresponding to the integer 0, is the smallest element and the bit-string 1n , corresponding to the integer 2n − 1, is the largest element). We discuss constructions of DCF in Section III. Distributed Multi-Point Functions (DMPF). Many applications of DPF (e.g., for constructions of pseudorandom correlation generators as in Section IV-E) require compressed shares of a sparse weight-t vector. This corresponds to secret shares of a t-point function in the place of a (weight-1) point function. Formally, a t-point function fA,B : {0, 1}n → G for A = {α1 , · · · αt } ⊂ {0, 1}n listed in ascending order and B = (β1 , · · · , βt ) ∈ Gt evaluates to βi on input αi for 1 ≤ i ≤ t and to 0 on all other inputs. We denote by

6

multi-point functions the collection of all t-point functions for all t. A Distributed Multi-Point Function (DMPF) is an FSS scheme for this function class with leakage function Leak(fA,B ) = (1n , G, t). In particular, the FSS keys are allowed to reveal a bound on the weight t, and the complexity of the scheme is allowed to grow with t. Multiplicative DPF. A natural variant of DPF, considered in [9], [10], is (m, t)-multiplicative DPF. Here, the output group G is the additive group of a commutative ring R, and the outputs of Eval on input x are an (m, t)-multiplicative secret sharing of the desired point function evaluation value fα,β (x). Security requires that any subset of t FSS keys reveals no information about fα,β beyond Leak(fα,β ). The multiplicative output sharing allows the parties to compute any polynomial of degree at most ⌊(m − 1)/t⌋ in the shared DPF output by local computation on their shares. In particular, when t = 1, this degree is m − 1. III. C ONSTRUCTIONS In this section, we address known constructions of FSS schemes, focusing on DPF. We begin with a detailed treatment of the best current construction of two-party DPF (Section III-A) and related extensions: multi-party DPF (Section III-B), distributed comparison functions (DCF; Section III-C), distributed multi-point functions (DMPF; Section III-D), and information-theoretic DPF (Section III-E). We then conclude with a general overview of known FSS constructions for different function classes (Section III-F). A. Constructing DPF In this section, we describe the state-of-the-art constructions of distributed point function (DPF) and distributed comparison function (DCF) from any pseudorandom generator (PRG). We refer the reader also to [23] for a video lecture covering these constructions as an additional resource. 1) DPF Warmup: Building Blocks and Square-Root DPF: To illustrate the ideas behind the two-party DPF construction, consider the following intuition. All constructions are based on two simple building blocks. The first is additive secret sharing, which takes a secret over an Abelian group and splits it into two random group elements that add up to the secret. In our case, the Abelian group will typically be of the form Zℓ2 , namely the set of ℓ-bit strings with the XOR operation. We view the secret as being split between two parties and denote the pair of shares of a secret s ∈ {0, 1}ℓ by [s] = (s0 , s1 ). The second building block is a PRG G that stretches a λ-bit random seed to a pseudorandom string of polynomial length ℓ(λ) ≫ λ. Now, let’s consider the following basic question: Which kinds of homomorphic operations can we perform on an additively shared secret s ∈ {0, 1}ℓ ? More concretely, for which functions f can the parties locally convert [s] into [f (s)] without knowing s? We have two simple kinds of homomorphisms: 1) Additive secret sharing is linearly homomorphic: If [s] = (s0 , s1 ) are additive shares of s then A · [s] = (A · s0 , A ·

s1 ) are additive shares of As. A useful corollary is the following conditional correction gadget: given additive shares [s], [t] of a string s ∈ {0, 1}ℓ and a “control bit” t ∈ {0, 1}, along with a public correction word CW ∈ {0, 1}ℓ , the parties can locally compute [s′ ] for s′ = s + t · CW . We view this as a conditional correction of the secret s by CW conditioned on t = 1. 2) In the 2-party case, additive secret sharing satisfies the following weak homomorphism: If G : {0, 1}λ → {0, 1}ℓ is a PRG, then G([s]) = (G(s0 ), G(s1 )) extends shares of the 0-string s = 0λ into shares of a longer 0string s′ = 0ℓ , and shares of a random string s ∈ {0, 1}λ into shares of a longer (pseudo-)random string s′ , where s′ is pseudo-random even given one share of s. Jumping ahead, the fact that the second homomorphism only applies to the 2-party case explains why the best known DPF constructions do not extend beyond two parties. Armed with the above two types of homomorphism, we are ready to describe a simple “square-root DPF” construction, in which the key size scales linearly with the square-root of the input domain size N = 2n . This DPF is implicit in the 2server PIR scheme of Chor and Gilboa [7]. The construction is shown in Fig 1. Consider a DPF with input domain [N ], where N = ℓ2 , and output group Z2 . We can view the two keys as defining additive shares of a vector u ∈ ZN 2 such that uα = β and uα′ = 0 for all α′ ̸= α. Folding u into an ℓ × ℓ matrix M , coordinate α in u belongs to some row i ∈ [ℓ] of M ; all other rows of M contain only zeros. As a first step, we generate compressed additive shares of a related matrix M ′ , which is similar to M except that row i is pseudorandom. This is done by choosing an independent PRG seed sj ∈ {0, 1}λ for each row j ̸= i of M ′ , and two independent seeds si0 , si1 for row i. Now, letting each DPF key kb include the ℓ seeds sjb , where for j ̸= i we have sjb = sj , we can apply the PRGbased homomorphism to each row, locally expanding the keys (k0 , k1 ) into additive shares [M ′ ] as above. As the second and final step, we need to correct row i of M ′ to match row i of M . To this end, we exploit the linear homomorphism of the additive sharing of M ′ and apply the above correction gadget: for each row of M ′ we add to the keys a secret-shared control bit, which is 1 for row i and 0 for all other rows. Finally, we add a public correction word CW ∈ {0, 1}ℓ to correct row i of M ′ to match row i in M . All in all, each augmented key includes (λ + 1) ·√ ℓ secret bits, along with an ℓ-bit public√correction. Since ℓ = N , the key size scales linearly with N . Looking at the structure of the two keys, they are identical except in the length-λ part that corresponds to row i. Thus, we can view the non-public part of these keys as an additively shared point function over G = Zλ2 . This suggests the possibility of further compressing the non-public part via the use of recursion. In the following section, we describe a treebased approach which is loosely based on this idea. 2) Tree-Based DPF: In this section we describe the stateof-the-art PRG-based DPF construction from [4]. Unlike the previous square-root construction, here the key size scales logarithmically with the domain size N , namely linearly in

7

k0

k1

[tj ]

M = M0 ⊕ M1 col 1 · · · col j

Row 1:

Row i:

Row ℓ:

1

s

=

1

s

[0]

0

.. .

.. .

.. .

.. .

.. .

si0

̸=

si1

[1]

.. .

.. .

.. .

.. .

.. .

sℓ

=

sℓ

[0]

0

PRG expand + correct

0

···

0

∗

(ℓ × ℓ) ···

col ℓ

···

0

.. . ···

β

.. . ···

.. . ···

0

same seeds ⇒ zero row

0

indep. seeds + CW correction

.. . ···

0

same seeds ⇒ zero row

CW = G(si0 ) ⊕ G(si1 ) ⊕ (0, . . . , β, . . . , 0) Fig. 1. Square-root DPF construction for input domain [N ] with N = ℓ2 . Left: The two DPF keys (k0 , k1 ). Each key contains ℓ PRG seeds (one per matrix row) and secret-shared control bits [tj ]. For rows j ̸= i, both keys share the same seed sj ; for the special row i (containing target α), the keys hold independent seeds si0 ̸= si1 . A public correction word CW is included in both keys. Right: The reconstructed ℓ × ℓ matrix M = M0 ⊕ M1 . Shared seeds yield identical PRG outputs, so their XOR produces zero rows. Row i expands to √ a pseudorandom row, corrected via CW conditioned on [ti ] = [1] to place β at column j ∗ (the position of α within row i). Key size: (λ + 1) · ℓ + ℓ = O( N ).

the input length n. The parameters of this construction are captured by the following theorem. Theorem 3.1 (Tree-based two-party DPF): Suppose G : {0, 1}λ → {0, 1}2(λ+1) is a pseudorandom generator. Then the scheme (Gen• , Eval• ) from Figure 3 is a DPF for the family of point functions fα,β : {0, 1}n → G with key size n·(λ+2)+λ+⌈log2 |G|⌉ bits. The number of PRG invocations |G| in Gen is at most 2(n + ⌈ log λ+2 ⌉) and the number of PRG |G| invocations in Eval is at most n + ⌈ log λ+2 ⌉. Intuition. We now give a high-level description of the treebased construction, which provides intuition for the more formal description that will follow. For simplicity, consider first the case of a DPF with a single-bit output β = 1. At a high level, each of the two keys defines a GGM-style binary tree [24] with 2n leaves, where the leaves are labeled by inputs x ∈ {0, 1}n . We will refer to a path from the root to a leaf labeled by x as the evaluation path of x, and to the evaluation path of the special input α as the special evaluation path. Each node v in a tree will be labeled by a string of length λ + 1, consisting of a control bit t and a λ-bit seed s, where the label of each node is fully determined by the label of its parent. The function Eval• will compute the labels of all nodes on the evaluation path to the input x, using the root label as the key, and output the control bit of the leaf. We would like to maintain the invariant that for each node outside the special path, the two labels (on the two trees) are identical, and for each node on the special path the two control bits are different and the two seeds are indistinguishable from being random and independent. Note that since the label of a node is determined by that of its parent, if this invariant is met for a node outside the special path then it is automatically maintained by its children. Also, we can easily meet the invariant for the root (which is always on the special path) by just explicitly including the labels in the keys. The challenge is to ensure that the invariant is maintained also when leaving the special path.

Towards describing the construction, it is convenient to view the two labels of a node as a mod-2 additive secret sharing of its label, consisting of shares [t] = (t0 , t1 ) of the control bit t and shares [s] = (s0 , s1 ) of the λ-bit seed s. That is, t = t0 ⊕ t1 and s = s0 ⊕ s1 . The construction employs the same two types of homomorphism of additive secret sharing used in the square-root construction: namely, linear homomorphism that allows for conditional correction and PRG-based homomorphism [s′ ] = G([s]) mapping a shared s = 0λ to a longer shared s′ = 0m and random s ∈ {0, 1}λ to a longer pseudorandom s′ . To maintain the above invariant along the evaluation path, we use the two types of homomorphism as follows. Suppose that the labels of the i-th node vi on the evaluation path are [s], [t]. To compute the labels of the (i + 1)-th node, the parties start by locally computing [S] = G([s]) for a PRG G : {0, 1}λ → {0, 1}2λ+2 , parsing [S] as [sL , tL , sR , tR ]. The first two values correspond to labels of the left child and the last two values correspond to labels of the right child. To maintain the invariant, the keys will include a correction word CW for each level i. As discussed above, we only need to consider the case where vi is on the special path. By the invariant we have t = 1, in which case the correction will be applied. Suppose without loss of generality that αi = 1. This means that the left child of vi is off the special path whereas the right child is on the special path. To ensure that the invariant is maintained, we can include in both keys the correction CW (i) = (sL , tL , sR ⊕s′ , tR ⊕1) for a random seed s′ . Indeed, this ensures that after the correction is applied, the labels of the left and right child are [0], [0] and [s′ ], [1] as required. But since we do not need to control the value of s′ , except for making it pseudo-random, we can instead use the correction CW (i) = (sL , tL , sL , tR ⊕ 1) that can be described using λ + 2 bits. This corresponds to s′ = sL ⊕ sR . The n correction values CW (i) are computed by Gen• from the root labels by applying the above iterative computation along the special path, and are included in both keys.

8

Level i−1 (on-path) (i−1)

Gen: Correction word (here αi = 1, so Keep=R, Lose=L)

sb (i−1) tb

(i−1)

PRG (i−1)

G(sb →

CW CW

)

L R R ) → sL b ∥tb ∥sb ∥tb for b = 0, 1.
L L = t ⊕ t , tR ⊕ t R ⊕ 1 | {z } |0 {z 1} |0 {z1 }

Expand: G(sb (i)

(i)

L sL 0 ⊕ s1 , sCW

tR CW

L R R sL b ∥tb ∥sb ∥tb (i−1)

Apply correction: ⊕ tb

· CW (i)

Eval: Party b’s update (selects right/Keep child) (i)

(i−1)

sb = sR b ⊕ tb Left

tL CW

(i)

(i−1)

tb = t R b ⊕ tb

· sCW ,

· tR CW

Right (αi = 1)

Left/Lose child (not selected, off-path) (i−1)

Lose: off-path

Keep: on-path

L L L s̃L 0 ⊕ s̃1 = (s0 ⊕ s1 ) ⊕ (t0 | {z } | differ

Labels identical: L L L s̃L 0 = s̃1 , t̃0 = t̃1

Invariant preserved: (i) (i) t0 ⊕ t1 = 1 (i) (i) s0 , s1 indep. pseudorandom

(i−1)

⊕t {z 1

=1

) · sCW = 0 } | {z } L = sL 0 ⊕s1

L L L L L t̃L 0 ⊕ t̃1 = (t0 ⊕ t1 ) ⊕ 1 · (t0 ⊕ t1 ) = 0

Parties agree on all off-path nodes ⇒ these cancel in output.

(i−1)

Fig. 2. Illustration of a single level in the tree-based DPF, shown for αi = 1 (right = Keep, left = Lose). The parent on-path node holds seeds sb with (i−1) (i−1) t0 ⊕ t1 = 1. After PRG expansion and conditional correction, the right/Keep child preserves the invariant (differing control bits, independent seeds), while the left/Lose child’s labels become identical across both parties. The case αi = 0 is symmetric (left = Keep, right = Lose).

Finally, assuming that β = 1, the output of Eval• is just the shares [t] of the leaf corresponding to x. A different value of β (from an arbitrary Abelian group) can be handled via an additional correction CW (n+1) . The formal construction. A full description of the construction that follows the above blueprint and is used for proving Theorem 3.1 is given in Figure 3. The core idea for how the tree is defined at each level during key generation and evaluation is depicted in Fig. 2. B. Multi-Party DPF A natural generalization of two-party DPF is multi-party DPF, in which a dealer distributes the keys to m parties with 1 ≤ t < m corruptions. We refer to schemes with these parameters as (m, t)-DPF. Multi-party DPF schemes were constructed in three regimes for the number of corrupt parties. The first regime is t = 1, and the performance measures of known schemes [9], [10] in this regime roughly match the performance of the 2-party scheme in Figure 3. These multiparty schemes have the additional benefit that the output is shared in a multiplicative secret sharing, allowing the computation of a circuit with low multiplicative depth on the output without interaction. In the second regime, t = m − 1, i.e., the adversary controls all but one of the parties. In this regime, the best known schemes with security from one-way functions [2], [8] are similar to the square root scheme in Section III-A with key size and evaluation time that are proportional to a square root of the domain size. In the final regime, 1 < t < m/2, or more precisely m = td + 1 for d > 1. In this regime, the most efficient scheme [9] composes a DPF for full threshold with an information-theoretically secure DPF to achieve key size and evaluation time that are proportional to 2n/(2d) .

Multiplicative DPF. The following theorem summarizes the current state of the art for (m, 1)-DPF, in which the output is shared in a multiplicative sharing, e.g. CNF secret sharing [25] or Shamir secret sharing [26]. This type of secret sharing enables computing a polynomial of degree m−1 on the secret by manipulating the secret shares locally without interaction. Theorem 3.2: Suppose G is a pseudorandom generator with seed length λ, let G be a group and let the number of parties be m > 2. Then, there exists an (m, 1) DPF scheme for the family of point functions fα,β : {0, 1}n → G with output that is a CNF secret shared over G with threshold 1 and key size per party that is O(mn(λ + log m) + m2 log |G|). When only additive reconstruction is needed, it suffices for G to be an Abelian group. When the CNF-shared output is used for multiplication, e.g., via conversion into Shamir shares [27], the group G should be viewed as the additive group of a commutative ring, and the local products are taken in that ring. A scheme that satisfies Theorem 3.2 is constructed in [10]. This scheme follows the general tree structure of the twoparty scheme from Section III-A2 with two main differences. Each level of the tree is associated with roughly m different correction words and a node in the tree holds both a seed for the PRG and an ID of one of the correction words. The evaluation procedure ensures that in any node of the tree, which is not on the path to α, the seeds and IDs of all m parties are identical. In any node of the tree, which is on the path to α, the seeds are drawn independently from a pseudorandom distribution and all the IDs of correction words are distinct. Maintaining this invariant in the leaves ensures that by stretching the final seeds to a length of m − 1 group elements in G, and with correction words of appropriate size, the parties can output shares in a replicated, or CNF, secret

9

Optimized Distributed Point Function (Gen• , Eval• ) Let G : {0, 1}λ → {0, 1}2(λ+1) be a pseudorandom generator. Let ConvertG : {0, 1}λ → G be a map converting a random λ-bit string to a pseudorandom group element of G. Gen• (1λ , α, β, G): 1: Let α = α1 , . . . , αn ∈ {0, 1}n be the bit decomposition of α (0) (0) 2: Sample random s0 ← {0, 1}λ and s1 ← {0, 1}λ (0) (0) 3: Let t0 = 0 and t1 = 1 4: for i = 1 to n do (i−1) R R L L sR sR 5: sL ) and sL 0 ||t0 ← G(s0 1 ||t1 ← 0 ||t0 1 ||t1 (i−1) G(s1 ). 6: if αi = 0 then Keep ← L, Lose ← R 7: else Keep ← R, Lose ← L 8: end if 9: sCW ← sLose ⊕ sLose 0 1 L L R R R 10: tCW ← t0 ⊕ tL 1 ⊕ αi ⊕ 1 and tCW ← t0 ⊕ t1 ⊕ αi (i) L R 11: CW ← sCW ||tCW ||tCW (i) (i−1) 12: sb ← sKeep ⊕ tb · sCW for b = 0, 1 b (i) (i−1) 13: tb ← tKeep ⊕ t · tKeep CW for b = 0, 1 b b 14: end for  n (n) 15: CW (n+1) ← (−1)t1 · β − Convert(s0 ) +  (n) Convert(s1 ) ∈ G (0) 16: Let kb = sb ||CW (1) || · · · ||CW (n+1) 17: return (k0 , k1 ) Eval• (b, kb , x): 1: Parse kb = s(0) ||CW (1) || · · · ||CW (n+1) , and let t(0) = b. 2: for i = 1 to n do R 3: Parse CW (i) = sCW ||tL CW ||t  CW L  (i) (i−1) (i−1) 4: τ ← G(s ) ⊕ (t · sCW ||tCW ||sCW ||tR CW ) 5: Parse τ (i) = sL ||tL sR ||tR ∈ {0, 1}2(λ+1) 6: if xi = 0 then s(i) ← sL , t(i) ← tL 7: else s(i) ← sR , t(i) ← tR 8: end if 9: end for   10: return (−1)b · Convert(s(n) ) + t(n) · CW (n+1) ∈ G Fig. 3. Pseudocode for optimized DPF construction for the class fα,β : {0, 1}n → G. The symbol || denotes string concatenation. Subscripts 0 and 1 refer to party id. All s values are λ-bit strings and t values are a single bit.

sharing scheme of β in the point α and of 0 in every other point α ̸= x ∈ {0, 1}n . If G is a ring then CNF secret sharing enables non-interactive computation of shares of polynomials of degree at most m−1 over the ring. If G is a field F, |F| > m, then there is a procedure to first locally transform the CNF shares into Shamir shares [27] and then compute polynomials of degree at most m − 1 over F. Multi-party DPF with many corruptions. In the regime of t > 1, the schemes are significantly less efficient. The reason for this, which was already mentioned in Section III-A1, is that two-party constructions encode a zero bit by parties holding identical seeds. Obtaining multiple encoded zero bits from a singled encoded zero bit is possible non-interactively by locally stretching the identical seeds to longer identical strings.

However, in the multi-party setting, one cannot take such a direct approach with identical seeds, as an adversary that controls two or more parties can determine if they share a zero bit. In the full threshold regime, i.e. t = m − 1, the two state of the art constructions [2], [8] achieve a square-root scheme, improving over the trivial information-theoretic approach, but leaving a large gap in performance between 2-party and multiparty schemes. Both constructions also place restrictions on the output group. Theorem 3.3 summarizes the results of the multi-party scheme from [2]. Theorem 3.3: Suppose G : {0, 1}λ → {0, 1}2λ is a pseudorandom generator, let G = F2 and let the number of parties be m > 2. Then, there exists an (m, m − 1) DPF scheme for the family of point functions fα,β : {0, 1}n → G with output that is a additively shared over G and key size per party that is 2⌈n/2⌉ · 2⌈(m−2)/2⌉ λ(1 + o(1)). The general structure of the construction is similar to the square-root DPF in Section III-A1, where the domain {0, 1}n is viewed as a matrix of roughly equal dimensions. There exist a unique row α1 and a unique column α2 in this matrix that correspond to the special input α ∈ {0, 1}n . The main difference between the two schemes is in the distribution pattern of the PRG seeds. The m-party scheme of [2] samples 2m−1 independent seeds for each row of the matrix that represents the domain {0, 1}n . In every row that does not contain α, the Gen procedure selects one seed sS for every subset S ⊆ [m] of even size and provides it to all parties i ∈ S. In α1 , the critical row that contains α, Gen provides one fresh seed sS ′ for every subset S ′ ⊆ [m] of parties of odd size. Eval expands every seed to the length of the row. In all non-critical rows the sum of expanded strings over G = F2 is 0, while in the critical row the sum of strings is some pseudo random v. Gen also chooses a correction word cw such that v⊕cw = eα2 , i.e. a unit vector with 1 at α2 and zero anywhere else. Gen also provides an additive secret sharing over F2 of a control bit per row, which is 1 in α1 and 0 anywhere else. Eval completes its operation after expanding the seeds and computing the sum of all the expanded strings by adding the product of the public correction word and the share of the control bit associated with the evaluated row. Security is ensured due to two properties. First, the view of the distribution of the seeds, given m − 1 of the parties, is identical for the row that contains α and for every other row. Second, the party that is not corrupted by the adversary receives one seed that no other party has. Therefore, since the value of the correction word is cw = v ⊕ eα2 , and v is the sum of all the expanded seeds, the correction word is computationally indistinguishable from random for the adversary. The above description slightly differs from the scheme in [2] since it uses a single correction word instead of 2m−1 correction words. This allows, through a careful balancing of the number of rows and columns of the domain matrix, to reduce the dependence of the key size on the number of parties from about 2m to roughly 2m/2 . Remark 3.4: The output group can be generalized to Zp for any small prime p at the cost of increasing the key size by

10

a multiplicative factor of O (p/2)m/2 . Generalization of the output group to Zk for a smooth integer k with distinct prime factors is straightforward via the Chinese Remainder Theorem. The authors of [8] set out to improve the exponential dependence in key size (and evaluation time) on the number of parties in the above construction. The following theorem presents the main result. Theorem 3.5: Suppose G : {0, 1}λ → {0, 1}2λ is a pseudorandom generator, let G = Zpq for a prime p and integer q and let the number of parties be m > 2. Then, there exists an (m, m − 1) DPF scheme for the family of point functions fα,β : {0, 1}n → G with output that is additively shared over G and key size per party that is poly(m, λ) · 2n/2 . This work first shows that any seed distribution pattern which is deterministic and has the following three properties must have exponential size: (1) Any seed in a non-critical row must be used an even number of times by all the parties together, (2) Each party receives a unique seed for the critical row, and (3) The distribution of seeds is identical between the critical row and other rows. As a corollary, the seed distribution scheme in [2] is optimal if these properties are met. On the other hand, [8] shows that a randomized pattern for seed distribution can have a polynomial number of seeds per party. In more detail, Gen distributes the same seed to a random pairs of parties (including a pair of seeds to the same party) for every row. Gen distributes b additional seeds, one seed per party, in the critical row. This type of approach satisfies the first two desired properties of the seed distribution. By a careful choice of a, b, the statistical distance between the distribution of the critical row and a non-critical row is inverse-polynomial (although non-negligible). The final step is a local privacy amplification step proposed in [28] via Locally Decodable Codes, achieving negligible distinguishing advantage. Other components of the construction, such as the correction word and the control bits, are copied from [2] without impacting the asymptotic key size. Leveraging multiplicativity for better DPF key size. In the final regime, m = td + 1 for some d > 1. [9] proposes a construction in this regime with properties that are summarized in Theorem 3.6. Theorem 3.6: Suppose G : {0, 1}λ → {0, 1}2λ is a pseudorandom generator, let G = F2 , let d, t > 1 and let the number of parties be m = dt + 1. Then, there exists an (m, t) DPF scheme for the family of point functions fα,β : {0, 1}n → G with output that is additively shared over  G and key size per n/2d mt /2 t party that is O 2 ·2 · m dλ . The scheme uses two ideas: the DPF scheme with security against all but one corrupt parties from [2] and the multiplicative property of CNF secret sharing. In more detail, the scheme views the domain {0, 1}n as a d-dimensional cube with each side of length 2n/d . If α =Q(α1 , . . . , αd ) in this cube, then the d goal is to compute fα1 ,β ·
i=2 fαi ,1 . Let (Gen′ , Eval′ ) be the m ′ DPF scheme for m = t parties with threshold t′ = m′ − 1. For each point function fαi ,· , Gen runs Gen′ (αi , ·). Each of the m′ “virtual” parties is associated with a subset of size t out of the m real parties. A real party receives all the keys of subsets to which it does not belong. Therefore, a subset of t

real parties misses one key, ensuring security. Eval(x) works in two steps. If the coordinates of x are (x1 , . . . , xd ), then Eval first runs Eval′ on every xi that the party holds. Now, the parties hold secret shares of fαi ,· (xi ) for i = 1, . . . , d. More precisely, the parties hold (m′ , d) CNF shares of each fαi ,· (xi ). In the second step of Eval, the parties exploit the multiplicative property of CNF sharing Qd to non-interactively compute additive shares of fα1 ,β · i=2 fαi ,1 , which is β if x = α and is 0 if x ̸= α. C. Extending to Distributed Comparison Functions (DCF) Recall that a DCF is an FSS for the class of comparison < functions fα,β : {0, 1}n → G, where α ∈ {0, 1}n , β ∈ G, < and fα,β (x) = β for x < α and 0 ∈ G for x ≥ α. Here we view x = x1 . . . xn and α = α1 . . . αn as representing n-bit integers, where x1 and α1 are the most significant bits. A natural question is whether we can use any DPF construction to obtain a DCF. This turns out to be indeed possible, though with a multiplicative overhead of n. Indeed, x < α if and only if (1) x1 < α1 or (2) x1 = α1 and x2 < α2 or (3) x1 x2 = α1 α2 and x3 < α3 , ..., or (n): x1 x2 . . . xn−1 = α1 α2 . . . αn−1 and xn < αn . Rewriting condition (i) as x1 x2 . . . xi 1 = α1 α2 . . . αi−1 0αi , and noticing that the n conditions are mutually exclusive, we can write < fα,β (x) =

n X

fαi ,β (xi )

(1)

i=1

for αi = α1 α2 . . . αi−1 0αi and xi = x1 x2 . . . xi 1. This generically reduces DCF to n instances of DPF. Can we do better? It turns out that the tree-based construction of DPF from Section III-A2 can be converted into a DCF with a very small overhead. In fact, the DPF key for fα,β can < also serve as a DCF key for fα,β in the useful case where G = Z2 and β = 1. This follows from the fact that the treebased DPF construction effectively generates not only additive shares of fα,β , but also additive shares of fα′ ,β for every prefix α′ of α. This implies that each term fαi ,β (xi ) from Eq. (1) can be evaluated locally from the DPF keys: If xi = 1, the term is 0 can be omitted from the summation. If xi = 0, then we can write this term as fα′ ,β (x1 . . . xi−1 1) where α′ is the length-i prefix of α. To handle the case of a general output group G and payload β, it suffices to augment the tree-based DPF so that every intermediate level is also treated as the final output level, yielding the prefix-DPF instances fα′ ,β required by the above construction. This involves roughly n · log |G| extra correction bits in each key. Finally, we note that two instances of DCF can be used for a distributed interval function, which evaluates to β on a secret interval [a, b] and to 0 elsewhere. D. Extending to Distributed Multi-Point Functions (DMPF) Many applications of DPF, such as their use within constructions of efficient pseudorandom correlation generators discussed in Section IV-E, actually require a compressed secret sharing of a (sparse) weight-t vector. This corresponds to

11

a distributed multi-point function (DMPF), where the secret function fA,B : {0, 1}n → G has up to t nonzero outputs for some public parameter t (see notation in Section II-C). In what follows, we provide a brief overview of existing DMPF constructions. Naı̈ve DMPF. In its simplest form, an additively shared vector of weight ≤ t can be obtained by adding together t additively shared vectors of weight ≤ 1. In turn, one can build t-DMPF via t independent copies of standard DPF, resulting in ×t cost in all metrics. • “Big-state” DMPF [29]. One can generalize the indicator bit in the standard tree-based DPF construction from [4] (Section III-A2) to an indicator t-bit string, which identifies multiple nonzero entries of the shared vector. The construction maintains the invariant that for a node in the tree lying on the kth accepting path in the depth-i level, its indicator string is the one-hot encoding of k, namely ek = 0k−1 ||1||0t−k ∈ {0, 1}t . This enables the parties to (unknowingly) perform different conditional corrections for t positions in each layer. To achieve this, each level of the tree will contain t sets of correction words, each containing λ + 2t bits. Each set will be used in an analogous manner to the standard tree-based construction. Namely, at each node of evaluation in the tree, and for every ℓ ∈ [t], each party will conditionally XOR in the ℓth correction word information, based on the value of the ℓth bit of its local indicator string. The costs of the big-state DMPF scheme grow quickly (quadratically) with the vector weight t; however, this construction typically outperforms the full-domain evaluation costs of competing approaches for small weights in the range 3 ≤ t ≤ 70. • DMPF from batch codes. DMPF construction with better asymptotic efficiency can be obtained from a probabilistic batch code (PBC) [30], [21], [31], [32], [33], [34]. A batch code [35], [36] is a distributed encoding scheme that allows a large database to be distributed across ℓ servers such that any “batch” of t database symbols can be retrieved by reading one symbol from each server. The goal is to minimize the total storage requirements, using ℓ > t servers to beat the simple solution of duplicating the database across all servers. Here we consider PBC, a probabilistic variant of batch codes, where the encoding replicates each database symbol among a set of servers using a probabilistic replication pattern. Efficient constructions of PBC can be based on cuckoo hashing [30], [21], [31], [37]. When applied to FSS for multi-point functions, a PBC reduces the task of building a weight-t DMPF on domain size 2n = N (the large database size), to ℓ > t separate weight-1 DPF instances, each with domain size < N . The batch code provides a mapping between positions of the ℓ short DPF vectors to positions of the original lengthN vector, so that each of the N positions is covered at least once, and the following combinatorial property is satisfied: For any subset of t positions within the length

•

N vector, there exists a choice of (at most) one entry from each of the ℓ vectors, which covers these t items. The key size of the DMPF scales with the number of PBC servers ℓ, and the full evaluation time scales with the total storage. The latter can get close to 2N in a cuckoo hashing based PBC. • OKVS-based DMPF. The final class of DMPF constructions we discuss rely on oblivious key-value stores (OKVS), originally proposed as a data structure supporting efficient private set intersection (PSI) protocols [38]. Improved OKVS constructions were given in [39], [40]. OKVS can be used as a method to encode specific positions in the binary tree (the “keys”) paired up with specific pieces of information needed for correction (the “values”), and these encodings can be given in the DMPF keys. An OKVS abstracts and generalizes the concept of polynomial interpolation, enabling higher concrete efficiency. The key size, key generation time and evaluation time of the corresponding OKVS-based DMPF are closely related to the OKVS instantiation. A simple polynomial-based OKVS can be used to provide improvements over naı̈ve DMPF [29], [41]. By applying the “random bands” RBOKVS construction of [40], one obtains a DMPF scheme with fastest evaluation time for a wide range of practically useful parameters [29]. Comparison of approaches. The best choice of DMPF varies strongly based on parameter regimes, with each of the four constructions outperforming others within some region. For example, based on experimental results from [29], the optimal DMPF construction in terms of minimal FullEval time is largely independent of the choice of the domain size 2n = N , and varies for different ranges of t as follows: • Naı̈ve DMPF: For t ≤ 2 • Big-state DMPF: For 3 ≤ t ≤ 70 4 • OKVS-based DMPF: For 70 < t < 10 • PBC-based DMPF: Comparable to OKVS starting at t ≥ 104 , and best starting around t ≈ 21,000. For the case of single-evaluation Eval, the picture is similar, but with an earlier switch between the big-state and OKVS (roughly t = 9 in the place of t = 70). We remark that each of the dominating regimes constitute an important range for applications. For example, the bigstate DMPF is a good fit for use in state-of-the-art PCG implementations [33] and other applications of DMPF that require small values of t. OKVS-based and PBC-based DMPF constructions provide improved running times for applications such as unbalanced PSI in the 2-server model, considered in [42]. Here a client wants to find the intersection of its set of t keywords (each of length n) with a potentially big (or even “streaming”) set of keywords held by two remote servers. E. Information-Theoretic DPF Nontrivial m-party DPF constructions are possible even in the information-theoretic setting, where each t keys perfectly hide the point function, provided that security threshold t satisfies t < m/2.

12

Such DPF constructions are closely related to protocols for information-theoretic private information retrieval (PIR) [5]. The first generation of such schemes were based on ReedMuller codes, and could achieve communication complexity N 1/Θ(m) . As it turns out, for m ≥ 3 these schemes imply information-theoretic DPF schemes with similar key size. Theorem 3.7 (Reed-Muller DPF, implicit in [5]): Let p ≥ 2 be a prime and m ≥ 2 an integer. There exists a perfectly secure m-party DPF, for point functions with input domain [N ] and output group Zp , where each key is of size O(m log m log(p) · N 1/(m−1) ). The above can be extended to larger security thresholds t ≥ 2, scaling m by roughly a factor of t. Subsequent information-theoretic PIR schemes [43], [44], [45], [46] improved the communication complexity to N o(1) with as few as 2 servers. These 2-server PIR schemes have the two servers output additive shares of a vector of length N o(1) , whose inner product with a secret linear combination vector known to the PIR client yields the output. By doubling the number of servers, we can ensure that each answer is known to two servers, and have the client share its linear combination vector between each pair of servers. This results in a 4-server PIR scheme with additive reconstruction, which given known 2-server PIR schemes yields the following. Theorem 3.8 (Perfectly secure 4-DPF [47]): Let p ≥ 3 be prime and s ≥ 1. There is a perfectly secure 4-party DPF (t = 1) with output group Zps , domain size N , and key size   √ O s log(p) · 2 2p log N log log N . Obtaining a 3-party information-theoretic DPF with N o(1) key size is more delicate, and only statistical (rather than perfect) security is known to be achievable. The starting point is a relaxed flavor of 3-party DPF obtained via 3-server PIR constructions from [44], [48]. It is relaxed in the sense that there is no way to fully control the nonzero output value β, and moreover this value inherently depends on α. An unfortunate byproduct is that revealing to the parties a “correction” that maps that shared output β̂ to the target β would compromise the secrecy of α. The high-level idea starts with a slight modification of this relaxed DPF so that the β values have at least one bit of entropy even when conditioned on α. Then, applying O(σ) independent copies, the β value has O(σ) bits of entropy. Finally, the random β̂ is mapped to the target β using a compressive linear hash function which is made public, namely part of all 3 keys. The statistical security of this construction follows from the Leftover Hash Lemma [49]. Theorem 3.9 (Statistically secure 3-party DPF): There is a statistically 2−σ -secure 3-party DPF for point functions with output group Zp (prime p), domain size N , and key size   √ O σ log(p) · 2 k(p) log N log log N , where k(2) = 6, k(3) = 10, and k(p) = 2p for p ≥ 5. Extensions to more general output groups appear in [50].

F. Overview of State-of-the-Art FSS Constructions As of the writing of this article (February 2026), the collection of known FSS constructions are as follows. The given complexity measures are with respect to n-bit inputs. Unless otherwise specified, the results of this section are for m = 2 parties. 0) “Lowest End” – Information-Theoretic FSS: Perfectly secure m-party FSS for linear functions can be implemented by additive secret sharing [19]. Another simple and perfectly secure FSS construction that applies to an arbitrary function class {f : {0, 1}n → G} is one that simply secret-shares the truth table of f . However, this requires exponential key size 2n · log |G|. Yet another simple and perfect FSS includes secret linear P combinations of public functions: namely,n fα⃗ (x) = i∈S αi gi (x), where the functions {gi : {0, 1} → G}i∈S are public for some module G over ring R, and α ⃗ = (αi )i∈S are secret R-coefficients. Perfectly secure m-party FSS for this class can be achieved by simply providing additive secret shares of the linear coefficients αi , with key size |S|⌈log |R|⌉ [2]. To evaluate the FSS key on input x, a party computes each gi (x) locally in the clear, and outputs the linear combination dictated by its shares of αi . This captures, for example, FSS for low-degree multivariate polynomials, by viewing the gi as the set of all monomials within the dictated degree. More sophisticated information theoretic FSS schemes can be obtained for m > 2 parties, provided that the security threshold t satisfies t < m/2. Such constructions will be discussed in Section III-E. 1) “Low End” – FSS from One-Way Functions: For simple but useful function classes (which are the focus of this survey), FSS can be constructed assuming only the existence of oneway functions, or equivalently, of a pseudorandom generator (PRG). This assumption can be shown to be minimal for m = 2 parties with nontrivial function classes and FSS key size; see, e.g., [3], [2]. The following constructions all make a black-box use of an arbitrary PRG stretching a λ-bit random seed to a pseudorandom output of length ≈ 2λ. In an AES-based implementation, we typically have λ = 128. • Point functions (DPF). The class of point functions consists of functions of the form fα,β , such that fα,β (x) outputs β if x = α and 0 otherwise. Here x, α ∈ {0, 1}n and β ∈ G for an Abelian group G. We let |β| denote the bit-length of a representation of a group element. When |β| is omitted it is understood to be 1. A distributed point function (DPF) is an FSS scheme for the class of point functions. – The first nontrivial (2-party) DPF was implicitly constructed in [7] in the context of computationally private information√retrieval. The key size of this construction is 2O( n) · λ, which is not polynomial in the input length n but still a super-polynomial improvement over the naive solution of additively sharing the size-2n truth table.

13

– The notion of DPF was first explicitly introduced in [3], which also gave a recursive construction with key size O(nlog2 3 · λ). This was improved to O(nλ) bits in [2] via a tree-based construction. – The best construction to date remains that of Boyle, Gilboa, and Ishai from 2016 [4], with key size ≈ nλ + |β|. More precisely, the key size is λ + n(λ + 2) − ⌊log(λ/|β|)⌋ bits.1 Any nontrivial improvement of this construction remains a highly motivated open problem. • Multi-party DPF. The complexity of existing m-party DPF constructions depends greatly on the desired security threshold 1 ≤ t ≤ m − 1. – For m > 2 parties, with security against t = m − 1: The construction presented in [2] has key size O(2m 2n/2 ·λ) bits. For a small number of parties m, this gives a near-quadratic improvement over the naive solution of secret-sharing the truth-table. In [8], the dependence on the number of parties was improved from exponential to polynomial via a randomized design, achieving key size 2n/2 ·poly(λ, m) (for small values of m, the construction from [2] has better concrete efficiency). The question of improving this square-root bound based on symmetric cryptography alone is one of the central open questions in the area. For example, it is even open a one-way function implies a 3-server DPF secure against 2 corruptions with key size O(λ· 2(1/2−ϵ)n ), for some constant ϵ > 0. – For m > 2 parties with a gap in the security threshold, i.e. 1 ≤ t < m − 1 corruptions: Better DPF constructions can be obtained from informationtheoretic private information retrieval schemes [5] or from PRG-based DPF [9]. One can also achieve a stronger form of multiplicative DPF [9], [10] in this setting, where Eval outputs multiplicative secret shares (e.g., “replicated shares” or “Shamir shares”) instead of additive shares. This allows parties to locally convert their Eval outputs to additive secret shares of the product of up to ⌊(m − 1)/t⌋ DPF outputs. (For example, for t = 1, the product of m − 1 outputs.) See Section III-B for more detailed discussion of multiparty DPF with m > 2 parties. • Comparison and interval functions. The class of comparison functions consists of functions fb which output 1 on inputs x with x < b, where the input space {0, 1}n is interpreted as integers from 0 to 2n −1. Interval functions f(a,b) output 1 precisely for inputs x that lie within the interval a < x < b, and 0 otherwise. Constructions of FSS for such functions follow a similar structure as DPFs. The best key size for comparison function is comparable to a DPF and for interval functions it is roughly twice the size [2], [4], [11]. See Section III-C for the case of distributed comparison functions (DCF). 1 In particular: λ + n(λ + 2) for λ-bit outputs, and λ + n(λ + 2) − ⌊log λ⌋ for 1-bit outputs.

Multi-point functions. A distributed multi-point function (DMPF) is an extension of DPF, where the secret function fA,B : {0, 1}n → G has up to t nonzero evaluation points for some publicly known parameter t (see notation in Section II-C). Many of the applications of DPF can benefit from this extension. For example, the application to PIR by keywords described in Section I-C can be extended using DMPF compute the intersection of a small set of t keywords held by a client with a database D of keywords held by the server, where the communication cost scales linearly with t and logarithmically with |D|. A simple way of realizing DMPF is by expressing it as the sum of t instances of DPF. The main disadvantage of this approach is that it increases the computational cost of full-domain evaluation by a factor of t. In Section III-D we discuss different approaches for minimizing this computational overhead at the price of a slightly bigger increase to the key size. • Offset function classes. The application of FSS to secure computation with preprocessing, proposed in [51], provides a low-communication reduction from secure evaluation of a gate g : Gin → Gout (mapping additive shares of the input to additive shares of the output), to FSS for a related offset class which includes, for any r ∈ Gin , the function gr (x) = g(x − r). It turns out that for many useful nonlinear gate functions g, the induced offset class is FSS-friendly in the sense that it admits a concretely efficient PRG-based FSS scheme. As a simple example, if g is a zero-test gate which outputs 1 ∈ Z2 if the input is zero and outputs 0 ∈ Z2 otherwise, then the induced offset class is just the set of point functions with 0/1 outputs. Optimized FSS schemes for the offset class of useful gates, such as ReLU, splines (piecewise polynomials), and many more were presented in [51], [11], [52], [53], [54], [55]. See Section IV-D for further discussion of this application of FSS. 0 n • NC functions. For d-local functions f : {0, 1} → k {0, 1} , in which each output bit depends on at most d = O(1) input bits, a PRG-based DPF can be used to get FSS with key size Od (k log n·λ) [2] (and evaluation time that scales with nd ). For example, the case k = 1 captures bit-matching predicates that depend on a constant number of input bits. This is based on the fact that FSS for an arbitrary function class of size N reduces to a DPF with domain size N by using the DPF to share the indicator vector of the function in the class. • Decision trees with topology leakage. A decision tree is defined by: (1) a tree topology, (2) variable labels on each node v (where the set of possible values of each variable is known), (3) value labels on each edge (the possible values of the originating variable), and (4) output labels on each leaf node. In the construction of [4], the key size is roughly |V | · λ bits, where V is the set of nodes, and evaluation on a given input requires |V | PRG invocations, and a comparable number of additions. The FSS is guaranteed to hide the secret edge value labels and leaf output labels, but (in order to achieve this efficiency) reveals the base tree •

14

topology and the identity of which variable is associated to each node. • Constant-dimensional intervals. A useful application of the above FSS scheme for decision trees is FSS for ddimensional interval functions. Such a multi-dimensional interval is a f (x1 , . . . , xd ) which evaluate to a selected nonzero value precisely when ai ≤ xi ≤ bi for some secret interval ranges (ai , bi )i∈[d] . For n-bit inputs xi , FSS for d-dimensional intervals can be obtained with key size and computation time O(nd · λ). For small values of d, such as d = 2 for supporting two-dimensional rectangles, this yields solutions with a reasonably good concrete efficiency. A lower bound of Ω̃(n1.5 ) on the evaluation time of FSS schemes for 2-dimensional intervals that make a black-box use of a PRG was recently obtained in [56] via a connection with dynamic data structures. In the context of private information retrieval, FSS schemes for the above function classes can be combined with serverside database operations to emulate private database search with richer query classes, such as Max/Min and top-k [57]. See Section IV for discussion of these and other applications of FSS from symmetric cryptography. Homomorphic Secret Sharing. When considering FSS for rich function classes, it is often more natural to use the dual notion of homomorphic secret sharing (HSS), where the roles of the input and the function are swapped. Namely, whereas FSS evaluates a secret-shared function on a public input, HSS evaluates a public function on a secret-shared input. Note that HSS and FSS are closely related, but that “HSS for a function class F ” is not identical to “FSS for the class F.” Notably, HSS for F places a more stringent requirement on the share size of an input x to grow only as a function of the size of x and support homomorphic evaluation of functions f ∈ F; in contrast, FSS for F must inherently have key size that grows with the description size of f ∈ F. FSS can be generically reduced to HSS by relying on universal functions. A universal function for a class F is a function UF such that for all f ∈ F and x ∈ {0, 1}n , it holds that UF (f, x) = f (x). Given such a universal function, one can reduce the problem of constructing FSS for F to the problem of constructing HSS for the class of functions UF := {UF (·, x) : x ∈ {0, 1}n }. The key size of the resulting FSS scheme (inherently) scales with the description size of f . 2) “Mid Range” – FSS/HSS from LPN-Style Assumptions: In recent years, there has been success in building lightweight constructions of HSS from variants of the Learning Parity with Noise (LPN) [58] assumption. The LPN assumption asserts that it is computationally hard to solve a system of uniformly random linear equations over F2 where each bit is flipped with some small probability ϵ. It can be shown that this search variant of LPN is equivalent to the decision variant, asserting that noisy linear combinations are pseudorandom. An equivalent formulation of LPN is that it is hard to decode a noisy (random) codeword from a given random linear code. Changing the distribution over equations is equivalent

to considering other types of linear codes. Many variants of LPN are standard in the literature, over fields other than F2 , and with different distributions over linear codes and/or noise. Depending on the parameter regime (e.g., noise rate), the LPN assumption and its variants can be viewed as lying in between symmetric cryptography and public-key cryptography. While LPN with low noise is known to imply publickey encryption [59], it is not known to imply additively homomorphic encryption (or even collision-resistant hashing, except in an extreme parameter regime [60]). In the context of HSS and especially in the related context of PCGs, LPN turns out to be surprisingly useful, even in a regime where it is not known to imply public-key encryption. Under LPN, the following HSS constructions are known: • HSS for constant-degree polynomials, from standard LPN [17]; • HSS for log λ/ log log λ-degree polynomials, from the superpolynomial hardness of LPN [61]. • Multi-party HSS for log λ/ log log λ-degree polynomials from a sparse variant of LPN [62]. This construction applies to any number of parties m with any linear secret sharing of the output. Combined with a linearly homomorphic encryption, it gives rise to a homomorphic encryption scheme for a similar class [63]. On the downside, unlike previous LPN-based HSS schemes, this construction suffers from an inverse-polynomial error. For the default notion of HSS, where the output shares are additive, the correctness error can be made negligible for the class of constant-degree polynomials [64]. This implies a multi-party DPF whose key size scales with N 1/d , for an arbitrary constant d. The construction relies on a combination of (non-sparse) LPN and a flavor of the MQ assumption, asserting that a random system of quadratic equations is hard to solve. This too qualifies as a “mid-range” construction, since the underlying assumptions are not known to imply public-key cryptography. In all of the above cases, the share size scales linearly with the input size and is sublinear in the description size of the function being evaluated. This rules out, for instance, HSS for constant-degree polynomials that uses additive sharing of all monomials (as was the case for the information-theoretic FSS for low-degree polynomials described above). An HSS scheme for degree-2 polynomials with compact (but not additive) output shares was constructed in [65] from threshold additively homomorphic encryption. Constructions of compact non-additive HSS for low-degree polynomials from partially homomorphic encryption schemes were given in [66], [67]. 3) “High End” – FSS/HSS from Public-Key Cryptography: Using standard public-key cryptography assumptions, HSS schemes exist for much richer function representation classes, including branching programs (capturing functions in NC1 and logspace) and even general circuits (capturing general polynomial time computations). Concretely, the following results are known. • Branching programs (inverse-poly error): Allowing for inverse-polynomial error (namely, δ-correctness for any inverse polynomial δ), a construction from Decisional

15

Diffie-Hellman (DDH) was presented in [12]. In this construction the running time of Eval is Õ(s2 /δ), where s is the branching program size and δ is the error probability (which can be made detectable, namely of a Las-Vegas type). This was subsequently improved to Õ(s1.5 /δ 0.5 ) in [68]. Optimized variants of the DDHbased constructions for simple but useful function classes are given in [69], [70]. A similar construction from the Decisional Composite Residuosity (DCR) assumption was presented in [71]. • Branching programs (negligible error): With full (negligible-error) correctness, HSS constructions from the DCR assumption were presented in [15], [16]. In these constructions, the running time scales linearly with s. • Circuits: A general-purpose FSS/HSS scheme for Boolean circuits based on the Learning With Errors (LWE) assumption was presented in [13] via a flavor of homomorphic encryption called “spooky encryption.” The construction combines a multi-key variant of fully homomorphic encryption with a local rounding procedure for converting noisy additive shares of the output over a big modulus to almost noiseless additive shares of the same output value over a small modulus. Note that a more efficient construction of HSS from LWE (and Ring-LWE) was given for the case of branching programs by [14]; this construction avoids homomorphic multiplication of encrypted values and instead emulates restricted multiplications via a form of distributed decryption. Additionally, a more direct construction of FSS for branching programs from LWE (and a small exponent variant of the DCR assumption) was given by [72], bypassing the overhead of universal circuits inflicted by the HSS-to-FSS transformation. IV. A PPLICATIONS In this section, we discuss some of the main applications of DPF and, more generally, FSS schemes for simple function classes, to concretely efficient secure computation and more. We start (Section IV-A) with a distributed key generation protocol which is needed in several of these applications, and then move on to describe different classes of applications. A. Efficient Distributed Key Generation In many applications of DPFs, there is no single entity who knows the identity of the secret point function; instead, the role of “client” is jointly executed across parties. In these cases, the point function itself is either generated or defined by values held secret shared across parties, and the Gen algorithm of the DPF must in turn be executed distributedly via a secure computation protocol. This is the situation, for example, for applications of DPFs to secure computation for RAM programs [22] or mixed-mode operations [51], [11], use of pseudorandom correlation generators for secure computation preprocessing [21], [51], [73], and more, as we discuss in the sections below. Secure execution of Gen can of course always be achieved generically, by running an off-the-shelf secure computation

protocol run on the corresponding Gen procedure expressed as a Boolean (or other) circuit. However, doing so requires unrolling the cryptographic pseudorandom generator (PRG) operations as complex Boolean circuits, which is typically undesirable for efficiency. Alternatively, work has gone toward designing targeted secure protocols for achieving the same goal, while remaining black box in the underlying cryptographic PRG. In particular, the parties locally evaluate the PRG on various inputs, but will never need to use (or know) the explicit code or circuit implementation of the PRG itself. This was initiated by the work of Doerner and shelat [22]. In this work (using DPFs for efficient secure computation of RAM programs), they presented a distributed Gen protocol for the standard tree-based DPF construction [4], which requires computation time linear in the DPF domain size N , and log N sequential communication rounds, but which crucially makes only black-box use of oblivious transfer and a pseudorandom generator. Their protocol remains the most efficient to date for this task. Note that in relaxed variants where one party is allowed to learn α (but still not β), the protocol can be parallelized, reducing the round complexity to constant [74], [31]. Black-box Distributed Gen [22]. A DPF key for the treebased DPF is made up of an initial seed, which is randomly and independently sampled for each party, and n + 1 public correction words. The i-th correction word, 1 ≤ i ≤ n is used to ensure that the values in the two children of v, the i-th node on the path from the root to α are suitable. That is, the values in the two trees of the child that is off-path must be identical, while the values of the child on the path are pseudorandom. That is achieved by setting the correction word to be the XOR of the two values of the off-path child, and having a single party XOR this value with its off-path child during Eval. Denote the seed at the left child of v by s0,ℓ for the first party and by s1,ℓ for the second party, and denote the seeds of the right children by s0,r , s1,r . Consider the expansion of all the seeds in the i-th level to strings of double the seed length, and divide them into all the left halves of these strings and all the right halves of these strings. [22] observes that if the values of all the nodes in the i-th level are identical in both trees except for the values of v, then the XOR of all the left halves in the first party is L ⊕ s0,ℓ and in the second party the XOR is L⊕s1,ℓ , for some identical string L that depends on all the nodes in the i-th level that are not on the path to α. Similarly, the XOR of all the right halves are R ⊕ s0,r and R ⊕ s1,r for the first party and for the second party, respectively. It follows that the i-th correction word is the XOR of all the left halves in both trees or the XOR of all the right halves in both trees. Determining which option is correct depends on α. Given a bit by bit secret sharing of α and an additive secret sharing of β in its target group G, the distributed generation protocol of [22] begins with each party independently sampling a random initial seed. The parties compute the correction words in order from the first to the n-th. To compute the ith correction word, the first party acts as the sender in an Oblivious Transfer (OT) protocol for strings, setting up two

16

messages m0 , m1 . If its share of the i-th bit of α is 0 then it assigns m0 = L ⊕ s0,ℓ and m1 = R ⊕ s0,r . If its share of the i-th bit of α is 1 then it switches between the values of the two strings. The second party acts as the OT receiver and learns mb for its share b of the i-th bit of α. If b = 0 then the correction word is mb ⊕ (L ⊕ s1,ℓ ), while if b = 1 then the correction word is mb ⊕(R⊕s1,r ). Therefore, the second party can compute the i-th correction word after the OT and share it with the first party. Computing the last correction word, which additively masks β does not even require an oblivious transfer. Each party computes the expansion of a seed in all the leaves of the tree into elements in G. A fixed linear combination of these values and of the shares of β gives the last correction word. The number of symmetric key operations, i.e., PRG expansions, in this protocol is O(2n ), while the number of string OTs is exactly n. We refer readers to Section 5 of [22] for a detailed description and pseudocode of the corresponding Distributed Gen procedure. This procedure was extended to handle distributed comparison functions in [11]. The main overheads of the protocol are the O(N ) computational cost for both parties, and the log N round complexity. While there are no known ways to avoid the former without making non-black-box use of cryptographic primitives, the round complexity can in some cases be reduced. If we are in a relaxed setting (as in some applications) where it is allowed to leak the secret index α to one of the two parties, the round complexity can be brought down to just two rounds, since all OTs can be performed in parallel [51], [31], [74]. Another approach based on a so-called programmable DPF [28] can achieve a constant round complexity without leaking α, although with poor concrete efficiency. In the setting of distributed multi-point functions, distributed setup protocols can get more involved, particularly for the more complex batch code or OKVS based DMPF constructions from Section III-D. A recent work [34] improves this by using a “reverse cuckoo hashing” based DMPF that is designed to simplify the setup protocol: instead of sampling hash functions and then obliviously assigning items into bins, the construction first picks a valid assignment and then solves a system of linear equations (inside 2-PC) to determine the hash functions. B. Private Reading In the introduction, we already sketched a simple application to the task of private information retrieval (PIR), where a client holding a private keyword α can perform a lookup to a database D held by two servers, such that the client learns whether α ∈ D, by using a DPF where α is encoded into a point function fα,β for β = 1. This approach implies simple and fast PIR implementations; see [75] and references therein. We now explore more expressive extensions of this. Consider a more structured database D, consisting of key-value pairs (vi , xi ) instead of just keywords. Using a DPF, we can extend the previous construction to perform a sum query, where the client learns the sum (over the DPF output group G) of all the xi ’s where vi = α. This can be again done by

generating DPF keys k0 , k1 for the point function fα,1 , and having each server b compute X yb = Eval(b, kb , vi ) · xi . (vi ,xi )∈D

After receiving each server’s shares, the client can reconstruct the result y0 + y1 . Going beyond equality constraints, using a distributed comparison function (DCF) instead of DPF allows the client to select (or sum) values that fall in a given interval. Various matching and aggregation functions of this type can be implemented using DPFs and DCFs, to allow for private database queries supporting a relatively large subset of SQL, as explored in [57]. Unbalanced Private Set Intersection. Another use-case for this type of protocol is the task of private set intersection, where the client holds a small set C and wishes to learn the intersection with the server’s database D, which is now a simple set of keywords {vi }i . By relaxing the standard PSI setting to a two-server model, where D is held by two noncolluding servers, the parties can run the naive PIR lookup for every element α ∈ C, allowing the client to learn C ∩ D. Note that the communication complexity of this protocol is independent of the size of D, unlike standard PSI solutions in the literature. This makes it particularly suitable for scenarios such as private contact discovery, where the server’s database is much larger than the client’s set. Further extensions and optimizations to this approach were considered in [76]. A form of function secret sharing has also been used to obtain efficient structure-aware PSI, where one party’s input set has a publicly known structure, yielding fuzzy PSI and beyond [77], [78], [79], [80]. C. Private Writing In a writing analog of PIR, instead of reading, the client wishes to periodically perform updates to a database by writing secret values. This was first considered by Ostrovsky and Shoup [81] in the information-theoretic setting, and solutions based on distributed point functions were proposed in [82], [4]. In this application, it is inherent that no single server can know the database, which is typically enforced by secretsharing it among the servers. Suppose that two servers hold additive shares v0,i and v1,i of each i-th entry in D, such that vi = v0,i + v1,i . A client who wishes to update entry α from vα to vα′ can create DPF keys k0 , k1 for the function fα,β , where β = vα′ − vα . If server b then updates its shares ′ to vb,i = vb,i + Eval(kb , i), the shared database is updated accordingly. Private Aggregate Statistics. This type of private writing can be applied to the task of privately gathering aggregate statistics from users of complex software such as a web browser or operating system. Such aggregate statistics are useful for identifying popular features, detecting malicious websites, tracking error rates, and more, while ensuring that the contribution of any individual user remains private.

17

As a concrete example (proposed in [4]), consider a private histogram protocol. Suppose there is a set of possible websites, indexed by the set S = [n], and a population of clients who each hold a private value αi ∈ S (e.g. a website that triggered a browser crash), and the goal is to compute the histogram counting how many clients experienced a crash under each of the sites in S, without revealing any individual input. Using the private writing technique above, each client generates DPF keys (ki,0 , ki,1 ) for the point function fαi ,1 and sends ki,b to server b. EachP server b then computes, for every j ∈ S, the sum hb,j = i Eval(ki,b , j). By the correctness of the DPF, the combined histogram h0,j + h1,j counts exactly the number of clients with input αi = j, while the security of the DPF ensures that no single server learns any individual client’s input. Prio [83] was the first practical system to address this type of private aggregation at scale. While Prio does not rely on DPFs, instead using standard secret-sharing, the authors noted that DPFs could be used to compress the share size in usecases such as histograms. The private histogram protocol above requires the set S to be small enough for the servers to enumerate. In many settings, however, the domain of possible inputs is exponentially large (e.g., arbitrary URLs or search queries), making full enumeration infeasible. The problem of private heavy hitters asks to identify the most frequently occurring strings among the client population, without learning any individual input and without enumerating the full domain. Boneh et al. [84] introduced the Poplar protocol, which solves this problem by relying on an incremental variant of the tree-based DPF (Section III-A) that allows evaluation on any prefix of an input. The key idea is that each client submits incremental DPF keys encoding their private string, and the servers use the incremental structure to efficiently search for heavy hitters by progressively expanding only the prefixes that appear frequently, rather than evaluating over the entire domain. Doplar [85] builds on the Poplar approach, reducing the number of rounds of server interaction needed to verify that client submissions are well-formed. Anonymous Messaging. The private writing paradigm can also be applied to build anonymous messaging systems. The Riposte [82] system is an anonymous bulletin board, where a set of servers hold secret shares of the messages to be sent over a given time period. A client who wishes to publish a message m uses the private writing protocol to insert it at a random position in the bulletin board, sending a DPF key to each server to allow it to update its shares. After all clients have submitted their keys in a given epoch, the servers jointly reconstruct the bulletin board to reveal the posted messages, while the DPF security ensures that no single server learns which client wrote to which row. A key challenge in this setting is handling write collisions: if two clients attempt to write to the same row, their messages will be summed together, corrupting both. Riposte addresses this by increasing the database size to accommodate the expected number of writes, together with some algebraic error correction techniques to allow recovery in case of a small

number of collisions. Handling Malicious Clients with Verifiable DPFs. In the above applications, the servers must trust that each client’s DPF keys encode a valid point function. A malicious client could submit keys that do not correspond to a valid point function, or with a nonzero point outside of a required range, which could corrupt the aggregation results. To mitigate this, many works add a verification procedure that allows the servers to check that keys are well-formed, whilst preserving privacy of the hidden point against a semi-honest server. One approach to supporting verifiability is via informationtheoretic arithmetic sketching techniques, first used in [4] and later developed in [86]. We give a simple example for proving that a DPF with domain size N = poly(λ), and outputs shared over a finite field F of characteristic > 2, encodes a single nonzero value β ∈ {0, 1}. After receiving the DPF keys from the client, the servers will agree upon some common randomness (for instance, derived from a shared PRF key) r1 , . . . , rN ∈ F. Let (y1 , . . . , yN ) be the vector of all N evaluations of the point function. will compute shares of P The idea is thatPthe servers z1 = yi ri and z2 = yi ri2 , and then use a small 2-PC protocol to check that z12 = z2 . This holds if and only if

0=

N X i=1

!2 yi ri

−

N X i=1

N X = (yi2 − yi )ri2 + i=1

yi ri2 X

2yi yj ri rj

1≤i<j≤N

Viewing this as a degree-2 polynomial in (r1 , . . . , rN ), notice that if there are two non-zero outputs yi and yj then the monomial ri rj has a non-zero coefficient (since the characteristic is not two), and so by the Schwartz-Zippel lemma, the probability of passing the verification is at most 2/|F|. Similarly, in case there is only a single non-zero output, yi , but it lies outside {0, 1}, then yi2 − yi ̸= 0, and again we can apply Schwartz-Zippel. In [4], [86], various other randomized sketching procedures are given for testing different kinds of relations, including different possibilities for β other than {0, 1}, supporting arbitrary finite fields, and supporting weight-w vectors for verifying distributed multi-point functions. Another approach to making a DPF verifiable is to use a cryptographic hash function. This approach relies specifically on the tree structure of the construction from Section III; it was initially used to verify consistency of a distributed puncturable PRF protocol in [74], and extended to obtain a verifiable DPF in [32]. The idea is that the tree will be extended by one level, so that the number of DPF outputs grows from N to 2N . The extra N values will all be zero, meaning that both servers obtain the same set of shares (after correcting for sign). Thus, the servers can just hash together the N extra shares, then exchange and compare the resulting hash values. It was shown in [32] that, under certain collision-resistance and correlationintractability assumptions on the hash function, this guarantees consistency of the DPF outputs, even if one of the servers is malicious.

18

This approach has the benefit of a lower round complexity than arithmetic sketching approaches, since the servers do not need to agree upon any randomness, and furthermore, no general-purpose 2-PC is needed. On the other hand, cryptographic hashing can be more computationally expensive than finite field operations, as observed in [85]. Both approaches to achieve verifiable DPFs (arithmetic sketching and using cryptographic hash functions) suffer from computation that is linear in the input domain size. Circumventing this obstacle is possible in some applications by considering only a subset of the input domain and verifying the output of the DPF only on that subset. That approach was adopted in [84] for the subset of heavy hitters, i.e., the most popular query strings that are supplied by multiple clients. However, limiting the consideration to a subset of the domain enables a subtle attack when the subset to be considered is unknown at Gen time. A malicious client can submit a query with multiple non-zero locations and will only be discovered if the subset of interest happens to include two or more non-zero inputs. In this way, a malicious client casts several “votes”, gaining more influence on the final result than an honest client. Extractable DPF is a refinement of standard DPF that blocks this type of double-voting attack. At a high level, the structure of the queries in extractable DPF ensures that a malicious client can only choose one point at which the sum of evaluations of the point has a permissible, non-zero value, where only a small subset of elements of the output group have a permissible value for a point function. In slightly more detail, a 2-party extractable DPF scheme in the Random Oracle Model is equipped with a polynomial time algorithm, called the extractor, which given as input the keys that Gen constructs and all of the calls to the random oracle that Gen makes returns as output an input location α. The adversary wins if Eval(0, k0 , α∗ )+Eval(1, k1 , α∗ ) = β for some α∗ ̸= α and a non-zero β, which is permissible as the output of a point function. The scheme is secure if the probability that the adversary wins is negligible. In [84], it was proven that the DPF presented in Figure 3 is an extractable DPF, given two assumptions: the PRG is modeled as a Random Oracle, and the output group of the point function is sufficiently large. Several other DPF constructions are not extractable, including the less efficient 2-party DPF schemes in [2], [3] and the multi-party DPF schemes in [2], [8]. Intuitively, the DPF in Figure 3 is extractable because a malicious client cannot control more than one non-zero path in the GGM tree. In any level i of the tree, an honest client uses the single correction word at its disposal to ensure that the evaluation of the function in one additional sub-tree, rooted at the offpath child of the i-th level on-path node, is zero. A malicious client has two possible strategies. First, it can generate a correction word that does not set the value in either child to zero. However, in this case, modeling the PRG as a random oracle implies that all of the two or more non-zero values are random and independent of each other, ensuring that the client can determine the final output of at most one leaf. If the output group is large enough in relation to the subset of permissible outputs of the point function, then the probability

that the value at more than one point will be in the permissible set is negligible. A second strategy for a malicious client is to provide different correction words to the two servers. Indeed, each of the keys k0 , k1 has a private part, which includes the initial PRG seeds used at the root of the tree, and a public part, which includes all the correction words. The private part is sampled independently for each key, while the public part is identical in an honest execution of Gen. To test that the client acts honestly, providing identical correction words in each key, the two servers can run a secure protocol to ensure that the two public parts of their keys are identical. To informally summarize the analysis on the DPF in Figure 3: if the input domain is {0, 1}n , the output group is G, the set of permissible values for a point function is P ⊆ G, the PRG is modeled as a random oracle with a malicious client making at most t calls to this PRG, and the two servers securely testing that the public parts of their keys are identical, then the DPF is extractable and the probability that a malicious client wins 2 |) . the security game is at most O((t +nt)|P |G| D. Secure Computation with Preprocessing A common paradigm for efficient secure two-party computation splits the protocol into an input-independent preprocessing (or offline) phase and a lightweight online phase. In the preprocessing phase, a trusted dealer (or an additional cryptographic protocol) distributes correlated randomness to the two parties. Once the inputs become available, the online phase uses this correlated randomness to evaluate the desired function with minimal interaction. Boyle, Gilboa, and Ishai [51] introduced a simple and general approach for secure computation with preprocessing, building on function secret sharing. This approach can be viewed as a generalization of the “TinyTable” protocol of Damgård et al. [87]: whereas TinyTable represents the correlated randomness for each gate as a full truth table (whose size is exponential in the number of input wires), the FSSbased approach replaces these truth tables with FSS keys, achieving exponential compression for gate types that admit efficient FSS schemes. The approach was further developed in [11], extending it to “mixed-mode” secure computation where different parts of the circuit operate over different algebraic domains. Overview of the approach. The central observation is best illustrated for a single gate. Consider a gate g : Gin → Gout that two parties P0 , P1 wish to evaluate on a secret input. Suppose that, rather than holding secret shares of the input w, both parties know a masked version ŵ = w + rin for a random mask rin ∈ Gin unknown to either party individually. If the dealer knows rin as well as a random output mask rout ∈ Gout , it can precompute the offset function grin ,rout (ŵ) = g(ŵ−rin )+ rout = g(w) + rout and distribute FSS keys for this function to the two parties. During the online phase, both parties evaluate their FSS keys on the common value ŵ, obtaining additive shares of g(w) + rout . After exchanging these shares, they recover the masked output g(w) + rout , which is itself a fresh masking of g(w), to use as input to the next gate.

19

To evaluate an entire circuit C, the dealer associates a random mask rj with every wire j in C, and for each gate prepares FSS keys for the corresponding offset function as above. The protocol maintains the invariant that both parties learn the masked value wj + rj for every wire j. At the input level, this is established by having each party send its masked input to the other; at each subsequent gate, the FSS-based procedure above advances the invariant from input wires to output wires. At the end, the dealer reveals the output-wire masks so the parties can recover the result. The efficiency gain over TinyTable comes from the FSS compression: instead of storing a full truth table for each gate’s offset function, the parties store only FSS keys. For gate types that admit compact FSS schemes, such as comparison and equality gates via DCF and DPF (Section III), the correlated randomness per gate is exponentially smaller than the truth table.2 A variant of this protocol, also described in [51], makes the correlated randomness circuit-independent by choosing masks for each gate independently and providing additive shares of the input masks alongside the FSS keys. The parties can then non-interactively reconcile the mask mismatch between adjacent gates during the online phase, at the cost of slightly higher communication (one group element per wire rather than per wire value). Instances and applications. Several well-known protocols in the preprocessing model can be viewed as special cases of this FSS-based framework. For gates computing a product over a ring (i.e., g(x1 , x2 ) = x1 · x2 ), the corresponding offset function class has an FSS scheme that reduces to the familiar Beaver triple technique [88]. For Boolean gates on a small number of input bits, the truth-table-based FSS recovers the TinyTable protocol [87]. The approach becomes particularly powerful for gates with structured functionality that admit efficient FSS but have large truth tables. Using DPF-based and DCF-based FSS, the following types of nonlinear gates can be efficiently implemented with compact correlated randomness and optimal online communication [51], [11]: • Equality test and integer comparison: Given a masked arithmetic input, the parties can securely evaluate whether two values are equal, or which is larger, using DPF and DCF respectively. • Bit decomposition: Converting an arithmetic sharing over a large group into sharings of the individual bits. This can be realized by composing comparison gates. • Fixed-point arithmetic: Operations such as truncation and rounding, which are essential for fixed-point representations of real numbers, can be expressed using comparison-based gates. • Nonlinear activation functions: Piecewise-linear or piecewise-polynomial approximations of functions such as ReLU or sigmoid can be evaluated using a small number of comparison and arithmetic gates. 2 A general method for compressing truth-table correlations was suggested in [17]. However, the running time still grows linearly with the truth-table size, or exponentially with the gate input length.

These capabilities make the FSS-based preprocessing approach especially useful for privacy-preserving machine learning, where secure computation must handle a mix of linear operations (e.g., matrix multiplications over arithmetic shares) and nonlinear operations (e.g., activation functions and argmax). Works such as [11] and subsequent systems [54], [55] have demonstrated that FSS-based techniques offer a competitive approach for such mixed-mode computations. E. Pseudorandom Correlation Generators As well as the general FSS-based approach above, DPFs have been instrumental in building pseudorandom correlation generators (PCG), which can produce large quantities of correlated randomness for use in MPC protocols in the preprocessing model with only a small amount of interaction [21], [17]. A PCG has a key generation algorithm that outputs a pair of short, correlated seeds, which can then be locally (or, silently) expanded to obtain a large quantity of correlated randomness. The correlated randomness might take the form of, for instance, a large batch of random oblivious transfer (OT) correlations, or a batch of Beaver triples. We give an overview of some simple constructions of PCGs based on the learning parity with noise assumption (LPN). To start with, observe that a DPF is a natural way to compress pseudorandom secret shares of a sparse vector. A weight-one vector ⃗v = (0, . . . , β, 0, . . . , 0) ∈ RN over a ring R can be viewed as the truth table of the point function fα,β : [N ] → R. Hence, a dealer can distribute secret shares of ⃗v to two parties by generating and giving out a pair of DPF keys. This easily extends to sharing weight-t sparse vectors for not-too-large t, by using a multi-point DPF. We can combine the compressed sparse vector sharing technique with LPN to obtain various forms of correlated randomness. The dual form of LPN over R states that for a secret, sparse vector ⃗e ∈ Rn and public, random matrix H ∈ Rm×n , the product H⃗e is computationally indistinguishable from a random vector (this is also known as the syndrome decoding problem). We first apply this to generating a so-called vector oblivious linear evaluation correlation (or vector-OLE), where one party holds vectors ⃗u, ⃗v while another party holds a scalar x and learns w ⃗ = ⃗ux +⃗v . The goal is for two parties to obtain a single, long instance of a random vector-OLE, given only a pair of short seeds. Viewing vector-OLE as a (subtractive) sharing of ⃗ux, we will define a pseudorandom ⃗u vector as an LPN instance H⃗e, and then use a multi-point DPF to give to the parties shares of ⃗ex, which has the same sparsity as ⃗e. After expanding the DPF seeds, each party can then locally multiply their share vector by H to obtain the respective ⃗v or w ⃗ output. As part of the PCG seeds, we additionally give one party x and the other party the sparse ⃗e vector, which completes the correlation setup. This PCG template can be extended beyond just a vectorOLE correlation. Firstly, vector-OLE can be generalized to give correlated OT, a form of OT where every pair of the sender’s messages satisfies mi,0 + mi,1 = ∆ for some fixed, secret offset ∆. This can be shown to be equivalent to vector-OLE where the ui entries are restricted to {0, 1},

20

also called subfield vector-OLE when the ring R is a binary extension field; furthermore, correlated OT can be converted into standard, random OT by putting the messages through a correlation-robust hash function [89]. Secondly, we can also use DPFs to obtain a PCG that produces a large batch of OLE correlations of the form wi = ui xi + vi , where all the ui , vi , xi ’s are independently random. This is done via a simple tensor product trick: sample two LPN error vectors ⃗e, ⃗e′ ∈ Rn , and define ⃗u = H⃗e and ⃗x = H⃗e′ . We have: ⃗u · ⃗x⊤ = H · ⃗e · (⃗e′ )⊤ H ⊤ ⃗e · (⃗e′ )⊤ is a tensor product matrix with at most t2 non-zero entries. Therefore, it can be distributed into shares using a t2 point DPF with domain size N 2 . After this, the parties can locally compute shares of ⃗u · ⃗x⊤ and take the diagonal of this matrix to obtain shares of ui xi for all i (as a by-product, they can additionally compute shares of any bilinear function of ⃗u and ⃗x). Optimizations and Extensions. The above construction for vector-OLE was first introduced in [21], while those for OT and OLE were given in [17]. Since then, PCGs have become a highly active area of research, and many variants of the above constructions with improved efficiency characteristics exist in the literature. Instead of using a uniform matrix H, practical constructions typically choose a structured matrix of a special form allowing for fast multiplication, thus relying on a structured variant of LPN instead of the standard LPN assumption. For example, H could be a quasi-circulant matrix [74], a polynomial multiplication matrix (as in ringLPN [73]), or chosen as the parity-check matrix chosen from a carefully designed family of codes with fast encoding and good minimum distance [90], [91]. Instead of the dual form of the LPN assumption given above, some works use LPN in its (standard) primal form A⃗s + ⃗e, where in the sparse-LPN variant, each row of A is chosen to be sparse, significantly speeding up computation [92]. Pseudorandom Correlation Functions. A useful extension of PCGs that enables a virtually unbounded number of correlated randomness instances is a pseudorandom correlation function (PCF) [93]. While a standard PCG allows parties to expand short, correlated seeds into a fixed-size batch of correlated pseudorandom strings, a PCF takes this a step further by acting as the “function” analogue. This is analogous to the way a standard pseudorandom function (PRF) extends a standard PRG. A PCF for simple correlations such as OT can be obtained from any FSS scheme for a class of (weak) PRF. While an LWE-based feasibility follows from FSS for general circuits, this approach is impractical. The first concretely efficient PCF construction from [93] relied on a new weak PRF candidate, in which a function in the class is a sum of point functions on variable-size subsets of the input. An FSS scheme for this class can thus be based on multiple DPF instances. Subsequent constructions of PCF for OT and other correlations were given in [90], [94], [95].

F. Locally Random Reductions We conclude with a complexity theoretic application of DPFs. Using a sub-exponentially secure DPF, which can in turn be based of a sub-exponentially-secure one-way function, we can obtain a (relaxed variant of) locally random reduction, for functions in high complexity classes that uses only two queries. This, in turn, can be used to improve over classical results on worst-case to average-case reductions for these classes. For context, classical arithmetization techniques in complexity theory [96], [97], [98] use polynomials to efficiently reduce the evaluation of f (x) to the evaluation of a related function g on inputs x1 , . . . , xn , where each input xi is individually random. Furthermore, if f is in PSPACE or EXPTIME, then so is g. This is referred to as an n-query locally random reduction (LRR). Such an LRR can be used for the following kind of worst-case to average-case reduction: given an oracle to any algorithm Ag for g which is correct on all but an ϵ-fraction of the inputs, we can efficiently implement a probabilistic algorithm Af for f which is correct for all inputs, except with ϵn error probability, by having Af (x) invoke Ag on x1 , . . . , xn obtained by the LRR. By a union bound, the probability that Ag is incorrect on any of these inputs is at most ϵn, implying a similar upper bound on the error probability of Af . As observed in [3], a 2-party DPF can yield a similar LRR with only 2 queries x0 , x1 : On input x, the reduction invokes Gen(x) to obtains DPF keys k0 , k1 . The function g is the DPF Eval function. For existing DPF constructions, if f is in PSPACE or EXPTIME, then so is g. Note, however, that this requires settling for a weaker notion of LRR, where each query xi is pseudorandom rather than perfectly random. (Pseudorandomness of keys holds for standard DPF constructions, including those described in Section III.) However, assuming a sub-exponentially secure PRG, which follows from a one-way function with similar security, we can still ensure that if Ag runs in (fixed) exponential time, the pseudorandomness of the DPF is good enough to fool Ag while still allowing for polynomial-time key generation. This relaxed notion of LRR yields worst-case to averagecase reduction as above for functions f in PSPACE or EXPTIME with only 2 queries. This implies that if Ag is correct on all but an ϵ-fraction of the inputs, Af errs with at most 2ϵ probability. An extension of this idea to efficiently checking the computation of polynomial-time computable functions was explored in [20]. However, this extension requires FSS or HSS schemes for more complex function classes, which can currently only be constructed from “public-key” cryptographic assumptions such as the LWE. V. O PEN Q UESTIONS We close with a selection of open problems in the area. •

Improved 2-party DPF: Can the ≈ n · λ key size of the best known PRG-based construction be improved? Here even concrete efficiency improvements (e.g., improved multiplicative constant) would be highly motivated.

21

Alternatively, is there a way to formalize a barrier toward such improvement, given only a restricted set of computational operations? • Multi-party DPF: Can one beat the square-root key-size barrier for PRG/OWF-based full-threshold multi-party DPF? In particular, is there a 3-party DPF secure against two corruptions with key size O(λ · 2(1/2−ϵ)n ) for some constant ϵ > 0? A canonical milestone is O(λ · 2n/3 ), but any constant improvement in the exponent would be a major advance. • FSS for conjunctions: Which cryptographic assumptions suffice for efficient FSS for the class of arbitrary conjunctions of input bits? Are one-way functions sufficient? Alternatively, does this imply public-key cryptography? Note that conjunctions of up to d bits can be achieved but with key size scaling as O(2d ). • Efficient distributed Gen: Is there a distributed generation algorithm for DPF which makes a black-box use of a PRG with computation time that is polylogarithmic, or even just sublinear, in the domain size? For reference, existing distributed Gen protocols are either non-blackbox in the PRG (e.g., naı̈ve secure evaluation of the Gen circuit), or require linear computation time in the domain size [22], [28]. • Information-theoretic DPF: Is there a perfectly secure 3party DPF with domain size N and key size N o(1) ? Here we only consider security with threshold t = 1, namely each individual key perfectly hides the secret point. Such a 4-party DPF, or alternatively a statistically secure 3party DPF, was presented in [47]. What is the minimal key size of an information-theoretic 2-party DPF with compact output shares (say, 2-bit long) if we allow a general (non-additive) reconstruction of the output from the shares? What can we say about the power of information-theoretic FSS in this setting? R EFERENCES [1] J. Håstad, R. Impagliazzo, L. A. Levin, and M. Luby, “A pseudorandom generator from any one-way function,” SIAM Journal on Computing, vol. 28, no. 4, pp. 1364–1396, 1999. [2] E. Boyle, N. Gilboa, and Y. Ishai, “Function secret sharing,” in Annual international conference on the theory and applications of cryptographic techniques. Springer, 2015, pp. 337–367. [3] N. Gilboa and Y. Ishai, “Distributed point functions and their applications,” in Eurocrypt’14, Proceedings 33. Springer, 2014, pp. 640–658. [4] E. Boyle, N. Gilboa, and Y. Ishai, “Function secret sharing: Improvements and extensions,” in CCS, 2016, pp. 1292–1303. [5] B. Chor, O. Goldreich, E. Kushilevitz, and M. Sudan, “Private information retrieval,” in Proceedings of the 36th Annual Symposium on Foundations of Computer Science (FOCS). IEEE, 1995, pp. 41–50. [6] E. Kushilevitz and R. Ostrovsky, “Replication is NOT needed: SINGLE database, computationally-private information retrieval,” in Proceedings of the 38th Annual Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, 1997, pp. 364–373. [7] B. Chor and N. Gilboa, “Computationally private information retrieval (extended abstract),” in Proceedings of the Twenty-Ninth Annual ACM Symposium on the Theory of Computing, El Paso, Texas, USA, May 4-6, 1997, F. T. Leighton and P. W. Shor, Eds. ACM, 1997, pp. 304–313. [Online]. Available: https://doi.org/10.1145/258533.258609 [8] A. Goel, M. Wang, and Z. Wang, “Multiparty distributed point functions,” in Crypto’25, 2025, pp. 140–173. [9] P. Bunn, E. Kushilevitz, and R. Ostrovsky, “Cnf-fss and its applications,” in Public-Key Cryptography–PKC 2022: 25th IACR International Conference on Practice and Theory of Public-Key Cryptography, Virtual

Event, March 8–11, 2022, Proceedings, Part I. Springer, 2022, pp. 283–314. [10] A. Agarwal, E. Boyle, N. Gilboa, Y. Ishai, M. Kelkar, and Y. Ma, “Compressing unit-vector correlations via sparse pseudorandom generators,” in CRYPTO. Springer, 2024, pp. 346–383. [11] E. Boyle, N. Chandran, N. Gilboa, D. Gupta, Y. Ishai, N. Kumar, and M. Rathee, “Function Secret Sharing for Mixed-Mode and Fixed-Point Secure Computation,” in EUROCRYPT, 2021, pp. 871–900. [12] E. Boyle, N. Gilboa, and Y. Ishai, “Breaking the circuit size barrier for secure computation under DDH,” in Advances in Cryptology - CRYPTO 2016 - 36th Annual International Cryptology Conference, ser. Lecture Notes in Computer Science, M. Robshaw and J. Katz, Eds., vol. 9814. Springer, 2016, pp. 509–539. [13] Y. Dodis, S. Halevi, R. D. Rothblum, and D. Wichs, “Spooky encryption and its applications,” in CRYPTO 2016, ser. LNCS, vol. 9816. Springer, 2016, pp. 93–120. [14] E. Boyle, L. Kohl, and P. Scholl, “Homomorphic secret sharing from lattices without FHE,” in EUROCRYPT 2019, ser. LNCS, vol. 11477, 2019, pp. 3–33. [15] C. Orlandi, P. Scholl, and S. Yakoubov, “The rise of paillier: Homomorphic secret sharing and public-key silent OT,” in Advances in Cryptology - EUROCRYPT 2021 - 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, October 17-21, 2021, Proceedings, Part I, ser. Lecture Notes in Computer Science, A. Canteaut and F. Standaert, Eds., vol. 12696. Springer, 2021, pp. 678–708. [Online]. Available: https://doi.org/10.1007/978-3-030-77870-5 24 [16] L. Roy and J. Singh, “Large message homomorphic secret sharing from DCR and applications,” in CRYPTO 2022, ser. LNCS, vol. 13508, 2022, pp. 657–687. [17] E. Boyle, G. Couteau, N. Gilboa, Y. Ishai, L. Kohl, and P. Scholl, “Efficient pseudorandom correlation generators: Silent ot extension and more,” in Advances in Cryptology – CRYPTO 2019, 2019. [18] D. Abram, I. Damgård, C. Orlandi, and P. Scholl, “An algebraic framework for silent preprocessing with trustless setup and active security,” in Advances in Cryptology - CRYPTO 2022 - 42nd Annual International Cryptology Conference, CRYPTO 2022, Santa Barbara, CA, USA, August 15-18, 2022, Proceedings, Part IV, ser. Lecture Notes in Computer Science, Y. Dodis and T. Shrimpton, Eds., vol. 13510. Springer, 2022, pp. 421–452. [Online]. Available: https://doi.org/10.1007/978-3-031-15985-5 15 [19] J. C. Benaloh, “Secret sharing homomorphisms: Keeping shares of A secret sharing,” in Advances in Cryptology - CRYPTO ’86, Santa Barbara, California, USA, 1986, Proceedings, ser. Lecture Notes in Computer Science, A. M. Odlyzko, Ed., vol. 263. Springer, 1986, pp. 251–260. [Online]. Available: https: //doi.org/10.1007/3-540-47721-7 19 [20] E. Boyle, N. Gilboa, Y. Ishai, H. Lin, and S. Tessaro, “Foundations of homomorphic secret sharing,” in 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, Cambridge, MA, USA, January 11-14, 2018, ser. LIPIcs, A. R. Karlin, Ed., vol. 94. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, pp. 21:1–21:21. [Online]. Available: https://doi.org/10.4230/LIPIcs.ITCS.2018.21 [21] E. Boyle, G. Couteau, N. Gilboa, and Y. Ishai, “Compressing vector OLE,” in Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, 2018, pp. 896–912. [22] J. Doerner and A. shelat, “Scaling oram for secure computation,” in ACM-CCS, 2017, pp. 523–535. [23] E. Boyle, “The 12th Bar-Ilan winter school on advances in secure computation: Function secret sharing (part 2),” 2022. [Online]. Available: https://www.youtube.com/watch?v=Zm-MUVve2 w [24] O. Goldreich, S. Goldwasser, and S. Micali, “How to construct random functions,” Journal of the ACM (JACM), vol. 33, no. 4, pp. 792–807, 1986. [25] M. Ito, A. Saito, and T. Nishizeki, “Secret sharing scheme realizing general access structure,” Electronics and Communications in Japan (Part III: Fundamental Electronic Science), vol. 72, no. 9, pp. 56–64, 1989. [26] A. Shamir, “How to share a secret,” Communications of the ACM, vol. 22, no. 11, pp. 612–613, 1979. [27] R. Cramer, I. Damgård, and Y. Ishai, “Share conversion, pseudorandom secret-sharing and applications to secure computation,” in Theory of Cryptography Conference. Springer, 2005, pp. 342–362. [28] E. Boyle, N. Gilboa, Y. Ishai, and V. I. Kolobov, “Programmable distributed point functions,” in Annual International Cryptology Conference. Springer, 2022, pp. 121–151.

22

[29] E. Boyle, N. Gilboa, M. Hamilis, Y. Ishai, and Y. Tu, “Improved constructions for distributed multi-point functions,” in IEEE Symposium on Security and Privacy (SP), 2025, pp. 2414–2432. [30] S. Angel, H. Chen, K. Laine, and S. T. V. Setty, “PIR with compressed queries and amortized query processing,” in SP 2018, 2018. [31] P. Schoppmann, A. Gascón, L. Reichert, and M. Raykova, “Distributed vector-OLE: Improved constructions and implementation,” in Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security, 2019. [32] L. de Castro and A. Polychroniadou, “Lightweight, maliciously secure verifiable function secret sharing,” in Advances in cryptology – EUROCRYPT 2022, 2022. [33] M. Bombar, D. Bui, G. Couteau, A. Couvreur, C. Ducros, and S. ServanSchreiber, “FOLEAGE: F4 OLE-based multi-party computation for boolean circuits,” Cryptology ePrint Archive, 2024. [34] A. Agarwal, S. Raghuraman, and P. Rindal, “Fully distributed multipoint functions for PCGs and beyond,” Cryptology ePrint Archive, Paper 2025/2294, 2025. [Online]. Available: https://eprint.iacr.org/2025/2294 [35] Y. Ishai, E. Kushilevitz, R. Ostrovsky, and A. Sahai, “Batch codes and their applications,” in Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004, L. Babai, Ed. ACM, 2004, pp. 262–271. [36] M. B. Paterson, D. R. Stinson, and R. Wei, “Combinatorial batch codes,” Adv. Math. Commun., vol. 3, no. 1, pp. 13–27, 2009. [37] K. Yeo, “Cuckoo hashing in cryptography: Optimal parameters, robustness and applications,” in Advances in Cryptology - CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Santa Barbara, CA, USA, August 20-24, 2023, Proceedings, Part IV, ser. Lecture Notes in Computer Science, H. Handschuh and A. Lysyanskaya, Eds., vol. 14084. Springer, 2023, pp. 197–230. [Online]. Available: https://doi.org/10.1007/978-3-031-38551-3 7 [38] G. Garimella, B. Pinkas, M. Rosulek, N. Trieu, and A. Yanai, “Oblivious key-value stores and amplification for private set intersection,” in Advances in Cryptology - CRYPTO 2021 - 41st Annual International Cryptology Conference, ser. Lecture Notes in Computer Science, T. Malkin and C. Peikert, Eds., vol. 12826. Springer, 2021, pp. 395–425. [39] S. Raghuraman and P. Rindal, “Blazing fast PSI from improved OKVS and subfield VOLE,” in Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, CCS, H. Yin, A. Stavrou, C. Cremers, and E. Shi, Eds. ACM, 2022, pp. 2505–2517. [40] A. Bienstock, S. Patel, J. Y. Seo, and K. Yeo, “Near-optimal oblivious key-value stores for efficient psi, PSU and volume-hiding multi-maps,” in 32nd USENIX Security Symposium, J. A. Calandrino and C. Troncoso, Eds. USENIX Association, 2023, pp. 301–318. [41] E. Külaots, T. Krips, H. Eerikson, and P. Pullonen-Raudvere, “SLAMPFSS: two-party multi-point function secret sharing from simple linear algebra,” IACR Cryptol. ePrint Arch., p. 1394, 2024. [42] S. Dittmer, Y. Ishai, S. Lu, R. Ostrovsky, M. Elsabagh, N. Kiourtis, B. Schulte, and A. Stavrou, “Streaming and unbalanced PSI from function secret sharing,” in Security and Cryptography for Networks 13th International Conference, SCN 2022, Amalfi, Italy, September 1214, 2022, Proceedings, ser. Lecture Notes in Computer Science, C. Galdi and S. Jarecki, Eds., vol. 13409. Springer, 2022, pp. 564–587. [43] S. Yekhanin, “Towards 3-query locally decodable codes of subexponential length,” in Proceedings of the 39th Annual ACM Symposium on Theory of Computing (STOC ’07). ACM, 2007, pp. 266–274. [44] K. Efremenko, “3-query locally decodable codes of subexponential length,” in Proceedings of the 41st Annual ACM Symposium on Theory of Computing (STOC ’09). ACM, 2009, pp. 39–44. [45] Z. Dvir and S. Gopi, “2-server PIR with sub-polynomial communication,” in Proceedings of the 47th Annual ACM Symposium on Theory of Computing (STOC 2015). ACM, 2015, pp. 577–584. [46] B. Alon, A. Beimel, and O. Lasri, “Simplified PIR and CDS protocols and improved linear secret-sharing schemes,” in Theory of Cryptography - 22nd International Conference, TCC 2025, Proceedings, Part II, ser. Lecture Notes in Computer Science, vol. 15494. Springer, 2025, pp. 365–398. [47] E. Boyle, N. Gilboa, Y. Ishai, and V. I. Kolobov, “Information-theoretic distributed point functions,” in 3rd Conference on Information-Theoretic Cryptography (ITC 2022), ser. Leibniz International Proceedings in Informatics (LIPIcs), vol. 230. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022, pp. 17:1–17:14. [48] A. Beimel, Y. Ishai, E. Kushilevitz, and I. Orlov, “Share conversion and private information retrieval,” in Proceedings of the 27th Conference on Computational Complexity, CCC 2012, Porto, Portugal, June 26-29, 2012. IEEE Computer Society, 2012, pp. 258–268. [Online]. Available: https://doi.org/10.1109/CCC.2012.23

[49] R. Impagliazzo, L. A. Levin, and M. Luby, “Pseudo-random generation from one-way functions,” in Proceedings of the Twenty-first Annual ACM Symposium on Theory of Computing, ser. STOC ’89. New York, NY, USA: Association for Computing Machinery, 1989, pp. 12–24. [50] Z. Li, C. Xing, Y. Yao, and C. Yuan, “Efficient pseudorandom correlation generators for any finite field,” in Eurocrypt’25. Springer, 2025, pp. 145–175. [51] E. Boyle, N. Gilboa, and Y. Ishai, “Secure computation with preprocessing via function secret sharing,” in TCC’19, Part I 17. Springer, 2019, pp. 341–371. [52] S. Wagh, “Pika: Secure computation using function secret sharing over rings,” Proceedings on Privacy Enhancing Technologies, 2022. [53] N. Jawalkar, K. Gupta, A. Basu, N. Chandran, D. Gupta, and R. Sharma, “Orca: Fss-based secure training and inference with gpus,” in IEEE Symposium on Security and Privacy, SP 2024, San Francisco, CA, USA, May 19-23, 2024. IEEE, 2024, pp. 597–616. [Online]. Available: https://doi.org/10.1109/SP54263.2024.00063 [54] K. Gupta, N. Jawalkar, A. Mukherjee, N. Chandran, D. Gupta, A. Panwar, and R. Sharma, “SIGMA: Secure GPT inference with function secret sharing,” PoPETs, vol. 2024, no. 4, pp. 61–79, October 2024. [55] K. Gupta, N. Chandran, D. Gupta, J. Katz, and R. Sharma, “SHARK: Actively secure inference using function secret sharing,” in 2025 IEEE Symposium on Security and Privacy, M. Blanton, W. Enck, and C. NitaRotaru, Eds. IEEE Computer Society Press, May 2025, pp. 2472–2490. [56] N. Gilboa and D. Weber, “Lower bounds on FSS from dynamic data structures,” in 17th Innovations in Theoretical Computer Science Conference, ITCS 2026, Bocconi University, Milan, Italy, January 27-30, 2026, ser. LIPIcs, S. Saraf, Ed., vol. 362. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2026, pp. 71:1–71:22. [Online]. Available: https://doi.org/10.4230/LIPIcs.ITCS.2026.71 [57] F. Wang, C. Yun, S. Goldwasser, V. Vaikuntanathan, and M. Zaharia, “Splinter: Practical private queries on public data,” in 14th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2017, Boston, MA, USA, March 27-29, 2017, A. Akella and J. Howell, Eds. USENIX Association, 2017, pp. 299–313. [Online]. Available: https://www.usenix.org/conference/nsdi17/technical-sessions/ presentation/wang-frank [58] A. Blum, M. L. Furst, M. J. Kearns, and R. J. Lipton, “Cryptographic primitives based on hard learning problems,” in Advances in Cryptology - CRYPTO ’93, 13th Annual International Cryptology Conference, ser. Lecture Notes in Computer Science, D. R. Stinson, Ed., vol. 773. Springer, 1993, pp. 278–291. [59] M. Alekhnovich, “More on average case vs approximation complexity,” in 44th Symposium on Foundations of Computer Science, FOCS 2003, Cambridge, MA, USA, October 11-14, 2003, Proceedings. IEEE Computer Society, 2003, pp. 298–307. [60] Z. Brakerski, V. Lyubashevsky, V. Vaikuntanathan, and D. Wichs, “Worst-case hardness for LPN and cryptographic hashing via code smoothing,” in Advances in Cryptology - EUROCRYPT 2019 - 38th Annual International Conference on the Theory and Applications of Cryptographic Techniques, ser. Lecture Notes in Computer Science, Y. Ishai and V. Rijmen, Eds., vol. 11478. Springer, 2019, pp. 619– 635. [61] G. Couteau and P. Meyer, “Breaking the circuit size barrier for secure computation under quasi-polynomial LPN,” in Advances in Cryptology - EUROCRYPT 2021 - 40th Annual International Conference on the Theory and Applications of Cryptographic Techniques, ser. Lecture Notes in Computer Science, vol. 12697. Springer, 2021, pp. 842–870. [62] Q. Dao, Y. Ishai, A. Jain, and H. Lin, “Multi-party homomorphic secret sharing and sublinear MPC from sparse LPN,” in Advances in Cryptology - CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Santa Barbara, CA, USA, August 20-24, 2023, Proceedings, Part II, ser. Lecture Notes in Computer Science, H. Handschuh and A. Lysyanskaya, Eds., vol. 14082. Springer, 2023, pp. 315–348. [Online]. Available: https://doi.org/10.1007/978-3-031-38545-2 11 [63] H. Corrigan-Gibbs, A. Henzinger, Y. T. Kalai, and V. Vaikuntanathan, “Somewhat homomorphic encryption from linear homomorphism and sparse LPN,” in Advances in Cryptology - EUROCRYPT 2025 - 44th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Madrid, Spain, May 4-8, 2025, Proceedings, Part II, ser. Lecture Notes in Computer Science, S. Fehr and P. Fouque, Eds., vol. 15602. Springer, 2025, pp. 3–33. [Online]. Available: https://doi.org/10.1007/978-3-031-91124-8 1 [64] G. Couteau, N. Kumar, and X. Ye, “Multiparty homomorphic secret sharing and more from LPN and MQ,” in Theory of Cryptography 23rd International Conference, TCC 2025. Springer, 2025.

23

[65] D. Catalano and D. Fiore, “Using linearly-homomorphic encryption to evaluate degree-2 functions on encrypted data,” in ACM SIGSAC Conference on Computer and Communications Security. ACM, 2015, pp. 1518–1529. [66] R. W. F. Lai, G. Malavolta, and D. Schröder, “Homomorphic secret sharing for low degree polynomials,” in Advances in Cryptology ASIACRYPT 2018 - 24th International Conference on the Theory and Application of Cryptology and Information Security, Brisbane, QLD, Australia, December 2-6, 2018, Proceedings, Part III, ser. Lecture Notes in Computer Science, T. Peyrin and S. D. Galbraith, Eds., vol. 11274. Springer, 2018, pp. 279–309. [Online]. Available: https://doi.org/10.1007/978-3-030-03332-3 11 [67] Y. Ishai, R. W. F. Lai, and G. Malavolta, “A geometric approach to homomorphic secret sharing,” in Public-Key Cryptography - PKC 2021 - 24th IACR International Conference on Practice and Theory of Public Key Cryptography, Virtual Event, May 10-13, 2021, Proceedings, Part II, ser. Lecture Notes in Computer Science, J. A. Garay, Ed., vol. 12711. Springer, 2021, pp. 92–119. [Online]. Available: https://doi.org/10.1007/978-3-030-75248-4 4 [68] I. Dinur, N. Keller, and O. Klein, “An optimal distributed discrete log protocol with applications to homomorphic secret sharing,” in Advances in Cryptology - CRYPTO 2018 - 38th Annual International Cryptology Conference, ser. Lecture Notes in Computer Science, H. Shacham and A. Boldyreva, Eds., vol. 10993. Springer, 2018, pp. 213–242. [69] E. Boyle, N. Gilboa, and Y. Ishai, “Group-based secure computation: Optimizing rounds, communication, and computation,” in Advances in Cryptology - EUROCRYPT 2017 - 36th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Paris, France, April 30 - May 4, 2017, Proceedings, Part II, ser. Lecture Notes in Computer Science, J. Coron and J. B. Nielsen, Eds., vol. 10211, 2017, pp. 163–193. [Online]. Available: https://doi.org/10.1007/978-3-319-56614-6 6 [70] E. Boyle, G. Couteau, N. Gilboa, Y. Ishai, and M. Orrù, “Homomorphic secret sharing: Optimizations and applications,” in Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, CCS 2017, Dallas, TX, USA, October 30 - November 03, 2017, B. Thuraisingham, D. Evans, T. Malkin, and D. Xu, Eds. ACM, 2017, pp. 2105–2122. [71] N. Fazio, R. Gennaro, T. Jafarikhah, and W. E. S. III, “Homomorphic secret sharing from paillier encryption,” in Provable Security - 11th International Conference, ProvSec 2017, ser. Lecture Notes in Computer Science, T. Okamoto, Y. Yu, M. H. Au, and Y. Li, Eds., vol. 10592. Springer, 2017, pp. 381–399. [72] E. Boyle, L. Kohl, Z. Li, and P. Scholl, “Direct FSS constructions for branching programs and more from prgs with encoded-output homomorphism,” in Advances in Cryptology - ASIACRYPT, ser. Lecture Notes in Computer Science, K. Chung and Y. Sasaki, Eds., vol. 15489. Springer, 2024, pp. 266–298. [73] E. Boyle, G. Couteau, N. Gilboa, Y. Ishai, L. Kohl, and P. Scholl, “Efficient pseudorandom correlation generators from ring-lpn,” in CRYPTO’20 Part II 40. Springer, 2020, pp. 387–416. [74] E. Boyle, G. Couteau, N. Gilboa, Y. Ishai, L. Kohl, P. Rindal, and P. Scholl, “Efficient two-round OT extension and silent non-interactive secure computation,” in ACM CCS 2019, L. Cavallaro, J. Kinder, X. Wang, and J. Katz, Eds. ACM Press, November 2019, pp. 291–308. [75] Q. Tan, C. Zeng, Q. Feng, C. Peng, W. Wang, and D. He, “Gpu-accelerated dpf-based private information retrieval for largescale database,” IACR Transactions on Cryptographic Hardware and Embedded Systems, vol. 2026, no. 3, pp. –, 2026. [Online]. Available: https://tches.iacr.org/index.php/TCHES/article/view/13131 [76] D. Demmler, P. Rindal, M. Rosulek, and N. Trieu, “PIR-PSI: Scaling private contact discovery,” PoPETs, vol. 2018, no. 4, pp. 159–178, October 2018. [77] G. Garimella, M. Rosulek, and J. Singh, “Structure-aware private set intersection, with applications to fuzzy matching,” in Advances in Cryptology - CRYPTO 2022, ser. Lecture Notes in Computer Science, Y. Dodis and T. Shrimpton, Eds., vol. 13507. Springer, 2022, pp. 323–352. [78] ——, “Malicious secure, structure-aware private set intersection,” in Advances in Cryptology - CRYPTO 2023, ser. Lecture Notes in Computer Science, H. Handschuh and A. Lysyanskaya, Eds., vol. 14081. Springer, 2023, pp. 577–610. [79] G. Garimella, B. Goff, and P. Miao, “Computation efficient structureaware PSI from incremental function secret sharing,” in Advances in Cryptology - CRYPTO, ser. Lecture Notes in Computer Science, L. Reyzin and D. Stebila, Eds., vol. 14927. Springer, 2024, pp. 309– 345.

[80] D. Bui, G. Garimella, P. Miao, and V. L. P. Pham, “New framework for structure-aware PSI from distributed function secret sharing,” in Advances in Cryptology - ASIACRYPT, ser. Lecture Notes in Computer Science, G. Hanaoka and B. Yang, Eds., vol. 16249. Springer, 2025, pp. 294–326. [81] R. Ostrovsky and V. Shoup, “Private information storage,” in Proceedings of the twenty-ninth annual ACM symposium on Theory of computing, 1997, pp. 294–303. [82] H. Corrigan-Gibbs, D. Boneh, and D. Mazières, “Riposte: An anonymous messaging system handling millions of users,” in 2015 IEEE Symposium on Security and Privacy. IEEE, 2015, pp. 321–338. [83] H. Corrigan-Gibbs and D. Boneh, “Prio: Private, robust, and scalable computation of aggregate statistics,” in 14th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2017, Boston, MA, USA, March 27-29, 2017, A. Akella and J. Howell, Eds. USENIX Association, 2017, pp. 259–282. [Online]. Available: https://www.usenix.org/conference/nsdi17/technical-sessions/ presentation/corrigan-gibbs [84] D. Boneh, E. Boyle, H. Corrigan-Gibbs, N. Gilboa, and Y. Ishai, “Lightweight techniques for private heavy hitters,” in IEEE Symposium on Security and Privacy, 2021, pp. 762–776. [85] H. Davis, C. Patton, M. Rosulek, and P. Schoppmann, “Verifiable distributed aggregation functions,” PoPETs, vol. 2023, no. 4, pp. 578– 592, October 2023. [86] D. Boneh, E. Boyle, H. Corrigan-Gibbs, N. Gilboa, and Y. Ishai, “Arithmetic sketching,” in CRYPTO˜2023, Part˜I, ser. LNCS, H. Handschuh and A. Lysyanskaya, Eds., vol. 14081. Springer, Cham, August 2023, pp. 171–202. [87] I. Damgård, J. B. Nielsen, M. Nielsen, and S. Ranellucci, “The tinytable protocol for 2-party secure computation, or: Gate-scrambling revisited,” in Annual International Cryptology Conference. Springer, 2017, pp. 167–187. [88] D. Beaver, “Efficient multiparty protocols using circuit randomization,” in Advances in Cryptology - CRYPTO ’91, ser. Lecture Notes in Computer Science, J. Feigenbaum, Ed., vol. 576. Springer, 1991, pp. 420–432. [89] Y. Ishai, J. Kilian, K. Nissim, and E. Petrank, “Extending oblivious transfers efficiently,” in CRYPTO˜2003, ser. LNCS, D. Boneh, Ed., vol. 2729. Springer, Berlin, Heidelberg, August 2003, pp. 145–161. [90] E. Boyle, G. Couteau, N. Gilboa, Y. Ishai, L. Kohl, N. Resch, and P. Scholl, “Correlated pseudorandomness from expand-accumulate codes,” in Crypto’22. Springer, 2022, pp. 603–633. [91] S. Raghuraman, P. Rindal, and T. Tanguy, “Expand-convolute codes for pseudorandom correlation generators from lpn,” in Crypto 2023. Springer, 2023, pp. 602–632. [92] K. Yang, C. Weng, X. Lan, J. Zhang, and X. Wang, “Ferret: Fast extension for correlated ot with small communication,” in Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, CCS 2020. ACM, 2020, pp. 1607–1626. [93] E. Boyle, G. Couteau, N. Gilboa, Y. Ishai, L. Kohl, and P. Scholl, “Correlated pseudorandom functions from variable-density lpn,” in FOCS’20. IEEE, 2020, pp. 1069–1080. [94] D. Bui, G. Couteau, P. Meyer, A. Passelègue, and M. Riahinia, “Fast public-key silent OT and more from constrained NaorReingold,” in Advances in Cryptology - EUROCRYPT 2024 - 43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zurich, Switzerland, May 26-30, 2024, Proceedings, Part VI, ser. Lecture Notes in Computer Science, M. Joye and G. Leander, Eds., vol. 14656. Springer, 2024, pp. 88–118. [Online]. Available: https://doi.org/10.1007/978-3-031-58751-1 4 [95] L. Braun, G. Couteau, K. Melissaris, M. Riahinia, and E. Sadeghi, “Fast pseudorandom correlation functions from sparse LPN,” in Advances in Cryptology – ASIACRYPT 2025. Springer, 2025. [96] D. Beaver and J. Feigenbaum, “Hiding instances in zero-knowledge proof systems,” in Advances in Cryptology — CRYPTO ’89 Proceedings, ser. Lecture Notes in Computer Science, vol. 435. Springer, 1990, pp. 326–338. [97] R. J. Lipton, “New directions in testing,” in Distributed Computing and Cryptography, ser. DIMACS Series in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, 1991, vol. 2, pp. 191–202. [98] L. Babai, L. Fortnow, N. Nisan, and A. Wigderson, “BPP has subexponential time simulations unless EXPTIME has publishable proofs,” Computational Complexity, vol. 3, no. 4, pp. 307–318, 1993.

24

Elette Boyle is a Senior Scientist in the Cryptography and Information Security (CIS) Laboratory at NTT Research and an Affiliate Professor at Reichman University, Israel. She received her Ph.D. at MIT and B.S. at Caltech, both in Mathematics, and served as a postdoctoral fellow at Technion Israel and Cornell University. Her research centers in cryptographic solutions for safely maintaining and processing sensitive data. In particular, her recent focus has been on protocols for secure multi-party computation, as well as underlying primitives such as function and homomorphic secret sharing. Her work has been recognized by awards from the European Research Council (ERC), Israeli Science Foundation (ISF), United States Air Force Office of Scientific Research (AFOSR), Google Research Scholar Award program, and the International Association of Cryptologic Research (IACR).

Niv Gilboa is an Associate Professor of Computer Science at Ben-Gurion University, Israel. He received a Ph.D. from the Faculty of Computer Science in the Technion, and did postdoctoral work at BGU. His research interests are broadly in secure computation, with an emphasis on function secret sharing, pseudorandom correlation generators, and fully linear proof systems. His work has been funded by awards from the Israeli Science Foundation (ISF), the Israeli Ministry of Science and Technology (MOST) and the European Horizon program.

Yuval Ishai is a Professor of Computer Science at the Technion, Israel, currently on a sabbatical at AWS, whose research spans cryptography and computational complexity theory. His works were recognized by best paper awards of the FOCS 2004, Crypto 2007, and Crypto 2016 conferences, a CCS 2025 distinguished paper award, a SIAM Outstanding Paper prize, and a TCC Test of Time Award. He is a fellow of the International Association for Cryptologic Research and served as a program chair of the TCC 2011, Eurocrypt 2019, and Eurocrypt 2020 conferences.

Peter Scholl is an Associate Professor in the Cryptography & Cyber Security group at Aarhus University. He has worked extensively on developing efficient cryptographic protocols for secure multi-party computation, correlated randomness generation, zero-knowledge proofs and post-quantum cryptography. His work has been funded through a Sapere Aude award from the Independent Research Fund Denmark (DFF), as well as various projects with DARPA, the European Union and partners in industry.