PaperlayerView exact revision on arXiv

Source-linked AI summary

A modular framework for randomness extraction based on Trevisan's construction

Wolfgang Mauerer, Christopher Portmann, Volkher B. Scholz

arXiv:1212.0520v1cs.ITcs.MSmath.ITquant-ph

TL;DR

Uniform randomness is needed for cryptography, simulation, and computation, but practical sources often contain only limited entropy. The paper presents a modular implementation of Trevisan’s quantum-secure extractor, evaluates interchangeable components, and derives explicit non-asymptotic results. The implementation supports realistic data sizes and current quantum key distribution scenarios, although performance and feasibility depend strongly on primitive choices.

  • Problem

    Applications need uniform randomness, while practical physical sources generally provide only partial entropy and cannot be made uniform by deterministic processing alone.

    Source: §I · p. 1

  • Method

    The paper implements Trevisan’s extractor with modular, interchangeable building blocks and analyzes their practical parameters, performance, and theoretical properties.

    Source: §I · pp. 1–2, §1 · p. 5, SUMMARY · p. 16

  • Results

    The implementation handles inputs of several GiBits, with throughput of about 17 kbit/s on a notebook and 160 kbit/s on a 48-core workstation.

    Source: B. Trevisan’s Construction · p. 5

  • Takeaways & Limitations

    The implementation can satisfy the needs of current quantum key distribution schemes, while different applications require different primitive combinations.

    Source: B. Trevisan’s Construction · p. 5, SUMMARY · p. 16

Abstract

from arXiv · show

Informally, an extractor delivers perfect randomness from a source that may be far away from the uniform distribution, yet contains some randomness. This task is a crucial ingredient of any attempt to produce perfectly random numbers---required, for instance, by cryptographic protocols, numerical simulations, or randomised computations. Trevisan's extractor raised considerable theoretical interest not only because of its data parsimony compared to other constructions, but particularly because it is secure against quantum adversaries, making it applicable to quantum key distribution. We discuss a modular, extensible and high-performance implementation of the construction based on various building blocks that can be flexibly combined to satisfy the requirements of a wide range of scenarios. Besides quantitatively analysing the properties of many combinations in practical settings, we improve previous theoretical proofs, and give explicit results for non-asymptotic cases. The self-contained description does not assume familiarity with extractors.

I. INTRODUCTION

Randomness extractors convert weakly random sources into shorter, nearly uniform outputs using an independent seed, with Trevisan’s construction offering quantum security, short seeds, and practical flexibility.

I. INTRODUCTION

  • Uniform randomness is essential for private communication, simulations, machine learning, and information-theoretically secure encryption, but physical sources typically provide only partial randomness.Extractors address this gap by processing imperfect physical randomness rather than requiring directly generated uniform bits.Source: §I · p. 1, A. What are extractors? · p. 2

A. What are extractors?

  • Extractors map a longer source string and a uniformly random seed to a shorter output that is close to uniform and independent of relevant side information.A quantum-proof (k, ε)-extractor processes n-bit inputs with d seed bits and produces m output bits, with entropy loss k −m.Source: §I · p. 1, A. What are extractors? · p. 3

I. INTRODUCTION

  • Trevisan’s extractor is quantum-proof and strong, making it suitable for privacy amplification in quantum key distribution even when the adversary knows the seed.Strongness means the seed remains nearly independent of the output and can be publicly revealed or reused.Source: §I · pp. 1–2, A. What are extractors? · p. 4
  • The work implements Trevisan’s 1999 construction as a modular, extensible platform that combines alternative building blocks for different experimental requirements.It also provides self-contained definitions, technical details, explicit constants, and guidance for users without prior extractor expertise.Source: §I · pp. 1–2

A. What are extractors?

  • Trevisan’s poly-logarithmic seed length improves on universal hashing, whose seed scales with the input or output length despite optimal entropy loss.Universal hashing remains the most common theoretical strong extractor in quantum key distribution, but its seed requirement grows with data size [6].Source: §I · p. 1, A. What are extractors? · p. 4

I. INTRODUCTION

  • Compared with the earlier implementation [7], the authors report several-orders-of-magnitude higher throughput and scalability to data sets 10 orders of magnitude larger.The implementation is intended for quantum cryptography, random-number generation, and further extractor research, with its source code publicly available.Source: §I · p. 2

B. Trevisan’s Construction

