International Association
for Cryptologic Research

We put forth and instantiate a new primitive of simultaneous-message, succinct (SMS) secure computation. Given a common reference string (CRS) setup phase, an SMS protocol for function f between two parties with inputs X, y has the following structure: - Parties simultaneously exchange a single message, - Communication is succinct, scaling with the shorter of the parties' inputs y, sublinear in the size of a long input X and output f(X,y), - Without further interaction, the parties can locally derive additive secret shares of f(X,y). SMS protocols enable a minimal communication structure for secure computation of the following scenario: Alice has a large private input X, Bob has a small private input y, and Charlie wants to learn f(X,y) for some public function f. Indeed, Alice and Bob simultaneously send each other a message using the CRS and their private inputs. Using the transcript and their private state, the parties obtain additive secret sharing of f(X,y), which they can send to Charlie incurring communication cost only twice that of the function output length. Importantly, the size of Alice's message does not grow with the size of her input X, and both Alice and Bob's first round message grow sub-linearly in the size of the output. In addition, Alice or Bob's view provides no information about the other party's input, even when they collude with Charlie. We obtain the following results: - Assuming Learning With Errors (LWE), we build an SMS protocol supporting evaluation of depth-d circuits. Alice's message is of size |f(X,y)|^(2/3) · poly(λ,d), and Bob's message is of size (|y| + |f(X,y)|^(2/3)) · poly(λ,d), where λ is the security parameter. - Assuming sub-exponentially secure indistinguishability obfuscation and somewhere-statistically-binding hash functions, we build SMS protocols supporting arbitrary polynomial-sized batch functions of the form (f(x_1,y),...,f(x_L,y)), for X = (x_1,...,x_L). The size of both Alice and Bob's messages in this construction is |f| · poly(λ,log L). We give several applications of SMS protocols, including: - Trapdoor hash functions (TDH) (Döttling et al., Crypto'19) for the same function class as SMS, in turn obtaining the first construction of TDH beyond linear functions from LWE. - A simple compiler for obtaining rate-1 fully homomorphic encryption (FHE) from any non-compact FHE scheme. - Correlation-intractable hash functions that are secure against all efficiently searchable relations.

Homomorphic secret sharing (HSS) is a distributed analogue of fully homomorphic encryption (FHE) where following an input-sharing phase, two or more parties can locally compute a function over their private inputs to obtain shares of the function output. Over the last decade, HSS schemes have been constructed from an array of different assumptions. However, all existing HSS schemes, except ones based on assumptions known to imply multi-key FHE, require a public-key infrastructure (PKI) or a correlated setup between parties. This limitation carries over to many applications of HSS. In this work, we construct *multi-key* homomorphic secret sharing (MKHSS), where given only a common reference string (CRS), two parties can secret share their inputs to each other and then perform local computations as in HSS, eliminating the need for PKI or a correlated setup. Specifically, we present the first MKHSS schemes supporting all NC1 computations from either the decisional Diffie--Hellman (DDH) assumption, the decisional composite residuosity (DCR) assumption, or DDH-like assumptions in class group. Our constructions imply the following applications in the CRS model: - Succinct two-round secure computation. Under the same assumptions as our MKHSS schemes, we construct a succinct, two-round, two-party secure computation protocol for NC1 circuits. Previously, such a result was only known from the learning with errors assumption. - Attribute-based NIKE. Under DCR or class group assumptions, we construct non-interactive key exchange (NIKE) protocols where two parties agree on a key if and only if their secret attributes satisfy a public NC1 predicate. This significantly generalizes the existing notion of password-based NIKE. - Public-key PCFs. Under DCR or class group assumptions, we construct public-key pseudorandom correlation functions (PCFs) for any NC1 correlation. This yields the first public-key PCFs for Beaver triples (and more) from non-lattice assumptions. - Silent MPC. Under DCR or class group assumptions, we construct a p-party secure computation protocol in the silent preprocessing model where the preprocessing phase has communication O(p), ignoring polynomial factors. All prior protocols that do not rely on multi-key FHE techniques require ω(p²) communication.

Distributed Point Functions (DPFs) are a useful cryptographic primitive enabling a dealer to distribute short keys to two parties, such that the keys encode additive secret shares of a secret point function. However, in many applications of DPFs, no single dealer entity has full knowledge of the secret point function, necessitating the parties to run an interactive protocol to emulate the setup. Prior works have aimed to minimize complexity metrics of such distributed setup protocols, e.g., round complexity, while remaining black-box in the underlying cryptography. We construct Non-Interactive DPFs (NIDPF), which have a one-round (semi-honest, simultaneous-message) setup protocol, removing the need for a trusted dealer. Specifically, our construction allows each party to publish a special “public key” to a public channel or bulletin board, where the public key encodes the party’s secret function parameters. Using the public key of another party, any pair of parties can locally derive a DPF key for the point function parameterized by the two parties’ joint inputs. We realize NIDPF from an array of standard assumptions, including DCR, SXDH, QR, and LWE. Each party’s public key is of size O(N^2/3), for point functions with a domain of size N, which leads to a sublinear communication setup protocol. The only prior approach to realizing such a non-interactive setup required using multi-key fully-homomorphic encryption or indistinguishability obfuscation. As immediate applications of our construction, we obtain the first “public-key setup” for several existing constructions of pseudorandom correlation generators and “one-round” protocols for secure comparisons.

In this paper, we build a framework for constructing Constrained Pseudorandom Functions (CPRFs) with inner-product constraint predicates, using ideas from subtractive secret sharing and related-key-attack security. Our framework can be instantiated using a random oracle or any suitable Related-Key-Attack (RKA) secure pseudorandom function. We provide three instantiations of our framework: 1. an adaptively-secure construction in the random oracle model; 2. a selectively-secure construction under the DDH assumption; and 3. a selectively-secure construction with a polynomial domain under the assumption that one-way functions exist. All three instantiations are constraint-hiding and support inner-product predicates, leading to the first constructions of such expressive CPRFs under each corresponding assumption. Moreover, while the OWF-based construction is primarily of theoretical interest, the random oracle and DDH-based constructions are concretely efficient, which we show via an implementation.

Oblivious Transfer (OT) is at the heart of secure computation and is a foundation for many applications in cryptography. Over two decades of work have led to extremely efficient protocols for efficiently evaluating OT instances in the preprocessing model, through a paradigm called OT extension. A few OT instances generated in an offline phase can be used to perform many OTs in an online phase efficiently, i.e., with very low communication and computational overheads. Specifically, traditional OT extension uses a small number of “base” OTs, generated using any black-box OT protocol, and convert them into many OT instances using only lightweight symmetric-key primitives. Recently, a new paradigm of OT with a public-key setup has emerged, which replaces the base OTs with a non-interactive setup: Using only the public key of the other party, two parties can efficiently compute a virtually unbounded number of OT instances on-the-fly. In this paper, we put forth a novel framework for OT extension with a public-key setup (henceforth, “public-key OT”) and concretely efficient instantiations. Implementations of our framework are 30–100× faster when compared to the previous state-of-the-art public-key OT protocols, and remain competitive even when compared to OT protocols that do not offer a public-key setup. Additionally, our instantiations result in the first public-key schemes with plausible post-quantum security. In summary, this paper contributes: - QuietOT: A framework for OT extension with public-key setup that uses fast, symmetric-key primitives to generate OT instances following a one-time public-key setup, and offering additional features such as precomputability. - A public-key setup for QuietOT from the RingLWE assumption, resulting in the first post-quantum construction of OT extension with a public-key setup. - An optimized, open-source implementation of our construction that can generate up to 1M OT extensions per second on commodity hardware. In contrast, the state-of-the-art public-key OT protocol is limited to at most 20K OTs per second. - The first formal treatment of the security of OT with a public-key setup in a multi-party setting, which addresses several subtleties that were overlooked in prior work.

Secure Multi-party Computation (MPC) allows two or more parties to compute any public function over their privately-held inputs, without revealing any information beyond the result of the computation. Modern protocols for MPC generate a large amount of input-independent preprocessing material called multiplication triples, in an offline phase. This preprocessing can later be used by the parties to efficiently instantiate an input-dependent online phase computing the function. To date, the state-of-the-art secure multi-party computation protocols in the preprocessing model are tailored to secure computation of arithmetic circuits over large fields and require little communication in the preprocessing phase, typically O(N · m) to generate m triples among N parties. In contrast, when it comes to computing preprocessing for computations that are naturally represented as Boolean circuits, the state-of-the-art techniques have not evolved since the 1980s, and in particular, require every pair of parties to execute a large number of oblivious transfers before interacting to convert them to N-party triples, which induces an Ω(N^2 · m) communication overhead. In this paper, we introduce F4OLEAGE, which addresses this gap by introducing an efficient preprocessing protocol tailored to Boolean circuits. F4OLEAGE exhibits excellent performance: it generates m multiplication triples over F2 using only N · m + O(N^2 · log m) bits of communication for N-parties, and can concretely produce over 12 million triples per second in the 2-party setting on one core of a commodity machine. Our result builds upon an efficient Pseudorandom Correlation Generator (PCG) for multiplications triples over the field F4. Roughly speaking, a PCG enables parties to stretch a short seed into a large number of pseudorandom correlations non-interactively, which greatly improves the efficiency of the offline phase in MPC protocols. Our construction significantly outperforms the state-of-the-art, which we demonstrate via a prototype implementation. This is achieved by introducing a number of protocol-level, algorithmic-level, and implementation-level optimizations on the recent PCG construction of Bombar et al. (Crypto 2023) from the Quasi-Abelian Syndrome Decoding assumption.