The Hebrew University

Secret sharing and multiparty computation (also called “secure function evaluation”) are fundamental primitives in modern cryptography, allowing a group of mutually dis-trustful players to perform correct, distributed computa-tions 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 play-ers 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 com-putation (MPQC) protocol, which can tolerate any!n−12 " cheaters among n players. Previous protocols for these tasks tolerated!n−14 " and!n−16 " 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 er-rors than traditional, exact codes. We introduce new fami-lies of authentication schemes and approximate codes tai-lored to the needs of our protocols, as well as new state pu-rification techniques along the lines of those used in fault-tolerant quantum circuits.