{"id":"4cae1049-27f4-4c8a-aaf1-1f7ff99f7022","arxiv_id":"2507.22535","paper_version":5,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"First scalable, quantum-accessible (ancilla-assisted), adaptive pseudorandom function-like quantum state generator from quantum-secure PRFs, built from an isometric Beta-sampling state preparation.","lead":"The authors construct a new way to prepare quantum states that are nearly Haar-random, using a qubit-by-qubit rotation procedure. This yields the first pseudorandom quantum function generator that is scalable, can accept quantum inputs entangled with an adversary's ancilla, and remains secure against adaptive queries.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 4.3 proof has an invalid base case in Appendix C: the initial total weight is constant 1, not χ²-distributed, so the induction does not start; the underlying Beta/χ² identity is true but requires a corrected proof.","rationale":"The paper's stated goal is a scalable, quantum-accessible, adaptive PRFS from QS-PRF. The load-bearing step is Lemma 4.3, which connects the Beta-splitting procedure to the Haar-random state's amplitude distribution; a failure there would invalidate the ARS stage and hence the PRFS. I examined the main construction and security proof. The base case of the induction in Appendix C is indeed wrong: |0>^n corresponds to a deterministic weight 1, not a χ²_{2^{n+1}} random variable. This is a genuine gap in the written proof. However, the underlying distributional identity is true (stick-breaking representation of Dirichlet), so the concern is fixable rather than fatal. I also checked the hybrid proof of Theorem 6.3 for the diamond-norm bound; there are algebra errors in the displayed simplification of the error terms (e.g., the step 2^m√(2^n n)ε1 = √n 2^{-λ/2}), but the corrected expression is still negligible in λ, so this does not threaten the central claim. No machine-checked proof or code is provided, consistent with the reader's CONDITIONAL verdict. Since the reader already identified the same weakest point and assigned CONDITIONAL, no verdict change is needed; the paper should add a corrected proof of Lemma 4.3.","tokens_in":40646,"tokens_out":23505,"duration_ms":286063,"concrete_test":"Give a correct proof of Lemma 4.3 without the false base case: e.g., start from the leaves with C_z ~ χ²_2 i.i.d., define W_{t,z} as the subtree sum, and show by backward induction that the conditional ratios have Beta(2^{n-t-1},2^{n-t-1}) and are independent; equivalently, verify that after all splits the leaf weight vector equals (C_z/Σ C_z) in distribution. A concrete minimal check: for n=2, compute the joint density of the four leaf weights from Algorithm 1 and confirm it is the Dirichlet(1,1,1,1) density. If exact equality holds, the base-case flaw is a proof artifact; if not, the ARS/PRFS construction is unsound.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central construction rests on Lemma 4.3, which asserts that the qubit-by-qubit Beta-splitting procedure produces the random amplitudes state (Definition 4.2). The proof in Appendix C proceeds by induction on t, maintaining that after t iterations the weights W_{t,z} are i.i.d. χ²_{2^{n-t+1}}. The base case t=0 is the state |0>^⊗n, which would require W_{0,∅} ~ χ²_{2^{n+1}}; but the actual initial weight is the constant 1. A constant is not a chi-squared random variable, so the induction hypothesis is false at the base and the proof cannot start. If the claimed identity were false, the amplitudes produced by Algorithm 1 would not be those of a Haar-random state, and Theorem 6.4 would fail. The identity is in fact true — sequential Beta splitting with parameters 2^{n-t-1} yields the Dirichlet(1,...,1) distribution of normalized χ²_2 weights — but the paper does not supply a correct proof. Thus the main theorem is currently supported by an invalid proof step, although the gap appears patchable.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper presents an isometric procedure for generating quantum states that are statistically close to Haar-random states when given oracle access to a truly random function, and pseudorandom when the random function is replaced by a quantum-secure PRF. The construction prepares random amplitudes by sequential Beta splitting in superposition, then applies random phases, yielding a scalable and isometric PRS. The same procedure is extended to accept an m-qubit input register, giving a scalable, adaptive, and ancilla-assisted quantum-accessible PRFS. The claimed results are Theorem 5.1 (scalable isometric PRS from quantum-secure PRF) and Theorem 6.4 (scalable, quantum-accessible, adaptive PRFS from quantum-secure PRF, hence from quantum-secure OWF). The paper includes detailed hybrid arguments, finite-precision bounds, a diamond-norm analysis for the PRFS, and a long appendix with classical sampling algorithms for the rounded Beta distribution.","tokens_in":40877,"tokens_out":6329,"duration_ms":76205,"significance":"If the main theorems are correct, this is the first construction of a PRFS that is simultaneously scalable, adaptive, and quantum-accessible in the strong ancilla-assisted sense, and it unifies several previously separate PRFS variants. The technical core is appealing: the qubit-by-qubit Beta-splitting method inspired by Grover-Rudolph is a genuinely different route from prior rejection-sampling constructions, and it gives an isometry rather than a channel with junk. The paper is commendably detailed: it provides explicit finite-precision bounds, full hybrid proofs, and a self-contained classical algorithm for rounded Beta sampling with a rigorous error analysis in Appendix G. There are no fitted parameters, and the security benchmark is the standard Haar measure, so the construction is falsifiable in the usual cryptographic sense. However, the central theorem currently rests on a lemma whose proof has an invalid base case, and the main PRFS theorem contains a length-parameter inconsistency in the key generation step; both issues are local and appear patchable.","major_comments":[{"comment":"The sampling algorithm A_RB is presented as deterministic and polynomial-time, but its precision parameter m_1 is chosen as 3m+3+ceil(log2(eta+3)), where eta is the constant asserted to exist in Lemma H.4. Lemma H.4 proves existence of such an eta by a limiting argument but does not provide an explicit value or an effective bound. Without an explicit universal constant, the construction of A_RB is not fully explicit, although the proof could be made constructive by computing a numerical bound in Lemma H.4. This does not affect the asymptotic correctness of the reduction, but it should be addressed for the paper's claim of an explicit sampling algorithm.","section":"Appendix G, Lemma G.5 and Lemma H.4"}],"minor_comments":[{"comment":"The states in Figure 2 are labeled with strings such as '|000⟩' that appear multiple times in different branches, which makes the figure hard to parse; using explicit binary prefixes would improve clarity.","section":"Figure 2"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"You should know about this paper: it's the first PRFS construction that is simultaneously scalable, quantum-accessible in the strong ancilla-assisted sense, and adaptive, assuming a quantum-secure PRF/OWF. The core idea is clean: prepare Haar-like states by recursively splitting a total weight with Beta random variables, done reversibly with a PRF supplying the randomness. This gives an isometric preparation procedure, unlike Brakerski–Shmueli's rejection sampling, so it naturally extends to a PRFS oracle. The security proof uses the right tools—diamond norm bounds for ancilla-assisted adversaries, with the exponential-in-m loss absorbed by scalability. The comparison tables and the discussion of LQS+24 are accurate and useful.\n\nThe paper is not yet correct as written. Lemma 4.3 in Appendix C claims that after t iterations the weights W_{t,z} are i.i.d. chi-squared with 2^{n-t+1} degrees of freedom. The base case t=0 has W_{0,∅}=1, a constant, not chi-squared, so the induction cannot start. The stress-test is right about that. However, the underlying distributional claim is true: sequential Beta splitting from a constant total with parameters 2^{n-t-1} produces Dirichlet(1,...,1) normalized weights, which is exactly the random-amplitudes distribution. This is patchable by a different induction (e.g., show W_t ~ Dirichlet(2^{n-t},...,2^{n-t})). So the main theorem rests on a repairable gap, not a false lemma.\n\nOther soft spots are minor. The appendices are long but mostly careful; the sampling algorithm's error analysis is genuinely detailed. The paper provides no code or machine-checked proof, so the conditional verdict is fair, but the construction and reductions are explicit and the math is close to complete.\n\nThis paper is for the microcrypt/quantum crypto theory crowd. I'd bring it to reading group: the Beta-splitting technique and the diamond-norm argument are worth understanding. I would not desk-reject it. Send it to peer review; the authors need to fix the Lemma 4.3 proof before acceptance, but the contribution deserves referee time.","headline":"Strong new construction for scalable, ancilla-assisted adaptive PRFS with a repairable proof gap in the Beta-splitting lemma.","tokens_in":41397,"tokens_out":4490,"would_cite":true,"duration_ms":49068,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["81P68","94A60"],"pacs":["03.67.Dd","03.67.Lx"],"model":"deepseek-v4-flash","headline":"This paper constructs the first pseudorandom quantum function-like state generator that is simultaneously scalable, fully quantum-accessible (even on entangled ancilla-assisted queries), and adaptive, assuming quantum-secure one-way…","keywords":["pseudorandom quantum states","pseudorandom function-like quantum states","scalability","quantum accessibility","adaptive security","isometric construction","Beta distribution","one-way functions"],"falsifier":"Simulate the random-amplitudes procedure for, say, n = 10 qubits with exact arithmetic, drawing independent Beta($2^{{n-t-1}}$, $2^{{n-t-1}}$) variables at the prescribed prefixes and forming the state; compare the empirical distribution of the squared coefficients to the normalized chi-squared-2 distribution over many samples, and separately test the first split where the initial total weight 1 is a constant rather than a chi-squared random variable. A statistically significant deviation, or a failure at that base case, would refute Lemma 4.3 and hence the core construction.","tokens_in":40453,"feed_emoji":"🔐","tokens_out":6870,"duration_ms":76652,"temperature":0.7,"pith_summary":"This paper builds pseudorandom quantum states (PRS) and pseudorandom function-like quantum states (PRFS) that are scalable, meaning the security parameter can grow independently of the number of qubits, and, for PRFS, secure against adaptive quantum queries even when the query state is entangled with an adversary's ancilla. The central technical step is an isometric procedure that prepares states whose amplitudes match a normalized complex Gaussian vector by splitting a total weight with independent Beta random variables and rotating qubits one at a time. Replacing the random function in this procedure by a quantum-secure pseudorandom function yields a scalable, isometric PRS, and feeding the PRFS input into the function yields the first PRFS that is simultaneously scalable, fully quantum-accessible, and adaptive. If correct, this unifies several PRFS variants under one construction and places scalable quantum-accessible PRFS inside the standard world of quantum-secure one-way functions.","feed_headline":"First fully quantum-accessible adaptive PRFS built","feed_subtitle":"New isometric construction makes pseudorandom quantum function states scalable and safe against entangled queries.","key_machinery":"The load-bearing object is the 'random amplitudes' isometric procedure. To prepare a state with coefficients equal to the square roots of independent chi-squared-2 random variables (so that normalized coefficients match Gaussian amplitudes), the algorithm recursively splits a total weight: at depth t, for each prefix z it samples an independent Beta($2^{{n-t-1}}$, $2^{{n-t-1}}$) variable and rotates the next qubit by the angle whose cosine-squared is that sample; the Beta-to-Gamma ratio identity then makes subtree weights follow chi-squared distributions, matching the Haar-random amplitude profile. The sampling is done in superposition by using the prefix as a seed to a classical Beta sampler and applying controlled rotations, giving an isometry rather than a state with discarded junk. A final random-phase step converts the real amplitudes into the complex Gaussian vector, and replacing the random function with a quantum-secure pseudorandom function turns the statistical closeness into computational pseudorandomness.","core_discovery":"The paper's main theorem states that, assuming a quantum-secure pseudorandom function family (which exists if quantum-secure one-way functions exist), there is a scalable, quantum-accessible, adaptive PRFS generator: for any polynomial input length m and output length n, a keyed family of isometries maps superposition inputs to an output register containing |x> followed by a state |ψ_x> that is computationally indistinguishable from a uniformly random (Haar-random) quantum state, and the adversary may query on states entangled with ancillas. The proof works through an asymptotically random state generator that, given oracle access to a random function, prepares a state within negligible trace distance of Haar-random, then replaces the random function by a quantum-secure PRF. For the PRFS, the input x is concatenated with each sampling prefix inside the oracle so that different inputs receive independent randomness; security against ancilla-assisted adversaries is obtained by bounding the diamond-norm distance through the Choi representation, paying a factor of 2^m that scalable parameters absorb.","pith_inferences":["The Beta-splitting template is not tied to chi-squared amplitudes: any distribution whose prefix-sum ratios are independent and efficiently samplable would yield the same isometric preparation, so the same code could port to other target ensembles with different coefficient statistics.","The ancilla-assisted security proof pays a 2^m factor from the Choi bound, and scalability is what absorbs it; a non-scalable version of the same isometry would be insecure against entangled queries, which helps explain why earlier non-scalable PRFS constructions stopped at pure-input access.","A concrete stress test of the construction is whether the recursive Beta-splitting identity remains exactly true when the initial total weight is the constant 1 rather than a chi-squared random variable, since the appendix's induction treats that base case informally."],"forward_implications":["A scalable, isometric PRS exists from quantum-secure PRFs, removing the logarithmic-qubit restriction of earlier phase-state PRS constructions.","A scalable, fully quantum-accessible (ancilla-assisted), adaptive PRFS exists from quantum-secure PRFs, the first construction with all three properties together.","The same PRFS construction yields long-input PRFS, short-input PRFS, short-output PRFS, non-adaptive PRFS, and classically-accessible adaptive PRFS as corollaries, and through known implications gives PRS, SB-QCOM, pseudo-encryption, CCA1-qPKE with quantum ciphers, and PD-PRF.","If a black-box separation between one-way functions and scalable PRFS is ever shown, this construction marks a natural boundary: a cryptography world without one-way functions that still contains all of those primitives."],"supporting_citations":[{"why":"Defines PRS and supplies the phase-state baseline that the new construction supersedes on scalability.","marker":"[JLS18]"},{"why":"Gives the first scalable PRS via quantum rejection sampling; its lack of isometry is the gap the paper fills.","marker":"[BS20]"},{"why":"Introduces PRFS and its selective-security definition, the primitive that is extended to adaptive ancilla-assisted security.","marker":"[AQY22]"},{"why":"Provides the classically- and quantum-accessible adaptive PRFS definitions and the applications that the new PRFS inherits.","marker":"[AGQY22]"},{"why":"Shows quantum-secure one-way functions imply quantum-secure PRFs, the assumption underlying the main theorems.","marker":"[Zha21]"},{"why":"Supplies the qubit-by-qubit rotation idea that the paper adapts by sampling Beta variables from prefixes.","marker":"[GR02]"},{"why":"Gives the prior scalable isometric PRS (quantum pseudorandom scramblers) and its limited PRFS implications, the comparison point for full scalability and ancilla-assisted security.","marker":"[LQS+24]"},{"why":"Supplies the Gamma sampling routine whose rounded version makes the Beta sampler efficient and finite-precision.","marker":"[MT00]"},{"why":"Gives the Box-Muller transform used to turn random phases on chi-squared amplitudes into Gaussian coefficients.","marker":"[BM58]"},{"why":"Provides the Choi and diamond-norm facts used to bound distinguishing advantage when the adversary holds entangled ancillas.","marker":"[Wat18]"}],"fun_headline_variants":["Quantum-accessible PRFS that scale and adapt","Entangled-query PRFS: now scalable and adaptive","Fully quantum-accessible adaptive PRFS achieved","PRFS resilient to entangled quantum input"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The construction rests on the identity that recursively splitting a fixed total weight of 1 by a binary tree of independent Beta random variables produces exactly the same distribution as the normalized squared amplitudes of independent Gaussian-square (chi-squared) variables; if that identity fails, the prepared states are no longer Haar-like.","fun_headline_variants_meta":{"raw":{"variants":["Quantum-accessible PRFS that scale and adapt","Entangled-query PRFS: now scalable and adaptive","Fully quantum-accessible adaptive PRFS achieved","PRFS resilient to entangled quantum input"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000285,"raw_usage":{"total_tokens":1706,"prompt_tokens":997,"completion_tokens":709,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":613,"completion_tokens_details":{"reasoning_tokens":650}},"tokens_in":613,"tokens_out":709,"duration_ms":8742,"temperature":1.0,"reasoning_tokens":650,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T11:36:04.809748+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate the random-amplitudes procedure for, say, n = 10 qubits with exact arithmetic, drawing independent Beta($2^{{n-t-1}}$, $2^{{n-t-1}}$) variables at the prescribed prefixes and forming the state; compare the empirical distribution of the squared coefficients to the normalized chi-squared-2 distribution over many samples, and separately test the first split where the initial total weight 1 is a constant rather than a chi-squared random variable. A statistically significant deviation, or a failure at that base case, would refute Lemma 4.3 and hence the core construction.","supporting_citations":[],"review_version":1}