Secure Multi-Party Computation (MPC) enables secure computation on private data. Many of today’s efficient MPC protocols need a representation of the evaluated function as circuit composed of Boolean or Lookup Tables (LUTs). To improve the practicality of MPC, we present SynCirc, a hardware synthesis framework optimized for MPC applications. Built on Verilog and the open-source tool Yosys-ABC, SynCirc introduces custom libraries and constraints for multi-input AND gates, achieving up to 3× reduction in multiplicative depth and online rounds compared to TinyGMW (Demmler et al., CCS’15).SynCirc also offers an expanded library of efficient building blocks like comparison, multiplexers and equality checks, and incorporates Boolean and LUT circuits. For these building blocks, we achieve improvements in multiplicative depth/online rounds between 22.3% and 66.7% over ShallowCC (Büscher et al., ESORICS’16). Our evaluation using the FLUTE framework (Brüggemann et al., IEEE S&P’23) shows that SynCirc has 116× less online communication than the multi-input AND gate protocol of Trifecta (Faraji and Kerschbaum, PETS’23).SynCirc introduces new capabilities, including enhanced support for High-Level Synthesis (HLS) with the XLS tool, enabling developers to create secure functions in C/C++ without the need for expertise in hardware definition languages like Verilog. SynCirc is an open-source toolchain that democratizes secure computation, simplifies circuit synthesis, and makes advanced privacy-preserving technologies more accessible.

We study network-agnostic secure multiparty computation with perfect security. Traditionally MPC is studied assuming the underlying network is either synchronous or asynchronous. In a network-agnostic setting, the parties are unaware of whether the underlying network is synchronous or asynchronous.

Pattern matching (PM) is the technique of identifying occurrences of a short pattern in a long text, where both, the pattern and text, are a string of characters. Since several applications demand the privacy of the pattern and the text in the process of identifying matches, designing secure solutions for PM is gaining popularity. Moreover, given the variety of applications that consider PM, we design secure solutions for three popular variants of PM---exact, wildcard and approximate. Our solutions are designed using the techniques of secure multiparty computation (MPC) in the two-party semi-honest setting. All of our solutions attain a fast response time, which is the time taken from submission of the input to obtaining the output, and forms a crucial parameter when analysing the performance of any protocol. Moreover, our protocols also provide an improved online communication complexity in comparison to prior works. Since determining if two secret-shared values are equal forms a crucial component in all the PM variants, we design a novel constant-round equality protocol in the two-party semi-honest setting. Our equality protocol outperforms all the prior works in the considered setting and can also be of independent interest. We implement all our protocols on the MPC framework of MOTION2NX to showcase the practicality of the designed solutions. In comparison to prior works that consider DNA matching (over 2-bit characters), our pattern matching protocols see improvements of up to 2 orders of magnitude in response time. Our equality protocol, too, excels over all existing constructions. To analyse the performance of our equality protocol in comparison to prior work, we benchmark it for varying input sizes. We observe that with increasing input sizes, the improvement in response time of our protocol keeps on increasing, with improvements of up to 9.7x for 256-bit inputs.

