Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

Round-Efficient Secure Computation in Point-to-Point Networks

Jonathan I. Katz, Chiu‐Yuen Koo

Published Jan 1, 2007• 32 citations
Publisher
DOI
10.1007/978-3-540-72540-4_18

Related papers

Round Efficient Unconditionally Secure Multiparty Computation Protocol

Arpita Patra, Ashish Choudhary, Chandrasekharan Pandu Rangan

Lecture notes in computer science•Jan 1, 2008•12 citations

Improving the Round Complexity of VSS in Point-to-Point Networks.

Jonathan I. Katz, Chiu‐Yuen Koo, Ranjit Kumaresan

We revisit the following question: what is the optimal round complexity of verifiable secret sharing (VSS)? We focus here on the case of perfectly-secure VSS where the number of corrupted parties t satisfies t < n/3, with n being the total number of parties. Work of Gennaro et al. (STOC 2001) and Fitzi et al. (TCC 2006) shows that, assuming a broadcast channel, 3 rounds are necessary and sufficient for efficient VSS. The efficient 3-round protocol of Fitzi et al., however, treats the broadcast channel as being available “for free” and does not attempt to minimize its usage. This approach leads to relatively poor round complexity when protocols are compiled for a point-to-point network. We show here a VSS protocol that is simultaneously optimal in terms of both the number of rounds and the number of invocations of broadcast. Our protocol also has a certain “2-level sharing” property that makes it useful for constructing protocols for general secure computation.

•Jan 1, 2007•0 citations

Round-Optimal Secure Multi-Party Computation

Shai Halevi, Carmit Hazay, Antigoni Polychroniadou +1 more

Lecture notes in computer science•Jan 1, 2018•37 citations

Optimization for large-scale VSS based on secure multicast

Fei Du

VSS is an important generalized secure multi-party computation protocol,the round complexity and communication complexity are two of its most important complexity measures.Some existing VSS protocols with constant round under standard model that requires secure channel and broadcast channel are efficient theoretically,however,they can' t be applied to real point-to-point networks.Because secure group communication has significant influence on security and performance for secure multi-party computation protocols,an architecture—SMPC over SM was proposed.A two-level decentralized group key management scheme that shared a group key among all members was designed.By assembling those messages needed to be unicast respectively in the scheme,and then multicasting the assembled message,constant order communication complexity was achieved,better scalability and ability of fault tolerance were also obtained.Based on the proposed architecture—SMPC over SM and group key management,VSS with constant round under standard model in Katz et al was optimized,its communication complexity was reduced from O(n3) to O(n2),optimum round complexity was inherited and processing delay of nodes was lowered to 1/n as well.

Yunnan Daxue xuebao. Shehui kexue ban•Jan 1, 2012•1 citation

Round-Optimal Secure Multi-party Computation

Shai Halevi, Carmit Hazay, Antigoni Polychroniadou +1 more

Journal of Cryptology•May 13, 2021•14 citations

Broadcast-Efficient Secure Multiparty Computation.

Juan A. Garay, Clint Givens, Rafail Ostrovsky

Secure multiparty computation (MPC) is perhaps the most popular paradigm in the area of cryptographic protocols. It allows several mutually untrustworthy parties to jointly compute a function of their private inputs, without revealing to each other information about those inputs. In the case of unconditional (information-theoretic) security, protocols are known which tolerate a dishonest minority of players, who may coordinate their attack and deviate arbitrarily from the protocol specification. It is typically assumed in these results that parties are connected pairwise by authenticated, private channels, and that in addition they have access to a “broadcast ” channel. Broadcast allows one party to send a consistent message to all other parties, guaranteeing consistency even if the broadcaster is corrupted. Because broadcast cannot be simulated on the point-to-point network when more than a third of the parties are corrupt, it is impossible to construct general MPC protocols in this setting without using a broadcast channel (or some equivalent addition to the model). A great deal of research has focused on increasing the efficiency of MPC, primarily in terms of round complexity and communication complexity. In this work we propose a refinement of the round complexity which we term broadcast complexity. We view the broadcast channel as an expensive resource

•Jan 1, 2012•3 citations
We revisit the following question: what is the optimal round complexity of verifiable secret sharing (VSS)? We focus here on the case of perfectly-secure VSS where the number of corrupted parties t satisfies t < n/3, with n being the total number of parties. Work of Gennaro et al. (STOC 2001) and Fitzi et al. (TCC 2006) shows that, assuming a broadcast channel, 3 rounds are necessary and sufficient for efficient VSS. The efficient 3-round protocol of Fitzi et al., however, treats the broadcast channel as being available “for free” and does not attempt to minimize its usage. This approach leads to relatively poor round complexity when protocols are compiled for a point-to-point network. We show here a VSS protocol that is simultaneously optimal in terms of both the number of rounds and the number of invocations of broadcast. Our protocol also has a certain “2-level sharing” property that makes it useful for constructing protocols for general secure computation.
VSS is an important generalized secure multi-party computation protocol,the round complexity and communication complexity are two of its most important complexity measures.Some existing VSS protocols with constant round under standard model that requires secure channel and broadcast channel are efficient theoretically,however,they can' t be applied to real point-to-point networks.Because secure group communication has significant influence on security and performance for secure multi-party computation protocols,an architecture—SMPC over SM was proposed.A two-level decentralized group key management scheme that shared a group key among all members was designed.By assembling those messages needed to be unicast respectively in the scheme,and then multicasting the assembled message,constant order communication complexity was achieved,better scalability and ability of fault tolerance were also obtained.Based on the proposed architecture—SMPC over SM and group key management,VSS with constant round under standard model in Katz et al was optimized,its communication complexity was reduced from O(n3) to O(n2),optimum round complexity was inherited and processing delay of nodes was lowered to 1/n as well.
Secure multiparty computation (MPC) is perhaps the most popular paradigm in the area of cryptographic protocols. It allows several mutually untrustworthy parties to jointly compute a function of their private inputs, without revealing to each other information about those inputs. In the case of unconditional (information-theoretic) security, protocols are known which tolerate a dishonest minority of players, who may coordinate their attack and deviate arbitrarily from the protocol specification. It is typically assumed in these results that parties are connected pairwise by authenticated, private channels, and that in addition they have access to a “broadcast ” channel. Broadcast allows one party to send a consistent message to all other parties, guaranteeing consistency even if the broadcaster is corrupted. Because broadcast cannot be simulated on the point-to-point network when more than a third of the parties are corrupt, it is impossible to construct general MPC protocols in this setting without using a broadcast channel (or some equivalent addition to the model). A great deal of research has focused on increasing the efficiency of MPC, primarily in terms of round complexity and communication complexity. In this work we propose a refinement of the round complexity which we term broadcast complexity. We view the broadcast channel as an expensive resource