Hybrid Quantum Cryptography from Communication Complexity

Francesco Mazzoncini; Balthazar Bauer; Peter Brown; Romain Alléaume

doi:10.22331/q-2025-09-24-1862

Hybrid Quantum Cryptography from Communication Complexity

Francesco Mazzoncini^1,2, Balthazar Bauer³, Peter Brown¹, and Romain Alléaume¹

¹Télécom Paris-LTCI, Institut Polytechnique de Paris, 19 Place Marguerite Perey, 91120 Palaiseau, France
²Orange Innovation, Orange Gardens, 44 avenue de la République, Châtillon, France
³LMV, Université de Versailles – Saint-Quentin-en-Yvelines, 55 Avenue de Paris, 78646 Versailles, France

Published:	2025-09-24, volume 9, page 1862
Editor:	Máté Farkas
Eprint:	arXiv:2311.09164v3
Doi:	https://doi.org/10.22331/q-2025-09-24-1862
Citation:	Quantum 9, 1862 (2025).

Find this paper interesting or want to discuss? Scite or leave a comment on SciRate.

Abstract

We introduce an explicit construction for a key distribution protocol in the Quantum Computational Timelock (QCT) security model, where one assumes that computationally secure encryption may only be broken after a time much longer than the coherence time of available quantum memories.
Taking advantage of the QCT assumptions, we build a key distribution protocol called HM-QCT from the Hidden Matching problem for which there exists an exponential gap in one-way communication complexity between classical and quantum strategies.
We establish that the security of HM-QCT against arbitrary i.i.d. attacks can be reduced to the difficulty of solving the underlying Hidden Matching problem with classical information. Legitimate users, on the other hand, can use quantum communication, which gives them the possibility of sending multiple copies of the same quantum state while retaining an information advantage. This leads to an everlasting secure key distribution scheme over $n$ bosonic modes. Such a level of security is unattainable with purely classical techniques. Remarkably, the scheme remains secure with up to $\mathcal{O}\big( \frac{\sqrt{n}}{\log(n)}\big)$ input photons for each channel use, extending the functionalities and potentially outperforming QKD rates by several orders of magnitudes.

► BibTeX data

