Article

Secure multi-party quantum computation

Authors:

Claude Crépeau,

Daniel Gottesman,

Adam SmithAuthors Info & Claims

STOC '02: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing

Pages 643 - 652

https://doi.org/10.1145/509907.510000

Published: 19 May 2002 Publication History

Abstract

Secure multi-party computing, also called secure function evaluation, has been extensively studied in classical cryptography. We consider the extension of this task to computation with quantum inputs and circuits. Our protocols are information-theoretically secure, i.e. no assumptions are made on the computational power of the adversary. For the weaker task of verifiable quantum secret sharing, we give a protocol which tolerates any t ξ n/4 cheating parties (out of n). This is shown to be optimal. We use this new tool to show how to perform any multi-party quantum computation as long as the number of dishonest players is less than n/6.

References

[1]

Proc. of 20th STOC, Chicago, Illinois, 2--4 May 1988.

[2]

D. Aharonov and M. Ben-Or. Fault tolerant quantum computation with constant error rate. quant-ph/9906129. Preliminary version in STOC '97. Submitted to SIAM J. Comp., June 1999.

Digital Library

[3]

D. Beaver. Multiparty protocols tolerating half faulty processors. In G. Brassard, editor, Proc. of CRYPTO '89, volume 435 of LNCS, pages 560--572. IACR, Springer-Verlag, 1990, 20--24 Aug. 1989.

Digital Library

[4]

D. Beaver. Foundations of secure interactive computing. In Feigenbaum {12}, pages 377--391.

Digital Library

[5]

M. Ben-Or, S. Goldwasser, and A. Wigderson. Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In ACM {1}, pages 1--10.

Digital Library

[6]

R. Canetti. Universally composable security: A new paradigm for cryptographic protocols. In Proc. of FOCS 2001, pages 136--147, 2001.

Digital Library

[7]

H. F. Chau. Quantum-classical complexity-security tradeoff in secure multiparty computations. Physical Review A, 61, March 2000.

[8]

D. Chaum, C. Crépeau, and I. Damgård. Multiparty unconditionally secure protocols (extended abstract). In ACM {1}, pages 11--19.

Digital Library

[9]

B. Chor, S. Goldwasser, S. Micali, and B. Awerbuch. Verifiable secret sharing and achieving simultaneity in the presence of faults (extended abstract). In Proc. of 26th FOCS, pages 383--395, Portland, Oregon, 21--23 Oct. 1985. ieee.

[10]

R. Cleve, D. Gottesman, and H.-K. Lo. How to share a quantum secret. Physical Review Letters, 83:648--651, 1999.

[11]

R. Cramer, I. Damgård, S. Dziembowski, M. Hirt, and T. Rabin. Efficient multiparty computations with dishonest minority. In J. Stern, editor, Proc. of EUROCRYPT 99, volume 1592 of LNCS. IACR, Springer-Verlag, 1999.

[12]

J. Feigenbaum, editor. Proc. of CRYPTO '91}, volume 576 of LNCS. IACR, Springer-Verlag, 1992, 11--15 Aug. 1991.

[13]

O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game or a completeness theorem for protocols with honest majority. In Proc. of 19th STOC, pages 218--229, New York City, 25--27 May 1987.

Digital Library

[14]

S. Goldwasser and L. A. Levin. Fair computation of general functions in presence of immoral majority. In A. J. Menezes and S. A. Vanstone, editors, Proc. of CRYPTO '90, volume 537 of LNCS, pages 77--93. IACR, Springer-Verlag, 1991.

Digital Library

[15]

D. Gottesman and C. H. Bennett. Unpublished work. 1998.

[16]

E. Knill and R. Laflamme. A theory of quantum error-correcting codes. Physical Review A, 55:900--911, 1997. quant-ph/9604034.

[17]

H.-K. Lo and H. F. Chau. Unconditional security of quantum key distribution over arbitrary long distances. Science, 283(5410):2050--2056, 26 March 1999}.

[18]

S. Micali and P. Rogaway. Secure computation (abstract). In Feigenbaum {12}, pages 392--404.

Digital Library

[19]

M. Nielsen and I. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000.

Digital Library

[20]

B. Pfitzmann and M. Waidner. Composition and integrity preservation of secure reactive systems. In Proc. of Computer and Communications Security, pages 245--254, 2000.

Digital Library

[21]

T. Rabin and M. Ben-Or. Verifiable secret sharing and multiparty protocols with honest majority (extended abstract). In Proc. of 21st STOC, pages 73--85, Seattle, Washington, 15--17 May 1989.

Digital Library

[22]

A. Smith. Multi-party quantum computation. Master's thesis, MIT, Aug. 2001. Available as quant-ph/0111030.

Cited By

Matsumoto R(2025)Advance Sharing Procedures for the Ramp Quantum Secret Sharing Schemes With the Highest Coding RateIEEE Transactions on Quantum Engineering10.1109/TQE.2025.35309396(1-7)Online publication date: 2025
https://doi.org/10.1109/TQE.2025.3530939
Cen WZhang JCai KSun SLui J(2025)A Fast Heuristic Entanglement Distribution Algorithm for Quantum Repeater ChainsIEEE Transactions on Networking10.1109/TNET.2024.347537833:1(146-161)Online publication date: Feb-2025
https://doi.org/10.1109/TNET.2024.3475378
Zhang JZhang JQin SJin Z(2025)A (t, n) threshold quantum secret sharing with authentication based on single photonsQuantum Information Processing10.1007/s11128-025-04672-224:2Online publication date: 18-Feb-2025
https://doi.org/10.1007/s11128-025-04672-2
Show More Cited By

