Secret extraction attacks against obfuscated IQP circuits

David Gross; Dominik Hangleiter

RECORD

Secret extraction attacks against obfuscated IQP circuits

David Gross, Dominik Hangleiter

Quantum Physics · Submitted 15 Dec 2023

abstract compiled · 2026-09-23 · no language-model review

The authors' main claim The important problem of finding an efficient and reliable verification protocol for sampling-based proofs of quantum supremacy thus remains open.

how it is stated · asserted 1.00 read the record →

Comment (0) Read on arXiv ↗

Cite ▾

Claim paper

The compiled record

The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.

Open the compiled record

Compiled by classifier-1.13.0 via TypeSafe API, question bank abstract-p1-20260923, 2026-09-23: 1 request, 8,840 input tokens.

What the abstract itself states, as probabilities: claims first 0.06 · states limitation 0.66 · human participants 0.02 · controlled comparison 0.04 · randomized assignment 0.01 · states quantitative result 0.91 · compares with prior results 0.93 · mentions code or data availability 0.05.

The abstract, sentence by sentence

arXiv listing abstract v2. Results and the main claim are underlined; show every role.

Quantum computing devices can now perform sampling tasks which, 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 IQP circuits, 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 NP-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 IQP Stabilizer Scheme 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 which 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 supremacy thus remains open.

background contribution method result interpretation main claim

What the classifier reports for each sentence. The number is the probability it gave the label.
#	sentence	role	the authors' own work	states the main conclusion	strength
s0	Quantum computing devices can now perform sampling tasks which, according to complexity-theoretic and numerical evidence, are beyond the reach of classical computers.	background 1.00	0.04	0.02	asserted 0.80
s1	This raises the question of how one can efficiently verify that a quantum computer operating in this regime works as intended.	background 0.84	0.04	0.02	asserted 0.53
s2	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 IQP circuits, and challenges a prover to execute it on a quantum computer.	background 1.00	0.02	0.02	asserted 1.00
s3	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.	background 0.90	0.05	0.03	asserted 0.99
s4	It was conjectured that extracting the secret from the challenge problem is NP-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.	background 0.97	0.03	0.04	speculative 0.90
s5	Unfortunately, about a decade later, Kahanamoku-Meyer found an efficient classical secret extraction attack.	background 0.96	0.03	0.06	asserted 1.00
s6	Bremner, Cheng, and Ji very recently followed up by constructing a wide-ranging generalization of the original protocol.	background 1.00	0.04	0.03	asserted 1.00
s7	Their IQP Stabilizer Scheme has been explicitly designed to circumvent the known weakness.	background 0.98	0.04	0.03	asserted 0.99
s8	They also suggested that the original construction can be made secure by adjusting the problem parameters.	background 0.96	0.04	0.03	hedged possibility 0.97
s9	In this work, we develop a number of secret extraction attacks which are effective against both new approaches in a wide range of problem parameters.	contribution 1.00	0.96	0.64	asserted 1.00
s10	In particular, we find multiple ways to recover the 300-bit secret hidden in a challenge data set published by Bremner, Cheng, and Ji.	result 0.95	0.96	0.22	asserted 1.00
s11	The important problem of finding an efficient and reliable verification protocol for sampling-based proofs of quantum supremacy thus remains open.	interpretation 0.60	0.10	0.53	asserted 1.00

What kind of paper the classifier reports this is: method or tool 0.89 · evidence from simulation or computation 0.72.

What was examined, and what was not

sources read

arXiv listing abstract v2

not examined

full text
figures and tables
references and citing sentences
relations to other papers

levels run

P abstract

not run

S sections
T body sentences
C citations
R cross-paper relations

Every quoted sentence on this record is the authors'. Every label is from Pith's closed vocabulary, with the probability shown beside it. Every number in the measurements table is the authors', checked by code. Record as JSON

The paper

Original abstract

Quantum computing devices can now perform sampling tasks which, 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 IQP circuits, 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 NP-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 IQP Stabilizer Scheme 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 which 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 supremacy thus remains open.

Human review

How Pith checks papers → · Full audit of this paper →

References

Forward citations

Cited by 2 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

Verifiable Quantum Advantage and Computation via Quantum Circuit Obfuscation
quant-ph 2026-09 conditional novelty 7.0 of 10

Assuming quantum indistinguishability obfuscation, this paper constructs a publicly verifiable proof of quantumness and private and public classical verification of BQP, plus a conditional route toward building qiO.
Strategic Plan for Neutral Atom Quantum Computation
quant-ph 2026-07 conditional novelty 3.0 of 10

If qubit-count growth (~1.8x/yr) and gate-error reduction (~0.62x/yr) continue, neutral-atom quantum computers could reach practical quantum advantage within a decade, this roadmap projects.

How the literature uses it

2 arXiv papers cite this in 11 sentences

Each citing sentence is taken from the citing paper's LaTeX source and typed by Pith's classifier. A label appears at probability 0.8 or more (0.95 for support), a contest at 0.7 or more; the quoted words are the citing authors'. How each label was checked · JSON

Papers citing it · 9 sentences without a confident label

Uses its method or tool 1 paper

Taking the IQP matrix $H$ as input, the procedure of the Radical Attack is as follows [ref] : * Compute the kernel of $G = H^T H$.

Instantaneous Quantum Polynomial-Time Sampling and Verifiable Quantum Advantage: Stabilizer Scheme and Classical Security · More classical attacks · 0.93

What it cites · 30 sentences without a confident label

Builds on 1 paper

Concretely, we propose two extensions of [ref] 's idea, which we call the Lazy Linearity Attack and the Double Meyer.

Forging quantum data: classically defeating an IQP-based quantum test · Introduction · 0.98

Uses the method or tool of 1 paper

The theory is tested on 100k examples generated by a software package provided as part of [ref] , and is found to match the empirical data well.

Instantaneous Quantum Polynomial-Time Sampling and Verifiable Quantum Advantage: Stabilizer Scheme and Classical Security · Introduction · 0.80

Uses data or values from 1 paper

In the new challenge of [ref] , $n=300, m=360$, so that $n-m/2 = 120$, meaning that $G_d⃗$ is so large that this simple approach is no longer feasible.

Instantaneous Quantum Polynomial-Time Sampling and Verifiable Quantum Advantage: Stabilizer Scheme and Classical Security · Analysis · 0.91

Compares with 1 paper

We also observe that for the Extended QRC construction, the Radical Attack and the approach of [ref] complement each other almost perfectly, in the sense that for every parameter choice, exactly one of the two works with near-certainty.

Forging quantum data: classically defeating an IQP-based quantum test · Introduction · 1.00

Cites as support 1 paper

Again, however, their implementation requires arithmetic operations, putting the advantage regime far beyond the reach of current technology [ref] .

Interactive Protocols for Classically-Verifiable Quantum Advantage · Introduction · 0.96

Cites as background 3 papers

A different approach to demonstrations of quantum advantage has focused on simple protocols based on sampling from the output of random quantum circuits [ref] .

Characterizing Quantum Supremacy in Near-Term Devices · Introduction · 0.91
We mostly follow the notation of Ref. [ref] .

Instantaneous Quantum Polynomial-Time Sampling and Verifiable Quantum Advantage: Stabilizer Scheme and Classical Security · Notation and definitions · 0.87
A relevant reference is [ref] (see also Refs. [ref] for a discussion in the context of stabilizer theory).

2208.01688 · Reconstructing the support from random samples · 0.82

Discussion

Know something about this paper? Leave a comment, or highlight any passage above to comment on it.