1 INTRODUCTION↩︎

Quantum cryptography is a multidisciplinary field taking advantage of quantum features, such as entanglement or the impossibility of cloning quantum states, to design cryptographic protocols. Two such protocols are Quantum Key Distribution (QKD) [1], [2] and Quantum Random Number Generators (QRNGs) [3]. QKD allows two honest parties to establish a secret key over an insecure public quantum channel, and QRNGs can produce truly unpredictable randomness.

Besides the physical implementation using quantum technology, quantum cryptographic protocols rely on classical computation and communication. In particular, both QKD and QRNGs depend on classical data processing steps to achieve their goals. One of these steps, privacy amplification [4], is crucial for security. Bugs or deviations from a correct implementation can introduce vulnerabilities and compromise the security guarantees of the protocols. In the case of QKD, this could result in the generation of insecure keys.

Current standardization efforts in quantum cryptography have focused on the security of physical devices and quantum operations [5], [6]. To ensure the security of the complete protocol, these efforts have to be extended to include all classical post-processing tasks. This includes the careful selection and standardization of algorithms, rigorous testing against publicly available test vectors, and validation through well-established certification programs. In contrast to classical cryptographic algorithms and devices [7], [8], such processes do not yet exist for quantum cryptography.

1.1 Our Contribution↩︎

Our work provides a reference implementation of the functions used in privacy amplification allowing to check for correctness.

1. randextract is an open-source Python library that implements (modified) Toeplitz hashing and Trevisan’s extractor, two types of functions commonly used in the privacy amplification step. It is distributed as an easy-to-use Python package. This allows the source code to remain close to the mathematical formulations, reduces the possibility of implementation bugs due to peculiarities of the programming language and improves readability, allowing a large audience to read and audit the code. The library focuses on correctness, containing hundreds of unit and integration tests, and is not performance-optimized.

2. The library can be used directly in a quantum cryptographic protocol to implement the privacy amplification step.

3. The library can be used to test and validate high-performance implementations, whose source code may be unavailable or difficult to audit. We use randextract to test and validate three randomness extractors that have been used in recent QKD and QRNG implementations. With these real world examples, we highlight the importance of the classical post-processing phase for security and correctness.

4. We provide a function to generate test vectors for privacy amplification implementations in order to facilitate external audits. We use the same format as in the NIST Cryptographic Algorithm Validation Program. These test vectors can be used by the community in a validation process included into future standardization efforts of quantum cryptographic devices.

1.2 Outline↩︎

The paper is organized as follows: Sec. 2 introduces the background of quantum key distribution, quantum random number generation and privacy amplification. In particular, Sec. 2.4 introduces the theory of two families of quantum-proof extractors: (modified) Toeplitz hashing and Trevisan’s construction. Sec. 3, 4, and 5 present our main contributions. In Sec. 3, we describe our Python package, randextract, in detail. Sec. 4 demonstrates how the library can be used to test and validate third-party implementations. Notably, using our library, we identify and correct a bug in a modified Toeplitz hashing implementation used in a high-speed QKD experiment. We also uncover discrepancies between the mathematical specification and the actual implementation of a high-performance Trevisan’s construction implementation used in QKD and QRNG experiments.

Sec. 5 introduces a set of test vectors for Toeplitz hashing, proposed as a step towards future standardization efforts. Finally, Sec. 6 presents our conclusions and outlines directions for future work.

2 THEORETICAL BACKGROUND↩︎

2.1 Notation & Definitions↩︎

The capital letters \(X\), \(Y\) and \(Z\) denote classical random variables, which take values \(x\), \(y\) and \(z\). Calligraphic fonts \(\mathcal{X}\), \(\mathcal{Y}\) and \(\mathcal{Z}\) denote the alphabet of the corresponding random variables. The probability that the random variable \(Z\) takes the value \(z\) is \(P_Z(Z=z)\), sometimes abbreviated to \(P_Z(z)\) or \(P(z)\) when it is clear from the context which random variable it refers to. For two random variables \(X\) and \(Y\), the joint probability is defined as \(P_{XY}(x,y)=P(X=x \land Y=y)\), and the conditional probability of \(X\) given \(Y\) as \(P_{X|Y}(x,y)=P_{X|Y=y}(x)=P_{XY}(x,y)/P_Y(y)\).

The guessing probability, defined as the probability of correctly guessing the value of a random variable \(X\), is \[\nonumber p_\text{guess}(X) = \max_{x\in\mathcal{X}}P_X(X=x)\,,\] which motivates the definition of the min-entropy \[\nonumber H_\text{min}(X)=-\log_2 p_\text{guess}(X)\,.\]

The uniform distribution over a random variable \(X\) is denoted by \(U_X\), i.e., each \(x\in\mathcal{X}\) is equally likely, and the guessing probability is \(1/|\mathcal{X}|\).

