Multiplication triples from entangled quantum resources

Maxwell Gold, Eric Chitambar · 2025

Read Multiplication triples from entangled quantum resources by Maxwell Gold, Eric Chitambar (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-10385.txt.

Introduction

Maxwell Gold and Eric Chitambar show how entangled quantum states can mint shared secrets for secure group computing, in a 2025 paper. Secure multi-party protocols often start from pre-shared random patterns, such as multiplication triples. Making those patterns today needs a trusted dealer or private lines. The pair replace the dealer with a referee who learns nothing, plus a shared entangled graph state that can be checked for honesty.

Their protocol pulls one binary multiplication triple out of the quantum resource. Privacy is perfect against a cheating party, as long as one pair among the three stays honest. The triple then serves as a brick for stronger tools, such as oblivious transfer and general group computing. The authors frame quantum links as a cleaner source of trust for secure computing.

Catalog record

CREATORMaxwell Gold, Eric Chitambar
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE74 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-10385

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Multiplication triples from entangled quantum resources Maxwell Gold, Eric Chitambar Abstract An efficient paradigm for multi-party computation (MPC) are protocols structured around access to shared pre-processed computational resources. In this model, certain forms of correlated randomness are distributed to the participants prior to their computation. The shared randomness is then consumed in a computation phase that involves public communication with efficient round complexity, and the computation is secure in this second phase provided the initial correlations were distributed securely. Usually the latter requires some 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 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 nothing 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 N -party Boolean function, assuming access to the proper broadcasting channel. 1 Introduction The problem of distributed computation within the pre-processing model [ BDOZ11 , DPSZ12 ] , offers a powerful methodology for constructing information theoretic (or provable) malicious-secure MPC. On the assumption of access to private shared randomness , the private evaluation of an arbitrary function, f , can be built entirely from information theoretic broadcasting primitives, referred to as openings , where parties announce padded information. The trick in computing f with correctness lies in how the parties’ randomness is correlated, such that from their openings the parties can locally reconstruct f . It is straightforward to prove security in this model, in the sense that a malicious adversary (one who deviates arbitrarily from the protocol) can only learn anything about an honest party’s input from their local reconstruction of f [ Bea92 ] . This all hinges upon the assumption of access to such forms of correlated randomness, however, where it is known to be impossible to disseminate these resources in a purely classical setting without resorting to strong information theoretic assumptions, such as a trusted Dealer that does not know f and private peer-to-peer channels, or unproven hardness assumptions [ IL89 ] . In this work we tackle the problem of disseminating multiplication triples from entangled quantum resources. A multiplication triple is unique form of shared randomness that enables private multiplication of party inputs in this model. With quantum resources, we achieve information theoretic malicious-secure privacy based on assumptions much weaker than a trusted Dealer. In this paper, we formally define the problem of quantum triple distribution (QTD), which similar to its namesake, works to instantiate a functionality for triple distribution (TD), and present an instantiating protocol that utilizes entangled resources to extract such a correlation. We work in a three-party computation (3PC) setting, utilizing a non-collaborating Referee ( \mathbf{R} ) to assist a pair, Alice ( \mathbf{A} ) and Bob ( \mathbf{B} ), in a protocol for disseminating binary multiplication triples. To this end, we introduce a particular tripartite quantum resource, represented as a graph state, \ket{G_{\wedge}} , from which a triple can be extracted through local measurements made by the parties. We show that so long as any pair among \{\mathbf{A},\mathbf{B},\mathbf{R}\} act honestly, a private binary multiplication triple can be extracted without communication, from the resource state we introduce. In order to efficiently prove the privacy offered by our resource state we assume an ideal quantum resource is distributed to each party when executing our protocol. The appeal is that there are protocols for distributing graph states with an information theoretic certificate of authenticity [ McK14 , Bac+20 , MK20 ] . In particular, there exist resource efficient graph state verification protocols, which have been shown to handle malicious networks of players [ UM22 ] , and support composable security definitions on their own [ CMY24 ] . This lets us assume access to an ideal functionality \mathcal{F}_{\ket{G_{\wedge}}} that distributes the resource state, when proving the security of our protocol. A feature in utilizing quantum resources for cryptography is in there ability to encode classical shared randomness. Their known advantage arises from how the no-cloning theorem enables some level of cheat-sensitivity when transmitting information through quantum channels. The canonical example of quantum key distribution (QKD) allows parties to tackle the classical problem of key distribution (KD), and establish shared bipartite secret key in a way that is statistically resilient against an active eavesdropper [ BB84 , Eke91 ] , and composable in any cryptographic system [ Ben+05 ] . By utilizing such resources for provable secure TD, a protocol for QTD removes several assumptions typical of classical analogs. Namely, there is no need for a trusted Dealer who does not know f , and no assumptions on private channels are necessary. Hence, instantiating a protocol for QTD, along with the proper ideal broadcast channel, allows a group to tackle the problem of secure function evaluation from start to finish with information-theoretic malicious-secure privacy guarantees, where assumptions come in from three distinct sources: • The various assumptions tied to the certification of the resource states. • The assumption of at least an honest pair acting on each tripartite resource. • The assumption of an ideal broadcasting channel for the online phase. The advantage that quantum resource provide in this problem comes from the combined assumptions from the first two bullets, which make up the necessary requirements to build an offline phase from QTD. In this paper, we provide a solution for the second bullet. Furthermore, despite requiring an honest majority when strictly working in a 3PC setting, by further forcing the Referee be honest in our protocol, an (N+1) -party setting (not counting the Referee against N ) can achieve privacy against a malicious majority, given N>3 , from only QTD and an ideal broadcast channel. 1.1 Related work In [ GLCG25 ] , we presented a version of our primitive embedded in a larger 3PC protocol that allowed for the evaluation of a limited class of Boolean functions that only admit quadratic bit conjunctions. While this was sufficient for privately computing any function taking inputs from only two parties, we show here how this can be extended to any multiparty function. Furthermore, the primitive itself has been retooled, such that it directly yields a binary multiplication triple, from non-interactive input-independent quantum measurements made on an ideal resource state. To the best of our knowledge there is little existing work regarding protocols that focus on efficiently disseminating multiplication triples from entangled quantum states. In [ RKFW21 ] , it was shown how entanglement can be used to construct shared tables

Read the complete text