Secure Multiparty Quantum Computation with (Only) a Strict Honest Majority
Authors:
- 1 January 2006
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 02725428,p. 249-260
Abstract
Secret sharing and multiparty computation (also called "secure function evaluation") are fundamental primitives in modern cryptography, allowing a group of mutually distrustful players to perform correct, distributed computations under the sole assumption that some number of them will follow the protocol honestly. This paper investigates how much trust is necessary $that is, how many players must remain honest - in order for distributed quantum computations to be possible. We present a verifiable quantum secret sharing (VQSS) protocol, and a general secure multiparty quantum computation (MPQC) protocol, which can tolerate any cheaters among n players. Previous protocols for these tasks tolerated lfloor (n - 1)/4 rfloor and lfloor (n - 1)/6 rfloor cheaters, respectively. The threshold we achieve is tight - even in the classical case, "fair" multiparty computation is not possible if any set of n/2 players can cheat. Our protocols rely on approximate quantum error-correcting codes, which can tolerate a larger fraction of errors than traditional, exact codes. We introduce new families of authentication schemes and approximate codes tailored to the needs of our protocols, as well as new state purification techniques along the lines of those used in fault-tolerant quantum circuitsKeywords
All Related Versions
This publication has 16 references indexed in Scilit:
- Information-theoretically secure protocols and security under composition2006
- A de Finetti representation for finite symmetric quantum statesJournal of Mathematical Physics, 2005
- Fault-tolerant quantum computation2002
- Perfectly secure message transmission2002
- Secure multi-party quantum computation2002
- How to Share a Quantum SecretPhysical Review Letters, 1999
- Robust sharing of secrets when the dealer is honest or cheatingJournal of the ACM, 1994
- Verifiable secret sharing and multiparty protocols with honest majority1989
- Multiparty unconditionally secure protocols1988
- How to play ANY mental game1987