What a lovely hat

Many foundational results in the literature of consensus follow the Dolev-Yao model (FOCS '81), which treats digital signatures as ideal objects with perfect correctness and unforgeability. However, no work has yet formalized an ideal signature scheme that is both suitable for this methodology and possible to instantiate, or a composition theorem that ensures security when instantiating it cryptographically. The Universal Composition (UC) framework would ensure composition if we could...

Modern blockchain-based consensus protocols aim for efficiency (i.e., low communication and round complexity) while maintaining security against adaptive adversaries. These goals are usually achieved using a public randomness beacon to select roles for each participant. We examine to what extent this randomness is necessary. Specifically, we provide tight bounds on the amount of entropy a Byzantine Agreement protocol must consume from a beacon in order to enjoy efficiency and adaptive...

Asynchronous multiparty computation (AMPC) requires an input agreement phase where all participants have a consistent view of the set of private inputs. While the input agreement problem can be precisely addressed by a Byzantine fault-tolerant consensus known as Asynchronous Common Subset (ACS), existing ACS constructions with potential post-quantum security have a large $\widetilde{\mathcal{O}}(n^3)$ communication complexity for a network of $n$ nodes. This poses a bottleneck for AMPC in...

It is well known that a trusted setup allows one to solve the Byzantine agreement problem in the presence of $t<n/2$ corruptions, bypassing the setup-free $t<n/3$ barrier. Alas, the overwhelming majority of protocols in the literature have the caveat that their security crucially hinges on the security of the cryptography and setup, to the point where if the cryptography is broken, even a single corrupted party can violate the security of the protocol. Thus these protocols provide higher...

The parallel broadcast (PBC) problem generalises the classic Byzantine broadcast problem to the setting where all $n$ nodes broadcast a message and deliver $O(n)$ messages. PBC arises naturally in many settings including multi-party computation. Recently, Tsimos, Loss, and Papamanthou (CRYPTO 2022) showed PBC protocols with improved communication, against an adaptive adversary who can corrupt all but a constant fraction $\epsilon$ of nodes (i.e., $f < (1 - \epsilon)n$). However, their study...

Security of blockchain technologies primarily relies on decentralization making them resilient against a subset of entities being taken down or corrupt. Blockchain scaling, crucial to decentralisation, has been addressed by architectural changes: i.e., the load of the nodes is reduced by parallelisation, called sharding or by taking computation load off the main blockchain via rollups. Both sharding and rollups have limitations in terms of decentralization and security. A crucial component...

Byzantine broadcast is one of the fundamental problems in distributed computing. Many of its practical applications, from multiparty computation to consensus mechanisms for blockchains, require increasingly weaker trust assumptions, as well as scalability for an ever-growing number of users $n$. This rules out existing solutions which run in a linear number of rounds in $n$ or rely on trusted setup requirements. In this paper, we propose the first sublinear-round and trustless Byzantine...

We investigate the feasibility of permissionless consensus (aka Byzantine agreement) under standard assumptions. A number of protocols have been proposed to achieve permissionless consensus, most notably based on the Bitcoin protocol; however, to date no protocol is known that can be provably instantiated outside of the random oracle model. In this work, we take the first steps towards achieving permissionless consensus in the standard model. In particular, we demonstrate that worst-case...

Despite ensuring both consistency and liveness, state machine replication protocols remain vulnerable to adversaries who manipulate the transaction order. To address this, researchers have proposed order-fairness techniques that rely either on building dependency graphs between transactions, or on assigning sequence numbers to transactions. Existing protocols that handle dependency graphs suffer from sub-optimal performance, resilience, or security. On the other hand, Pompe (OSDI '20)...

Targeted Denial-of-Service (DoS) attacks have been a practical concern for permissionless blockchains. Potential solutions, such as random sampling, are adopted by blockchains. However, the associated security guarantees have only been informally discussed in prior work. This is due to the fact that existing adversary models are either not fully capturing this attack or giving up certain design choices (as in the sleepy model or asynchronous network model), or too strong to be...

Typical results in multi-party computation (in short, MPC) capture faulty parties by assuming a threshold adversary corrupting parties actively and/or fail-corrupting. These corruption types are, however, inadequate for capturing correct parties that might suffer temporary network failures and/or localized faults - these are particularly relevant for MPC over large, global scale networks. Omission faults and general adversary structures have been proposed as more suitable alternatives....

Over the past decade, cryptocurrencies have garnered attention from academia and industry alike, fostering a diverse blockchain ecosystem and novel applications. The inception of bridges improved interoperability, enabling asset transfers across different blockchains to capitalize on their unique features. Despite their surge in popularity and the emergence of Decentralized Finance (DeFi), trustless bridge protocols remain inefficient, either relaying too much information (e.g.,...

The classical distributed key generation protocols (DKG) are resurging due to their widespread applications in blockchain. While efforts have been made to improve DKG communication, practical large-scale deployments are still yet to come due to various challenges, including the heavy computation and communication (particularly broadcast) overhead in their adversarial cases. In this paper, we propose a practical DKG for DLog-based cryptosystems, which achieves (quasi-)linear computation and...

We consider the mainstream model in secure computation known as the bare PKI setup, also as the {bulletin-board PKI}. It allows players to broadcast once and non-interactively before they receive their inputs and start the execution. A bulletin-board PKI is essentially the minimum setup known so far to implement the model known as {messages-authentication}, i.e., when $P$ is forwarded a signed message, it considers it to be issued by $R$ if and only if $R$ signed it. It is known since...

Regular access to unpredictable and bias-resistant randomness is important for applications such as blockchains, voting, and secure distributed computing. Distributed random beacon protocols address this need by distributing trust across multiple nodes, with the majority of them assumed to be honest. Numerous applications across the blockchain space have led to the proposal of several distributed random beacon protocols, with some already implemented. However, many current random beacon...

It is well-known that Atomic Broadcast (AB) in asynchronous networks requires randomisation and that at most $t < n/3$ out of $n$ players are Byzantine corrupted. This is opposed to synchronous AB which can tolerate $t < n/2$ corruptions and can be deterministic. We show that these requirements can be conceptually separated by constructing an asynchronous AB protocol which tolerates $t < n/2$ corruptions from blackbox use of Common Coin and Reliable Broadcast (RB). We show the power of this...

Byzantine agreement (BA) asks for a set of parties to reach agreement in an adversarial setting. A central question is how to construct efficient BA protocols that scale well with the number of parties. In particular, the communication complexity is a critical barrier for large-scale implementations. State-of-the-art, scalable BA protocols typically work by sampling a small, unpredictable committee of parties that will send messages in each round. These messages must reach all honest...

We initiate the study of the network agnostic MPC protocols with statistical security. Network agnostic protocols give the best possible security guarantees irrespective of the underlying network type. We consider the general-adversary model, where the adversary is characterized by an adversary structure which enumerates all possible candidate subsets of corrupt parties. The $\mathcal{Q}^{(k)}$ condition enforces that the union of no $k$ subsets from the adversary structure covers the party...

Designing efficient distributed protocols for various agreement tasks such as Byzantine Agreement, Broadcast, and Committee Election is a fundamental problem. We are interested in $scalable$ protocols for these tasks, where each (honest) party communicates a number of bits which is sublinear in $n$, the number of parties. The first major step towards this goal is due to King et al. (SODA 2006) who showed a protocol where each party sends only $\tilde O(1)$ bits throughout $\tilde O(1)$...

Let $C$ be an error-correcting code over a large alphabet $q$ of block length $n$, and assume that, a possibly corrupted, codeword $c$ is distributively stored among $n$ servers where the $i$th entry is being held by the $i$th server. Suppose that every pair of servers publicly announce whether the corresponding coordinates are ``consistent'' with some legal codeword or ``conflicted''. What type of information about $c$ can be inferred from this consistency graph? Can we check whether errors...

In STOC 1989, Rabin and Ben-Or (RB) established an important milestone in the fields of cryptography and distributed computing by showing that every functionality can be computed with statistical (information-theoretic) security in the presence of an active (aka Byzantine) rushing adversary that controls up to half of the parties. We study the round complexity of general secure multiparty computation and several related tasks in the RB model. Our main result shows that every...

We present Bingo, an adaptively secure and optimally resilient packed asynchronous verifiable secret sharing (PAVSS) protocol that allows a dealer to share $f+1$ secrets with a total communication complexity of $O(\lambda n^2)$ words, where $\lambda$ is the security parameter and $n$ is the number of parties. Using Bingo, we obtain an adaptively secure validated asynchronous Byzantine agreement (VABA) protocol that uses $O(\lambda n^3)$ expected words and constant expected time, which we in...

Time-lock puzzles (TLP) are a fascinating type of cryptographic problem that is easy to generate, but takes a certain time to solve, even when arbitrary parallel speedup is allowed. TLPs have wide-ranging applications including fairness, round efficient computation, and more. To reduce the effort needed to solve large numbers of TLPs, prior work has proposed batching techniques to reduce the cost of solving. However, these proposals either require: (1) a trusted setup or (2) the puzzle size...

In this work, we study perfectly-secure multi-party computation (MPC) against general (non-threshold) adversaries. Known protocols in a synchronous network are secure against $Q^{(3)}$ adversary structures, while in an asynchronous network, known protocols are secure against $Q^{(4)}$ adversary structures. A natural question is whether there exists a single protocol which remains secure against $Q^{(3)}$ and $Q^{(4)}$ adversary structures in a synchronous and in an asynchronous network...

Central Bank Digital Currencies (CBDCs) aspire to offer a digital replacement for physical cash and as such need to tackle two fundamental requirements that are in conflict. On the one hand, it is desired they are private so that a financial “panopticon” is avoided, while on the other, they should be regulation friendly in the sense of facilitating any threshold-limiting, tracing, and counterparty auditing functionality that is necessary to comply with regulations such as Know Your Customer...

In this work, we present an almost-surely terminating asynchronous Byzantine agreement (ABA) protocol for $n$ parties. Our protocol requires ${\cal O}(n^2)$ expected time and is secure against a computationally-unbounded malicious (Byzantine) adversary, characterized by a non-threshold adversary structure ${\cal Z}$, which enumerates all possible subsets of potentially corrupt parties. Our protocol has optimal resilience where ${\cal Z}$ satisfies the ${\cal Q}^{(3)}$ condition; i.e. union...

Byzantine agreement (BA) is a fundamental primitive in distributed systems and has received huge interest as an important building block for blockchain systems. Classical byzantine agreement considers a setting where $n$ parties with fixed, known identities want to agree on an output in the presence of an adversary. Motivated by blockchain systems, the assumption of fixed identities is weakened by using a \emph{resource-based model}. In such models, parties do not have fixed known identities...

In 1985, Dolev and Reischuk proved a fundamental communication lower bounds on protocols achieving fault tolerant synchronous broadcast and consensus: any deterministic protocol solving those tasks (even against omission faults) requires at least a quadratic number of messages to be sent by nonfaulty parties. In contrast, many blockchain systems achieve consensus with seemingly linear communication per instance against Byzantine faults. We explore this dissonance in three main ways. First,...

We present a new abstraction based on crusader agreement called $\textit{Binding Crusader Agreement}$ (BCA) for solving binary consensus in the $\textit{asynchronous}$ setting against an $\textit{adaptive}$ adversary. BCA has the validity, agreement, and termination properties of crusader agreement in addition to a new property called $\textit{binding}$. Binding states that before the first non-faulty party terminates, there is a value $v \in \{0,1\}$ such that no non-faulty party can output...

In this paper, we design secure multi-party computation (MPC) protocols in the asynchronous communication setting with optimal resilience. Our protocols are secure against a computationally-unbounded malicious adversary, characterized by an adversary structure $\mathcal{Z}$, which enumerates all possible subsets of potentially corrupt parties. Our protocols incur a communication of $\mathcal{O}(|\mathcal{Z}|^2)$ and $\mathcal{O}(|\mathcal{Z}|)$ bits per multiplication for perfect and...

One of the most successful applications of peer-to-peer communication networks is in the context of blockchain protocols, which—in Satoshi Nakamoto's own words—rely on the "nature of information being easy to spread and hard to stifle." Significant efforts were invested in the last decade into analyzing the security of these protocols, and invariably the security arguments known for longest-chain Nakamoto-style consensus use an idealization of this tenet. Unfortunately, the real-world...

Byzantine agreement is a fundamental primitive in cryptography and distributed computing, and minimizing its round complexity is of paramount importance. It is long known that any randomized $r$-round protocol must fail with probability at least $(c\cdot r)^{-r}$, for some constant $c$, when the number of corruptions is linear in the number of parties, $t = \theta(n)$. On the other hand, current protocols fail with probability at least $2^{-r}$. Whether we can match the lower bound agreement...

We present Shanrang, the first fully asynchronous proactive secret sharing scheme with dynamic committee support. Even in the worst possible network environment, where messages could have arbitrary latencies, Shanrang allows a dynamic committee to store a secret and periodically refresh the secret shares in a distributed fashion. When the committee changes, both the old committee and the new committee jointly refresh and transfer the shares to the new committee, without revealing the secret...

Secure multi-party computation (MPC) is a fundamental problem in secure distributed computing. An MPC protocol allows a set of $n$ mutually distrusting parties to carry out any joint computation of their private inputs, without disclosing any additional information about their inputs. MPC with information-theoretic security (also called unconditional security) provides the strongest security guarantees and remains secure even against computationally unbounded adversaries. Perfectly-secure...

Asynchronous BFT consensus can implement robust mission-critical decentralized services in the unstable or even adversarial wide-area network without relying on any form of timing assumption. Starting from the work of HoneyBadgerBFT (CCS 2016), several studies tried to push asynchronous BFT towards practice. In particular, in a recent work of Dumbo (CCS 2020), they redesigned the protocol backbone and used one multi-valued validated Byzantine agreement (MVBA) to replace $n$ concurrent...

We introduce Themis, a scheme for introducing fair ordering of transactions into (permissioned) Byzantine consensus protocols with at most $f$ faulty nodes among $n \geq 4f +1$. Themis enforces the strongest notion of fair ordering proposed to date. It also achieves standard liveness, rather than the weaker notion of previous work with the same fair ordering property. We show experimentally that Themis can be integrated into state-of-the-art consensus protocols with minimal modification...

We investigate the communication complexity of Byzantine agreement protocols for long messages against an adaptive adversary. In this setting, prior results either achieved a communication complexity of $O(nl\cdot\poly(\kappa))$ or $O(nl + n^2 \cdot \poly(\kappa))$ for $l$-bit long messages. We improve the state of the art by presenting protocols with communication complexity $O(nl + n \cdot \poly(\kappa))$ in both the synchronous and asynchronous communication models. The synchronous...

The problem of Byzantine Fault Tolerance (BFT) has received a lot of attention in the last 30 years. The seminal work by Fisher, Lynch, and Paterson (FLP) shows that there does not exist a deterministic BFT protocol in complete asynchronous networks against a single failure. In order to address this challenge, researchers have designed randomized BFT protocols in asynchronous networks and deterministic BFT protocols in partial synchronous networks. For both kinds of protocols, a basic...

Consensus protocols enable $n$ parties, each holding some input string, to agree on a common output even in the presence of corrupted parties. While the problem is well understood in the classic byzantine setting, recent work has pushed to understand the problem when realistic types of failures are considered and a majority of parties may be corrupt. Garay and Perry consider a model with both byzantine and crash faults and develop a corruption-optimal protocol with perfect security...

Verifiable Secret-Sharing (VSS) is a fundamental primitive in secure distributed computing. It is used as an important building block in several distributed computing tasks, such as Byzantine agreement and secure multi-party computation. VSS has been widely studied in various dimensions over the last three decades and several important results have been achieved related to the fault-tolerance, round-complexity and communication efficiency of VSS schemes. In this article, we consider VSS...

Agreement protocols for partially synchronous or asynchronous networks tolerate fewer than one-third Byzantine faults. If parties are equipped with trusted hardware that prevents equivocation, then fault tolerance can be improved to fewer than one-half Byzantine faults, but typically at the cost of increased communication complexity. In this work, we present results that use small trusted hardware without worsening communication complexity assuming the adversary controls a fraction of the...

Random beacon protocols provide a continuous public source of randomness and their applications range from public lotteries to zero-knowledge proofs. Existing random beacon protocols in the bounded synchronous model sacrifice either the fault tolerance or the communication complexity for security, or ease of reconfigurability. This work overcomes the challenges with the existing works through a novel communication efficient combination of state machine replication and (publicly) verifiable...

Multi-signatures are used to attest that a fixed collection of $n$ parties, represented by their respective public keys, have all signed a given message. An emerging application of multi-signatures is to be found in consensus protocols to attest that a qualified subset of a global set of $n$ validators have reached agreement. In this paper, we point out that the traditional security model for multi-signatures is insufficient for this new application, as it assumes that every party in the...

Most state machine replication protocols are either based on the 40-years-old Byzantine Fault Tolerance (BFT) theory or the more recent Nakamoto’s longest chain design. Longest chain protocols, designed originally in the Proof-of-Work (PoW) setting, are available under dynamic participation, but has probabilistic confirmation with long latency dependent on the security parameter. BFT protocols, designed for the permissioned setting, has fast deterministic confirmation, but assume a fixed...

Byzantine Broadcast is an important topic in distributed systems and improving its round complexity has long been a focused challenge. Under honest majority, the state of the art for Byzantine Broadcast is 10 rounds for a static adversary and 16 rounds for an adaptive adversary. In this paper, we present a Byzantine Broadcast protocol with expected 8 rounds under a static adversary and expected 10 rounds under an adaptive adversary. We also generalize our idea to the dishonest majority...

The round complexity of Byzantine Broadcast (BB) has been a central question in distributed systems and cryptography. In the honest majority setting, expected constant round protocols have been known for decades even in the presence of a strongly adaptive adversary. In the corrupt majority setting, however, no protocol with sublinear round complexity is known, even when the adversary is allowed to {\it strongly adaptively} corrupt only 51\% of the players, and even under reasonable setup or...

Distributed ledgers, such as those arising from blockchain protocols, have been touted as the centerpiece of an upcoming security-critical information technology infrastructure. Their basic properties---consistency and liveness---can be guaranteed under specific constraints about the resources of an adversary relative to the resources of the nodes that follow the protocol. Given the intended long-livedness of these protocols, perhaps the most fundamental open security question currently is...

Generating randomness collectively has been a long standing problem in distributed computing. It plays a critical role not only in the design of state-of-the-art BFT and blockchain protocols, but also for a range of applications far beyond this field. We present RandRunner, a random beacon protocol with a unique set of guarantees that targets a realistic system model. Our design avoids the necessity of a (Byzantine fault-tolerant) consensus protocol and its accompanying high complexity and...

In this paper, we present an optimally-resilient, unconditionally-secure asynchronous multi-party computation (AMPC) protocol for $n$ parties, tolerating a computationally unbounded adversary, capable of corrupting up to $t < \frac{n}{3}$ parties. Our protocol needs a communication of ${\cal O}(n^4)$ field elements per multiplication gate. This is to be compared with previous best AMPC protocol (Patra et al, ICITS 2009) in the same setting, which needs a communication of ${\cal O}(n^5)$...

Byzantine Broadcast is crucial for many cryptographic protocols such as secret sharing, multiparty computation and blockchain consensus. In this paper we apply gossiping (propagating a message by sending to a few random parties who in turn do the same, until the message is delivered) and propose new communication-efficient protocols, under dishonest majority, for Single-Sender Broadcast (BC) and Parallel Broadcast (PBC), improving the state-of-the-art in several ways. As our warm-up result,...

Understanding the communication complexity of Byzantine agreement (BA) is a fundamental problem in distributed computing. In particular, as protocols are run with a large number of parties (as, e.g., in the context of blockchain protocols), it is important to understand the dependence of the communication on the number of parties $n$. Although adaptively secure BA protocols with $o(n^2)$ communication are known in the synchronous and partially synchronous settings, no such protocols are...

Byzantine Broadcast (BB) is a central question in distributed systems, and an important challenge is to understand its round complexity. Under the honest majority setting, it is long known that there exist randomized protocols that can achieve BB in expected constant rounds, regardless of the number of nodes $n$. However, whether we can match the expected constant round complexity in the corrupt majority setting --- or more precisely, when $f \geq n/2 + \omega(1)$ --- remains unknown, where...

In STOC 1988, Ben-Or, Goldwasser, and Wigderson (BGW) established an important milestone in the fields of cryptography and distributed computing by showing that every functionality can be computed with perfect (information-theoretic and error-free) security at the presence of an active (aka Byzantine) rushing adversary that controls up to $n/3$ of the parties. We study the round complexity of general secure multiparty computation in the BGW model. Our main result shows that every...

In their seminal work, Ben-Or and Linial (1985) introduced the full information model for collective coin-tossing protocols involving $n$ processors with unbounded computational power using a common broadcast channel for all their communications. The design and analysis of coin-tossing protocols in the full information model have close connections to diverse fields like extremal graph theory, randomness extraction, cryptographic protocol design, game theory, distributed protocols, and...

Blockchain Sharding is a blockchain performance enhancement approach. By splitting a blockchain into several parallel-run committees (shards), it helps increase transaction throughput, reduce resources required, and increase reward expectation for participants. Recently, several flexible sharding methods that can tolerate up to $n/2$ Byzantine nodes ($n/2$ security level) have been proposed. However, these methods suffer from two main drawbacks. First, in a non-sharding blockchain, nodes can...

Traditional Blockchain Sharding approaches can only tolerate up to n/3 of nodes being adversary because they rely on the hypergeometric distribution to make a failure (an adversary does not have n/3 of nodes globally but can manipulate the consensus of a Shard) hard to happen. The system must maintain a large Shard size (the number of nodes inside a Shard) to sustain the low failure probability so that only a small number of Shards may exist. In this paper, we present a new approach of...

Decades of research in both cryptography and distributed systems has extensively studied the problem of state machine replication, also known as Byzantine consensus. A consensus protocol must satisfy two properties: consistency and liveness. These properties ensure that honest participating nodes agree on the same log and dictate when fresh transactions get added. They fail, however, to ensure against adversarial manipulation of the actual ordering of transactions in the log. Indeed, in...

We present a novel framework for asynchronous permissioned blockchain with high performance and post-quantum security for the first time. Specifically, our framework contains two asynchronous Byzantine fault tolerance (aBFT) protocols SodsBC and SodsBC++. We leverage concurrently preprocessing to accelerate the preparation of three cryptographic objects for the repeated consensus procedure, including common random coins as the needed randomness, secret shares of symmetric encryption keys for...

Traditional bounds on synchronous Byzantine agreement (BA) and secure multi-party computation (MPC) establish that in absence of a private correlated-randomness setup, such as a PKI, protocols can tolerate up to $t<n/3$ of the parties being malicious. The introduction of ``Nakamoto style'' consensus, based on Proof-of-Work (PoW) blockchains, put forth a somewhat different flavor of BA, showing that even a majority of corrupted parties can be tolerated as long as the majority of the ...

Blockchain brings dawn to decentralized applications which coordinate correct computations without a prior trust. However, existing scalable on-chain frameworks are incompetent in dealing with intensive validation. On the one hand, duplicated execution pattern leads to limited throughput and unacceptable expenses. On the other hand, there lack fair and secure incentive mechanisms allocating rewards according to the actual workload of validators, thus deriving bad dilemmas among rational...

The importance of efficient MPC in today's world needs no retelling. An obvious barebones requirement to execute protocols for MPC is the ability of parties to communicate with each other. Traditionally, we solve this problem by assuming that every pair of parties in the network share a dedicated secure link that enables reliable message transmission. This assumption is clearly impractical as the number of nodes in the network grows, as it has today. In their seminal work, Dwork, Peleg,...

We explore a Byzantine Consensus protocol called Dfinity Consensus, recently published in a technical report. Dfinity Consensus solves synchronous state machine replication among $n = 2f + 1$ replicas with up to $f$ Byzantine faults. We provide a succinct explanation of the core mechanism of Dfinity Consensus to the best of our understanding. We prove the safety and liveness of the protocol specification we provide. Our complexity analysis of the protocol reveals the follows. The protocol...

Most classical consensus protocols rely on a leader to coordinate nodes’ voting efforts. One novel idea that stems from blockchain-style consensus is to rely, instead, on a “longest-chain” idea for such coordination. Such a longest-chain idea was initially considered in randomized protocols, where in each round, a node has some probability of being elected a leader who can propose the next block. Recently, well-known systems have started implementing the deterministic counterpart of such...

We present a simple, deterministic protocol for ledger consensus that tolerates Byzantine faults. The protocol is executed by $n$ servers over a synchronous network and can tolerate any number $t$ of Byzantine faults with $t<n/3$. Furthermore, the protocol can offer (i) transaction processing at full network speed, in the optimistic case where no faults occur, (ii) instant confirmation: the client can be assured in a single round-trip time that a submitted transaction will be settled,...

We present new protocols for Byzantine agreement in the synchronous and authenticated setting, tolerating the optimal number of $f$ faults among $n=2f+1$ parties. Our protocols achieve an expected $O(1)$ round complexity and an expected $O(n^2)$ communication complexity. The exact round complexity in expectation is 10 for a static adversary and 16 for a strongly rushing adaptive adversary. For comparison, previous protocols in the same setting require expected 29 rounds.

Secure message transmission and Byzantine agreement have been studied extensively in incomplete networks. However, information theoretically secure multiparty computation (MPC) in incomplete networks is less well understood. In this paper, we characterize the conditions under which a pair of parties can compute oblivious transfer (OT) information theoretically securely against a general adversary structure in an incomplete network of reliable, private channels. We provide characterizations...

Byzantine broadcast is a fundamental primitive for secure computation. In a setting with $n$ parties in the presence of an adversary controlling at most $t$ parties, while a lot of progress in optimizing communication complexity has been made for $t < n/2$, little progress has been made for the general case $t<n$, especially for information-theoretic security. In particular, all information-theoretic secure broadcast protocols for $\ell$-bit messages and $t<n$ and optimal round complexity...

In state-of-the-art e-voting systems, a bulletin board (BB) is a critical component for preserving election integrity and availability. Although it is common in the literature to assume that a BB is a centralized entity that is trusted, in the recent works of Culnane and Schneider [CSF 2014] and Chondros et al. [ICDCS 2016], the importance of removing BB as a single point of failure has been extensively discussed. Motivated by these works, we introduce a framework for the formal security...

The problem of Byzantine Agreement (BA) is of interest to both distributed computing and cryptography community. Following well-known results from the distributed computing literature, BA problem in the asynchronous network setting encounters inevitable non-termination issues. The impasse is overcome via randomization that allows construction of BA protocols in two flavours of termination guarantee -- with overwhelming probability and with probability one. The latter type termed as...

A reliable source of randomness is not only an essential building block in various cryptographic, security, and distributed systems protocols, but also plays an integral part in the design of many new blockchain proposals. Consequently, the topic of publicly-verifiable, bias-resistant and unpredictable randomness has recently enjoyed increased attention. In particular random beacon protocols, aimed at continuous operation, can be a vital component for current Proof-of-Stake based distributed...

In the problem of byzantine agreement (BA), a set of n parties wishes to agree on a value v by jointly running a distributed protocol. The protocol is deemed secure if it achieves this goal in spite of a malicious adversary that corrupts a certain fraction of the parties and can make them behave in arbitrarily malicious ways. Since its first formalization by Lamport et al. (TOPLAS `82), the problem of BA has been extensively studied in the literature under many different assumptions. One...

The decentralized cryptocurrency Bitcoin has experienced great success but also encountered many challenges. One of the challenges has been the long confirmation time. Another challenge is the lack of incentives at certain steps of the protocol, raising concerns for transaction withholding, selfish mining, etc. To address these challenges, we propose Solida, a decentralized blockchain protocol based on reconfigurable Byzantine consensus augmented by proof-of-work. Solida improves on Bitcoin...

Inspired by the astonishing success of cryptocurrencies, most notably the Bitcoin system, several recent works have focused on the design of robust blockchain-style protocols that work in a peer-to-peer setting such as the Internet. In contrast to the setting traditionally considered in multiparty computation (MPC), in these systems, honesty is measured by computing power instead of requiring that only a certain fraction of parties is controlled by the adversary. This provides a potential...

In this paper, we study the round complexity of concurrently secure multi-party computation (MPC) with super-polynomial simulation (SPS) in the plain model. In the plain model, there are known explicit attacks that show that concurrently secure MPC with polynomial simulation is impossible to achieve; SPS security is the most widely studied model for concurrently secure MPC in the plain model. We obtain the following results: – Three-round concurrent MPC with SPS security against Byzantine...

Peer-to-peer (P2P) systems such as BitTorrent and Bitcoin are susceptible to serious attacks from byzantine nodes that join as peers. Research has explored many adversarial models with additional assumptions, ranging from mild (such as pre-established PKI) to strong (such as the existence of common random coins). One such widely-studied model is the general-omission model, which yields simple protocols with good efficiency, but has been considered impractical or unrealizable since it...

The problems of Byzantine Broadcast (BB) and Byzantine Agreement (BA) are of interest to both distributed computing and cryptography community. Extension protocols for these primitives have been introduced to handle long messages efficiently at the cost of small number of single-bit broadcasts, referred to as seed broadcasts. While the communication optimality has remained the most sought-after property of an extension protocol in the literature, we prioritize both communication and...

Bias-resistant public randomness is a critical component in many (distributed) protocols. Existing solutions do not scale to hundreds or thousands of participants, as is needed in many decentralized systems. We propose two large-scale distributed protocols, RandHound and RandHerd, which provide publicly-verifiable, unpredictable, and unbiasable randomness against Byzantine adversaries. RandHound relies on an untrusted client to divide a set of randomness servers into groups for scalability,...

In the setting of secure multiparty computation, a set of mutually distrusting parties wish to securely compute a joint function. It is well known that if the communication model is asynchronous, meaning that messages can be arbitrarily delayed by an unbounded (yet finite) amount of time, secure computation is feasible if and only if at least two-thirds of the parties are honest, as was shown by Ben-Or, Canetti, and Goldreich [STOC'93] and by Ben-Or, Kelmer, and Rabin [PODC'94]. The...

Byzantine broadcast is a distributed primitive that allows a specific party to consistently distribute a message among $n$ parties in the presence of potential misbehavior of up to $t$ of the parties. The celebrated result of \cite{PSL80} shows that broadcast is achievable from point-to-point channels if and only if $t < n/3$. The following two generalizations have been proposed to the original broadcast problem. In~\cite{FM98} the authors considered a \emph{general adversary} characterized...

A fundamental communication primitive in distributed computing is Reliable Message Transmission (RMT), which refers to the task of correctly sending a message from a party to another, despite the presence of Byzantine corruptions. In this work we address the problem in the general adversary model of Hirt and Maurer [5], which subsumes earlier models such as the global or local threshold adversaries. Regarding the topology knowledge, we employ the recently introduced Partial Knowledge Model...

Bitcoin is the first and most popular decentralized cryptocurrency to date. In this work, we extract and analyze the core of the Bitcoin protocol, which we term the Bitcoin backbone, and prove two of its fundamental properties which we call common prefix and chain quality in the static setting where the number of players remains fixed. Our proofs hinge on appropriate and novel assumptions on the hashing power of the adversary relative to network synchronicity; we show our results to be tight...

We study the Reliable Broadcast problem in incomplete networks against a Byzantine adversary. We examine the problem under the locally bounded adversary model of Koo (2004) and the general adversary model of Hirt and Maurer (1997) and explore the tradeoff between the level of topology knowledge and the solvability of the problem. We refine the local pair-cut technique of Pelc and Peleg (2005) in order to obtain impossibility results for every level of topology knowledge and any type of...

We consider the Secure Broadcast problem in incomplete networks. We study the resilience of the Certified Propagation Algorithm (CPA), which is particularly suitable for ad hoc networks. We address the issue of determining the maximum number of corrupted players $t^{\mathrm{CPA}}_{\max}$ that CPA can tolerate under the $t$-locally bounded adversary model, in which the adversary may corrupt at most $t$ players in each player's neighborhood. For any graph $G$ and dealer-node $D$ we provide...

Verifiable secret sharing (VSS) is a vital primitive in secure distributed computing. It allows an untrusted dealer to verifiably share a secret among n parties in the presence of an adversary controlling at most t of them. VSS in the synchronous communication model has received tremendous attention in the cryptographic research community. Nevertheless, recent interest in deploying secure distributed computing over the Internet requires going beyond the synchronous communication model and...

Distributed key generation (DKG) has been studied extensively in the cryptographic literature. However, it has never been examined outside of the synchronous setting, and the known DKG protocols cannot guarantee safety or liveness over the Internet. In this work, we present the first realistic DKG protocol for use over the Internet. We propose a practical system model for the Internet and define an efficient verifiable secret sharing (VSS) scheme in it. We observe the necessity of Byzantine...

In this paper we give the minimal connectivity required in a synchronous directed network, which is under the influence of a computationally unbounded \emph{Byzantine} adversary that can corrupt a subset of nodes, so that Secure Message Transmission is possible between sender $S$ and receiver $R$. We also show that secure communication between a pair of nodes in a given synchronous directed network is possible in both directions if and only if reliable communication is possible between...

We present an efficient and optimally resilient Asynchronous Byzantine Agreement (ABA) protocol involving n = 3t+1 parties over a completely asynchronous network, tolerating a computationally unbounded Byzantine adversary, who can control at most t parties out of the n parties. The amortized communication complexity of our ABA protocol is O(n^{3} \log \frac{1}{\epsilon}) bits for attaining agreement on a single bit, where \epsilon (\epsilon > 0) denotes the probability of non-termination. ...

The problem of unconditionally reliable message transmission (URMT) is to design a protocol which when run by players in a network enables a sender S to deliver a message to a receiver R with high probability, even when some players in the network are under the control of an unbounded adversary. Renault and Tomala [JoC2008] gave a characterization of undirected neighbour networks over which URMT tolerating Byzantine adversary is possible. In this paper, we generalize their result to the case...

We study the problem of information-theoretically secure message transmission (SMT) in asynchronous directed networks. In line with the literature, the distrust and failures of the network is captured via a computationally unbounded Byzantine adversary that may corrupt some subset of nodes. We give a characterization of networks over which SMT from sender S to receiver R is possible in both the well-known settings, namely perfect SMT (PSMT) and unconditional SMT (USMT). We distinguish...

The round complexity of verifiable secret sharing (VSS) schemes has been studied extensively for threshold adversaries. In particular, Fitzi et al. showed an efficient 3-round VSS for $n \geq 3t+1$ \cite{FitziVSSTCC06}, where an infinitely powerful adversary can corrupt t (or less) parties out of $n$ parties. This paper shows that for non-threshold adversaries, -Two round VSS is possible iff the underlying adversary structure satisfies ${\cal Q}^4$ condition; -Three round VSS is possible...

For unconditionally reliable message transmission (URMT) in synchronous directed networks of n nodes, a subset of which may be Byzantine faulty, it is well-known that the minimum connectivity requirements for zero-error (perfect) protocols to exist is strictly higher than those where a negligible yet non-zero error probability is allowed (Monte Carlo protocols). In this work, we study the minimum connectivity requirements for the existence of (a) synchronous Las Vegas protocols, (b)...

Consider the following problem: a sender S and a receiver R are part of an unreliable, connected, distributed network. The distrust in the network is modelled by an entity called adversary, who has unbounded computing power and who can corrupt some of the nodes of the network (excluding S and R)in a variety of ways. S wishes to send to R a message m that consists of \ell elements, where \ell \geq 1, selected uniformly from a finite field F. The challenge is to design a protocol, such that...

This dissertation deals with three most important as well as fundamental problems in secure distributed computing, namely Verifiable Secret Sharing (VSS), Byzantine Agreement (BA) and Multiparty Computation (MPC). VSS is a two phase protocol (Sharing and Reconstruction) carried out among $n$ parties in the presence of a centralized adversary who can corrupt up to $t$ parties. Informally, the goal of the VSS protocol is to share a secret $s$, among the $n$ parties during the sharing phase in...

Verifiable Secret Sharing (VSS) is a fundamental primitive used as a building block in many distributed cryptographic tasks, such as Secure Multiparty Computation (MPC) and Byzantine Agreement (BA). An important variant of VSS is Asynchronous VSS (AVSS) which is designed to work over asynchronous networks. AVSS is a two phase (Sharing, Reconstruction) protocol carried out among n parties in the presence of a computationally unbounded active adversary, who can corrupt up to t parties. We...

In this paper, we re-visit the problem of perfectly secure message transmission (PSMT) in a directed network under the presence of a threshold adaptive Byzantine adversary, having unbounded computing power. Desmedt et.al have given the characterization for three or more phase PSMT protocols over directed networks. Recently, Patra et. al. have given the characterization of two phase PSMT over directed networks. Even though the issue of tradeoff between phase complexity and communication...

In this paper, we present new and general constructions of lossy encryption schemes. By applying results from Eurocrypt '09, we obtain new general constructions of cryptosystems secure against a Selective Opening Adversaries (SOA). Although it was recognized almost twenty years ago that SOA security was important, it was not until the recent breakthrough works of Hofheinz and Bellare, Hofheinz and Yilek that any progress was made on this fundamental problem. The Selective Opening problem is...

Secure multiparty computation (MPC) allows a set of $n$ parties to securely compute an agreed function, even if up to $t$ parties are under the control of an adversary. In this paper, we propose a new {\it Asynchronous secure multiparty computation} (AMPC) protocol that provides information theoretic security with $n = 4t+1$, where $t$ out of $n$ parties can be under the influence of a {\it Byzantine (active)} adversary ${\cal A}_t$ having {\it unbounded computing power}. Our protocol...

In this paper, we re-visit the problem of {\it perfectly reliable message transmission} (PRMT) and {\it perfectly secure message transmission}(PSMT) in a {\it directed network} under the presence of a threshold adaptive Byzantine adversary, having {\it unbounded computing power}. Desmedt et.al have given the necessary and sufficient condition for the existence of PSMT protocols in directed networks. In this paper, we first show that the necessary and sufficient condition (characterization)...

Verifiable Secret Sharing (VSS) is a fundamental primitive used as a building block in many distributed cryptographic tasks, such as Secure Multiparty Computation (MPC) and Byzantine Agreement (BA). An important variant of VSS is Asynchronous VSS (AVSS) which is designed to work over asynchronous networks. AVSS is a two phase (Sharing, Reconstruction) protocol carried out among $n$ parties in the presence of a computationally unbounded active adversary, who can corrupt up to $t$ parties. ...

We present an efficient, optimally-resilient Asynchronous Byzantine Agreement (ABA) protocol involving n = 3t+1 parties over a completely asynchronous network, tolerating a computationally unbounded Byzantine adversary, capable of corrupting at most t out of the n parties. In comparison with the best known optimally-resilient ABA protocols of Canetti and Rabin (STOC 1993) and Abraham, Dolev and Halpern (PODC 2008), our protocol is significantly more efficient in terms of the communication...