A simpler proof of zero-knowledge against quantum attacks using Grover's amplitude amplification

Keiji Matsumoto

REVIEW

A simpler proof of zero-knowledge against quantum attacks using Grover's amplitude amplification

Keiji Matsumoto

Quantum Physics · Submitted 22 Feb 2006 · 2 references

Pith's verdict: A simpler simulator for quantum zero-knowledge with a fixable operator-order typo in the central proof.

T0 · AI review

How this review was made: An AI referee (deepseek-v4-flash) read the paper on August 28, 2026 and answered a fixed list of questions about it. T0 is the starting level every paper gets. The levels describe how deeply Pith has checked the paper, never the authors.

T0 AI review An AI read the paper and answered a fixed list of questions.
T1 Audit Automatic checks that the references and files the paper relies on exist and match.
T2 Compute The paper's code or calculations re-run with the same results.
T3 Formal statement The claims written out in a formal math language a computer can read.
T4 Proof Those claims proved, and the proof checked by computer.

How Pith checks papers →

· 3 major objections · 5 minor · Ask about this paper · The compiled record · Read the full review →

Challenge this review Comment (0) Read on arXiv ↗

Cite ▾

arXiv IDquant-ph/0602186 (version 1)

Pith IDDL27ZCGZ, Pith's permanent record of this paper and its review

CitationKeiji Matsumoto. "A simpler proof of zero-knowledge against quantum attacks using Grover's amplitude amplification." arXiv:quant-ph/0602186 (2006). https://pith.science/paper/DL27ZCGZ

Cite this reviewBibTeX for Pith's review of this paper

Claim paper

Why Pith says this

Highlight any text to comment on it.

Editor's note

read the letter

Colleague,

Short version: the paper has a real new idea—replacing Watrous's failure-state rotation with a single Grover amplitude-amplification step—and the core identity (2) is correct when re-derived. But the printed proof of (2) is internally inconsistent: the 'Therefore' paragraph runs A S_i^1 A^{-1} S_i^0 A, the reverse of (2), and then expands A^{-1} S_i^0 A as if it were A^{-1} S_i^1 A. That expansion is invalid, since S_i^0 projects on |0_X> and S_i^1 projects on the success subspace Π. The block calculation only checks out in the order of (2), with S_i^1 expanded first and S_i^0 applied as diag(i I_W, I_X). So the theorem is very likely true, but the manuscript as it stands cannot be verified from the displayed derivation.

What the paper does well: equation (1) proves the 1/2 success probability is independent of the auxiliary input, which is exactly the input-independence needed for uniform zero-knowledge. Section 3.1 generalizes the construction to arbitrary success probability λ and shows the two-dimensional invariant subspace, which is a clean way to see Grover's behavior. That part is solid.

Soft spots in proportion: the operator-order typo is the big one, and it is a one-line fix. Section 3.2, the claimed extension to G3C and NP, is only a sketch; it does not prove that the classical simulator's success probability is exactly 1/m for every auxiliary input, unlike the 1/2 case where eq (1) is supplied. That is a genuine gap. Notation and typos are sloppy—'ı' for i, an odd date on the arXiv header—but those are minor.

Bottom line: this deserves a serious referee. With the derivation fixed and Section 3.2 expanded or explicitly flagged as future work, it would be a useful note for the quantum-zero-knowledge community. I'd send it to review rather than desk-reject.

Referee report

Major objections (3)

[§2.2, Eq. (2)] Eq. (2) states A S_i^0 A^{-1} S_i^1 A |ψ⟩|0_X⟩ = (i−1)ΠA|ψ⟩|0_X⟩, but the displayed calculation in the 'Therefore' paragraph begins with A S_i^1 A^{-1} S_i^0 A, i.e., the two phase operators are interchanged. The calculation then replaces A^{-1} S_i^0 A by (i−1)A^{-1}ΠA + I, which is the expansion of A^{-1} S_i^1 A, not of A^{-1} S_i^0 A; the latter would be (i−1)A^{-1}(I_W⊗|0_X⟩⟨0_X|)A + I. The block computation that follows is consistent with the order A S_i^0 A^{-1} S_i^1 A and with expanding A^{-1} S_i^1 A first. Thus the printed proof does not derive Eq. (2); the operator order and the expansion must be corrected.
[§2.2, repeated rounds] The protocol is explicitly repeated polynomially many times, and the text discusses rewinding and the no-cloning obstacle, but it never gives a valid composition argument. The unitary A is defined to act on |ψ⟩|0_V⟩|0_A⟩... and thus assumes the verifier's workspace V starts in |0_V⟩; after one round V holds the verifier's state, so a second application of the same A would reset it. One cannot simply concatenate the per-round simulators as defined, and treating the whole transcript as a single round would make the success probability (1/2)^k rather than 1/2. The paper needs either a precise sequential-composition lemma or an explicit statement that only the single-round protocol is being claimed.
[§3.2] The NP extension is not a proof. It assumes without justification that the simulator A for the G3C protocol succeeds with probability exactly 1/m for every auxiliary input |ψ⟩; the GMW case proved this input-independence in Eq. (1), but no analogous argument is given here. The section also omits the definitions of the relevant projectors and phase operations, and the assertion that repeated measurement/reflection iterations yield a successful simulation does not by itself establish that the final state is indistinguishable from the real interaction. This section should either be expanded into a full argument or explicitly labeled as a sketch.

Minor objections (5)

