Stream randomness extraction against quantum side information

Cheng-Kang Pan; Chun-Yang Luan; Gang-Xi Wang; Lin Cheng; Xiang-Jie Lie; Xiang Zhang; Xingjian Zhang

arxiv: 2605.09556 · v1 · submitted 2026-05-10 · 🪐 quant-ph

Stream randomness extraction against quantum side information

Chun-Yang Luan , Xiang-Jie Lie , Lin Cheng , Gang-Xi Wang , Cheng-Kang Pan , Xiang Zhang , Xingjian Zhang This is my paper

Pith reviewed 2026-05-12 04:25 UTC · model grok-4.3

classification 🪐 quant-ph

keywords randomness extractionquantum side informationuniversal2 hashingstream processingToeplitz matrixquantum random number generatorspost-processingsecurity proof

0 comments

The pith

A stream implementation of universal2 randomness extractors preserves security against quantum side information by using an offline mask and online XOR.

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

This paper shows that randomness extractors based on almost dual universal2 hashing can be turned into a streaming form without weakening their proven security against quantum side information. The approach moves the matrix operations into an offline pre-processing stage that creates a pseudo-random mask, after which raw measurement bits are handled immediately by a simple XOR. If the proof holds, real-time quantum random number generators no longer need to buffer complete blocks before extraction. Readers would care because latency and memory demands drop while the original security bounds remain unchanged.

Core claim

The authors prove that this stream implementation strictly preserves the security guarantees of the original block-wise protocols. They shift the computational burden from a time-consuming block-wise post-processing stage into an offline pre-processing stage that generates a pseudo-random mask, allowing raw data to be processed on the fly using bitwise XOR. They detail the transformation for three constructions based on standard Toeplitz, circulant, and modified Toeplitz matrices, and benchmark the resulting stream versions on realistic quantum experimental data.

What carries the argument

The offline-generated pseudo-random mask followed by online XOR, which together preserve the almost-dual universal2 property of the original hash family required for security against quantum adversaries.

If this is right

Toeplitz, circulant, and modified Toeplitz matrix constructions all admit equivalent stream implementations that keep the original security level.
Real-time post-processing of quantum random number generator output becomes possible without extra buffering.
The same security analysis that applies to block-wise universal2 hashing continues to apply directly to the stream version.
Practical benchmarks on experimental quantum data confirm that the stream versions run with reduced latency.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The offline mask stage could be pre-computed once and reused across multiple devices if the mask is generated from a fixed seed.
Similar offline-precompute tricks may apply to other hashing-based post-processing steps in quantum key distribution.
Hardware implementations could exploit the simple XOR step to achieve continuous extraction at the rate of the raw detector.

Load-bearing premise

The mask generated offline must maintain the almost-dual universal2 property when paired with the stream XOR, exactly as needed by the original security proof.

What would settle it

A concrete counter-example in which the stream extractor leaks strictly more information than its block-wise counterpart on the same quantum measurement data and side-information state would disprove the preservation claim.

Figures

Figures reproduced from arXiv: 2605.09556 by Cheng-Kang Pan, Chun-Yang Luan, Gang-Xi Wang, Lin Cheng, Xiang-Jie Lie, Xiang Zhang, Xingjian Zhang.

**Figure 2.** Figure 2: FIG. 2. Runtime comparison between block and stream im [PITH_FULL_IMAGE:figures/full_fig_p006_2.png] view at source ↗

read the original abstract

Randomness extraction is indispensable for quantum random number generators, serving to eliminate bias and potential information leakage from raw measurement data. Conventional extractors operate in a block-wise fashion, requiring the complete accumulation of raw data before processing. To circumvent the latency and buffering overheads that hinder real-time random number generation, recent work introduced a stream-cipher implementation for the randomness extractor based on the Toeplitz matrix hashing. In this work, we generalize this stream-processing paradigm to the broader family of randomness extractors based on (almost dual) universal$_2$ random hashing. Specifically, we shift the computational burden from a time-consuming block-wise post-processing stage into an offline pre-processing stage that generates a pseudo-random mask. This allows the raw data to be processed by the mask on the fly using a simple bitwise exclusive-OR operation. Crucially, we prove that this stream implementation strictly preserves the security guarantees of the original block-wise protocols. We detail the transformation of three typical constructions -- based on standard Toeplitz, circulant, and modified Toeplitz matrices -- from block to stream implementations, and benchmark their practical performance using realistic quantum experimental data. We anticipate our framework will enhance the efficiency of real-time quantum cryptographic systems.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

