Multi-party computation (MPC) enables a set of mutually n distrusting parties to compute any function on their private inputs. Mainly, MPC facilitates agreement on the function's output while preserving the secrecy of honest inputs, even against a subset of t parties controlled by an adversary. With applications spanning from anonymous broadcast to private auctions, MPC is considered a cornerstone of distributed cryptography, and significant research efforts have been aimed at making MPC practical in the last decade. However, most libraries either make strong assumptions like the network being bounded synchronous, or incur high computation overhead from the extensive use of expensive public-key operations that prevent them from scaling beyond a few dozen parties. This work presents Velox, an asynchronous MPC protocol that offers fairness against an optimal adversary corrupting up to t < n/3 parties. Velox significantly enhances practicality by leveraging lightweight cryptographic primitives-such as symmetric-key encryption and hash functions-which are 2-3 orders of magnitude faster than public-key operations, resulting in substantial computational efficiency. Moreover, Velox is highly communication-efficient, with linear amortized communication relative to circuit size and only O(n3) field elements of additive overhead. Concretely, Velox requires just 9.33 field elements per party per multiplication gate, more than 10× reduction compared to the state of the art. Moreover, Velox also offers Post-Quantum Security as lightweight cryptographic primitives retain their security against a quantum adversary. We implement Velox comprehensively, covering both offline and online phases, and evaluate its performance on a geographically distributed testbed through a real-world application: anonymous broadcast. Our implementation securely shuffles a batch of k = 256 messages in 4 seconds with n = 16 parties and 18 seconds with n = 64 parties, a 36× and 28.6× reduction in latency compared to the prior best work. At scale with n = 112 parties, Velox is able to shuffle the same batch of messages in under 50 seconds from end to end, illustrating its effectiveness and scalability. Overall, our work removes significant barriers faced by prior asynchronous MPC solutions, making asynchronous MPC practical and efficient for large-scale deployments involving 100s of parties.

Byzantine Agreement (BA) allows a set of n parties to agree on a value even when up to t of the parties involved are corrupted. While previous works have shown that, for ℓ-bit inputs, BA can be achieved with the optimal communication complexity O(ℓn) for sufficiently large ℓ, BA only ensures that honest parties agree on a meaningful output when they hold the same input, rendering the primitive inadequate for many real-world applications.

Abstract Broadcast protocols enable a set of n parties to agree on the input of a designated sender, even facing attacks by malicious parties. In the honest-majority setting, randomization and cryptography were harnessed to achieve low-communication broadcast with sub-quadratic total communication and balanced sub-linear cost per party. However, comparatively little is known in the dishonest-majority setting. Here, the most communication-efficient constructions are based on Dolev and Strong (SICOMP ’83), and sub-quadratic broadcast has not been achieved. On the other hand, the only nontrivial $$\omega (n)$$ ω ( n ) communication lower bounds are restricted to deterministic protocols, or against strong adaptive adversaries that can perform “after the fact” removal of messages. We provide new communication lower bounds in this space, which hold against arbitrary cryptography and setup assumptions, as well as a simple sub-quadratic broadcast protocol showing near tightness of our first bound.

Agreement protocols are crucial in various emerging applications, spanning from distributed (blockchains) oracles to fault-tolerant cyber-physical systems. In scenarios where sensor/oracle nodes measure a common source, maintaining output within the convex range of correct inputs, known as convex validity, is imperative. Present asynchronous convex agreement protocols employ either randomization, incurring substantial computation overhead, or approximate agreement techniques, leading to high$\tilde{\mathcal{O}(n^{3})}$communication for an$n$-node system. This paper introduces Delphi, a deterministic protocol with$\tilde{\mathcal{O}(n^{2})}$communication and minimal computation overhead. Delphi assumes that honest inputs are bounded, except with negligible probability, and integrates agreement primitives from literature with a novel weighted averaging technique. Experimental results highlight Delphi's superior performance, showcasing a significantly lower latency compared to state-of-the-art protocols. Specifically, for an$n$= 160-node system, Delphi achieves an 8x and 3x improvement in latency within CPS and AWS environments, respectively.

Byzantine Agreement (BA) allows a set of n parties to agree on a value even when up to t of the parties involved are corrupted. While previous works have shown that, for ℓ-bit inputs, BA can be achieved with the optimal communication complexity Õ(ℓn) for sufficiently large ℓ, BA only ensures that honest parties agree on a meaningful output when they hold the same input, rendering the primitive inadequate for many real-world applications.

Multidimensional Approximate Agreement considers a setting of n parties, where each party holds a vector in ℝD as input. The honest parties are required to obtain very close outputs in ℝD that lie inside the convex hull of their inputs.

