Quantum-Classical Complexity-Security Tradeoff In Secure Multi-Party Computation

Abstract

I construct a secure multi-party scheme to compute a classical function by a succinct use of a specially designed fault-tolerant random polynomial quantum error correction code. This scheme is secure provided that (asymptotically) strictly greater than five-sixths of the players are honest. Moreover, the security of this scheme follows directly from the theory of quantum error correcting code, and hence is valid without any computational assumption. I also discuss the quantum-classical complexity-security tradeoff in secure multi-party computation schemes and argue why a full-blown quantum code is necessary in my scheme.

Greatly expanded and clarified, 10 pages, requires amsfonts

References in corpus (5)

• Quantum secret sharing
• Unconditional Security Of Quantum Key Distribution Over Arbitrarily Long Distances
• Decoherence Free Subspaces for Quantum Computation
• How to share a quantum secret
• Quantum repeaters based on entanglement purification

Cited by in corpus (8)

• Four Photon Entanglement from Down Conversion
• Secure multi-party quantum summation based on quantum Fourier transform
• Multi-party Quantum Computation
• Secure assisted quantum computation
• Unconditionally Secure Quantum Coin Tossing
• Secure Multi-party Quantum Computing
• Multi-party quantum summation based on quantum teleportation
• Improvements on "Secure multi-party quantum summation based on quantum Fourier transform"