Zero-Knowledge Proofs of Quantumness

Duong Hieu Phan; Weiqiang Wen; Xingyu Yan; Jinwei Zheng

doi:10.62056/ayiv4fe-3

Zero-Knowledge Proofs of Quantumness

Authors

Duong Hieu Phan, Weiqiang Wen, Xingyu Yan, Jinwei Zheng

Duong Hieu Phan

LTCI, Telecom Paris, Institut Polytechnique de Paris, Paris, France
hieu dot phan at telecom-paris dot fr

Weiqiang Wen

LTCI, Telecom Paris, Institut Polytechnique de Paris, Paris, France
weiqiang dot wen at telecom-paris dot fr

Xingyu Yan

State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Telecommunications, Beijing, 100876, China
School of Cyberspace Science and Technology, Beijing Institute of Technology, Beijing, 100081, China
yanxy2020 at bupt dot edu dot cn

Jinwei Zheng

LTCI, Telecom Paris, Institut Polytechnique de Paris, Paris, France
jinwei dot zheng at telecom-paris dot fr

Keywords: Quantum cryptography Zero-knowledge Proofs of quantumness.

Abstract

With the rapid development of quantum computers, proofs of quantumness have recently become an interesting and intriguing research direction. However, in all current schemes for proofs of quantumness, quantum provers almost invariably face the risk of being maliciously exploited by classical verifiers. In fact, through malicious strategies in interaction with quantum provers, classical verifiers could solve some instances of hard problems that arise from the specific scheme in use. In other words, malicious verifiers can break some schemes (that quantum provers are not aware of) through interaction with quantum provers. All this is due to the lack of formalization that prevents malicious verifiers from extracting useful information in proofs of quantumness.

To address this issue, we formalize zero-knowledge proofs of quantumness. Intuitively, the zero-knowledge property necessitates that the information gained by the classical verifier from interactions with the quantum prover should not surpass what can be simulated using a simulated classical prover interacting with the same verifier. As a result, the new zero-knowledge notion can prevent any malicious verifier from exploiting quantum advantage. Interestingly, we find that the classical zero-knowledge proof is sufficient to compile some existing proofs of quantumness schemes into zero-knowledge proofs of quantumness schemes.

Due to some technical reason, it appears to be more general to require zero-knowledge proof on the verifier side instead of the prover side. Intuitively, this helps to regulate the verifier's behavior from malicious to be honest-but-curious. As a result, both parties will play not only one role in the proofs of quantumness but also the dual role in the classical zero-knowledge proof.

Specifically, the two principle proofs of quantumness schemes: Shor's factoring-based scheme and learning with errors-based scheme in [Brakerski et al, FOCS, 2018], can be transformed into zero-knowledge proofs of quantumness by requiring an extractable non-interactive zero-knowledge argument on the verifier side. Notably, the zero-knowledge proofs of quantumness can be viewed as an enhanced security notion for proofs of quantumness. To prevent malicious verifiers from exploiting the quantum device's capabilities or knowledge, it is advisable to transition existing proofs of quantumness schemes to this framework whenever feasible.

References

[AA11]

Scott Aaronson and Alex Arkhipov. The computational complexity of linear optics. In 43rd Annual ACM Symposium on Theory of Computing, pages 333–342. 2011. DOI: 10.1145/1993636.1993682

Google Scholar ePrint

[AAB⁺19]

Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C Bardin, Rami Barends, Rupak Biswas, Sergio Boixo, Fernando GSL Brandao, and David A and others Buell. Quantum supremacy using a programmable superconducting processor. Nature, 574(7779):505–510, 2019. DOI: 10.1038/s41586-019-1666-5

Google Scholar ePrint

[ACGH20]

Gorjan Alagic, Andrew M Childs, Alex B Grilo, and Shih-Han Hung. Non-interactive classical verification of quantum computation. In Theory of Cryptography Conference, pages 153–180. 2020. Springer. DOI: https://doi.org/10.1007/978-3-030-64381-2_6

Google Scholar ePrint

[AMMW24]

Yusuf Alnawakhtha, Atul Mantri, and Daochen Miller Carl A and Wang. Lattice-based quantum advantage from rotated measurements. Quantum, 8:1399, 2024. DOI: https://doi.org/10.22331/q-2024-07-04-1399

Google Scholar ePrint

[BCM⁺18]

