{"id":"f672146e-0d64-4b2a-8e1f-a0436a0aa5cd","arxiv_id":"2412.01966","paper_version":2,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Key-updating functions for Liang's quantum homomorphic encryption are implemented as classical-quantum circuits, enabling runtime key updates and linear classically controlled S gates, and the approach is demonstrated on Szegedy quantum and semiclassical walks.","lead":"This paper builds a simulator that lets a remote server run quantum walks on encrypted data without learning the data, using a method that updates decryption keys on the fly instead of precomputing them. It shows the approach works for both standard and semiclassical quantum walks on small graphs, and provides open-source code.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"X-only QOTP security claim in Sec. III.C fails for the pure-state initializations actually used in the Sec. V semiclassical simulations; the ciphertext ensemble is not maximally mixed.","rationale":"The reader's identified weak point, the simplified simulation's reuse of Bell ancillas, is actually sound: the Bell measurements act on a separate subsystem and commute with subsequent main-system unitaries, so moving them earlier and resetting the ancillas does not alter the walker's distribution, and the paper's realistic-versus-simplified comparisons corroborate this. The more serious issue is the security analysis in Section III.C, which conflates a mixed state diagonal in the computational basis with a pure superposition having positive amplitudes. The semiclassical simulation in Section V uses a pure state produced by an RY gate, and for such states the X-averaged ciphertext retains coherence between computational basis states, so the ensemble is not maximally mixed. This does not invalidate the circuit-construction or simulation results, but it undermines the stated perfect-security guarantee of the semiclassical QHE protocol as implemented. The paper should either use full X+Z QOTP for the initial state or explicitly restrict the security claim to mixed-state inputs; the central implementation claims otherwise remain credible, so a conditional acceptance is appropriate.","tokens_in":29772,"tokens_out":27593,"duration_ms":496743,"concrete_test":"Analytically compute the ciphertext ensemble for the actual Section V initialization: take |psi> = RY(theta)|0> with cos(theta/2) = sqrt(0.75), encrypt with a random bit x via X^x, and average over x. Evaluate whether rho_avg = (|0><0| + |1><1|)/2. It is not; rho_avg = 0.5 I + sqrt(0.1875)(|0><1| + |1><0|). More generally, compute the trace distance between the X-averaged ciphertext and I/2 for any non-uniform probability vector p; any nonzero value falsifies the perfect-security claim in Section III.C for pure-state classical-distribution inputs.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Section III.C claims that for states representing classical distributions, encrypting with only X gates preserves perfect security, and proves it via Eq. (38) for the mixed state rho_c = sum p_i |i><i|. However, the semiclassical walk simulation in Section V initializes the walker in a pure state, e.g. sqrt(0.75)|0> + sqrt(0.25)|1> created by an RY gate. For a pure superposition |psi> = sum sqrt(p_i)|i>, the X-averaged ciphertext is rho = (1/2^n) sum_a X^a|psi><psi|X^a, which retains off-diagonal terms sqrt(p_i p_j) and is not I/2^n unless p is uniform. For n=1 and p=0.75, rho = 0.5 I + sqrt(0.1875)(|0><1|+|1><0|), with trace distance sqrt(0.1875) from the maximally mixed state. A server measuring in a non-computational basis such as |+>,|-> can estimate p and distinguish the state from random, so the protocol is not perfectly secure for the pure-state inputs used in the reported semiclassical simulation. This affects the central claim of implementing semiclassical walks with a perfectly secure QHE scheme; the fix is to use full X+Z QOTP or to restrict the security claim to mixed-state inputs.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper reformulates Liang's quasi-compact quantum homomorphic encryption scheme as a classical-quantum circuit in which the encryption key is updated at running time, avoiding the exponential precomputation of key-updating functions used in earlier Qiskit implementations. It derives key-updating functions for Clifford gates, T/T† gates, measurement, and reset; analyzes T/T† counts for Szegedy quantum walks on cycle, complete, and bipartite graphs; and reports Qiskit simulations of a quantum walk on a bipartite graph and a semiclassical walk on a cycle, benchmarked against the SQUWALS simulator. The paper also introduces the CQC-QHE library for constructing and simulating such circuits.","tokens_in":30031,"tokens_out":28642,"duration_ms":261975,"significance":"If the security and correctness claims hold, the paper is a useful contribution to the practical simulation of QHE schemes. The key-updating derivations are self-contained and correct, the T-count formulas check out, and the simulations are cross-checked against an independent deterministic simulator (SQUWALS) and an unencrypted circuit. The reformulation with a linear number of classically controlled S gates is a genuine improvement over previous exponential precomputation approaches. However, one load-bearing security claim is flawed for the pure-state initializations actually used in the semiclassical simulations, and this needs to be addressed before the results can be accepted as stated.","major_comments":[{"comment":"The perfect-security argument for X-only QOTP is valid only for states that are diagonal in the computational basis, but the text explicitly claims that the argument covers quantum superpositions. For the pure state |ψ⟩ = √p|0⟩ + √(1−p)|1⟩ used in the semiclassical simulation (Section V, cycle graph, initial vector (0.75, 0.25, 0, ...), created by an RY gate), the X-averaged ciphertext is ρ = (1/2)∑_a X^a|ψ⟩⟨ψ|X^a = (1/2)I + √(p(1−p))(|0⟩⟨1| + |1⟩⟨0|), whose trace distance from the maximally mixed state is √(p(1−p)) ≠ 0. A server can measure in the {|+⟩,|−⟩} basis and estimate p, so the protocol is not perfectly secure for such inputs. The final equality in Eq. (38) uses ρ_c = Z_iρ_cZ_i†, which is false for a coherent superposition; it holds only for the diagonal mixed state of Eq. (37). This is load-bearing because the abstract and Section VI claim perfect security for the semiclassical walk implementation, and the simulations initialize the walker in a pure superposition. The fix is to encrypt pure initial states with the full X+Z QOTP of Eq. (21), or to restrict the security claim and the simulations to diagonal mixed-state inputs; the former is preferable and is compatible with the rest of the scheme.","section":"III.C (Eq. 38)"}],"minor_comments":[{"comment":"The identity H = A X A† with A = SHT H S†H is stated without proof; the identity is correct, but a short derivation or an explicit reference would make the +2 T/T† cost in Eq. (52) easier to verify.","section":"IV.B (Eq. 52)"},{"comment":"The equivalence between the full L-ancilla simulation and the simplified two-ancilla simulation is demonstrated only empirically in SM Figure S8; a short formal argument invoking the deferred-measurement principle would strengthen Section V, since the semiclassical walk results use the simplified simulation.","section":"SM SII"},{"comment":"The complexity expression in Eq. (22) refers to the composed Clifford key-updating functions, while the Qiskit implementation uses one key-updating function per gate; this distinction is acknowledged in Section VI but should be stated at the point of Eq. (22) to avoid confusion.","section":"II.D (Eq. 22)"},{"comment":"There are typographical issues such as 'SQUW ALS' for SQUWALS and inconsistent spacing in 'T /T†'; also, the notation log2(N) is used for log_2(N) and should be made consistent.","section":"General"}],"recommendation":"major_revision","confidential_remarks":"The security flaw in Section III.C is significant but fixable within the manuscript's scope: the simulations can use full X+Z QOTP for pure-state inputs, and the text can be revised to restrict the X-only security claim to diagonal mixed states. The rest of the technical content appears sound, and the benchmark against SQUWALS is appropriate because it is cross-checked against an unencrypted Qiskit circuit rather than used to fit parameters."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe good news first: this paper gives the first Qiskit implementation of Liang's QHE scheme where the encryption keys are updated at runtime, so you don't need exponential key precomputation. The classical-quantum circuit decomposition for the key-updating functions is sound (Eqs. 7-20 are just gate commutation), the T-count formulas in Section IV match direct counting on the decomposed circuits, and the simulations reproduce the SQUWALS benchmark. The code is on GitHub. That is a genuinely useful tool for the QHE subfield.\n\nThe soft spot is the security analysis in Section III.C. The paper claims that for states representing classical distributions, X-only QOTP is perfectly secure, and proves it for a diagonal mix of computational basis states (Eq. 37-38). But the semiclassical walk initializes the walker in a pure superposition, e.g. sqrt(0.75)|0> + sqrt(0.25)|1> from an RY gate. For such a state, averaging over X keys leaves off-diagonal terms, so the ciphertext is not maximally mixed and a server measuring in a non-computational basis can estimate the amplitudes. Trace distance from the maximally mixed state is nonzero. So the claim as stated is false.\n\nThe fix is easy, and it does not break the paper's main contribution: use the full X+Z QOTP (which is what the simulations in Section V actually do - the keys in Table III have both X and Z parts), or restrict the security claim to diagonal mixed-state encodings. The authors should also clarify that the semiclassical walk's coherent encoding is not a classical distribution in the security sense.\n\nMinor points: the decomposition H = A X A† (Section IV.B) is asserted without proof; it's a standard identity, but a one-line verification would help. The simplified Bell-reuse simulation in SM SII relies on the principle of deferred measurements; the empirical check against the full simulation is convincing, though a formal argument would be cleaner.\n\nOverall, the implementation work is solid and reproducible, and the paper deserves peer review. The security claim needs fixing, not the core machinery.\n\nRecommendation: send it to review, with a request that the authors correct the X-only security claim and rephrase the associated statements.","headline":"The simulation machinery is a real step forward for QHE testing, but the X-only QOTP security claim in Sec. III.C is wrong for the pure-state encodings used in the semiclassical walk.","tokens_in":30581,"tokens_out":5623,"would_cite":true,"duration_ms":49796,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P68"],"pacs":["03.67.Lx"],"model":"deepseek-v4-flash","headline":"This paper claims that a teleportation-based quantum homomorphic encryption scheme can be rewritten as a classical-quantum circuit whose encryption key is updated at run time, making the number of classically controlled S gates linear in…","keywords":["quantum homomorphic encryption","classical-quantum circuits","Szegedy quantum walk","semiclassical quantum walk","Clifford+T gate complexity","runtime key updating","homomorphic measurement and reset","quantum circuit simulation"],"falsifier":"Run any Clifford+T circuit through both the full scheme, with one Bell register per $T/T^\\dagger$ gate measured after the main circuit, and the simplified scheme, with two Bell ancillas measured and reset after each $T/T^\\dagger$ gate, forcing identical initial keys and identical Bell-outcome bits in both runs, then compare the decrypted output distributions; any difference beyond sampling noise would show that the interleaved measurement and reset altered the main-qubit evolution.","tokens_in":29548,"feed_emoji":"🔐","tokens_out":10226,"duration_ms":89791,"temperature":0.7,"pith_summary":"Quantum homomorphic encryption lets an untrusted server run a circuit on encrypted qubits, but in the leading teleportation-based schemes the client's decryption key for each T gate depends on a measurement outcome, and earlier simulations handled this by precomputing an exponential number of key mappings. This paper claims that the whole scheme can be rewritten as a classical-quantum circuit in which the key is updated at run time, gate by gate, so the number of classically controlled S gates grows linearly with the number of $T/T^\\dagger$ gates. The same circuit treatment is extended to intermediate measurements and resets, which are exactly the operations a semiclassical quantum walk needs. If the claim is correct, homomorphic evaluation of Szegedy quantum and semiclassical walks becomes practical to simulate, and the construction gives a reusable recipe for other low-T-gate algorithms.","feed_headline":"Quantum homomorphic encryption keys update in linear time","feed_subtitle":"Semiclassical Szegedy walks on encrypted data now run with runtime key updates, no exponential precomputation.","key_machinery":"The load-bearing object is the table of key-updating functions and their classical-quantum circuit implementation. For each Clifford gate the update is a classical operation over the XOR-encoded key bits; for each $T/T^\\dagger$ gate the update is a classical-quantum procedure in which the client measures a Bell register in an $S^a$-rotated basis and feeds the outcome bits back into the key. The paper's second mechanism is the simplified simulation: by invoking the principle of deferred measurements, the Bell registers can be measured and reset immediately after each $T$ gate, so two ancilla qubits serve all $T$ gates and the memory cost no longer grows with the circuit's $T$-gate count. These rules together make the encryption key an explicitly dynamical quantity of the circuit rather than a precomputed object.","core_discovery":"The central claim is that the decryption phase of the teleportation-based QHE scheme can be built as a classical-quantum circuit instead of an exponential table lookup. Each Clifford gate contributes a deterministic update on the classical key bits $x$ and $z$; each $T$ gate contributes a teleported $S^a$ correction whose control bit $a$ is the current key bit, plus two fresh randomness bits from an $S^a$-rotated Bell measurement; each $T^\\dagger$ gate contributes the analogous update. Because these updates are executed in order during simulation, the final key is obtained when the circuit is run, not before it, and the number of classically controlled S gates is one per $T/T^\\dagger$ gate. The paper also provides key-updating rules for measurement and reset, and shows that the $T/T^\\dagger$-gate counts for Szegedy walk circuits on cycle, complete, and complete bipartite graphs grow polylogarithmically or logarithmically in the number of nodes, so the schemes are efficient for those walks. Simulations on small instances reproduce the deterministic walk probabilities after decryption.","pith_inferences":["Beyond the paper, the same gate-by-gate key update should generalize to any gate-teleportation QHE scheme whose corrections are Clifford operations conditioned on measurement bits; the scheme's practical limit is the client's classical processing speed, not the quantum resource count.","Because the semiclassical walk is adaptive, with each step's initial state depending on the previous measurement, the reset and measurement rules imply that limited classes of adaptive quantum circuits can be run homomorphically, not only fixed-depth ones; this is directly testable on repeated-measurement algorithms.","The $T$-count analysis points to the update operator $V$ as the real cost driver: graphs with structured transition matrices admitting efficient $V$ circuits will be the natural targets for QHE, while irregular Markov chains should be expected to break the polylogarithmic scaling.","The two-ancilla simplification, if it holds exactly, also suggests a hardware-level resource trade: mid-circuit measurement and qubit reuse could let QHE run on small devices with fixed qubit counts, at the price of deeper circuits and measurement errors."],"forward_implications":["Circuits with polynomially many $T/T^\\dagger$ gates can be evaluated homomorphically without exponential key precomputation; the client's work scales with the circuit size.","Homomorphic evaluation extends to circuits containing intermediate measurements and resets, so semiclassical walks and other algorithms with mid-circuit measurements become valid QHE workloads.","The Szegedy walk circuits considered here have polylogarithmic or logarithmic $T/T^\\dagger$ counts in the number of graph nodes, so homomorphic evaluation of these walks is efficient rather than asymptotically prohibitive.","The simplified two-ancilla simulation makes the memory footprint of a classical QHE simulation independent of the number of $T/T^\\dagger$ gates, enabling larger test circuits in classical simulators.","The reusable circuit blocks form a library for building and testing QHE implementations of other Clifford+T algorithms."],"supporting_citations":[{"why":"Base teleportation QHE scheme that the paper reformulates into classical-quantum circuits.","marker":"[7]"},{"why":"Earlier QHE simulation requiring exponential key precomputation; the run-time key-update approach improves on it.","marker":"[18]"},{"why":"Introduces the Szegedy quantum walk operator that the homomorphic circuits implement.","marker":"[25]"},{"why":"Defines the semiclassical Szegedy walk whose intermediate measurements and resets need new homomorphic rules.","marker":"[40]"},{"why":"Deterministic classical simulator used to validate the decrypted walk distributions.","marker":"[43]"},{"why":"Provides the deferred-measurement principle underpinning the two-ancilla simplified simulation.","marker":"[45]"},{"why":"Supplies the efficient update-operator circuits for cycle, complete, and bipartite graphs that set the T-gate counts.","marker":"[49]"},{"why":"Gives the Clifford+T approximation cost for rotations used in the complete-graph T-gate count.","marker":"[51]"},{"why":"Supplementary material with the simplified-simulation details and correctness proof for the bipartite update circuit.","marker":"[52]"}],"fun_headline_variants":["Quantum homomorphic keys now update in linear time","Semiclassical Szegedy walks get linear-time key updates","Exponential key prep eliminated for quantum homomorphic encryption","CQC-QHE: encrypted quantum walks with fast keys","Semiclassical walks on encrypted data, keys in linear time"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The simplified simulation assumes that measuring and resetting the Bell ancilla qubits immediately after each T gate, instead of storing every Bell register until the end, leaves the main qubits' evolution exactly unchanged; if the early measurement disturbs the state or produces ordering effects, the semiclassical-walk simulation would not faithfully represent the QHE protocol.","fun_headline_variants_meta":{"raw":{"variants":["Quantum homomorphic keys now update in linear time","Semiclassical Szegedy walks get linear-time key updates","Exponential key prep eliminated for quantum homomorphic encryption","CQC-QHE: encrypted quantum walks with fast keys","Semiclassical walks on encrypted data, keys in linear time"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000264,"raw_usage":{"total_tokens":1633,"prompt_tokens":1005,"completion_tokens":628,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":621,"completion_tokens_details":{"reasoning_tokens":546}},"tokens_in":621,"tokens_out":628,"duration_ms":5983,"temperature":1.0,"reasoning_tokens":546,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T00:00:08.884746+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run any Clifford+T circuit through both the full scheme, with one Bell register per $T/T^\\dagger$ gate measured after the main circuit, and the simplified scheme, with two Bell ancillas measured and reset after each $T/T^\\dagger$ gate, forcing identical initial keys and identical Bell-outcome bits in both runs, then compare the decrypted output distributions; any difference beyond sampling noise would show that the interleaved measurement and reset altered the main-qubit evolution.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Base teleportation QHE scheme that the paper reformulates into classical-quantum circuits."},{"cited_title":"Demonstrating Quantum Homomorphic Encryption Through Simulation","cited_arxiv_id":"2406.16247","evidence_quote":"Earlier QHE simulation requiring exponential key precomputation; the run-time key-update approach improves on it."},{"cited_title":"Shenvi, J","cited_arxiv_id":null,"evidence_quote":"Introduces the Szegedy quantum walk operator that the homomorphic circuits implement."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Defines the semiclassical Szegedy walk whose intermediate measurements and resets need new homomorphic rules."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Deterministic classical simulator used to validate the decrypted walk distributions."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the deferred-measurement principle underpinning the two-ancilla simplified simulation."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the efficient update-operator circuits for cycle, complete, and bipartite graphs that set the T-gate counts."},{"cited_title":"Loke and J","cited_arxiv_id":null,"evidence_quote":"Gives the Clifford+T approximation cost for rotations used in the complete-graph T-gate count."},{"cited_title":"Hagberg, D","cited_arxiv_id":null,"evidence_quote":"Supplementary material with the simplified-simulation details and correctness proof for the bipartite update circuit."}],"review_version":1}