Approximate Agreement (AA) allows a set of n parties that start with real-valued inputs to obtain values that are at most within a parameter ε > 0 from each other and within the range of their inputs. Existing AA protocols, both for the synchronous network model (where any message is delivered within a known delay Δ time) and the asynchronous network model, are secure when up to t < n/3 of the parties are corrupted and require no initial setup (such as a public-key infrastructure (PKI) for signatures). We consider AA protocols where a PKI is available, and show the first AA protocol that achieves simultaneously security against ts corruptions when the network is synchronous and ta corruptions when the network is asynchronous, for any 0 ≤ ta < n/3 ≤ ts < n/2 such that ta + 2 · ts < n. We further show that our protocol is optimal by proving that achieving AA for ta +2·ts ≥ n is impossible (even with setup). Remarkably, this is also the first AA protocol that tolerates more than n/3 corruptions in the synchronous network model.

Minimizing the round complexity of Byzantine Agreement (BA) protocols is a fundamental problem in distributed computing. The typical approach to achieve round efficient (randomized) BA is to have a weak form of BA, called graded consensus (GC), followed by a distributed coin, and to repeat this process until some termination condition is met---as introduced by Feldman and Micali (STOC'88).

Classical protocols for reliable broadcast and consensus provide security guarantees as long as the number of corrupted parties f is bounded by a single given threshold t. If f > t, these protocols are completely deemed insecure. We consider the relaxed notion of multi-threshold reliable broadcast and consensus where validity, consistency and termination are guaranteed as long as f ≤ t_v, f ≤ t_c and f ≤ t_t respectively. For consensus, we consider both variants of (1-ε)-consensus and almost-surely terminating consensus, where termination is guaranteed with probability (1-ε) and 1, respectively. We give a very complete characterization for these primitives in the asynchronous setting and with no signatures: - Multi-threshold reliable broadcast is possible if and only if max{t_c,t_v} + 2t_t < n. - Multi-threshold almost-surely consensus is possible if max{t_c, t_v} + 2t_t < n, 2t_v + t_t < n and t_t < n/3. Assuming a global coin, it is possible if and only if max{t_c, t_v} + 2t_t < n and 2t_v + t_t < n. - Multi-threshold (1-ε)-consensus is possible if and only if max{t_c, t_v} + 2t_t < n and 2t_v + t_t < n.

Commitment schemes that admit zero-knowledge proofs for relations among committed values are known as commit-and-prove functionalities or notarized envelopes. An important role in this context play equality proofs among commitments. They appear in various contexts of multi-party computation, circuit satisfiability or inclusion proofs. Using commit- and-prove functionalities admitting equality, we investigate blackbox constructions of commit-and-prove functionalities admitting more complex relations. Typically, these constructions have to create commitments to additional values to achieve a certain level of soundness. An important efficiency measure is the number of such additional commitments. We prove that, for the natural and quite general class of 3-round public-coin zero-knowledge protocols, implementing the inequality relation, or any of the relations NAND, NOR, or XOR, essentially requires at least 2n additional commitments in order to achieve a soundness of 2-n. A folklore protocol shows that this bound is tight for inequality.

We consider the general setting where users need to provide a secret code c to a verifying entity V in order to obtain access to a resource. More generally, the right to access the resource could, for example, be granted if one knows one of two codes ci and C2. For privacy reasons, a party P may want to hide which of the two codes it knows and only prove that it knows at least one of them. For example, if the knowledge of a code corresponds to membership in a certain society, one may want to hide which society one belongs to. In cryptography, such a proof is called a witness-hiding proof of knowledge. How can P prove such a statement to V? This paper is concerned with witness-hiding proofs of knowledge using simple mechanical tools. Specifically, we consider cable (or bicycle) locks, where the codes of the locks correspond to the secret codes. The above example of proving knowledge of either ci or c2 in a witness-hiding fashion can be achieved simply as follows. When given the two locks closed and unlinked (by V), P presents the configuration of the two locks interlocked, which can be generated if and only if P knows at least one of the codes. In the most general case with n codes c1, ..., Cn, the access right is characterized by a so-called knowledge structure Γ ⊆ P({1, ..., n}), a subset of the power set of {1, ..., n}. Access is granted if a user knows the codes corresponding to any of the subsets of Γ. We present lock-based protocols for witness-hiding proofs of knowledge for any such monotone knowledge structure, and investigate the efficiency (i.e., in particular, the number of lock configurations that P must present) in several settings such as the availability of solid rings or the availability of multiple locks for a given code. The topic of this paper is similar in spirit to other works, such as the picture hanging puzzles by Demaine et al., which explore connections between topology and real-world applications, where the motivation arises also, or even primarily, from mathematical curiosity.