Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2402.01445

All graph state verification protocols are composably secure

Léo Colisson, Damian Markham, Raja Yehia

Published Feb 2, 2024• 2 citations
arXivHTMLPDF

Abstract

Graph state verification protocols allow multiple parties to share a graph state while checking that the state is honestly prepared, even in the presence of malicious parties. Since graph states are the starting point of numerous quantum protocols, it is crucial to ensure that graph state verification protocols can safely be composed with other protocols, this property being known as composable security. Previous works [YDK21] conjectured that such a property could not be proven within the abstract cryptography framework: we disprove this conjecture by showing that all graph state verification protocols can be turned into a composably secure protocol with respect to the natural functionality for graph state preparation. Moreover, we show that any unchanged graph state verification protocols can also be considered as composably secure for a slightly different, yet useful, functionality. Finally, we show that these two results are optimal, in the sense that any such generic result, considering arbitrary black-box protocols, must either modify the protocol or consider a different functionality. Along the way, we show a protocol to generalize entanglement swapping to arbitrary graph states that might be of independent interest.

DOI
10.48550/arxiv.2402.01445

Related papers

Verification of graph states in an untrusted network

Anupama Unnikrishnan, Damian Markham

Graph states are a large class of multipartite entangled quantum states that form the basis of schemes for quantum computation, communication, error correction, metrology, and more. In this work, we consider verification of graph states generated by an untrusted source and shared between a network of possibly dishonest parties. This has implications in certifying the application of graph states for various distributed tasks. We present a protocol which is globally efficient for a large family of useful graph states, including cluster states, GHZ states, cycle graph states, and more. For general graph states, efficiency with respect to the security parameter is maintained, though there is a cost increase with the size of the graph state. The protocols are practical, requiring only multiple copies of the graph state, local measurements, and classical communication.

arXiv:2007.13126•Physical Review A•May 13, 2022•15 citations

Composable security for multipartite entanglement verification

Raja Yehia, Eleni Diamanti, Iordanis Kerenidis

The authors present a composably secure protocol allowing $n$ parties to test an entanglement generation resource controlled by a possibly dishonest party. The test requires only local quantum operations and authenticated classical communication once a state is shared among them. The composability ensures that the protocol can be used multiple times in a row or as a subroutine in any bigger protocol without threatening the overall security.

arXiv:2004.07679•Physical Review A•May 19, 2021•6 citations

Why quantum state verification cannot be both efficient and secure: a categorical approach

Fabian Wiesner, Ziad Chaoui, Diana Kessler +2 more

The advantage of quantum protocols lies in the inherent properties of the shared quantum states. These states are sometimes provided by sources that are not trusted, and therefore need to be verified. Finding secure and efficient quantum state verification protocols remains a big challenge, and recent works illustrate trade-offs between efficiency and security for different groups of states in restricted settings. However, whether a universal trade-off exists for all quantum states and all verification strategies remains unknown. In this work, we instantiate the categorical composable cryptography framework to show a fundamental limit for quantum state verification for all cut-and-choose approaches used to verify arbitrary quantum states. Our findings show that the prevailing cut-and-choose techniques cannot lead to quantum state verification protocols that are both efficient and secure.

arXiv:2411.04767•Nov 7, 2024•0 citations

Quantum Secure Multi-Party Summation with Graph State

Yaohua Lu, Gangyi Ding

Quantum secure multi-party summation (QSMS) is a fundamental problem in quantum secure multi-party computation (QSMC), wherein multiple parties compute the sum of their data without revealing them. This paper proposes a novel QSMS protocol based on graph state, which offers enhanced security, usability, and flexibility compared to existing methods. The protocol leverages the structural advantages of graph state and employs random graph state structures and random encryption gate operations to provide stronger security. Additionally, the stabilizer of the graph state is utilized to detect eavesdroppers and channel noise without the need for decoy bits. The protocol allows for the arbitrary addition and deletion of participants, enabling greater flexibility. Experimental verification is conducted to demonstrate the security, effectiveness, and practicality of the proposed protocols. The correctness and security of the protocols are formally proven. The QSMS method based on graph state introduces new opportunities for QSMC. It highlights the potential of leveraging quantum graph state technology to securely and efficiently solve various multi-party computation problems.