Zvika Brakerski, Paul Christiano, Urmila Mahadev, Umesh Vazirani, and Thomas Vidick. A Cryptographic Test of Quantumness and Certifiable Randomness from a Single Quantum Device. In 59th Annual Symposium on Foundations of Computer Science, pages 320-331. 2018. DOI: 10.1109/FOCS.2018.00038

Google Scholar ePrint

[BG92]

Mihir Bellare and Oded Goldreich. On defining proofs of knowledge. In Advances in Cryptology - CRYPTO 1992, pages 390–420. 1992. Springer. DOI: https://doi.org/10.1007/3-540-48071-4_28

Google Scholar ePrint

[BGKM⁺23]

Zvika Brakerski, Alexandru Gheorghiu, Gregory D. Kahanamoku-Meyer, Eitan Porat, and Thomas Vidick. Simple Tests of Quantumness Also Certify Qubits. In Advances in Cryptology – CRYPTO 2023, pages 162–191, Cham. 2023. Springer Nature Switzerland. DOI: https://doi.org/10.1007/978-3-031-38554-4_6

Google Scholar ePrint

[BJS11]

Michael J Bremner, Richard Jozsa, and Dan J Shepherd. Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 467(2126):459–472, 2011. DOI: https://doi.org/10.1098/rspa.2010.0301

Google Scholar ePrint

[BKVV20]

Zvika Brakerski, Venkata Koppula, Umesh Vazirani, and Thomas Vidick. Simpler Proofs of Quantumness. In 15th Conference on the Theory of Quantum Computation, Communication and Cryptography. 2020. DOI: https://doi.org/10.4230/LIPIcs.TQC.2020.8

Google Scholar ePrint

[CGJL23]

Orestis Chardouvelis, Vipul Goyal, Aayush Jain, and Jiahui Liu. Quantum Key Leasing for PKE and FHE with a Classical Lessor. Cryptology ePrint Archive, Paper 2023/1640. 2023.

Google Scholar ePrint

[GMW86]

Oded Goldreich, Silvio Micali, and Avi Wigderson. Proofs that yield nothing but their validity and a methodology of cryptographic protocol design. In 27th Annual Symposium on Foundations of Computer Science. 1986. DOI: doi: 10.1109/SFCS.1986.47

Google Scholar ePrint

[JK25]

Ruta Jawale and Dakshita Khurana. Unclonable Non-interactive Zero-Knowledge. In Advances in Cryptology – ASIACRYPT 2024, pages 94–128, Singapore. 2025. Springer Nature Singapore. DOI: https://doi.org/10.1007/978-981-96-0947-5_4

Google Scholar ePrint

[KLVY23]

Yael Kalai, Alex Lombardi, Vinod Vaikuntanathan, and Lisa Yang. Quantum advantage from any non-local game. In 55th Annual ACM Symposium on Theory of Computing, pages 1617–1628. 2023. DOI: 10.1145/3564246.3585164

Google Scholar ePrint

[KMCVY22]

Gregory D Kahanamoku-Meyer, Soonwon Choi, Umesh V Vazirani, and Norman Y Yao. Classically verifiable quantum advantage from a computational Bell test. Nature Physics, 18(8):918–924, 2022. DOI: https://doi.org/10.1038/s41567-022-01643-7

Google Scholar ePrint

[MLA⁺22]

Lars S Madsen, Fabian Laudenbach, Mohsen Falamarzi Askarani, Fabien Rortais, Trevor Vincent, Jacob FF Bulmer, Filippo M Miatto, Leonhard Neuhaus, Lukas G Helt, Matthew J Collins, and others. Quantum computational advantage with a programmable photonic processor. Nature, 606(7912):75–81, 2022. DOI: https://doi.org/10.1038/s41586-022-04725-x

Google Scholar ePrint

[MP13]

Daniele Micciancio and Chris Peikert. Hardness of SIS and LWE with Small Parameters. In Advances in Cryptology – CRYPTO 2013, pages 21–39, Berlin, Heidelberg. 2013. Springer Berlin Heidelberg. DOI: https://doi.org/10.1007/978-3-642-40041-4_2

Google Scholar ePrint

[Reg24]

Oded Regev. An efficient quantum factoring algorithm. Journal of the ACM, 2024. DOI: https://doi.org/10.1145/3708471

Google Scholar ePrint

[Sho94]

