Secure Multiparty Quantum Computation with (Only) a Strict Honest Majority

Details Secure Multiparty Quantum Computation with (Only) a Strict Honest Majority Secure Multiparty Quantum Computation with (Only) a Strict Honest Majority

2008-01-10

arxiv.org/abs/0801.1544v1

Proc. 47th Annual IEEE Symposium on the Foundations of Computer Science (FOCS '06), pp. 249-260. IEEE Press, 2006

Physics

Quantum Physics

10 pages, preliminary version in FOCS'06

Scientific paper

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 (n-1)/2 (rounded down) cheaters among n players. Previous protocols for these tasks tolerated (n-1)/4 (rounded down) and (n-1)/6 (rounded down) 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 circuits.

Affiliated with

Also associated with

No associations

Rating

Secure Multiparty Quantum Computation with (Only) a Strict Honest Majority does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Secure Multiparty Quantum Computation with (Only) a Strict Honest Majority, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Secure Multiparty Quantum Computation with (Only) a Strict Honest Majority will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-436132