Pith. sign in

REVIEW 3 major objections 4 minor 16 references

randextract: a Reference Library to Test and Validate Privacy Amplification Implementations

T0 review · 3 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read The paper presents randextract, an open-source Python reference library for privacy amplification, and shows that validating high-performance implementations against it uncovers real, security-relevant bugs.

desk verdict A practical validation library that has already caught real bugs in QKD/QRNG privacy amplification code; worth a serious referee despite a minor under-supported claim. read the letter →

arxiv 2506.00124 v1 pith:K7YDUFIW submitted 2025-05-30 quant-ph cs.CR

Iyán Méndez Veiga , Esther Hänggi This is my paper
classification quant-phcs.CR
keywords privacyamplificationrandomnessextractorsToeplitzhashingTrevisan'sextractorquantumkeydistributionrandomnumbergeneratorreferenceimplementationtestvectors
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

The paper argues that the security guarantees of quantum key distribution and quantum random number generation depend as much on correct classical post-processing as on the quantum hardware, and that privacy amplification is the step whose failure can silently invalidate the final key's secrecy. To address this, it presents randextract, an open-source Python library that implements quantum-proof strong seeded extractors, specifically modified Toeplitz hashing and Trevisan's construction, with code kept close to the mathematical definitions and covered by extensive tests. The library is also a validation workbench: a Validator class compares third-party implementations against this reference behavior, and the authors demonstrate its use by finding a GPU implementation that drops the final input bit and a C++ Trevisan implementation whose weak design violates the security-relevant bound. The paper further contributes test vectors in a request/response format modeled on established cryptographic algorithm validation programs, aiming to support future certification of quantum cryptographic post-processing.

What carries the argument

