Advances in Cryptology – EUROCRYPT 2024

Garbled Circuit (GC) techniques usually work with Boolean circuits. Despite intense interest, efficient arithmetic generalizations of GC were only known from strong assumptions, such as LWE.

We construct symmetric-key-based arithmetic garbled circuits from circular correlation robust hashes, the assumption underlying the celebrated Free XOR garbling technique. Let \(\lambda \) denote a security parameter, and consider the integers \(\mathbb {Z}_m\) for any \(m \ge 2\). Let \(\ell = \lceil \log _2 m \rceil \) be the bit length of \(\mathbb {Z}_m\) values. We garble arithmetic circuits over \(\mathbb {Z}_m\) where the garbling of each gate has size \(O(\ell \cdot \lambda )\) bits. Contrast this with Boolean-circuit-based arithmetic, requiring \(O(\ell ^2\cdot \lambda )\) bits via the schoolbook multiplication algorithm, or \(O(\ell ^{1.585}\cdot \lambda )\) bits via Karatsuba’s algorithm.

Our arithmetic gates are compatible with Boolean operations and with Garbled RAM, allowing to garble complex programs of arithmetic values.

In the setting of solitary output computations, only a single designated party learns the output of some function applied to the private inputs of all participating parties with the guarantee that nothing beyond the output is revealed. The setting of solitary output functionalities is a special case of secure multiparty computation, which allows a set of mutually distrusting parties to compute some function of their private inputs. The computation should guarantee some security properties, such as correctness, privacy, fairness, and output delivery. Full security captures all these properties together.

Solitary output computation is a common setting that has become increasingly important, as it is relevant to many real-world scenarios, such as federated learning and set disjointness. In the set-disjointness problem, a set of parties with private datasets wish to convey to another party whether they have a common input. In this work, we investigate the limits of achieving set-disjointness which already has numerous applications and whose feasibility (under non-trivial conditions) was left open in the work of Halevi et al. (TCC 2019).

Towards resolving this, we completely characterize the set of Boolean functions that can be computed in the three-party setting in the face of a malicious adversary that corrupts up to two of the parties. As a corollary, we characterize the family of set-disjointness functions that can be computed in this setting, providing somewhat surprising results regarding this family and resolving the open question posed by Halevi et al.

The combination of these features makes our protocols a good match for implementing a signature service over a public blockchain with many validators, where guaranteed output delivery is an absolute must. In that setting, there is a system-wide public key, where the corresponding secret signature key is distributed among the validators. Clients can submit messages (under suitable controls, e.g., smart contracts), and authorized messages are signed relative to the global public key.

Asymptotically, when running with committees of n parties, our protocols can generate \(\varOmega (n^2)\) signatures per run, while providing resilience against \(\varOmega (n)\) corrupted nodes and broadcasting only \(O(n^2)\) group elements and scalars (hence O(1) elements per signature).

We prove the security of our protocols via a reduction to the hardness of the discrete logarithm problem in the random oracle model.

Motivated by secure database search, we present secure computation protocols for a function f in the client-servers setting, where a client can obtain f(x) on a private input x by communicating with multiple servers each holding f. Specifically, we propose generic compilers from passively secure protocols, which only keep security against servers following the protocols, to actively secure protocols, which guarantee privacy and correctness even against malicious servers. Our compilers are applied to protocols computing any class of functions, and are efficient in that the overheads in communication and computational complexity are only polynomial in the number of servers, independent of the complexity of functions. We then apply our compilers to obtain concrete actively secure protocols for various functions including private information retrieval (PIR), bounded-degree multivariate polynomials and constant-depth circuits. For example, our actively secure PIR protocols achieve exponentially better computational complexity in the number of servers than the currently best-known protocols. Furthermore, our protocols for polynomials and constant-depth circuits reduce the required number of servers compared to the previous actively secure protocols. In particular, our protocol instantiated from the sparse Learning Parity with Noise (LPN) assumption is the first actively secure protocol for multivariate polynomials which has the minimum number of servers, without assuming fully homomorphic encryption.

Common randomness is an essential resource in many applications. However, Cleve (STOC 86) rules out the possibility of tossing a fair coin from scratch in the presence of a dishonest majority. A second-best alternative is a Coin Tossing Extension (CTE) protocol, which uses an “online” oracle that produces a few common random bits to generate many common random-looking bits. We initiate the systematic study of fully-secure CTE, which guarantees output even in the presence of malicious behavior. A fully-secure two-party statistical CTE protocol with black-box simulation was implicit in Hofheinz et al. (Eurocrypt 06), but its round complexity is nearly linear in its output length. The problem of constant-round CTE with superlogarithmic stretch remained open.

