|
Published Articles >> Table of Contents >> Abstract
47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06)
pp. 249-260
Secure Multiparty Quantum Computation with (Only) a Strict Honest Majority
Michael Ben-Or, The Hebrew University, Israel
Claude Crepeau, McGill University, Canada
Daniel Gottesman, Perimeter Institute for Theoretical Physics, Canada
Avinatan Hassidim, The Hebrew University, Israel
Adam Smith, Weizmann Institute of Science, Israel
Full Article Text:
 
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/FOCS.2006.68
Send link to a friend
| 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 \left[ {\frac{{n - 1}}
{2}} \right] cheaters among n players. Previous protocols for these
tasks tolerated \left[ {\frac{{n - 1}}
{4}} \right]
and \left[ {\frac{{n - 1}}
{6}} \right] 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 errorcorrecting
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 faulttolerant
quantum circuits.
|
 Additional Information
|
Citation:
Michael Ben-Or, Claude Crepeau, Daniel Gottesman, Avinatan Hassidim, Adam Smith,
"Secure Multiparty Quantum Computation with (Only) a Strict Honest Majority,"
focs,
pp. 249-260,
47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06),
2006
|
|