They show how to convert almost-dual-universal2 extractors to a streaming form via offline mask generation plus online XOR, with a proof that quantum security bounds are preserved.

read the letter

The main point is that this paper takes the stream-extractor trick that was done for Toeplitz hashing and extends it to the wider class of almost dual universal2 functions. They move the matrix construction offline to produce a fixed mask, then reduce the online step to a simple XOR on the incoming raw bits. Explicit recipes are given for the standard Toeplitz, circulant, and modified-Toeplitz cases, and they run the resulting extractors on real quantum random-number data to measure throughput and latency gains. The central claim is that the security proof against quantum side information carries over unchanged from the block-wise version. That claim is the part worth checking first, because if the reduction holds it removes the buffering delay that has been a practical headache for real-time QRNG systems. The argument appears to rely only on the standard properties of these hash families rather than any data-dependent fitting, which keeps the circularity risk low. Benchmarks on experimental traces are included, which is helpful for judging whether the latency savings are real under actual noise levels. The main soft spot is that the full security derivation is only summarized in the abstract; without the detailed steps it is hard to see exactly how the mask is shown to retain the required almost-dual-universal2 distance. Minor gaps in the experimental section, such as how post-processing parameters were chosen and whether they were fixed before looking at the data, could also be tightened. This is useful reading for anyone building low-latency quantum random-number generators for cryptography. A reader who already works with universal2 extractors or quantum key distribution hardware will pick up concrete constructions and a security argument they can adapt. It is worth sending to peer review because the generalization is new, the claimed proof targets a clear practical need, and the experimental component gives something concrete to evaluate even if revisions are needed on the derivation details.

Referee Report

1 major / 3 minor

Summary. The manuscript generalizes stream-cipher implementations of randomness extractors from the Toeplitz case to the broader family of almost-dual-universal₂ hash functions. It shifts computation to an offline pre-processing stage that produces a pseudo-random mask, after which raw data is processed on-the-fly via bitwise XOR. The central claim is an explicit proof that this transformation strictly preserves the security guarantees of the original block-wise protocols against quantum side information, for standard Toeplitz, circulant, and modified-Toeplitz constructions; the work also reports benchmarks on realistic quantum experimental data.

Significance. If the preservation proof is correct, the result removes a key practical obstacle to real-time quantum random number generation by eliminating block-wise buffering and latency while retaining rigorous security bounds. The explicit treatment of three distinct matrix families together with empirical performance data on actual QRNG output strengthens the case for immediate adoption in quantum cryptographic hardware.

major comments (1)

[§4, Theorem 2] §4, Theorem 2 (stream preservation for modified Toeplitz): the argument that the offline mask maintains the required almost-dual-universal₂ distance bound relies on the mask being statistically independent of the quantum side information; the proof sketch does not explicitly quantify any residual correlation introduced by the deterministic PRNG used to generate the mask, which is load-bearing for the 'strictly preserves' claim.

minor comments (3)

[§3.1] §3.1: the notation for the mask vector M and its generation from the seed is introduced without a clear forward reference to the security analysis in §4, making the reduction harder to follow on first reading.
[Table 3] Table 3: extraction-rate and security-parameter columns are reported without error bars or details on the number of experimental runs, which weakens the practical-performance claims even though they are not central to the proof.
[Figure 4] Figure 4 caption: the plotted curves for the three constructions do not state the fixed security parameter ε used, preventing direct comparison with the theoretical bounds derived earlier.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading of our manuscript and the constructive feedback. We are pleased with the positive assessment and address the major comment point by point below.