We prove that statistical CTE with full black-box security and superlogarithmic stretch must have superconstant rounds. In the computational setting we prove that with \(N\ge 2\) parties and polynomial stretch:

To date, the strongest notions of security achievable for two-round publicly-verifiable cryptographic proofs for \(\textsf{NP}\) are witness indistinguishability (Dwork-Naor 2000, Groth-Ostrovsky-Sahai 2006), witness hiding (Bitansky-Khurana-Paneth 2019, Kuykendall-Zhandry 2020), and super-polynomial simulation (Pass 2003, Khurana-Sahai 2017). On the other hand, zero-knowledge and even weak zero-knowledge (Dwork-Naor-Reingold-Stockmeyer 1999) are impossible in the two-round publicly-verifiable setting (Goldreich-Oren 1994). This leaves an enormous gap in our theoretical understanding of known achievable security and the impossibility results for two-round publicly-verifiable cryptographic proofs for \(\textsf{NP}\).

Towards filling this gap, we propose a new and natural notion of security, called witness semantic security, that captures the natural and strong notion that an adversary should not be able to learn any partial information about the prover’s witness beyond what it could learn given only the statement x. Not only does our notion of witness semantic security subsume both witness indistinguishability and witness hiding, but it also has an easily appreciable interpretation.

Moreover, we show that assuming the subexponential hardness of LWE, there exists a two-round public-coin publicly-verifiable witness semantic secure argument. To our knowledge, this is the strongest form of security known for this setting.

As a key application of our work, we show that non-interactive zero-knowledge (NIZK) arguments in the common reference string (CRS) model can additionally maintain witness semantic security even when the CRS is maliciously generated. Our work gives the first construction from (subexponential) standard assumptions that achieves a notion stronger than witness-indistinguishability against a malicious CRS authority.

In order to achieve our results, we give the first construction of a ZAP from subexponential LWE that is adaptively sound. Additionally, we propose a notion of simulation using non-uniform advice about a malicious CRS, which we also believe will be of independent interest.

Garbled Circuit (GC) is a basic technique for practical secure computation. GC handles Boolean circuits; it consumes significant network bandwidth to transmit encoded gate truth tables, each of which scales with the computational security parameter \(\kappa \). GC optimizations that reduce bandwidth consumption are valuable.

It is natural to consider a generalization of Boolean two-input one-output gates (represented by 4-row one-column lookup tables, LUTs) to arbitrary N-row m-column LUTs. Known techniques for this do not scale, with naïve size-\(O(Nm\kappa )\) garbled LUT being the most practical approach in many scenarios.

Our novel garbling scheme – \(\textsf{logrow}\) – implements GC LUTs while sending only a logarithmic in N number of ciphertexts! Specifically, let \(n = \lceil \log _2 N \rceil \). We allow the GC parties to evaluate a LUT for \((n-1)\kappa + nm\kappa + Nm\) bits of communication. \(\textsf{logrow}\) is compatible with modern GC advances, e.g. half gates and free XOR.

Our work improves state-of-the-art GC handling of several interesting applications, such as privacy-preserving machine learning, floating-point arithmetic, and DFA evaluation.

Publicly Verifiable Secret Sharing (PVSS) allows a dealer to publish encrypted shares of a secret so that parties holding the corresponding decryption keys may later reconstruct it. Both dealing and reconstruction are non-interactive and any verifier can check their validity. PVSS finds applications in randomness beacons, distributed key generation (DKG) and in YOSO MPC (Gentry et al. CRYPTO’21), when endowed with suitable publicly verifiable re-sharing as in YOLO YOSO (Cascudo et al. ASIACRYPT’22).

Building on our PVSS scheme’s ability to recover the original secret, we propose two DKG protocols for discrete logarithm key pairs: a biasable 1-round protocol, which improves on the concrete communication/computational complexities of previous works; and a 2-round unbiasable protocol, which improves on the round complexity of previous works. We also add publicly verifiable resharing towards anonymous committees to our PVSS, so that it can be used to efficiently transfer state among committees in the YOSO setting. Together with a recent construction of MPC in the YOSO model based on class groups (Braun et al. CRYPTO’23), this results in the most efficient full realization (i.e. without assuming receiver anonymous channels) of YOSO MPC based on the CDN framework with transparent setup.