Trevisan’s extractor combines one-bit extractors with weak designs to produce longer random outputs from imperfect sources while supporting quantum-proof strong extraction. Its modular design lets users trade throughput, entropy loss, seed length, and source assumptions across practical constructions.

B. Trevisan’s Construction

  • Trevisan’s construction applies one-bit extractors to overlapping seed subsets and concatenates their outputs into a longer extracted string.The weak design controls subset overlap, while each one-bit extractor produces one output bit.Source: B. Trevisan’s Construction · p. 4, §1 · p. 5
  • The construction is a recipe combining interchangeable one-bit extractors and weak designs, allowing choices tailored to application-specific parameter regimes.The implementation exposes these building blocks so users can prioritize speed, entropy loss, or assumptions on the initial randomness.Source: B. Trevisan’s Construction · p. 4, §2 · p. 6
  • Trevisan’s extractor is quantum-proof and strong, while requiring only poly-logarithmic seed length in the input length.As a strong extractor, its seed is almost independent of the final output and is not consumed in the extraction process.Source: B. Trevisan’s Construction · p. 4
  • 17 kbit/s on a notebook and 160 kbit/s on a 48-core workstation are achieved by GF(p)-weak design with XOR extraction, while extracting one percent of available entropy.For 4 GiBit input, the one-bit extractor needs 1.7 KiBit of seed and the total seed is roughly 2.9 MiBit.Source: B. Trevisan’s Construction · pp. 4–5
  • A low-entropy source favors block weak design with polynomial hashing, which has almost minimal entropy loss and the shortest seed but reaches only a few kbit/s on a notebook.With 48 cores it reaches 70 kbit/s for a much shorter input length, and nearly all entropy can be extracted using slightly less than 300 KiBit of total seed.Source: B. Trevisan’s Construction · p. 5

1. Description

  • For a weak (m, t, r, d)-design and a quantum-proof (k, ε)-strong one-bit extractor, the resulting construction is quantum-proof (k + rm, mε)-strong.When r = 1, the weak design contributes roughly no additional entropy loss, while ε remains the error per output bit.Source: §1 · p. 5

2. Constructions overview

  • The overview compares XOR-code, Lu’s construction, and polynomial hashing with alternative weak designs using seed length, entropy, and free parameters to characterize their trade-offs.The standard design uses d = t^2 and r = 2^e, while the iterated design has r = 1 and therefore no design-induced entropy loss.Source: §2 · p. 6

B. Weak designs

The paper adapts established weak-design constructions and proves their validity under broader parameter conditions, including an iterated design with unit overlap.

B. Weak designs

  • The Nisan–Wigderson weak-design construction is proved valid for any prime-power t and any m with overlap r = 2^e.This extends earlier parameter restrictions requiring m to be a power of t or a multiple of a power of t.Source: B. Weak designs · p. 6
  • An iterated construction adapted from Ma and Tan [18] achieves overlap r = 1, eliminating entropy loss caused by the weak design.The paper proves the correctness of this construction in Appendix C 2.Source: B. Weak designs · p. 6

1. Basic construction

The paper develops polynomial and block weak designs for Trevisan’s extractor, then analyzes an XOR-code one-bit extractor and its resulting quantum-proof guarantees. The block construction reduces overlap to r = 1, while parameter choices expose seed-length and efficiency trade-offs.

1. Basic construction

  • Polynomially indexed sets form a weak design with total preceding overlap bounded by 2em.The construction uses m polynomials over GF(t), each yielding a set of t pairs within [d] for d = t^2.Source: §1 · p. 7

2. Reducing the overlap

  • The block weak design places smaller basic designs diagonally, yielding d = (ℓ + 1)t^2 and overlap parameter r = 1.The number and sizes of component designs are determined by the block parameters m_i and n_i.Source: §2 · p. 7
  • For typical parameters, the block weak design increases the required seed by a factor of 50 as the one-bit extractor’s seed length varies.The figure’s inset relates the number of blocks to the seed overhead because block-design seed size grows linearly with block number.Source: Figure 3 · p. 7, §2 · p. 7

1. XOR-code

  • The XOR-code one-bit extractor is efficient and ℓ-local, but requires seed length t ∈ O(log n log 1/ε) and has entropy loss linear in n.Its seed length is larger than the optimal O(log n + log 1/ε) bound.Source: §1 · p. 7
  • The XOR-code has seed length t = ℓ log n, with binary entropy h(p) = −p log p − (1 − p) log(1 − p).The appropriate locality ℓ is selected numerically from the target entropy-loss parameter γ and error ε.Source: §1 · p. 8
  • Using the XOR-code in Trevisan’s construction gives quantum-proof strong-extractor guarantees, with parameters determined by the weak-design overlap and per-bit error.For a weak (m, t, r, d)-design, the construction has output error mε and entropy parameter k + rm in the cited guarantee.Source: §1 · p. 8
  • The choice of µ controls the XOR extractor’s behavior and therefore influences the seed length through γ = µα.The paper distinguishes experimental entropy deficiency α from extraction-induced loss using µ.Source: §1 · p. 8