Entropy•Jan 17, 2024•11 citations

Committed MPC

Tore Kasper Frederiksen, Benny Pinkas B, Avishay Yanai

We present a new multiparty computation protocol secure against a static and malicious dishonest majority. Unlike most previous protocols that were based on working on MAC-ed secret shares, our approach is based on computations on homomorphic commitments to secret shares. Specifically we show how to realize MPC using any additively-homomorphic commitment scheme, even if such a scheme is an interactive two-party protocol. Our new approach enables us to do arithmetic computation over arbitrary finite fields. In addition, since our protocol computes over committed values, it can be readily composed within larger protocols, and can also be used for efficiently implementing committing OT or committed OT. This is done in two steps, each of independent interest: Black-box extension of any (possibly interactive) two-party additively homomorphic commitment scheme to an additively homomorphic multiparty commitment scheme, only using coin-tossing and a “weak” equality evaluation functionality. Realizing multiplication of multiparty commitments based on a lightweight preprocessing approach. Finally we show how to use the fully homomorphic commitments to compute any functionality securely in the presence of a malicious adversary corrupting any number of parties.

Lecture notes in computer science•Jan 1, 2018•22 citations

Round-Efficient Black-Box Construction of Composable Multi-Party Computation.

Susumu Kiyoshima

We present a round-efficient black-box construction of a general multi-party computation (MPC) protocol that satisfies composability in the plain model. The security of our protocol is proven in the angel-based UC framework [Prabhakaran and Sahai, STOC’04] under the minimal assumption of the existence of semi-honest oblivious transfer protocols. The round complexity of our protocol is $$\max (\widetilde{O}(\log ^2n), O(R_{{{{\mathsf {O}}}{{\mathsf {T}}}}}))$$ when the round complexity of the underlying oblivious transfer protocol is $$R_{{{{\mathsf {O}}}{{\mathsf {T}}}}}$$ . Since constant-round semi-honest oblivious transfer protocols can be constructed under standard assumptions (such as the existence of enhanced trapdoor permutations), our result gives a $$\widetilde{O}(\log ^2n)$$ -round protocol under these assumptions. Previously, only an $$O(\max (n^{\epsilon }, R_{{{{\mathsf {O}}}{{\mathsf {T}}}}}))$$ -round protocol was shown, where $$\epsilon >0$$ is an arbitrary constant. We obtain our MPC protocol by constructing a $$\widetilde{O}(\log ^2n)$$ -round CCA-secure commitment scheme in a black-box way under the assumption of the existence of one-way functions.

