Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes on data engineering and communications technologies

The Novel Multi Source Method for the Randomness Extraction

Maksim Iavich, Tamari Kuchukhidze

Published Jan 1, 2023• 0 citations
Publisher
DOI
10.1007/978-3-031-24475-9_6

Related papers

How to Extract Useful Randomness from Unreliable Sources

Divesh Aggarwal, Maciej Obremski, João Ribeiro +2 more

Lecture notes in computer science•Jan 1, 2020•11 citations

Multi-Source Randomness Extractors Against Quantum Side Information, and their Applications

Kai-Min Chung, Xin Li, Xiaodi Wu

We study the problem of constructing multi-source extractors in the quantum setting, which extract almost uniform random bits against quantum side information collected from several initially independent classical random sources. This is a natural generalization of seeded randomness extraction against quantum side information and classical independent source extraction. With new challenges such as potential entanglement in the side information, it is not a prior clear under what conditions do quantum multi-source extractors exist; the only previous work is [KK12], where the classical inner-product two-source extractors of [CG88] and [DEOR04] are shown to be quantum secure in the restricted Independent Adversary (IA) Model and entangled Bounded Storage (BS) Model. In this paper we propose a new model called General Entangled (GE) Adversary Model, which allows arbitrary entanglement in the side information and subsumes both the IA model and the BS model. We proceed to show how to construct GE-secure quantum multi-source extractors. To that end, we propose another model called One-sided Adversary (OA) Model, which is weaker than all the above models. Somewhat surprisingly, we establish equivalence between strong OA-security and strong GE-security. As a result, all classical multi-source extractors can either directly work, or be modified to work in the GE model at the cost of one extra random source. Thus, our constructions essentially match the best known constructions of classical multi-source extractors. We also apply our techniques to two important problems in cryptography and distributed computing --- privacy amplification and network extractor. We show that as long as the sources have certain amounts of conditional min-entropy in our GE model (even with entangled quantum side information), we can design very efficient privacy amplification protocols and network extractors.

arXiv:1411.2315•Electronic colloquium on computational complexity•Nov 10, 2014•10 citations

Algebraic Symmetry and Stochastic Independence: A Comparative Study of Deterministic, Seeded, and Matrix-based Randomness Extraction on QRNG-Generated Datasets

Muhammad Kamran, Roohi Zafar, Tahir Malik

Theoretically, Quantum random number generators (QRNGs) can produce truly random numbers that cannot be predicted in advance and have numerous uses. But in practice, it cannot escape the problem of unwanted classical noise, which reduces the quality of the random bits they produce. Therefore, we need to post-process data from a QRNG’s entropy source to improve the statistical quality of the classical output sequence generated from the quantum entropy source. In this work, we implement and compare six extraction primitives: Von Neumann, Multi-level Peres, Toeplitz-hash, Circulant-hash, Trevisan’s construction, and SHA-256 distillation. Using a large classical random bit stream generated by an experimental QRNG, we evaluate these algorithms based on extraction efficiency (η), computational complexity, and seed-entropy requirements. The findings show that although deterministic approaches, such as Multi-level Peres, outperform von Neumann maps, algebraic approaches, especially Circulant extractors, offer higher throughput (η = 0.90) and lower seed consumption by leveraging the cyclicity of the group Zn. The Trevisan extractor provides strong theoretical security with reduced seed growth, but at the cost of higher computational complexity. In contrast, the SHA-256-based method offers fast practical post-processing but provides no information-theoretic entropy guarantees. Statistical validation via autocorrelation and inter-sequence cross-correlation confirms that all evaluated methods successfully decouple hardware-induced dependencies

International Journal of Modern Physics C•Oct 30, 2026•0 citations

Quantum-Resilient Randomness Extraction

Renato Renner

Lecture notes in computer science•Jan 1, 2011•0 citations

Two-Source Extractors Secure Against Quantum Adversaries

Roy Kasher, Julia Kempe