read point-by-point responses

Referee: [§4, Theorem 2] §4, Theorem 2 (stream preservation for modified Toeplitz): the argument that the offline mask maintains the required almost-dual-universal₂ distance bound relies on the mask being statistically independent of the quantum side information; the proof sketch does not explicitly quantify any residual correlation introduced by the deterministic PRNG used to generate the mask, which is load-bearing for the 'strictly preserves' claim.

Authors: We acknowledge the referee's observation that the proof of Theorem 2 would benefit from an explicit quantification of the mask's independence from the quantum side information. In the construction, the pseudo-random mask is generated entirely offline by a deterministic PRNG whose seed is chosen independently of the quantum system and before any raw data acquisition. Because the PRNG is deterministic, the resulting mask is a fixed string once the seed is fixed, and this fixed mask is statistically independent of the quantum side information by construction. To strengthen the argument and directly address potential residual correlations, we will revise Section 4 to include a detailed remark bounding any such effects under standard cryptographic assumptions on the PRNG (e.g., that the seed is drawn from a distribution independent of the quantum state). This clarification will be incorporated without changing the main theorem statement or the reported security bounds. revision: yes

Circularity Check

0 steps flagged

No significant circularity detected in derivation chain

full rationale

The paper's central claim is an explicit proof that the stream implementation (offline mask + on-the-fly XOR) preserves the security guarantees of the original block-wise almost-dual-universal2 extractors against quantum side information. This is framed as a general reduction relying on standard properties of universal2 hashing, applied to Toeplitz, circulant, and modified-Toeplitz constructions. No load-bearing step reduces by construction to a fitted parameter, self-definition, or self-citation chain; the preservation argument targets precisely the transformation described in the weakest assumption. The derivation remains self-contained against external benchmarks for universal2 extractors, with no renaming of known results or smuggled ansatzes.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the established definition and security properties of (almost dual) universal2 hashing from prior literature; the novel contribution is the stream transformation and its proof.

axioms (1)

standard math Security properties of (almost dual) universal2 random hashing against quantum side information
Invoked as the foundation for both the original block-wise protocols and the stream version.

pith-pipeline@v0.9.0 · 5528 in / 1114 out tokens · 46981 ms · 2026-05-12T04:25:01.222166+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

we prove that this stream implementation strictly preserves the security guarantees of the original block-wise protocols
IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

shift the computational burden ... into an offline pre-processing stage that generates a pseudo-random mask ... bitwise exclusive-OR

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

26 extracted references · 26 canonical work pages

[1]

Concatenatexwith a zero and extend it to ann- bit string,x ′ = (x∥0)∈ {0,1} n, withx ′ n−1 = 0 and x′ i =x i for 0≤i≤n−2

work page
[2]

Generate a circulant matrix fromx ′: Cx′ =   x′ 0 x′ 1 · · ·x ′ n−1 x′ n−1 x′ 0 · · ·x ′ n−2 ... ... ... ... x′ 1 x′ 2 · · ·x ′ 0   .(9)

work page
[3]

basic operation

Apply the matrix product betweenC x′ andyand preserve the firstmbits: z=h y(x) := (Cx′ ·ymod 2) m−1 0 ,(10) where we use (·)j i to denote thei’th to thej’th bits in the underlying vector. In this construction, the seed length is 1 bit longer than the raw data. The random function defined by the cir- culant construction is universal 2 as in Eq. (5). It is ...

work page
[4]

Huang, X

Y. Huang, X. Zhang, and X. Ma, Stream privacy am- plification for quantum cryptography, PRX Quantum3, 020353 (2022)

work page 2022
[5]

Herrero-Collantes and J

M. Herrero-Collantes and J. C. Garcia-Escartin, Quan- tum random number generators, Reviews of Modern Physics89, 015004 (2017)

work page 2017
[6]

X. Ma, X. Yuan, Z. Cao, B. Qi, and Z. Zhang, Quantum random number generation, npj Quantum Information2, 1 (2016)