•Jan 1, 2014•0 citations
Graph state verification protocols allow multiple parties to share a graph state while checking that the state is honestly prepared, even in the presence of malicious parties. Since graph states are the starting point of numerous quantum protocols, it is crucial to ensure that graph state verification protocols can safely be composed with other protocols, this property being known as composable security. Previous works [YDK21] conjectured that such a property could not be proven within the abstract cryptography framework: we disprove this conjecture by showing that all graph state verification protocols can be turned into a composably secure protocol with respect to the natural functionality for graph state preparation. Moreover, we show that any unchanged graph state verification protocols can also be considered as composably secure for a slightly different, yet useful, functionality. Finally, we show that these two results are optimal, in the sense that any such generic result, considering arbitrary black-box protocols, must either modify the protocol or consider a different functionality. Along the way, we show a protocol to generalize entanglement swapping to arbitrary graph states that might be of independent interest.
Graph states are a large class of multipartite entangled quantum states that form the basis of schemes for quantum computation, communication, error correction, metrology, and more. In this work, we consider verification of graph states generated by an untrusted source and shared between a network of possibly dishonest parties. This has implications in certifying the application of graph states for various distributed tasks. We present a protocol which is globally efficient for a large family of useful graph states, including cluster states, GHZ states, cycle graph states, and more. For general graph states, efficiency with respect to the security parameter is maintained, though there is a cost increase with the size of the graph state. The protocols are practical, requiring only multiple copies of the graph state, local measurements, and classical communication.
The authors present a composably secure protocol allowing nnn parties to test an entanglement generation resource controlled by a possibly dishonest party. The test requires only local quantum operations and authenticated classical communication once a state is shared among them. The composability ensures that the protocol can be used multiple times in a row or as a subroutine in any bigger protocol without threatening the overall security.
The advantage of quantum protocols lies in the inherent properties of the shared quantum states. These states are sometimes provided by sources that are not trusted, and therefore need to be verified. Finding secure and efficient quantum state verification protocols remains a big challenge, and recent works illustrate trade-offs between efficiency and security for different groups of states in restricted settings. However, whether a universal trade-off exists for all quantum states and all verification strategies remains unknown. In this work, we instantiate the categorical composable cryptography framework to show a fundamental limit for quantum state verification for all cut-and-choose approaches used to verify arbitrary quantum states. Our findings show that the prevailing cut-and-choose techniques cannot lead to quantum state verification protocols that are both efficient and secure.
Quantum secure multi-party summation (QSMS) is a fundamental problem in quantum secure multi-party computation (QSMC), wherein multiple parties compute the sum of their data without revealing them. This paper proposes a novel QSMS protocol based on graph state, which offers enhanced security, usability, and flexibility compared to existing methods. The protocol leverages the structural advantages of graph state and employs random graph state structures and random encryption gate operations to provide stronger security. Additionally, the stabilizer of the graph state is utilized to detect eavesdroppers and channel noise without the need for decoy bits. The protocol allows for the arbitrary addition and deletion of participants, enabling greater flexibility. Experimental verification is conducted to demonstrate the security, effectiveness, and practicality of the proposed protocols. The correctness and security of the protocols are formally proven. The QSMS method based on graph state introduces new opportunities for QSMC. It highlights the potential of leveraging quantum graph state technology to securely and efficiently solve various multi-party computation problems.
We present a new multiparty computation protocol secure against a static and malicious dishonest majority. Unlike most previous protocols that were based on working on MAC-ed secret shares, our approach is based on computations on homomorphic commitments to secret shares. Specifically we show how to realize MPC using any additively-homomorphic commitment scheme, even if such a scheme is an interactive two-party protocol. Our new approach enables us to do arithmetic computation over arbitrary finite fields. In addition, since our protocol computes over committed values, it can be readily composed within larger protocols, and can also be used for efficiently implementing committing OT or committed OT. This is done in two steps, each of independent interest: Black-box extension of any (possibly interactive) two-party additively homomorphic commitment scheme to an additively homomorphic multiparty commitment scheme, only using coin-tossing and a “weak” equality evaluation functionality. Realizing multiplication of multiparty commitments based on a lightweight preprocessing approach. Finally we show how to use the fully homomorphic commitments to compute any functionality securely in the presence of a malicious adversary corrupting any number of parties.
We present a round-efficient black-box construction of a general multi-party computation (MPC) protocol that satisfies composability in the plain model. The security of our protocol is proven in the angel-based UC framework [Prabhakaran and Sahai, STOC’04] under the minimal assumption of the existence of semi-honest oblivious transfer protocols. The round complexity of our protocol is max⁡(O~(log⁡2n),O(ROT))\max (\widetilde{O}(\log ^2n), O(R_{{{{\mathsf {O}}}{{\mathsf {T}}}}}))max(O(log2n),O(ROT​)) when the round complexity of the underlying oblivious transfer protocol is ROTR_{{{{\mathsf {O}}}{{\mathsf {T}}}}}ROT​ . Since constant-round semi-honest oblivious transfer protocols can be constructed under standard assumptions (such as the existence of enhanced trapdoor permutations), our result gives a O~(log⁡2n)\widetilde{O}(\log ^2n)O(log2n) -round protocol under these assumptions. Previously, only an O(max⁡(nϵ,ROT))O(\max (n^{\epsilon }, R_{{{{\mathsf {O}}}{{\mathsf {T}}}}}))O(max(nϵ,ROT​)) -round protocol was shown, where ϵ>0\epsilon >0ϵ>0 is an arbitrary constant. We obtain our MPC protocol by constructing a O~(log⁡2n)\widetilde{O}(\log ^2n)O(log2n) -round CCA-secure commitment scheme in a black-box way under the assumption of the existence of one-way functions.