Article

Free access

The round complexity of secure protocols

Authors:

D. Beaver,

S. Micali,

P. RogawayAuthors Info & Claims

STOC '90: Proceedings of the twenty-second annual ACM symposium on Theory of Computing

Pages 503 - 513

https://doi.org/10.1145/100216.100287

Published: 01 April 1990 Publication History

PDF eReader

References

[1]

[BB89] J. Bar-Ilan and D. Beaver, "Non-Cryptographic Fault Tolerant Computing in a Constant Number of Rounds of Interaction," Proc. of the 8th PODC (1989), 201-209.

Digital Library

Google Scholar

[2]

[Be88] D. Beaver, "Secure Multiparty Protocols Tolerating Half Faulty Processors," Harvard Technical Report TR-19-88, and in CRYPTO-89 Proceedings.

Google Scholar

[3]

[Be90] D. Beaver, "Security, Fault-Tolerance, and Communication Complexity for Distributed Systems," Harvard University Ph.D. Thesis, 1990.

Digital Library

Google Scholar

[4]

[BFKR89] D. Beaver, J. Feigenbaum, J. Kilian, and P. Rogaway, "Cryptographic Applications of Locally Random Reductions," Bell Laboratories Technical Memorandum, November 1989. Also a 1990 PODC submission, "Security with Low Communication Overhead."

Google Scholar

[5]

[BG89] D. Beaver and S. Goldwasser, "Multiparty Computations with Faulty Majority," CRYPTO-89 Proceedings.

Digital Library

Google Scholar

[6]

[BE88] M. Ben-Or and R. El-Yaniv, "Interactive Consistency in Constant Expected Time," manuscript, December 1988.

Google Scholar

[7]

[BGW88] M. Ben-Or, S. Goldwasser and A. Wigderson, "Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation," Proc. of the 20th STOC (1988), 1-10.

Digital Library

Google Scholar

[8]

[BM82] M. Blum and S. Micali, "How to Generate Cryptographically Strong Sequences of Pseudo-Random Bits," SIAM J. of Computing, 13:850-864 (1984), and FOCS 82.

Digital Library

Google Scholar

[9]

[Ch89] D. Chaum, "The Spymasters Double-Agent Problem: Multiparty Computations Secure Unconditionally from Minorities and Cryptographically from Majorities," CRYPTO-89 Proceeding.

Digital Library

Google Scholar

[10]

[CCD88] D. Chaum, C. Crépeau and I. Damgård, "Multiparty Unconditionally Secure Protocols," Proc. of the 20th STOC (1988), 11-19.

Digital Library

Google Scholar

[11]

[CDG87] D. Chaum, I. Damgård and J. van de Graff, "Multiparty Computations Ensuring the Privacy of Each Party's Input and Correctness of the Result," CRYPTO-87 Proceedings, 87-119.

Digital Library

Google Scholar

[12]

[CGMA85] B. Chor, O. Goldreich, S. Micali and B. Awerbuch, "Verifiable Secret Sharing and Achieving Simultaneity in the Presence of Faults," Proc. of the 26th FOCS (1985), 383-395.

Google Scholar

[13]

[CR87] B. Chor and M. Rabin, "Achieving Independence in Logarithmic Number of Rounds," Proc. of the 6th PODC (1987).

Digital Library

Google Scholar

[14]

[Fe88] P. Feldman, "One Can Always Assume Private Channels," unpublished manuscript (1988).

Google Scholar

[15]

[FM88] P. Feldman and S. Micali, "Optimal Algorithms for Byzantine Agreement," Proc. of the 20th STOC (1988), 148-161.

Digital Library

Google Scholar

[16]

[GHY87] Z. Galil, S. Haber and M. Yung, "Cryptographic Computation: Secure Fault-Tolerant Protocols and the Public-Key Model," CRYPTO-87 Proceedings, 135-155.

Digital Library

Google Scholar

[17]

[GMW87] O. Goldreich, S. Micali and A. Wigderson, "How to Play Any Mental Game," Proc. of the 19th STOC (1987), 218-229.

Digital Library

Google Scholar

[18]

[GV87] O. Goldreich and R. Vainish, "How to Solve any Protocol Problem--An Efficiency Improvement," CRYPTO-87 Proceedings, 76-86.

Digital Library

Google Scholar

[19]

[Ha88] S. Haber, "Multi-Party Cryptographic Computation: Techniques and Applications," Columbia University Ph.D. Thesis (1988).

Digital Library

Google Scholar

[20]

[Ha90] J. Håstad, "Pseudo-Random Generators with Uniform Assumptions," these proceedings.

Digital Library

Google Scholar

[21]

[KMR90] J. Kilian, S. Micali and P. Rogaway, "The Notion of Secure Computation," manuscript, March 1990.

Google Scholar

[22]

[ILL89] R. Impagliazzo, L. Levin and M. Luby, "Pseudo-Random Generation from One-Way Functions," Proc. of the 21st STOC (1989), 12-23.

Digital Library

Google Scholar

[23]

[RB89] T. Rabin and M. Ben-Or, "Verifiable Secret Sharing and Multiparty Protocols with Honest Majority," Proc. of the 21st STOC (1989), 73-85.

Digital Library

Google Scholar

[24]

[Ro90] P. Rogaway, "The Round Complexity of Secure Protocols," MIT Ph.D. Thesis (1990).

Digital Library

Google Scholar

[25]

[Ya82a] A. Yao, Protocols for Secure Computation, Proc. of the 23rd FOCS (1982) 160-164.

Google Scholar

[26]

[Ya82b] A. Yao, "Theory and Applications of Trapdoor Functions," Proc. of the 23rd FOCS (1982) 80-91.

Google Scholar