work page 2016
[7]

Mannalatha, S

V. Mannalatha, S. Mishra, and A. Pathak, A comprehen- 9 sive review of quantum random number generators: con- cepts, classification and the origin of randomness, Quan- tum Information Processing22, 439 (2023)

work page 2023
[8]

X. Ma, F. Xu, H. Xu, X. Tan, B. Qi, and H.-K. Lo, Postprocessing for quantum random-number generators: Entropy evaluation and randomness extraction, Physical Review A87, 062327 (2013), arXiv:1207.1473 [quant-ph]

work page arXiv 2013
[9]

J. L. Carter and M. N. Wegman, Universal classes of hash functions (extended abstract), inProceedings of the Ninth Annual ACM Symposium on Theory of Comput- ing, STOC ’77 (Association for Computing Machinery, New York, NY, USA, 1977) p. 106–112

work page 1977
[10]

Nisan and D

N. Nisan and D. Zuckerman, Randomness is linear in space, Journal of Computer and System Sciences52, 43 (1996)

work page 1996
[11]

C. H. Bennett, G. Brassard, and J.-M. Robert, Pri- vacy amplification by public discussion, SIAM Journal on Computing17, 210 (1988)

work page 1988
[12]

C. H. Bennett, G. Brassard, C. Cr´ epeau, and U. M. Maurer, Generalized privacy amplification, IEEE Trans- actions on Information Theory41, 1915 (1995)

work page 1915
[13]

Renner and R

R. Renner and R. K¨ onig, Universally composable privacy amplification against quantum adversaries, inTheory of Cryptography Conference (TCC 2005), Lecture Notes in Computer Science, Vol. 3378 (Springer, 2005) pp. 407– 425, arXiv:quant-ph/0403133 [quant-ph]

work page arXiv 2005
[14]

Tomamichel, C

M. Tomamichel, C. Schaffner, A. Smith, and R. Ren- ner, Leftover hashing against quantum side informa- tion, IEEE Transactions on Information Theory57, 5524 (2011)

work page 2011
[15]

Q. Li, X. Sun, X. Zhang, and H. Zhou, Im- proved real-time post-processing for quantum ran- dom number generators, Advanced Quantum Technolo- gies 10.1002/qute.202400025 (2024), arXiv:2301.08621 [quant-ph]

work page doi:10.1002/qute.202400025 2024
[16]

Pironio, A

S. Pironio, A. Ac´ ın, S. Massar, A. Boyer de la Giroday, D. N. Matsukevich, P. Maunz, S. Olmschenk, D. Hayes, L. Luo, T. A. Manning, and C. Monroe, Random num- bers certified by Bell’s theorem, Nature464, 1021 (2010)

work page 2010
[17]

J. L. Carter and M. N. Wegman, Universal classes of hash functions, Journal of Computer and System Sciences18, 143 (1979)

work page 1979
[18]

Hayashi and T

M. Hayashi and T. Tsurumaru, More efficient privacy amplification with less random seeds via dual universal hash function, IEEE Transactions on Information Theory 62, 2213 (2016)

work page 2016
[19]

Portmann and R

C. Portmann and R. Renner, Security in quantum cryp- tography, Reviews of Modern Physics94, 025008 (2022)

work page 2022
[20]

Foreman, R

C. Foreman, R. Yeung, A. Edgington, and F. J. Cur- chod, Cryptomite: A versatile and user-friendly library of randomness extractors, Quantum9, 1584 (2025)

work page 2025
[21]

Krawczyk, Lfsr-based hashing and authentication, in Advances in Cryptology — CRYPTO ’94, Lecture Notes in Computer Science, Vol

H. Krawczyk, Lfsr-based hashing and authentication, in Advances in Cryptology — CRYPTO ’94, Lecture Notes in Computer Science, Vol. 839 (Springer, 1994) pp. 129– 139

work page 1994
[22]

Krawczyk, New hash functions for message authenti- cation, inAdvances in Cryptology — EUROCRYPT ’95, Lecture Notes in Computer Science, Vol