The statistical distance between two probability distributions \(P_X\) and \(P_Y\), defined over the same alphabet \(\mathcal{X}\), is given by \[\nonumber d(X, Y) = \frac{1}{2} \sum_{x\in\mathcal{X}}\left|P_X(x=x) - P_Y(y=x)\right|\,.\] Operationally, the statistical distance represents the maximum advantage one can gain in correctly identifying whether a single sample was drawn from \(P_X\) or \(P_Y\). A probability distribution of a random variable \(X\) is said to be \(\epsilon-\)close to uniform if its distance with respect to the uniform distribution is bounded by \(\epsilon\), i.e., \[\label{eq:stat95dist} d(X, U) = \frac{1}{2}\sum_{x\in\mathcal{X}}\left|P(x)-\frac{1}{|\mathcal{X}|}\right| \leq\epsilon\,.\tag{1}\]

Greek letters, such as \(\rho\) and \(\sigma\), are used to denote quantum states. Given a Hilbert space \(\mathcal{H}\), a quantum state \(\rho\) can be represented by a positive semi-definite Hermitian operator of unit trace acting on \(\mathcal{H}\). Any quantum state can be expressed in terms of an orthonormal basis \(\{\ket{i}\}_{i}\) of \(\mathcal{H}\) \[\nonumber \rho = \sum_{i,j}\rho_{ij}\ket{i}\bra{j}\,,\] where \(\rho_{ij}\) are complex numbers, \(\rho_{ij}=\rho_{ji}^*\), and \(\require{physics} \Tr[\rho]=\sum_i\rho_{ii}=1\).

Letters from the beginning of the alphabet, such as \(A\), \(B\) or \(E\) are used to denote the subsystems that form a composite quantum system. For example, \(\rho_{ABE}\) denotes a quantum state acting on the Hilbert space \(\mathcal{H}=\mathcal{H}_A\otimes\mathcal{H}_B\otimes\mathcal{H}_E\).

A (classical) random variable \(X\) can be written as a diagonal quantum state \[\nonumber \rho_X=\sum_{x\in\mathcal{X}}P(x)\ketbra{x}\,,\] and the uniform distribution can be represented as the maximally mixed state \[\nonumber \sigma_U=\frac{1}{\dim(\mathcal{H})}\sum_{i=1}^{\dim(\mathcal{H})}\ketbra{i}\,.\]

Of special interest in quantum cryptography are the so-called classical-quantum (cq) states, which allow to represent a quantum system correlated with a classical random variable. Given a probability distribution \(P_X\) and a set of quantum states \(\{\rho_E^x\}_x\), a cq-state is defined as \[\label{eq:cq-state} \rho_{XE}=\sum_{x\in\mathcal{X}}\left(P_X(x)\ketbra{x}\otimes\rho_{E}^x\right)\,.\tag{2}\]

This formalism is particularly relevant in security analyses, where the classical variable models the honest party’s output (e.g., a raw key), and the quantum system \(E\) represents the adversary’s side information.

Quantum measurements are represented by a set of positive operators \(\{E_i\}_i\) satisfying \(\sum_i E_i=\mathbb{1}\). These sets are called Positive Operator-Valued Measure (POVM). Given a state \(\rho\) and a measurement \(\{E_i\}_i\), the probability of measuring the value \(i\) is given by \(\require{physics} \Tr[E_i\rho]\).

The trace distance generalizes the notion of statistical distance to the quantum setting. For two quantum states \(\rho\) and \(\sigma\), it is defined as \[\require{physics} \nonumber d(\rho,\sigma)=\frac{1}{2}\left\|\rho-\sigma\right\|_\text{tr}=\frac{1}{2}\Tr\sqrt{(\rho-\sigma)^\dagger(\rho-\sigma)}\,.\]

Analogously to the statistical distance, the trace distance provides an operational interpretation as a measure of distinguishability between quantum states. If a system is prepared in either \(\rho\) or \(\sigma\) with equal probability, the maximum probability with which the state can be correctly identified; e.g., by doing a (single) quantum measurement or feeding the state into another quantum protocol, is \(\frac{1}{2} + \frac{1}{2}d(\rho,\sigma)\).

The trace distance of a classical random variable \(X\) from uniform from the point of view of an adversary with quantum side information \(E\) is given by \[\label{eq:trace95dist95uniform} d(\rho_{XE},\sigma_U\otimes\rho_E)=\frac{1}{2}\left\|\rho_{XE}-\sigma_U\otimes\rho_E\right\|_\text{tr}\,.\tag{3}\]

Finally, both the guessing probability and the min-entropy can be generalized to the setting of cq-states. The guessing probability of a random variable \(X\) conditioned on a quantum system \(E\) is \[\require{physics} \nonumber p_\text{guess}(X|E)=\max_{\{E_x\}}\sum_{x\in\mathcal{X}}P_X(x)\Tr[\rho_E^xE_x]\,,\] where the maximization is over all the POVMs, and the conditional min-entropy \[\nonumber H_\text{min}(X|E)=-\log_2 p_\text{guess}(X|E)\,.\]

2.2 Quantum Cryptography↩︎

2.2.1 Quantum Key Distribution↩︎

An ideal key distribution protocol is one that produces a bit string that is identical for the honest parties and that looks uniform from the adversary’s point of view. Real protocols cannot usually achieve this perfectly and, instead, produce an output that is \(\epsilon\)-close to the ideal one, i.e., the trace distance between the output of the real and the ideal protocol, as in Eq. 3 , is bounded by \(\epsilon\). The trace distance guarantees that the real protocol is indistinguishable from the ideal protocol, except with probability \(\epsilon\). This notion of security as the distinguishability between an ideal and a real protocol guarantees that the protocol is composable [9]–[12], i.e., it remains secure even if it is used with other protocols to form a larger cryptographic system.

