An efficient combination of quantum error correction and authentication

Yfke Dulek; Garazi Muguruza; Florian Speelman

doi:10.62056/ah2i5w7sf

An efficient combination of quantum error correction and authentication

Authors

Yfke Dulek, Garazi Muguruza, Florian Speelman

Yfke Dulek

CWI, Netherlands
QuSoft, Netherlands

Garazi Muguruza

University of Amsterdam, Netherlands
QuSoft, Netherlands
g dot muguruza at uva dot nl

Florian Speelman

University of Amsterdam, Netherlands
QuSoft, Netherlands
f dot speelman at uva dot nl

Keywords: quantum cryptography quantum authentication quantum error-correction trap code

Abstract

When sending quantum information over a channel, we want to ensure that the message remains intact. Quantum error correction and quantum authentication both aim to protect (quantum) information, but approach this task from two very different directions: error-correcting codes protect against probabilistic channel noise and are meant to be very robust against small errors, while authentication codes prevent adversarial attacks and are designed to be very sensitive against any error, including small ones.

In practice, when sending an authenticated state over a noisy channel, one would have to wrap it in an error-correcting code to counterbalance the sensitivity of the underlying authentication scheme. We study the question of whether this can be done more efficiently by combining the two functionalities in a single code. To illustrate the potential of such a combination, we design the threshold code, a modification of the trap authentication code which preserves that code's authentication properties, but which is naturally robust against depolarizing channel noise. We show that the threshold code needs polylogarithmically fewer qubits to achieve the same level of security and robustness, compared to the naive composition of the trap code with any concatenated CSS code. We believe our analysis opens the door to combining more general error-correction and authentication codes, which could improve the practicality of the resulting scheme.

References

[ABOE08]

Dorit Aharonov, Michael Ben-Or, and Elad Eban. Interactive Proofs For Quantum Computations. Preprint, 2008. DOI: https://arxiv.org/abs/0810.5375

Google Scholar ePrint

[ADSS17]

Gorjan Alagic, Yfke Dulek, Christian Schaffner, and Florian Speelman. Quantum Fully Homomorphic Encryption with Verification. In Tsuyoshi Takagi and Thomas Peyrin, editors, ASIACRYPT 2017, Part I, volume 10624 of LNCS, pages 438–467. December 2017. Springer, Cham. DOI: 10.1007/978-3-319-70694-8_16

Google Scholar ePrint

[AGM18]

Gorjan Alagic, Tommaso Gagliardoni, and Christian Majenz. Unforgeable Quantum Encryption. In Jesper Buus Nielsen and Vincent Rijmen, editors, EUROCRYPT 2018, Part III, volume 10822 of LNCS, pages 489–519. 2018. Springer, Cham. DOI: 10.1007/978-3-319-78372-7_16

Google Scholar ePrint

[AGM21]

Gorjan Alagic, Tommaso Gagliardoni, and Christian Majenz. Can you sign a quantum state?. Quantum, 5:603, 2021. DOI: 10.22331/q-2021-12-16-603

Google Scholar ePrint

[BCG⁺02]

H. Barnum, C. Crepeau, D. Gottesman, A. Smith, and A. Tapp. Authentication of quantum messages. In The 43rd Annual IEEE Symposium on Foundations of Computer Science, pages 449–458. 2002. DOI: 10.1109/SFCS.2002.1181969

Google Scholar ePrint

[BCG⁺06]

Michael Ben-Or, Claude Crépeau, Daniel Gottesman, Avinatan Hassidim, and Adam Smith. Secure Multiparty Quantum Computation with (Only) a Strict Honest Majority. In 47th FOCS, pages 249–260. October 2006. IEEE Computer Society Press. DOI: 10.1109/FOCS.2006.68

Google Scholar ePrint

[BGS13]

Anne Broadbent, Gus Gutoski, and Douglas Stebila. Quantum One-Time Programs - (Extended Abstract). In Ran Canetti and Juan A. Garay, editors, CRYPTO 2013, Part II, volume 8043 of LNCS, pages 344–360. August 2013. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-40084-1_20