2. Lu’s construction

Lu’s construction combines random-walk sampling on an expander graph with one-bit hashing, yielding a quantum-proof Trevisan extractor but rarely reaching practically favorable parameter regimes.

2. Lu’s construction

  • Lu’s extractor selects input bits through a random walk on a g-regular graph, then hashes the selected substring to one bit.The hash computes the parity of the bitwise product with a random seed.Source: §2 · p. 8
  • Expander graphs reduce the walk description to a seed comprising the initial vertex, walk directions, and final hashing seed.The total seed is t = nb(n)+ c(ℓ−1) log g + ℓ.Source: §2 · pp. 9–10
  • The graph construction supports dimensions expressible as ℓ^2 and can be generated during the walk using constant space.Its arithmetic uses modulo operations, with a conditional-division optimization noted for the small multiplicative factor 2.Source: §2 · p. 9
  • The construction can be quantum-proof when its one-bit extractor is combined with Trevisan’s construction and a weak design.The supplied parameterization gives a quantum-proof (k, mε)-strong extractor.Source: §2 · p. 10
  • Decreasing ν sharply increases the required walk length, while small ν is needed even for tiny extraction fractions.Consequently, Lu’s construction is preferable to two-universal hashing only rarely.Source: §2 · p. 10, Figure 7 · p. 10, Figure 8 · p. 10

3. Polynomial hashing

Polynomial hashing combines a Reed–Solomon-style polynomial hash with a Hadamard-style hash to obtain a quantum-proof extractor with short seed requirements, but its evaluation cost limits performance.

3. Polynomial hashing

  • Polynomial hashing partitions the input into field elements, evaluates a polynomial, and then applies a second hash to produce the output bit.The seed is split into α for polynomial evaluation and β for the final parity hash.Source: §3 · pp. 10–11
  • Combining the two 2-AU2 hashes yields a δ-AU2 construction with δ ≤ 1/2 + ε′² under ℓ = ⌈log n + 2 log 1/ε′⌉ and s = ⌈n/ℓ⌉.Source: §3 · p. 11
  • The resulting construction is quantum-proof when inserted into Trevisan’s framework.The supplied theorem statements give the corresponding quantum-proof strong-extractor guarantee.Source: §3 · p. 11
  • Polynomial hashing has consistently small seed requirements and no extraction factor µ, but its polynomial degree is the crucial performance bottleneck.For n = 10^6, the degree is approximately 10,000, and the polynomial must be evaluated for every extracted bit.Source: Figure 10 · p. 11
  • The polynomial-hashing extractor is therefore unsuitable for performance-intensive scenarios despite outperforming two-universal hashing across a wide parameter range.The comparison is stated in the parameter overview for r = 2e.Source: Figure 10 · p. 11

IV. IMPLEMENTATION

The implementation prioritizes correctness, throughput, portability, and extensibility through compiled C++, independent finite-field libraries, multicore execution, and reusable weak-design storage.

A. Implementation Architecture

  • The code supports standalone execution, dry-run parameter estimation, library integration, and R-language calls for high-level workflows.The full source code is available for inspection and modification.Source: A. Implementation Architecture · p. 11, §1 · p. 12
  • C++16 supplies the performance-critical implementation while preserving a clean, extensible architecture portable from laptops to HPC machines.The design can exploit low-level CPU capabilities for bit-level operations.Source: §1 · p. 12

1. Architecture

  • Independent NTL and OpenSSL libraries, together with compile-time invariants and sanity checks, support cross-validation of finite-field calculations.Checks can be disabled at compile time to avoid runtime penalties.Source: §1 · p. 12
  • A mostly lock-free multicore design distributes work precisely and avoids stalls from synchronized communication.The implementation uses the threading building blocks library as its foundation.Source: §1 · p. 12
  • Weak designs may be precomputed and reused, but measured storage-transfer times exceeded on-the-fly computation for the standard design.Block weak designs are more favorable because only the basic design must be stored.Source: §1 · p. 12