[27]

[Ya86] A. Yao, "How to Generate and Exchange Secrets," Proc. of the 18th STOC (1986) 162-167.

Google Scholar

Cited By

View all

Scafuro AVerber T(2025)A New Paradigm for Server-Aided MPCIACR Communications in Cryptology10.62056/ab3wa0l5vt1:4Online publication date: 13-Jan-2025
https://doi.org/10.62056/ab3wa0l5vt
Lu YZhang BRen K(2025)Load-Balanced Server-Aided MPC in Heterogeneous ComputingIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.349454720(114-128)Online publication date: 2025
https://doi.org/10.1109/TIFS.2024.3494547
Zhang CLiu YXu MYang XLi PYang CLiu QXiong XChen PWang W(2025)Trans-Border Trusted Data Spaces: A General Framework Supporting Trustworthy International Data CirculationIEEE Access10.1109/ACCESS.2025.354129513(30481-30496)Online publication date: 2025
https://doi.org/10.1109/ACCESS.2025.3541295
Show More Cited By

Recommendations

The Exact Round Complexity of Secure Computation
Proceedings, Part II, of the 35th Annual International Conference on Advances in Cryptology --- EUROCRYPT 2016 - Volume 9666

We revisit the exact round complexity of secure computation in the multi-party and two-party settings. For the special case of two-parties without a simultaneous message exchange channel, this question has been extensively studied and resolved. In ...
On the Round Complexity of Black-Box Secure MPC
Advances in Cryptology – CRYPTO 2021
Abstract
We consider the question of minimizing the round complexity of secure multiparty computation (MPC) protocols that make a black-box use of simple cryptographic primitives with security against any number of malicious parties. In the plain model, ...
Round-Optimal Secure Multi-party Computation
Abstract
Secure multi-party computation (MPC) is a central cryptographic task that allows a set of mutually distrustful parties to jointly compute some function of their private inputs where security should hold in the presence of an active (i.e. malicious)...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

STOC '90: Proceedings of the twenty-second annual ACM symposium on Theory of Computing

April 1990

574 pages

ISBN:0897913612

DOI:10.1145/100216

Editor:
Harriet Ortiz

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 1990

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

STOC90

Sponsor:

SIGACT

STOC90: 22nd Annual ACM Symposium on Theory of Computing

May 13 - 17, 1990

Maryland, Baltimore, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

505
Total Citations
View Citations
2,724
Total Downloads

Downloads (Last 12 months)430
Downloads (Last 6 weeks)51

Reflects downloads up to 23 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

View all

Scafuro AVerber T(2025)A New Paradigm for Server-Aided MPCIACR Communications in Cryptology10.62056/ab3wa0l5vt1:4Online publication date: 13-Jan-2025
https://doi.org/10.62056/ab3wa0l5vt
Lu YZhang BRen K(2025)Load-Balanced Server-Aided MPC in Heterogeneous ComputingIEEE Transactions on Information Forensics and Security10.1109/TIFS.2024.349454720(114-128)Online publication date: 2025
https://doi.org/10.1109/TIFS.2024.3494547
Zhang CLiu YXu MYang XLi PYang CLiu QXiong XChen PWang W(2025)Trans-Border Trusted Data Spaces: A General Framework Supporting Trustworthy International Data CirculationIEEE Access10.1109/ACCESS.2025.354129513(30481-30496)Online publication date: 2025
https://doi.org/10.1109/ACCESS.2025.3541295
Tozawa KMorita HMizuki T(2025)Single-shuffle card-based protocol with eight cards per gate and its extensionsNatural Computing10.1007/s11047-024-10006-5Online publication date: 9-Jan-2025
https://doi.org/10.1007/s11047-024-10006-5
Baek CKim T(2025)Can we beat three halves lower bound? (Im)possibility of reducing communication cost for garbled circuitsDesigns, Codes and Cryptography10.1007/s10623-025-01577-0Online publication date: 8-Feb-2025
https://doi.org/10.1007/s10623-025-01577-0
Cui HWang XYang KYu Y(2025)Actively Secure Half-Gates with Minimum Overhead under Duplex NetworksJournal of Cryptology10.1007/s00145-025-09539-438:2Online publication date: 26-Feb-2025
https://doi.org/10.1007/s00145-025-09539-4
Cohen RDoerner JKondi YShelat A(2025)Guaranteed Output in $$O(\sqrt{n})$$ Rounds for Round-Robin Sampling ProtocolsJournal of Cryptology10.1007/s00145-024-09523-438:1Online publication date: 13-Jan-2025
https://doi.org/10.1007/s00145-024-09523-4
Ali SMamoon SUsman AAbidin ZZhao C(2025)HybridFL: Hybrid Approach Toward Privacy-Preserving Federated LearningSecurity and Privacy in New Computing Environments10.1007/978-3-031-73699-5_1(3-18)Online publication date: 1-Jan-2025
https://doi.org/10.1007/978-3-031-73699-5_1
Yan XLian BYang YWang XCui JZhao XWang FChen K(2024)A Ciphertext Reduction Scheme for Garbling an S-Box in an AES Circuit with Minimal Online TimeSymmetry10.3390/sym1606066416:6(664)Online publication date: 28-May-2024
https://doi.org/10.3390/sym16060664
Luo YChen YLi TTan CDou H(2024)Cloud-SMPC: two-round multilinear maps secure multiparty computation based on LWE assumptionJournal of Cloud Computing10.1186/s13677-023-00586-513:1Online publication date: 22-Jan-2024
https://doi.org/10.1186/s13677-023-00586-5
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

The Exact Round Complexity of Secure Computation

On the Round Complexity of Black-Box Secure MPC

Round-Optimal Secure Multi-party Computation