{"id":"99d018b2-880e-4bfa-95a5-c3f5e262bef9","arxiv_id":"2506.15547","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"A quasi-linear-time version of Raz's two-source extractor with reduced entropy requirements, quantum-proof variants, and an open-source implementation.","lead":"Raz's two-source extractor, which combines a high-entropy and a low-entropy source, has been made practical: the authors give a version that runs in quasi-linear time instead of quartic time, with weaker entropy requirements. The work includes an explicit theorem, an open-source implementation, and a numerical tool for choosing parameters.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1's proof depends on Eq. (B14), whose key inequality is false for parameters satisfying the theorem's own hypotheses, so the claimed entropy improvement is not established as written.","rationale":"The reader's weakest-assumption analysis correctly identifies Eq. (B14) as the load-bearing flaw: it is the only place where the proof of Theorem 1 establishes the crucial lower bound on -log(γ1), and the inequality is demonstrably false under the theorem's own hypotheses. The numerical counterexample is valid and confirms the proof gap. I agree with the reader's assessment that this is likely repairable, because a direct estimate using m ≤ n1/2 and n1-k1 ≤ n1 bypasses the faulty expression and appears to yield the same final error bound. The paper has independent support from the quasi-linear-time construction, the NTT-based implementation, and the open-source code, so the central idea is not undermined. However, as written the theorem is not proven, so a conditional verdict is appropriate. The additional typos in the strong-extractor parameters (k'_2 written with k1 instead of k2) are related but secondary; they do not affect the weak-extractor theorem, which is the core contribution.","tokens_in":27424,"tokens_out":10449,"duration_ms":89790,"concrete_test":"Re-derive the Case 1 bound without invoking Eq. (B14): from the theorem's assumptions confirm m ≤ n1/2 and n1-k1 ≤ n1, so m(n1-k1) ≤ n1^2/2, and hence floor(log(m(n1-k1)))+1 ≤ 2log(n1). Then verify that substituting this estimate into the proof's chain (B15)-(B19) yields -log(γ1) ≥ 2(λm+1) for all parameters satisfying (B5)-(B7). If the substituted chain holds, Theorem 1 is recoverable; if not, the central entropy claim remains unproved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central theorem needs, in Case 1, the lower bound -log(γ1) ≥ 2(λm+1). To obtain it, the proof uses Eq. (B14), which asserts floor(log(m(n1-k1))) < log(k2/(λ32(n1-k1))). This is claimed to follow from (B7), δ<1/2, and λ>1/4, but the implication is invalid: (B7) gives m ≤ (1/λ)(δk2/16 - 1) < k2/(32λ), so m(n1-k1) < k2(n1-k1)/(32λ), not k2/(λ32(n1-k1)). For allowed parameters (n1=10^4, k1=8·10^3, k2=10^2, δ=0.4, λ=0.3, m=5), all theorem hypotheses hold, but floor(log(m(n1-k1))) = floor(log(10^4)) = 13, while log(k2/(λ32(n1-k1))) = log(100/19200) ≈ -7.58. Thus the inequality fails by a large margin. Consequently, the proof's control of -log(γ1) is unsupported, and Theorem 1's reduced k1 requirement is not derived. A local repair appears available: since m ≤ n1/2 and n1-k1 ≤ n1, one gets m(n1-k1) ≤ n1^2/2, hence floor(log(m(n1-k1)))+1 ≤ 2log(n1), which together with k1 ≥ (1/2+δ)n1 + 2log(n1) recovers -log(γ1) ≥ δk2/8 ≥ 2(λm+1). This suggests the theorem may be salvageable, but the argument as printed is broken at this step.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The manuscript proposes an efficient implementation of Raz's two-source extractor by instantiating the fast (p',ζ)-biased generator of Meka et al. within Raz's framework. It claims a quasi-linear runtime O(n1 log(n1)^2), an improved analytic theorem with weaker entropy requirements, strong and quantum-proof variants, and an open-source implementation in the Cryptomite library with numerical parameter optimization. The central advertised results are Theorem 1 (explicit efficient extractor with weak/strong forms) and Corollary 1 (quantum-proof version in the Markov model), together with extensive numerical comparisons and benchmarks.","tokens_in":27778,"tokens_out":8727,"duration_ms":78694,"significance":"If the main theorem is correct, the result is a valuable practical and theoretical contribution: it removes the O(n^4) runtime bottleneck of the original Raz construction, achieves quasi-linear time, improves the analytic entropy/error trade-off, and provides a usable implementation with benchmarks up to n1 ≈ 1.5×10^8. The open-source code and the numerical parameter module are concrete strengths, as is the careful reproduction of the Meka et al. generator analysis. However, the main theorem is not proven as written because a central inequality in Appendix B2 is false; the contribution is contingent on repairing that step. The gap appears local and likely fixable, but it directly affects the claimed parameter range of Theorem 1.","major_comments":[{"comment":"The inequality chain labelled (B14) is false. From assumption (B7), m ≤ (1/λ)(δk2/16−1), and the bounds δ<1/2 and λ>1/4 only give m(n1−k1) < k2(n1−k1)/(32λ); they do not imply floor(log(m(n1−k1))) < log(k2/(λ32(n1−k1))). For parameters satisfying the theorem's hypotheses, e.g. n1=10^4, δ=0.4, k1=9100, k2=100, λ=0.3, m=5, the left-hand side is floor(log(4500))=12 while the right-hand side is log(100/8640)≈−6.43. This invalidates the positivity argument and the subsequent lower bound on −log(γ1) in Case 1, so the claimed error bound ϵ≤2^{(1−4λ)m/2−1} is not proven for the stated parameter range. A repair is plausible (e.g. bounding floor(log(m(n1−k1))) by 2log n1 using m≤n1/2 and n1−k1≤n1), but the proof as printed is broken at this step.","section":"Appendix B2, Eq. (B14)"},{"comment":"The statement of Theorem 1 requires only k1 ≥ (1/2+δ)n1 + 2 log(n1) in Eq. (18), while the proof in Eq. (B5) assumes k1 ≥ (1/2+δ)n1 + 2 log(n1) + 1. The extra +1 is used in the final positivity step of Case 1 (the last inequality of (B14) and the line 'last follows from (B5)'). The theorem therefore claims a wider parameter range than the proof actually establishes; the statement, the appendix, and Corollary 1 (which does include the +1) should be reconciled.","section":"Theorem 1 statement vs Appendix B2, Eq. (B5)"}],"minor_comments":[{"comment":"The strong-extractor entropy parameter k'_2 is printed as k'_2 = k1 + m/2 + 2 + log(1/γ); it should be k2 + m/2 + 2 + log(1/γ), as in Corollary 2 and Eq. (B8).","section":"Lemma 5(ii), Eq. (B2)"},{"comment":"The algorithm reuses the symbols δ and ζ for local convolution variables, while δ and ζ denote the entropy-advantage and bias parameters elsewhere in the paper; this makes the pseudo-code hard to follow and should be changed.","section":"Algorithm 1"},{"comment":"The text says n1=10^4 is fixed and α1 is varied, while the caption of Fig. 2 says k1=0.8×10^4 is fixed; these describe different parameter settings and should be aligned.","section":"Section IV.B / Fig. 2 caption"},{"comment":"The phrase 'the constraint k2≤n2≤n1/2' implicitly uses the fact that an (n2,k2)-source satisfies k2≤n2; this implicit convention should be stated explicitly.","section":"Appendix B2, Case 2"}],"recommendation":"major_revision","confidential_remarks":"The paper contains a genuine practical contribution, and the gap in Eq. (B14) appears repairable, so I recommend major revision rather than rejection. The authors should also verify that the numerical comparisons in Section IV are based on the corrected theorem or on the direct optimization of Lemma 5, since the analytic curve labelled 'This work, λ optimized' depends on Theorem 1."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"This paper is worth knowing about for two reasons. First, it makes Raz's two-source extractor quasi-linear time by using the Meka et al. small-bias generator, and it ships working code in Cryptomite with benchmarks up to n1 ~ 1.5e8. That is a genuine practical advance, and the runtime claim O(n1 log^2 n1) is supported by the construction and the timing plots. The NTT implementation avoids FFT rounding, the parameter optimization module is a nice addition, and the numerical comparisons with Raz05 and Foreman23 are informative.\n\nThe weak spot is the new analytic theorem, Theorem 1. The proof in Appendix B2 contains an invalid inequality right at the point where it needs to bound -log γ1. Eq. (B14) asserts floor(log(m(n1-k1))) < log(k2/(λ32(n1-k1))), but the hypothesis m ≤ (1/λ)(δk2/16 - 1) with δ<1/2 gives m(n1-k1) < k2(n1-k1)/(32λ), not k2/(λ32(n1-k1)). The printed bound drops a factor (n1-k1) into the wrong place. For n1=10^4, k1=8e3, k2=100, δ=0.4, λ=0.3, m=5 (all permitted by the theorem), the left side is log(10^4)≈13 and the right side is negative, so the inequality fails by a mile. That means the claimed reduction in k1 does not follow from the proof as written.\n\nI think a local repair exists: since m ≤ n1/2, you get m(n1-k1) ≤ n1^2/2, so floor(log(m(n1-k1)))+1 ≤ 2 log n1, and the k1 bound would give -log γ1 ≥ δk2/8 ≥ 2(λm+1). But the argument printed in the paper is broken at this step, and the theorem is not established as is. There are also small typos: the main-text statement of Theorem 1 omits the +1 that appears in the appendix version, and Lemma 5 and Corollary 1 write k'_2 with k1 instead of k2. Those are easy fixes.\n\nNone of this undermines the construction, Lemma 5, or the code. The practical contribution stands. But the paper overclaims with Theorem 1 as a new analytic result, and a referee should require a corrected proof or a clear downgrade.\n\nWho is this for? Anyone who needs an efficient two-source extractor in practice, especially QKD privacy amplification or randomness amplification. The theoretical claims need caution until the proof is fixed. I would send it to peer review — it deserves referee time — but with the expectation of major revisions to the theorem proof before acceptance.","headline":"Practical Raz extractor with real code and good benchmarks, but Theorem 1's proof has a false inequality at Eq. (B14); the construction may be fine, the analytic claim needs a fix.","tokens_in":28316,"tokens_out":3677,"would_cite":true,"duration_ms":33490,"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":"This paper presents a quasi-linear-time version of Raz's two-source extractor with reduced entropy requirements, strong and quantum-proof variants, and an open-source implementation.","keywords":["two-source extractor","Raz extractor","quasi-linear time","biased generator","min-entropy","quantum-proof","number-theoretic transform","randomness extraction"],"falsifier":"Check Eq. (B14) at the permitted parameters $n_1=10^6$, $k_1=900100$, $k_2=100$, $\\delta=0.4$, $\\lambda=0.3$, $m=5$: the inequality $\\lfloor \\log(m(n_1-k_1))\\rfloor < \\log(k_2/(\\lambda 32(n_1-k_1)))$ becomes $18 < -13$, which is false, showing the proof chain in Theorem 1 breaks for allowed parameters.","tokens_in":27215,"feed_emoji":"🎲","tokens_out":13669,"duration_ms":109290,"temperature":0.7,"pith_summary":"This paper presents an implementation of Raz's two-source extractor that runs in $O(n_1\\log(n_1)^2)$ time, together with a theorem that lowers the min-entropy requirements on the two sources and allows the output length to be tuned. If correct, this makes Raz's construction practical for large inputs and extends it to strong and quantum-proof settings. An open-source implementation and a parameter-optimization module are also provided.","feed_headline":"Raz extractor runs in quasi-linear time with reduced entropy needs","feed_subtitle":"A fast biased generator yields O(n log^2 n) extraction, with strong and quantum-proof variants and ready-to-use code.","key_machinery":"The engine is the fast $(p',\\zeta)$-biased generator $G(\\beta,\\nu)_\\alpha = \\nu \\sum_{i=0}^{p'-1}(\\alpha\\beta)^i$ over $\\mathrm{GF}(2^t)$, whose output block for any index $\\alpha$ is computed in $O(\\log p')$ field operations via the identity $\\sum_{i=0}^{p'-1}(\\alpha\\beta)^i = \\prod_{j=0}^{\\log p'-1}(1+(\\alpha\\beta)^{2^j})$. This replaces the two-step construction used by Raz (strings $\\zeta$-biased for linear tests followed by $p'$-wise independent strings) that caused the $O(n_1^4)$ runtime. The paper matches generator parameters to the extractor by setting the seed length $n_1 = r+t$ with $r=t=n_1/2$, choosing the second source to index the output block, and using circulant-matrix arithmetic over $\\mathrm{GF}(2^t)$ to make each convolution fast; the final implementation uses the number-theoretic transform for exact arithmetic.","core_discovery":"The central theorem claims: for $n_2\\le n_1/2$, $k_1\\ge (1/2+\\delta)n_1+2\\log(n_1)$, $k_2\\ge \\max(3.2\\log(8n_1/k_2),40)$, and $m\\le (1/\\lambda)(\\delta k_2/16-1)$ with $0.25<\\lambda<(\\delta k_2/16-1)$, there exists an explicit two-source extractor with error $\\epsilon\\le 2^{(1-4\\lambda)m/2-1}$ computable in $O(n_1\\log(n_1)^2)$ time, plus a strong version with slightly larger error. The construction instantiates Raz's template using the fast $(p',\\zeta)$-biased generator of [42], splitting the first source into two halves that set the finite-field element and the scalar, letting the second source choose an output block, and reading off the first $m$ bits. The paper also derives a quantum-proof version in the Markov model and reports numerical parameter optimizations that outperform the analytic bounds at finite sizes.","pith_inferences":["The same fast biased generator could be dropped into other extractor constructions that call for biased linear-test generators, potentially lowering their computational complexity as well; this is not explored in the paper.","The paper's numerical observation that finite-size optimization beats asymptotic theorems suggests that other extractor analyses could benefit from parameter-search modules rather than closed-form bounds.","The restriction $n_2 \\le n_1/2$ arises from the efficient parameter matching ($r=t=n_1/2$); removing this restriction or randomizing the block choice might yield efficient Raz extractors for longer second sources, an open direction the paper flags."],"forward_implications":["Raz's extractor becomes usable for input sizes up to $n_1 \\approx 1.5\\times 10^8$, where the original $O(n_1^4)$ implementation is prohibitive, making two-source extraction viable for practical randomness amplification and quantum key distribution privacy amplification.","The new analytic theorem reduces the entropy requirement on the first source to $k_1 \\ge (1/2+\\delta)n_1 + 2\\log(n_1)$ and on the second to logarithmic min-entropy, with output length tunable by $\\lambda$.","The strong and quantum-proof versions retain quasi-linear computation time, so they can be composed with seeded extractors such as those in [4] or [2] to extend the output length.","The numerical parameter module shows that optimizing $p$ and $p'$ at finite sizes outperforms the asymptotic analytic theorems, giving larger output or lower entropy rates for fixed error.","The implementation using the number-theoretic transform avoids floating-point rounding, so the extractor output is exact."],"supporting_citations":[{"why":"Supplies the original Raz extractor construction and its parameter framework that this work inherits.","marker":"[6]"},{"why":"Provides the fast $(p',\\zeta)$-biased generator whose $O(\\log p')$ block computation is the source of the quasi-linear runtime.","marker":"[42]"},{"why":"Gives the fast finite-field/circulant-matrix arithmetic used to implement the generator efficiently.","marker":"[4]"},{"why":"Supplies the Markov-model lemma that converts the classical extractor into a quantum-proof one.","marker":"[37]"},{"why":"Documents the $O(n_1^4)$ runtime of prior Raz implementations and serves as the comparison point for the strong extractor.","marker":"[17]"}],"fun_headline_variants":["Quasi-linear two-source extractor cuts entropy needs","Fast Raz extractor: quasi-linear time, reduced entropy","Improved Raz two-source extractor runs in quasi-linear time","Efficient two-source extractor with quantum-proof variant","Raz extractor gets quasi-linear speedup and lower entropy"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The main theorem's proof assumes a logarithmic inequality that is false for some of the parameter values the theorem itself permits, so the claimed reduction in entropy requirements is not proven as written.","fun_headline_variants_meta":{"raw":{"variants":["Quasi-linear two-source extractor cuts entropy needs","Fast Raz extractor: quasi-linear time, reduced entropy","Improved Raz two-source extractor runs in quasi-linear time","Efficient two-source extractor with quantum-proof variant","Raz extractor gets quasi-linear speedup and lower entropy"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000166,"raw_usage":{"total_tokens":1256,"prompt_tokens":951,"completion_tokens":305,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":567,"completion_tokens_details":{"reasoning_tokens":225}},"tokens_in":567,"tokens_out":305,"duration_ms":3033,"temperature":1.0,"reasoning_tokens":225,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T19:34:07.223278+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Check Eq. (B14) at the permitted parameters $n_1=10^6$, $k_1=900100$, $k_2=100$, $\\delta=0.4$, $\\lambda=0.3$, $m=5$: the inequality $\\lfloor \\log(m(n_1-k_1))\\rfloor < \\log(k_2/(\\lambda 32(n_1-k_1)))$ becomes $18 < -13$, which is false, showing the proof chain in Theorem 1 breaks for allowed parameters.","supporting_citations":[{"cited_title":"Extractors with weak random seeds","cited_arxiv_id":null,"evidence_quote":"Supplies the original Raz extractor construction and its parameter framework that this work inherits."},{"cited_title":"Targeted lossy functions and applications","cited_arxiv_id":null,"evidence_quote":"Provides the fast $(p',\\zeta)$-biased generator whose $O(\\log p')$ block computation is the source of the quasi-linear runtime."},{"cited_title":"leaking operation","cited_arxiv_id":null,"evidence_quote":"Gives the fast finite-field/circulant-matrix arithmetic used to implement the generator efficiently."},{"cited_title":"Extractors: Low entropy requirements colliding with non- malleability","cited_arxiv_id":null,"evidence_quote":"Supplies the Markov-model lemma that converts the classical extractor into a quantum-proof one."},{"cited_title":"Non-malleable extractors, two-source extractors and privacy amplification","cited_arxiv_id":null,"evidence_quote":"Documents the $O(n_1^4)$ runtime of prior Raz implementations and serves as the comparison point for the strong extractor."}],"review_version":2}