2. Implementation details

The implementation exposes modular interfaces for weak designs and one-bit extractors, then applies a common Trevisan algorithm while accommodating machine-level performance and component-specific constraints.

1. Trevisan’s extractor

  • The GF(2^x)-based weak design only supports seed lengths that are powers of two, which can force larger-than-requested initial seeds.Component boundary conditions can therefore constrain otherwise requested parameter sets.Source: §2 · p. 13, §1 · p. 13

2. Implementation details

  • Weak-design and one-bit-extractor classes provide interfaces for seed sizing, parameter computation, index generation, extraction, and overlap reporting.These methods allow the higher-level algorithm to operate without knowing internal component details.Source: §2 · pp. 12–13
  • Performance-critical operations use machine arithmetic and integer logarithms instead of software multiprecision and floating-point calculations.The implementation generally needs only floor or ceiling logarithms.Source: §2 · p. 13
  • The fixed-width index type limits addressable randomness, and processing multiple gigabytes requires a 64-bit machine and kernel.The stated bound is 2^(w−3) bytes for index width w.Source: §2 · p. 13

B. Algorithms

  • The reference algorithms are presented in implementation-oriented pseudocode, while the complete reference implementation contains about 5000 lines of source code.The Trevisan loop computes each output bit in a data-parallel structure using the selected design and extractor.Source: B. Algorithms · p. 13, §1 · p. 13

1. Trevisan’s extractor

  • Trevisan’s algorithm is independent of the chosen weak design and one-bit extractor, with only inferred parameters depending on component properties.This separation is implemented through polymorphic base-class interfaces.Source: §2 · p. 12, §1 · p. 13

2. Weak Designs

The implementation supports Hartman–Raz weak designs over extension and prime finite fields, plus block designs that reuse a basic design through structured indexing and caching.

Hartman and Raz

  • Hartman–Raz designs use polynomial evaluation over finite fields, with GF(2^x) and GF(p) variants implemented.Requested extractor parameters t_req may require increasing the design-provided value to t′, with t ≥ t_req.Source: §2 · p. 13

Finite-field arithmetic

  • Prime-field arithmetic requires overflow-avoiding algorithms, while extension-field arithmetic reduces operations modulo an irreducible polynomial.The implementation avoids arbitrary-precision fallback for prime-field products and exploits irreducible polynomials of order 3 or 5 for GF(2^m).Source: §2 · p. 14

Block Weak Design

  • Block weak designs reuse a basic design by placing its matrix representation on the diagonal of a larger matrix.This structure can reduce memory requirements through sparse storage and derived blocks.Source: §2 · p. 14
  • 2012-style indexing derives block rows by adding j·t2 to basic-design indices, while row permutation groups related rows for cache reuse.Because Trevisan’s algorithm traverses rows sequentially, this ordering minimises repeated calls to the basic construction.Source: §2 · p. 14
  • The block-design routine infers block coordinates and recomputes the basic design only when the relevant block index changes.Otherwise, it reuses the cached construction across the corresponding rows.Source: §2 · p. 14

3. 1-Bit extractors

The paper implements several one-bit extractors and evaluates their practical runtime across primitive combinations, showing that scalability and throughput depend strongly on the chosen design.

3. 1-Bit extractors

  • The one-bit implementations include XOR coding, polynomial hashing with Reed–Solomon/Hadamard coding, and Lu’s expander-based random walk.RSH evaluates a polynomial over GF(2^l), while Lu’s construction updates an expander-graph vertex through encoded edges.Source: §3 · pp. 14–15
  • RSH reuses global polynomial coefficients and applies Horner’s rule, while parity is computed with word-level operations and bit counting.These optimisations reduce repeated polynomial work and replace single-bit parity operations with machine-oriented processing.Source: §3 · p. 15
  • The Lu implementation requires a slightly larger randomness budget because bit-string contributions are aligned to machine-word edge widths.The increase is described as a negligible additive factor.Source: §3 · p. 15

V. RUNTIME COMPARISON

  • The authors benchmark selected typical cases on a laptop and workstation rather than exhaustively measuring all primitive combinations.The selection reflects throughput, scalability, weak-design and extractor-performance trade-offs across machine characteristics.Source: §V · p. 15, Table I · p. 15
  • More CPUs do not guarantee higher RSH throughput: setup and parallelisation overhead can create a local maximum before performance declines with input length.The figure reports throughput above 100 kbit/s only for very small inputs, where the required seed can exceed the extracted randomness.Source: Figure 11 · p. 16

