Pith. sign in

REVIEW 2 major objections 4 minor 68 references

An efficient construction of Raz's two-source randomness extractor with improved parameters

T0 review · 2 major / 4 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2506.15547 v1 pith:64EPU3JN submitted 2025-06-18 cs.CR cs.CCquant-ph

Cameron Foreman , Lewis Wooltorton , Kevin Milner , Florian J. Curchod This is my paper · ORCID
classification cs.CRcs.CCquant-ph
keywords two-sourceextractorRazquasi-lineartimebiasedgeneratormin-entropyquantum-proofnumber-theoretictransformrandomnessextraction
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

  • 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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • 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.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 4 minor

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.

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 (2)
  1. [Appendix B2, Eq. (B14)] 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.
  2. [Theorem 1 statement vs Appendix B2, Eq. (B5)] 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.
minor comments (4)
  1. [Lemma 5(ii), Eq. (B2)] 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).
  2. [Algorithm 1] 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.
  3. [Section IV.B / Fig. 2 caption] 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.
  4. [Appendix B2, Case 2] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the central extractor theorem is derived from external lemmas (Raz; Meka et al.; Arnon-Friedman et al.), with same-author references confined to code, comparisons, and future-work remarks.

full rationale

No circular dependency found. Theorem 1 is proved by instantiating the external (p',ζ)-biased generator of Meka et al. inside Raz's extractor lemma (Lemma 2), choosing l = floor(log(m(n1-k1))), ζ = 2^{l-n1/2}, and then deriving the entropy requirements from explicit inequalities (B5)-(B7). The error bound follows from bounding -log(γ1) and -log(γ2) using those stated constraints; the parameter choices are not fitted to the theorem's conclusion. The quantum-proof corollaries invoke the external generic reduction of Arnon-Friedman et al. (Lemma 1), not a self-citation chain. The only same-author references are [5] (the Cryptomite code library), [17] (a prior strong Raz construction used for numerical comparison), and [54] (future work); none of these is a premise in the proof of Theorem 1 or in Corollaries 1-2. The critique that Eq. (B14) contains a false inequality, if accurate, is a correctness defect in the proof's algebra rather than a circularity: a broken inequality step does not make the theorem equivalent to its inputs by construction. Accordingly, the paper is self-contained against external benchmarks for its central derivation, and no circular step can be exhibited.

Assumptions & free parameters 4 free parameters · 5 assumptions · 0 invented entities

All free parameters are internal to the construction and optimized numerically; the derivation does not fit any data. The main external inputs are the Meka et al. generator (with proof reproduced) and the Raz proof template, plus the Arnon-Friedman et al. quantum reduction. No invented entities.

free parameters (4)
  • p = optimized numerically
    Even integer bounded by p' / m; free variable in Lemma 5 and Theorem 1, optimized in Section IV to maximize output length or minimize second-source entropy.
  • p' = 2^l = optimized numerically
    Power-of-two parameter with l ≤ n2 + log(n1/2); chosen as 2^floor(log(m(n1-k1))) in the analytic proof, optimized numerically in the provided module.
  • λ = optimized numerically
    Interpolation parameter in Theorem 1 with 0.25 < λ < (δk2/16 - 1); controls error exponent vs output length; λ=1 recovers Raz-like error.
  • δ = optimized numerically
    Parameter in k1 ≥ (1/2+δ)n1 + 2 log n1; free, optimized in numerical comparisons.
assumptions (5)
  • standard math The Meka et al. construction G(β,ν)_α = ν ∑_{i=0}^{p'-1}(αβ)^i is a (p',2ζ)-biased generator over GF[2] with each block computable in O(log p') field operations.
    Lemma 4, proved in Appendix A following [42,43]; external theorem reproduced in the paper.
  • standard math Raz's original extractor lemma (Lemma 2) gives the error and strong-extractor penalties for a (p',ζ)-biased generator.
    Imported from [6] and used as the template for Lemma 5; proof is in the cited paper.
  • domain assumption Arnon-Friedman et al. Theorem 2 (Lemma 1): any strong two-source extractor is quantum-proof in the Markov model with entropy penalty log(1/ϵ).
    Used to derive Corollaries 1 and 2; not proved in this paper.
  • domain assumption The implementation requires a known irreducible polynomial over GF[2^{n1/2}]; current known trinomials limit n1/2 ≤ 74,207,281.
    Practical bound from the Great Trinomial Hunt [53]; theoretical claims are not limited by this.
  • domain assumption Two-source security model: independent min-entropy sources; quantum model uses Markov sources with I(X:Y|E)=0 and conditional min-entropy bounds.
    Definition 2 and Definition 3; the extractor's security is stated relative to these models.

how reviews work

0 comments
Cite this review

Pith. "Pith review of An efficient construction of Raz's two-source randomness extractor with improved parameters." pith.science (2026). https://pith.science/paper/64EPU3JN

@misc{pith2026250615547,
  author       = {Pith},
  title        = {Pith review of: An efficient construction of Raz's two-source randomness extractor with improved parameters},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/64EPU3JN}},
  note         = {Machine review of arXiv:2506.15547}
}
read the original abstract

Randomness extractors are algorithms that distill weak random sources into near-perfect random numbers. Two-source extractors enable this distillation process by combining two independent weak random sources. Raz's extractor (STOC '05) was the first to achieve this in a setting where one source has linear min-entropy (i.e., proportional to its length), while the other has only logarithmic min-entropy in its length. However, Raz's original construction is impractical due to a polynomial computation time of at least degree 4. Our work solves this problem by presenting an improved version of Raz's extractor with quasi-linear computation time, as well as a new analytic theorem with reduced entropy requirements. We provide comprehensive analytical and numerical comparisons of our construction with others in the literature, and we derive strong and quantum-proof versions of our efficient Raz extractor. Additionally, we offer an easy-to-use, open-source code implementation of the extractor and a numerical parameter calculation module.

Figures

Figures reproduced from arXiv: 2506.15547 by the authors.

Figure 1
Figure 1. FIG. 1: Comparison of maximum output lengths for different constructions of Raz’s extractor, across different min-entropy [PITH_FULL_IMAGE:figures/full_fig_p010_1.png] view at source ↗
Figure 2
Figure 2. FIG. 2: Comparison of the smallest min-entropy rate for the second source, [PITH_FULL_IMAGE:figures/full_fig_p011_2.png] view at source ↗
Figure 3
Figure 3. FIG. 3: Benchmark results for the code implementation on an Apple M4 processor, showing the mean and two standard [PITH_FULL_IMAGE:figures/full_fig_p012_3.png] view at source ↗

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

68 extracted references · 64 canonical work pages

  1. [1]

    Construction 1([42], Section 1.1).Letnandp ′ be positive integers satisfyingp′≤n

    The fast(p ′,ζ)-biased generator of reference [42, 43] We present the construction from [42] and its application as a computationally efficient(p′,ζ)-biased generator. Construction 1([42], Section 1.1).Letnandp ′ be positive integers satisfyingp′≤n. Letζ >0andFbe a finite field with|F|≥max{n,p ′/ζ}. LetA,Bbe arbitrary subsets ofF, with|A|=nand|B|=p ′/ζ. D...

    work page

  2. [2]

    Then the generator of Construction 1 viewed as a functionG:{0,1} r+t→{0,1} n·t is a(p′,2ζ)-biased generator

    Lettbe a positive integer, and supposer:= log(p ′/ζ)is a positive integer, such that2t≥max{n,2 r}. Then the generator of Construction 1 viewed as a functionG:{0,1} r+t→{0,1} n·t is a(p′,2ζ)-biased generator. Moreover, given any seed(β,ν)∈GF[2 r]×GF[2 t]and an indexj∈{0,...,n−1}, thej th block (oftbits) can be computed using O(log(p′))field operations over...

    work page

  3. [3]

    To summarize the above discussion, reference [42] presents a(p′,2ζ)-biased generator of output lengthn·t, for some well chosen parameters p′,ζ,nandt

    Application to Raz’s two-source extractor We now match up the parameters of the generator to those required by Raz’s extractor. To summarize the above discussion, reference [42] presents a(p′,2ζ)-biased generator of output lengthn·t, for some well chosen parameters p′,ζ,nandt. The seed is of lengthr+t, wherer= log(p ′/ζ), and output blocks of sizetcan be ...

    work page

  4. [4]

    leaking operation

    Making Raz’s extractor quantum-proof in the Markov model Using Theorem 1, we now apply Lemma 1 to obtain a quantum-proof version of the efficient Raz extractor with improved parameters. Corollary 1(Efficient quantum-proof Raz extractor).Letn 1,n 2,k 1,k 2,mbe positive integers,0< δ <1/2and 0.75<λ<(δk 2/16−1), such thatn 2≤n 1/2and k1≥ 1 2 +δ n1 + 2 log(n1...

    work page

  5. [5]

    Concatenation with a seeded extractor It is possible to increase the output length of Raz’s extractor by using it in conjunction with a strong seeded extractor. Specifically, using Raz’s strong extractor to generatemRAZ bits with errorϵ RAZ, and feeding this output into a seeded extractor, it is possible to re-extract from one of the original inputs. To e...

    work page

  6. [6]

    Extractors with weak random seeds

    Ran Raz. Extractors with weak random seeds. InProceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, STOC ’05, page 11–20, New York, NY, USA, 2005. Association for Computing Machinery

    work page 2005

  7. [7]

    This is due to the relatively small input lengthsn1 = 104,n 2 =n 1/2and error requirement ϵ= 2−16

    We note that all versions can break the barrierα1 +α 2 >1in the weak case, but in the strong case, Raz’s original version fails to do so. This is due to the relatively small input lengthsn1 = 104,n 2 =n 1/2and error requirement ϵ= 2−16. In the weak case, we find that our analytic theorem closely matches the performance of Raz’s original theorem, regardles...

    work page

  8. [8]

    Extractors for a constant number of polynomially small min-entropy independent sources

    Anup Rao. Extractors for a constant number of polynomially small min-entropy independent sources. InProceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 497–506, 2006

    work page 2006

Show all 68 references
  1. [9]

    Unbiased bits from sources of weak randomness and probabilistic communication complexity.SIAM Journal on Computing, 17(2):230–261, 1988

    Benny Chor and Oded Goldreich. Unbiased bits from sources of weak randomness and probabilistic communication complexity.SIAM Journal on Computing, 17(2):230–261, 1988

    1988

  2. [10]

    Extractors and pseudorandom generators.Journal of the ACM, 48(4):860–879, 2001

    Luca Trevisan. Extractors and pseudorandom generators.Journal of the ACM, 48(4):860–879, 2001

    2001

  3. [11]

    LFSR-based hashing and authentication

    Hugo Krawczyk. LFSR-based hashing and authentication. InProceedings of the 14th Annual Cryptology Conference (CRYPTO 94), pages 129–139, 1994

    1994

  4. [12]

    More efficient privacy amplification with less random seeds via dual universal hash function.IEEE Transactions on Information Theory, 62(4):2213–2232, 2016

    Masahito Hayashi and Toyohiro Tsurumaru. More efficient privacy amplification with less random seeds via dual universal hash function.IEEE Transactions on Information Theory, 62(4):2213–2232, 2016

    2016

  5. [13]

    Cryptomite: A versatile and user-friendly library of randomness extractors.Quantum, 9:1584, 2025

    Cameron Foreman, Richie Yeung, Alec Edgington, and Florian J Curchod. Cryptomite: A versatile and user-friendly library of randomness extractors.Quantum, 9:1584, 2025

    2025

  6. [14]

    Derandomization: A brief overview.Current Trends in Theoretical Computer Science, 1:165–188, 2002

    Valentine Kabanets. Derandomization: A brief overview.Current Trends in Theoretical Computer Science, 1:165–188, 2002

    2002

  7. [15]

    More on the sum-product phenomenon in prime fields and its applications.International Journal of Number Theory, 1(01):1–32, 2005

    Jean Bourgain. More on the sum-product phenomenon in prime fields and its applications.International Journal of Number Theory, 1(01):1–32, 2005

    2005

  8. [16]

    Improved randomness extraction from two independent sources

    Yevgeniy Dodis, Ariel Elbaz, Roberto Oliveira, and Ran Raz. Improved randomness extraction from two independent sources. InInternational Workshop on Randomization and Approximation Techniques in Computer Science, pages 334–

  9. [17]

    Non-malleable extractors, two-source extractors and privacy amplification

    Xin Li. Non-malleable extractors, two-source extractors and privacy amplification. In2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 688–697. IEEE, 2012

    2012

  10. [18]

    Improved two-source extractors, and affine extractors for polylogarithmic entropy

    Xin Li. Improved two-source extractors, and affine extractors for polylogarithmic entropy. In2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 168–177. IEEE, 2016

    2016

  11. [19]

    Explicit two-source extractors and resilient functions

    Eshan Chattopadhyay and David Zuckerman. Explicit two-source extractors and resilient functions. InProceedings of the forty-eighth annual ACM symposium on Theory of Computing, pages 670–683, 2016

    2016

  12. [20]

    Two source extractors for asymptotically optimal entropy, and (many) more

    Xin Li. Two source extractors for asymptotically optimal entropy, and (many) more. In2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 1271–1281. IEEE, 2023

    2023

  13. [22]

    Device-independent randomness amplification and privatization.IEEE Journal on Selected Areas in Information Theory, 1(2):568–584, 2020

    Max Kessler and Rotem Arnon-Friedman. Device-independent randomness amplification and privatization.IEEE Journal on Selected Areas in Information Theory, 1(2):568–584, 2020

    2020

  14. [23]

    Recent advances in randomness extraction.Entropy, 24(7):880, 2022

    Eshan Chattopadhyay. Recent advances in randomness extraction.Entropy, 24(7):880, 2022

    2022

  15. [24]

    Finitedevice-independentextractionofablockmin-entropysourceagainstquantumadversaries

    RavishankarRamanathan. Finitedevice-independentextractionofablockmin-entropysourceagainstquantumadversaries. arXiv preprint arXiv:2304.09643, 2023

    2023 arXiv

  16. [25]

    Practical randomness amplifi- cation and privatisation with implementations on quantum computers.Quantum, 7:969, 2023

    Cameron Foreman, Sherilyn Wright, Alec Edgington, Mario Berta, and Florian J Curchod. Practical randomness amplifi- cation and privatisation with implementations on quantum computers.Quantum, 7:969, 2023

    2023

  17. [26]

    PhD thesis, University of Cambridge, 2007.Also available as arXiv:0911.3814

    Roger Colbeck.Quantum and Relativistic Protocols For Secure Multi-Party Computation. PhD thesis, University of Cambridge, 2007.Also available as arXiv:0911.3814

    2007 arXiv

  18. [27]

    Free randomness can be amplified.Nature Physics, 8:450–454, 2012

    Roger Colbeck and Renato Renner. Free randomness can be amplified.Nature Physics, 8:450–454, 2012

    2012

  19. [28]

    Device-independent quantum key distribution secure against collective attacks.New Journal of Physics, 11(4):045021, 2009

    Stefano Pironio, Antonio Acin, Nicolas Brunner, Nicolas Gisin, Serge Massar, and Valerio Scarani. Device-independent quantum key distribution secure against collective attacks.New Journal of Physics, 11(4):045021, 2009

    2009

  20. [29]

    Pironio, A

    S. Pironio, A. Acin, S. Massar, A. Boyer de la Giroday, D. N. Matsukevich, P. Maunz, S. Olmschenk, D. Hayes, L. Luo, T. A. Manning, and C. Monroe. Random numbers certified by Bell’s theorem.Nature, 464:1021–1024, 2010

    2010

  21. [30]

    Privacy amplification with tam- perable memory via non-malleable two-source extractors.IEEE Transactions on Information Theory, 68(8):5475–5495, 2022

    Divesh Aggarwal, Maciej Obremski, João Ribeiro, Mark Simkin, and Luisa Siniscalchi. Privacy amplification with tam- perable memory via non-malleable two-source extractors.IEEE Transactions on Information Theory, 68(8):5475–5495, 2022

    2022

  22. [31]

    Realistic noise-tolerant randomness amplification using finite number of devices

    FernandoGSLBrandão, RavishankarRamanathan, AndrzejGrudka, KarolHorodecki, MichałHorodecki, PawełHorodecki, Tomasz Szarek, and Hanna Wojewódka. Realistic noise-tolerant randomness amplification using finite number of devices. Nature communications, 7(1):11345, 2016

    2016

  23. [32]

    Multi-source non-malleable extractors and applications

    Vipul Goyal, Akshayaram Srinivasan, and Chenzhi Zhu. Multi-source non-malleable extractors and applications. InAnnual International Conference on the Theory and Applications of Cryptographic Techniques, pages 468–497. Springer, 2021

    2021

  24. [33]

    2-source extractors under computational assumptions and cryptography with defective randomness

    Yael Tauman Kalai, Xin Li, and Anup Rao. 2-source extractors under computational assumptions and cryptography with defective randomness. In2009 50th Annual IEEE Symposium on Foundations of Computer Science, pages 617–626, 2009

    2009

  25. [34]

    Non-malleable extractors with short seeds and applications to privacy amplification

    Gil Cohen, Ran Raz, and Gil Segev. Non-malleable extractors with short seeds and applications to privacy amplification. In2012 IEEE 27th Conference on Computational Complexity, pages 298–308, 2012

    2012

  26. [35]

    Non-Malleable Extractors - New Tools and Improved Constructions

    Gil Cohen. Non-Malleable Extractors - New Tools and Improved Constructions. In Ran Raz, editor,31st Conference on Computational Complexity (CCC 2016), volume 50 ofLeibniz International Proceedings in Informatics (LIPIcs), pages 8:1–8:29, Dagstuhl, Germany, 2016. Schloss Dagstu...

    2016

  27. [36]

    Schulman

    Gil Cohen and Leonard J. Schulman. Extractors for near logarithmic min-entropy. In2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 178–187, 2016

    2016

  28. [37]

    Extractors: Low entropy requirements colliding with non- malleability

    Divesh Aggarwal, Eldon Chung, and Maciej Obremski. Extractors: Low entropy requirements colliding with non- malleability. InAnnual International Cryptology Conference, pages 580–610. Springer, 2023

    2023

  29. [38]

    Robust randomness generation on quantum computers.Available on Amazon Braket, 2021

    Mario Berta and Fernando Brandao. Robust randomness generation on quantum computers.Available on Amazon Braket, 2021

    2021

  30. [39]

    Non-malleable secret sharing

    Vipul Goyal and Ashutosh Kumar. Non-malleable secret sharing. InProceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pages 685–698, 2018

    2018

  31. [40]

    N. Alon, O. Goldreich, J. Hastad, and R. Peralta. Simple construction of almost k-wise independent random variables. In Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science, pages 544–553 vol.2, 1990

    1990

  32. [41]

    Nonmalleable extractors and codes, with their many tampered extensions

    Eshan Chattopadhyay, Vipul Goyal, and Xin Li. Nonmalleable extractors and codes, with their many tampered extensions. SIAM Journal on Computing, 49(5):999–1040, 2020

    2020

  33. [42]

    Targeted lossy functions and applications

    Willy Quach, Brent Waters, and Daniel Wichs. Targeted lossy functions and applications. InAdvances in Cryptology– CRYPTO 2021: 41st Annual International Cryptology Conference, CRYPTO 2021, Virtual Event, August 16–20, 2021, Proceedings, Part IV 41, pages 424–453. Springer, 2021

    2021

  34. [43]

    Extracting randomness from extractor-dependent sources

    Yevgeniy Dodis, Vinod Vaikuntanathan, and Daniel Wichs. Extracting randomness from extractor-dependent sources. In Advances in Cryptology–EUROCRYPT 2020: 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14...

    2020

  35. [44]

    Near-optimal erasure list-decodable codes

    Avraham Ben-Aroya, Dean Doron, and Amnon Ta-Shma. Near-optimal erasure list-decodable codes. In35th Computational Complexity Conference (CCC 2020). Schloss-Dagstuhl-Leibniz Zentrum für Informatik, 2020

    2020

  36. [45]

    Rotem Arnon Friedman, Christopher Portmann, and Volkher B. Scholz. Quantum-proof multi-source randomness extrac- tors in the Markov model. InTheory of Quantum Computation, Communication, and Cryptography, 2015

    2015

  37. [46]

    König and Barbara M

    Robert T. König and Barbara M. Terhal. The bounded-storage model in the presence of a quantum adversary.IEEE Transactions on Information Theory, 54(2):749–762, February 2008

    2008

  38. [47]

    Small-bias probability spaces: Efficient constructions and applications.SIAM Journal on Computing, 22(4):838–856, 1993

    Joseph Naor and Moni Naor. Small-bias probability spaces: Efficient constructions and applications.SIAM Journal on Computing, 22(4):838–856, 1993

    1993

  39. [48]

    A modular framework for randomness extraction based on Trevisan’s construction.arXiv preprint arXiv:1212.0520, 2012

    Wolfgang Mauerer, Christopher Portmann, and Volkher B Scholz. A modular framework for randomness extraction based on Trevisan’s construction.arXiv preprint arXiv:1212.0520, 2012

    2012 arXiv

  40. [49]

    A fast and simple randomized parallel algorithm for the maximal independent set problem.Journal of Algorithms, 7(4):567–583, 1986

    Noga Alon, László Babai, and Alon Itai. A fast and simple randomized parallel algorithm for the maximal independent set problem.Journal of Algorithms, 7(4):567–583, 1986

    1986

  41. [50]

    Rothblum, and Ron D

    Raghu Meka, Omer Reingold, Guy N. Rothblum, and Ron D. Rothblum. Fast pseudorandomness for independence and load balancing. In Javier Esparza, Pierre Fraigniaud, Thore Husfeldt, and Elias Koutsoupias, editors,Automata, Languages, and Programming, pages 859–870, Berlin, Heidelb...

    2014

  42. [51]

    Personal communications

    Ron Rothblum, 2024. Personal communications

    2024

  43. [52]

    Multi-source randomness extractors against quantum side information, and their applications.arXiv preprint arXiv:1411.2315, 2014

    Kai-Min Chung, Xin Li, and Xiaodi Wu. Multi-source randomness extractors against quantum side information, and their applications.arXiv preprint arXiv:1411.2315, 2014

    2014 arXiv

  44. [53]

    This work,λoptimized

    has identified irreducible trinomials for large fieldsGF[2s]where2 s−1is a Mersenne prime by exploiting the ability to efficiently test irreducibility when the factorization of2s−1is known, and exhaustively testing all possible trinomials for irreducibility. These are the larg...

  45. [54]

    Three xor-lemmas - an exposition

    Oded Goldreich. Three xor-lemmas - an exposition. In Oded Goldreich, editor,Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation - In Collaboration with Lidor Avigad, Mihir Bellare, Zvika Brakerski, Shafi Goldwasser, Shai Hale...

    2011

  46. [55]

    Another direction is to consider the efficient implementation ofnon-malleable extractors, of which Raz’s extractor is a common building block

    and our efficient Raz extractor construction significantly reduces the entropy requirements, allowing us to obtain new fundamental bounds. Another direction is to consider the efficient implementation ofnon-malleable extractors, of which Raz’s extractor is a common building bl...

  47. [56]

    Two-source extractors secure against quantum adversaries

    Roy Kasher and Julia Kempe. Two-source extractors secure against quantum adversaries. InInternational Workshop on Randomization and Approximation Techniques in Computer Science, pages 656–669. Springer, 2010

    2010

  48. [57]

    Nearly-linear time seeded extractors with short seeds.arXiv preprint arXiv:2411.07473, 2024

    Dean Doron and João Ribeiro. Nearly-linear time seeded extractors with short seeds.arXiv preprint arXiv:2411.07473, 2024

    2024

  49. [58]

    Leftover hashing against quantum side infor- mation

    Marco Tomamichel, Renato Renner, Christian Schaffner, and Adam Smith. Leftover hashing against quantum side infor- mation. InProceedings of the 2010 IEEE Symposium on Information Theory (ISIT10), pages 2703–2707, 2010

    2010

  50. [59]

    Trevisan’s extractor in the presence of quantum side information.SIAM Journal on Computing, 41:915–940, 2012

    Anindya De, Christopher Portmann, Thomas Vidick, and Renato Renner. Trevisan’s extractor in the presence of quantum side information.SIAM Journal on Computing, 41:915–940, 2012

    2012

  51. [60]

    Cambridge University Press, 2006

    Gilles Van Assche.Quantum cryptography and secret-key distillation. Cambridge University Press, 2006

    2006

  52. [61]

    Brent and Paul Zimmermann

    Richard P. Brent and Paul Zimmermann. The great trinomial hunt.CoRR, abs/1005.1967, 2010

    1967 arXiv

  53. [62]

    Curchod, Cameron Foreman, and Mafalda L

    Florian J. Curchod, Cameron Foreman, and Mafalda L. Almeida.(in preparation)

  54. [63]

    Generating quasi-random sequences from slightly-random sources

    Miklos Santha and Umesh V Vazirani. Generating quasi-random sequences from slightly-random sources. InProceedings of the 25th IEEE Symposium on Foundations of Computer Science (FOCS-84), pages 434–440, 1984

    1984

  55. [64]

    Improved two-source extractors against quantum side information

    Jakob Miller, Martin Sandfuchs, and Carla Ferradini. Improved two-source extractors against quantum side information. arXiv preprint arXiv:2503.05528, 2025

    2025 arXiv

  56. [65]

    Encyclopedia of Mathematics and its Applications

    Rudolf Lidl and Harald Niederreiter.Finite Fields. Encyclopedia of Mathematics and its Applications. Cambridge Uni- versity Press, 2 edition, 1996

    1996

  57. [66]

    Two-source extractors secure against quantum adversaries

    Roy Kasher and Julia Kempe. Two-source extractors secure against quantum adversaries. InApproximation, Randomiza- 15 tion, and Combinatorial Optimization, Lecture Notes in Computer Science, pages 656–669, 2010. Appendix A: Complete proofs for the fast(p′,ζ)-biased generator of...

    2010

  58. [67]

    Then the generator of Construction 1 viewed as a functionG:{0,1} r+t→{0,1} n·t is a(p′,2ζ)-biased generator

    Lettbe a positive integer, and supposer:= log(p ′/ζ)is a positive integer, such that2t≥max{n,2 r}. Then the generator of Construction 1 viewed as a functionG:{0,1} r+t→{0,1} n·t is a(p′,2ζ)-biased generator. Moreover, given any seed(β,ν)∈GF[2 r]×GF[2 t]and an indexj∈{0,...,n−1...

  59. [68]

    DefineN= (n 1/2)2n2

    Proof of Lemma 5 Lemma 5.Letn 1 andn 2 be positive integers, wheren1 is even andn 2≤n 1/2. DefineN= (n 1/2)2n2. Then for any positive integersk1,k 2,m,l,pandγ >0such thatm≤n 1/2,l≤n 2 + log(n1/2), p≤2 l/m,pis even and any γ≥2 (n1−k1)/p· (2ζ)1/p +p·2 −k2/2 ,(B1) 18 whereζ= 2 l−...

  60. [69]

    Proof of Theorem 1 Theorem 1.Letn 1,k 1,n 2,k 2,mbe positive integers,0<δ <1/2and0.25<λ<(δk 2/16−1), such thatn 2≤n 1/2 and k1≥ 1 2 +δ n1 + 2 log(n1) + 1,(B5) k2≥max h 3.2 log 8n1 k2 ,40 i ,(B6) m≤ 1 λ δk2 16 −1 .(B7) 5 This assignment can be done using any bijection between t...

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.