@article{Mazzoncini2025hybridquantum,
  doi = {10.22331/q-2025-09-24-1862},
  url = {https://doi.org/10.22331/q-2025-09-24-1862},
  title = {Hybrid {Q}uantum {C}ryptography from {C}ommunication {C}omplexity},
  author = {Mazzoncini, Francesco and Bauer, Balthazar and Brown, Peter and All{\'{e}}aume, Romain},
  journal = {{Quantum}},
  issn = {2521-327X},
  publisher = {{Verein zur F{\"{o}}rderung des Open Access Publizierens in den Quantenwissenschaften}},
  volume = {9},
  pages = {1862},
  month = sep,
  year = {2025}
}

► References

[1] Charles H. Bennett and Gilles Brassard. ``Quantum cryptography: Public key distribution and coin tossing''. Theoretical Computer Science 560, 7–11 (2014).
https://doi.org/10.1016/j.tcs.2014.05.025

[2] Stefano Pirandola, Riccardo Laurenza, Carlo Ottaviani, and Leonardo Banchi. ``Fundamental limits of repeaterless quantum communications''. Nature Communications 8, 15043 (2017).
https://doi.org/10.1038/ncomms15043

[3] Dominique Unruh. ``Everlasting Multi-party Computation''. In Ran Canetti and Juan A. Garay, editors, Advances in Cryptology – CRYPTO 2013. Pages 380–397. Lecture Notes in Computer ScienceBerlin, Heidelberg (2013). Springer.
https://doi.org/10.1007/978-3-642-40084-1_22

[4] Dmitry Gavinsky, Julia Kempe, Iordanis Kerenidis, Ran Raz, and Ronald de Wolf. ``Exponential separations for one-way quantum communication complexity, with applications to cryptography''. In Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing. Pages 516–525. STOC '07New York, NY, USA (2007). Association for Computing Machinery.
https://doi.org/10.1145/1250790.1250866

[5] Ziv Bar-Yossef, T.s Jayram, and Iordanis Kerenidis. ``Exponential separation of quantum and classical one-way communication complexity''. In Electronic Colloquium on Computational Complexity (ECCC). Pages 128–137. (2004).
https://doi.org/10.1145/1007352.1007379

[6] Nilesh Vyas and Romain Alleaume. ``Everlasting Secure Key Agreement with performance beyond QKD in a Quantum Computational Hybrid security model'' (2020). arXiv:2004.10173.
arXiv:2004.10173

[7] John Watrous. ``The Theory of Quantum Information''. Cambridge University Press. (2018). 1 edition.
https://doi.org/10.1017/9781316848142

[8] Khabat Heshami, Duncan G. England, Peter C. Humphreys, Philip J. Bustard, Victor M. Acosta, Joshua Nunn, and Benjamin J. Sussman. ``Quantum memories: Emerging applications and recent advances''. Journal of Modern Optics 63, 2005–2028 (2016).
https://doi.org/10.1080/09500340.2016.1148212

[9] Craig Gidney and Martin Ekerå. ``How to factor 2048 bit RSA integers in 8 hours using 20 million noisy qubits''. Quantum 5, 433 (2021).
https://doi.org/10.22331/q-2021-04-15-433

[10] Gláucia Murta, Federico Grasselli, Hermann Kampermann, and Dagmar Bruß. ``Quantum Conference Key Agreement: A Review''. Advanced Quantum Technologies 3, 2000025 (2020).
https://doi.org/10.1002/qute.202000025

[11] Mark Braverman and Anup Rao. ``Information Equals Amortized Communication'' (2011). arXiv:1106.3595.
arXiv:1106.3595

[12] Andrew Chi-Chih Yao. ``Some complexity questions related to distributive computing(Preliminary Report)''. In Proceedings of the Eleventh Annual ACM Symposium on Theory of Computing. Pages 209–213. STOC '79New York, NY, USA (1979). Association for Computing Machinery.
https://doi.org/10.1145/800135.804414

[13] Niraj Kumar, Iordanis Kerenidis, and Eleni Diamanti. ``Experimental demonstration of quantum advantage for one-way communication complexity surpassing best-known classical protocol''. Nature Communications 10, 4152 (2019).
https://doi.org/10.1038/s41467-019-12139-z

[14] Niraj Kumar. ``Practically Feasible Robust Quantum Money with Classical Verification''. Cryptography 3, 26 (2019).
https://doi.org/10.3390/cryptography3040026

[15] Ivan B. Damgård, Serge Fehr, Renato Renner, Louis Salvail, and Christian Schaffner. ``A Tight High-Order Entropic Quantum Uncertainty Relation with Applications''. In Alfred Menezes, editor, Advances in Cryptology - CRYPTO 2007. Pages 360–378. Lecture Notes in Computer ScienceBerlin, Heidelberg (2007). Springer.
https://doi.org/10.1007/978-3-540-74143-5_20

[16] Daniele Cozzolino, Beatrice Da Lio, Davide Bacco, and Leif Katsuo Oxenløwe. ``High-Dimensional Quantum Communication: Benefits, Progress, and Future Challenges''. Advanced Quantum Technologies 2, 1900038 (2019).
https://doi.org/10.1002/qute.201900038

[17] Cosmo Lupo and Seth Lloyd. ``Quantum-Locked Key Distribution at Nearly the Classical Capacity Rate''. Physical Review Letters 113, 160502 (2014).
https://doi.org/10.1103/PhysRevLett.113.160502

[18] Daniel J. Lum, John C. Howell, M. S. Allman, Thomas Gerrits, Varun B. Verma, Sae Woo Nam, Cosmo Lupo, and Seth Lloyd. ``Quantum enigma machine: Experimentally demonstrating quantum data locking''. Physical Review A 94, 022315 (2016).
https://doi.org/10.1103/PhysRevA.94.022315

[19] Cosmo Lupo and Seth Lloyd. ``Continuous-variable quantum enigma machines for long-distance key distribution''. Physical Review A 92, 062312 (2015).
https://doi.org/10.1103/PhysRevA.92.062312

[20] Stephanie Wehner, Christian Schaffner, and Barbara Terhal. ``Cryptography from Noisy Storage''. Physical Review Letters 100, 220502 (2008). arXiv:0711.2895.
https://doi.org/10.1103/PhysRevLett.100.220502
arXiv:0711.2895

[21] Robert Koenig, Stephanie Wehner, and Juerg Wullschleger. ``Unconditional security from noisy quantum storage''. IEEE Transactions on Information Theory 58, 1962–1984 (2012). arXiv:0906.1030.
https://doi.org/10.1109/TIT.2011.2177772
arXiv:0906.1030

[22] Manuel B. Santos, Paulo Mateus, and Armando N. Pinto. ``Quantum oblivious transfer: A short review''. Entropy 24, 945 (2022). arXiv:2206.03313.
https://doi.org/10.3390/e24070945
arXiv:2206.03313

[23] Álvaro J. Almeida, Ricardo Loura, Nikola Paunković, Nuno A. Silva, Nelson J. Muga, Paulo Mateus, Paulo S. André, and Armando N. Pinto. ``A brief review on quantum bit commitment''. In Second International Conference on Applications of Optics and Photonics. Volume 9286, pages 189–196. SPIE (2014).
https://doi.org/10.1117/12.2063733

[24] Hoi-Kwong Lo and H. F. Chau. ``Why quantum bit commitment and ideal quantum coin tossing are impossible''. Physica D: Nonlinear Phenomena 120, 177–187 (1998).
https://doi.org/10.1016/S0167-2789(98)00053-0

[25] Harry Buhrman, Matthias Christandl, and Christian Schaffner. ``Complete Insecurity of Quantum Protocols for Classical Two-Party Computation''. Physical Review Letters 109, 160501 (2012).
https://doi.org/10.1103/PhysRevLett.109.160501

[26] Nelly Huei Ying Ng, Siddarth K. Joshi, Chia Chen Ming, Christian Kurtsiefer, and Stephanie Wehner. ``Experimental implementation of bit commitment in the noisy-storage model''. Nature Communications 3, 1326 (2012).
https://doi.org/10.1038/ncomms2268

[27] C. Erven, N. Ng, N. Gigov, R. Laflamme, S. Wehner, and G. Weihs. ``An experimental implementation of oblivious transfer in the noisy storage model''. Nature Communications 5, 3418 (2014).
https://doi.org/10.1038/ncomms4418

[28] Fabian Furrer, Tobias Gehring, Christian Schaffner, Christoph Pacher, Roman Schnabel, and Stephanie Wehner. ``Continuous-variable protocol for oblivious transfer in the noisy-storage model''. Nature Communications 9, 1450 (2018).
https://doi.org/10.1038/s41467-018-03729-4

[29] Prahladh Harsha, Rahul Jain, David McAllester, and Jaikumar Radhakrishnan. ``The Communication Complexity of Correlation''. IEEE Transactions on Information Theory 56, 438–449 (2010).
https://doi.org/10.1109/TIT.2009.2034824

[30] Anup Rao and Amir Yehudayoff. ``Communication Complexity: And Applications''. Cambridge University Press. Cambridge (2020).
https://doi.org/10.1017/9781108671644

[31] Cosmo Lupo. ``Quantum Data Locking for Secure Communication against an Eavesdropper with Time-Limited Storage''. Entropy 17, 3194–3204 (2015).
https://doi.org/10.3390/e17053194

[32] Jonathan Katz and Yehuda Lindell. ``Introduction to Modern Cryptography''. Chapman & Hall/CRC. (2014). 2 edition.
https://doi.org/10.5555/2700550

[33] Renato Renner. ``Security of quantum key distribution''. International Journal of Quantum Information 06, 1–127 (2008).
https://doi.org/10.1142/S0219749908003256

[34] Gilles Brassard and Louis Salvail. ``Secret-Key Reconciliation by Public Discussion''. In Tor Helleseth, editor, Advances in Cryptology — EUROCRYPT '93. Pages 410–423. Lecture Notes in Computer ScienceBerlin, Heidelberg (1994). Springer.
https://doi.org/10.1007/3-540-48285-7_35

[35] C. H. Bennett, G. Brassard, C. Crépeau, and U. Maurer. ``Generalized privacy amplification''. IEEE Trans. Inf. Theory (1995).
https://doi.org/10.1109/18.476316

[36] Norbert Lütkenhaus and Mika Jahma. ``Quantum key distribution with realistic states: Photon-number statistics in the photon-number splitting attack''. New Journal of Physics 4, 44 (2002).
https://doi.org/10.1088/1367-2630/4/1/344

[37] Igor Devetak and Andreas Winter. ``Devetak, I. & Winter, A. Distillation of secret key and entanglement from quantum states. Proc. R. Soc. Lond. A 461, 207-235''. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences 461 (2003).
https://doi.org/10.1098/rspa.2004.1372

[38] Deepthi Gopal and Stephanie Wehner. ``Using post-measurement information in state discrimination''. Physical Review A 82, 022326 (2010). arXiv:1003.0716.
https://doi.org/10.1103/PhysRevA.82.022326
arXiv:1003.0716

[39] Hoi-Kwong Lo, Xiongfeng Ma, and Kai Chen. ``Decoy State Quantum Key Distribution''. Physical Review Letters 94, 230504 (2005).
https://doi.org/10.1103/PhysRevLett.94.230504

[40] Wei Li, Likang Zhang, Hao Tan, Yichen Lu, Sheng-Kai Liao, Jia Huang, Hao Li, Zhen Wang, Hao-Kun Mao, Bingze Yan, Qiong Li, Yang Liu, Qiang Zhang, Cheng-Zhi Peng, Lixing You, Feihu Xu, and Jian-Wei Pan. ``High-rate quantum key distribution exceeding 110 Mb s–1''. Nature Photonics 17, 416–421 (2023).
https://doi.org/10.1038/s41566-023-01166-4

[41] Marcin Pawłowski and Nicolas Brunner. ``Semi-device-independent security of one-way quantum key distribution''. Physical Review A 84, 010302 (2011).
https://doi.org/10.1103/PhysRevA.84.010302

[42] Lars Lydersen, Carlos Wiechers, Christoffer Wittmann, Dominique Elser, Johannes Skaar, and Vadim Makarov. ``Hacking commercial quantum cryptography systems by tailored bright illumination''. Nature Photonics 4, 686–689 (2010).
https://doi.org/10.1038/nphoton.2010.214

[43] Davide Orsucci, Jean-Daniel Bancal, Nicolas Sangouard, and Pavel Sekatski. ``How post-selection affects device-independent claims under the fair sampling assumption''. Quantum 4, 238 (2020).
https://doi.org/10.22331/q-2020-03-02-238

[44] Antonio Acín, Daniel Cavalcanti, Elsa Passaro, Stefano Pironio, and Paul Skrzypczyk. ``Necessary detection efficiencies for secure quantum key distribution and bound randomness''. Physical Review A 93, 012319 (2016).
https://doi.org/10.1103/PhysRevA.93.012319

Cited by

[1] Máté Farkas, Jurij Volčič, Sigurd A. L. Storgaard, Ranyiliu Chen, and Laura Mančinska, "Maximal device-independent randomness in every dimension", Nature Physics 22 2, 319 (2026).

The above citations are from Crossref's cited-by service (last updated successfully 2026-08-09 22:15:34). The list may be incomplete as not all publishers provide suitable and complete citation data.

On SAO/NASA ADS no data on citing works was found (last attempt 2026-08-09 22:15:34).

This Paper is published in Quantum under the Creative Commons Attribution 4.0 International (CC BY 4.0) license. Copyright remains with the original copyright holders such as the authors or their institutions.