SUMMARY

  • Trevisan extraction is feasible in practice for some scenarios, but short-seed extractors generally suffer from low extraction rates and require primitive-specific choices.The implementation is reported to meet the needs of current quantum key distribution schemes.Source: SUMMARY · p. 16

V. RUNTIME COMPARISON

  • 2–3 orders of magnitude higher throughput and much larger feasible inputs distinguish the framework from Ref. [7].Figure 12 compares the framework with Ref. [7] for the primitive combination supported by that implementation.Source: Figure 12 · p. 16

Appendix A: Extractor definitions

The appendix defines strong, quantum-proof, local, and classical-proof extractors, then states coding-theoretic results used to derive the paper’s constructions.

Appendix A: Extractor definitions

  • A strong extractor maps a weak source and uniform seed to an almost-uniform output that is approximately independent of the seed.The paper defines this for sources with min-entropy at least k and error parameter ε.Source: Appendix A · p. 17
  • With quantum side information, extraction requires output close to uniform and independent of the side-information system.The quantum-proof definition extends the strong-extractor requirement to states classical on the source register.Source: Appendix A · p. 17

Appendix B: Known extractor results

  • Any strong extractor is classical-proof with shifted parameters, specifically (k + log 1/ε, 2ε).The appendix also notes that conventional extractors become classical-proof with slightly weaker parameters.Source: Appendix A · p. 18

Appendix A: Extractor definitions

  • An ℓ-local extractor depends on only ℓ input bits for each fixed seed, with the selected locations determined by that seed.The definition applies to extractors with or without quantum side information.Source: Appendix A · p. 18

1. List-decodable codes

  • List-decodable codes constrain the number of codewords in each Hamming ball and yield one-bit extractors through the stated lemmas.The appendix records both extractor and classical-proof consequences for list-decodable codes.Source: §1 · p. 18

2. One-bit extractors

The appendix relates one-bit, universal-hashing, and Trevisan constructions to quantum-proof extraction, including parameter transformations and an improved Trevisan bound.

2. One-bit extractors

  • A strong one-bit extractor becomes quantum-proof with parameters (k + log 1/ε, 3√ε).This is stated for a (k, ε)-strong extractor with one output bit.Source: §2 · p. 19
  • If the one-bit extractor is already classical-proof, the appendix gives a refined quantum-proof transformation.The refinement is presented as implicit in Ref. [39].Source: §2 · p. 19

3. Universal hashing

  • A δ-almost-universal2 hash family has low collision probability, and suitable δ yields a quantum-proof extractor when hashes are sampled uniformly.The construction is defined by Ext(x, y) := h_y(x).Source: §3 · p. 19

4. Trevisan’s extractor

  • Trevisan’s construction combines a quantum-proof one-bit extractor with a weak design to produce a quantum-proof strong extractor.Lemma B.8 gives parameters (k + rm, mε), where m is the output length and r is a weak-design parameter.Source: §4 · p. 19
  • Using a one-bit extractor already known to be quantum-proof yields better parameters than the earlier theorem in Ref. [4].The improvement follows from applying Lemma B.8 directly.Source: §4 · p. 19

Appendix C: Weak design proofs

Appendix C proves overlap bounds for two weak-design constructions: the basic construction has r < 2e, while the overlap-reduced construction achieves r = 1.

1. Basic construction

  • The basic weak-design construction satisfies r < 2e.The proof uses the established bound r < e when m is divisible by t_c, then extends it to intermediate m by dropping final sets, which cannot increase overlap.Source: §1 · p. 19
  • For intermediate m, replacing it with m′ = (k + 1)t_c and dropping the final sets preserves the bound because overlap can only decrease.The resulting inequality is strict, yielding the stated bound after the displayed estimate.Source: §1 · p. 19

2. Reducing the overlap

  • The overlap-reducing weak-design construction achieves r = 1.The proof indexes sets by (i, j) and verifies the second condition of the weak-design definition for r = 1.Source: §2 · p. 19
  • The remaining bound follows from a geometric-series estimate and conditions (C1)–(C3), with strict integrality forcing the required conclusion.The proof explicitly invokes the geometric-series sum and then uses the fact that the left-hand side is an integer.Source: §2 · pp. 19–20
  • Sets belonging to different i-indices are disjoint, so their pairwise intersections have size zero.This disjointness is used to control the overlap for each set with i ≤ ℓ − 1.Source: §2 · p. 20
Loading 1212.0520v1…