2026-07-24T09:32:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22636 2026-04-17T05:31:40Z ddc:004 open_access

Single-Round Proofs of Quantumness from Knowledge Assumptions Arabadjieva, Petia Gheorghiu, Alexandru Gitton, Victor Metger, Tony Proofs of quantumness Knowledge assumptions Learning with errors Decisional Diffie-Hellman A proof of quantumness is an efficiently verifiable interactive test that an efficient quantum computer can pass, but all efficient classical computers cannot (under some cryptographic assumption). Such protocols play a crucial role in the certification of quantum devices. Existing single-round protocols based solely on a cryptographic hardness assumption (like asking the quantum computer to factor a large number) require large quantum circuits, whereas multi-round ones use smaller circuits but require experimentally challenging mid-circuit measurements. In this work, we construct efficient single-round proofs of quantumness based on existing knowledge assumptions. While knowledge assumptions have not been previously considered in this context, we show that they provide a natural basis for separating classical and quantum computation. Our work also helps in understanding the interplay between black-box/white-box reductions and cryptographic assumptions in the design of proofs of quantumness. Specifically, we show that multi-round protocols based on Decisional Diffie-Hellman (DDH) or Learning With Errors (LWE) can be "compiled" into single-round protocols using a knowledge-of-exponent assumption [Bitansky et al., 2012] or knowledge-of-lattice-point assumption [Loftus et al., 2012], respectively. We also prove an adaptive hardcore-bit statement for a family of claw-free functions based on DDH, which might be of independent interest. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Petia Arabadjieva and Alexandru Gheorghiu and Victor Gitton and Tony Metger 2025 Is Part Of LIPIcs, Volume 325, 16th Innovations in Theoretical Computer Science Conference (ITCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2025.8 urn:nbn:de:0030-drops-226364 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2025.8 eng https://creativecommons.org/licenses/by/4.0/legalcode