Zero-knowledge proofs are a cryptographic cornerstone of privacy-preserving technologies such as “Confidential Transactions” (CT), which aims at hiding monetary amounts in cryptocurrency transactions. Due to its asymptotically logarithmic proof size and transparent setup, most state-of-the-art CT protocols use the Bulletproofs (BP) [8] zero-knowledge proof system for set membership proofs such as range proofs. However, even taking into account recent efficiency improvements, BP comes with a serious overhead in terms of concrete proof size as well as verifier running time and thus puts a large burden on practical deployments of CT and its extensions.

In this work, we introduce Bulletproofs++ (BP++), a drop-in replacement for BP that improves its concrete efficiency and compactness significantly. As for BP, the security of BP++ relies only on the hardness of the discrete logarithm problem in the random oracle model, and BP++ retains all features of Bulletproofs including transparent setup and support for proof aggregation, multi-party proving and batch verification. Asymptotically, BP++ range proofs require only \(O(n / \log n)\) group scalar multiplications compared to O(n) for BP and BP+.

At the heart of our construction are novel techniques for permutation and set membership, enabling highly efficient proofs of statements encoded as arithmetic circuits. Concretely, a single BP++ range proof to establish that a committed value is in a 64-bit range (as commonly required by CT) is just 416 bytes over a 256-bit elliptic curve, 38% smaller than an equivalent BP and 27% smaller than BP+. When instantiated on the secp256k1 curve as used in Bitcoin, our benchmarks show that proving is about 5 times faster than BP and verification is about 3 times faster than BP+. When aggregating 32 range proofs, proving and verification are about 9.5 times and 5.5 times faster, respectively.

We study secure multiparty computation in the asynchronous setting with perfect security and optimal resilience (less than one-fourth of the participants are malicious). It has been shown that every function can be computed in this model [Ben-OR, Canetti, and Goldreich, STOC’1993]. Despite 30 years of research, all protocols in the asynchronous setting require \(\varOmega (n^2C)\) communication complexity for computing a circuit with C multiplication gates. In contrast, for nearly 15 years, in the synchronous setting, it has been known how to achieve \({\mathcal {O}}(nC)\) communication complexity (Beerliova and Hirt; TCC 2008). The techniques for achieving this result in the synchronous setting are not known to be sufficient for obtaining an analogous result in the asynchronous setting.

We close this gap between synchronous and asynchronous secure computation and show the first asynchronous protocol with \({\mathcal {O}}(nC)\) communication complexity for a circuit with C multiplication gates. Linear overhead forms a natural barrier for general secret-sharing-based MPC protocols. Our main technical contribution is an asynchronous weak binding secret sharing that achieves rate-1 communication (i.e., \({\mathcal {O}}(1)\)-overhead per secret). To achieve this goal, we develop new techniques for the asynchronous setting, including the use of trivariate polynomials (as opposed to bivariate polynomials).

We study broadcast protocols in the information-theoretic model under optimal conditions, where the number of corruptions t is at most one-third of the parties, n. While worst-case \(\varOmega (n)\) round broadcast protocols are known to be impossible to achieve, protocols with an expected constant number of rounds have been demonstrated since the seminal work of Feldman and Micali [STOC’88]. Communication complexity for such protocols has gradually improved over the years, reaching O(nL) plus expected \(O(n^4\log n)\) for broadcasting a message of size L bits.

This paper presents a perfectly secure broadcast protocol with expected constant rounds and communication complexity of O(nL) plus expected \(O(n^3 \log ^2n)\) bits. In addition, we consider the problem of parallel broadcast, where n senders, each wish to broadcast a message of size L. We show a parallel broadcast protocol with expected constant rounds and communication complexity of \(O(n^2L)\) plus expected \(O(n^3 \log ^2n)\) bits. Our protocol is optimal (up to expectation) for messages of length \(L \in \varOmega (n \log ^2 n)\).

Our main contribution is a framework for obtaining perfectly secure broadcast with an expected constant number of rounds from a statistically secure verifiable secret sharing. Moreover, we provide a new statistically secure verifiable secret sharing where the broadcast cost per participant is reduced from \(O(n \log n)\) bits to only \(O(\textsf{poly}\log n)\) bits. All our protocols are adaptively secure.