Key distribution is traditionally implemented using public-key cryptography, e.g., RSA [13], Diffie-Hellman [14] or ML-KEM [15], [16]. These protocols are secure if the adversary is limited in computing power, and given some assumptions on the computational hardness of certain mathematical problems.

Quantum Key Distribution (QKD) is a quantum cryptographic protocol that enables two honest parties to establish a shared secret key over an insecure quantum channel. QKD is fundamentally different from public-key cryptography because the established keys are information-theoretically secure [17], i.e., their security does not depend on a limitation in computing power of the adversary.

Any quantum key distribution protocol consists of two distinct phases:

1. a quantum phase, in which quantum states are prepared, transmitted over a public quantum channel, and measured;

2. and a classical phase, in which the classical data that corresponds to the preparation settings and measurement results is post-processed to derive the final shared secret keys.

The classical post-processing involves several subprotocols or steps, which might differ slightly from one particular protocol to another. A common way to implement this phase in a QKD protocol is the following:

1. The starting point after the quantum phase are two raw keys, bit strings held by the honest parties that are neither equal nor completely secret.

2. A sample from the raw keys is compared and then discarded to perform the testing step, also known as parameter estimation. The honest parties reveal some of the bits over the classical channel to estimate the losses and number of errors, which allows to bound the amount of information an adversary might have obtained during the quantum phase. Testing aborts the protocol if this estimation is beyond a certain threshold, and continues otherwise. A real implementation correctly recognizes when an adversary has too much information except with probability \(\epsilon_\text{pe}\).

3. In case the honest parties decide to continue the protocol, the next step is called information reconciliation and corrects the errors of the (remaining) raw keys to obtain the corrected keys. This step ensure the correctness of the protocol, and it is often implemented using error-correcting codes (see e.g., [18]). After this step, the two honest parties hold identical keys, which are partially secret, except with probability \(\epsilon_\text{ir}\).

4. Lastly, the corrected keys are transformed into shorter but completely secret bit strings in the privacy amplification step. These are the final secret keys. At the end of this step, the honest parties still hold equal keys but these are now also secret from the adversary except with probability \(\epsilon_\text{pa}\).

A security proof of a QKD protocol [19] is a theoretical statement, with well-defined conditions and a security claim in terms of a security parameter \(\epsilon\) bounding the probability that the output of the protocol differs from an ideal key distribution protocol, i.e., guarantees that the honest parties end up with an equal, perfectly secure key except with probability \(\epsilon\). If the subprotocols are defined in a composable way, then the security parameter can be bounded in terms of the parameters of these subprotocols using the union bound [20], i.e., \(\epsilon\leq\epsilon_\text{pe}+\epsilon_\text{ir}+\epsilon_\text{pa}\). This security parameter \(\epsilon\) can ideally be made arbitrarily small at the cost of a lower key rate.

2.2.2 Quantum Random Number Generator↩︎

A Quantum Random Number Generator (QRNG) is a type of hardware random number generator that uses quantum systems to generate randomness. Most hardware random number generators use classical physical processes, and since these processes are deterministic, these protocols need to assume that the initial state of the system is only partially known by an adversary. QRNGs, on the other hand, take advantage of the inherent unpredictability of quantum phenomena. Even if a quantum state is perfectly described, the outcome of a measurement is, in general, not deterministic [21].

QRNG protocols are similar to QKD protocols but with just one party involved. In the quantum phase, the same party prepares and measures quantum states, and the classical post-processing does not contain an information reconciliation step. The security notion for QRNG protocols is the same as in QKD, i.e., close-to-uniform randomness even from the point of view of an adversary who might hold a quantum state initially correlated with the state of the QRNG system. The privacy amplification step can be used in exactly the same way as in a QKD protocol. It removes bias arising from the quantum phase and side-information held by an adversary.

2.3 Privacy Amplification with Seeded Randomness Extractors↩︎

As introduced in Sec. 2.2.1, Privacy Amplification (PA) is a classical post-processing procedure whose goal is to compress partially secret (classical) bit strings into bit strings that are uniform and independent of any adversary’s (quantum) knowledge. In the context of QKD, the adversary’s knowledge of the corrected keys can originate from eavesdropping or tampering with the quantum states transmitted over the public quantum channel, as well as from observing the authenticated classical communication, such as the error correction syndrome exchanged during the information reconciliation step.

The correct composable definition of ideal keys or ideal randomness after privacy amplification is an upper bound on Eq. 3 , i.e., \[\nonumber d(\rho_{XE},\sigma_U\otimes\rho_E)\leq\epsilon_\text{pa}\,,\] which guarantees that the final keys from QKD or the output from a QRNG look uniform from an adversary’s point of view, except with a small probability \(\epsilon_\text{pa}\).

2.3.0.1 Seeded Randomness Extractors

Privacy amplification can be implemented using seeded randomness extractors (see e.g., [22]). A seeded randomness extractor is a function that takes as input

1. a weak random source \(X\), i.e., a bit string of length \(n\), and

