Fast Bounded-Independence Functions and Their Duals∗ Martijn Brehm†
Yuval Ishai‡
Nicolas Resch§
arXiv:2606.07009v1 [cs.CR] 5 Jun 2026
June 8, 2026
Abstract We continue the study of fast functions, computable by linear-size circuits, that share useful properties of random functions. Motivated by cryptographic applications, we generalize and improve on previous results in this area, obtaining the following results: • For any constant t, we construct a fast t-wise independent hash function with algebraic degree log2 t (over F2 ), simultaneously optimizing both asymptotic circuit size and degree. • We simplify and improve a recent construction (ITCS 2026) of a family of fast codes with fast duals, both meeting the Gilbert-Varshamov bound. Unlike the previous construction, our construction has negligible failure probability, can accommodate general fields and rates, supports a systematic encoding, and admits fast universal encoders. • We strengthen the above to support stronger random-like properties, such as optimal combinatorial list-decoding. This is achieved by constructing, for any constant t, a family of fast linear functions that map any t linearly independent inputs to uniform and statistically independent outputs. Prior to our work, this was only known for t = 1. We demonstrate the usefulness of the above results to cryptography. This includes the first nontrivial protocols for perfectly secure multiparty computation whose circuit complexity scales linearly with the number of parties, as well as protocols for computing encrypted matrix-vector products with optimal asymptotic circuit complexity.
∗ This is a full version of [BIR26].
† Informatics Institute, University of Amsterdam. [email protected].
‡ Technion and AWS. [email protected]. This work is not associated with Amazon. Research supported by ISF grant 3527/24 and BSF grant 2022370. § Informatics Institute, University of Amsterdam. [email protected]. Research supported by an NWO (Dutch Research Council) grant with number C.2324.0590.
1
Contents 1 Introduction 1.1 Our Results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.2 Technical Overview . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.3 Related Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3 3 5 7
2 Preliminaries 2.1 Coding Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Computational Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Hash Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4 The q-ary XOR Lemma . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
8 8 9 10 11
3 Constructions of Fast Codes with Fast Duals 11 3.1 Fast Good Code with Fast Good Dual . . . . . . . . . . . . . . . . . . . . . . . . . . 13 3.2 Fast List-Decodable Code with Fast List-Decodable Dual . . . . . . . . . . . . . . . 15 4 Fast Bounded-Independence Functions 18 4.1 Fast t-Wise Independent Hash Functions . . . . . . . . . . . . . . . . . . . . . . . . . 18 4.2 Fast Bounded-Independence LUOF . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22 5 Cryptographic Applications 24 5.1 Fast Information-Theoretic MPC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 5.2 Fast Encrypted Matrix-Vector Product . . . . . . . . . . . . . . . . . . . . . . . . . . 27 5.3 Fast and Conservative Substitutes for Random Linear Codes . . . . . . . . . . . . . 27 5.4 MPC-Friendly t-Wise Hash Functions . . . . . . . . . . . . . . . . . . . . . . . . . . 28 A Deferred Proofs 32 A.1 Proof of Lemma 5.3 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 A.2 Analysis of Protocol 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33
2
1
Introduction
An important trend in cryptographic research is to develop cryptographic schemes realizing functionalities as efficiently as possible. Ideally, the cost of performing a task with security should be on the order of the cost of performing the same task without security. That is, security just results in a constant multiplicative computational overhead. Originating from [IKOS08], this has been the theme of a line of work on cryptography with constant computational overhead; see [BCG+ 23] and the references therein. As a concrete example, consider the task of hashing a large amount of data, where one generates a short digest from a long string. One typically wants the hash function to satisfy certain desirable properties of a random function. Ideally, the cost of performing the hashing should only scale linearly with the size of the data. Which “random-like” properties can be satisfied while achieving constant computational overhead compared to just reading the input? Similarly, one can consider the task of encoding a large vector in a way that satisfies desirable properties of a random linear code. In this case, one is sometimes also required to apply the encoding function of the dual code. Is it possible to implement both the primal and the dual encoding with constant overhead? The above hashing and encoding primitives serve as useful building blocks in many algorithmic and cryptographic applications. Minimizing their overhead is relevant to all of these applications.
1.1
Our Results
To make progress on the above questions, we provide new constructions that achieve constant computational overhead for random-like functions. This refers by default to implementations by (fan-in 2) Boolean or arithmetic circuits whose size scales linearly with the input and output length; see Section 2.2 for discussion. We refer to such an implementation as being fast. For hash functions, the work of Ishai, Kushilevitz, Ostrovsky, and Sahai [IKOS08] demonstrated the existence of fast pairwise independent hash functions with arbitrary input and output length. We first demonstrate that one can build on this result to instead obtain fast t-wise independent hash functions. That is, even after seeing t−1 hash values, the t-th value is completely unpredictable (assuming the input is distinct from the previous t−1 inputs). This result has already been discussed informally in talks by authors of [IKOS08]. Here we spell it out in detail, also achieving near-optimal algebraic degree as a function of t, which is useful for cryptographic applications. This result also acts as a nice warmup for our later results. Theorem 1.1 (Fast t-wise hash function; informal version of Theorem 4.3). For any constant t ≥ 2, finite field Fq , input length k, and output length r, there exists a construction of a fast t-wise independent hash function family H of functions h : Fkq → Frq . For q = 2, this can be done with (optimal) algebraic degree of log2 t. Fast dual codes. Partially motivated by cryptographic applications, a recent work of Brehm and Resch [BR26] constructed a family of linear codes C ≤ Fn2 of rate 1/2 with the following properties: • Both the code and its dual admit fast encoding; • With probability ≥ 1 − 1/poly(n), the code and its dual C ⊥ achieve distance ε-close to the Gilbert-Varshamov (GV) bound.
3
Recall that a code C of rate R achieves distance ε-close to the GV bound, if its (relative) −1 distance is at least h−1 q (1 − R − ε), where hq is the q-ary entropy function (and hq is its inverse); see Section 2.1 for more discussion. The GV bound captures the distance achieved by uniformly random linear codes, which is typically the best distance one could reasonably hope for. The [BR26] result was based on a rather involved analysis of a code constructed in a manner inspired by repeat-multiple-accumulate codes [DJM98]. While it provided good concrete efficiency that can be useful for applications (see Remark 1.3), this result also has several drawbacks: • The code is only constructed over the binary field F2 ; • The code (and its dual) need to have rate exactly 1/2; • The randomized construction of the code has a non-negligible failure probability; • The encoding map is not systematic (which is a problem for some applications); • The construction does not provide a fast universal circuit for encoding given both the message and the randomness defining the code. Building on the work of Druk and Ishai [DI14] (which, in turn, builds on [IKOS08]), we provide a simpler alternative construction that does not suffer from any of these drawbacks. Theorem 1.2 (Fast code with fast dual; informal version of Theorem 3.1). For any R ∈ (0, 1) and any prime power q, there is a family of codes C ≤ Fnq of rate R along with their duals C ⊥ , for which: • Both C and C ⊥ admit fast systematic encoding; • ∀ε > 0, C and C ⊥ are both ε-close to the GV bound with probability ≥ 1 − 2q −εn . Furthermore, the encoding matrices for C and C ⊥ are determined by a linear-sized universal circuit. Remark 1.3. A significant advantage of the construction from [BR26] is concrete efficiency: encoding can be done by circuits of size 12n. In contrast, the current approach involves much bigger hidden constants that we did not attempt to optimize. As an additional comment, for both constructions the encoding circuit has depth O(log n), which is asymptotically optimal in the bounded fan-in case. However, here too we expect our construction to have a much bigger hidden constant than the previous construction from [BR26]. Fast, random-like codes. By building off the concept of local similarity [MRR+ 24, GM22, MRSY25] – which informally allows one to argue that A code ensemble “behaves like” a uniformly random linear code – we can show that we can extend upon this construction, to obtain C and C ⊥ possessing stronger properties. For example, they can be proved to have very good list-decodability, up to capacity, with optimal list sizes. Recall that a code C ≤ Fnq is said to be (ρ, L)-list-decodable if for all z ∈ Fnq the number of codewords within distance ρ from z is at most L. Additionally, the rate 1 − hq (ρ) is called the list-decoding capacity: informally, it is the maximum rate at which a code can be (ρ, L)-list-decodable with any “reasonable” (i.e., sub-exponential) list-size L. We say a code is ε-close to list-decoding capacity if it has rate at least 1 − hq (ρ) − ε. Theorem 1.4 (Fast list-decodable code with fast dual; informal version of Theorem 3.2). For any R ∈ (0, 1) and any prime power q, there is a randomized procedure producing a code C ≤ Fnq of rate R for which: 4
• Both C and C ⊥ admit fast systematic encoding; • ∀ε > 0, both C and C ⊥ are ε-close to capacity, with list-size O(1/ε) with probability ≥ 1 − q −Ω(εn) . Furthermore, the encoding matrices for C and C ⊥ are determined by a linear-sized universal circuit. We comment here that list-size O(1/ε) is the best one can “reasonably” hope for, in the sense that there is no known construction of a code ε-close to list-decoding capacity with list-size o(1/ε). For context, prior work had managed to construct linear-time encodable codes with such listdecodability [GM22], and also managed to construct a code where it and its dual achieve such listdecodability [MRSY25]: getting both properties simultaneously is, to the best of our knowledge, novel. Cryptographic applications. While our results are broadly useful in any contexts in which error-correcting codes or hash functions are used, they are particularly motivated by several cryptographic applications. In the context of information-theoretic cryptography, any linear code along with a dual code can support secure multiplication in secure multiparty computation (MPC) [Mas95, CDM00]. Our results imply the first perfectly secure MPC protocols in which both the security threshold and the computational complexity (measured by Boolean circuit size) scale linearly with the number of parties. Concretely, for any constant-size function f whose inputs and outputs are owned by a constant number of parties, we get a perfectly secure n-party protocol, with a near-optimal (passive) corruption threshold of t = (1/2−ε)·n, in which the total circuit size of all parties is O(n). Our result on fast and minimal-degree t-wise hash functions can also be useful for simultaneously minimizing communication and round complexity in distributed MPC implementations. In the context of complexity-based cryptography, our work (as well as the related [BR26]) is motivated by a recent technique for computing encrypted matrix-vector products [BCH+ 25]. This technique relies on two dual codes, where one code is used for encrypting the matrix and the other is used for encrypting the vector. Our construction of fast dual codes gets around some of the limitations of the previous construction from [BR26] which are relevant to this use case. See Section 5 for details on these and other cryptographic applications.
1.2
Technical Overview
In this section, we briefly discuss how we obtain our main results. First, we recall the IKOS construction of linear-sized pairwise independent hash function [IKOS08], and then the DI construction of a linear-time encodable code getting ε-close to the GV bound [DI14], which itself builds off the IKOS construction. Firstly, the IKOS construction essentially goes as follows: 1. First, apply a fast code with large distance to the input. The alphabet for this code will be large, but constant. 2. Next, apply a (constant-sized) pairwise-independent hash function to each of the coordinates. 3. Lastly, apply an extractor for bit-fixing sources, which is obtained from the transpose of a generator matrix for a good code. In particular, one can take the transpose of the code applied
5
in the first step (this also guarantees this step is fast, thanks to a “transposition” principle – cf. Lemma 3.4). A visual depiction of this construction can be found in Figure 1. The intuition for the pairwise independence is as follows. Given two distinct inputs, the first encoding step produces codewords that have many distinct coordinates. On these distinct coordinates, the constant-sized hash functions map the coordinates to independent, uniform values. The last step then extracts from these many coordinates with independent values a single string of independent values. To get the t-wise independent hash function family, we simply have to replace the constantsized pairwise-independent hash functions by constant-sized t-wise independent hash functions. The reasoning now is very similar. Suppose now we are given t distinct inputs. If the initial code distance is good enough (greater than 1 − 1/t2 ), then in many of the coordinates all the values of the encodings will be distinct, allowing the inner hash functions to output independent, uniform randomness which can be extracted in the last step. We now turn to the constructions of the codes. Here, we make use of the concept of a linear uniform output family (LUOF), as defined in [DI14]. This is a random variable A distributed over k × r matrices such that, for any fixed nonzero vector x ∈ Fkq , xA is distributed uniformly over Frq . We recall that if A is uniformly random, then it has this property. In this work – as in [DI14] – we look for distributions over k × r matrices such that the map x 7→ xA is fast (informally, implementable by a linear-sized circuit). For brevity, we will call such an LUOF fast. The basic idea of [DI14] is to construct a fast LUOF over k × n matrices. It is relatively straightforward that this suffices for obtaining codes ε-close to the GV bound.1 To get the fast LUOF, [DI14] keep the first and third steps the same as in the IKOS construction, but instead of applying pairwise independent hash functions, they simply apply constant-sized matrices to each of the coordinates, which are viewed as length-β vectors over the base field Fq (recall the first encoding step may increase the alphabet size, but only by a constant amount). The reasoning for why this gives an LUOF is very similar. Given a nonzero message vector, the first encoding step gives many coordinates on which it is nonzero, and on these coordinates the small matrices map them to uniform values, which the final step can extract into a single uniform string, as required. Now, to get codes where both it and its dual have good distance, we look at the code with systematic encoding map x 7→ (x, xA), where now A is supported on k × r matrices. This gives a code C of block-length n := k + r and dimension k, and if A is fast, then so is the map x 7→ (x, xA). Additionally, it is easy to verify that the code defined by the encoding map y 7→ (−yA⊤ , y) is dual to C, and the transposition principle guarantees that computing y 7→ −yA⊤ is also fast. Furthermore, we show that if A is LUOF, then so is A⊤ : the crucial ingredient in this argument is Vazirani’s XOR Lemma [CGH+ 85, Rao07]. Finally, a simple argument shows then that both C and C ⊥ get ε-close to the GV bound with high probability, as desired. To consider more sophisticated properties like list-decodability, we observe that it suffices to consider the following generalization of the LUOF property. We say a random matrix A supported on k × r matrices is t-LUOF if, given t linearly independent vectors x1 , . . . , xt ∈ Fkq , the vectors x1 A, . . . , xt A are uniform and independent over Frq .2 Again, we observe that if A is a uniformly 1 Indeed, one can inspect the “standard” argument that random linear codes – i.e., codes defined by sampling a uniformly random generator matrix – get ε-close to the GV-bound with high probability, and observe that the only property one uses is that uniformly random matrices give an LUOF. 2 In this second case, we mean independent in the “stochastic” sense.
6
random matrix, then it has this property for any t ≤ k (for t > k, the concept is vacuous, as there are no sets of k + 1 or more linearly independent vectors in Fkq ). Our first observation is that, by assuming the first code of the DI construction has sufficiently good distance (> 1−1/q t ), we can obtain a t-LUOF via their construction. The argument is similar to above: now, we are given t linearly independent vectors x1 , . . . , xt , and we need to argue that in many coordinates we still have linearly independent vectors (recall that each coordinate of this first encoding step is a length-β vector). This indeed follows assuming the distance is sufficiently large. Then, on these good coordinates, the inner matrices map the linearly independent vectors to independent, uniform values, which are then extracted in the final step. Having obtained thus a t-LUOF A, we can then consider the (random) code C with encoding map x 7→ (x, xA), along with its dual defined by the encoding y 7→ (−yA⊤ , y). That we can then prove these codes achieve sophisticated properties like list-decoding then follows from the theory of local similarity, as developed in recent works [MRR+ 24, GM22, MRSY25]. Morally speaking, one observes that if one wishes to prove a code is (ρ, L)-list-decodable, then one is interested in computing quantities like P[x1 , . . . , xL+1 ∈ C], where x1 , . . . , xL+1 are all within distance ρ of some vector z. Suppose one has an argument that shows uniformly random linear codes C ′ are with high probability (ρ, L)-list-decodable, where C ′ is defined as the kernel of a uniformly random (n − k) × n matrix. In this case, we know that P[x1 , . . . , xL+1 ∈ C ′ ] = q −(n−k) dim(span{x1 ,...,xL+1 }) . One can verify that for the random C defined as above, we have P[x1 , . . . , xL+1 ∈ C ′ ] = q −(n−k) dim(span{x1 ,...,xL+1 }) , assuming A is (L + 1)-LUOF. That is, if we take t = L + 1, then we get list-decodability for C (or, more precisely, whatever list-decodability is known to hold for C ′ whp, also holds for C whp). Also, generalizing the reasoning above we can show that if A is t-LUOF, then so is A⊥ , in which case we can derive analogous list-decodability guarantees for C ⊥ .
1.3
Related Work
While we have already mentioned the papers most directly connected to our work, we now mention a few more relevant related works. Work by Gál, Hansen, Koucký, Pudlák and Viola [GHK+ 13] studies circuit sizes for encoding maps of asymptotically good codes over the binary alphabet. However, their model allows for gates with unbounded fan-in (whereas we allow only fan-in 2), and additionally they insist of small depth (constant, or log∗ n), whereas we allow for larger depth (say, O(log n)). Another related work by Li [Li26] considers the unbounded arithmetic circuit complexity (i.e., gates are arbitrary and have unbounded fan-in) of secret-sharing schemes. The main result is a demonstration that the graph underlying the circuit computing the shares for such a scheme must be a superconcentrator. Based on this fact, lower bounds on the size of such a sharing circuit are derived. A final related work is due to Fan, Li and Yang [FLY22], which builds a pairwise independent hash function with optimal size of ≈ 2n (where n is the input length) in the B2 circuit model (i.e., Boolean circuits with arbitrary fan-in 2 gates).3 Unlike the IKOS construction (and ours), their construction only yields highly compressive mappings (that is, the output length is ≈ n0.1 ), it is not perfectly pairwise independent (only statistically close), and only achieves linear size when the circuit can depend on the key (rather than having a single universal circuit of linear size that takes both the key and the input). 3 They obtain additional bounds for other circuit classes.
7
2
Preliminaries
We use N to denote the set of positive integers, and for n ∈ N we abbreviate [n] := {1, 2, . . . , n}. Throughout, q denotes a prime power, and Fq a finite field with q elements. By default, we view vectors x ∈ Fnq as row vectors. We will also use tuple notation to denote concatenation: given x ∈ Fnq and y ∈ Fm q , z = (x, y) denotes the length n + m vector such that zi = xi for i ∈ [n], and zi = yi−n for i ∈ {n + 1, . . . , n + m}. P For a distribution D over a finite set U (which itself is a function D : U → [0, 1] satisfying u∈U D(u) = 1), we denote by X ∼ D a random variable distributed according to D, i.e., for all u ∈ U , P[X = u] = D(u). For a finite set S, we write X ∼ S to denote that X is a random variable 1 if u ∈ S, and 0 otherwise. distributed uniformly at random over the set S, i.e., P[X = u] = |S| Pn n For vectors x, y ∈ Fq , their inner-product is defined as ⟨x, y⟩ := i=1 xi yi ∈ Fq . We recall that the inner-product thus defined is commutative (⟨x, y⟩ = ⟨y, x⟩), and that additionally it is linear in both arguments, e.g., ⟨αx + βy, z⟩ = α⟨x, z⟩ + β⟨y, z⟩, where also z ∈ Fnq and α, β ∈ Fq . For a subspace V ≤ Fnq , we denote its dual space by V ⊥ := {u ∈ Fnq : ∀v ∈ V, ⟨u, v⟩ = 0}, which we recall is also a subspace and has dimension dim(V ⊥ ) = n − dim(V ), and that additionally (V ⊥ )⊥ = V . and vectors x ∈ Faq and y ∈ Fbq , we always have Lastly, we recall that given a matrix M ∈ Fa×b q is the transpose of M . ⟨xM, y⟩ = ⟨x, yM ⊤ ⟩, where M ⊤ ∈ Fb×a q
2.1
Coding Theory
An Fq -linear code C is an Fq -linear subspace of Fnq for some n ∈ N. The block-length of C is the value n. If dim(C) = k, then C’s rate is R(C) := nk . Given two vectors x, y ∈ Fnq , the (relative) Hamming distance between them is d(x, y) := n1 |{i ∈ [n] : xi ̸= yi }|. Additionally, for a vector x ∈ Fnq its (relative) Hamming weight is wt(x) := n1 |{i ∈ [n] : xi ̸= 0}| = n1 |supp(x)|, where we’ve also defined the support of a vector as the set of nonzero coordinates. Note that wt(x) = d(x, 0) and that d(x, y) = wt(x−y). Because of this latter equality, for any Fq -linear code we have that the (relative) minimum distance δ(C) := min{d(c, c′ ) : c, c′ ∈ C, c ̸= c′ } is also equal to min{wt(c) : c ∈ C \ {0}}. Lastly, for a linear code C, we refer to C ⊥ as its dual code. , which is a rank-k Every Fq -linear code of dimension k admits a generator matrix G ∈ Fk×n q (n−k)×n
, matrix such that C = {xG : x ∈ Fkq }. It additionally admits a parity-check matrix H ∈ Fq which is a rank-n − k matrix such that C = {x ∈ Fnq : Hx⊤ = 0}. It follows that if H is a ⊥ parity-check matrix for C, then H is a generator matrix for Ck×k. Additionally, the matrices satisfy ⊤ is the k × k identity matrix and GH = 0. If G is of the form G = Ik | A where Ik ∈ Fq k×(n−k) Ik | A is a systematic generator A ∈ Fq , then G issaid to be systematic. Note that if G = matrix for C, then H = −A⊤ | In−k is a parity-check matrix for C, as −A ⊤ GH = Ik | A = −A + A = 0 . In−k We will also be interested in codes where the underlying alphabet is in fact a vector space over n Fq . Specifically, for β ∈ N we will refer to an Fq -subspace C ≤ Fβq as an Fq -additive code k β , and we define its over Fq . The block-length is still n, while the rate of such a code is now βn minimum distance with respect to the alphabet Fβq . That is, given a codeword c ∈ C, writing it as c = (c(1) , . . . , c(n) ) with each c(i) ∈ Fβq , we define wtβ (c) := n1 |{i ∈ [n] : c(i) ̸= 0}|, and then 8
δ(C) := min{wtβ (c) : c ∈ C \ {0}}. Note that all Fq -additive codes over Fβq admit a generator matrix G of size k × βn. We often deal not with a single code C, but rather with an infinite family of codes {Ci }i≥1 for an increasing sequence of block-lengths ni ∈ N, each with dimension {ki }i≥1 and distance {δi }i≥1 . The rate of the family of codes can then be defined as R := lim inf i→∞ ki /ni and the relative distance as δ := lim inf i→∞ δi . We call a family of codes asymptotically good whenever both R > 0 and δ > 0. We assume the field Fq is the same within a family. The q-ary Gilbert-Varshamov bound gives a lower bound on the asymptotic relative distance δ given the rate R for a family of codes over Fq . In particular, it represents the minimum distance achieved by uniformly random (linear) codes (defined, e.g., by sampling a uniformly random generator matrix). Its definition makes use of the q-ary entropy function hq : [0, 1 − 1/q] → [0, 1], which itself is defined as 1 1 hq (x) := x logq (q − 1) + x logq + (1 − x) logq x 1−x for x ∈ (0, 1 − 1/q] and hq (0) = 0 at the left endpoint. This function increases continuously on its domain, and therefore admits a continuous inverse h−1 q : [0, 1] → [0, 1−1/q]. The Gilbert-Varshamov (GV) bound states that there exist codes of distance ≥ δ and rate ≥ 1 − hq (δ). In other words, −1 codes of rate R can achieve distance ≥ h−1 q (1 − R). If a rate R code achieves distance hq (1 − R − ε) for some ε > 0, we will say that it is ε-close to the GV bound. We recall that uniformly random codes are ε-close to the GV bound with probability ≥ 1 − q −εn . Lastly, we recall the concept of list-decodability. For ρ ∈ (0, 1 − 1/q) and L ∈ N, we say that a code C ⊆ Σn (for an arbitrary finite alphabet Σ) is (ρ, L)-list-decodable if, for all z ∈ Σn , we have |{c ∈ C : d(c, z) ≤ ρ}| ≤ L . It is known codes of rate R can achieve decoding radius ρ so long as ρ < h−1 q (1 − R). More precisely, there exist codes of rate 1 − hq (ρ) − ε that are (ρ, O(1/ε))-list-decodable; however, any code of rate 1 − hq (ρ) + ε is not (ρ, L)-list-decodable for any L ≤ q o(n) . For this reason, 1 − hq (ρ) is called list-decoding capacity. We will say that a code is ε-close to list-decoding capacity if it has rate 1 − hq (ρ) − ε. It is known that there exist codes ε-close to list-decoding capacity with list-size O(1/ε); in fact, random linear codes achieve this with high probability [GHK11, LW20]. Furthermore, it is not known if codes ε-close to list-decoding capacity exist with list-size o(1/ε); thus, hoping for list-size O(1/ε) is a reasonable target.
2.2
Computational Model
We will be interested in encoding functions and hash functions that admit “fast” algorithms. This refers by default to having a uniform family of linear-size arithmetic circuits, but can also refer to other computational models in which Spielman’s error correcting codes can be implemented in linear time. See [Spi96] for discussion. More concretely, our default complexity measure refers to the size of an arithmetic circuit over a finite field Fq . Wires carry field elements into gates. Gates have two input wires and output the addition, multiplication or subtraction of the incoming field elements. We allow gates to have arbitrary fan-out. We also allow gates with a fan-in of 0, which represent either an input variable, a constant scalar, or (for randomized circuits) an independently uniformly random value from Fq . We will typically consider linear circuits in which one of the inputs for each multiplication gate is a scalar 9
The size of the circuit is defined as the number of wires, the depth as the length of the longest path from an input to an output, and the algebraic degree as the highest (total) degree of an output as an Fq -polynomial in the inputs. We consider infinite families of circuits Ck over Fq where Ck has k input variables. We consider uniform families, which means there is a polynomial time algorithm that maps 1k to a description of Ck . We call a function f : Fkq → Frq fast if there exists a uniform circuit family Ck which computes f , where each Ck has size O(k). We will sometimes apply this notion also to families of randomized functions computed by randomized circuits. Finally, for a family of linear functions, we assume by default that the family of linear-size circuits are linear in the sense defined above.
2.3
Hash Functions
First, we recall the definition of a hash function with bounded independence. Definition 2.1 (t-wise independent hash function). Let q, k, r ∈ N and let H denote a distribution over functions from [q]k → [q]r . We say that H is a t-wise independent hash function family if, for all x1 , . . . , xt ∈ [q]k distinct, we have, over H ∼ H, (H(x1 ), . . . , H(xt )) ∼ [q]rt . In other words, for all y1 , . . . , yt ∈ [q]r it holds that " t # ^ P H(xi ) = yi = q −rt . i=1
We recall the following classical construction of t-wise independent hash functions, based on degree ≤ (t − 1)-polynomials [CW79, Vad12]. Proposition 2.2 (Construction of t-wise independent hash functions). Let q be a prime power, let β ∈ N with q β ≥ t, and let H denote the uniform distribution over functions Fqβ → Fqβ of Pt−1 the form h(x) = i=0 hi xi . That is, the domain and range are interpreted as the finite field with q β elements, and the sampled functions are all degree ≤ (t − 1) polynomials. Then H is a t-wise independent hash function family. Observe that sampling according to H as defined above requires tβ log2 q bits of uniform randomness. By considering the entropy of the resulting distribution (H(x1 ), . . . , H(xt )), this is optimal, as the uniform distribution over Fβ·t q has entropy βt log2 (q), and by the data-processing inequality entropy cannot increase. In particular, if H only ever output functions represented by polynomials of degree ≤ t′ − 1 with ′ ′ t < t, then H would be supported on a set of size ≤ q βt , and therefore H would have entropy ′ at most log q βt = βt′ log(q), a contradiction to the above. Hence, guaranteeing that every hash function has degree ≤ t − 1 as a polynomial over Fqβ is optimal. However, we can also think of the functions as being maps from Fβq → Fβq – that is, inputs and outputs are length-β vectors with coordinates in Fq – then the functions can be chosen to have smaller degree. That is, one can fix an Fq -linear isomorphism Fβq → Fqβ such that, under this identification, the function t−1 X F : Fqβ → Fqβ , x 7→ Fi · xi i=0
10
is represented by a function G = (G1 , . . . , Gβ ) : Fβq → Fβq where each Gj has degree ≤ (q − 1) logq (t) [BC12, Section 2]. More precisely, one can bound the degree of each Gj by max{|i|q : Fi ̸= 0} , Pβ−1 where we’ve defined |i|q as j=0 xj where i = j=0 xj q j . In other words, it is the sum of the coordinates in the base-q expansion of i. Thus, we can have t-wise independent hash functions with degree (q − 1) logq (t): if i ≤ t − 1, one can verify that |i|q ≤ (q − 1) logq (t). When q = 2, this bound is just log2 (t). We record this fact below. Pβ−1
Lemma 2.3. Let q be a prime power and let β ∈ N with q β ≥ t. There exists a t-wise independent hash function family H of functions from Fβq → Fβq such that every function h ∈ supp(H) has algebraic degree ≤ (q − 1) logq (t).
2.4
The q-ary XOR Lemma
Finally, we record a useful lemma, sometimes referred to as Vazirani’s XOR Lemma [CGH+ 85]. We will use the generalization to larger fields, for which a proof can be found in Rao’s exposition of Bourgain’s 2-source extractor [Rao07, Lemma 4.2]. In fact, we just need the ε = 0 version of that statement, which results in the following. Lemma 2.4. Let x be a random vector distributed over Fnq . Then x ∼ Fnq if and only if for all ξ ∈ Fnq \ {0}, ⟨ξ, x⟩ ∼ Fq . In words: in order to test if a random vector is uniform over Fnq , it suffices to check that its inner-product with each (fixed) non-zero vector is uniform over Fq .
3
Constructions of Fast Codes with Fast Duals
In this section we concern ourselves with the construction of a “fast good code” with a “fast good dual,” as coined by [BR26]. These are pairs of linear codes that are dual to each other, that are both fast, and that are both asymptotically good with a rate-distance tradeoff at the GV-bound. Applications of such a pair of objects include protocols for information-theoretic secure multiparty computation (MPC) and encrypted matrix vector products with asymptotically optimal circuit size, as we discuss further in Section 5. Recalling from the introduction, such a pair of codes was first given by [BR26], but their construction had a number of downsides, like being restricted to binary alphabets and both codes needing to have rate 1/2. We present a new such construction in Section 3.1 which amends the five drawbacks described in the introduction. The construction relies on a fast linear uniformoutput family (LUOF), a distribution over matrices A such that xA is uniform for any nonzero x (see Definition 3.3). The properties of this new construction are summarized in the following theorem. When we refer to a map as being systematic we mean that it maps an input vector x to an output vector of the form (x, y) or (y, x), i.e. the output vector contains the input vector. Theorem 3.1. Let q be a prime power and fix R, ε ∈ (0, 1) with ε < min{R, 1 − R}. There i ni exist uniform families of randomized linear arithmetic circuits {Ci : FR → Fnq i }i∈N and {Ci⊥ : q (1−R )n
i i Fq → Fnq i }i∈N , where (ni )i∈N is an increasing sequence of positive integers and (Ri )i∈N is a sequence of real numbers with each Ri ni ∈ N, satisfying the following properties.
11
• Rate: limi→∞ Ri = R (and hence limi→∞ (1 − Ri ) = 1 − R). i ni • Efficient encodability: For each i ∈ N, Ci : FR → Fnq i is of size O(ni ) with O(ni ) q uniformly random field elements. The map is systematic.
(1−R )n
i i • Dual efficient encodability: For each i ∈ N, Ci⊥ : Fq → Fnq i of size O(ni ) with O(ni ) uniformly random field elements. The map is systematic.
• Good distance: For each i ∈ N, let Ci denote the random code with encoding map determined by Ci , where the randomness is over the internal randomness of the circuit. Then Ci −εni has rate Ri and distance h−1 (GV-bound). q (1 − Ri − ε) except with probability q • Good dual distance: For each i ∈ N, let Ci⊥ denote the random code with encoding map determined by Ci⊥ , where the randomness is over the internal randomness of the circuit. Then −εni Ci⊥ has rate 1 − Ri and distance h−1 (GV-bound). q (Ri − ε) except with probability q • Duality: For each i ∈ N, the codes Ci and Ci⊥ are dual to one another, assuming the encoder circuits use the same randomness. The distance analysis of these codes is much simpler than that of the construction of [BR26]. This gives a better prospect of generalizing to other properties; to prove that our code construction doesn’t just generate a “fast good code” with “fast good dual,” but a code with additional interesting properties. We indeed manage to do so, and in Section 3.2 prove that our construction yields a pair of codes that additionally are t-locally similar to a random linear code (albeit, at some cost in terms of parameters). Intuitively, this means that any t-local property of random linear codes also applies to this pair of codes, which are features that can be ruled out by a small, size t subset of vectors. This includes distance (t = 1) and list-of-L-decodability (t = L + 1). Note that this generalizes the construction from the first subsection, which we leave mostly as a warm-up. We conclude with the following result, which, to the best of our knowledge, is the first (randomized) construction of a code achieving list-decoding capacity with fast (linear-size) encoding. This holds for both the code we construct and its dual. In fact, the codes we construct have the best-known list-size of L = O(1/ε). Theorem 3.2. Let q be a prime power and fix R, ε ∈ (0, 1). There is a c > 0 such that, assuming min{1 − R − cε, R − cε} > 0, the following holds. There exist uniform families of randomized (1−Ri )ni i ni → Fnq i }i∈N , where (ni )i∈N → Fnq i }i∈N and {Ci⊥ : Fq linear arithmetic circuits {Ci : FR q is an increasing sequence of positive integers and (Ri )i∈N is a sequence of real numbers with each Ri ni ∈ N, satisfying the following properties. • Rate: limi→∞ Ri = R (and hence limi→∞ (1 − Ri ) = 1 − R). i ni • Efficient encodability: For each i ∈ N, Ci : FR → Fnq i is of size O(ni ) with O(ni ) q uniformly random field elements. The map is systematic.
(1−R )n
i i • Dual efficient encodability: For each i ∈ N, Ci⊥ : Fq → Fnq i of size O(ni ) with O(ni ) uniformly random field elements. The map is systematic.
• Good list-decodability: For each i ∈ N, let Ci denote the random code with encoding map determined by Ci , where the randomness is over the internal randomness of the circuit. Then −Ω(ni ) Ci has rate Ri and is (h−1 q (1 − Ri − cε), ⌈1/ε⌉)-list-decodable except with probability q (list-decoding capacity). 12
• Good dual list-decodability: For each i ∈ N, let Ci⊥ denote the random code with encoding map determined by Ci⊥ , where the randomness is over the internal randomness of the circuit. Then Ci⊥ has rate 1 − Ri and is (h−1 q (Ri − cε), ⌈1/ε⌉)-list-decodable except with probability q −Ω(ni ) (list-decoding capacity). • Duality: For each i ∈ N, the codes Ci and Ci⊥ are dual to one another, assuming the encoder circuits use the same randomness.
3.1
Fast Good Code with Fast Good Dual
Our construction for a “fast good code” with “fast good dual” is based on an object known as a linear uniform output family. This is any matrix A which maps any fixed non-zero input vector to a uniformly random vector in the output space. Definition 3.3. (Linear Uniform Output Family, LUOF) Let A be a random matrix distributed over Fk×r . We call A a linear uniform output family (LUOF) if, for all x ∈ Fkq \ {0}, we have q r xA ∼ Fq . Classical constructions of LUOF, such as the family of Toeplitz matrices, require circuits of quasilinear size. Here we use the fast (i.e., linear-size universal circuit) LUOF construction of Druk and Ishai [DI14], which works over any finite field Fq and for any choice of k and r. This LUOF itself as a generator can be used to construct a fast good code: simply use the LUOF A ∈ Fk×n q matrix for a linear code. Since the LUOF is fast, so is the code. The code also is asymptotically good, with rate-distance tradeoff at the GV-bound, which follows in a standard way from the fact that each message is mapped to a uniformly random vector in the output space. We briefly recall this argument as we will use a similar argument for our code constructions. The probability the code attains some distance δ can then (by a union bound) be upper bounded by the probability that any message attains weight at most δ, times the number of messages. Since each message ends up as a uniformly random output vector, the probability it has weight at most δ is equal to the number of weight at most δ output vectors divided by the size of the output space: q n·hq (d/n)−n , where hq is the q-ary entropy function. Multiplying by the number of messages q k gives an upper bound on the probability the code attains distance δ of q n(hq (δ)−1+k/n) , which is q −Ω(n) (negligible in n) whenever k/n < 1 − hq (δ). This tradeoff between the rate R := k/n and distance δ is exactly the q-ary GV-bound. The fast LUOF of Druk and Ishai thus generates a fast good code. But the authors note that the dual of any code generated by a LUOF likewise is good: it also attains the GV-bound. However, it is not clear what the encoding function of such a dual code looks like, and in particular, whether this dual code is fast. We now give a slightly more complicated code construction which does explicate what the dual code looks like, and indeed lets us guarantee that the dual code is fast. Instead of having the primal code be generated by a k × n LUOF, we suppose that we have a k × r LUOF called A. We then consider the linear maps x 7→ (x, xA) and x 7→ (−xA⊤ , x). These are implemented by the generator matrices G = [Ik |A] and H = [−A⊤ |Ir ]. Here, Ik and Ir are the k × k and r × r identity matrices. Note that G is a k × (r + k) matrix and H is a r × (r + k) matrix. Let us write n := r + k for the block length, so that the primal code generated by G has rate k/n and the dual code generated by H has rate (n − k)/n. We now claim that G is a fast good code with a fast good dual H satisfying the properties listed in Theorem 3.1. We spend the rest of this subsection verifying each of the properties listed in this theorem. 13
Proof of Theorem 3.1. To start, we can choose G to have any rate R ∈ (0, 1), the codes G and H clearly have systematic encoding maps, and G and H generate dual codes as H is the parity-check matrix of G: −A ⊤ GH = [Ik | A] = −Ik A + AIr = −A + A = 0 . Ir The two harder properties that remain are the fact that G and H admit fast encoding maps (arithmetic circuits of linear size in the input) and attain the GV-bound. Starting with the fast encoding maps, recall that that xG = (x, xA) and that xH = (−xA⊤ , x). Copying x and applying a minus sign can of course both be done fast. If we sample the LUOF A according to the construction of [DI14], then computing xA is fast too. From this fact it actually follows that computing xA⊤ is fast too: Lemma 3.4 (Transposition principle [Bor56]). There exists a constant c4 > 0 such that for every finite field F the following holds. Let C be an arithmetic circuit over F of size t which consists of only addition and scalar multiplication gates and computes the function f (x) = xA (where xA is a matrix-vector product). Then there exists an arithmetic circuit C ′ of size at most c4 t that computes the function f ′ (x) = xA⊤ . All that remains is to show that G and H attain the GV-bound. We start with the code G, which we recall encoded a vector x to (x, xA). What we need to show is that the probability that −εn G fails to have distance h−1 , where we recall that n is q (1 − R − ε) for some ε > 0 is at most q the block length of G. Since our code is linear, this event is equivalent to G having a codeword of weight at most h−1 q (1 − R − ε). There are at most q nhq (δ) length n vectors of weight at most δ. Recall the earlier high-level proof that a random linear code attains the GV-bound (in fact, any generator matrix that is a LUOF). There, we could argue that any message vector is mapped to a uniformly random output vector, so that any specific vector y ∈ Fnq is in the code with probability q k−n : there are q k messages, and each has a probability of q −n of being mapped to a some specific output vector. Applying a union bound over all bad codewords (with weight below the target d) yields an upper bound on the probability that such a code fails to have distance δ: q nhq (δ)+k−n = q n(hq (δ)−1+k/n) = q n(hq (δ)−1+R) = q n(1−R−ε−1+R) = q −εn , where in the last step we substituted in our target distance of δ = h−1 q (1 − R − ε). Now, we cannot directly apply this reasoning to our code, as our code does not map each message to a uniformly random output vector. The first k entries of our output will be a copy of the message, and only the last r entries will be uniformly random. However, it is not hard to see that we can derive the same upper bound of q k−n = q −r on the probability that a given vector y ∈ Fnq is in our code C. This then immediately yields the GV-bound by the above derivation. Recall that y ∈ C whenever yH ⊤ = 0 where H = [−A⊤ |Ik ] is the parity-check matrix of C. Let us split up y = (y (1) , y (2) ) with y (1) ∈ Fkq and y (2) ∈ Frq . Then we can write h i h i P [y ∈ C] = P yH ⊤ = 0 = P y (2) − y (1) A = 0 = P y (2) = y (1) A ≤ q −r , where the last step is because A is a LUOF, so that the output y (1) A is uniformly random over Frq if y (1) ̸= 0; if y (1) = 0, then y (2) ̸= 0 (since y = (y (1) , y (2) ) ̸= 0), so then P y (2) = y (1) A = 0. Thus, in our code we obtain the same (upper bound on the) probability that a given codeword is in our 14
code as we had above for a random linear code. It follows that we obtain the exact same bound on the probability that our code achieves distance d, and hence we recover the GV-bound. It remains to prove that the dual code, generated by H with the linear map x 7→ (−xA⊤ , x), also attains the GV-bound. To do this, we prove Lemma 3.5 just below which states that if A is a LUOF, then −A⊤ is also a LUOF. The proof that H achieves the GV-bound is then analogous to that of G, establishing the theorem. Lemma 3.5. Let r, k ∈ N. Let A be a random matrix distributed over Fk×r . If A is LUOF, then q so is −A⊤ . Proof. It is immediate that if A is LUOF, then so is −A. Thus, it suffices to prove that if A is LUOF, then so is A⊤ . That is, we must show that for all x ∈ Frq \ {0}, we have xA⊤ ∼ Fkq . By Lemma 2.4, it suffices to prove that for all ξ ∈ Fkq \ {0}, we have ⟨ξ, xA⊤ ⟩ ∼ Fq . Now, ⟨ξ, xA⊤ ⟩ = ⟨ξA, x⟩. Since ξ ̸= 0 and A is LUOF, we know that ξA ∼ Frq , so now by the other direction of Lemma 2.4 we have ⟨ξA, x⟩ ∼ Fq , as desired.
3.2
Fast List-Decodable Code with Fast List-Decodable Dual
We now generalize the previous construction to yield not just a “fast good code” with “fast good dual”, but codes that are in addition t-locally similar to a random linear code. We won’t define t-local similarity formally, which would require some additional definitions. Instead, we make use of Proposition II.8 of [MRSY25] (a result which was implicit in earlier works [MRR+ 24, GM22]) which states that a code is t-locally similar to a random linear code whenever any selection of t linearly independent vectors are in C with probability at most q −n(1−R)t , where R is the rate, q is the field size and n is the block length.4 We will establish that (a slight generalization of) our code construction satisfies this property. As explained in the introduction to this section, this roughly implies that our code shares with random linear codes all features that can be ruled out by size t subsets of vectors. Our goal will be to show that our code construction yields a pair of codes that have good list-decodability. Recall that a code C ⊆ Fnq is (ρ, L)-list-decodable if for all z ∈ Fnq , |{c ∈ C : d(c, z) ≤ ρ}| ≤ L. Observe that proving a code C is (ρ, L)-list-decodable amounts to showing that certain sets of vectors of size L are not contained in C: in this specific case, the vectors that must be shown to not lie in C are all L + 1-subsets of some Hamming ball of radius ρ. This aligns exactly with the intuitive idea that a local property is one that can be ruled out by a small set of vectors. Proposition II.9 of [MRSY25] makes this precise by showing that any linear code that is t-locally similar to a random linear code has good list-decodability. We state it in full below. Proposition 3.6. Let q be a prime power. Let k, n, L ∈ N, let R = k/n and let ε > 1/(L + 1). For n sufficiently large compared to L, there exists a constant c > 0 such that the following holds. n If ρ = h−1 q (1 − R − cε) and C ≤ Fq is a random code of rate R that is (L + 1)-locally similar to a random linear code, then with probability at least 1 − q −ε(n−on→∞ (1)) , C is (ρ, L)-list-decodable. We note that the maximum radius up to which one can hope to list-decode is h−1 q (1 − R − ε), and existentially at radius h−1 (1 − R − ε) lists of size O(1/ε) are sufficient. Thus, if we can prove q 4 Note that this result requires
n ≥ ωn→∞ (q 2t ), i.e. logq n
q and t.
15
the block length needs to be large enough compared to
that our codes are t-locally similar to random linear codes, they essentially obtain the best-known list-decodability. We now turn to proving this, thereby establishing Theorem 3.2. We recall once more that to prove t-local similarity it suffices to prove that any choice of b ≤ t linearly independent vectors are in the codes with probability at most q −n(1−R)b . Our original code construction used a fast LUOF which guaranteed that any fixed non-zero input vector is mapped to a uniformly random output vector. This property is not sufficient for our current purposes, as it doesn’t guarantee that multiple distinct inputs are mapped to uniform outputs independently. To obtain this guarantee, we generalize the notion of a LUOF. Instead of requiring a single non-zero input to be mapped to a uniform random output, we require t linearly independent inputs to be mapped to uniformly and independent outputs. Definition 3.7. Let t, r, k ∈ N. Let A be a random matrix distributed over Fk×r . We call A a q t-wise linear uniform output family (t-LUOF) if, for all x1 , x2 , . . . , xt ∈ Fkq linearly independent, we have (x1 A, x2 A, . . . , xt A) ∼ Ftr q . That is, the collection of random variables xi A for i ∈ [t] are all uniform over Frq , and independent. Remark 3.8. Note that if a random matrix is t-LUOF, then it is also s-LUOF for any s ≤ t. Indeed, sr if (x1 A, x2 A, . . . , xt A) ∼ Ftr q , then also (x1 A, x2 A, . . . , xs A) ∼ Fq . In Section 4.2 we will show that the DI construction of a fast LUOF can be generalized to yield a fast t-LUOF as well. For now, we show that our code construction, set up with a t-LUOF instead of a 1-LUOF, gives us t-local similarity. Or more specifically, we prove that our construction yields a fast list-decodable code with fast list-decodable dual, as described in Theorem 3.2. Proof of Theorem 3.2. We use the codes G and H according to the code construction outlined in Section 3.1, but instead of using the fast 1-LUOF of [DI14], we use the fast t-LUOF which we construct in Section 4.2. We recall that proof of Theorem 3.1 in that same subsection which shows us that these codes are dual, can be of any rates (as long as they sum to 1, of course), and have fast, systematic encoding maps. But now, instead of proving good distance, we need to argue that our codes are t-locally similar to random linear codes, for which we recall it suffices to show that any choice of b ≤ t linearly independent vectors are in the codes with probability at most q −n(1−R)b . Note that R = k/n and n = k + r, so that n(1 − R) = n(1 − k/n) = n − k = r. The probability upper bound then becomes q −rb . We now show that G and H indeed have probability ≤ q −rb that any fixed selection of b nonzero and linearly independent vectors is in our code, establishing the required list-decodability by Proposition 3.6. This will require not just that A is t-LUOF, but that A⊤ is t-LUOF as well, which we establish in Lemma 3.9. Then, in Lemma 3.10 we show that G satisfies the earlier probability bound. A completely analogous proof establishes this result for H, which in turn completed the proof of our theorem. Lemma 3.9. Let t, r, k ∈ N. Let A be a random matrix distributed over Fk×r which is t-LUOF. q Then A⊤ is also t-LUOF. Proof. We must show that for all ξ1 , . . . , ξt ∈ Frq linearly independent, we have (ξ1 A⊤ , . . . , ξt A⊤ ) ∼ tk ⊤ ⊤ Ftk q . By Lemma 2.4, it suffices to argue that for any x ∈ Fq \ {0}, we have ⟨x, (ξ1 A , . . . , ξt A )⟩ ∼ Fq . Write x = (x1 , . . . , xt ) with each xi ∈ Fkq , then we need to argue ⟨x, (ξ1 A⊤ , . . . , ξt A⊤ )⟩ =
t X i=1
16
⟨xi , ξi A⊤ ⟩ =
t X ⟨ξi , xi A⟩ i=1
is uniform. Fix a basis {yi : i ∈ [s]} for the space span{xi : i ∈ [t]}, and note Ps that s ≥ 1 since we assumed that not all the xi ’s are 0. We can (uniquely) write each xi = j=1 xij yj with the xij ∈ Fq . So then + * s * t + t t t X s s X X X X X X ⟨ξi , xi A⟩ = ξi , xij yj A = xij ⟨ξi , yj A⟩ = xij ξi , yj A . i=1
i=1
j=1
i=1 j=1
j=1
i=1
Now, since y1 , . . . , ys are linearly independent, we know that y = (y1 A, . . . , ys A) ∼ Fsr q . Considering P Pt t now the vector ξ = i=1 xi1 ξi , . . . , i=1 xis ξi , if we show that it is nonzero, then by Lemma 2.4 we will conclude that * t + s X X xij ξi , yj A = ⟨ξ, y⟩ ∼ Fq , j=1
i=1
as Ptrequired. So, we must show ξ ̸= 0. That is, we must show that Ptfor some j ∈ [s], we have i=1 xij ξj ̸= 0. Since ξ1 , . . . , ξt are linearly independent, we have i=1 xij ξi = 0 ⇐⇒ x1j = x2j = · · · = xtj = 0; this implies that we just must show some xij ̸= 0. To see this is true, note that some xi ̸= 0, and so since the yi ’s form a basis that means some xij ̸= 0, as desired. Lemma 3.10. Let b, t, r, k ∈ N with b ≤ t, and let A be a random matrix distributed over Fk×r q which is t-LUOF. Consider systematic linear code C := {(x, xA) : x ∈ Fkq }, which has block-length n := k + r. Then, for all x1 , . . . , xb ∈ Fnq linearly independent, we have P [∀j ∈ [b], xj ∈ C] ≤ q −rb . Proof. Since C is generated by G = Ik | A , it is checked by the matrix H = −A⊤ | Ir . Note that, for all x ∈ Fnq , xH ⊤ = x(2) − x(1) A, where x = (x(1) , x(2) ) with x(1) ∈ Fkq and x(2) ∈ Frq . Hence, P [∀j ∈ [b], xj ∈ C] = P ∀j ∈ [b], xj H ⊤ = 0 h i h i (2) (1) (1) (2) = P ∀j ∈ [b], xj − xj A = 0 = P ∀j ∈ [b], xj A = xj (1) (1)
(1)
Let us first consider the case that x1 , . . . , xb are linearly independent. Then, it follows directly from the fact that A is t-wise LUOF (and hence, b-wise LUOF, since b ≤ t) that the vector (1) (1) (x1 A⊤ , . . . , xb A⊤ ) is distributed uniformly over Fbr q , and hence the probability it takes on the (2)
(2)
value (x1 , . . . , xb ) is q −rb . Hence, h i (1) (1) (2) (2) (1) = P (x1 A⊤ , . . . , xb A⊤ ) = (x1 , . . . , xb ) = q −rb . (1)
(1)
Let us now consider the case that x1 , . . . , xb are linearly dependent. Fix j ∗ ∈ [b] minimal such (1) (1) (1) that xj ∗ ∈ span{x1 , . . . , xj ∗ −1 } (note that we could have j ∗ = 1, where we’ve used the convention Pj ∗ −1 (1) (1) that span(∅) = {0}). Thus, there exist multipliers λ1 , . . . , λj ∗ −1 ∈ Fq such that xj ∗ = i=1 λi xi (again, if j ∗ = 1, this is just the empty sum, which has value 0). We have h i (1) (2) (1) ≤ P ∀j ∈ [j ∗ ], xj A⊤ = xj We claim the above probability is 0, which certainly establishes the required bound (1) ≤ q −rb . 17
To see this term is 0, we write h i (1) (2) P ∀j ∈ [j ∗ ], xj A⊤ = xj h i h i (1) (2) (1) (2) (1) (2) = P xj ∗ A⊤ = xj ∗ ∀i < j ∗ , xi A⊤ = xi · P ∀i < j ∗ , xi A⊤ = xi (1)
(2)
Note that the event ∀i < j ∗ , xi A⊤ = xi does indeed have nonzero probability: if j ∗ ≥ 2, as (1) (1) the vectors x1 , . . . , xj ∗ −1 are linearly independent and A⊤ is (j ∗ − 1)-LUOF, the above argument ∗ shows this event has probability q −r(j −1) , while if j ∗ = 1 we condition on the empty event, which has probability 1. (1) (2) Now, conditioned on the event ∀i < j ∗ , xi A⊤ = xi , we have ∗ ∗ ∗ jX −1 jX −1 jX −1 (1) ⊤ (1) ⊤ (1) ⊤ (2) xj ∗ A = λi xi A = λ i xi A = λi xi . i=1 (1)
(2)
Thus, if xj ∗ A⊤ = xj ∗ , then also
i=1
Pj ∗ −1 i=1
(2)
λ i xi
(1) (2) xj ∗ = (xj ∗ , xj ∗ ) =
i=1
(2)
= xj ∗ , which then means that
∗ jX −1
(1) (2) λi (xi , xi ) =
i=1
∗ jX −1
λ i xi .
i=1
Since the x1 , . . . , xb were assumed linearly independent, this cannot happen. So the probability is 0, as desired.
4
Fast Bounded-Independence Functions
In this section we extend previous results from [IKOS08, DI14] on hash functions and linear codes by considering a higher independence parameter t.
4.1
Fast t-Wise Independent Hash Functions
In this section we prove that, with minor modifications, the IKOS construction [IKOS08] can yield t-wise independent hash functions. This generalized variant is still fast as long as t is constant. We summarized the IKOS construction for pairwise independent hash functions (t = 2) in Section 1.2. We now briefly recall that the construction consisted first of an encoding step (determined by code with very good distance over a larger alphabet); then, constant-sized hash functions are applied to the coordinates of the encoding; lastly, an extraction step (implemented by the transpose of a generator matrix for a good code) is applied. To generalize this to t-wise independence, the first natural change that one must make is that the small, constant-sized hashes h1 , . . . , hm should now be sampled so as to be t-wise independent (where m is the block-length of the first code), which we can naturally do (and, assuming t = O(1), this will only affect the circuit-size by a constant factor). Now, recalling the proof of pairwise independence for the IKOS construction, the good distance of the first code guaranteed that, in many coordinates, the encodings of the two distinct inputs will be different. That is, if the code’s distance was 1 − ε, that exactly means that in at least a 1 − ε fraction of coordinates, the encodings will differ. 18
For t-wise independence, we are given t inputs x1 , . . . , xt , and in order to use the t-wise independence of the little hashes h1 , . . . , hm , we need many coordinates ℓ ∈ [m] in which all the encodings differ. In this case, an averaging argument will establish this holds in at least a 1 − 2t · ε fraction of coordinates. Thus, so long as ε > 0 is chosen small enough (which can be done at the cost of increasing the alphabet size for the initial code), the argument goes through. We now formally prove the construction works. We will use the following codes from [DI14]: Theorem 4.1 ([DI14, Theorem 2]). For every prime power q and 0 < δ < 1 there exists 0 < ρ < 1, k ≥ ρ and minimum β ∈ N and a family of Fq -additive codes Dk ≤ (Fβq )m with rate R = βm β-distance ≥ δ. Recall this means that, for all c ∈ Dk \ {0}, we have wtβ (c) ≥ δ. Furthermore, the encoding map EDk can be computed by a uniform family of O(k)-size arithmetic circuits over Fq . Remark 4.2. Theorem 4.1 above promises codes of rate at least some value ρ; however, in some cases we will in fact require codes of a smaller rate, while preserving the same distance and running time. We can easily arrange for this by, say, zeroing out some coordinates from the messages. E.g., if Dk has dimension k and we’d instead like a code with dimension k ′ < k, we just append k − k ′ ′ 0’s to the message m ∈ Fkq prior to encoding via EDk . Theorem 4.3. Let k, r ∈ N be growing parameters, fix t ∈ N, and let q be a prime power. There exists an arithmetic circuit Ck,r : Fkq → Frq of size O(k + r) with O(k + r) uniformly random field elements such that, over the uniformly random field elements, the circuit implements a t-wise independent hash function of degree (q − 1) logq (t). Proof. We first describe the construction. Fix constants 0 < ε, δ2 < 1 with 1 − 2t · ε + δ2 > 1, m m be Fq and C2 ⊆ Fβq and fix β ∈ N large enough so that the following hold. Let C1 ⊆ Fβq additive codes of dimension k and r, respectively, and with distance 1 − ε and δ2 , respectively. Such codes are promised to exist by Theorem 4.1 (along with Remark 4.2 in order to reduce the codes’ dimensions, if required). Let G1 and G2 denote generator matrices for C1 and C2 , respectively. Let C1 : Fkq → Fm·β be the (uniform) arithmetic circuit of size O(m) implementing G1 , and let q r be the (uniform) arithmetic circuits of size O(m) implementing G⊤ → F C2 : Fm·β q q 2 . That such circuits exist follows from Theorem 4.1 and Lemma 3.4. Lastly, the circuit samples t·β·m = O(k+r) uniformly random symbols which we take to describe m t-wise independent functions h1 , . . . , hm : Fβq → Fβq . We remark that, thanks to Proposition 2.2, we can indeed sample such constant-sized t-wise hash functions. We imagine composing these functions hi into the map m m h : Fβq → Fβq , h x(1) , . . . , x(m) = h1 (x(1) ), . . . , hm (x(m) ) . As each hℓ can be implemented by a uniform, randomized arithmetic circuit of size Oβ,t (1), h can be implemented by a uniform, randomized arithmetic circuit of size O(m); call this circuit B. Note that B then requires O(k + r) uniformly random field elements. Defining the circuit Ck,r now as C2 ◦ B ◦ C1 , it is immediate that it is uniform and of size O(m) = O(k + r), with O(k + r) uniformly random field elements. Additionally, by Lemma 2.3 we can enforce that all the hℓ ’s have algebraic degree ≤ (q − 1) logq (t), and so since the other steps are linear, the composite function also has algebraic degree ≤ (q − 1) logq (t). Let us write H : Fkq → Frq to denote the function defined by the circuit Ck,r . We refer the reader to Figure 1 which gives a schematic of H. Recall that H takes O(k + r) uniformly random field 19
x ∈ Fkq C1 : Fkq → Fm·β = Fβq q
C2⊤ : Fβq
m
G1
x(i) ∈ Fβq
x(1)
x(2)
hi : Fβq → Fβq
h1
h2
m
→ Fβq
x(m)
hm
...
m
G⊤ 2
y ∈ Frq
Figure 1: A schematic of the IKOS construction for t-wise independent hash functions. The functions hi are constant size t-wise independent hash functions which we sample. C1 is a code with generator matrix G1 and C2 is a code with generator matrix G2 . elements. What we want to prove is that, over these random values (which sample the m t-wise independent hash functions h1 , . . . , hm : Fβq → Fβq ), H is a t-wise independent hash function family. That is, given distinct input vectors x1 , . . . , xt ∈ Fkq , over the randomness we have that z := (H(x1 ), . . . , H(xt )) ∼ Frt q . \ {0}, and to prove that ⟨y, z⟩ ∼ Fq . To do this, by Lemma 2.4 it suffices to consider any y ∈ Ftr mq m → Fβq be the function determined Write y = (y1 , . . . , yt ) with each yi ∈ Frq , and let h : Fβq by sampling the m individual t-wise independent hash function hi . Then ⟨z, y⟩ =
t X i=1
⟨yi , H(xi )⟩ =
t X
yi , h(xi G1 )G⊤ 2 =
t X
i=1
⟨yi G2 , h(xi G1 )⟩ .
(2)
i=1
Let ci = xi G1 and di = yi G2 , and note that c1 , . . . , ct are distinct codewords in C1 and d1 , . . . , dt are codewords in C2 which are not all 0. Without loss of generality, assume d1 ̸= 0. Write ci = (1) (m) (1) (m) (ℓ) (ℓ) (ci , . . . , ci ) and di = (di , . . . , di ) with each ci , di ∈ Fβq . We can now write (2) =
m X t D E X (ℓ) (ℓ) di , hℓ (ci ) ℓ=1 i=1
We claim there exists ℓ∗ ∈ [m] for which 20
(ℓ∗ )
(a) d1
̸= 0, and (ℓ∗ )
(b) the vectors c1
(ℓ∗ )
, . . . , ct
∈ Fβq are distinct.
We establish this claim now. Since C2 has distance ≥ δ2 ,condition (a) holds for at least a δ2 fraction of ℓ ∈ [m]. As for the second condition, consider the 2t codewords cij = ci − cj for 1 ≤ i < j ≤ t. (ℓ) Since C1 has distance 1 − ε, we have that cij ̸= 0 for at least a 1 − ε fraction of ℓ ∈ [m]. Thus, we (ℓ)
(ℓ)
have cij = 0 for at most an ε-fraction of ℓ ∈ [m], implying cij = 0 for some 1 ≤ i < j ≤ t for at most a 2t · ε fraction of ℓ ∈ [m]. Therefore, condition (b) holds for at least a 1 − 2t · ε fraction of ℓ ∈ [m]. Since 1 − 2t · ε + δ2 > 1 by assumption, by the pigeonhole principle some ℓ ∈ [m] must exist satisfying conditions (a) and (b). E Pt D (ℓ∗ ) (ℓ∗ ) So, fix such an ℓ∗ . Since the h1 , . . . , hm are sampled independently, if we prove that i=1 di , hℓ∗ (ci ) ∼ E Pm Pt D (ℓ) (ℓ) Fq , then additionally ℓ=1 i=1 di , hℓ (ci ) ∼ Fq , as required. To this end, without loss of (ℓ)
generality assume there is 1 ≤ s ≤ t such that di
̸= 0 iff i ≤ s. So then
t D s D E X E X (ℓ∗ ) (ℓ∗ ) (ℓ∗ ) (ℓ∗ ) di , hℓ (ci ) = di , hℓ∗ (ci ) . i=1 (ℓ∗ )
i=1
(ℓ∗ )
are distinct (and s ≤ t), the t-wise independence of hℓ∗ guarSince the vectors c1 , . . . , cs (ℓ∗ ) (ℓ∗ ) anteesDthe values hℓ∗ E (c1 ), . . . , hℓ∗ (cs ) are independent and uniform, which guarantees that ∗ ∗ Ps (ℓ ) (ℓ ) , hℓ∗ (ci ) ∼ Fq , as required. i=1 di Remark 4.4. In Theorem 4.3, we argued that we can achieve O(k + r) circuit size for constant values of t. Naturally, the constant hidden in the big-O notation depends on the choice of t. An inspection of the proof shows that the dependence is roughly Θ(t7 ). Firstly, in order to guarantee t 1 − 2 · ε is not too small, we require ε = O(1/t2 ). The codes promised by Theorem 4.1 can be verified to require β = O(1/ε3 ) (this itself stems from using the best-known explicit constructions of lossless expander graphs, whose degree are of this order). Thus, in the end we require β = Ω(t6 ), and since the total size is about t · β, we get Θ(t7 ). In particular, with t = poly(log(k + r)) we could still achieve size Õ(k + r). This means that when t = logo(1) k, we get better asymptotic size than an FFT-based implementation of a hash function using degree-t polynomials. Remark 4.5. We remark that having smaller algebraic degree is not possible, at least in the case q = 2. Here, we use the following standard fact (see, e.g., [HHL19, Section 3.1]): if f : Fβ2 → F2 is a β polynomial map with algebraic degree at most d and d < β, then for any x0 , x1 , . . . , xd+1 ∈ F2 , we P P have S⊆[d+1] f x0 + i∈S xi = 0. That is: the sum over any (d + 1)-dimensional affine space is 0. Now, suppose one had H supported on maps G = (G1 , . . . , Gβ ) : Fβ2 → Fβ2 , where each Gj is of degree d with 2d+1 ≤ t. Then, choose x1 , . . . , xd+1 ∈ Fβ2 linearly independent (this is possible since d P< β, i.e., d + 1 ≤ β), and x0 arbitrarily; say, x0 = 0. The linear independence implies the values i∈S xi are distinct for over S ⊆ [d + 1]. Then we know that, no matter what G is sampled, we
21
have ! X S⊆[d+1]
G
X i∈S
xi
! =
X
G1
X
xi
, . . . , Gβ
i∈S
S⊆[d+1]
xi
i∈S
=
!! X
!
! X
S⊆[d+1]
G1
X
xi
X
,...,
i∈S
S⊆[d+1]
Gβ
X
xi = (0, . . . , 0) = 0 .
i∈S
Thus, we can find 2d+1 ≤ t distinct input values such that, after revealing the hash value on the first 2d+1 − 1 of them, the last value is determined (as the sum of the previous values). So the distribution cannot define a t-wise independent hash function family.
4.2
Fast Bounded-Independence LUOF
Recall the definitions of a linear uniform output family (LUOF) (Section 3.1) and a t-wise LUOF (Section 3.2). The t-wise LUOF can be thought of as a linear analogue of t-wise independent hash functions. Of course, when restricting to a linear function, one cannot hope to achieve a t-wise independent hash function, as any distinct yet linearly dependent inputs will be mapped to linearly dependent outputs (and hence not stochastically independent). This motivated us to define a t-LUOF as any matrix which maps t distinct linearly independent non-zero inputs to uniformly random and independent outputs. Our goal in this subsection is to give a construction for a fast t-wise LUOF. Recall that we required this for the fast list-decodable codes with fast list-decodable duals of Section 3.2. Akin to how we showed that the fast t-wise independent hash function by generalizing the IKOS construction for fast pairwise independent hash function (assuming one uses a code with large enough distance), we will generalize the fast LUOF construction of Druk and Ishai [DI14] to give a fast t-LUOF. Here also this will rely on the codes from Theorem 4.1 having sufficiently large distance. We remark that the encoding circuits for the codes we construct only have linear size if q = O(1) (see Remark 4.7). Theorem 4.6. Let k, r ∈ N be growing parameters, fix t ∈ N, and let q be a prime power. There exists an arithmetic circuit Ck,r : Fkq → Frq of size O(k + r) with O(k + r) uniformly random field elements such that, over the O(k + r) uniformly random field elements, the circuit implements a t-LUOF. Proof. We first provide the construction, which is very similar to that given in the proof of Theorem 4.3. Fix 0 < ε, δ2 < 1 with 1 − q t · ε + δ2 > 1. Fix β ∈ N with β ≥ t large enough so that the following hold. We first choose codes C1 , C2 exactly as in Theorem 4.3, which we now recall for the reader’s convenience. m m Let C1 ⊆ Fβq and C2 ⊆ Fβq be Fq -additive codes of dimension k and r, respectively, and with distance 1−ε and δ2 , respectively. Such codes are promised to exist by Theorem 4.1 (along with Remark 4.2 in order to reduce the codes’ dimensions, if required). Let G1 and G2 denote generator matrices for C1 and C2 , respectively. Additionally, from Theorem 4.1 and Lemma 3.4 it holds that G1 and G⊤ 2 can both be implemented by uniform arithmetic circuits of size O(m) = O(k + r); call these circuits C1 and C2 , respectively. Lastly, the circuit samples m·β 2 = O(r+k) uniformly random symbols which we take to describe m random matrices F1 , . . . , Fm ∈ Fβ×β . Let F ∈ Fβm×βm denote the block-diagonal matrix with q q
22
the Fi ’s as blocks, that is,
β m
F1 0 F = . ..
0 F2 .. .
··· ··· .. .
0 0 .. . .
0
0
···
Fm
β m
obtained by mapping ((x(1) , . . . , x(m) ) 7→ (x(1) F1 , . . . , x(m) Fm ) → Fq Observe that the map Fq can be implemented by a uniform randomized arithmetic circuit of size O(m · β 2 ) = O(r + k) with the Fi ’s as above; let B denote this circuit. The final circuit Ck,r is then defined as C2 ◦ B ◦ C1 . That they have size O(k + r) follows from the given construction. The circuit samples O(r + k) uniformly random field elements to implement F . x ∈ Fkq = Fβq C1 : Fkq → Fm·β q
C2⊤ : Fβq
m
G1
x(i) ∈ Fβq
x(1)
x(2)
Fi : Fβq → Fβq
F1
F2
m
→ Fβq
x(m)
Fm
...
m
G⊤ 2
y ∈ Frq
Figure 2: A schematic of the IKOS construction for t-linear uniform output families (t-LUOF). The functions Fi are constant size random matrices which we sample. C1 is a code with generator matrix G1 and C2 is a code with generator matrix G2 . Let us write A = G1 F G⊤ 2 to denote the function defined by the circuit Ck,r . We refer the reader to Figure 2 which gives a schematic of A. What we want to prove is that, over the random field elements sampled by the circuit to implement F , A is a t-LUOF. Let x1 , . . . , xt ∈ Fkq be linearly independent. By Lemma 2.4, it suffices to consider a nonzero y ∈ Ftr q , and prove that ⟨y, (Ax1 , . . . , Axt )⟩ ∼ Fq over the O(k + r) uniformly random field elements. Write y = (y1 , . . . , yt ) with each yi ∈ Frq . Then ⟨y, (x1 A, . . . , xt A) =
t X
yi , xi G1 F G⊤ 2 =
i=1
t X i=1
23
⟨yi G2 , xi G1 F ⟩ .
Put di := yi G2 and ci := xi G1 for all i ∈ [t]. Note that the vectors c1 , . . . , ct ∈ C1 , and that they are all linearly independent. We additionally have that d1 , . . . , dt ∈ C2 , and they are not all 0. (1) (m) Without loss of generality, assume that d1 ̸= 0. For each i ∈ [t], write di = (di , . . . , di ) and (1) (m) (ℓ) (ℓ) ci = (ci , . . . , ci ) with each di , ci ∈ Fβq . Then t X
⟨yi G2 , xi G1 F ⟩ =
i=1
m X t D E X (ℓ) (ℓ) di , ci Fℓ ℓ=1 i=1
We claim there exists an ℓ∗ ∈ [m] for which: (ℓ∗ )
(a) d1
̸= 0, and (ℓ∗ )
(b) the vectors c1
(ℓ∗ )
, . . . , ct
∈ Fβq are linearly independent.
To see this, since C2 has distance ≥ δ2 , condition (a) holds for at least a P δ2 fraction of ℓ ∈ [m]. t Considering now condition (b), for each λ ∈ Ftq \ {0}, we have that cλ = i=1 λi ci is a nonzero codeword (that they are nonzero uses the assumption that the ci ’s are linearly independent). Thus, (ℓ) for at least a 1 − ε fraction of ℓ ∈ [m], we have cλ ̸= 0, or in other words, for at most an ε fraction (ℓ) (ℓ) of ℓ ∈ [m] we have cλ = 0. By a union bound, the fraction of ℓ ∈ [m] for which cλ = 0 for some λ ∈ Ftq \ {0} is at most q t · ε. Hence, condition (b) holds for at least a 1 − q t · ε fraction of ℓ ∈ [m]. Since we assumed 1 − q t · ε + δ2 > 1, we find that the required ℓ∗ ∈ [m] exists. Pt D (ℓ∗ ) (ℓ∗ ) E Fix one such ℓ∗ ∈ [m]. Since the F1 , . . . , Fm are independent, if we prove that i=1 di , ci Fℓ∗ ∼ Pm Pt D (ℓ) (ℓ) E Pt D (ℓ∗ ) (ℓ∗ ) E Fq , then also ℓ=1 i=1 di , ci Fℓ ∼ Fq , as desired. To prove i=1 di , ci Fℓ∗ ∼ Fq , sup(ℓ∗ )
pose without loss of generality that we have d1
(ℓ∗ )
, . . . , ds
(ℓ∗ )
(ℓ∗ )
̸= 0 and ds+1 = · · · = dt
= 0. Then
t D s D E X E X (ℓ∗ ) (ℓ∗ ) (ℓ∗ ) (ℓ∗ ) di , ci Fℓ∗ = di , ci Fℓ∗ . i=1 ∗
(ℓ )
i=1
∗
(ℓ )
are linearly independent, over the randomness of Fℓ∗ , the vecNow, since the c1 , . . . , cs (ℓ∗ ) (ℓ∗ ) tors c1 Fℓ∗ , . . . , cs Fℓ∗ are independent and uniform over Fβq . Therefore, applying Lemma 2.4, D ∗ E (ℓ ) (ℓ∗ ) the inner products di , ci Fℓ∗ are independent and uniform for i = 1, . . . , s, so the sum Ps D (ℓ∗ ) (ℓ∗ ) E , ci Fℓ∗ is uniform over Fq , as desired. i=1 di Remark 4.7. Again, as in Remark 4.4 we can roughly say that since we require ε < q −t and β > 1/ε3 , we at the very least require β > q 3t , showing that the constant in the big-O notation for the circuits in Theorem 4.6 is at least q O(t) . In particular, this forces both q and t to be constant to obtain a meaningful bound.
5
Cryptographic Applications
In this section we discuss several cryptographic applications of fast bounded-independence functions, most of which also require fast duals.
24
5.1
Fast Information-Theoretic MPC
We start by applying asymptotically good fast codes with fast duals towards secure multiparty computation (MPC) in the client-server model. For constant-size functions, our protocol is perfectly secure against almost 1/2 of the n servers, and has total circuit complexity of O(n). This should be contrasted with similar protocols based on algebraic MPC-friendly codes, such as Reed-Solomon codes, whose circuit complexity is (at least) quasi-linear in n. Theorem 5.1 (Near-optimal perfect MPC for constant-size functions). Let m be a constant number of clients, X and Y finite input and output domains, and ε > 0 an arbitrarily small constant. For every (finite) f : X m → Y m and ε > 0, there is an m-client, n-server protocol for f with the following features. • The protocol has perfect (information-theoretic) security against a passive adversary corrupting (at most) one client and t = (1/2 − ε) · n of the n servers. • The total computational complexity of all parties, measured by Boolean circuit size, is O(n). The above result is essentially the best one could hope for in the case of constant-size functions. First, the security threshold is nearly optimal, since a similar protocol with security threshold t > n/2 would imply information-theoretic oblivious transfer. Second, the circuit complexity is asymptotically optimal, since if a client sends messages to o(n) servers, the adversary can corrupt all of these servers and learn the client’s input. (In the perfect security case, this holds even in random access models where we only charge for messages actually sent.) Protocols in the above client-server model can be used as a building block for other cryptographic applications. For example, the above result can be used to obtain an oblivious transfer combiner with similar near-optimality features using the MPC-based approach from [HIKN08]. An OLE protocol. We will start with the simpler special case of (1) m = 2 clients, (2) the function f = OLE that takes one bit x from a receiver client, two bits (y, z) from a sender client and delivers xy + z (over F) to the receiver, and (3) sub-optimal but constant fractional security threshold t = Ω(n). This case already captures the core difficulty of the problem. We will later outline how to bootstrap from this case to general functions and near-optimal security threshold using standard techniques. In the following F can be any finite field, but the case F = F2 is sufficient for our purposes. Proposition 5.2. Let f : F × F2 → F be the OLE functionality, which takes x ∈ F from a Receiver client and y, z ∈ F from a Sender client, and delivers f (x, (y, z)) = xy + z to Receiver. Let C ≤ Fn+1 and its dual C ⊥ ≤ Fn+1 be linear codes with coordinates indexed 0, 1, . . . , n. Assume the following: 1. C has minimum distance dist > t + 1. 2. C ⊥ has minimum distance dist⊥ > t + 1. 3. Both C and C ⊥ have encoder circuits, E and E ⊥ , of size s. Then, there exists a perfectly secure protocol that computes f against any passive adversary corrupting up to t servers and at most one client. Furthermore, the total arithmetic circuit size of all parties is O(n + s).
25
To prove the above proposition, we start with a lemma that applies the well-known connection between linear error correcting codes and secret sharing [Mas95] while respecting the circuit complexity of the encoder. See Appendix A.1 for a proof. Lemma 5.3 (Secret sharing from linear codes). Let C ≤ Fn+1 be a linear code with coordinates indexed 0, 1, . . . , n and dual distance dist⊥ ≥ 2. Let E : Fk → Fn+1 be an arithmetic encoder circuit for C of size s. Then, the secret sharing scheme that shares a secret σ ∈ F into n shares by sampling a uniformly random codeword c ∈ C subject to c0 = σ and dropping c0 satisfies the following: 1. Perfect privacy: Any subset of shares T ⊂ {1, . . . , n} of size |T | ≤ dist⊥ − 2 perfectly hides σ. 2. Linear complexity: The generation of the shares from σ can be computed by a randomized arithmetic circuit of size at most s + n. We are now ready to describe the protocol establishing Proposition 5.2, using a simple clientserver instance of MPC from “multiplicative” secret sharing [CDM00]. Protocol 1 (Information-Theoretic OLE over F). 1. Setup: Client 1 (Receiver) holds input x ∈ F. Client 2 (Sender) holds inputs y, z ∈ F. There are n servers. A passive adversary may corrupt at most one client and t servers. 2. Receiver input sharing: (a) Receiver samples a uniformly random codeword c ∈ C subject to the constraint c0 = x. This is done using Lemma 5.3. (b) Receiver sends share ci to Server i (for i = 1, . . . , n). 3. Sender input sharing: (a) Sender samples a uniformly random codeword d ∈ C ⊥ subject to the constraint d0 = y. This too is done using Lemma 5.3. n (b) Sender samples a uniformly Pnrandom blinding vector e = (e1 , . . . , en ) ∈ F subject to the strict additive constraint i=1 ei = z.
(c) Sender sends shares di and ei to Server i (for i = 1, . . . , n). 4. Server computation: (a) Server i receives ci from Receiver and (di , ei ) from Sender. (b) Server i locally computes wi = ei − ci · di . (c) Server i sends wi back to Receiver. 5. Output decoding: (a) Receiver computes the final output as out = See Appendix A.2 for analysis of Protocol 1.
26
Pn
i=1 wi .
From OLE to general constant-size functions. To extend the above protocol from two-party OLE to a protocol with m = O(1) clients for any constant-size function f , we can use the known completeness of OLE (an arithmetic variant of OT) for secure computation of Boolean or arithmetic circuits [GMW87, IPS09]. At a high level, the clients start by additively sharing their inputs among each other. Then, each addition gate is processed by having the clients locally add their shares, and each multiplication gate is processed via O(m2 ) invocations of the OLE protocol to additively share each cross-term ai bj between the client holding ai and the client holding bj . The protocol concludes by having the clients exchange their output shares. When the field F is of constant size, the Boolean circuit complexity of the protocol is O(n) for any constant-size circuit. Achieving near-optimal security. The security threshold t of the protocol is close to the smaller minimal distance of the primal code and its dual, namely min(dist, dist⊥ ). One approach for getting it arbitrarily close to 1/2 is to let F be an arbitrarily large constant, in which case Theorem 3.1 gives a pair of codes with relative distance 1/2 − ε. Another approach is to start with a protocol that has an arbitrarily small (but constant) security threshold, say by using F = F2 , and apply a general threshold amplification technique based on virtualization [Bra87, ORV94, DIK+ 08]. Putting everything together. With the above extensions of Proposition 5.2, we can use our constructions of fast dual codes (cf. Theorem 3.1) to obtain the main result of this section captured by Theorem 5.1. This construction is semi-explicit in the sense that there is a PPT algorithm that generates circuits implementing the parties with negl(n) failure probability.
5.2
Fast Encrypted Matrix-Vector Product
Switching to the computational security setting, a recent application of fast dual codes with randomlike properties was recently given in the context of computing on encrypted data [BCH+ 25]. Concretely, an encrypted matrix-vector product (EMVP) protocol enables a client to encode a matrix M using a secret code C and then compute an unbounded number of matrix-vector products M qi by encrypting each query vector qi using the dual code C ⊥ . Linear algebra attacks are prevented by adding a suitable type of noise. Under a variant of the Learning Subspace with Noise (LSN) assumption [DKL09, CIMR25], the protocol hides both M and qi from a server who stores the encrypted matrix and processes the encrypted queries. Using our new families of fast dual codes, we obtain the first candidate EMVP protocols in which both the matrix encoding and the query encoding have asymptotically optimal circuit complexity. The recent construction of fast dual codes from [BR26] is limited to F2 and has a non-negligible failure probability.
5.3
Fast and Conservative Substitutes for Random Linear Codes
The previous two applications inherently relied on having a fast code coupled with a fast dual. A broader use case, which does not require duality, is providing a fast substitute to a random linear code in the context of applications that rely on the hardness of “noisy linear algebra.” Our new construction of fast t-LUOF (Section 4.2) can serve as a more conservative candidate than the previous 1-LUOF construction from [DI14]. In more detail, in most cryptographic applications of noisy linear algebra, one typically considers the minimal distance of the code or its dual as a heuristic measure of hardness. Thus, it is perhaps
27
not clear why the t-local similarity provided by t-LUOF (for t ≥ 2) is interesting. To illustrate this, consider code-based constructions that rely on the LPN assumption,5 where one assumes that the distributions (A, Ae) and (A, b) are computationally indistinguishable, where e is a random sparse vector and b is a uniformly random vector (in this case, one should think of A ∈ Fk×r with r > k). This use of minimal distance as q a proxy for conjectured LPN hardness is common in the recent line of works on pseudorandom correlation generators (PCGs) [BCGI18, BCG+ 19]. Indeed, minimal distance is sufficient for provably defeating any attack that fits under a natural “linear attack” framework [CRR21]. However, it is arguably a more conservative to use an A that shares more nuanced combinatorial properties with random linear codes, such as list-decodability/-recoverability. This is exactly what the t-LUOF property guarantees.
5.4
MPC-Friendly t-Wise Hash Functions
Finally, when distributing the computation of a function f between two or more parties, either via classical MPC techniques [Yao86, GMW87, BGW88, CCD88] or via fully homomorphic encryption [Gen09], the cost of the protocol depends on both the circuit size and the algebraic degree. For t = O(1), our constructions of fast t-wise independent hash functions from Section 4.1 simultaneously optimize both asymptotic size and degree. There are many algorithmic applications that benefit from t-wise independent hashing for constant t > 2. Two well-known examples are the use of 4-wise independence in sketching [AMS99] and 5-wise independence in linear probing [PPR07].
References [AMS99]
Noga Alon, Yossi Matias, and Mario Szegedy. The space complexity of approximating the frequency moments. Journal of Computer and System Sciences, 58(1):137–147, 1999.
[BC12]
Christina Boura and Anne Canteaut. On the influence of the algebraic degree of F −1 on the algebraic degree of G◦F . IEEE Transactions on Information Theory, 59(1):691–702, 2012.
[BCG+ 19] Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, and Peter Scholl. Efficient pseudorandom correlation generators: Silent OT extension and more. In Annual International Cryptology Conference (CRYPTO), pages 489–518. Springer, 2019. [BCG+ 23] Elette Boyle, Geoffroy Couteau, Niv Gilboa, Yuval Ishai, Lisa Kohl, Nicolas Resch, and Peter Scholl. Oblivious transfer with constant computational overhead. In Carmit Hazay and Martijn Stam, editors, Advances in Cryptology - EUROCRYPT 2023 - 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23-27, 2023, Proceedings, Part I, volume 14004 of Lecture Notes in Computer Science, pages 271–302. Springer, 2023. 5 What we will give below is often called dual-LPN, which is equivalent to the more standard variant.
28
[BCGI18] Elette Boyle, Geoffroy Couteau, Niv Gilboa, and Yuval Ishai. Compressing vector OLE. In David Lie, Mohammad Mannan, Michael Backes, and XiaoFeng Wang, editors, Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, CCS 2018, Toronto, ON, Canada, October 15-19, 2018, pages 896–912. ACM, 2018. [BCH+ 25] Fabrice Benhamouda, Caicai Chen, Shai Halevi, Yuval Ishai, Hugo Krawczyk, Tamer Mour, Tal Rabin, and Alon Rosen. Encrypted matrix-vector products from secret dual codes. In Chun-Ying Huang, Jyh-Cheng Chen, Shiuh-Pyng Shieh, David Lie, and Véronique Cortier, editors, Proceedings of the 2025 ACM SIGSAC Conference on Computer and Communications Security, CCS 2025, Taipei, Taiwan, October 13-17, 2025, pages 394–408. ACM, 2025. [BGW88]
Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. Completeness theorems for noncryptographic fault-tolerant distributed computation. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing (STOC), pages 1–10. ACM, 1988.
[BIR26]
Martijn Brehm, Yuval Ishai, and Nicolas Resch. Fast bounded-independence functions and their duals. In Information Theoretic Cryptography Conference (ITC ’26), 2026.
[Bor56]
J. L. Bordewijk. Inter-reciprocity applied to electrical networks. Applied Scientific Research, Section B, 6(1):1–74, 1956.
[BR26]
Martijn Brehm and Nicolas Resch. Linear Time Encodable Binary Code Achieving GV Bound with Linear Time Encodable Dual Achieving GV Bound. In Shubhangi Saraf, editor, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026), volume 362 of Leibniz International Proceedings in Informatics (LIPIcs), pages 28:1– 28:19, Dagstuhl, Germany, 2026. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
[Bra87]
Gabriel Bracha. An O(log n) expected rounds randomized Byzantine generals protocol. Journal of the ACM (JACM), 34(4):910–920, 1987.
[CCD88]
David Chaum, Claude Crépeau, and Ivan Damgård. Multiparty unconditionally secure protocols. In Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing (STOC), pages 11–19. ACM, 1988.
[CDM00]
Ronald Cramer, Ivan Damgård, and Ueli M. Maurer. General secure multi-party computation from any linear secret-sharing scheme. In Bart Preneel, editor, Advances in Cryptology - EUROCRYPT 2000, International Conference on the Theory and Application of Cryptographic Techniques, Bruges, Belgium, May 14-18, 2000, Proceeding, volume 1807 of Lecture Notes in Computer Science, pages 316–334. Springer, 2000.
[CGH+ 85] Benny Chor, Oded Goldreich, Johan Håstad, Joel Friedman, Steven Rudich, and Roman Smolensky. The bit extraction problem of t-resilient functions (preliminary version). In 26th Annual Symposium on Foundations of Computer Science, Portland, Oregon, USA, 21-23 October 1985, pages 396–407. IEEE Computer Society, 1985. [CIMR25] Caicai Chen, Yuval Ishai, Tamer Mour, and Alon Rosen. Secret-key PIR from random linear codes. Cryptology ePrint Archive, 2025. To appear in STOC 2026.
29
[CRR21]
Geoffroy Couteau, Peter Rindal, and Srinivasan Raghuraman. Silver: Silent VOLE and oblivious transfer from hardness of decoding structured LDPC codes. In Tal Malkin and Chris Peikert, editors, Advances in Cryptology - CRYPTO 2021 - 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16-20, 2021, Proceedings, Part III, volume 12827 of Lecture Notes in Computer Science, pages 502–534. Springer, 2021.
[CW79]
Larry Carter and Mark N. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences, 18(2):143–154, 1979.
[DI14]
Erez Druk and Yuval Ishai. Linear-time encodable codes meeting the gilbert-varshamov bound and their cryptographic applications. In Proceedings of the 5th Conference on Innovations in Theoretical Computer Science, ITCS ’14, page 169–182, New York, NY, USA, 2014. Association for Computing Machinery.
[DIK+ 08] Ivan Damgård, Yuval Ishai, Mikkel Krøigaard, Jesper Buus Nielsen, and Adam Smith. Scalable multiparty computation with nearly optimal work and resilience. In Advances in Cryptology – CRYPTO 2008, volume 5157 of Lecture Notes in Computer Science, pages 241–261. Springer, 2008. [DJM98]
Dariush Divsalar, Hui Jin, and Robert J McEliece. Coding theorems for” turbo-like” codes. In Proceedings of the annual Allerton Conference on Communication control and Computing, volume 36, pages 201–210. University Of Illinois, 1998.
[DKL09]
Yevgeniy Dodis, Yael Tauman Kalai, and Shachar Lovett. On cryptography with auxiliary input. In Michael Mitzenmacher, editor, Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 June 2, 2009, pages 621–630. ACM, 2009.
[FLY22]
Zhiyuan Fan, Jiatu Li, and Tianqi Yang. The exact complexity of pseudorandom functions and the black-box natural proof barrier for bootstrapping results in computational complexity. In Stefano Leonardi and Anupam Gupta, editors, STOC ’22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20 - 24, 2022, pages 962–975. ACM, 2022.
[Gen09]
Craig Gentry. Fully homomorphic encryption using ideal lattices. In Michael Mitzenmacher, editor, Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, pages 169–178. ACM, 2009.
[GHK11]
Venkatesan Guruswami, Johan Håstad, and Swastik Kopparty. On the list-decodability of random linear codes. IEEE Transactions on Information Theory, 57(2):718–725, 2011.
[GHK+ 13] Anna Gál, Kristoffer Arnsfelt Hansen, Michal Koucký, Pavel Pudlák, and Emanuele Viola. Tight bounds on computing error-correcting codes by bounded-depth circuits with arbitrary gates. IEEE Trans. Inf. Theory, 59(10):6611–6627, 2013. [GM22]
Venkatesan Guruswami and Jonathan Mosheiff. Punctured low-bias codes behave like random linear codes. In 63rd IEEE Annual Symposium on Foundations of Computer 30
Science, FOCS 2022, Denver, CO, USA, October 31 - November 3, 2022, pages 36–45. IEEE, 2022. [GMW87] Oded Goldreich, Silvio Micali, and Avi Wigderson. How to play any mental game or a completeness theorem for protocols with honest majority. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing (STOC), pages 218–229. ACM, 1987. [HHL19]
Hamed Hatami, Pooya Hatami, and Shachar Lovett. Higher-order fourier analysis and applications. Foundations and Trends® in Theoretical Computer Science, 13(4):247– 448, 2019.
[HIKN08] Danny Harnik, Yuval Ishai, Eyal Kushilevitz, and Jesper Buus Nielsen. Ot-combiners via secure computation. In Ran Canetti, editor, Theory of Cryptography, Fifth Theory of Cryptography Conference, TCC 2008, New York, USA, March 19-21, 2008, volume 4948 of Lecture Notes in Computer Science, pages 393–411. Springer, 2008. [IKOS08]
Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, and Amit Sahai. Cryptography with constant computational overhead. In Cynthia Dwork, editor, Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, pages 433–442. ACM, 2008.
[IPS09]
Yuval Ishai, Manoj Prabhakaran, and Amit Sahai. Secure arithmetic computation with no honest majority. In Omer Reingold, editor, Theory of Cryptography, 6th Theory of Cryptography Conference, TCC 2009, San Francisco, CA, USA, March 15-17, 2009. Proceedings, volume 5444 of Lecture Notes in Computer Science, pages 294–314. Springer, 2009.
[Li26]
Yuan Li. Secret sharing on superconcentrator, 2026.
[LW20]
Ray Li and Mary Wootters. Improved list-decodability of random linear binary codes. IEEE Transactions on Information Theory, 67(3):1522–1536, 2020.
[Mas95]
James L Massey. Some applications of coding theory in cryptography. In Codes and Cyphers: Cryptography and Coding IV, pages 33–47. Forma, 1995.
[MRR+ 24] Jonathan Mosheiff, Nicolas Resch, Noga Ron-Zewi, Shashwat Silas, and Mary Wootters. Low-density parity-check codes achieve list-decoding capacity. SIAM J. Comput., 53(6):S20–38, 2024. [MRSY25] Jonathan Mosheiff, Nicolas Resch, Kuo Shang, and Chen Yuan. Randomness-efficient constructions of capacity-achieving list-decodable codes. In 2025 IEEE International Symposium on Information Theory (ISIT), pages 1–6, 2025. [ORV94]
Rafail Ostrovsky, Sridhar Rajagopalan, and Umesh V. Vazirani. Simple and efficient leader election in the full information model. In Frank Thomson Leighton and Michael T. Goodrich, editors, Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 23-25 May 1994, Montréal, Québec, Canada, pages 234–242. ACM, 1994.
31
[PPR07]
Anna Pagh, Rasmus Pagh, and Milan Ružić. Linear probing with constant independence. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 318–327, 2007.
[Rao07]
Anup Rao. An exposition of bourgain’s 2-source extractor. Electron. Colloquium Comput. Complex., TR07-034, 2007.
[Spi96]
Daniel A. Spielman. Linear-time encodable and decodable error-correcting codes. IEEE Transactions on Information Theory, 42(6):1723–1731, 1996.
[Vad12]
Salil P. Vadhan. Pseudorandomness. Foundations and Trends in Theoretical Computer Science, 7(1–3):1–336, 2012.
[Yao86]
Andrew Chi-Chih Yao. How to generate and exchange secrets. In 27th Annual Symposium on Foundations of Computer Science (FOCS 1986), pages 162–167. IEEE, 1986.
A
Deferred Proofs
A.1
Proof of Lemma 5.3
Proof. We prove each property separately. Perfect privacy. Suppose for the sake of contradiction that a set of shares T with |T | ≤ dist⊥ − 2 leaks information about the secret σ. In a linear secret sharing scheme, this implies that the secret can be reconstructed via a linear combination of the shares in T . Thus, there exist constants {ai }i∈T over F such that for all valid codewords c ∈ C: X c0 = ai ci i∈T
Rearranging, we get the following linear constraint: X c0 − ai ci = 0 i∈T
By definition, any such a constraint corresponds to a vector in the dual code C ⊥ . Specifically, it defines a dual codeword h ∈ C ⊥ where h0 = 1, hi = −ai for i ∈ T , and hj = 0 for all j ∈ / T ∪ {0}. Because h0 ̸= 0, h is a non-zero dual codeword. Its Hamming weight is at most 1 + |T |. Given our assumption that |T | ≤ dist⊥ − 2, the weight of h is bounded by: wt(h) ≤ 1 + |T | ≤ 1 + (dist⊥ − 2) = dist⊥ − 1 This directly contradicts the premise that the dual distance of C is dist⊥ , which requires all non-zero dual codewords to have a weight of at least dist⊥ . Therefore, no such linear combination exists, and the shares in T are perfectly independent of σ.
32
Circuit size. Using column vector notation, encoder circuit E implements a linear map c = M m, where m ∈ Fk is a message vector and M ∈ F(n+1)×k is the generator matrix of C. The first coordinate of the resulting codeword is: c0 =
k X
M0,j mj
j=1
Because dist⊥ ≥ 2, the vector (1, 0, . . . , 0) is strictly excluded from C ⊥ . Consequently, c0 is not identically zero for all codewords, meaning there is at least one index j ∗ where the matrix entry M0,j ∗ ̸= 0. Without loss of generality, assume M0,k ̸= 0. To enforce the condition c0 = σ and uniformly sample the remaining degrees of freedom, the arithmetic sharing circuit performs the following steps: 1. Takes σ and k − 1 uniformly random field elements m1 , . . . , mk−1 ∈ F as input. 2. Computes the dependent message symbol mk algebraically: k−1 X M0,j mj mk = M −1 σ − 0,k
j=1
Because the coefficients M0,j are fixed constants, computing mk requires at most k − 1 field additions/subtractions and 1 scalar multiplication. This step adds exactly k arithmetic gates. 3. Feeds m = (m1 , . . . , mk ) into the original encoder circuit E, which requires s gates. The total size of the new sharing circuit is s + k. Since C is a proper subspace of Fn+1 (implied by the dual distance strictly greater than 1), its dimension k is bounded by k ≤ n. Therefore, the total arithmetic circuit size is strictly bounded by s + n.
A.2
Analysis of Protocol 1
We separately analyze correctness, circuit complexity, and security. Perfect correctness. separates into:
Receiver computes out = out =
n X
Pn
ei −
i=1
i=1 wi =
n X
Pn
i=1 (ei − ci di ).
By linearity, this
ci di
i=1
Pn ⊥ Because c ∈ C and Pdn ∈ C , their inner product over all n+1 coordinates is exactly zero: i=0 ci di = 0. This implies i=1 ci di = −c0 d0 = −xy. Furthermore, Sender constructed the blinding vector Pn such that i=1 ei = z. Substituting these values yields: out = z − (−xy) = xy + z as required.
33
Circuit complexity. Using Lemma 5.3, sampling c ∈ C given c0 = x using the size-s encoder E requires an arithmetic circuit of size at most s + n. Symmetrically, sampling d ∈ C ⊥ requires size at most s + n. Sampling the additive shares e requires generating n − 1 random elements and n − 1 subtractions, which takes O(n) gates. Each of the n servers performs exactly one multiplication and one subtraction (O(1) per server, O(n) total). The Receiver performs n − 1 additions to reconstruct the output (O(n) gates). Summing these costs yields a total arithmetic circuit size of O(n + s). Perfect security. We show that the adversary’s view can be perfectly simulated. Let T ⊂ {1, . . . , n} be the set of corrupted servers, with |T | ≤ t. If only the servers are corrupted, security follows immediately from Lemma 5.3. We consider the cases where one client is corrupted, and assume wlog that |T | = t. Case 1: Sender and t servers are corrupted. The real view consists of y, z, the codeword d, the blinding vector e, and the shares {ci }i∈T . The privacy of the Receiver’s input depends on the dual distance of C, which is dist⊥ . Because dist⊥ > t + 1, we have |T | ≤ t ≤ d⊥ − 2. By Lemma 5.3, the projection of c onto the coordinates perfectly hides x. Case 2: Receiver and t servers are corrupted. The real view consists of x, the codeword c, the output xy + z, the shares {di , ei }i∈T from Sender, and the responses {wi }ni=1 . The privacy of Sender’s input y depends on the dual distance of C ⊥ , which is the minimum distance of the primal code C, denoted as dist. 1. Simulate Sender’s shares: Because dist > t + 1, we have |T | ≤ t ≤ dist − 2. The true projection of d onto T is uniformly distributed over F|T | . The simulator samples {di }i∈T uniformly at random. It also samples {ei }i∈T uniformly at random. 2. Simulate corrupted server responses: For i ∈ T , the simulator computes wi = ei − ci di . 3. Simulate honest server responses: The final sum must evaluate to the legitimate P output xy + z. The sum of the uncorrupted responses is deterministically constrained: i∈T / wi = P (xy + z) − i∈T wi . The simulator samples the remaining n − |T | values of wi uniformly at random subject to this sum. In the real protocol, the uncorrupted blindingP shares {ei }i∈T / are uniformly random field elements P subject only to the constraint i∈T e = z − e . Because wi = ei − ci di , the {ei }i∈T i / values / i∈T i act as an information-theoretic one-time pad perfectly masking the values of ci di . The constraint on the visible responses is: ! ! X X X X X X wi = (ei −ci di ) = z − ei − −xy − ci di = (xy+z)− (ei −ci di ) = (xy+z)− wi i∈T /
i∈T /
i∈T
i∈T
i∈T
i∈T
The real variables {wi }i∈T are uniformly distributed subject exactly to this equation, perfectly / matching the simulator. The adversary extracts no additional information about y or z.
34