Traditional private set intersection (PSI) involves a receiver and a sender holding sets X and Y, respectively, with the receiver learning only the intersection \(X\cap Y\). We turn our attention to its fuzzy variant, where the receiver holds \(|X|\) hyperballs of radius \(\delta \) in a metric space and the sender has |Y| points. Representing the hyperballs by their center, the receiver learns the points \(x\in X\) for which there exists \(y\in Y\) such that \(\textsf{dist}(x,y)\le \delta \) with respect to some distance metric. Previous approaches either require general-purpose multi-party computation (MPC) techniques like garbled circuits or fully homomorphic encryption (FHE), leak details about the sender’s precise inputs, support limited distance metrics, or scale poorly with the hyperballs’ volume.

This work presents the first black-box construction for fuzzy PSI (including other variants such as PSI cardinality, labeled PSI, and circuit PSI), which can handle polynomially large radius and dimension (i.e., a potentially exponentially large volume) in two interaction messages, supporting general \(L_{\textsf{p}\in [1,\infty ]}\) distance, without relying on garbled circuits or FHE. The protocol excels in both asymptotic and concrete efficiency compared to existing works. For security, we solely rely on the assumption that the Decisional Diffie-Hellman (DDH) holds in the random oracle model.

We present new protocols for threshold Schnorr signatures that work in an asynchronous communication setting, providing robustness and optimal resilience. These protocols provide unprecedented performance in terms of communication and computational complexity. In terms of communication complexity, for each signature, a single party must transmit a few dozen group elements and scalars across the network (independent of the size of the signing committee). In terms of computational complexity, the amortized cost for one party to generate a signature is actually less than that of just running the standard Schnorr signing or verification algorithm (at least for moderately sized signing committees, say, up to 100).

As protocols for verifiably sharing a secret key with an associated public key and the technology of super-invertible matrices both play a major role in threshold cryptography and multi-party computation, our two new innovations should have applicability well beyond that of threshold Schnorr signatures.

A recent work by Ball, Li, Lin, and Liu [Eurocrypt’23] presented a new instantiation of the arithmetic garbling paradigm introduced by Applebaum, Ishai, and Kushilevitz [FOCS’11]. In particular, Ball et al.’s garbling scheme is the first constant-rate garbled circuit over large enough bounded integer computations, inferring the first constant-round constant-rate secure two-party computation (2PC) over bounded integer computations in the presence of semi-honest adversaries.

The main source of difficulty in lifting the security of garbling schemes-based protocols to the malicious setting lies in proving the correctness of the underlying garbling scheme. In this work, we analyze the security of Ball et al.’s scheme in the presence of malicious attacks.

In the consensus problem, n parties want to agree on a common value, even if some of them are corrupt and arbitrarily misbehave. If the parties have a common input m, then they must agree on m.

Protocols solving consensus assume either a synchronous communication network, where messages are delivered within a known time, or an asynchronous network with arbitrary delays. Asynchronous protocols only tolerate \(t_a < n/3\) corrupt parties. Synchronous ones can tolerate \(t_s < n/2\) corruptions with setup, but their security completely breaks down if the synchrony assumptions are violated.

Network-agnostic consensus protocols, as introduced by Blum, Katz, and Loss [TCC’19], are secure regardless of network conditions, tolerating up to \(t_s\) corruptions with synchrony and \(t_a\) without, under provably optimal assumptions \(t_a \le t_s\) and \(2t_s + t_a < n\). Despite efforts to improve their efficiency, all known network-agnostic protocols fall short of the asymptotic complexity of state-of-the-art purely synchronous protocols.

In this work, we introduce a novel technique to compile any synchronous and any asynchronous consensus protocols into a network-agnostic one. This process only incurs a small constant number of overhead rounds, so that the compiled protocol matches the optimal round complexity for synchronous protocols. Our compiler also preserves under a variety of assumptions the asymptotic communication complexity of state-of-the-art synchronous and asynchronous protocols. Hence, it closes the current efficiency gap between synchronous and network-agnostic consensus.

As a plus, our protocols support \(\ell \)-bit inputs, and can be extended to achieve communication complexity \(\mathcal {O}(n^2\kappa + \ell n)\) under the assumptions for which this is known to be possible for purely synchronous protocols.