Google Scholar ePrint

[BJSW16]

Anne Broadbent, Zhengfeng Ji, Fang Song, and John Watrous. Zero-Knowledge Proof Systems for QMA. In Irit Dinur, editor, 57th FOCS, pages 31–40. October 2016. IEEE Computer Society Press. DOI: 10.1109/FOCS.2016.13

Google Scholar ePrint

[BMPZ19]

Fabio Banfi, Ueli Maurer, Christopher Portmann, and Jiamin Zhu. Composable and Finite Computational Security of Quantum Message Transmission. In Dennis Hofheinz and Alon Rosen, editors, TCC 2019, Part I, volume 11891 of LNCS, pages 282–311. December 2019. Springer, Cham. DOI: 10.1007/978-3-030-36030-6_12

Google Scholar ePrint

[BW16]

Anne Broadbent and Evelyn Wainewright. Efficient Simulation for Quantum Message Authentication. In Anderson C. A. Nascimento and Paulo Barreto, editors, ICITS 16, volume 10015 of LNCS, pages 72–91. August 2016. Springer, Cham. DOI: 10.1007/978-3-319-49175-2_4

Google Scholar ePrint

[DGJ⁺20]

Yfke Dulek, Alex B. Grilo, Stacey Jeffery, Christian Majenz, and Christian Schaffner. Secure Multi-party Quantum Computation with a Dishonest Majority. In Anne Canteaut and Yuval Ishai, editors, EUROCRYPT 2020, Part III, volume 12107 of LNCS, pages 729–758. May 2020. Springer, Cham. DOI: 10.1007/978-3-030-45727-3_25

Google Scholar ePrint

[DNS10]

Frédéric Dupuis, Jesper Buus Nielsen, and Louis Salvail. Secure Two-Party Quantum Evaluation of Unitaries against Specious Adversaries. In Tal Rabin, editor, CRYPTO 2010, volume 6223 of LNCS, pages 685–706. August 2010. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-14623-7_37

Google Scholar ePrint

[DNS12]

Frédéric Dupuis, Jesper Buus Nielsen, and Louis Salvail. Actively Secure Two-Party Evaluation of Any Quantum Operation. In Reihaneh Safavi-Naini and Ran Canetti, editors, CRYPTO 2012, volume 7417 of LNCS, pages 794–811. August 2012. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-32009-5_46

Google Scholar ePrint

[DS18]

Yfke Dulek and Florian Speelman. Quantum ciphertext authentication and key recycling with the trap code. In 13th Conference on the Theory of Quantum Computation, Communication and Cryptography, pages 1:1–1:17. 2018. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. DOI: 10.4230/LIPIcs.TQC.2018.1

Google Scholar ePrint

[GH01]

Andrew V. Goldberg and Jason D. Hartline. Competitive Auctions for Multiple Digital Goods. In European Symposium on Algorithms, pages 416–427. 2001. Springer Berlin Heidelberg. DOI: 10.1007/3-540-44676-1_35

Google Scholar ePrint

[Got96]

Daniel Gottesman. Class of quantum error-correcting codes saturating the quantum Hamming bound. Phys. Rev. A, 54:1862–1868, 1996. DOI: 10.1103/PhysRevA.54.1862

Google Scholar ePrint

[GYZ17]

Sumegha Garg, Henry Yuen, and Mark Zhandry. New Security Notions and Feasibility Results for Authentication of Quantum Data. In Jonathan Katz and Hovav Shacham, editors, CRYPTO 2017, Part II, volume 10402 of LNCS, pages 342–371. August 2017. Springer, Cham. DOI: 10.1007/978-3-319-63715-0_12

Google Scholar ePrint

[HLM16]

Patrick Hayden, Debbie W. Leung, and Dominic Mayers. The Universal Composable Security of Quantum Message Authentication with Key Recyling. Preprint, 2016. DOI: https://arxiv.org/abs/1610.09434

Google Scholar ePrint

[Mau12]

