Lecture notes in computer science

On Secure Computation of Solitary Output Functionalities with and Without Broadcast

Bar Alon, Eran Omri

Published Jan 1, 2023• 0 citations

Publisher

DOI: 10.1007/978-3-031-48618-0_4

Related papers

On Fully Secure MPC with Solitary Output

Shai Halevi, Yuval Ishai, Eyal Kushilevitz Z +2 more

Lecture notes in computer scienceJan 1, 201913 citations

Secure Computation with Minimal Interaction, Revisited

Yuval Ishai, Ranjit Kumaresan, Eyal Kushilevitz Z +1 more

Lecture notes in computer scienceJan 1, 201541 citations

On the Communication Complexity of Secure Multi-Party Computation With Aborts

James Bartusek, Thiago Bergamaschi, Seri Khoury +2 more

A central goal of cryptography is Secure Multi-party Computation (MPC), where n parties desire to compute a function of their joint inputs without letting any party learn about the inputs of its peers. Unfortunately, it is well-known that MPC guaranteeing output delivery to every party is infeasible when a majority of the parties are malicious. In fact, parties operating over a point-to-point network (i.e., without access to a broadcast channel) cannot even reach an agreement on the output when more than one third of the parties are malicious (Lamport, Shostak, and Pease, JACM 1980).

arXiv:2406.06914ACM Symposium on Principles of Distributed Computing (PODC)Jun 5, 20240 citations

Studies on fault-tolerant broadcast and secure computation

Jonathan I. Katz, Chiu‐Yuen Koo

In this dissertation, we consider the design of broadcast and secure multi-party computation (MPC) protocols in the presence of adversarial faults. Secure multi-party computation is the most generic problem in fault-tolerant distributed computing. In principle, a multi-party computation protocol can be used to solve any distributed cryptographic problem. Informally, the problem of multi-party computation is the following: suppose we have n parties P1, P2,…, Pn where each party Pi has a private input xi. Together, the parties want to compute a function of their inputs (y1, y2,…, yn) = f(x1,x2,…, xn). However, some parties can be corrupted and do not execute a prescribed protocol faithfully. Even worse, they may be controlled by an adversary and attack the protocol in a coordinated manner. Despite the presence of such an adversary, a secure MPC protocol should ensure that each (corrupted) party Pi learn only its output yi but nothing more. Broadcast in the presence of adversarial faults is one of the simplest special cases of multi-party computation and important component of larger protocols. In short, broadcast allows a party to send the same message to all parties, and all parties to be assured they have received identical messages. The contribution of this dissertation is twofold. First, we construct broadcast and secure multi-party computation protocols for honest majority in a point-to-point network whose round complexities improve significantly upon prior work. In particular, we give the first expected constant-round authenticated broadcast protocol for honest majority assuming only public-key infrastructure and signatures. Second, we initiate the study of broadcast in radio networks in the presence of adversarial faults. In radio networks, parties communicate through multicasting messages; a message can only be received by the parties within some radius from the sender. Feasibility and impossibility results are given, and our bounds are tight.

Jan 1, 200710 citations

Secure Computations on Real-Valued Signals

Björn Deiseroth, Martin Franz, Kay Hamacher +3 more

Dec 1, 20107 citations

Fairness Versus Guaranteed Output Delivery in Secure Multiparty Computation.

Ran Cohen, Yehuda Lindell

In the setting of secure multiparty computation, a set of parties wish to compute a joint function of their private inputs. The computation should preserve security properties such as privacy, correctness, independence of inputs, fairness and guaranteed output delivery. In the case of no honest majority, fairness and guaranteed output delivery cannot always be obtained. Thus, protocols for secure multiparty computation are typically of two disparate types: protocols that assume an honest majority (and achieve all properties including fairness and guaranteed output delivery), and protocols that do not assume an honest majority (and achieve all properties except for fairness and guaranteed output delivery). In addition, in the two-party case, fairness and guaranteed output delivery are equivalent. As a result, the properties of fairness (which means that if corrupted parties receive output then so do the honest parties) and guaranteed output delivery (which means that corrupted parties cannot prevent the honest parties from receiving output in any case) have typically been considered to be the same. In this paper, we initiate a study of the relation between fairness and guaranteed output delivery in secure multiparty computation. We show that in the multiparty setting these proper-ties are distinct and proceed to study under what conditions fairness implies guaranteed output delivery (the opposite direction always holds). We also show the existence of non-trivial func-tions for which complete fairness is achievable (without an honest majority) but guaranteed output delivery is not, and the existence of non-trivial functions for which complete fairness and guaranteed output delivery are achievable. Our study sheds light on the role of broadcast in fairness and guaranteed output delivery, and shows that these properties should sometimes be considered separately.

Jan 1, 20140 citations