The load-bearing objects are two families of quantum-proof strong seeded randomness extractors. Modified Toeplitz hashing, defined by $\mathrm{Ext}_{\mathrm{Mod.\ Toeplitz}}(x,y) := (T'(y) \| \mathbb{1}_m) x$, concatenates an $m \times (n-m)$ Toeplitz matrix with the $m \times m$ identity matrix, reducing the seed length from $n+m-1$ to $n-1$ bits while preserving two-universality. Trevisan's construction, $\mathrm{Ext}_{\mathrm{Trevisan}}(x,y) := \mathrm{Ext}_1(x,y_{S_0}) \cdots \mathrm{Ext}_1(x,y_{S_{m-1}})$, concatenates the outputs of a one-bit extractor on seeds selected by a weak $(m,t,r,d)$-design, and the weak-design condition $\sum_{j=0}^{i-1} 2^{|S_i \cap S_j|} \le rm$ is what guarantees the construction stays a strong quantum-proof extractor. Around these definitions, the Validator class and the generated request/response test vectors form the mechanism that turns mathematical definitions into a practical check on third-party code.

What would settle it

For a small input length, such as 128 bits, enumerate all possible seeds and check whether randextract's modified Toeplitz output always equals the explicit matrix-vector product of Eq. (10); any single mismatch refutes the reference claim, and an independent implementation with identical bit-order and endianness conventions that disagrees on any test vector would do the same.

Watch

Extended reading notes

Core claim

The paper's central claim is that a deliberately simple, readable reference implementation can serve as ground truth for the correctness of privacy amplification, and that comparing optimized implementations against this reference exposes real bugs that would otherwise go unnoticed. Using randextract, the paper reports three concrete findings: a GPU-based modified Toeplitz hashing implementation silently ignored the last bit of its input; a C++ implementation of Trevisan's construction applied arithmetic optimizations that are only valid for field sizes that are powers of two, breaking the weak-design condition and therefore the extractor's security guarantee; and the same C++ library evaluates polynomial coefficients in the reverse order from its own specification, changing outputs though not the validity of the design. The paper also shows how to generate reproducible test vectors so that third parties and future standardization efforts can repeat these checks without trusting a single implementation's source code.

Load-bearing premise

The validator's authority rests on randextract's own correctness: if its bit ordering, endianness, or finite-field arithmetic disagrees with the mathematical definitions or with an external implementation's input format, then a reported discrepancy would be a convention mismatch rather than a bug in the implementation under test.

Editorial extensions

If this is right

  • Any privacy amplification implementation can be validated against a public reference before deployment, even when its source code is closed or hard to audit.
  • The provided test vectors can feed a certification program: a device would pass only if its outputs match the reference across the full range of inputs it is expected to handle.
  • For Trevisan-based extractors, certification cannot rely on end-to-end output checks alone, because the weak design and one-bit extractor components must each be verified, as the broken finite-field arithmetic example shows.
  • The same validator workflow can be used during development of new implementations, catching boundary-condition bugs such as the dropped last bit before the code is deployed in an experiment.

Reading between the lines

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

  • The authority of any reference implementation is convention-dependent: bit order, endianness, and finite-field representations need to be standardized before the test vectors can play the role the paper envisions for certification.
  • The validation method could be turned into an automated differential fuzzer that generates adversarial and boundary inputs and checks arbitrary implementations without hand-written examples.
  • The same reference-and-validate pattern could be applied to the other classical post-processing steps, such as parameter estimation and information reconciliation, whose errors also contribute to the composable security bound.
  • A single reference implementation can carry a subtle shared-convention bug, so an independent second implementation or a formal proof of the reference would strengthen the test vectors enough for high-assurance certification.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 4 minor

Summary. The paper presents randextract, an open-source Python reference library for privacy amplification primitives, specifically standard and modified Toeplitz hashing and Trevisan's extractor. The authors argue that classical post-processing, especially privacy amplification, is underscrutinized in quantum-cryptography standardization and that a readable, auditable reference implementation can serve as an oracle for validating high-performance third-party implementations. They describe the library's design, its Validator class, and its ability to generate CAVP-style test vectors. They report three validation case studies: a GPU-based modified Toeplitz implementation that ignores the final input bit, a Rust Toeplitz implementation validated during development, and a C++ Trevisan implementation with three identified issues. The paper includes a small sample test-vector response file and calls for extension of standardization efforts to classical post-processing.

Significance. If correct, randextract addresses a genuine need: privacy amplification is security-critical in QKD and QRNGs, and high-performance implementations are difficult to audit. The reported bug in a state-of-the-art GPU implementation, where the last input bit is silently dropped, is a concrete and valuable demonstration that validation of PA code matters. The library is openly available, has unit and integration tests, and provides a structured way to generate test vectors in a format familiar from NIST CAVP. These are real strengths. The paper's main limitation is that the library itself is the reference oracle, so its authority depends on conventions and internal correctness that are not fully pinned down; one of the three reported C++ Trevisan issues is explicitly marked with a 'we believe' rather than a proof. These issues do not invalidate the contribution, but they need to be resolved before the library can be recommended as a trustworthy reference for the community.

major comments (3)
  1. [§4.3] The third issue reported for the C++ Trevisan implementation is dismissed with 'We believe this deviation does not affect the correctness of the weak design, but it does result in outputs that differ from our implementation.' This is an unproven assumption, and it is load-bearing for the claim that the library exposes bugs rather than convention mismatches. If randextract's coefficient ordering, rather than the C++ implementation's, deviates from the mathematical specification in App. C.1 of Mauerer et al. (2012), then the reported output difference is a false positive. Please provide a concrete argument, or a short computation, that reversing the polynomial coefficients is a bijective transformation preserving the weak-design condition in Eq. (11), and explicitly state which convention matches App. C.1. Alternatively, if the reversal is only a representational difference, do not list it as a 'bug' or 'issue' without that clarification.
  2. [§5.1] The sample test-vector file is labeled 'Modified Toeplitz Hashing' with 'Input Length: 128' and 'Compression ratio: 1/2', i.e., output length 64. According to Eq. (10), modified Toeplitz hashing with parameters n=128 and m=64 requires a seed of length n-1 = 127 bits. The provided SEED field, however, is 32 hex characters, i.e., 128 bits. This is inconsistent with the stated algorithm. If the implementation pads the seed to a byte boundary, that convention must be documented and reflected in the header; if the vector is actually for standard Toeplitz hashing, which uses n+m-1 = 191 bits, then the SEED is still too short. Please correct the header, the seed length, or the vector itself, because unambiguous test vectors are a central contribution of §5.
  3. [§3 and §4] The paper does not explicitly specify the bit-ordering, byte-ordering, and finite-field representation conventions used by randextract (e.g., whether index 0 is the least-significant or most-significant bit, and which polynomial basis is used for GF(2^k) via the Galois package). Since the library serves as the reference oracle, any discrepancy with a third-party implementation could be a convention mismatch rather than a bug. This is particularly relevant to the Trevisan validation in §4.3 and to the reusable test vectors in §5. Please add a precise conventions section and, ideally, provide at least one small test vector with a hand-computable derivation or an independently implemented check, to break the circularity of using the library as its own oracle.
minor comments (4)
  1. [§3.4] The text says 'Finally, the output is computed in Step 4 by calling the extract() method', but the preceding enumerated list has only three steps; this should refer to Step 3.
  2. [§3.5.1] The code comment says '8 Mib' while the variable is 'MiB'; please use consistent IEC units throughout.
  3. [§4.3] The sentence 'A full description of the issues and solutions are contained directly in the library repository' has a subject-verb agreement error; it should be 'A full description ... is contained'.
  4. [§2.4.1] The FFT-based efficient implementation is described with the Fourier matrix F_q and element-wise multiplication, but it is not stated how the operations are mapped to binary arithmetic (e.g., whether the FFT is over reals/complex numbers and then reduced modulo 2). A brief note would help readers connect the formula to the actual Python implementation.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; randextract's role as reference oracle is mitigated by independent unit tests, toy examples, and external bug reports, and the only 'we believe' caveat in §4.3 is a convention risk, not a circular step.

full rationale

The paper makes no claim that reduces by construction to its own inputs. The mathematical definitions (Eqs. (9), (10), (12)) are standard literature results from Carter-Wegman, Hayashi-Tsurumaru, Trevisan, De et al., and Konig-Terhal; randextract is presented as an implementation of those definitions, not as a derivation of them. The validation results in Sec. 4 are comparisons against external code: the GPU modified-Toeplitz bug (ignored final bit) is a concrete, code-level finding; the Rust validation is exhaustive for small inputs; and the C++ Trevisan weak-design violation is reasoned from finite-field arithmetic, independent of randextract's conventions. The self-referential aspect is the test-vector generator and the reference oracle: vectors are produced by the same library, so their authority inherits the library's correctness. This is mitigated by the stated unit tests, toy examples designed for manual computation, and the fact that the reported bugs are externally checkable. The paper itself flags the one unresolved convention point in Sec. 4.3: 'We believe this deviation does not affect the correctness of the weak design, but it does result in outputs that differ from our implementation.' That is a limitation/correctness risk (if randextract's coefficient ordering were the non-standard one, the mismatch could be a convention artifact), but it is an admitted uncertainty, not a fitted input, self-citation chain, or definitional equivalence. No load-bearing self-citation is present; the authors' own PyPI reference is just the software distribution point, and the Bosshard et al. GPU implementation is co-authored by Hänggi but is the target of a negative bug report rather than evidence. Score 0.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The central claim relies on standard results in randomness extraction and on the correctness of the software toolchain, but no free parameters are fitted and no new entities are postulated.

assumptions (3)
  • domain assumption A family of two-universal hash functions yields a quantum-proof strong extractor for output length m <= k + 2 - 2 log(1/epsilon) (leftover hash lemma).
    Invoked in Sec 2.4 to justify Toeplitz and modified Toeplitz hashing as quantum-proof extractors. Cited from Renner & Koenig 2005 and Tomamichel et al. 2011.
  • domain assumption Trevisan's construction, built from a strong one-bit extractor and a weak design satisfying Eq. (11), is a quantum-proof strong extractor.
    Used in Sec 2.4.2; relies on De et al. 2012 and Koenig & Terhal 2008.
  • standard math The efficient FFT-based multiplication of a Toeplitz matrix with a vector produces the same result as direct matrix-vector multiplication as defined in Eqs. (9) and (10).
    Assumed in Sec 2.4.1 for the efficient implementation; cited to Hayashi & Tsurumaru 2016.

how reviews work

0 comments
Cite this review

Pith. "Pith review of randextract: a Reference Library to Test and Validate Privacy Amplification Implementations." pith.science (2026). https://pith.science/paper/K7YDUFIW

@misc{pith2026250600124,
  author       = {Pith},
  title        = {Pith review of: randextract: a Reference Library to Test and Validate Privacy Amplification Implementations},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/K7YDUFIW}},
  note         = {Machine review of arXiv:2506.00124}
}
read the original abstract

