08/09/2006, 11:00 — 12:00 — Amphitheatre Va4, Civil Engineering Building
Michael Ben-Or, Hebrew University
Secure Multiparty Quantum Computation with (Only) a Strict Honest
Majority
Secret sharing and secure 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
cheaters among n players. Previous protocols for these tasks
tolerated (n-1)/4 and (n-1)/6 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. Joint work with Claude
Crepeau, Daniel Gottesman, Avinatan Hassidim and Adam Smith.
Please note exceptional time and place.