Multi-point function secret sharing (FSS) is a building block for pseudo-random correlation generators used in novel silent correlation generation methods for various secure multi-party computation applications. However, the main construction used so far is the naive approach to combining several point functions. In this paper, we propose an efficient and natural generalisation of the point function FSS scheme of Boyle et al. 2016 using a tree structure, a pseudorandom generator and systems of linear equations. We propose a new notion of distributed random multi-point function. Our construction splits the distributed multi-point function scheme into a random multi-point function scheme and an algorithm to transform a random output into the desired output value. The resulting scheme, which we call SLAMP-FSS, improves upon the state of the art in terms of calls to a pseudorandom generator (PRG).
Multi-point function secret sharing (FSS) is a building block for pseudo-random correlation generators used in novel silent correlation generation methods for various secure multi-party computation applications. However, the main construction used so far is the naive approach to combining several point functions. In this paper, we propose an efficient and natural generalisation of the point function FSS scheme of Boyle et al. 2016 using a tree structure, a pseudorandom generator and systems of linear equations. We propose a new notion of distributed random multi-point function. Our construction splits the distributed multi-point function scheme into a random multi-point function scheme and an algorithm to transform a random output into the desired output value. The resulting scheme, which we call SLAMP-FSS, improves upon the state of the art in terms of calls to a pseudorandom generator (PRG).
A (t, r)-function secret sharing ((t, r)-FSS) scheme allows a dealer to secret-share a functionf among r parties as r secret keys k1, ... , krsuch that for any input x the parties can compute r output shares that allow the reconstruction of f (x) but any ≤ t of the parties cannot learn any information aboutf. FSS schemes for point functions have been constructed under the name of distributed point functions (DPFs). The existing DPFs are computationally secure and based on the existence of PRGs or OWFs. As a result, the protocols where DPFs work as building blocks are computationally secure as well. In this paper, we study information-theoretically secure (t, r)-FSS (called (t, r)-itFSS) and propose a generic transformation from information-theoretic private information retrieval (PIR) schemes to itFSS schemes for point functions. We measure the efficiency of itFSS with its communication complexity, which can be defined as the total length of the secret keys and the output shares, maximized over the choices off and x. By instantiating the generic transformation, we obtain (t, r)-itFSS schemes for a variety of choices of (t, r), which have sublinear (in the functions' domain size) communication complexity. How to make sure that the parties' shares of f (x) do not reveal more information than what needed to computef(x) is an interesting problem. An itFSS with this property is called function-private. In this paper, we also define a parameter called the mutual rate of itFSS in order to measure the amount of information that will be leaked by the parties' output shares. We calculate the mutual rates for several specific itFSS schemes. We also define computational function privacy and propose a 2-party itFSS scheme with computational function privacy.
Function secret sharing (FSS) is a cryptographic primitive that is introduced by Boyle et al. (Eurocrypt 2015), motivated by application scenarios involving private access to large distributed data while minimising the overhead of communication, for example, private information retrieval. Informally, an n-party FSS scheme splits a function f into n functions f1,...,fnsuch that f = f1+...+ fnand every strict subset of the function shares hide f . Most of the known FSS constructions only have computational hiding, namely, the hiding property holds only against a computationally bounded adversary. We consider information-theoretic hiding in this work while allowing f to be recovered from t function shares and correspondingly, any (t - 1) function shares unconditionally hide f . Call it (t, n)-threshold function secret sharing ((t, n)-TFSS for short). Using information-theoretic tools and through a series of optimizations, we show that our (t, n)-TFSS have better performance than FSS in terms of communication complexity, a criterion that measures the efficiency of such protocols. Specifically, a (t, n)-TFSS scheme with communication complexity O(l) is designed in this paper and it is better than the existing FSS schemes with lowest communication complexity O(λl), where λ is the length of pseudo-random generator's seeds. In addition, the (t, n)-TFSS have an extra robustness property in the sense that even if up to (n - t) function shares are not available, the protocol still computes the function value at a given point correctly.
We consider the problem of actively secure two-party machine-learning inference in the preprocessing model, where the parties obtain (input-independent) correlated randomness in an offline phase that they can then use to run an efficient protocol in the (input-dependent) online phase. In this setting, the state-of-the-art is the work of Escudero et al. (Crypto 2020); unfortunately, that protocol requires a large amount of correlated randomness, extensive communication, and many rounds of interaction, which leads to poor performance. In this work, we show protocols for this setting based on function secret sharing (FSS) that beat the state-of-the-art in all parameters: they use less correlated randomness and fewer rounds, and require lower communication and computation. We achieve this in part by allowing for a mix of boolean and arithmetic values in FSS-based protocols (something not done in prior work), as well as by relying on “interactive FSS;’ a generalization of FSS we introduce. To demonstrate the effectiveness of our approach we build SHARK-the first FSS-based system for actively secure inference-which outperforms the state-of-the-art by up to 2300×.
Abstract. As an extension of multi-party computation (MPC), we propose the concept of secure parallel multi-party computation which is to securely compute multi-functions against an adversary with multistructures. Precisely, there are m functions f1,..., fm and m adversary structures A1,..., Am, where fi is required to be securely computed against an Ai-adversary. We give a general construction to build a parallel multi-party computation protocol from any linear multi-secret sharing scheme (LMSSS), provided that the access structures of the LMSSS allow MPC at all. When computing complicated functions, our protocol has more advantage in communication complexity than the “direct sum” method which actually executes a MPC protocol for each function. The paper also provides an efficient and generic construction to obtain from any LMSSS a multiplicative LMSSS for the same multi-access structure. 1
A Distributed Point Function (DPF) is a crypto-graphic primitive used for compressing additive secret shares of a secret unit vector across two parties. Many DPF applications require compressed shares of a sparse weight- t vector, namely a Distributed Multi-Point Function (DMPF). Despite the strong motivation and prior optimization efforts, in most use cases the best practical implementation of DMPF is still a simple brute-force combination oftindependent DPFs. We present new constructions and optimized implementations of DMPFs in different parameter regimes, providing significant efficiency savings over existing approaches. We showcase our new constructions within applications of pseu-dorandom correlation generators (PCGs) and 2-server private set intersection (PSI). Incorporating our tools into the state-of-the-art PCG for “silent” generation of binary multiplication triples (FOLEAGE, Bombar et al, ePrint'24) yields a x2.68 improvement in throughput, with only x 1.4 blowup in the seed size. On a single core of our benchmark machine, our implementation silently generates up to 22.1 million triples per second, outperforming even the best “non-silent” protocol (Roy, CRYPTO'22), which generates 16 million triples per second.
While classically cryptography is concerned with the problem of private communication among two entities, say players, in modern cryptography multi-player protocols play an important role.And among these, it is probably fair to say that secret sharing, and its stronger version verifiable secret sharing (VSS), as well as multi-party computation (MPC) belong to the most appealing and/or useful ones.The former two are basic tools to achieve better robustness of cryptographic schemes against malfunction or misuse by "decentralizing" the security from one single to a whole group of individuals (captured by the term threshold cryptography).The latter allows-at least in principle-to execute any collaboration among a group of players in a secure way that guarantees the correctness of the outcome but simultaneously respects the privacy of the participants.In this work, we study three aspects of secret sharing, VSS and MPC, which we denote by fundamentals, generality, and efficiency.By fundamentals we mean the quest for understanding why a protocol works and is secure in abstract (and hopefully simple) mathematical terms.By generality we mean generality with respect to the underlying mathematical structure, in other words, minimizing the mathematical axioms required to do some task.And efficiency of course deals with the improvement of protocols with respect to some meaningful complexity measure.We briefly summarize our main results.(1) We give a complete characterization of blackbox secret sharing in terms of simple algebraic conditions on the integer sharing coefficients, and we propose a black-box secret sharing scheme with minimal expansion factor.Note that, in contrast to the classical field-based secret sharing schemes, a black-box secret sharing scheme allows to share a secret sampled from an arbitrary Abelian group and requires only black-box access to the group operations and to random group elements.Such a scheme may be very useful in the construction of threshold cryptosystems based on groups with secret order (like RSA).(2) We show that without loss of efficiency, MPC can be based on arbitrary finite rings.This is in sharp contrast to the literature where essentially all MPC protocols require a much stronger mathematical structure, namely a field.Apart from its theoretical value, this can lead to efficiency improvements since it allows a greater freedom in the (mathematical) representation of the task that needs to be securely executed.(3) We propose a unified treatment of perfectly secure linear VSS and distributed commitments (a weaker version of the former), and we show that the security of such a scheme can be reduced to a linear algebra condition.The security of all known schemes follows as corollaries whose proofs are pure linear algebra arguments, in contrast v to some hybrid arguments used in the literature.(4) We construct a new unconditionally secure VSS scheme with minimized reconstruction complexity in the setting of a dishonest minority.This improves on the reconstruction complexity of the previously best known scheme without affecting the (asymptotic) complexity of the sharing phase.In the context of MPC with pre-processing, our scheme allows to improve the computation phase of earlier protocols without increasing the complexity of the pre-processing.(5) Finally, we consider commitment multiplication proofs, which allow to prove a multiplicative relation among three commitments, and which play a crucial role in computationally secure MPC.We study a non-interactive solution which works in a distributed-verifier setting and essentially consists of a few executions of Pedersen's VSS.We simplify and improve the protocol, and we point out a (previously overlooked) property which helps to construct non-interactive proofs of partial knowledge in this setting.This allows for instance to prove the knowledge of ℓ out of m given secrets, without revealing which ones.We also construct a noninteractive distributed-verifier proof of circuit satisfiability, which-in principle-allows to prove anything that can be proven without giving away the proof.