We initiate the study of multi-source extractors in the quantum world. In this setting, our goal is to extract random bits from two independent weak random sources, on which two quantum adversaries store a bounded amount of information. Our main result is a two-source extractor secure against quantum adversaries, with parameters closely matching the classical case and tight in several instances. Moreover, the extractor is secure even if the adversaries share entanglement. The construction is the Chor-Goldreich [CG88] two-source inner product extractor and its multi-bit variant by Dodis et al. [DEOR04]. Previously, research in this area focused on the construction of seeded extractors secure against quantum adversaries; the multi-source setting poses new challenges, among which is the presence of entanglement that could potentially break the independence of the sources.

arXiv:1005.0512•May 4, 2010•3 citations

New Imperfect Random Source with Applications to Coin-Flipping

Yevgeniy Dodis

Lecture notes in computer science•Jan 1, 2001•12 citations
We study the problem of constructing multi-source extractors in the quantum setting, which extract almost uniform random bits against quantum side information collected from several initially independent classical random sources. This is a natural generalization of seeded randomness extraction against quantum side information and classical independent source extraction. With new challenges such as potential entanglement in the side information, it is not a prior clear under what conditions do quantum multi-source extractors exist; the only previous work is [KK12], where the classical inner-product two-source extractors of [CG88] and [DEOR04] are shown to be quantum secure in the restricted Independent Adversary (IA) Model and entangled Bounded Storage (BS) Model. In this paper we propose a new model called General Entangled (GE) Adversary Model, which allows arbitrary entanglement in the side information and subsumes both the IA model and the BS model. We proceed to show how to construct GE-secure quantum multi-source extractors. To that end, we propose another model called One-sided Adversary (OA) Model, which is weaker than all the above models. Somewhat surprisingly, we establish equivalence between strong OA-security and strong GE-security. As a result, all classical multi-source extractors can either directly work, or be modified to work in the GE model at the cost of one extra random source. Thus, our constructions essentially match the best known constructions of classical multi-source extractors. We also apply our techniques to two important problems in cryptography and distributed computing --- privacy amplification and network extractor. We show that as long as the sources have certain amounts of conditional min-entropy in our GE model (even with entangled quantum side information), we can design very efficient privacy amplification protocols and network extractors.
Theoretically, Quantum random number generators (QRNGs) can produce truly random numbers that cannot be predicted in advance and have numerous uses. But in practice, it cannot escape the problem of unwanted classical noise, which reduces the quality of the random bits they produce. Therefore, we need to post-process data from a QRNG’s entropy source to improve the statistical quality of the classical output sequence generated from the quantum entropy source. In this work, we implement and compare six extraction primitives: Von Neumann, Multi-level Peres, Toeplitz-hash, Circulant-hash, Trevisan’s construction, and SHA-256 distillation. Using a large classical random bit stream generated by an experimental QRNG, we evaluate these algorithms based on extraction efficiency (η), computational complexity, and seed-entropy requirements. The findings show that although deterministic approaches, such as Multi-level Peres, outperform von Neumann maps, algebraic approaches, especially Circulant extractors, offer higher throughput (η = 0.90) and lower seed consumption by leveraging the cyclicity of the group Zn. The Trevisan extractor provides strong theoretical security with reduced seed growth, but at the cost of higher computational complexity. In contrast, the SHA-256-based method offers fast practical post-processing but provides no information-theoretic entropy guarantees. Statistical validation via autocorrelation and inter-sequence cross-correlation confirms that all evaluated methods successfully decouple hardware-induced dependencies
We initiate the study of multi-source extractors in the quantum world. In this setting, our goal is to extract random bits from two independent weak random sources, on which two quantum adversaries store a bounded amount of information. Our main result is a two-source extractor secure against quantum adversaries, with parameters closely matching the classical case and tight in several instances. Moreover, the extractor is secure even if the adversaries share entanglement. The construction is the Chor-Goldreich [CG88] two-source inner product extractor and its multi-bit variant by Dodis et al. [DEOR04]. Previously, research in this area focused on the construction of seeded extractors secure against quantum adversaries; the multi-source setting poses new challenges, among which is the presence of entanglement that could potentially break the independence of the sources.