Privacy-preserving graph analysis allows performing computations on graphs that store sensitive information while ensuring all the information about the topology of the graph, as well as data associated with the nodes and edges, remains hidden. The current work addresses this problem by designing a highly scalable framework, Graphiti, that allows securely realising any graph algorithm. Graphiti relies on the technique of secure multiparty computation (MPC) to design a generic framework that improves over the state-of-the-art framework of GraphSC by Araki et al. (CCS'21). The key technical contribution is that Graphiti has round complexity independent of the graph size, which in turn allows attaining the desired scalability. Specifically, this is achieved by (i) decoupling the Scatter primitive of GraphSC into separate operations of Propagate and ApplyE, (ii) designing a novel constant-round approach to realise Propagate, as well as (iii) designing a novel constant-round approach to realise the Gather primitive of GraphSC by leveraging the linearity of the aggregation operation. We benchmark the performance of Graphiti for the application of contact tracing via BFS for 10 hops and observe that it takes less than 2 minutes when computing over a graph of size 10^7. Concretely it improves over the state-of-the-art up to a factor of 1034× in online run time. Similar to GraphSC by Araki et al., since Graphiti relies on a secure protocol for shuffle, we additionally design a shuffle protocol secure against a semi-honest adversary in the 2-party with a helper setting. Given the versatility of shuffle protocol, the designed solution is of independent interest. Hence, we also benchmark the performance of the designed shuffle where we observe improvements of up to 1.83× in online run time when considering an input vector of size 10^7, in comparison to the state-of-the-art in the considered setting.

Secure multiparty computation (MPC) enables privacy-preserving collaborative computation over sensitive data held by multiple mutually distrusting parties. Unfortunately, in the most natural setting where a majority of the parties are maliciously corrupt (also called the dishonest majority setting), traditional MPC protocols incur high overheads and offer weaker security guarantees than are desirable for practical applications. In this paper, we explore the possibility of circumventing these drawbacks and achieving practically efficient dishonest majority MPC protocols with strong security guarantees by assuming an additional semi-honest, non-colluding helper party HP .1We believe that this is a more realistic alternative to assuming an honest majority, since many real-world applications of MPC involving potentially large numbers of parties (such as dark pools) are typically enabled by a central governing entity that can be modeled as the HP.In the above model, we are the first to design, implement and benchmark a practically-efficient and general multi-party framework, Asterisk. Our framework requires invoking HP only a constant number of times, achieves the strong security guarantee of fairness (either all parties learn the output or none do), scales to hundreds of parties, outperforms all existing dishonest majority MPC protocols, and is, in fact, competitive with state-of-the-art honest majority MPC protocols. Our experiments show that Asterisk achieves 228 – 288× speedup in preprocessing as compared to the best dishonest majority MPC protocol. With respect to online time, Asterisk supports 100-party evaluation of a circuit with 106multiplication gates in approximately 20 seconds. We also implement and benchmark practically efficient and highly scalable dark pool instances using Asterisk. The corresponding run times showcase the effectiveness of Asterisk in enabling efficient realizations of real-world privacy-preserving applications with strong security guarantees.

E-commerce companies are actively considering the use of delivery drones for customer fulfillment, leading to growing concerns around citizen privacy. Drones are equipped with cameras, and the video feed from these cameras is often required as part of routine navigation, be it for semi-autonomous or fully-autonomous drones. Footage of ground-based citizens captured in these videos may lead to privacy concerns. This paper presents Privadome, a system that implements the vision of a virtual privacy dome centered around the citizen. Privadome is designed to be integrated with city-scale regulatory authorities that oversee delivery drone operations and realizes this vision through two components, PD-MPC and PD-ROS. PD-MPC allows citizens equipped with a mobile device to identify drones that have captured their footage. It uses secure two-party computation to achieve this goal without compromising the privacy of the citizen’s location. PD-ROS allows the citizen to communicate with such drones and obtain an audit trail showing how the drone uses their footage and determine if privacy-preserving steps are taken to sanitize the footage.

Consider the problem of securely identifying$\tau$-heavy hitters, where given a set of client inputs, the goal is to identify those inputs which are held by at least$\tau$clients in a privacy-preserving manner. Towards this, we design a novel system$\mathsf {Vogue}$, whose key highlight in comparison to prior works, is that it ensures complete privacy and does not leak any information other than the heavy hitters. In doing so,$\mathsf {Vogue}$aims to achieve as efficient a solution as possible. To showcase these efficiency improvements, we benchmark our solution and observe that it requires around 14 minutes to compute the heavy hitters for$\tau$= 100 on 256-bit inputs when considering 400 K clients. This is in contrast to the state of the art solution that requires over an hour for the same. In addition to the static input setting described above,$\mathsf {Vogue}$also accounts for streaming inputs and provides a protocol that outperforms the state-of-the-art therein. The efficiency improvements witnessed while computing heavy hitters in both, the static and streaming input settings, are attributed to our new secure stable compaction protocol, whose round complexity is independent of the size of the input array to be compacted.

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.

The rising issues of harassment, exploitation, corruption and other forms of abuse have led victims to seek comfort by acting in unison against common perpetrators. This is corroborated by the widespread #MeToo movement, which was explicitly against sexual harassment. Installation of escrow systems has allowed victims to report such incidents. The escrows are responsible for identifying the perpetrator and taking the necessary action to bring justice to all its victims. However, users hesitate to participate in these systems due to the fear of such sensitive reports being leaked to perpetrators, who may further misuse them. Thus, to increase trust in the system, cryptographic solutions are being designed to realize web-based secure allegation escrow (SAE) systems.

Abstract The growing volumes of data being collected and its analysis to provide better services are creating worries about digital privacy. To address privacy concerns and give practical solutions, the literature has relied on secure multiparty computation techniques. However, recent research over rings has mostly focused on the small-party honest-majority setting of up to four parties tolerating single corruption, noting efficiency concerns. In this work, we extend the strategies to support higher resiliency in an honest-majority setting with efficiency of the online phase at the centre stage. Our semi-honest protocol improves the online communication of the protocol of Damgård and Nielsen (CRYPTO’07) without inflating the overall communication. It also allows shutting down almost half of the parties in the online phase, thereby saving up to 50% in the system’s operational costs. Our maliciously secure protocol also enjoys similar benefits and requires only half of the parties, except for one-time verification towards the end, and provides security with fairness. To showcase the practicality of the designed protocols, we benchmark popular applications such as deep neural networks, graph neural networks, genome sequence matching, and biometric matching using prototype implementations. Our protocols, in addition to improved communication, aid in bringing up to 60–80% savings in monetary cost over prior work.

Identifying a cluster around a seed node in a graph, termed local clustering, finds use in several applications, including fraud detection, targeted advertising, community detection, etc. However, performing local clustering is challenging when the graph is distributed among multiple data owners, which is further aggravated by the privacy concerns that arise in disclosing their view of the graph. This necessitates designing solutions for privacy-preserving local clustering and is addressed for the first time in the literature. We propose using the technique of secure multiparty computation (MPC) to achieve the same. Our local clustering algorithm is based on the heat kernel PageRank (HKPR) metric, which produces the best-known cluster quality. En route to our final solution, we have two important steps: (i) designing data-oblivious equivalent of the state-of-the-art algorithms for computing local clustering and HKPR values, and (ii) compiling the data-oblivious algorithms into its secure realisation via an MPC framework that supports operations over fixed-point arithmetic representation such as multiplication and division. Keeping efficiency in mind for large graphs, we choose the best-known honest-majority 3-party framework of SWIFT (Koti et al., USENIX'21) and enhance it with some of the necessary yet missing primitives, before using it for our purpose. We benchmark the performance of our secure protocols, and the reported run time showcases the practicality of the same. Further, we perform extensive experiments to evaluate the accuracy loss of our protocols. Compared to their cleartext counterparts, we observe that the results are comparable and thus showcase the practicality of the designed protocols.

Secure shuffle is an important primitive that finds use in several applications such as secure electronic voting, oblivious RAMs, secure sorting, to name a few. For time-sensitive shuffle-based applications that demand a fast response time, it is essential to design a fast and efficient shuffle protocol. In this work, we design secure and fast shuffle protocols relying on the techniques of secure multiparty computation. We make several design choices that aid in achieving highly efficient protocols. Specifically, we consider malicious 3-party computation setting with an honest majority and design robust ring-based protocols. Our shuffle protocols provide a fast online (i.e., input-dependent) phase compared to the state-of-the-art for the considered setting. To showcase the efficiency improvements brought in by our shuffle protocols, we consider two distinct applications of anonymous broadcast and secure graph computation via the GraphSC paradigm. In both cases, multiple shuffle invocations are required. Hence, going beyond standalone shuffle invocation, we identify two distinct scenarios of multiple invocations and provide customised protocols for the same. Further, we showcase that our customized protocols not only provide a fast response time, but also provide improved overall run time for multiple shuffle invocations. With respect to the applications, we not only improve in terms of efficiency, but also work towards providing improved security guarantees, thereby outperforming the respective state-of-the-art works. We benchmark our shuffle protocols and the considered applications to analyze the efficiency improvements with respect to various parameters.

Consider a set of N clients, each of which holds a private input string. An input string that is held by at least τ clients is defined as a τ-heavy hitter. In various application scenarios, data-aggregation servers are interested in learning τ-heavy hitters. To ensure that the servers do not learn anything about client input in the process, the problem of identifying heavy hitters privately is gaining popularity. Towards this, we design a novel system called Vogue, which provides improved efficiency as well as security guarantees over the state-of-the-art system of Poplar. Concretely, Vogue provides up to 27x efficiency improvement over Poplar when considering 400,000 clients who hold 256-bit input strings. Moreover, Vogue overcomes intermediate information leakages present in Poplar and guarantees full security in the presence of a malicious adversary. In the process of designing Vogue, we also design secure and efficient protocols for stable compaction and shuffle, each of which improves over its respective state-of-the-art.

Secure multiparty computation (MPC) is increasingly being used to address privacy issues in various applications. The recent work of Alon et al. (CRYPTO'20) identified the shortcomings of traditional MPC and defined a Friends-and-Foes (FaF) security notion to address the same. We showcase the need for FaF security in real-world applications such as dark pools. This subsequently necessitates designing concretely efficient FaF-secure protocols. Towards this, keeping efficiency at the center stage, we design ring-based FaF-secure MPC protocols in the small-party honest-majority setting. Specifically, we provide (1,1)-FaF secure 5 party computation protocols (5PC) that consider one malicious and one semi-honest corruption and constitutes the optimal setting for attaining honest-majority. At the heart of it lies the multiplication protocol that requires a single round of communication with 8 ring elements (amortized). To facilitate having FaF-secure variants for several applications, we design a variety of building blocks optimized for our FaF setting. The practicality of the designed (1,1)-FaF secure 5PC framework is showcased by benchmarking dark pools. In the process, we also improve the efficiency and security of the dark pool protocols over the existing traditionally secure ones. This improvement is witnessed as a gain of up to 62x in throughput compared to the existing ones. Finally, to demonstrate the versatility of our framework, we also benchmark popular deep neural networks.

The growing volumes of data collected and its analysis to provide better services create worries about digital privacy. The literature has relied on secure multiparty computation techniques to address privacy concerns and give practical solutions. However, recent research has mostly focused on the small-party honest-majority setting of up to four parties, noting efficiency concerns. In this work, we extend the strategies to support a larger number of participants in honest-majority setting with efficiency at the center stage.

Abstract Traditional zero-knowledge protocols have been studied and optimized for the setting where a single prover holds the complete witness and tries to convince a verifier about a predicate on the witness, without revealing any additional information to the verifier. In this work, we study the notion of distributed-prover zero knowledge (DPZK) for arbitrary predicates where the witness is shared among multiple mutually distrusting provers and they want to convince a verifier that their shares together satisfy the predicate. We make the following contributions to the notion of distributed proof generation: (i) we propose a new MPC-style security definition to capture the adversarial settings possible for different collusion models between the provers and the verifier, (ii) we discuss new efficiency parameters for distributed proof generation such as the number of rounds of interaction and the amount of communication among the provers, and (iii) we propose a compiler that realizes distributed proof generation from the zero-knowledge protocols in the Interactive Oracle Proofs (IOP) paradigm. Our compiler can be used to obtain DPZK from arbitrary IOP protocols, but the concrete efficiency overheads are substantial in general. To this end, we contribute (iv) a new zero-knowledge IOP Graphene which can be compiled into an efficient DPZK protocol. The (D + 1)-DPZK protocol D-Graphene, with D provers and one verifier, admitsO(N1/c) proof size with a communication complexity ofO(D2·(N1−2/c+Ns)), whereNis the number of gates in the arithmetic circuit representing the predicate andNsis the number of wires that depends on inputs from two or more parties. Significantly, only the distributed proof generation in D-Graphene requires interaction among the provers. D-Graphene compares favourably with the DPZK protocols obtained from the state-of-art zero-knowledge protocols, even those not modelled as IOPs.

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 functionality can be realized in only four rounds of interaction, and that some functionalities cannot be computed in three rounds. This completely settles the round-complexity of perfect actively-secure optimally-resilient MPC, resolving a long line of research. Our lower-bound is based on a novel round-reduction technique that allows us to lift existing three-round lower-bounds for verifiable secret sharing to four-round lower-bounds for general MPC. To prove the upper-bound, we develop new round-efficient protocols for computing degree-2 functionalities over large fields, and establish the completeness of such functionalities. The latter result extends the recent completeness theorem of Applebaum, Brakerski and Tsabary (TCC 2018, Eurocrypt 2019) that was limited to the binary field.

The problem of Byzantine Agreement (BA) is of interest to both the distributed computing and cryptography communities. Following well-known results from distributed computing literature, the 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 flavors of termination guarantee—with overwhelming probability and with probability one. The latter type, termed as almost-surely terminating BA, is the main focus of this article. An eluding problem in the domain of almost-surely terminating BA is achieving a constant expected running time. Our primary contribution in this work makes significant progress in this direction. In a setting with n parties and an adversary with unbounded computing power controlling at most t parties in a Byzantine fashion, we present two almost-surely terminating BA protocols in the asynchronous setting: ○ With the optimal resilience of t < n /3, our first protocol runs for an expected O ( n ) time. The existing protocols in the same setting either run for an expected O ( n 2 ) time (Abraham et al., PODC 2008) or require exponential computing power from the honest parties (Wang, CoRR 2015). In terms of communication complexity, our construction outperforms all the known constructions with t < n /3 that offer almost-surely terminating feature. ○ With the resilience of t < n /3 + ϵ for any ϵ > 0, our second protocol runs for an expected O (1/ϵ) time. The expected running time of our protocol turns constant when ϵ is a constant fraction. The known constructions with a constant expected running time either require ϵ to be at least 1 (Feldman-Micali, STOC 1988 and Patra-Pandu Rangan, PODC 2010), implying t < n /4, or call for exponential computing power from the parties (Wang, CoRR 2015). We follow the traditional route of building BA via common coin protocol that in turn reduces to Asynchronous Verifiable Secret-Sharing (AVSS). Our constructions are built on a variant of AVSS that is termed as shunning . A shunning AVSS fails to offer the properties of AVSS when the corrupt parties strike, but allows the honest parties to locally detect and shun a set of corrupt parties for any future communication. Our shunning AVSS with t < n /3 and t < n /3 + ϵ guarantee Ω( n ) and, respectively, Ω(ϵ t 2 ) conflicts to be revealed when failure occurs. Turning this shunning AVSS to a common coin protocol efficiently constitutes yet another contribution of this work. As a secondary contribution, we show the power of the shunning technique and present a highly efficient cryptographically secure shunning AVSS, which is used further to design an asynchronous BA protocol with the optimal resilience of t < n /3 in the cryptographic setting. Our construct achieves an amortized expected communication complexity of O ( n 2 ) bits for reaching agreement on a single bit while consuming a constant expected running time. This property has been achieved for the first time in the cryptographic setting and that, too, with standard cryptographic assumptions. The best-known existing construction (Cachin et al., CCS 2002), while still needing more communication complexity than ours, is proven secure only in the Random-Oracle Model (ROM).

Abstract Privacy-preserving machine learning (PPML) via Secure Multi-party Computation (MPC) has gained momentum in the recent past. Assuming a minimal network of pair-wise private channels, we propose an efficient four-party PPML framework over rings ℤ2ℓ, FLASH, the first of its kind in the regime of PPML framework, that achieves the strongest security notion of Guaranteed Output Delivery (all parties obtain the output irrespective of adversary’s behaviour). The state of the art ML frameworks such as ABY3 by Mohassel et.al (ACM CCS’18) and SecureNN by Wagh et.al (PETS’19) operate in the setting of 3 parties with one malicious corruption but achieve the weaker security guarantee of abort. We demonstrate PPML with real-time efficiency, using the following custom-made tools that overcome the limitations of the aforementioned state-of-the-art– (a) dot product, which is independent of the vector size unlike the state-of-the-art ABY3, SecureNN and ASTRA by Chaudhari et.al (ACM CCSW’19), all of which have linear dependence on the vector size. (b) Truncation and MSB Extraction, which are constant round and free of circuits like Parallel Prefix Adder (PPA) and Ripple Carry Adder (RCA), unlike ABY3 which uses these circuits and has round complexity of the order of depth of these circuits. We then exhibit the application of our FLASH framework in the secure server-aided prediction of vital algorithms– Linear Regression, Logistic Regression, Deep Neural Networks, and Binarized Neural Networks. We substantiate our theoretical claims through improvement in benchmarks of the aforementioned algorithms when compared with the current best framework ABY3. All the protocols are implemented over a 64-bit ring in LAN and WAN. Our experiments demonstrate that, for MNIST dataset, the improvement (in terms of throughput) ranges from 24 × to 1390 × over LAN and WAN together.

Secure Multi-party Computation (MPC) with small population and honest majority has drawn focus specifically due to customization in techniques and resulting efficiency that the constructions can offer. In this work, we investigate a wide range of security notions in the five-party setting, tolerating two active corruptions. Being constant-round, our protocols are best suited for real-time, high latency networks such as the Internet. In a minimal setting of pairwise-private channels, we present efficient instantiations with unanimous abort (where either all honest parties obtain the output or none of them do) and fairness (where the adversary obtains its output only if all honest parties also receive it). With the presence of an additional broadcast channel (known to be necessary), we present a construction with guaranteed output delivery (where any adversarial behaviour cannot prevent the honest parties from receiving the output). The broadcast communication is minimal and independent of circuit size. In terms of performance (communication and run time), our protocols incur minimal overhead over the best known protocol of Chandran et al. (ACM CCS 2016) that achieves the least security of selective abort. Further, our protocols for fairness and unanimous abort can be extended to n-parties with at most √n corruptions, similar to Chandran et al. Going beyond the most popular honest-majority setting of three parties with one corruption, our results demonstrate feasibility of attaining stronger security notions for more than one active corruption at an expense not too far from the least desired security of selective abort.

Secure Multi-Party Computation (MPC) with small number of parties is an interesting area of research, primarily due to its ability to model most real-life MPC applications and the simplicity and efficiency of the resulting protocols. In this work, we present efficient, constant-round 3-party (3PC) and 4-party (4PC) protocols in the honest-majority setting that achieve strong security notions of fairness (corrupted parties receive their output only if all honest parties receive output) and guaranteed output delivery (corrupted parties cannot prevent honest parties from receiving their output). Being constant-round, our constructions are suitable for Internet-like high-latency networks and are built from garbled circuits (GC). Assuming the minimal model of pairwise-private channels, we present two protocols that involve computation and communication of a single GC-- (a) a 4-round 3PC with fairness, (b) a 5-round 4PC with guaranteed output delivery. Empirically, our protocols are on par with the best known 3PC protocol of Mohassel et al. [CCS 2015] that only achieves security with selective abort, in terms of the computation time, LAN runtime, WAN runtime and communication cost. In fact, our 4PC outperforms the 3PC of Mohassel et al. significantly in terms of per-party computation and communication cost. With an extra GC, we improve the round complexity of our 4PC to four rounds. The only 4PC in our setting, given by Ishai et al. [CRYPTO 2015], involves 12 GCs. Assuming an additional broadcast channel, we present a 5-round 3PC with guaranteed output delivery that involves computation and communication of a single GC. A broadcast channel is inevitable in this setting for achieving guaranteed output delivery, owing to an impossibility result in the literature. The overall broadcast communication of our protocol is nominal and most importantly, is independent of the circuit size. This protocol too induces a nominal overhead compared to the protocol of Mohassel et al.

Perfectly-secure verifiable secret sharing (VSS) and multi-party computation (MPC) protocols in asynchronous network tolerate only at most one-fourth of corruption, while their counterparts in synchronous network sustain against at most one-third corruption. Moreover property-wise, synchronous protocols provide much stronger guarantees than the asynchronous counterparts. Taking note of the fact that asynchronous network is more realistic on one hand and on the other, synchrony of a network has positive impact on several aspects of distributed protocols including properties and fault-tolerance, we explore the power of hybrid networks that combines best of both the worlds by supporting a few synchronous rounds at the onset of a protocol execution, before turning to asynchronous mode. In hybrid networks, we investigate various feasibility questions pertaining to protocols giving guarantees attainable in synchronous and asynchronous networks. For the asynchronous protocols in hybrid networks, we hope to leverage the initial synchronous rounds to bridge the gap in the fault-tolerance with the synchronous protocols under minimal synchrony assumption. We ask the following fundamental question of both theoretical and practical importance: What is the minimum number of initial synchronous rounds necessary and sufficient in a hybrid network to construct asynchronous perfectly-secure VSS and MPC protocols with the fault-tolerance of synchronous protocols? On the positive note, we show that the answer is one for VSS which is clearly optimal. Notably no broadcast oracle is invoked in the synchronous round of our proposed VSS protocol. On the negative side, we prove that one synchronous round is not enough for MPC, putting MPC on a higher pedestal than VSS in terms of difficulty. For synchronous protocols in hybrid networks, we hope to save on the synchronous rounds leveraging conveniently the available asynchronous phase. We settle the question for VSS in the negative showing that three rounds that are known to be necessary (and sufficient) for VSS in synchronous networks, are also required in hybrid networks. VSS being a special case of MPC, the lower bound holds true for MPC. We match the lower bound with a three-round protocol. Notably, synchronous MPC with cryptographic security is known to be achievable in hybrid networks with one synchronous round.

We revisit the problem of distributed consensus in directed graphs tolerating crash failures; we improve the round and communication complexity of the existing protocols. Moreover, we prove that our protocol requires the optimal number of communication rounds, required by any protocol belonging to a specific class of crash-tolerant consensus protocols in directed graphs.

parties to securely compute an agreed function f over some finite field in the presence of a computationally unbounded adversary, who can maliciously corrupt any t out of the n parties. Most of the known efficient MPC protocols are designed in the offline- online framework introduced in a seminal work by Beaver in CRYPTO 1991. In this framework, the parties generate shared random and private multiplication-triples during the offline phase, which are used later in the online phase for securely evaluating the multiplication gates in the circuit representing f . The efficiency of the MPC protocols in this framework then relies on efficient ways of implementing the offline phase. In this paper, we propose a new and simple framework for generating shared and private random multiplication triples with unconditional security. The existing protocols approach this problem by first producing shared pairs of private and random values, followed by securely computing the shared product of each pair of values. The latter task involves a multiplication protocol for shared values that are typically communication intensive. Our framework takes a completely different approach and shuns the use of multiplication protocol. Namely, we ask the parties to verifiably share random multiplication triples and then securely extract shared random multiplication triples unknown to the adversary, from the shared triples. Realizing our framework in the asynchronous and hybrid network setting,1 we present the first ever MPC protocols with a linear (in the number of parties) communication overhead per multiplication gate in the circuit representing f . These are significant improvements over the best known existing MPC protocols in the asynchronous and hybrid network setting with communication complexity O(n2) and O(n3), respectively. Our framework when applied to the synchronous setting results in round-efficient MPC protocols.

The problem of broadcast and Byzantine Agreement are of interest to both distributed computing and cryptography community. Often these primitives require prohibitive communication and round complexity. Broadcast extensions have been introduced to broadcast long messages at the cost of small number of broadcasts for bit. The latter are referred to as seed broadcasts.

Adaptive security is a strong corruption model that captures "hacking" attacks where an external attacker breaks into parties' machines in the midst of a protocol execution. There are two types of adaptively-secure protocols: adaptive with erasures and adaptive without erasures. Achieving adaptivity without erasures is preferable, since secure erasures are not always trivial. However, it seems far harder. We introduce a new model of adaptive security called adaptive security with partial erasures that allows erasures, but only assumes them in a minimal sense. Specifically, if all parties are corrupted then security holds as long as any single party successfully erases. In addition, security holds if any proper subset of the parties is corrupted without erasures. We initiate a theoretical study of this new notion and demonstrate that secure computation in this setting is as efficient as static secure computation. In addition, we study the relations between semi-adaptive security [GWZ09], adaptive security with partial erasures, and adaptive security without any erasures. We prove that the existence of semi-adaptive OT implies secure computation in all these settings.

Asynchronous Verifiable Secret Sharing (AVSS) is a fundamental primitive in secure distributed computing. It finds significant application in problems like asynchronous Byzantine Agreement (ABA) and Asynchronous Multiparty Computation (AMPC). In [4], we presented a new asynchronous primitive called Asynchronous Weak Commitment (AWC) and used it to construct an AVSS scheme, which is thus far the most communication efficient AVSS scheme. Through this brief announcement, we wish to make our result visible to the Distributed Computing community.

Perfectly reliable message transmission (PRMT) is one of the fundamental problems in distributed computing. It allows a sender to reliably transmit a message to a receiver in an unreliable network, even in the presence of a computationally unbounded adversary. In this article, we study the inherent trade-off between the three important parameters of the PRMT protocols, namely, the network connectivity ( n ), the round complexity ( r ), and the communication complexity by considering the following generic question (which can be considered as the holy grail problem) in the context of the PRMT protocols. Given an n -connected network, a message of size ℓ (to be reliably communicated) and a limit c for the total communication allowed between the sender and the receiver, what is the minimum number of communication rounds required by a PRMT protocol to send the message, such that the communication complexity of the protocol is O( c )? We answer this interesting question by deriving a nontrivial lower bound on the round complexity. Moreover, we show that the lower bound is tight in the amortized sense, by designing a PRMT protocol whose round complexity matches the lower bound. The lower bound is the first of its kind, that simultaneously captures the inherent tradeoff between the three important parameters of a PRMT protocol.

We design a three phase communication optimal perfectly secure message transmission (OPSMT) protocol tolerating a computationally unbounded mobile mixed adversary. This improves the nine phase OPSMT protocol of [2].

In [7], the authors presented a novel perfect (i.e error-free Asynchronous Verifiable Secret Sharing (AVSS) protocol and using the AVSS, they designed a perfect Asynchronous Multiparty Computation (AMPC) protocol that provides the best known communication complexity in the literature. In this paper, we show another important application of the AVSS in [7] by applying it to design an efficient Asynchronous Byzantine Agreement (ABA) protocol with n = 4t + 1, where n denotes the number of parties involved in the execution ABA and t denotes the maximum number of parties that can be corrupted by an active unbounded powerful adversary. Our ABA protocol attains a communication complexity that is significantly better than that of the only known existing ABA of [4] with n = 4t + 1, while keeping all other properties in place.

In this paper, we re-visit the problem of unconditionally secure message transmission (USMT) from a sender S to a receiver R, who are part of a distributed synchronous network, modeled as an arbitrary directed graph. Some of the intermediate nodes between S and R can be under the control of an adversary having unbounded computing power. Desmedt and Wang [4] have given the characterization of USMT in directed networks. However, in their model, the underlying network is abstracted as directed node disjoint paths (also called as wires/channels) between S and R, where the intermediate nodes are oblivious, message passing nodes and perform no other computation. In this work, we first show that the characterization of USMT given by Desmedt et.al [4] does not hold good for arbitrary directed networks, where the intermediate nodes can perform some computation, beside acting as message forwarding nodes. We then give the characterization of USMT in arbitrary directed networks, considering the entire network as a whole. As far our knowledge is concerned, this is the first ever characterization of USMT in arbitrary directed networks.

Consider a completely asynchronous network consisting of n parties where every two parties are connected by a private channel. An adversary At with unbounded computing power actively controls at most t = ([n/3] − 1) out of n parties in Byzantine fashion. In this setting, we say that π is a t-resilient, (1 − ε)-terminating Asynchronous Byzantine Agreement (ABA) protocol, if π satisfies all the properties of Byzantine Agreement (BA) in asynchronous settings tolerating At and terminates (i.e every honest party terminates π with probability at least (1 − ε). In this work, we present a new t-resilient, (1 − ε)-terminating ABA protocol which privately communicates O(Cn6 κ) bits and A-casts1 O(Cn6 κ) bits, where ε = 2−Ω(κ) and C is the expected running time of the protocol. Moreover, conditioned on the event that our ABA protocol terminates, it does so in constant expected time; i.e., C = O(1). Our ABA protocol is to be compared with the only known t-resilient, (1 − ε)-terminating ABA protocol of [5] in the same settings, which privately communicates O(Cn11 κ4) bits and A-casts O(Cn11 κ2 log(n)) bits, where ε = 2−Ω(κ) and C = O(1). So our ABA achieves a huge gain in communication complexity in comparison to the ABA of [5], while keeping all other properties in place. In another landmark work, in PODC 2008, Abraham et. al [1] proposed a t-resilient, 1-terminating (called as almost-surely terminating in [1]) ABA protocol which privately communicates O(Cn6 log n) bits and A-casts O(Cn6 log n) bits. But ABA protocol of Abraham et. al. takes polynomial (C = O(n2)) expected time to terminate. Hence the merits of our ABA protocol over the ABA of Abraham et. al. are: (i) For any κ < n2 log n, our ABA is better in terms of communication complexity (ii) conditioned on the event that our ABA protocol terminates, it does so in constant expected time (the constant is independent of n, t and κ), whereas ABA of Abraham et. al. takes polynomial expected time. Summing up, in a practical scenario where a faster and communication efficient ABA protocol is required, our ABA fits the bill better than ABA protocols of [5, 1].

No abstract available.

In this paper, we study the inherent tradeoff between the network connectivity, phase complexity and communication complexity of perfectly reliable message transmission (PRMT) problem in undirected synchronous network, tolerating a mixed adversary A(tb,tf), who has unbounded computing power and can corrupt tb and tf nodes in the network in Byzantine and fail-stop fashion respectively.

No abstract available.

No abstract available.