{"id":"9375e2ca-23f1-42df-88d0-25d214c01267","arxiv_id":"2504.14957","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A linear number of parallel Kac's walk steps forms an adaptively secure pseudorandom unitary, and adding inverse queries costs no extra asymptotic steps.","lead":"This paper proves that repeating a simple random walk on two-qubit rotations, called the parallel Kac's walk, produces unitaries that are indistinguishable from perfectly random unitaries to any efficient quantum attacker. The construction also stays secure when the attacker is allowed to query the inverse operation.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"PRU proof hinges on cited O(1/N^2)-RSS bound for T=30n from [LQS+24, Thm 10]; if that bound fails, the distinct-block projection and main theorems collapse.","rationale":"The reader's weakest_assumption identifies the same load-bearing dependency: the O(1/N^2)-RSS bound imported from [LQS+24, Theorem 10]. I reviewed the internal proof structure and found no fatal internal inconsistency. The apparent inversion of the constant in Lemma 4.13 (the ratio ρ should be sqrt(∏(N-2i)/(N-i)) < 1 rather than sqrt(∏(N-i)/(N-2i)) > 1) is a typographical error that does not change the O(t^2/N) asymptotic since both are 1+O(t^2/N) in absolute value. The garbled inequality chain in Claim 5.25 is repairable and does not break the induction. The only step that is not derived in the paper is Theorem 4.3, and every subsequent lemma (3.1, 4.14, 4.15, 5.19) depends on it. If the cited bound is false for T=30n and d=5n, then the projection into the distinct block subspace fails and neither Theorem 4.4 nor Theorem 5.1 follows. Hence the concern is load-bearing, and the conditional acceptance recommendation remains appropriate.","tokens_in":53718,"tokens_out":20510,"duration_ms":164472,"concrete_test":"Independently re-derive the proof of [LQS+24, Theorem 10] with the parameters T=30n and d=5n, and verify that the RSS error is O(1/N^2) with an explicit constant small enough to preserve the O(t^2/N) bounds in Lemma 3.1 (in particular, the operator-norm error in Eq. (7) must be O(1/N^2) per basis element). If the best bound at T=30n is only O(1/N^c) for c<2, or if ε=O(1/N^2) is only achieved for T=Ω(n^2), then the central claim fails.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 4.3, cited from [LQS+24, Theorem 10] with parameters adjusted, asserts that HP_{n,T} is an ε-RSS distribution with ε=O(1/N^2) for T=30n and d=5n. Every subsequent step depends on this: Lemma 3.1 uses the RSS property to bound the equal-block term (Eq. 5) and the flip-first-bit term (Eq. 6) by O(1/N) each; Lemmas 4.14 and 4.15 invoke Lemma 3.1 to conclude the adversary's view is O(t^2/N)-close after projection; Theorem 4.4 and Theorem 5.1 then apply these with HP_{n,T} in place of the generic RSS distribution R. If the actual RSS error at T=30n is larger than O(1/N^2) (for example, O(1/N), or if reaching 1/N^2 requires T=Ω(n^2) rather than 30n), then the operator-norm bounds in Eq. (7) become O(1) per element, the union bound in Lemma 3.1 yields O(t^2) instead of O(t^2/N), and the projection into the distinct block subspace fails, invalidating the chain leading to both main theorems. The paper does not reproduce the proof of Theorem 10 nor state the exact constants, so this is a genuine load-bearing external assumption.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the parallel Kac's walk distribution HP_{n,T} on the unitary group U(N), N=2^n. Its main theorems state that for T=30n and d=5n, the distribution HP_{n,T+1} is computationally indistinguishable from the Haar distribution (Theorem 4.4), and that HP_{n,2T+1} is statistically indistinguishable even against adversaries allowed to make inverse queries, with an explicit bound 2t(11t+20)/N^{1/8} (Theorem 5.1). The proof proceeds by (i) importing an epsilon-RSS bound with epsilon=O(1/N^2) for HP_{n,30n} from [LQS+24, Theorem 10]; (ii) proving a projection lemma (Lemma 3.1) that an RSS operator followed by a random permutation leaves the adversary's recorded state in the distinct-block subspace; (iii) using the path-recording technique of [MH24] to compare the real oracle with a path-recording oracle; and (iv) extending this to a two-sided path-recording oracle V for the inverse-query result. The paper also explains how to derandomize the construction using QPRFs and QPRPs to obtain an efficient PRU.","tokens_in":53872,"tokens_out":20177,"duration_ms":170970,"significance":"If the proof is correct, this is a substantial result: it provides the first alternative construction of an adaptive-secure PRU beyond the PFC ensemble, confirms a conjecture in [LQS+24], and adds a strong-security guarantee against inverse queries. The manuscript is explicit about the quantitative bounds it proves and is careful in setting up the purified oracles and relation states. Its main strength is a modular reduction to a published scrambling theorem and to the path-recording framework of [MH24]. The principal correctness risk is the reliance on a very strong imported RSS bound, and the Section 5 proof currently contains several formally incorrect displays. These issues are significant but appear repairable without changing the asymptotic security claims.","major_comments":[{"comment":"The entire proof is conditional on the claim that HP_{n,30n} is an O(1/N^2)-RSS distribution, imported from [LQS+24, Theorem 10]. This bound is used in Lemma 3.1 to obtain the O(t^2/N) projection error, and every later lemma inherits it. The manuscript does not state the exact version of the theorem, the constants, or the parameter adjustment, and it does not reproduce the proof. Because O(1/N^2) is far stronger than the mixing bounds stated elsewhere for Kac-type walks, I request that the authors either include the full statement and a self-contained proof of the needed epsilon-RSS bound for T=30n, d=5n, or provide a precise page/theorem reference with enough detail to verify the parameter regime. Without this, both main theorems rest on an unverified external assumption.","section":"Section 4.1, Theorem 4.3"},{"comment":"The displayed chain at the end of the induction is not a valid proof. After establishing a lower bound of the form Re(...) >= 1 - 38t^2/N^{1/4} - 6t^{3/4}/N^{1/4} - 32*sqrt(t(t+1)/N), the text continues with '<= 1 - ...', then '<= ...', then '>= ...', reversing the inequality direction without explanation and introducing an extra N^{-1/4} factor in the second line. As printed, the claim does not follow. The intended bound appears repairable: for t>=1, one has 6t^{3/4} <= 6t and 32*sqrt(t(t+1)/N) <= 32(t+1)/N^{1/4}, which would give a lower bound of 1 - O(t^2/N^{1/4}), but the proof must be rewritten with consistent inequality directions.","section":"Section 5.4.1, Claim 5.25"},{"comment":"The final bound '<= 9t/N^{1/8}' does not follow from the preceding inequalities. The proof invokes |||u><u| - |v><v|||_1 <= 2|||u> - |v>||_2 and obtains |||u> - |v>||_2^2 <= 76t^2/N^{1/4}, which would yield 2*sqrt(76)t/N^{1/8} ~ 17.4t/N^{1/8}. To obtain 9t/N^{1/8} one needs the pure-state inequality TD <= sqrt(2(1-Re<u|v>)) <= sqrt(76)t/N^{1/8}, which is not the stated fact. The asymptotic negligibility is unaffected, but the quantitative lemma as proved is incorrect and must be corrected.","section":"Section 5.4.1, Lemma 5.27"}],"minor_comments":[{"comment":"References to 'Theorem 4.9' in the proofs of Lemma 4.8 and in Appendix A should be to 'Lemma 4.9'.","section":"Lemma 4.8 and Appendix A"},{"comment":"Appendix A contains duplicated case labels ('Case 2.1' and 'Case 2.1.2.2' appear twice), which makes the orthogonality argument harder to follow.","section":"Appendix A"},{"comment":"The right-invariance lemma is asserted as 'similar to [MH24, Lemma 4.3]' but the PR oracle here is modified (it excludes y in BIm(R) rather than y in Im(R)); please include the short proof or a precise statement of how the MH24 proof transfers.","section":"Lemma 2.8"},{"comment":"The section heading 'Cryptopgraphy' is a typo and should read 'Cryptography'.","section":"Section 2.4 heading"}],"recommendation":"major_revision","confidential_remarks":"The main theorem leans on a strong RSS bound from the same research group's earlier paper; I would ask the editor to ensure that the dependency is scrutinized, e.g., by requesting a detailed proof or an independent verification of the O(1/N^2) bound for T=30n. The formal errors in Section 5 are repairable and do not, in my view, undermine the asymptotic security claim, but they must be fixed before publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Short version: this paper confirms the conjecture from LQS+24 that a linear number of parallel Kac's walk steps forms an adaptive-secure PRU, and it adds statistical strong security against inverse-query adversaries. The result is genuinely new: prior work had the PFC-based PRU and the Kac walk as a state scrambler, but not the PRU theorem. The proof is not a routine extension. The authors adapt MH24's path-recording machinery to a different ensemble, define the HP-relation states and compress isometry, and extend the invariance argument to two-sided queries. The main theorems have explicit quantitative bounds, and the chain from RSS to projection to path recording to Haar indistinguishability is coherent.\n\nThe largest soft spot is exactly what the stress-test note says. Theorem 4.3 is imported from LQS+24: HP_{n,T} with T=30n, d=5n is epsilon-RSS with epsilon=O(1/N^2). Lemma 3.1 and every projection step after it need that specific bound. The paper does not reproduce the proof or state the exact constants, so this is a load-bearing external dependency. I do not see it as circular: the RSS theorem is an independent prior result, and the authors are the same group that proved it, so the citation pattern is not hiding a gap. But a referee should verify the parameter conversion, or the paper should include a proof sketch of that theorem, because if the RSS bound fails the entire PRU conclusion collapses.\n\nThe other issues are smaller. Claim 5.25 has a misprinted inequality in the induction chain; the direction is wrong as printed, though the intended argument is recoverable. Lemma 4.2 has a small hybrid-index slip. Several lemmas are borrowed from MH24 without proof; that is acceptable if the field trusts MH24, but for a standalone paper I would want precise references with constants, especially for the twirling lemma and the two-sided invariance claim. None of these appear to break the central argument.\n\nThe paper is not an efficiency breakthrough; PFC remains comparable. But an alternative PRU built from one repeated module, with inverse-query security, is a meaningful contribution to quantum pseudorandomness. The audience is researchers in quantum cryptography and anyone extending the path-recording technique.\n\nRecommendation: send it to peer review. Not a desk reject. Acceptance should be conditional on fixing the typos and making the dependence on LQS+24 Theorem 10 auditable, either by reproducing the proof or by stating its exact parameters and constants.","headline":"The paper proves the Kac-walk PRU conjecture with a substantial path-recording proof and adds inverse-query security; the main thing to check is the imported O(1/N^2) RSS bound from LQS+24.","tokens_in":54543,"tokens_out":1770,"would_cite":true,"duration_ms":19358,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"A linear number of repeated parallel Kac's walk steps is computationally indistinguishable from Haar-random unitaries, even against adversaries with inverse-query access.","keywords":["pseudorandom unitaries","parallel Kac's walk","path-recording technique","Haar-random unitaries","random state scrambler","inverse-query security","quantum cryptography"],"falsifier":"Take small qubit counts (n=6 through 12), run 30n rounds of the parallel Kac's walk on several random input states, and compare the two-copy output distribution with the Haar two-copy distribution in trace distance; the proof's projection lemma requires this distance to be O(1/$N^{2}$), so a measured rate slower than that at the stated step count would falsify the central theorem.","tokens_in":53388,"feed_emoji":"🎲","tokens_out":12718,"duration_ms":101971,"temperature":0.7,"pith_summary":"This paper claims that a linear number of sequential repetitions of the parallel Kac's walk forms a pseudorandom unitary family (PRU): after $T+1$ steps with $T=30n$ and $n$ qubits, the sampled unitary is computationally indistinguishable from the Haar measure on $U(N)$, where $N=2^n$. It further claims that $2T+1$ steps are statistically indistinguishable from Haar even to adversaries who may query both the unitary and its inverse. The construction is simply the repeated basic module of the walk—each step randomizes a permutation of the basis and applies independent $2\\times2$ Haar rotations on paired states—so if the result is correct, PRUs can be built by iterating a single primitive. This confirms a conjecture from the paper that introduced the parallel Kac's walk and gives another demonstration that the path-recording proof technique yields adaptive security.","feed_headline":"Linear Kac's walk steps yield secure pseudorandom unitaries","feed_subtitle":"Repeating the walk's random 2x2 rotation module 30n+1 times looks Haar-random, even to inverse-query adversaries.","key_machinery":"The load-bearing objects are the distinct block subspace, the purified function-permutation oracle HPO, and the Compress isometry. The distinct block subspace consists of tuples of basis states lying in different two-element blocks, where a block is a pair of strings sharing the length-$(n-1)$ suffix; Lemma 3.1 shows that an $O(1/N^2)$-random state scrambler (a distribution whose $t$-copy output on any pure state is $\\epsilon$-close to Haar) followed by a random permutation places any adversary state in this subspace up to error $O(t^2/N)$. HPO is the coherent version of one walk step: it records the sampled function $f$ and permutation $\\sigma$ in environment registers and applies $H_f P_\\sigma$ to the query register. The Compress isometry maps HPO's relation states $|\\phi_R\\rangle$ to the path-recording oracle's relation states $|R\\rangle$, and Lemma 4.13 shows that after projecting onto the distinct block subspace the two oracle views agree up to the same $O(t^2/N)$ error. Once the compressed view matches the path-recording oracle, the oracle's right-invariance property lets the proof move all adaptive queries into the environment, which is what renders the walk's output Haar-indistinguishable.","core_discovery":"The central theorem is that the distribution $\\mathrm{HP}_{n,T+1}$ with $T=30n$ and $d=5n$ is computationally indistinguishable from Haar random unitaries (Theorem 4.4), and that $\\mathrm{HP}_{n,2T+1}$ is statistically indistinguishable even against inverse-query adversaries: any $t$-query adversary distinguishing $\\mathrm{HP}_{n,2T+1}$ from Haar has advantage at most $2t(11t+20)/N^{1/8}$ (Theorem 5.1). The proof splits into two phases: the first $T$ rounds scramble the adversary's query history into the distinct block subspace, and the final round is analyzed through a purified function-permutation oracle and a path-recording oracle whose right invariance moves adaptive queries into an environment register. Replacing the random functions and permutations with quantum-secure pseudorandom counterparts makes the construction an efficient PRU under post-quantum one-way functions (Theorem 4.16).","pith_inferences":["An implication the authors leave implicit is that the two-phase proof only consumes the $O(1/N^2)$-random state scrambling property, so any scrambling family stable under one extra random permutation should plug into the same argument, making the result a template for PRU constructions.","The inverse-query proof sandwiches HPO between two scrambling blocks, one from the walk and one from Haar; the same sandwiching may give inverse-query security for other forward-secure PRU constructions whose path-recording oracle has two-sided invariance.","If the paper's suggested simplification—replacing the independent $2\\times2$ rotations by one shared rotation—preserves the $O(1/N^2)$-RSS bound, the construction would become a local random circuit PRU, which would resolve an open question in quantum complexity."],"forward_implications":["The distribution $\\mathrm{HP}_{n,30n+1}$ with $d=5n$ is computationally indistinguishable from Haar, so a linear number of parallel Kac's walk steps gives an adaptive-secure PRU.","The distribution $\\mathrm{HP}_{n,60n+1}$ is a statistical strong PRU: any $t$-query adversary with forward and inverse queries has distinguishing advantage at most $2t(11t+20)/N^{1/8}$.","When random functions and permutations are replaced by quantum-secure PRFs and PRPs, the resulting family is efficiently sampleable and is a PRU under the existence of post-quantum one-way functions.","The finite-precision approximation $\\widehat{\\mathrm{HP}}_{n,T+1}$ is computationally indistinguishable from $\\mathrm{HP}_{n,T+1}$, so the construction survives the truncation needed for actual circuit implementation."],"supporting_citations":[{"why":"Introduces the parallel Kac's walk and supplies Theorem 4.3, the O(1/N^2)-RSS bound at T=30n and d=5n, plus the approximation lemma for the implemented rotations.","marker":"[LQS+24]"},{"why":"Supplies the path-recording oracle, relation states, right-invariance lemma, and the adaptive-security proof template that the final Haar-indistinguishability step uses.","marker":"[MH24]"},{"why":"Provides the symmetric-subspace operator norm bound used to control the equal-pair projectors in Lemma 3.1.","marker":"[Har13]"},{"why":"Establishes quantum-secure pseudorandom functions, which replace the random functions in the efficient PRU construction.","marker":"[Zha21]"},{"why":"Gives quantum-secure pseudorandom permutations built from PRFs, which replace the random permutations in the efficient construction.","marker":"[Zha16]"}],"fun_headline_variants":["Parallel Kac walk yields adaptive-secure PRUs","Linear Kac repetitions defeat inverse-query attackers","Kac's walk: linear steps give strong PRU security","Parallel Kac: adaptive PRU from 30n+1 rounds"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The whole proof depends on the previously established claim that 30n steps of the parallel Kac's walk bring every input pure state to within O(1/$N^{2}$) of the Haar-random state, with N=2^n; if that scrambling claim is false or needs more steps, the projection into the distinct block subspace and the PRU conclusion do not follow.","fun_headline_variants_meta":{"raw":{"variants":["Parallel Kac walk yields adaptive-secure PRUs","Linear Kac repetitions defeat inverse-query attackers","Kac's walk: linear steps give strong PRU security","Parallel Kac: adaptive PRU from 30n+1 rounds"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000203,"raw_usage":{"total_tokens":1353,"prompt_tokens":882,"completion_tokens":471,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":498,"completion_tokens_details":{"reasoning_tokens":402}},"tokens_in":498,"tokens_out":471,"duration_ms":4378,"temperature":1.0,"reasoning_tokens":402,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T11:36:48.287257+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take small qubit counts (n=6 through 12), run 30n rounds of the parallel Kac's walk on several random input states, and compare the two-copy output distribution with the Haar two-copy distribution in trace distance; the proof's projection lemma requires this distance to be O(1/$N^{2}$), so a measured rate slower than that at the stated step count would falsify the central theorem.","supporting_citations":[],"review_version":1}