Quantum cryptographic protocols do not rely only on quantum-physical resources, they also require reliable classical communication and computation. In particular, the secrecy of any quantum key distribution protocol critically depends on the correct execution of the privacy amplification step. This is a classical post-processing procedure transforming a partially secret bit string, known to be somewhat correlated with an adversary, into a shorter bit string that is close to uniform and independent of the adversary's knowledge. It is typically implemented using randomness extractors. Standardization efforts in quantum cryptography have focused on the security of physical devices and quantum operations. Future efforts should also consider all algorithms used in classical post-processing, especially in privacy amplification, due to its critical role in ensuring the final security of the key. We present randextract, a reference library to test and validate privacy amplification implementations.

Figures

Figures reproduced from arXiv: 2506.00124 by the authors.

Figure 1
Figure 1. Diagram of a seeded randomness extractor that [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Toeplitz hashing is defined as the matrix-vector [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗
Figure 3
Figure 3. Trevisan’s extractor output (12) is the concatena [PITH_FULL_IMAGE:figures/full_fig_p007_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Screenshot showing the output of the script [PITH_FULL_IMAGE:figures/full_fig_p010_4.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

16 extracted references · 15 canonical work pages

  1. [1]

    Alagic, G., Bros, M., Ciadoux, P., Cooper, D., Dang, Q., Dang, T., Kelsey, J., Lichtinger, J., Liu, Y .-K., Miller, C., Moody, D., Peralta, R., Perlner, R., Robinson, A., Silberg, H., Smith-Tone, D., and Waller, N. (2025). Status report on the fourth round of the nist post- quantum cryptography standardization process. Tech- nical Report NIST IR 8545, Nat...

    work page 2025

  2. [5]

    The urgent need for memory safety in software products

    Cybersecurity and Infrastructure Security Agency (2023). The urgent need for memory safety in software products. https://www.cisa.gov/news-events/news/ urgent-need-memory-safety-software-products. Ac- cessed May 30,

    work page 2023

  3. [6]

    De, A., Portmann, C., Vidick, T., and Renner, R. (2012). Trevisan’s extractor in the presence of quantum side information.SIAM Journal on Computing, 41(4):915–

    work page 2012

  4. [8]

    ISO/IEC 23837-2:2023 — Information security — Security requirements, test and evaluation methods for quantum key distribu- tion — Part 2: Evaluation and testing methods

    ISO/IEC JTC 1/SC 27 (2023). ISO/IEC 23837-2:2023 — Information security — Security requirements, test and evaluation methods for quantum key distribu- tion — Part 2: Evaluation and testing methods. In- ternational Standard ISO/IEC 23837-2:2023, Interna- tional Organization for Standardization and Interna- tional Electrotechnical Commission, Geneva. Pub- l...

    work page 2023

  5. [10]

    Module-Lattice-Based Key-Encapsulation Mech- anism Standard

    National Institute of Standards and Technology (2024). Module-Lattice-Based Key-Encapsulation Mech- anism Standard. Federal Information Processing Standards Publication (FIPS) NIST FIPS 203, Department of Commerce, Washington, D.C. National Intelligence Service, Republic of Korea (2015). Korean cryptographic module validation program (kcmvp). https://eng....

    work page 2024

  6. [11]

    and Wigderson, A

    Nisan, N. and Wigderson, A. (1994). Hardness vs ran- domness.Journal of Computer and System Sciences, 49(2):149–167. NIST CA VP (2025). Cryptographic Algorithm Validation Program (CA VP). Program Overview CA VP, National Institute of Standards and Technology. Programme website, accessed 30 May

    work page 1994

  7. [12]

    Cryptographic Module Validation Program (CMVP)

    NIST CMVP (2025). Cryptographic Module Validation Program (CMVP). Program Overview CMVP, Na- tional Institute of Standards and Technology. Pro- gramme website, accessed 30 May

    work page 2025

  8. [13]

    Peterson, W. W. and Weldon, Jr., E. J. (1972).Error- Correcting Codes. MIT Press, Cambridge, MA, sec- ond edition. Pfitzmann, B. and Waidner, M. (2001). A model for asyn- chronous reactive systems and its application to secure message transmission. InSP ’01: Proceedings of the 2001 IEEE Symposium on Security and Privacy, page

    work page 1972

Show all 16 references
  1. [15]

    Raz, R., Reingold, O., and Vadhan, S. (2002). Extracting all the randomness and reducing the error in trevisan’s extractors.Journal of Computer and System Sciences, 65(1):97–128. Renner, R. (2005).Security of Quantum Key Distri- bution. PhD thesis, ETH Zurich. Available at htt...

    2002 arXiv

  2. [184]

    Python Language Ref- erence, version 3.x

    Python Software Foundation (2024). Python Language Ref- erence, version 3.x. https://docs.python.org/3/. Ac- cessed May 30,

    2024

  3. [230]

    Bennett, C., Brassard, G., Crepeau, C., and Maurer, U. (1995). Generalized privacy amplification.IEEE Transactions on Information Theory, 41(6):1915–

    1995

  4. [940]

    and Hellman, M

    Diffie, W. and Hellman, M. E. (1976). New directions in cryptography.IEEE Transactions on Information The- ory, 22(6):644–654. Ekert, A. K. (1991). Quantum cryptography based on Bell’s theorem.Physical Review Letters, 67(6):661–663. ETSI ISG-QKD (2016). ETSI GS QKD 011 V1.1.1 ...

    1976

  5. [1923]

    Bennett, C. H. and Brassard, G. (1984). Quantum cryp- tography: Public key distribution and coin tossing. InProceedings of IEEE International Conference on Computers, Systems, and Signal Processing, page 175, India. Boole, G. (1847).The Mathematical Analysis of Logic: Be- ing ...

    1984

  6. [2023]

    A., Palfree, J., Reddy, D

    Kavuri, G. A., Palfree, J., Reddy, D. V ., Zhang, Y ., Bi- enfang, J. C., Mazurek, M. D., Alhejji, M. A., Sid- diqui, A. U., Cavanagh, J. M., Dalal, A., Abell ´an, C., Amaya, W., Mitchell, M. W., Stange, K. E., Beale, P. D., Brand ˜ao, L. T. A. N., Booth, H., Peralta, R., Nam,...

    2024

  7. [2025]

    M., Schwabe, P., Seiler, G., and Stehl´e, D

    Avanzi, R., Bos, J., Ducas, L., Kiltz, E., Lepoint, T., Lyuba- shevsky, V ., Schanck, J. M., Schwabe, P., Seiler, G., and Stehl´e, D. (2020). CRYSTALS-Kyber: Algorithm specifications and supporting documentation. https: //csrc.nist.gov/Projects/post-quantum-cryptography/ post-...

    2020

  8. [5535]

    Trevisan, L. (2001). Extractors and pseudorandom genera- tors.J. ACM, 48(4):860–879. Virtanen, P., Gommers, R., Oliphant, T. E., Haberland, M., Reddy, T., Cournapeau, D., Burovski, E., Peterson, P., Weckesser, W., Bright, J., van der Walt, S. J., Brett, M., Wilson, J., Millman...

    2001

Pith tools

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