Peter W Shor. Algorithms for quantum computation: discrete logarithms and factoring. In 35th Annual Symposium on Foundations of Computer Science, pages 124–134. 1994. IEEE. DOI: 10.1109/SFCS.1994.365700

Google Scholar ePrint

[WBC⁺21]

Yulin Wu, Wan-Su Bao, Sirui Cao, Fusheng Chen, Ming-Cheng Chen, Xiawei Chen, Tung-Hsun Chung, Hui Deng, Yajie Du, Daojin Fan, and others. Strong quantum computational advantage using a superconducting quantum processor. Physical Review Letters, 127(18):180501, 2021. DOI: https://doi.org/10.1103/physrevlett.127.180501

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/ayiv4fe-3

History

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

How to cite

Duong Hieu Phan, Weiqiang Wen, Xingyu Yan, and Jinwei Zheng, Zero-Knowledge Proofs of Quantumness. IACR Communications in Cryptology, vol. 1, no. 4, Jan 13, 2025, doi: 10.62056/ayiv4fe-3.

License

Copyright is held by the author(s)

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

@article{CiC-1-4-24,
    author = "Phan, Duong Hieu and Wen, Weiqiang and Yan, Xingyu and Zheng, Jinwei",
    journal = "{IACR} {C}ommunications in {C}ryptology",
    publisher = "{I}nternational {A}ssociation for {C}ryptologic {R}esearch",
    title = "Zero-Knowledge Proofs of Quantumness",
    volume = "1",
    number = "4",
    date = "2025-01-13",
    year = "2025",
    issn = "3006-5496",
    doi = "10.62056/ayiv4fe-3"
}

TY - JOUR
AU - Phan, Duong
AU - Wen, Weiqiang
AU - Yan, Xingyu
AU - Zheng, Jinwei
PY  - 2025
TI  - Zero-Knowledge Proofs of Quantumness
JF  - IACR Communications in Cryptology
JA  - CIC
VL  - 1
IS  - 4
DO  - 10.62056/ayiv4fe-3
UR  - https://doi.org/10.62056/ayiv4fe-3
AB  - <p>  With the rapid development of quantum computers, proofs of quantumness have recently become an interesting and intriguing research direction. However, in all current schemes for proofs of quantumness, quantum provers almost invariably face the risk of being maliciously exploited by classical verifiers. In fact, through malicious strategies in interaction with quantum provers, classical verifiers could solve some instances of hard problems that arise from the specific scheme in use. In other words, malicious verifiers can break some schemes (that quantum provers are not aware of) through interaction with quantum provers. All this is due to the lack of formalization that prevents malicious verifiers from extracting useful information in proofs of quantumness.</p><p>To address this issue, we formalize zero-knowledge proofs of quantumness. Intuitively, the zero-knowledge property necessitates that the information gained by the classical verifier from interactions with the quantum prover should not surpass what can be simulated using a simulated classical prover interacting with the same verifier. As a result, the new zero-knowledge notion can prevent any malicious verifier from exploiting quantum advantage. Interestingly, we find that the classical zero-knowledge proof is sufficient to compile some existing proofs of quantumness schemes into zero-knowledge proofs of quantumness schemes.</p><p>Due to some technical reason, it appears to be more general to require zero-knowledge proof on the verifier side instead of the prover side. Intuitively, this helps to regulate the verifier's behavior from malicious to be honest-but-curious. As a result, both parties will play not only one role in the proofs of quantumness but also the dual role in the classical zero-knowledge proof.</p><p>Specifically, the two principle proofs of quantumness schemes: Shor's factoring-based scheme and learning with errors-based scheme in [Brakerski et al, FOCS, 2018], can be transformed into zero-knowledge proofs of quantumness by requiring an extractable non-interactive zero-knowledge argument on the verifier side. Notably, the zero-knowledge proofs of quantumness can be viewed as an enhanced security notion for proofs of quantumness. To prevent malicious verifiers from exploiting the quantum device's capabilities or knowledge, it is advisable to transition existing proofs of quantumness schemes to this framework whenever feasible. </p>
ER  -

Duong Hieu Phan, Weiqiang Wen, Xingyu Yan, and Jinwei Zheng, Zero-Knowledge Proofs of Quantumness. IACR Communications in Cryptology, vol. 1, no. 4, Jan 13, 2025, doi: 10.62056/ayiv4fe-3.