Ueli Maurer. Constructive Cryptography – A New Paradigm for Security Definitions and Proofs. In Theory of Security and Applications, pages 33–56. 2012. Springer Berlin Heidelberg. DOI: 10.1007/978-3-642-27375-9

Google Scholar ePrint

[MR11]

Ueli Maurer and Renato Renner. Abstract Cryptography. In The Second Symposium on Innovations in Computer Science, pages 1–21. 2011. Tsinghua University Press. DOI: 10.1007/978-3-642-27375-9_3

Google Scholar ePrint

[NC10]

Michael A. Nielsen and Isaac L. Chuang. Quantum computation and quantum information. Cambridge University Press, Cambridge, New York, 10th anniversary ed edition. 2010. DOI: 10.1119/1.1463744

Google Scholar ePrint

[Por17]

Christopher Portmann. Quantum Authentication with Key Recycling. In Jean-Sébastien Coron and Jesper Buus Nielsen, editors, EUROCRYPT 2017, Part III, volume 10212 of LNCS, pages 339–368. 2017. Springer, Cham. DOI: 10.1007/978-3-319-56617-7_12

Google Scholar ePrint

[Pre99]

John Preskill. Lecture notes for Physics 219: Quantum computation. Caltech Lecture Notes, 1999.

Google Scholar ePrint

[Ter15]

Barbara M. Terhal. Quantum Error Correction for Quantum Memories. Reviews of Modern Physics, 87(2):307–346, 2015. DOI: 10.1103/RevModPhys.87.307

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/ah2i5w7sf

History

Submitted: 2024-10-09
Accepted: 2024-12-03
Published: 2025-01-13

How to cite

Yfke Dulek, Garazi Muguruza, and Florian Speelman, An efficient combination of quantum error correction and authentication. IACR Communications in Cryptology, vol. 1, no. 4, Jan 13, 2025, doi: 10.62056/ah2i5w7sf.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.

@article{CiC-1-4-35,
    author = "Dulek, Yfke and Muguruza, Garazi and Speelman, Florian",
    journal = "{IACR} {C}ommunications in {C}ryptology",
    publisher = "{I}nternational {A}ssociation for {C}ryptologic {R}esearch",
    title = "An efficient combination of quantum error correction and authentication",
    volume = "1",
    number = "4",
    date = "2025-01-13",
    year = "2025",
    issn = "3006-5496",
    doi = "10.62056/ah2i5w7sf"
}

TY - JOUR
AU - Dulek, Yfke
AU - Muguruza, Garazi
AU - Speelman, Florian
PY  - 2025
TI  - An efficient combination of quantum error correction and authentication
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 1
IS  - 4
DO  - 10.62056/ah2i5w7sf
UR  - https://doi.org/10.62056/ah2i5w7sf
AB  - <p>  When sending quantum information over a channel, we want to ensure that the message remains intact. Quantum error correction and quantum authentication both aim to protect (quantum) information, but approach this task from two very different directions: error-correcting codes protect against probabilistic channel noise and are meant to be very robust against small errors, while authentication codes prevent adversarial attacks and are designed to be very sensitive against any error, including small ones.</p><p>  In practice, when sending an authenticated state over a noisy channel, one would have to wrap it in an error-correcting code to counterbalance the sensitivity of the underlying authentication scheme. We study the question of whether this can be done more efficiently by combining the two functionalities in a single code. To illustrate the potential of such a combination, we design the threshold code, a modification of the trap authentication code which preserves that code's authentication properties, but which is naturally robust against depolarizing channel noise. We show that the threshold code needs polylogarithmically fewer qubits to achieve the same level of security and robustness, compared to the naive composition of the trap code with any concatenated CSS code. We believe our analysis opens the door to combining more general error-correction and authentication codes, which could improve the practicality of the resulting scheme. </p>
ER  -

Yfke Dulek, Garazi Muguruza, and Florian Speelman, An efficient combination of quantum error correction and authentication. IACR Communications in Cryptology, vol. 1, no. 4, Jan 13, 2025, doi: 10.62056/ah2i5w7sf.