H. Krawczyk, New hash functions for message authenti- cation, inAdvances in Cryptology — EUROCRYPT ’95, Lecture Notes in Computer Science, Vol. 921 (Springer,

work page
[23]

Ara´ ujo and S

F. Ara´ ujo and S. Neves, The circulant hash revisited, Journal of Mathematical Cryptology15, 250 (2021)

work page 2021
[24]

T. Tsurumaru, Equivalence of three classical algorithms with quantum side information: Privacy amplifica- tion, error correction, and data compression, IEEE Transactions on Information Theory68, 1016 (2022), arXiv:2009.08823 [quant-ph]

work page arXiv 2022
[25]

Huanget al.[1], Maet al.[5] implicitly prove the equivalence between the primitives oferror correction with quantum side informationandprivacy amplifica- tion against quantum side informationusing the random Toeplitz hashing matrices

work page
[26]

Y.-Q. Nie, L. Huang, Y. Liu, F. Payne, J. Zhang, and J.-W. Pan, The generation of 68 gbps quantum random number by measuring laser phase fluctuations, Review of Scientific Instruments86, 063105 (2015)

work page 2015

[1] [1]

Concatenatexwith a zero and extend it to ann- bit string,x ′ = (x∥0)∈ {0,1} n, withx ′ n−1 = 0 and x′ i =x i for 0≤i≤n−2

work page

[2] [2]

Generate a circulant matrix fromx ′: Cx′ =   x′ 0 x′ 1 · · ·x ′ n−1 x′ n−1 x′ 0 · · ·x ′ n−2 ... ... ... ... x′ 1 x′ 2 · · ·x ′ 0   .(9)

work page

[3] [3]

basic operation

Apply the matrix product betweenC x′ andyand preserve the firstmbits: z=h y(x) := (Cx′ ·ymod 2) m−1 0 ,(10) where we use (·)j i to denote thei’th to thej’th bits in the underlying vector. In this construction, the seed length is 1 bit longer than the raw data. The random function defined by the cir- culant construction is universal 2 as in Eq. (5). It is ...

work page

[4] [4]

Huang, X

Y. Huang, X. Zhang, and X. Ma, Stream privacy am- plification for quantum cryptography, PRX Quantum3, 020353 (2022)

work page 2022

[5] [5]

Herrero-Collantes and J

M. Herrero-Collantes and J. C. Garcia-Escartin, Quan- tum random number generators, Reviews of Modern Physics89, 015004 (2017)

work page 2017

[6] [6]

X. Ma, X. Yuan, Z. Cao, B. Qi, and Z. Zhang, Quantum random number generation, npj Quantum Information2, 1 (2016)

work page 2016

[7] [7]

Mannalatha, S

V. Mannalatha, S. Mishra, and A. Pathak, A comprehen- 9 sive review of quantum random number generators: con- cepts, classification and the origin of randomness, Quan- tum Information Processing22, 439 (2023)

work page 2023

[8] [8]

X. Ma, F. Xu, H. Xu, X. Tan, B. Qi, and H.-K. Lo, Postprocessing for quantum random-number generators: Entropy evaluation and randomness extraction, Physical Review A87, 062327 (2013), arXiv:1207.1473 [quant-ph]

work page arXiv 2013

[9] [9]

J. L. Carter and M. N. Wegman, Universal classes of hash functions (extended abstract), inProceedings of the Ninth Annual ACM Symposium on Theory of Comput- ing, STOC ’77 (Association for Computing Machinery, New York, NY, USA, 1977) p. 106–112

work page 1977

[10] [10]

Nisan and D

N. Nisan and D. Zuckerman, Randomness is linear in space, Journal of Computer and System Sciences52, 43 (1996)

work page 1996

[11] [11]

C. H. Bennett, G. Brassard, and J.-M. Robert, Pri- vacy amplification by public discussion, SIAM Journal on Computing17, 210 (1988)

work page 1988

[12] [12]

C. H. Bennett, G. Brassard, C. Cr´ epeau, and U. M. Maurer, Generalized privacy amplification, IEEE Trans- actions on Information Theory41, 1915 (1995)

work page 1915

[13] [13]

Renner and R

R. Renner and R. K¨ onig, Universally composable privacy amplification against quantum adversaries, inTheory of Cryptography Conference (TCC 2005), Lecture Notes in Computer Science, Vol. 3378 (Springer, 2005) pp. 407– 425, arXiv:quant-ph/0403133 [quant-ph]

work page arXiv 2005

[14] [14]

Tomamichel, C

M. Tomamichel, C. Schaffner, A. Smith, and R. Ren- ner, Leftover hashing against quantum side informa- tion, IEEE Transactions on Information Theory57, 5524 (2011)

work page 2011

[15] [15]

Q. Li, X. Sun, X. Zhang, and H. Zhou, Im- proved real-time post-processing for quantum ran- dom number generators, Advanced Quantum Technolo- gies 10.1002/qute.202400025 (2024), arXiv:2301.08621 [quant-ph]

work page doi:10.1002/qute.202400025 2024

[16] [16]

Pironio, A

S. Pironio, A. Ac´ ın, S. Massar, A. Boyer de la Giroday, D. N. Matsukevich, P. Maunz, S. Olmschenk, D. Hayes, L. Luo, T. A. Manning, and C. Monroe, Random num- bers certified by Bell’s theorem, Nature464, 1021 (2010)

work page 2010

[17] [17]

J. L. Carter and M. N. Wegman, Universal classes of hash functions, Journal of Computer and System Sciences18, 143 (1979)

work page 1979

[18] [18]

Hayashi and T

M. Hayashi and T. Tsurumaru, More efficient privacy amplification with less random seeds via dual universal hash function, IEEE Transactions on Information Theory 62, 2213 (2016)

work page 2016

[19] [19]

Portmann and R

C. Portmann and R. Renner, Security in quantum cryp- tography, Reviews of Modern Physics94, 025008 (2022)

work page 2022

[20] [20]

Foreman, R

C. Foreman, R. Yeung, A. Edgington, and F. J. Cur- chod, Cryptomite: A versatile and user-friendly library of randomness extractors, Quantum9, 1584 (2025)

work page 2025

[21] [21]

Krawczyk, Lfsr-based hashing and authentication, in Advances in Cryptology — CRYPTO ’94, Lecture Notes in Computer Science, Vol

H. Krawczyk, Lfsr-based hashing and authentication, in Advances in Cryptology — CRYPTO ’94, Lecture Notes in Computer Science, Vol. 839 (Springer, 1994) pp. 129– 139

work page 1994

[22] [22]

Krawczyk, New hash functions for message authenti- cation, inAdvances in Cryptology — EUROCRYPT ’95, Lecture Notes in Computer Science, Vol

H. Krawczyk, New hash functions for message authenti- cation, inAdvances in Cryptology — EUROCRYPT ’95, Lecture Notes in Computer Science, Vol. 921 (Springer,

work page

[23] [23]

Ara´ ujo and S

F. Ara´ ujo and S. Neves, The circulant hash revisited, Journal of Mathematical Cryptology15, 250 (2021)

work page 2021

[24] [24]

T. Tsurumaru, Equivalence of three classical algorithms with quantum side information: Privacy amplifica- tion, error correction, and data compression, IEEE Transactions on Information Theory68, 1016 (2022), arXiv:2009.08823 [quant-ph]

work page arXiv 2022

[25] [25]

Huanget al.[1], Maet al.[5] implicitly prove the equivalence between the primitives oferror correction with quantum side informationandprivacy amplifica- tion against quantum side informationusing the random Toeplitz hashing matrices

work page

[26] [26]

Y.-Q. Nie, L. Huang, Y. Liu, F. Payne, J. Zhang, and J.-W. Pan, The generation of 68 gbps quantum random number by measuring laser phase fluctuations, Review of Scientific Instruments86, 063105 (2015)

work page 2015