[§3.1] In the evolution formula for |succ⟩, the printed coefficients φ(λφ+1−λ) and −φ√λ(1−λ)(1−φ) should be ϕ(λφ+1−λ) and −ϕ√λ(1−λ)(1−φ) (the outer phase factors should be ϕ, not φ), as follows from the preceding block calculation. The subsequent φ=ϕ=−1 formulas are unaffected.
[Throughout] The imaginary unit is typeset inconsistently as ı rather than a consistent i; please use a uniform symbol.
[§2.3] There is a typo 'colllapses', and the notation AS−1 0 A−1 should be written as A S_0^{-1} A^{-1} to avoid ambiguity.
[§2.1] The normalization in the initial state after step (a) is written carelessly; it should be a normalized density matrix, e.g., (1/n!)∑_τ |τ(G_0)⟩⟨τ(G_0)|.
[§3.2] 'm being a polynomially-bounded function of the input length n' should read 'm being polynomially bounded in the input length n'.

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

The paper

The paper claims

A new simulator construction using Grover's amplitude amplification proves the Goldreich-Micali-Wigderson graph isomorphism protocol is zero-knowledge against quantum verifiers, simplifying Watrous's earlier proof.

The reading

The Goldreich-Micali-Wigderson (GMW) protocol lets a prover convince a verifier that two graphs are isomorphic (same shape under relabeling) without revealing the relabeling. In one round, the prover sends a random relabeled copy of the first graph; the verifier asks for a relabeling of one of the two graphs (chosen at random); the prover answers. A classical 'simulator' can produce a fake conversation that looks like a real one, but only about half the time: it guesses the verifier's challenge first, and if the guess is wrong, it rewinds and tries again.

In the quantum setting, rewinding is hard because quantum states cannot be copied. Watrous found a workaround by rotating a failure state into a success state with a special operation. This paper replaces that with Grover's amplitude amplification, a standard quantum search trick. The simulator still guesses the challenge, but instead of rewinding on failure, it applies a sequence of phase flips that amplify the success branch until it has probability 1. The key equation shows that with the right phases, one step of this amplification turns the simulator's 1/2 success probability into certainty.

The paper also sketches how the same trick could amplify a simulator that succeeds with probability 1/m, which would extend the result to graph 3-coloring and therefore to all NP problems. The sketch for this extension is thin; the details are left to an earlier paper by Watrous. Overall, the new construction is a genuine simplification of the existing proof, though it does not prove any new facts about the world.

Extended reading notes

Core claim

The GMW graph isomorphism protocol is zero-knowledge against any polynomial-time quantum verifier, proven by a new simulator that applies one Grover amplitude step with phase i to turn the classical simulator's 1/2 success probability into certainty, as stated in equation (2): A S_i^0 A^{-1} S_i^1 A |ψ⟩|0_X⟩ = (i−1)ΠA|ψ⟩|0_X⟩.

Load-bearing premise

For the NP extension, the paper assumes without proof that the classical simulator for the G3C protocol (from Watrous [2]) succeeds with probability exactly 1/m for every auxiliary input |ψ⟩; if this probability varied with |ψ⟩, the Grover amplification in Section 3.1 would not produce a uniform zero-knowledge simulator. For the GMW part, the analogous input-independence is proven in equation (1).

Original abstract

Watrous had presented the first proof of zero-knowledge property of a proof system against a quantum verifier. The key of the proof is the construction of a quantum simulator. In the construction, the 'failure state' is rotated to the 'success' state by a tricky operation which is initially developped for the amplification of QMA proof systems. This manuscript presents a new and simpler construction of a simulator. In the construction, we simply amplify the success probability of a classical simulator using Grover's amplification.

The compiled record

The paper's own sentences, arranged, kept beside the review and separate from it. 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.

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

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

The abstract, sentence by sentence

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

Watrous had presented the first proof of zero-knowledge property of a proof system against a quantum verifier. The key of the proof is the construction of a quantum simulator. In the construction, the 'failure state' is rotated to the 'success' state by a tricky operation which is initially developped for the amplification of QMA proof systems. This manuscript presents a new and simpler construction of a simulator. In the construction, we simply amplify the success probability of a classical simulator using Grover's amplification.

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	Watrous had presented the first proof of zero-knowledge property of a proof system against a quantum verifier.	background 1.00	0.02	0.03	asserted 1.00
s1	The key of the proof is the construction of a quantum simulator.	background 0.96	0.05	0.04	asserted 1.00
s2	In the construction, the 'failure state' is rotated to the 'success' state by a tricky operation which is initially developped for the amplification of QMA proof systems.	background 0.97	0.07	0.05	asserted 1.00
s3	This manuscript presents a new and simpler construction of a simulator.	contribution 1.00	0.92	0.63	asserted 1.00
s4	In the construction, we simply amplify the success probability of a classical simulator using Grover's amplification.	method 0.82	0.91	0.57	asserted 1.00

What kind of paper the classifier reports this is: theoretical result 0.90 · evidence from proof or derivation 1.00.

What was examined, and what was not

sources read

arXiv listing abstract v1

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

References

Discussion

Disagree with the review, or know something it missed? Leave a comment, highlight any passage above to comment on it, or challenge this review formally.

[1] [1]

G. Brassard, P. Hoyer, and A. Tapp, “Quantum Counting”, Pro c. of 25th International Colloquium on Automata, Languages, and Prog ramming (ICALP’98), LNCS 1443, 820-831, 1998, quant-ph/9805082

View on Pith Pith review arXiv 1998

[2] [2]

J. Watrous, ”Zero-knowledge against quantum attacks”, qua nt-ph/0511020, 2005 7

View on Pith arXiv 2005