2. a uniform seed \(Y\), i.e., a bit string of length \(d\),

and outputs a bit string of length \(m\) (see Figure 1), i.e., \[\label{eq:seeded95ext} \text{Ext}\::\: \{0, 1\}^n \times \{0, 1\}^d \rightarrow \{0, 1\}^m\tag{4}\]

A seeded randomness extractor can be used to transform a bit string with high min-entropy into an almost-uniform bit string. In order to correctly implement the privacy amplification step using these extractors we require two additional conditions:

1. The output of the extractor is independent of the seed. This is because the random seed is revealed to the adversary during the execution of the protocol.

2. The output is close to uniform for an adversary with quantum side information.

Extractors satisfying the first condition are called strong, and those satisfying the second condition quantum-proof.

A quantum-proof (\(k,\epsilon)\)-strong seeded randomness extractor [23] is a function defined as in Eq. 4 which, for a uniform independent seed \(Y\) and input \(X\) with conditional min-entropy \(H_\text{min}(X|E)\geq k\), outputs a string \(\text{Ext}(X, Y)\) satisfying \[\label{eq:dist95quantum95proof95ext} d(\rho_{\text{Ext}(X, Y)YE}, \sigma_U\otimes\rho_Y\otimes\rho_E) \leq \epsilon_\text{pa}\,,\tag{5}\] i.e., the output is \(\epsilon_\text{pa}\)-close to the ideal output which is uniform, independent of the seed and uncorrelated to the quantum side information.

In the context of QKD and QRNG protocols, only quantum-proof strong randomness extractors can to be used to realize the privacy amplification step. Therefore, these are the extractors implemented in randextract.

2.4 Construction of Randomness Extractors↩︎

Families of two-universal hash functions are quantum-proof strong extractors. Alternative constructions are possible such as the Trevisan’s construction.

