Quantum multiplication triples

A relevant paradigm for multi-party computation (MPC) are those protocols which benefit from an input-independent offline phase. Here, resources in the form of distributed correlations are initially disseminated, allowing for a significant reduction in the communication complexity of the computation occurring in an online phase thereafter. We present a novel approach for generating these offline correlations with quantum graph states. Our primary contribution is a primitive for secret-sharing bit conjunctions, applicable for the evaluation of arbitrary N-party Boolean circuits. We work in an (N+1)-party setting, utilizing a non-colluding Referee, and demonstrate how input-independent measurements made on tripartite graph states generate the necessary offline correlations required to distribute shares of these bit conjunctions in a subsequent online phase, with communication overhead that scales similarly to the classical setting. This work opens a pathway towards the execution of N-party MPCs with information-theoretic security.