Homomorphic secret sharing (HSS) [19] is the secret sharing analogue of homomorphic encryption [37,51], which supports local evaluation of functions on shares of secret inputs. A standard N -party t-private secret sharing scheme randomly splits an input x into N shares, (x 1 , . . . , x N ), such that any subset of t shares reveals nothing about the input. An HSS scheme additionally supports computations on shared inputs by means of local computations on their shares. More concretely, there is a local evaluation algorithm Eval and reconstruction algorithm Rec satisfying the following homomorphism requirement. Given a description of a function f , the algorithm Eval(f, x j ) maps an input share x j to a corresponding output share y j such that Rec(y 1 , . . . , y m ) = f (x). To avoid trivial solutions, 1 the HSS output shares should be compact in the sense that their length depends only on the output length of f and the security parameter, and hence the reconstruction time does not grow in the function size. HSS enables private outsourcing of computation to multiple non-colluding servers. It also has applications to secure multiparty computation (MPC) with sublinear communication [19,27,29], multi-server private information retrieval (PIR) and secure keywords search [18,39,53], generating correlated pseudorandomness [15,16], and much more.
The work of Boyle, Gilboa and Ishai [19] gave the first nontrivial example of a 2-party HSS scheme without FHE. Their scheme supports the class of polynomial-size branching programs (which contains NC 1 ) and is based on the Decisional Diffie-Hellman (DDH) assumption. A series of followup works have extended their result, improving efficiency [17,20,22], and diversifying the underlying assumptions to Decision Composite Residuosity (DCR) [33,50,52] or assumptions based on class groups of imaginary quadratic fields [1]. For more limited function classes, which include constant-degree polynomials, 2-party HSS can be based on different flavors of the Learning Parity with Noise (LPN) assumption [16,29]. However, when it comes to the general setting of HSS with N ≥ 3 parties, constructions have been lacking, with the only known solutions relying on either FHE [11,12,21,26,32,48] or Indistinguishability Obfuscation (iO) [18]. 2The same "multi-party barrier" exists when it comes to the construction of sublinear-communication MPC protocols, the goal is to achieve (per-party) communication cost that is sublinear in the size of the circuit being computed. Until the DDH-based construction of HSS [19], this could only be achieved using FHE. It is easy to see that an N -party (N -1)-private HSS for a function class F directly implies an MPC protocol for functions in F with communication depending only on the input and output lengths. Thus, all 2-party HSS schemes in previous works immediately yield 2-party low-communication MPC for lowdepth computations (log-or log log-depth). Furthermore, these protocols can be extended to handle general layered circuits with a communication cost sublinear in the circuit size (by a log or log log factor). Unfortunately, when it comes to general multiparty settings, with up to N -1 corruption, the only known solutions again rely on FHE or iO.
Motivated by the state-of-the-art, we ask:
Can we have general N -party t-private HSS for useful classes of functions, and sublinear communication MPC for general number of parties, without FHE or iO?
In this work, based on the sparse LPN assumption (described shortly), we construct general N -party t-private HSS for log log-depth arithmetic circuits, and more generally, for the class of multivariate polynomials with log / log log degree and a polynomial number of monomials. Our HSS natively supports arithmetic computation over arbitrary field F q (assuming sparse LPN over F q ). It also enjoys concrete efficiency. In particular, the server computation overhead can be made constant (independent of the security parameter) when evaluating constant degree polynomials, and shares of multiple outputs can be packed together to achieve optimal download rate [35]. As an application of our HSS, we obtain the first sublinear-communication MPC for general layered circuits and arbitrary number of parties without relying on FHE or iO. We now describe our results in more detail.
Sparse LPN. Given two sparsity parameters k = ω(1) ∈ N and δ ∈ (0, 1), the (k, δ)-sparse LPN assumption over a finite field F q states that the following distributions are computationally indistinguishable:
(A, s T A + e T mod q) ≈c (A, r) , where A ∈ F n×m q , s ← F n q , e ∈ F m q , r ← F m q .
The public matrix A ∈ F n×m q is k-sparse, meaning that each column is sampled randomly subject to having Hamming weight exactly k, while the error vector e is n -δ -sparse in the sense that each coordinate e i is random non-zero with probability 1/n δ and 0 otherwise. This work relies on the sparse LPN assumption that the above indistinguishability holds for every super-constant k, every constant δ ∈ (0, 1), every prime modulus q (potentially exponentially large in λ), and any polynomial number m of samples. See Assumption 4.1 for the precise formulation. In fact, in this work it suffices to require the above indistinguishability to hold for some δ > 0 (though we believe that the assumption should hold for any constant δ ∈ (0, 1)).
Variants of this assumption in the binary field F 2 have been proposed and studied for at least a couple of decades in average-case complexity (see works such as [2,3,10,30,34,40,45,47]). The work of [6] generalized the assumption to large fields F q . Both of these variants have been used in a number of works (see for example [2,4,7,42]). The related assumption of local PRGs [40] has also been used in a number of works including the recent construction of program obfuscation scheme [44]. Comparing with previous variants, our assumption is relatively conservative in two aspects. First, we consider public matrices that are (k = ω(1))-sparse, instead of constant sparse k = O (1). In fact, for our constructions of HSS and sublinear communication MPC, it suffices to set k = poly(log λ). Second, the error-rate 1/n δ can be an arbitrary inverse polynomial, whereas for some application such as PKE [4] we require δ to be greater than some fixed constant.
The work of [4] showed how to construct PKE from sparse LPN over F 2 with constant sparsity k = 3, sample complexity n 1.4 and error probability o(n -0.2 ). Their scheme could be naturally extended to work with the variant of the assumption for a fairly general choice of parameters. In particular, they could work with any choice of constant k ≥ 3, assuming a sample complexity of m = n 1+(k/2-1)(1-δ) for δ > 0, where the noise probability should be o(n -δ ). In our case, k is set to be ω(1) (so n k is super-polynomial), and our sample complexity is only polynomial in n. For these parameters the noise probability implying PKE through [4] is smaller than any inverse polynomial, while for us, the noise probability could be n -δ for any δ > 0. Therefore, to the best of our knowledge, our parameters are not known to imply PKE. We survey cryptanalysis of the sparse LPN problem, and give more details on the PKE scheme, in the full version.
General N-party t-private HSS Scheme. Assuming sparse LPN, we present a construction of HSS schemes for general number of parties N and privacy threshold t. Our schemes support computing functions represented by multivariate polynomials with degree O(log λ/ log log λ) and polynomial number of monomials; in particular, this class of functions contains O(log log)-depth arithmetic circuits. However, similar to the DDH-based HSS construction of [19], our schemes have a noticeable correctness error, which can be made as small as any inverse polynomial, at the cost of worse efficiency. Theorem 1.1 (Multi-party HSS, informal). Assume sparse LPN. For any number of parties N ≥ 2, privacy threshold t < N, modulus q, error probability = 1/ poly(λ), there is a N -party, t-private HSS with correctness error for the following class of functions:
-Function Class P(F q , D, M): multivariate polynomials over the finite field F q with degree D = O(log λ/ log log λ) and number of monomials M = poly(λ).
The reconstruction of the above HSS scheme is linear. Furthermore, the scheme can be modified to have compact (but non-linear) reconstruction and negligible error rate.
Previously, sparse LPN with specific parameters was used to build public-key encryption (PKE) through the classic work of [4]. However, as remarked above, our parameters implying HSS are not known to imply PKE. Therefore, we obtain the first multi-party HSS scheme for useful classes of functions from a plausibly mini-crypt assumption. In contrast, previous (2-party) HSS schemes were either based on LWE, on various number theoretic assumptions (DDH/DCR/QR), or on standard LPN (with dense public matrix) that required the error rate to be below n -0.5 ; all of these assumptions are known to imply PKE. See Fig. 1 for details.
Besides accommodating general N and t, our construction enjoys several other desirable features. First, thanks to the fact that the sparse LPN assumption
(N, t)
DDH [17,19,20], DCR [33] (2, 1) Branching programs (NC 1 ) 1/ poly LWE [22] (2, 1) Branching programs (NC 1 ) negl DCR [50,52] (2, 1) Branching programs (NC 1 ) negl Class Groups [1] (2, 1) Branching programs (NC 1 ) negl LPN [16] (2, 1) Constant-degree polynomials none Quasi-poly LPN [29] (2, 1) Loglog-depth circuits none Degree-k Homomorphic Encryption [43,46] dt k+2 , t Degree-d polynomials none a Unconditional (Shamir-based) [35] (dt + 1, t) Degree-d polynomials none iO and OWF [18] ( , ) Circuits (P/ poly) none FHE [21,32] "arithmetize" to arbitrary field F q , our HSS schemes natively support evaluating these polynomials (and arithmetic circuits) over arbitrary field F q . Second, our construction can also accommodate general reconstruction threshold t < t ≤ N , namely, how many output shares are needed in order to reconstruct the output. Having a smaller reconstruction threshold are useful in certain applications, for instance, it implies fault tolerance to server failures in the scenario of outsourcing computation to multiple servers via HSS. Furthermore, our schemes have constant server-computation overhead when computing low degree polynomials and optimal download rate, which we expand in detail later.
Besides sparse LPN, our sublinear-communication MPC also (inevitably) needs to rely on an Oblivious Transfer (OT) protocol. The latter can be based on standard LPN with noise rate below n -0.foot_4 [2,31] or a specific sparse LPN-type assumption [4]. 3 In summary, sublinear-communication MPC can be obtained using only assumptions in the LPN family.
Finally, we note that by an existing compiler due to Naor and Nissim [49], we can upgrade our MPC protocols to be maliciously secure while preserving per-party sublinear communication cost, assuming the existence of Collision-Resistant Hash (CRH) functions. Again, CRH can be constructed from standard LPN with low-noise rate log 2 (n)/n [24].
Low Server Computation Overhead. If assuming stronger variants of sparse LPN assumption where the public matrix is constant-sparse,foot_3 i.e., k = O(1), we can slightly adapt the evaluation procedure of our HSS construction, so that, the computation overhead of each party/server for computing constant-degree polynomials represented as a sum of monomials is only a constant. More precisely, to compute a single degree d monomial over F q , the local homomorphic evaluation procedure can be represented by a degree d arithmetic circuit over F q of size O((k + 1) d ). Next, homomorphic addition of the outputs of t monomials involves only t addition over F q . Therefore, when both k and d are constants, the overhead is at most O((k + 1) d /d) (i.e., the ratio between the server cost and the cost of computing a single monomial) a constant. In comparison, almost all previous HSS schemes (tolerating N -1 corruption) have a server computation overhead proportional to the security parameter poly(λ) [1,22,29,33,50,52]; the only exception is using FHE [38] with polylogarithmic overhead, which implies HSS with poly(log λ) overhead.
We remark that HSS for low-degree polynomials is well-motivated by a variety of applications, for instance, multi-server private information retrieval, for computing inner product between two integer-valued vectors (a degree-2 function) which is a measure of correlation, and for computing intersection of d sets where each set is represented by a characteristic vector in F 2 , and intersection can be computed by instances of a degree-d monomial over F 2 . See [35,43,46] for more examples.
Simple Reconstruction and Optimal Download Rate. In fact, our HSS is also "compatible" with an arbitrary multi-secret sharing scheme LMSS. This allows us to achieve much better download rate 5 by packing many function evaluations into a single set of output shares. In particular, by plugging in the multi-secret Shamir sharing [36], we achieve a rate of 1-t/N , which matches the best possible rate for information-theoretic HSS. In fact, this also applies to computational HSS with linear reconstruction, or where the output share size is independent of the computational security parameter.foot_5 Theorem 1.3 (General Linear Output Shares, informal). For any field F q , assume sparse LPN over F q . For any N ≥ 2, t < N, = 1/ poly(λ), and any N -party, t-private linear secret sharing scheme LSS, there is an N -party, t-private HSS with correctness error for the same function class as in Theorem 1.1 satisfying the following properties:
-the output shares are LSS secret shares of the output y with probability 1 -(and LSS secret shares of some wrong value with probability ). -using an appropriate LMSS, the output shares can be packed together to achieve download rate 1t/N .
The above should be compared with the 1 -Dt/N rate of the (perfectly correct) information-theoretic construction from [35], which is in fact optimal for HSS in which both the sharing and the reconstruction are linear. To the best of our knowledge, the only other computationally secure HSS scheme with (1-t/N ) download rate uses FHE with certain properties. This scheme is sketched in the full version.
2-party sublinear MPC. The work of Boyle, Gilboa, and Ishai [19] showed how to build sublinear 2PC for layered circuits of size S with communication complexity roughly O(S/ log S), under the DDH assumption. Following this template, later works showed that we can replace DDH with various other assumptions such as DCR [33,50,52], poly-modulus LWE [22], or class group assumptions [1]. More recently, Couteau and Meyer [29] showed that assuming the quasi-polynomial hardness of (dense) LPN, we can have 2PC with sublinear communication complexity roughly O(S/ log log S). Finally, in the correlated randomness model with polynomial storage, Couteau constructed information theoretically secure MPC protocols with communication complexity O(S/log log S) [27].
Beyond 2 parties. In a very recent and independent work, Boyle, Couteau and Meyer [14] constructed the first sublinear MPC protocols for N ≥ 3 parties from assumptions that are not known to imply FHE. This includes a 3-party protocol from a combination of a variant of the (dense) LPN assumption and either DDH or QRA, as well as a 5-party protocol additionally assuming DCR and a local PRG. In contrast, we obtain a sublinear MPC protocol for any number of parties N , based entirely on variants of the LPN assumption (sparse LPN and OT, which is implied from low-noise dense LPN).
Our technical approach is very different from that of [14]. The results of [14] are based on a novel compiler that obtains a sublinear N -party MPC protocol from an (N -1)-party HSS scheme satisfying an extra "Las-Vegas"foot_6 correctness property, along with a PIR scheme with special properties. (See [14] for details, and Proposition 1 in [14] for a more general framework.) We cannot use the compiler from [14] to obtain our MPC result (Theorem 1.2), for two reasons: our HSS scheme does not satisfy the extra Las-Vegas property, and (even standard) PIR is not known to follow from any variant of LPN.
Instead, our sublinear MPC protocol follows the blueprint of a similar (2party) HSS-based construction from [19], adapting it to the lower complexity class supported by our HSS scheme and extending it to cope with a big number of parties. This approach is more direct and simpler than the compiler from [14], thanks to the fact that we can use an N -party (rather than an (N -1)-party) HSS scheme to construct N -party sublinear MPC protocols.
Finally, we note that while our MPC protocol inherently has a negligible correctness error, the construction in [14] can leverage HSS schemes with Las-Vegas correctness to yield perfectly correct (3-party or 5-party) MPC protocols [28]. We leave open the possibility of obtaining a Las-Vegas variant of our HSS scheme or a perfectly correct sublinear MPC from sparse LPN and OT.
Our results are facilitated mainly due to structural properties underlying our assumption of sparse LPN.
Sparse LPN. We start by recalling the sparse LPN assumption. Our assumption states that the following two distributions are computationally indistinguishable:
where a i are randomly chosen k-sparse vectors over F n q for a prime power q, and m is an arbitrarily chosen polynomial in n. The error e i is chosen sparsely from a Bernoulli random variable over F q with probability of error being n -δ for a constant δ > 0. On the other hand, {u i } are chosen at random from F q . In this work, we can work with any δ > 0 and typically consider k = ω(1) as an appropriately chosen super constant, however the assumption is plausible even when k is chosen to be a constant integer greater than equal to 3 as long as m = o(n k/2 ). Such an assumption will allow our homomorphic secret sharing scheme to support a slightly bigger function class. We discuss the history and cryptanalysis of this assumption in the full version. Our function class consists of multivariate polynomials over F q , and the sparse LPN assumption we will use to build such an HSS will also be over the same F q . We now illustrate how this assumption gives rise to a conceptually clean construction of a homomorphic secret sharing scheme.
We now describe the ideas behind our HSS construction. In this work, we consider the function class P(F q , D, M) which consists of polynomials evaluated on inputs that are vectors of arbitrary polynomial length over F q . These polynomials are of degree D, and are subject to an upper bound of M on the number of monomials. Looking ahead, we will handle D = log λ log log λ and M = poly(λ) where λ is the security parameter. This already lets us evaluate Boolean circuits that are local where the locality 8 is bounded by D = log λ log log λ -any circuit that has a locality bounded by D, can be represented by such a polynomial. We refer to the definitions for a homomorphic-secret sharing scheme HSS = (Share, Eval, Rec) in Sect. 3.2.
Template from Boyle et al. Our scheme follows the same high-level template that was first suggested by [19] and has been later adopted in a number of follow-ups such as [1,22,50,52], but introduces a number of important twists. Suppose we want to secret share a vector x ∈ F m q = (x 1 , . . . , x m ) amongst N parties. We work with a suitable linear secret sharing scheme over F q . In this overview, we will work with the additive secret sharing for N parties, but it could be any linear secret sharing scheme over F q (or its field extensions).
Each party can be handed over the shares of x:
, respectively. This is already enough to build a homomorphic secret sharing scheme supporting linear functions. Namely, parties can locally compute shares of linear functions of x by applying appropriate linear functions over their shares [[x
The main ingredient in prior HSS schemes is a method that lets one noninteractively compute share of multiplication of an intermediate computation y with an input symbol x i . The idea is that one publishes an encryption of the input {ct s (x i )} and encryptions of the products {ct s (x i • s j )}, where s = (s 1 , . . . , s n ) is the secret key, using a suitably chosen linearly homomorphic encryption scheme (such schemes can typically be instantiated from any of the LWE/DDH/DCR/QR assumptions). Since we are encrypting functions of the secret key inside the ciphertext, the encryption scheme must also be KDM secure (or we must assume it is KDM secure).
These encryptions are given to all parties. Along with these encryptions and the shares of the input [[x i ]] , each party P receives a share [[x i • s j ]] of the product x i s j . The key step is a procedure that allows one to start with a share
. This step leverages structural properties of the linearly homomorphic encryption scheme. Typically in such settings, one homomorphically computes on the ciphertext by "multiplying" ct s (x i ) with [[y]] . The resulting ciphertext is then "decrypted" in a distributed fashion using the secret-shares of the form [[y • s j ]] , assuming that the decryption is almost linear. This produces 8 The locality of any Boolean circuit is the number of input bits it depends on.
] can be computed by starting with ct s (x i s j ) instead.
Which linearly homomorphic encryption one chooses can present different sets of challenges for realizing the above step. [19,50] relied on DDH/Pallier based encryption. Since the ambient space of shares is over some field, whereas the encryption consists of group elements, this step include some operations done over the groups followed by a "distributed discrete-log" step that works specifically for two parties. In LWE based schemes such as [22], the ciphertexts live in the same space as that of the shares. The issue is that while the ciphertexts are almost linear in the secret, they have a low-norm error. The authors suggest a rounding based idea that was inspired by earlier works on homomorphic encryption [23,25] that for some (not so) coincidental reason works specifically for two parties. Our main approach consists of devising a suitable linearly homomorphic encryption that sits naturally over the field F q , and does not suffer from the issues that prevented scaling of previous ideas beyond two parties.
Suitable Linearly Homomorphic Encryption. The main issue with prior linear homomorphic encryption schemes that restricts constructions to two parties is that they don't work naturally with the linear secret sharing scheme. As a result, special share conversion methods have to be devised (which seem to be stuck at two parties). It is instructive to ask what properties a linear homomorphic encryption could satisfy so that it works more naturally with the linear secret sharing scheme.
To this end, consider the following (broken) encryption scheme that encrypts input x i as ct s (x i ) = (a i , b i = a i , s + x i ) where s is a vector of F n q and a i ← F n q is randomly chosen. Similarly, we have ct s (x i s j ) = (a i,j , b i,j = a i,j , s + x i s j ). Such an encryption scheme is both linearly homomorphic and has a linear decryption function over F q . On the other hand, it is obviously not secure: one could find the secret s by solving a properly constructed linear equation system.
But, for the time being assume that the scheme was secure. If this were true, then this will give rise to a homomorphic secret sharing scheme supporting corruption patterns governed by any linear secret sharing scheme over F q , thanks to it being linearly homomorphic over F q and having linear decryption over F q . Indeed, observe that
LPN-Based Linearly Homomorphic Encryption. While the above proposal would work, as described before, it is obviously not secure. To fix the security issue, one could leverage an encryption scheme based on the standard LPN assumption.
We could instead have ct s
) where e i and e i,j are chosen from the generalized Bernoulli random variables Ber(F q , η) where η(n) is chosen to be a small inverse polynomial n -δ . The resulting scheme is now secure by the LPN assumption, it is also linearly homomorphic and has a linear decryption over F q . Although, the decryption has a small probability correctness error due to noise. The problem we now face is correctness of the output. We can observe that if one is initially given [[x i ]] and [[x i • s j ]] , as one computes shares for degree two computations x i1 • x i2 , Eq. 1 instead yields noisy shares
Here by "noisy" we don't mean that the shares of individual parties are corrupted, but rather that, with some small probability the shares reconstruct to something else other than the desired computation (but they are still consistent secret sharing of some "noisy" output). Each computed share can be corrupted with probability η due to the LPN noise. Moreover, as one evaluates further to compute degree three terms, the noise increases further. To compute degree three shares of the form x i1 • x i2 • x i3 , the noise probability could already be overwhelming. This is because due to Eq. 1,
Thus, each conversion is a function of one LPN sample and n shares derived in the previous layer. The probability of having no noise in the reconstructed output is roughly the probability that all the shares derived in the previous layer are non-noisy and the LPN sample used in that layer has no noise. This probability is roughly (1η) O(n) assuming that the errors are independent. As η 1 n , this probability is already negligible.
Sparse LPN for Error Control. We can observe that in Eq. 1 above (now with noisy shares),
where k is a parameter that could be a constant or slightly super-constant, the error build up will be manageable. The probability that the share is non-noisy is can now be lower-bounded by 1 -(k + 1)η. This is because this equation now depends only on k + 1 noisy shares derived in the previous layer and one LPN sample, both with noise rate η.
Going inductively, the shares at level D for computing a degree D monomial are non-noisy with probability at least 1 -O((k + 1) D η). If one further adds M such degree D monomials to compute the polynomial of desired form the resulting shares are non-noisy with probability is at least 1 -O(M (k + 1) D η). We can make sure that this probability is 1
λ . If M is some polynomial in λ, D = log λ log log λ , and η = n -δ for some constant δ > 0, we can set k = log O (1) λ and n as some other polynomial in λ. More details of our HSS scheme can be found in Sect. 5.1.
To sum up, one would compute
where a i is chosen to be a random sparse vector as in the distribution specified by the sparse LPN assumption, and e i is generated as a sparse noise. {ct s (x i s j )} i,j are generated analogously. Since our assumption works naturally over the field F q one could use any linear secret sharing scheme over F q . One can then evaluate any function in P(F q , D, M). For any function f in the function class, at the end of the evaluation each party gets a noisy share f (x 1 , . . . , x m ) . With all but a small inverse polynomial probability, these shares reconstruct to f (x) using the same linear reconstruction that is used for the base secret sharing scheme.
One issue that we have not discussed thus far is that in our HSS scheme, one gives out encryptions that are dependent on the key s. Namely, all parties not only get encryptions of the input ct s (x i ), but also encryptions ct s (x i s j ) of the products x i s j . Therefore, we need to argue that KDM security follows from sparse LPN. Note that indeed if ct s (x i s j ) were encrypted using the standard LPN assumption, namely by setting ct s (x i s j ) = (a i,j , a i,j , s + e i,j + x i s j ), where a i,j is chosen randomly over F n q , then such KDM security holds directly from LPN. The idea is that one can "simulate" such an encryption from an LPN sample (a , b = a , s + e) as follows. We can simply set a i,j = a -(0, . . . , 0, x i , 0, . . . 0) xi at j th coordinate = ax i • v j for the j th unit vector v j , and b i,j = b .
Observe that b = a , s + e = a i,j , s + x i s j + e. Since a is chosen at random, the distribution of a i,j is also identically random even given x i .
The above simulation strategy fails to work when a i,j are exactly k-sparse for some k. This is because the vector a i,j that is used to construct ct s (x i • s j ) might actually be distinguishable from the distribution of ax j v j . Not only there could be a difference in the number of non-zero coordinates, this could also leak out x i (by observing the value at of a i,j formed this way at the j th coordinate).
We modify slightly the distribution of the coefficient vectors a i,j used to generate ct s (x i • s j ) so that one could prove KDM security under sparse LPN assumption. Below we sketch the main ideas assuming q is a prime power greater than 2.
Modified Distribution. In the actual scheme in Sect. 5, we encrypt the vector x as ct s (x i ) = (a i , a i , s + e i + x i ) where a i are exactly k-sparse. However, to encrypt the products x i s j , we compute ct s (x i s j ) = (a i,j , a i,j , s + e i,j + x i,j ) where a i,j are chosen differently. They are chosen to be 2k -1 sparse with the constraint that the j th coordinate of a i,j is non-zero. This constraint enables us to prove security from sparse LPN as long as q > 2.
Our main idea is that such a sample a i,j , b i,j can be simulated from sufficiently (polynomially) many samples of sparse LPN with sparsity k. Say we have two samples of the form c 1 , d 1 and c 2 , d 2 such that d i = c i , s + e i for i ∈ {1, 2}. Additionally, c 1 and c 2 are non-zero at the j th coordinate and that is the only coordinate at which both c 1 and c 2 are non-zero. Any pair of samples will satisfy this property with an inverse polynomial probability provided k is reasonably small. We sample a random non-zero field element r, and two non-zero elements μ 1 , μ 2 ∈ F q so that μ 1 c 1,j + μ 2 c 2,j = r + x i . Computing such non-zero μ 1 and μ 2 requires that q > 2. Indeed if q = 2, there is only one choice for μ 1 and μ 2 and then our condition μ 1 c 1,j + μ 2 c 2,j = r + x i may not hold. Now let α = μ 1 c 1 + μ 2 c 2 , and set a i,j = αx i v j . Our desired sample then becomes ct s (
Note that the error μ 1 e 1 +μ 2 e 2 is still sparse (with noise rate close to 2η); our remaining task is to show that a i,j has the right distribution. This follows from the following argument. Since c 1 and c 2 have disjoint support aside from the j th coordinate, the distribution of a i,j on coordinates not equal to j is identical to a random (2k -2)-sparse vector. On the other hand, at the j th coordinate a i,j is set to be equal to r, which is random non-zero.
When q = 2, we are not able to prove KDM security of our distribution under (exactly) k-sparse LPN. On the other hand, relying on a related assumption we can indeed show KDM security. In this assumption, the samples will consist of two kinds of coefficient vectors a i : with half probability, a i will be k-sparse, otherwise it will be (k -1)-sparse. We refer to Sect. 4.1 for more details.
We can leverage our homomorphic secret sharing scheme to build a sublinear MPC protocol for (Boolean) layered circuits. Here too, our result follows the main conceptual outline suggested by [19], with a number of low-level, yet important, differences in the implementation. The differences in implementation come from three sources: handling arbitrary number of parties, dealing with restricted function classes supported by the HSS, and dealing with correctness error. In the following, recall that Boolean layered circuits of width W , depth D and size S are designed so that every layer is computed by applying some gates on inputs only on the previous layer. Our sublinear MPC will can compute such a circuit supporting N with a communication of O(ω(1) • S/ log log S + (D + W ) • S o (1) • poly(N, λ)) for an arbitrarily small tunable ω (1).
Recipe for Sublinear MPC from HSS from Boyle et al. The intuition why an HSS scheme could be helpful for this task was first brought out by [19] and can be described as follows. Suppose that our HSS scheme supported arbitrary circuits and had no correctness error. Then parties can then run any MPC protocol that distributes shares sh 1 , . . . , sh N that correspond to a homomorphic secret sharing of x of their combined input. The amount of communication per-party for this would be polynomial in the security parameter λ, |x| and the number of parties N . Each party P can then locally evaluate on their share sh to compute the desired layered circuit C to form evaluation st and output this value. For our purposes, let the length of the output be M , which is the width of the last layer. Let st = (st ,1 , . . . , st ,M ). The j th output bit can be reconstructed by adding {st ,j } ∈[N ] . This yields an additional communication of |st | = O(M ) bits per-party. Thus, the total communication is poly(λ, N, |x|) + O(M ) which is sublinear in the circuit size.
There are two typical challenges that arise in materializing the intuition above. First, the HSS scheme typically could have an error in output reconstruction. For all currently known schemes with erroneous outputs, leaking out which outputs don't reconstruct correctly can jeopardize security (much as how leaking which LPN samples have error can break the assumption). The second challenge is that typically HSS schemes don't support circuits of arbitrary size; instead, they may only handle circuits of depth log S or even log log S. Indeed, our HSS can only handle circuits of depth c • log log S, for any constant c < 1.
To address the challenges of circuit depth, Boyle et al. suggested the following. They suggested dividing the circuit C into L = S/ log S special layers (or S/ log log S in our case depending on the depth supported by the HSS scheme), such that HSS can be performed from one layer to the next. Unfortunately, this won't work as is because one cannot afford to run a general-purpose MPC for every chunk to generate HSS sharings of the state of the circuit at that layer. This is because the communication for this step could grow as O(W poly(λ, N )) where W is the width of the circuit. Any savings by running HSS evaluation of circuits with depth log S (or log log S in our case) could be drowned out by multiplicative poly(λ, N ) term. To address this, Boyle et al. suggested that for every chunk i ∈ [L], the MPC is run to generate an HSS sharing of N secret keys
for a rate-one encryption scheme. Since keys are smaller in size compared to the state of the circuit, this could be done with significantly less communication. The keys sk i, for every chunk i ∈ [L] and party P is known only to party P . The evaluation will follow in encrypt-then-evaluate cycles. Namely, (rate-one) encrypted HSS evaluated shares will be decrypted by HSS, computed upon according the circuit chunk description, and then the resulting HSS evaluations are encrypted by each party using their key for that chunk. This process could go on, but at the end we must reconstruct the output. If our HSS is perfectly/statistically correct each party could simply release the HSS share evaluations unencrypted corresponding to the output layer.
If the HSS evaluations do not satisfy correctness as described above, there could be multiple additional issues. First, the output of computation for each chunk might not be correct. More importantly, for the output layer, when parties reveal the HSS evaluations it could jeopardize security. The fix for the first issue that was proposed was to evaluate the circuit in a fault tolerant fashion using appropriate error correction. Each HSS evaluation will now not only correspond to a decryption followed by evaluation, it will also have an error correction step. To address the second issue, Boyle et al. suggested using MPC at the final layer to reconstruct the final output as opposed to clearly releasing the evaluations. This will introduce additional communication but only about M • poly(N, λ). Specific Issues in Our Context. We now discuss specific issues that we need to address in our context.
-We can handle circuits of depth log log S, so we have to implement both error correction and decryption within that depth.
-Each party P encrypt their HSS evaluation under their secret key sk i, . Even if the decryption circuit of the encryption is very simple, decrypting O(N ) encryptions, followed by HSS reconstruction and evaluation corresponding to the chunk all under the hood of HSS could be too complex for us as such a function has a locality of Ω(N ).
To address error correction issue, we will do naive majority-based error correction. We will have κ = ω(1) copies of HSS shares for the same set of encryption keys, where κ could be any super-constant. Each party will then release κ rateone encryptions, one for each of the κ HSS evaluations. For the error correction, each HSS evaluation function will simply use majority decoding and compute the majority of κ HSS reconstructions and then apply the circuit corresponding to the chunk. If HSS reconstruction and the decryption are very local, then the whole circuit is very local. This introduces a κ factor larger communication that the previous approach, but we can choose κ = o(log log S) so that our communication is sublinear.
To implement the encryption with a very local decryption, we rely on sparse LPN yet again. In particular, we revisit the encryption scheme described in Eq. 3, whose decryption circuit has locality equal to the sparsity parameter k. We can handle decryption errors via the same majority-based fault tolerance approach, as described above.
To solve the third issue, we leverage the fact that our encryption scheme is key-homomorphic. Instead of setting up HSS shares for keys {sk i, } ∈[N ] , we set up HSS shares for the sum Σ ∈[N ] sk i, = sk i . The ciphertexts encrypting HSS shares under key sk i, could be homomorphically added to form a ciphertext under sk i of the HSS reconstruction of the circuit state for the chunk, thanks to the additive reconstruction of our HSS scheme and the additive homomorphism of the encryption scheme. Now, the HSS evaluation could decrypt just the resulting ciphertext encrypted under sk i as opposed to decrypting N ciphertexts.
While these are the main ideas, there are a number of low-level details that we could not dive into in this overview. The details of our sublinear MPC can be found in Sect. 6.
Notation. Let N = {1, 2, . . . } be the natural numbers, and define [a, b] := {a, a + 1, . . . , b}, [n] := [1, n]. Our logarithms are in base 2. For a finite set S, we write x ← S to denote uniformly sampling x from S. We denote the security parameter by λ; our parameters depend on λ, e.g. n = n(λ), and we often drop the explicit dependence. We abbreviate PPT for probabilistic polynomial-time. Our adversaries are non-uniform PPT ensembles A = {A λ } λ∈N . We write negl(λ) to denote negligible functions in λ. Two ensembles of distributions {D λ } λ∈N and {D λ } λ∈N are computationally indistinguishable if for any non-uniform PPT adversary A there exists a negligible function negl such that A can distinguish between the two distributions with probability at most negl(λ).
For q ∈ N that is a prime power, we write F q to denote the finite field with q elements, and F × q to denote its non-zero elements. We write vector and matrices in boldcase, e.g. v ∈ F m and A ∈ F n×m . We recall the model of arithmetic circuits, and properties of the Bernoulli distribution Ber(F q , ), in the full version
We describe linear (multi-)secret sharing schemes, denoted L(M)SS. Looking ahead, our HSS construction will work with an arbitrary LMSS/LSS scheme. The reader can think of the Shamir LMSS as a running example, described in Definition 3.3 below.
A N -party, tprivate, s-secret linear multi-secret sharing scheme (LMSS) over a finite field F is a tuple of PPT algorithms LMSS = (Share, Rec) with the following syntax:
-Share(x 1 , . . . , x s ; ρ) → (sh 1 , . . . , sh N ). Given secrets x 1 , . . . , x s ∈ F, this algorithm samples randomness ρ ∈ F r and return shares sh i ∈ F bi for all i ∈ [N ]. Note that r, b 1 , . . . , b N ∈ N are also part of the description of LMSS. We require Share :
-Rec(sh 1 , . . . , sh N ) → (x 1 , . . . , x s ). Given shares (sh 1 , . . . , sh N ), return the secrets (x 1 , . . . , x s ) or ⊥. We require Rec :
We require the following properties:
-Correctness. For any x 1 , . . . , x s ∈ F, we have -Privacy. For any tuples (x 1 , . . . , x s ), (x 1 , . . . , x s ) ∈ F s and any subset T ⊂ [N ] of size at most t, the following distributions are the same:
We define the rate of LMSS to be r
A LMSS instance for s secrets can be "split" into s LSS instances LSS (1) , . . . , LSS (s) , where for all σ ∈ [s], LSS (σ) shares input x in the σ th slot of LMSS as (0, . . . , x, . . . , 0) = x • u σ , where
is the σ'th unit vector of dimension s and with a single 1 at coordinate σ.
These LSS instances can be "merged" back into a LMSS instance in the following sense: there exists an operation Pack, such that for any ∈ [N ], given party P 's shares of the LSS instances ) , returns party P 's share of the LMSS instance:
We recall the construction of the Shamir LMSS in e.g. [36]. Note that this LMSS achieves the optimal tradeoff (see [35]) between the rate and the privacy threshold t, meaning that r = 1t/N .
Let F be a finite field, N be the number of parties, and t the privacy threshold. Let d = log |F| (2Nt) , and define E to be the unique extension field of F of degree d. Let γ be a primitive element of E over F. For any s ≤ Nt, the N -party, t-private, (ds)secret Shamir LMSS is defined as follows. Pick arbitrary distinct field elements α 1 , . . . , α N , β 1 , . . . , β s ∈ E.
-Share(x 1 , . . . , x ds ) → (sh 1 , . . . , sh N ). On input (x 1 , . . . , x ds ) ∈ F ds , we pack every d elements (x dj , . . . , x dj+d-1 ) into a field element y j of E by setting
-Rec(sh 1 , . . . , sh N ) → (x 1 , . . . , x ds ). On input the shares (sh 1 , . . . , sh N ), we interpolate the unique polynomial p(X) ∈ E[X] of degree at most s + t -1 such that p(α i ) = sh i for all i ∈ I. We then compute y j = p(β j ) for all j ∈ [s], and break y j down into d elements (x dj , . . . , x dj+d-1 ) of F (which is a F-linear operation). Return (x 1 , . . . , x ds ).
We recall the definition of homomorphic secret sharing schemes from [18,21], in the setting with a single client, an arbitrary number N of servers, and security against t colluding servers. The functions we consider are arithmetic circuits over a finite field.
Definition 3.4. Let N (λ), t(λ), q(λ), corr (λ) be polynomials in λ. A N -party, t-private homomorphic secret sharing (HSS) scheme with correctness error corr , for a class of arithmetic circuits F = {F λ } λ∈N over the finite field F q , is a tuple of PPT algorithms HSS = (Share, Eval, Rec) with the following syntax:
-Share(x) → (sh 1 , . . . , sh N ): given a vector x ∈ F m q of field elements, this algorithm returns a secret sharing (sh 1 , . . . , sh N ) of x.
-Eval(i, f, sh i ) → osh f,i : given party index i ∈ [N ], a function f ∈ F λ and the share sh i , this algorithm returns an output share osh f,i .
-Rec({osh f,i } i∈[N ] ) → y f : given the output shares {osh f,i } i∈ [N ] , this algorithm returns the final output y f or ⊥.
We require HSS to satisfy the following properties:
-Correctness. We say that the HSS scheme is corr -correct, if in an honest execution of HSS algorithms with error bound corr , one can reconstruct the correct output given the output shares with probability at least 1corr . Formally, for all λ ∈ N, all functions f ∈ F λ , and inputs x to f , we have
-Security. We say that the HSS scheme is secure if any subset of no more than t shares of the input x reveals no information about x. Formally, for any sequence of subsets {T λ } λ , where T = T λ ⊂ [N ] has size t, and any PPT adversary A = (A 1 , A 2 ), the advantage of A in the following experiment is bounded by 1/2 + negl(λ) for a negligible function negl.
A picks challenge inputs ((x 0 , x 1 ), st) ← A 1 (1 λ , T ). 2. C(x 0 , x 1 ) samples a random bit b ← {0, 1} and computes (sh b,1 , . . . , sh b,N ) ← HSS.Share(x b ).
The advantage of A in the above experiment is the probability that b equals b .
-Compactness. There exists a polynomial p such that for any λ ∈ N, any i ∈ [N ], any f ∈ F λ , any input x to f , given (sh j ) j∈[N ] ← Share(x), the output share osh f,i ← Eval(i, f, sh i ) satisfies |osh f,i | ≤ p(λ). In particular, the output share sizes do not depend on the size of the function f . Remark 3.5 (Linear Reconstruction). We say that an HSS scheme for a class of arithmetic circuits F over a field F q has linear reconstruction if for every f ∈ F, input x to f , shares (sh j ) j∈[N ] , and party i ∈ [N ], the operation Eval(i, f, sh i ) → osh f,i produces output shares that are vectors of field elements in F q . Furthermore, the reconstruction Rec({osh f,i } i∈[N ] ) → y f consists of applying a F q -linear map over the output shares osh f,i .
In this section, we define our sparse learning parity with noise ( sLPN) assumption. sLPN is a natural variant of the LPN assumption, where each column of the public matrix is now k-sparse for a parameter k. First introduced by Alekhnovich [2], who used it for obtaining hardness of approximation results, variants of the sLPN assumption were subsequently used for constructing local pseudorandom generators [8], cryptography with constant computational overhead [42], public-key encryption schemes [4], pseudorandom correlation generators [15] and more. In the full version, we give an overview of known attacks against sLPN that may help establish a plausible concrete tradeoff between the parameters.
Let λ ∈ N be the security parameter, n = n(λ) be the dimension, m = m(λ) ∈ N the number of samples, k = k(λ) ≤ n the sparsity parameter, q = q(λ) ∈ N the field size, and = (λ) ∈ (0, 1) the noise rate. We define the sparse LPN distribution D sLPN,n,m,k, ,q to be output distribution of the following process:
-Sample s ← F 1×n q uniformly at random. -Sample A randomly from F n×m q such that every column of A has exactly k non-zero elements.
-Sample e ← (Ber(F q , )) 1×m , where Ber(F q , ) returns 0 with probability 1 -, and a uniformly random non-zero element of
Similarly, we define D rand,n,m,k, ,q to be identical to the distribution D sLPN,n,m,k, ,q except that b is chosen uniformly at random from F 1×m q .
We now state our Sparse LPN assumption. Note the following two parameter choices: k = ω( 1) is a super-constant, and the noise rate = O(n -δ ) for some δ ∈ (0, 1). Assumption 4.1 (The (δ, q)-sLPN Assumption). Let λ ∈ N be the security parameter, δ ∈ (0, 1) be a constant, and q = q(λ) is a sequence of prime powers computable in poly(λ) time. We say that the (δ, q)-sLPN holds if for all functions n = n(λ), m = m(λ), k = k(λ), = (λ) efficiently computable in poly(λ) time, with k = ω(1) ≤ n and = O(n -δ ), the following two distributions are computationally indistinguishable:
We will also use sLPN n,m,k, ,q to refer to the (decisional) sparse LPN problem with fixed parameters, where an adversary needs to distinguish between the two distributions above. Remark 4.2. In our sparse LPN assumption, we choose k = ω(1) to be a superconstant (in particular, polylogarithmic) to avoid dealing with syntactical issues arising when k is a constant. Formulations of sparse LPN are well-studied and believed to be hard over F 2 when k ≥ 3 is a constant (See for example [2,4,34]). Such formulations can support even up to m = n k/2-samples for arbitrary constant > 0. In such cases, however, we require the m columns of A to not admit a sparse combination of columns say (i 1 , . . . , i ) such that A ii +. . . A i = 0 for some constant . This is achieved by requiring the k-regular bipartite graph formed with the columns of A satisfies certain expansion conditions. Unfortunately, this criterion fails to hold for a random graph/random A with inverse polynomial probability 1 n O(1) . We could have worked with a stronger assumption, where k is a constant and the matrix A comes from a special distribution of sparse matrices, 9 to achieve a slightly more expressive function class supported by our HSS scheme. Namely, in such a case we could handle D = O(log λ). But for simplicity, we choose to work with super-constant k and uniform k-sparse matrix A.
For the security proof of our HSS construction, we will also require the pseudorandomness of a specific secret-dependent sLPN distribution. In this distribution, we essentially encrypt each input x i and x i • s j for all i, j under sLPN. We note that the result proved in this section corresponds to the notion of KDM security with function f x,j (s) = x • s j for a given index j ∈ [n] and for all x ∈ F q , defined in prior works [5,13,22]. Definition 4.3 (Sparse LPN KDM distribution). Let δ ∈ (0, 1) be a constant and q = q(λ) a sequence of prime powers efficiently computable in poly(λ) time. Let λ ∈ N be the security parameter, and n(λ), m(λ), k(λ), (λ) ∈ N be efficiently computable functions of 1 n such that q is a prime power, k = ω(1) < n/2, and = O(n -δ ). For any sequence of vectors {x = x λ } λ where x λ ∈ F m q , we define the distribution D kdm sLPN,n,m,k, ,q (x) to be the output of the following process:
, where e i,j ← Ber(F q , ).
Similarly, we define D kdm rand,n,m,k, ,q to be exactly the distribution above except that b i , b i,j are chosen uniformly at random from F q for all i ∈ [m], j ∈ [n].
We now show that the above KDM distribution is also computationally indistinguishable from random, assuming the sparse LPN assumption for the same parameters n, k, q, slightly lower noise rate /2, and a polynomially larger m . Note that the lemma requires q > 2 due to a technical detail, sketched in the technical overview. We give a full proof in the full version, and discuss a few workarounds for the case q = 2.
Let δ, q, n, m, k, and x be as specified in Definition 4.3. For q > 2 and k ∈ ω(1) ∩ o( √ n), assuming the (δ, q)-sLPN assumption holds (c.f. Assumption 4.1), the following distributions are computationally indistinguishable:
In this section, we describe our main HSS construction from Sparse LPN (c.f. Assumption 4.1). Our scheme can handle log / log log-degree polynomials containing a polynomial number of monomials, and achieve -correctness for an arbitrary inverse polynomial .
Function Class. Our HSS supports the function class P(F q , D, M) consists of multivariate polynomials over field F q with degree D and number of monomials M . We do not put any constraint on the number of variables m of the polynomial, as long as it is poly(λ). In particular, every function f ∈ P(D, M ) can be represented as a sum of monomials:
where c γ ∈ F q is a coefficient and M γ is a monomial of degree at most D over x.
Our HSS construction will require polynomials to be represented this way, which is without loss of generality since one can efficiently pre-process any polynomial to be of this form. Looking ahead, our scheme will achieve D = O log λ log log λ and M = poly(λ).
In particular, this function class allows us to evaluate arbitrary arithmetic circuits (with fan-in 2) of depth d = c • log log λ, for any c < 1. This is because every output of such a circuit can be computed by a degree-2 d polynomial in 2 d number of variables. Since the degree is D = 2 d = log c λ = O log λ log log λ , and the number of monomials is M ≤ (2 d ) 2 d < (log c λ) log λ/ log log λ = λ c , we can see that this circuit can be supported by our HSS.
Parameters for Sparse LPN. We will use below the Sparse LPN assumption over F q with noise rate n -δ for an arbitrary constant δ ∈ (0, 1), chosen such that the assumption holds, and dimension n which is a polynomial in the security parameter λ depending on D and M .
Ingredient: A Linear Secret Sharing Scheme. In our scheme, we require an arbitrary N -party, t-private LSSS scheme LSS = (Share, Rec) supported over the field F q of computation. For convenience, the reader may think of the Shamir secret sharing scheme (c.f. Definition 3.3). When N > q, note that the shares in the Shamir LSSS live in a suitable extension field E of F q such that |E| > N.
Scheme Overview. We now give a high-level overview of our multi-party HSS scheme, expanding on some points made in the technical overview. The full construction is presented in Fig. 2. In our scheme, HSS.Setup will choose a suitable LSS scheme with reconstruction over F q and suitably set sLPN parameters n and k. To share an input x ∈ F m q , HSS.Share will generate encryptions ct s (x), ct s (x ⊗ s) drawn from the distribution D kdm sLPN,n,m,k, ,q (x) in Definition 4.3, along with secret sharings of x and x ⊗ s. Namely:
-We sample a random k sparse coefficient vector a i ∈ F n q for every i ∈ [m]. Similarly, for every i ∈ [m], j ∈ [n], we sample a random 2k -1 sparse vector a i,j ∈ F n q so that it is non-zero at the j th coordinate.
-To encrypt x i for i ∈ [m], we sample a random secret vector s ← F n q and compute b i = a i , s + x i + e i for all i ∈ [m], where e i ← Ber(F q , ) is Bernoulli with noise rate = n -δ . -We also encrypt x i • s j for every i ∈ [m], j ∈ [n] as follows. We compute b i,j = a i,j , s + x i • s j + e i,j , where e i,j ← Ber(F q , ) is Bernoulli with noise rate = n -δ . Notice that together ct s (x
is exactly from the D kdm sLPN,n,m,k, ,q distribution. -We secret share each x i , for i ∈ [m], and products
using our LSSS scheme. Let us denote the shares of each party P with ∈ [N ] by [[x i ]] and [[x i • s j ]] , respectively.
-Each party P 's share sh (x) consists of cts(x),
.
Homomorphic Evaluation. To execute HSS.Eval, each party P (for ∈ [N ]) will perform homomorphic operations on its local shares. Intitially, the parties start with sharings of the form [
. Relying additionally on the sparse LPN encodings, we will maintain the invariant that for every intermediate value of computation y, each party P stores shares of y and y • s j for j ∈ [n]. However, as a result of the computation each share can be corrupted by a lowprobablity noise over F q . We will denote these shares using a special notation α for the intermediate variable α. To be precise α = [[α + e α ]] where e α is a low-probability noise.
The Eval operations will involve both the linear shares and the noisy ciphertext ct x (s), leading to a build-up of noise as each party continue its local computation. The homomorphic operations are performed as follows:
-To add together two intermediate values y and z, each party P can just add its local noisy shares:
This operation increases the noise rate only by a factor of 2. Therefore, this extends straightforwardly to handle arbitrary linear combinations of a polynomial number of intermediate values assuming that the initial noise rate is small enough. -To multiply an intermediate value y with an input x i , each party P will utilize its encryptions (a i , b i ), {(a i,j , b i,j )} j∈ [n] along with its noisy shares of y to compute:
(4) The reason why the above holds is the following. Recall that Supp(a) denotes the non-zero coordinates of a. Without any noise, the above computation gives the right result, since the equation
together with the linearity of the shares, imply that
In other words, as long as the potentially noisy shares y , { y • s j } j∈Supp(ai) were noise-free and the sample b i was also noise free, then the share produced by (x i • y) in Eq. 4 will be noise free. A similar argument applies for correctness of computing (x i • y) • s j . The presence of noise affects the correctness as follows. Because both a i and a i,j have sparsity at most 2k -1, at every multiplication step the error probability grows by a factor at most O(k). On careful analysis, this growth at each level is just right to set parameters so that we can handle the desired function class.
Using the homomorphic operations described above, we can evaluate any multivariate polynomial f ∈ P(D, M ), written as f (x 1 , . . . , x m ) = S∈Λ c S • x S , by first locally evaluating each monomial x S , then locally taking a linear combination of the results. Finally, we describe the reconstruction algorithm HSS.Rec. At the end of the local computations, each party P will hold a noisy share y of the output y = f (x). Since these are LSS shares, we may reconstruct a noisy version of y by applying the reconstruction algorithm of LSS.
Noise growth analysis. We now analyze the noise growth of our homomorphic operations. Here, we will write explicit noise terms (colored in red) for our noisy shares:
We start by considering party 's homomorphic multiplication of an input x i , shared as sh (x i ), with an intermediate value y, shared as y , { y
Next, compute secret sharings (for all i ∈ [m], j ∈ [n]):
-Eval( , P, sh (x)) → osh P, . Given a party index ∈ [N ], a m-variate polynomial P ∈ P(D, M ), and the corresponding share sh (x), we first evaluate each monomial of P , then add these monomials together. The party P stores, for each intermediate value z during the computation, a noisy share
defined as follows:
where y is an intermediate value and xi is an input, parse { {y} } as above, then compute
• If z = γ cγ • yγ where cγ are coefficients and yγ are intermediate values, parse { {yγ} } as above, then compute
Once party P has computed the noisy share { {z} } for the final output P (x), return osh P, := z . -Rec(I, {osh } ∈I ) → z. Given a subset of parties I ⊂ [N ] and corresponding output shares {osh } ∈I , return z ← LSS.Rec (I, {osh } ∈I ).
where we denote the noise term in blue (which has a fixed noise rate O(n -δ )), we can compute the following:
Similarly, we can compute the noise growth for the noisy shares
We observe that after multiplication, the noisy shares x i • y and x i • y • s j both contain one new noise term, and due to the k-sparsity of a i and (2k -1)sparsity of a i,j , aggregate at most 2k prior noises. Therefore, the rate of noise increase by a factor of at most 2k + 1. As we started out with noise level n -δ for some arbitrary δ ∈ (0, 1), after D steps the noise level is at most (2k + 1) D n -δ . Next, we consider the noise growth for homomorphic linear combination. Here, the error growth is much less, allowing us to aggregate M error terms for arbitrary M = poly(λ). Namely, for any coefficients c γ ∈ F q and any intermediate noisy shares { {y γ } } with γ ∈ [M ], we have:
The noise level for the final share grows by a factor of M .
For a given program class P(F q , D, M), given any constant δ ∈ (0, 1) for which the Sparse LPN assumption holds, and given desired correctness error ∈ (0, 1), we need to choose k and n so that
When D = O(log λ/ log log λ), M = poly(λ), and = 1/ poly(λ), we may choose k = log c λ for a sufficiently small constant c > 0, and n = λ c for a sufficiently large constant c > 0 for the above conditions to hold.
Our HSS input share size |sh (x)|, for x ∈ F m q , is equal to m(n+1)+mn(n+1)+(m+mn)|LSS| = m(n+1)((n+1)+|LSS|), where |LSS| is the share size of the linear secret sharing scheme. In particular, by Remark 5.1 this share size depends on program class P(D, M ) supported (since n depends on D and M ). In contrast, our HSS output share is just an LSS share. We also note that when LSS is the Shamir secret sharing scheme, the share size |LSS| is e field elements, where e ∈ N is the smallest integer such that t < q e . For computation, our HSS evaluation only has an overhead of O(nk|LSS|), since we need to compute on n + 1 shares y , { y • s j } j∈ [n] , and during multiplication we suffer another O(k) overhead in computing a linear combination of (k + 1) terms.
While Sparse LPN has been extensively studied in the asymptotic setting (see our discussion in Sect. 1.1), there have been little work on determining concrete parameters for the assumption. Prior works such as [6,54] proposed parameters for Sparse LPN in the constant noise regime, while our noise rate is smaller, namely 1/n δ for an arbitrary 0 < δ < 1. Thus, we leave as interesting open questions the task of figuring out concrete parameters for Sparse LPN in our noise regime, and optimizing our HSS to be more efficient.
In fact, our HSS construction can be made even more efficient than Remark 5.2 for polynomials of constant degree D, where we may achieve O(k D • M ) computation overhead for polynomials with M monomials. If we were to set k = O(1), then the overhead is constant in M . This follows from a more conservative computation of only the necessary values required to evaluate the polynomial. Namely, each homomorphic multiplication of an intermediate value y with an input x i requires only (k + 1) secret shares {[[ys σ ]]} σ∈Supp(a) . As a consequence, each degree D monomial computation will touch at most O(k D ) sparse LPN samples and secret shares and involve roughly these many binary additions and multiplications.
From our noise growth analysis above and the subsequent Remark 5.1 on parameter selection, we can conclude the correctness of our HSS construction.
Assume the Sparse LPN assumption holds with constant δ ∈ (0, 1). For any = 1/ poly(λ), any D = O(log λ/ log log λ), and any M = poly(λ), for parameters n and k chosen according to Remark 5.1, the resulting HSS construction in Fig. 2 is correct except with probability . Remark 5.6 (Decreasing the correctness error). We note that our correctness error can be decreased to negl(λ), at the cost of larger share sizes, more computation, and making reconstruction non-additive. This is done by giving out some κ = ω(1) copies of the same HSS sharings, each with fresh randomness, doing HSS evaluations of the same function for each of these sharings, then taking majority.
We will now show that our HSS scheme is secure. Again, most of the heavy lifting is done in Lemma 4.4, from which our proof follows almost immediately. Lemma 5.7 (Security of HSS). Assume the Sparse LPN assumption holds with constant δ ∈ (0, 1). For any finite field F q , any number of parties N ≥ 2, any threshold t < N, any D = O(log λ/ log log λ), and any M = poly(λ), with parameters chosen as in Remark 5.1, the N -party HSS construction in Fig. 2 for the class P(F q , D, M) satisfies HSS security with threshold t.
Proof. Recall that for security of HSS, we need to show that for any subset I ⊂ [N ] of size |I| ≤ t and any vectors x, x ∈ F m q , the shares {sh (x)} ∈I and {sh (x )} ∈I are computationally indistinguishable. By construction of HSS.Share, these shares consist of two parts, the KDM ciphertexts {ct s (x), ct s (x ⊗ s)} versus {ct s (x ), ct s (x ⊗ s)}, along with the LSS shares
The former is indistinguishable due to Lemma 4.4 (for q = 2, we may take any of the approaches, detailed in the full version, to conclude Lemma 4.4), and the latter is indistinguishable due to t-privacy of LSS.
Putting everything together, we get our HSS with desired functionality. Theorem 5.8 (Multi-party HSS). Assume the Sparse LPN assumption (c.f. Assumption 4.1) holds. For any number of parties N ≥ 2, privacy threshold t < N, finite field F q , and error probability = 1/ poly(λ), there is a N -party, t-private HSS with correctness error for the function class P(F q , D, M) with degree D = O(log λ/ log log λ) and number of monomials M = poly(λ).
In the full version, we will present the packed HSS variant that allows us to conclude Theorem 1.3.
In this section, we leverage our HSS in Sect. 5 to build a sublinear MPC, with per-party communication dominated by the term O(S/ log log S), for layered Boolean circuits of size S. 10 Our MPC construction can support an arbitrary N = poly(λ) parties with up to (N -1)-out-of-N corruptions.
Layered Boolean Circuits. Our MPC construction achieves sublinear communication for the class of layered Boolean circuits. A Boolean circuit C : {0, 1} n → {0, 1} m is layered if its nodes can be partitioned into D = depth(C) layers (L 1 , . . . , L D ) such that any edge (u, v) of C satisfies u ∈ L i and v ∈ L i+1 for some i ≤ D -1. The width width(C) of a layered circuit C is defined to be the maximum number of non-output gates contained in any single layer. In our MPC, we assume that the parties input are x 1 , . . . , x N , concatenated into x := x 1 x 2 . . . x N . Then x is the overall input to the circuit C, and at the end of the MPC, each party should get C(x). Remark 6.1 (Circuit Decomposition). From an existing result in [19], for any d ∈ N, we have a decomposition of C into L = D/d special layers (L 1 , . . . , L L ) such that: (1) two consecutive layers are of distance at most 2d from each other, and (2) letting w i be the width of layer L i for all i ∈ [L], we have L i=1 w i ≤ S/d. We denote by C i,j the circuit computing the j th output of layer L i+1 from the inputs of layer L i , for all i ∈ [L -1], j ∈ [w i+1 ].
For simplicity, in our MPC construction we will assume that all the inputs to C are in the first layer, and all outputs are in the last layer. This is without loss of generality, as all intermediate values in our construction are represented in the same form; thus, we can "delay" an input until it is needed in an intermediate layer, and similarly delay an output till the end.
Protocol Description. Following the main ideas discussed in Sect. 2.3, we now give our MPC construction in Figs. 3 and4. In our construction, we assume that each party has access to a broadcast channel. This is simply for ease of presentation, since in the semi-honest model we can simulate such a broadcast channel by letting parties pass messages in a cyclic or star-like fashion. In the full version, we will prove that our MPC is secure, with desired sublinear per-party communication as in Theorem 1.2. Remark 6.2 (Removing dependence on width). We note that our MPC incurs a communication cost proportional to the circuit width W , due to the use of the public vectors {a i2,i3 } i2∈[W ],i3∈ [κ] . We suggest two main approaches to reduce/eliminate the additive term proportional to the width.
-If the number of parties are large, since this is a semi-honest protocol, each party can be required to output W •κ N such vectors, as opposed to running the MPC for computing W • κ such vectors. In this case this additive term can be replaced by a term that grows like W • poly(log N, log λ)/N . This per party communication becomes sublinear for big enough N .
-Since these vectors are chosen randomly (among all k Enc -sparse vectors), this term can be removed altogether if we are willing to assume any of the following: 1) a uniform random string, 2) a random oracle, or 3) an explicit family of k Enc -sparse matrices for which the sparse LPN assumption holds. Any of these assumptions allow the parties to have the description of a i2,i3 without any further communication.
A trivial solution is letting the output shares be (f, xj) and Rec reconstruct x from the shares and then compute f . However, this solution is uninteresting since it is not useful.
The work of[18] builds 2-party HSS for general polynomial-sized computation from subexponentially secure iO and one-way functions. Their construction can be extended to the multiparty setting.
Namely, the PKE constructed in[4] can be directly transformed into a semi-honest OT.
In such a setting, we shall use public matrices from specific distributions instead of being uniform. See Remark 4.2 for a discussion.
The download rate is the ratio of the output size over the sum of all output share sizes (for details, see[35]).
The latter conditions rule out HSS schemes in which the output shares contain a homomorphic encryption of the output. Such schemes can only achieve good rate when the output size is much bigger than the (computational) security parameter.
An HSS scheme has Las-Vegas correctness with error if each output share can be set to ⊥ with at most probability, and if no output share is set to ⊥ then the shares must always add up to the correct output.
For example, the distribution in the work of Applebaum and Kachlon[9].
More generally, our construction can generalize to any constant-size field. For simplicity, we only cover the Boolean case.