Index Terms

Secure multi-party quantum computation
1. Security and privacy
  1. Cryptography
  2. Systems security
    1. Operating systems security
2. Theory of computation
  1. Logic
  2. Models of computation
    1. Probabilistic computation

Recommendations

Everlasting Multi-party Computation

A protocol has everlasting security if it is secure against adversaries that are computationally unlimited after the protocol execution. This models the fact that we cannot predict which cryptographic schemes will be broken, say, several decades after ...
Collusive attacks to "circle-type" multi-party quantum key agreement protocols

We find that existing multi-party quantum key agreement (MQKA) protocols designed for fairness of the key are, in fact, unfair. Our analysis shows that these protocols are sensitive to collusive attacks; that is, dishonest participants can collaborate ...
Efficient Fair Secure Two-Party Computation
APSCC '12: Proceedings of the 2012 IEEE Asia-Pacific Services Computing Conference)

Yao first introduced a constant-round protocol for secure two-party computation (2PC) withstanding semi-honest adversaries by using a tool called """"garbled circuit"""". Later, many protocols based on garbled circuit approach have been presented, most ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC '02: Proceedings of the thiry-fourth annual ACM symposium on Theory of computing

May 2002

840 pages

ISBN:1581134959

DOI:10.1145/509907

Conference Chair:
John Reif
Duke University

Copyright © 2002 ACM.

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]

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 May 2002

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

STOC02

Sponsor:

SIGACT

STOC02: Symposium on the Theory of Computing

May 19 - 21, 2002

Quebec, Montreal, Canada

Acceptance Rates

STOC '02 Paper Acceptance Rate 91 of 287 submissions, 32%;

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

96
Total Citations
View Citations
409
Total Downloads

Downloads (Last 12 months)83
Downloads (Last 6 weeks)9

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Matsumoto R(2025)Advance Sharing Procedures for the Ramp Quantum Secret Sharing Schemes With the Highest Coding RateIEEE Transactions on Quantum Engineering10.1109/TQE.2025.35309396(1-7)Online publication date: 2025
https://doi.org/10.1109/TQE.2025.3530939
Cen WZhang JCai KSun SLui J(2025)A Fast Heuristic Entanglement Distribution Algorithm for Quantum Repeater ChainsIEEE Transactions on Networking10.1109/TNET.2024.347537833:1(146-161)Online publication date: Feb-2025
https://doi.org/10.1109/TNET.2024.3475378
Zhang JZhang JQin SJin Z(2025)A (t, n) threshold quantum secret sharing with authentication based on single photonsQuantum Information Processing10.1007/s11128-025-04672-224:2Online publication date: 18-Feb-2025
https://doi.org/10.1007/s11128-025-04672-2
Brassard GCrépeau C(2025)Quantum CryptographyEncyclopedia of Cryptography, Security and Privacy10.1007/978-3-030-71522-9_241(2032-2032)Online publication date: 8-Jan-2025
https://doi.org/10.1007/978-3-030-71522-9_241
Kose B(2024)The Convergence of Quantum Computing and BlockchainApplications and Principles of Quantum Computing10.4018/979-8-3693-1168-4.ch021(418-436)Online publication date: 31-Jan-2024
https://doi.org/10.4018/979-8-3693-1168-4.ch021
Song SLe Gall FHayashi M(2024)Prior entanglement exponentially improves one-server quantum private information retrieval for quantum messagesEPJ Quantum Technology10.1140/epjqt/s40507-024-00266-611:1Online publication date: 6-Sep-2024
https://doi.org/10.1140/epjqt/s40507-024-00266-6
Sutradhar KVenkatesh R(2024)SVQCP: A Secure Vehicular Quantum Communication ProtocolIEEE Transactions on Network Science and Engineering10.1109/TNSE.2024.339615711:5(4850-4859)Online publication date: Sep-2024
https://doi.org/10.1109/TNSE.2024.3396157
Iñesta ÁChoi HEnglund DWehner S(2024)Quantum Circuit Switching with One-Way Repeaters in Star Networks2024 IEEE International Conference on Quantum Computing and Engineering (QCE)10.1109/QCE60285.2024.00215(1857-1867)Online publication date: 15-Sep-2024
https://doi.org/10.1109/QCE60285.2024.00215
Schoinas ITriantafyllou AIoannidis DTzovaras DDrosou AVotis KLagkas TArgyriou VSarigiannidis P(2024)Federated Learning: Challenges, SoTA, Performance Improvements and Application DomainsIEEE Open Journal of the Communications Society10.1109/OJCOMS.2024.34580885(5933-6017)Online publication date: 2024
https://doi.org/10.1109/OJCOMS.2024.3458088
Chen FJiang LMüller HRicherme PChu CFu ZYang M(2024)NISQ Quantum Computing: A Security-Centric Tutorial and Survey [Feature]IEEE Circuits and Systems Magazine10.1109/MCAS.2024.334966524:1(14-32)Online publication date: Sep-2025
https://doi.org/10.1109/MCAS.2024.3349665
Show More Cited By

View Options

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten