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

1/p-Secure Multiparty Computation without Honest Majority and the Best of Both Worlds

Amos Beimel, Yehuda Lindell, Eran Omri, Ilan Orlov

Published Jan 1, 2011• 55 citations
Publisher
DOI
10.1007/978-3-642-22792-9_16

Related papers

$${\varvec{1/p}}$$-Secure Multiparty Computation without an Honest Majority and the Best of Both Worlds

Amos Beimel, Yehuda Lindell, Eran Omri +1 more

Journal of Cryptology•Jul 16, 2020•4 citations

Round-Optimal Secure Multiparty Computation with Honest Majority

Prabhanjan Ananth, Arka Rai Choudhuri, Aarushi Goel +1 more

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

When Is a Semi-honest Secure Multiparty Computation Valuable?

Radhika Bhargava, Chris Clifton

Lecture notes in computer science•Jan 1, 2019•1 citation

On Achieving the “Best of Both Worlds” in Secure Multiparty Computation

Yuval Ishai, Jonathan I. Katz, Eyal Kushilevitz +2 more

Two settings are traditionally considered for secure multiparty computation, depending on whether or not a majority of the parties are assumed to be honest. Existing protocols that assume an honest majority provide “full security” (and, in particular, guarantee output delivery and fairness) when this assumption holds, but are completely insecure if this assumption is violated. On the other hand, known protocols tolerating an arbitrary number of corruptions do not guarantee fairness or output delivery even if only a single party is dishonest. It is natural to wonder whether it is possible to achieve the “best of both worlds”: namely, a single protocol that simultaneously achieves the best possible security in both the above settings. Here, we rule out this possibility (at least for general functionalities) and show some positive results regarding what can be achieved.

SIAM Journal on Computing•Jan 1, 2011•32 citations

On achieving the "best of both worlds" in secure multiparty computation

Jonathan I. Katz

Two settings are typically considered for secure multipartycomputation, depending on whether or not a majority of the partiesare assumed to be honest. Protocols designed under this assumptionprovide "full security" (and, in particular, guarantee outputdelivery and fairness) when this assumption is correct; however, if half or more of the parties are dishonest then security iscompletely compromised. On the other hand, protocols toleratingarbitrarily-many faults do not provide fairness or guaranteed output delivery even if only a single party is dishonest. It isnatural to wonder whether it is possible to achieve the "best ofboth worlds" : namely, a single protocol that simultaneouslyachieves the best possible security in both the above settings. Ishai, et al. (Crypto 2006) recently addressed this question, andruled out constant-round protocols of this type.

ACM Symposium on Theory of Computing (STOC)•Jun 11, 2007•70 citations

Round Efficient Unconditionally Secure Multiparty Computation Protocol

Arpita Patra, Ashish Choudhary, Chandrasekharan Pandu Rangan

Lecture notes in computer science•Jan 1, 2008•11 citations
Two settings are traditionally considered for secure multiparty computation, depending on whether or not a majority of the parties are assumed to be honest. Existing protocols that assume an honest majority provide “full security” (and, in particular, guarantee output delivery and fairness) when this assumption holds, but are completely insecure if this assumption is violated. On the other hand, known protocols tolerating an arbitrary number of corruptions do not guarantee fairness or output delivery even if only a single party is dishonest. It is natural to wonder whether it is possible to achieve the “best of both worlds”: namely, a single protocol that simultaneously achieves the best possible security in both the above settings. Here, we rule out this possibility (at least for general functionalities) and show some positive results regarding what can be achieved.
Two settings are typically considered for secure multipartycomputation, depending on whether or not a majority of the partiesare assumed to be honest. Protocols designed under this assumptionprovide "full security" (and, in particular, guarantee outputdelivery and fairness) when this assumption is correct; however, if half or more of the parties are dishonest then security iscompletely compromised. On the other hand, protocols toleratingarbitrarily-many faults do not provide fairness or guaranteed output delivery even if only a single party is dishonest. It isnatural to wonder whether it is possible to achieve the "best ofboth worlds" : namely, a single protocol that simultaneouslyachieves the best possible security in both the above settings. Ishai, et al. (Crypto 2006) recently addressed this question, andruled out constant-round protocols of this type.