A family of functions \(\mathcal{F}=\{f_y\}_y\), such that \(f_y\::\:\mathcal{X}\rightarrow\mathcal{Z}\), is two-universal if \[\nonumber \Pr_{f_y\in\mathcal{F}}[f_y(x)=f_y(x')]\leq\frac{1}{|\mathcal{Z}|}\,,\] for any distinct \(x,x'\in\mathcal{X}\), and \(f_y\) picked uniformly at random [24]. This means that the number of collisions, when the function is picked uniformly at random, is bounded by the size of the output alphabet. There exist two-universal functions from \(\{0, 1\}^n\) to \(\{0, 1\}^m\) for any positive integers \(0\leq m \leq n\) [25].

A seeded randomness extractor, as defined in Eq. 4 , is realized from a family of two-universal hash functions \(\mathcal{F}\) by using the seed \(y\in\mathcal{Y}\) to choose one particular function \(f_y\in\mathcal{F}\) and hashing the input \(x\in\mathcal{X}\) with this chosen function, i.e., \[\label{eq:ext95from95universal} \text{Ext}(x, y):= f_y(x)\,.\tag{6}\]

The quantum leftover hash lemma [19], [26], [27] states that a family of two-universal functions, as defined in Eq. 6 , is a quantum-proof \((k, \epsilon_\text{pa})\)-strong extractor for output length \(m\) less or equal than \[\nonumber \left\lfloor k + 2 - 2\log \frac{1}{\epsilon}\right\rfloor\,.\]

2.4.1 Toeplitz Hashing↩︎

The set of all binary \(m\times n\) Toeplitz matrices defines a family of two-universal hash functions, where each matrix corresponds to a specific function in the family. A matrix \(T\) is said to be a Toeplitz matrix if its elements satisfy \[\label{eq:Toeplitz95matrix} T_{i,j}=T_{i-1,j-1}\,.\tag{7}\] Toeplitz matrices are, therefore, fully characterized by their first row and column.

One common method to select a specific matrix from this family using the seed \(y\) is to define the matrix entries based on \(y\) as follows: \[\label{eq:Toeplitz95matrix95seed95construction} T_{i,j}(y):= y_{i-j}\,.\tag{8}\]

2.4.1.1 Standard Toeplitz Hashing

Using Eq. 8 to construct a matrix from the seed, the standard Toeplitz hashing (see e.g., [28]) is defined as \[\label{eq:ext95toeplitz} \text{Ext}_\text{\tiny Toeplitz}(x, y):=T(y)\cdot x\,.\tag{9}\] Figure 2 shows this construction graphically.

2.4.1.2 Efficient implementation

General matrix-vector multiplication has a computational complexity \(\mathcal{O}(n^2)\). However, the matrix-vector multiplication of Toeplitz hashing can be implemented more efficiently with a computational complexity \(\mathcal{O}(n\log n)\) using the Fast Fourier Transform (FFT). First, the \(m\times n\) Toeplitz matrix is transformed into a square \((m+n-1)\times(m+n-1)\) circulant matrix by adding \(n-1\) additional rows and \(m-1\) columns. Then, this matrix can be diagonalized using the Fourier matrix \(F_q\), whose matrix elements are determined by \(F_{j,k}=\frac{1}{\sqrt{q}}e^{2\pi ijk/q}\) with \(q=m+n-1\). The circulant matrix can, therefore, be written in terms of the seed \(y\) as \[\nonumber \hat{T}_q(y)=F_q^{-1}\text{diag}(F_q y)F_q\,.\]

And the complete Toeplitz extractor as \[\nonumber \text{Ext}_\text{\tiny Toeplitz}(x,y)=\text{FFT}^{-1}\Big(\text{FFT}(y) \odot \text{FFT}(\hat{x})\Big)\Big|_{0\dots m-1}\,,\] where \(\hat{x}\) is the input \(x\) padded with \(m-1\) zeros, \(\odot\) denotes element-wise multiplication of the two vectors, and \(|_{0\dots m-1}\) means that the output of the inverse fast Fourier transform is truncated to the first \(m\) bits (see App. C from [29]).

2.4.1.3 Modified Toeplitz Hashing

Standard Toeplitz hashing requires a seed of length \(m + n - 1\) bits. However, it is possible to reduce the seed length to \(n - 1\) bits by using a different family of two-universal hash functions [29]. For the same input and output lengths, the so-called modified Toeplitz hashing uses as its hashing matrix the concatenation of a smaller Toeplitz matrix with the \(m \times m\) identity matrix, i.e., \[\label{eq:ext95mod95toeplitz} \text{Ext}_\text{\tiny Mod.~Toeplitz}(x, y) := (T'(y) \,\|\, \mathbb{1}_m)x\,,\tag{10}\] where \(T'(y)\) is a Toeplitz matrix of dimension \(m \times (n - m)\). The matrix-vector multiplication remains efficiently computable using the same FFT-based approach described above.

2.4.2 Trevisan’s Construction↩︎

Two-universal hashing is not the only way to define strong quantum-proof seeded extractors. Trevisan [30] developed a method to construct arbitrary extractors from one-bit extractors and weak designs. Later, it was proven that this construction generates a quantum-proof strong extractor [31] from a strong one-bit extractor.

2.4.2.1 One-Bit Extractors

One-bit extractors are simply extractors defined as in Eq. 4 with \(m=1\). Any one-bit \((k,\epsilon)\)-strong extractor is a quantum-proof \((k-\log\epsilon, 3\sqrt{\epsilon})\)-strong extractor. If the one-bit extractor is already classical-proof, then it can be shown that it is also a quantum-proof \((k,(1+\sqrt{2})\sqrt{\epsilon})\)-strong extractor [32].
A combinatorial design [33] is a family of subsets \(W=[S_0,S_1,\dots,S_{m-1}]\), with \(S_i\subseteq[d]\), typically constructed so that the intersections between the subsets satisfy certain constraints. These designs are widely used in theoretical computer science due to their ability to balance overlap and independence.

2.4.2.2 Weak Design

A weak \((m,t,r,d)\)-design is a combinatorial design, i.e., a family of sets \(W=[S_0, S_1,\dots,S_{m-1}]\in[d]\), where all sets are of size \(t\), satisfying \[\label{eq:weak-design-bound} \sum_{j=0}^{i-1}2^{|S_i\cap S_j|}\leq rm\tag{11}\] for all \(i\) [34].

2.4.2.3 Trevisan’s extractor

Given a quantum-proof strong one-bit extractor \(\text{Ext}_1(x, y)\) and a weak design \(W=[S_0,\dots,S_{m-1}]\), Trevisan’s extractor is realized as \[\label{eq:trevisan95construction} \text{Ext}_\text{\tiny Trevisan}(x, y):=\text{Ext}_1(x, y_{S_0})\dots \text{Ext}_1(x, y_{S_{m-1}})\,.\tag{12}\] Figure 3 shows this construction graphically.

2.4.2.4 Computational complexity

The computational complexity of Trevisan’s construction depends on the specific choice of the weak design and the one-bit extractor. In practice, Trevisan’s extractor is often significantly slower than Toeplitz hashing. However, it offers an important advantage: certain constructions require only a seed of polylogarithmic length in the input size. For instance, the construction using a weak design over a finite field and a polynomial-time one-bit extractor requires a seed of length \(\mathcal{O}(\log^2 n)\) [35]. In contrast, Toeplitz and modified Toeplitz hashing require seeds of length \(\mathcal{O}(n)\). Trevisan’s extractor may therefore be preferable in scenarios where good randomness is a scarce resource.

3 RANDEXTRACT↩︎

randextract is our open-source Python package implementing some of the most used privacy amplification algorithms. It is available at the Python Package Index (PyPI) [36]. We recommend installing it in a virtual Python environment, for example, by running the following commands

python -m venv --upgrade-deps env-randextract
source env-randextract/bin/activate
pip install randextract

Other ways of installing the package are described in the latest available online documentation.

3.1 Overview & Goals↩︎

The goal of randextract is to provide a readable and easy-to-audit library implementing most of the PA algorithms used in quantum cryptographic protocols. The source code stays close to the mathematical formulation to avoid deviations and facilitate the audit of its correctness. Only when it can be done without impacting this primary goal, secondary goals such as performance are taken into consideration. The package also provides classes and helping functions to aid validating third-party implementations. The package is intended to be self-contained, with comprehensive documentation that introduces the theory of randomness extractors, explains their relevance to quantum cryptographic protocols, includes several toy examples suitable for manual computation, and provides real-world validation cases.

3.2 Structure & Design↩︎

The source code repository follows a standard Python structure.

• src/randextract: source code of the library.

• tests: unit and integration tests.

• docs/source: source code of the online documentation.

• examples: scripts validating real world privacy amplification implementations.

• resources: additional resources such as plots, datasets used in testing and the scripts to generate them, Jupyter notebooks, test vectors, etc.

The package is modular by design allowing to be easily extended in the future with additional extractors. A common API is enforced using abstract classes. For example, the abstract class RandomnessExtractor defined in the module randomness_extractor.py requires that the implementation classes, such as the ToeplitzHashing class, implement the properties input_length, seed_length and output_length, and the method extract().

3.3 Dependencies↩︎

randextract uses the Python Standard Library [37] and the well-known numerical libraries NumPy [38] and Scipy [39]. In addition, the Galois package [40] is used to compactly define arrays and polynomials over finite fields.

3.4 Usage↩︎

randextract can be used directly to implement the PA step of quantum cryptographic protocols. It can also be used to validate other implementations. In both cases the workflow is the same:

1. Choose a particular class of seeded randomness extractors.

2. Instantiate one particular extractor with the desired input and output lengths, and the required parameters. When using randextract to implement the PA step, the optimal parameters can be calculated with the library. When validating other implementations, these have to match the implementation being tested.

3. Extract the randomness from the weak source, or validate the implementation.

3.4.0.1 Implementing PA

The choice of the extractor class in Step 1 depends on the requirements of the quantum cryptographic protocol. In Step 2, the optimal input and output lengths can be computed using randextract, based on the model of the weak randomness source and the desired security parameter \(\epsilon_\text{pa}\) from Eq. 5 . This is handled by the calculate_length() helper method available in any RandomnessExtractor implementation. Finally, the output is computed in Step 4 by calling the extract() method on the instantiated extractor.

3.4.0.2 Validating other implementations

To validate an external implementation, Steps 1 and 2 must follow the same extractor class and parameter choices. In Step 3, rather than manually extracting outputs and comparing them across different seeds and inputs, the custom extractor can be passed directly to the Validator class. External implementations are registered using the add_implementation() method, and validation is performed via the validate() method. Any failing test cases are recorded, and detailed insights into discrepancies can be obtained using the analyze_failed_test() method.

3.5 Code Examples↩︎

3.5.1 Toeplitz Hashing↩︎

3.5.1.1 Implementing PA with Toeplitz hashing

The following code snippet illustrates how to create an extractor based on standard Toeplitz hashing, as defined in Eq. 9 . First, the relevant classes are imported:

from galois import GF2

import randextract
from randextract import (
    RandomnessExtractor,
    ToeplitzHashing
)

Next, the optimal output length is computed for inputs of 8 Mib originating from a weak random source with initial min-entropy \(\frac{1}{n}H_\text{min}(X|E)\geq\frac{1}{2}\), and for a security parameter of \(\epsilon_\text{pa}=10^{-6}\).

Mib = 2**20

out_len = ToeplitzHashing.calculate_length(
    extractor_type="quantum",
    input_length=8*MiB,
    relative_source_entropy=0.5,
    error_bound=1e-6,
)

A Toeplitz hashing extractor is then instantiated for the corresponding input and output lengths:

ext = RandomnessExtractor.create(
    extractor_type="toeplitz",
    input_length=8*MiB,
    output_length=out_len
)

Finally, the hashing is applied to (pseudo)random input and seed bit strings:

ext_int = GF2.Random(MiB)
ext_seed = GF2.Random(ext.seed_length)
ext_out = ext.extract(ext_int, ext_seed)

3.5.1.2 Validating a third-party implementation of modified Toeplitz hashing

The following code snippet demonstrates how to validate a third-party implementation. First, two additional classes are imported:

from randextract import (
    ModifiedToeplitzHashing,
    Validator
)

The reference extractor is instantiated using the ModifiedToeplitzHashing class, which implements Eq. 10 , with the same input and output lengths as the implementation under test. In this case, the extractor takes inputs of 1 Mib and compresses them by 50%. The resulting object is functionally equivalent to one created via RandomnessExtractor.create(), as shown in the previous example.

ref_ext = ModifiedToeplitzHashing(
    input_length=2**20,
    output_length=2**19
)

An auxiliary function is defined to convert binary arrays into string representations:

def gf2_to_str(gf2_arr):
    arr = np.array(gf2_arr)
    arr_str = (arr + ord("0")).tobytes()
    return arr_str.decode()

A Validator instance is then initialized with the reference extractor, and the third-party implementation is registered. The validator is configured to interact with the implementation via standard input/output, using the previously defined conversion function as a parser:

val = Validator(ext)
val.add_implementation(
    label="Rust-stdio-fft",
    input_method="stdio",
    command="./modified_toeplitz $SEED$ $INPUT$",
    format_dict={
        "$SEED$": gf2_to_str,
        "$INPUT$": gf2_to_str
    },
)

Validation is performed using \(10^4\) randomly generated input samples:

val.validate(
    mode="random",
    sample_size=10**4
)

3.5.2 Trevisan’s extractor↩︎

To instantiate a randomness extractor based on Trevisan’s construction, additional parameters must be specified. In addition to the input and output lengths, common to all seeded extractors, one must select concrete implementations for the one-bit extractor and the weak design. These implementations may impose constraints on the parameters. For instance, the weak design provided by the class FiniteFieldPolynomialDesign requires the size of the subsets to be a prime number (or a prime power). Such constraints are automatically handled by the calculate_length() method.

The following example shows how to instantiate a Trevisan extractor configured to take 1 Mib of input and output 1 Kib, using a finite field weak design and a polynomial-based one-bit extraction. No additional imports are required:

ext = RandomnessExtractor.create(
   extractor_type="trevisan",
   weak_design_type="finite_field",
   one_bit_extractor_type="polynomial",
   one_bit_extractor_seed_length=1024,
   input_length=2**20,
   output_length=2**10,
)

Once the extractor object has been instantiated, the extraction process is performed identically across all implementations:

ext_input = GF2.Random(ext.input_length)
ext_seed  = GF2.Random(ext.seed_length)
ext_out = ext.extract(ext_input, ext_seed)

Additional examples and the complete API documentation for randextract are available online¹.

4 VALIDATING PRIVACY AMPLIFICATION IMPLEMENTATIONS↩︎

randextract is well-suited for small proof-of-concept implementations or protocols where privacy amplification can be performed offline. In contrast, production environments requiring real-time privacy amplification typically demand performance-optimized and highly efficient implementations. In the last years, due to huge improvements on the quantum-physical part of quantum cryptography protocols [41], the classical post-processing has become a bottleneck [42]. The secret key rate of QKD protocols and the throughput of QRNGs is limited by how fast the classical post-processing can be done. This has motivated the development of high-performance implementations of both information reconciliation and PA algorithms, using hardware accelerators such as GPUs [43] or FPGAs [44]. These implementations are harder to read and audit, and deviations from the mathematical definitions are harder to spot.

In this section we show how we used randextract to test, validate and fix such high-performance PA implementations.

4.1 GPU modified Toeplitz hashing↩︎

Modern GPUs can accelerate a wide range of computational tasks, including the calculation of the FFT. A CUDA and Vulkan-based implementation of the modified Toeplitz hashing algorithm [43] was employed in a QKD experiment [45] involving ultrafast single-photon detectors, where constraints on block lengths and throughput made the use of FPGAs impractical. To the best of our knowledge, this remains the fastest known implementation of modified Toeplitz hashing.

We tested the GPU-based implementation using our own extractor alongside the Validator class. Instead of relying on files for input and output, we integrated our package with the GPU implementation using ZeroMQ queues, which are its preferred communication interface. During validation, we immediately observed discrepancies in approximately half of the tests involving randomized inputs, specifically those where the last bit was set to 1. This allowed us to quickly identify the root cause of the issue: the GPU implementation was ignoring the final bit of the input vector.

Our library helped us in identifying and fixing the issue. The GPU implementation is available online² and our validation is provided as an example in the repository³.

4.2 Rust Toeplitz hashing↩︎

Rust is a modern programming language that is designed to achieve both memory safety and high performance [46]. Memory safety is a valuable feature for all software, but it is especially critical for software used in cryptographic protocols since many serious security bugs are caused by memory related issues [47]. To explore this further, a Rust implementation of Toeplitz hashing was developed at the Lucerne University of Applied Sciences and Arts as part of a semester student project⁴. The primary goal was to evaluate the performance of a CPU-based Toeplitz hashing implementation within a memory-safe environment.

We used the Validator class to exhaustively test all possible input–seed pairs for small input lengths by interacting directly with the Rust process. For larger input vectors, we conducted randomized tests using file-based input and output. The library was employed throughout the development of the Rust implementation for continuous testing, to support identifying bugs and handling edge cases.

4.3 C++ Trevisan’s construction↩︎

Validating Trevisan’s extractors is more complex than validating extractors based on two-universal hashing. This increased complexity arises from the greater number of configurable components in Trevisan’s construction, such as the choice of one-bit extractor and weak design.

A C++ high-performance implementation of Trevisan’s construction providing two different weak designs and three one-bit extractors was developed in [35]. This library was used in QRNG [48] and QKD [49] experiments.

When validating this implementation, we identified three issues affecting the basic weak design implementation based on finite fields. Two of these are caused by an over-optimization of the multiplication and addition operations, which are implemented using left-shift and bitwise OR operations, respectively. While such optimizations are correct for powers of two, they are generally invalid when working with finite fields of arbitrary order, such as those used in this implementation. As a result, the computed subset overlap violates the bound specified in Eq. 11 , indicating that the resulting family of subsets does not form a valid weak design. Consequently, the Trevisan’s construction, as defined in Eq. 12 , using these subsets is not a strong quantum-proof extractor. The third issue concerns a deviation in how polynomial evaluation is performed. In particular, the coefficients are interpreted in reverse compared to the formulation in App. C.1 of [35]. We believe this deviation does not affect the correctness of the weak design, but it does result in outputs that differ from our implementation.

A full description of the issues and solutions are contained directly in the library repository⁵.

5 TEST VECTORS FOR PRIVACY AMPLIFICATION↩︎

Classical cryptographic functions are heavily standardized. There exist standards and procedures to get certified (see e.g., [50]). The National Institute of Standards and Technology (NIST) operates the Cryptographic Module Validation Program (CMVP), which promotes the use of validated cryptographic modules. The validation proceeds in two steps:

1. First, the underlying cryptographic algorithms and their components are tested and validated through the Cryptographic Algorithm Validation Program (CAVP) [8]. This validation is performed using the Automated Cryptographic Validation Test System in a black-box manner. The implementation receives a list of inputs in a request file (.req). The implementation then obtains the outputs based on those inputs and generates a response file (.rsp), which contains both the provided inputs from the received request and the outputs.

2. Then, the full cryptographic module, including software or hardware integration, is tested under the CMVP [7]. This step involves functional testing, documentation review, and an evaluation of the module’s conformance to requirements defined in standards such as FIPS 140-3 [51]. The testing is performed by accredited third-party laboratories, and successful validation results in an official NIST certificate, authorizing the module for use in regulated and security-sensitive environments.

Other countries, such as Spain [52] in Europe and South Korea [53] in Asia, have similar validation processes for cryptographic modules, typically based on the ISO/IEC 19790 standard [54].

Currently, no equivalent validation program exists for the algorithms used in quantum cryptographic devices. Most efforts have focused on the physical layer, particularly on mitigating side-channel attacks. Looking ahead, it is crucial to establish validation frameworks for the classical post-processing steps of QKD, especially for the steps that are crucial for the final security such as parameter estimation or privacy amplification, since these are the steps that guarantee the secrecy of the final key. Standardization of QKD protocols should define a set of approved PA algorithms, which would then be subject to testing in a CAVP-like program using randomly generated test vectors. These vectors should comprehensively reflect the range of inputs that the device is expected to handle in practice, taking into account both its operational capabilities and the constraints dictated by the protocol’s security proof. After the successful completion of these tests, the post-processing modules can be validated under a CMVP-style certification program.

The Validator class in randextract can generate tests vectors following the same format as the request (.req) and response (.rsp) files used in CAVP.

5.1 Example: Test Vectors for Toeplitz Hashing↩︎

As an example, we provide below a response file for a small modified Toeplitz hashing extractor. Additional larger examples are available online⁶. Request and response files for any randomness extractor implemented in randextract can be generated using the generate_test_vector() method from the Validator class.

# CAVS
# ModifiedToeplitzHashing
# Input Length : 128
# Compression ratio: 1/2
# Generated on Tue May 20 15:12:03 2025

[EXTRACT]

COUNT = 0
INPUT = e3fc097a6dcc77fc781a7ed3533528c8
SEED = 05f47ea39db462da99e3e29b06721ae6
OUTPUT = ab264a34f8ebc27c

COUNT = 1
INPUT = ff3d1bfe1f4c15730dc6ec1c36c7c4e8
SEED = 3eeaf730861d37e9d751d29fd6ad0ece
OUTPUT = 6411c793f97badae

COUNT = 2
INPUT = b7fa3c803d20709f25603bb1b3072917
SEED = 63296df538784e26c446211c058eb9a4
OUTPUT = 3bcfb106e23573e2

COUNT = 3
INPUT = 42c2ddcaef33a3e7998104c76605a588
SEED = 05b7c4012ffc8b5a17cdc544f3e7e2fd
OUTPUT = 48f041d38296ffcc

COUNT = 4
INPUT = a14c3632e4fbffff0e10b10ba4ccdc5d
SEED = 7733fabb766a34b3883762e240db6f20
OUTPUT = 16b0ed99752aa43a

COUNT = 5
INPUT = 23473c65a2c5ab8dbe073f8e419ccee7
SEED = 0c50697d5a102b6ef9016e809fb6a515
OUTPUT = f0b5b4d1f7cb519f

COUNT = 6
INPUT = 5b2719a61b8f72e208587b4ad0ec8ac0
SEED = 0ee322c8bfa4a7e901b3e0bcb0f8bad3
OUTPUT = b1731fb59a4bdb98

COUNT = 7
INPUT = 82c6f364c42caa101fb70e562585fc86
SEED = 29aa29456ea804ca102737d1d150e221
OUTPUT = d35034bccd12b0c4

6 CONCLUSIONS & FUTURE WORK↩︎

The correctness of classical post-processing, and in particular the privacy amplification step, is essential for the security of real quantum cryptographic protocols. Only through careful and rigorous validation can the keys obtained in QKD protocols be secure in practice. Deviations from correct privacy amplification procedures may enable practical attacks, allowing adversaries, even those without quantum capabilities, to partially or fully recover the secret keys.

Our main contribution is an open-source Python library that implements quantum-proof strong extractors used in QKD and QRNG protocols. The library is designed for readability and auditability, with implementations closely following the mathematical definitions. We used this library to test, validate, and fix issues in external high-performance implementations.

Future work can add new classes of functions to randextract such as quantum-proof two-source (seedless) extractors. The modular design of the library will facilitate this task. Additionally, randextract can provide an open platform to test and validate quantum cryptographic protocols in ongoing post-processing standardization efforts at ETSI, ITU-T, etc.

ACKNOWLEDGMENTS↩︎

This work was supported by the Swiss National Science Foundation Practice-to-Science Grant No 199084.

References↩︎