Paper 2025/100

Zero-Knowledge Proofs of Quantumness

Duong Hieu Phan, Télécom Paris, Institut Polytechnique de Paris
Weiqiang Wen, Télécom Paris, Institut Polytechnique de Paris
Xingyu Yan, Beijing University of Posts and Telecommunications, Beijing Institute of Technology
Jinwei Zheng, Télécom Paris, Institut Polytechnique de Paris
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 reasons, 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.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published by the IACR in CIC 2024
DOI
https://doi.org/10.62056/ayiv4fe-3
Keywords
Quantum cryptographyZero-knowledgeProofs of quantumness.
Contact author(s)
hieu phan @ telecom-paris fr
weiqiang wen @ telecom-paris fr
yanxy2020 @ bupt edu cn
jinwei zheng @ telecom-paris fr
History
2025-01-23: approved
2025-01-22: received
See all versions
Short URL
https://ia.cr/2025/100
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2025/100,
      author = {Duong Hieu Phan and Weiqiang Wen and Xingyu Yan and Jinwei Zheng},
      title = {Zero-Knowledge Proofs of Quantumness},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/100},
      year = {2025},
      doi = {https://doi.org/10.62056/ayiv4fe-3},
      url = {https://eprint.iacr.org/2025/100}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.