Universität zu Köln

Gross, David ORCID: 0000-0001-8888-3028 and Hangleiter, Dominik ORCID: 0000-0002-4766-7967 (2025). Secret-Extraction Attacks against Obfuscated Instantaneous Quantum Polynomial-Time Circuits. PRX Quantum, 6 (2). American Physical Society. ISSN 2691-3399

PDF PRXQuantum.6.020314.pdf Bereitstellung unter der CC-Lizenz: Creative Commons Attribution. Download (863kB)

Abstract

[Artikel-Nr. 020314] Quantum computing devices can now perform sampling tasks that, according to complexity-theoretic and numerical evidence, are beyond the reach of classical computers. This raises the question of how one can efficiently verify that a quantum computer operating in this regime works as intended. In 2008, Shepherd and Bremner proposed a protocol in which a verifier constructs a unitary from the comparatively easy-to-implement family of so-called and challenges a prover to execute it on a quantum computer. The challenge problem is designed to contain an obfuscated secret, which can be turned into a statistical test that accepts samples from a correct quantum implementation. It was conjectured that extracting the secret from the challenge problem is -hard, so that the ability to pass the test constitutes strong evidence that the prover possesses a quantum device and that it works as claimed. Unfortunately, about a decade later, Kahanamoku-Meyer found an efficient classical secret-extraction attack. Bremner, Cheng, and Ji very recently followed up by constructing a wide-ranging generalization of the original protocol. Their has been explicitly designed to circumvent the known weakness. They also suggested that the original construction can be made secure by adjusting the problem parameters. In this work, we develop a number of secret-extraction attacks that are effective against both new approaches in a wide range of problem parameters. In particular, we find multiple ways to recover the 300 -bit secret hidden in a challenge data set published by Bremner, Cheng, and Ji. The important problem of finding an efficient and reliable verification protocol for sampling-based proofs of quantum advantage thus remains open.

Item Type:	Article
Creators:	Creators Email ORCID ORCID Put Code Gross, David UNSPECIFIED https://orcid.org/0000-0001-8888-3028 UNSPECIFIED Hangleiter, Dominik UNSPECIFIED https://orcid.org/0000-0002-4766-7967 UNSPECIFIED
URN:	urn:nbn:de:hbz:38-796875
Identification Number:	10.1103/PRXQuantum.6.020314
Journal or Publication Title:	PRX Quantum
Volume:	6
Number:	2
Date:	22 April 2025
Publisher:	American Physical Society
ISSN:	2691-3399
Language:	English
Faculty:	Faculty of Mathematics and Natural Sciences
Divisions:	Faculty of Mathematics and Natural Sciences > Department of Physics > Institute for Theoretical Physics
Subjects:	Physics
['eprint_fieldname_oa_funders' not defined]:	Publikationsfonds UzK
Refereed:	Yes
URI:	http://kups.ub.uni-koeln.de/id/eprint/79687