Maxwell Gold

An efficient paradigm for multi-party computation (MPC) are protocols structured around access to shared pre-processed computational resources. In this model, distributed correlations are initially disseminated to participants in some form of shared randomness. This allows for a phase of computation, thereafter, built on information theoretic broadcasting primitives with efficient round complexity. While privacy against a malicious adversary is trivial in this phase, the same information theoretic guarantees cannot be met when distributing shared randomness classically, without strong setup assumptions, such as a trusted Dealer and private channels. We present a novel approach for generating these correlations from entangled quantum graph states, and yield information theoretic privacy guarantees that hold against a malicious adversary, with limited assumptions. Our primary contribution is a tripartite resource state and measurement-based protocol for extracting a binary \textit{multiplication triple}, a special form of shared randomness that enables the private multiplication of a bit conjunction. Here, we employ a third party as a Referee, and demand only an honest pair among the three parties. The role of this Referee is weaker than that of a Dealer, as the Referee learns nothings about the underlying shared randomness that is disseminated. We prove perfect privacy for our protocol, assuming access to an ideal copy of the resource state, an assumption that is based on the existence of graph state verification protocols. Finally, we demonstrate its application as a primitive for more complex Boolean functionalities such as 1-out-of-2 oblivious transfer (OT) and MPC for an arbitrary $N$-party Boolean function, assuming access to the proper broadcasting channel.