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

arXiv:1212.0520

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

Wolfgang Mauerer, Christopher Portmann, Volkher B. Scholz

Published Dec 3, 2012• 20 citations
arXivHTMLPDF

Abstract

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

DOI
10.48550/arxiv.1212.0520

Related papers

Trevisan's Extractor in the Presence of Quantum Side Information

Anindya De, Christopher Portmann, Thomas Vidick +1 more

Randomness extraction involves the processing of purely classical information and is therefore usually studied with in the framework of classical probability theory. However, such a classical treatment is generally too restrictive for applications where side information about the values taken by classical random variables may be represented by the state of a quantum system. This is particularly relevant in the context of cryptography, where an adversary may make use of quantum devices. Here, we show that the well-known construction paradigm for extractors proposed by Trevisan is sound in the presence of quantum side information. We exploit the modularity of this paradigm to give several concrete extractor constructions, which, e.g., extract all the conditional (smooth) min-entropy of the source using a seed of length polylogarithmic in the input, or only require the seed to be weakly random.

arXiv:0912.5514•SIAM Journal on Computing•Jan 1, 2012•161 citations

A Novel Hybrid Method for Randomness Extraction

Maksim Iavich, Роман Сергійович Одарченко

Randomness is widely used in various fields, including encryption, statistical analysis, and numerical simulations. Randomness is also a fundamental resource in science and engineering. For such applications, we usually need to provide unbiased and independent random bits. This raises the issue of where to get these supposed random bits. Quantum random number generators (QRNGs) generate real random numbers based on the inherent randomness of quantum measurements. In practice, unfortunately, quantum randomness is inevitably mixed with classical randomness due to classical noise. Also, randomness is often correlated and biased. It is necessary to process the resulting raw bits sequence and convert them to good-quality output values that are as close to uniform distribution as possible. Random extractors are required for this. We analyze the randomness obtained by quantum random number generators as well as various examples of post-processing. We discuss the types of randomness extractors. Also, we use information-theoretically secure extractors and present improved novel randomness extraction.

CRC Press eBooks•May 30, 2025•0 citations

Trevisan's extractor in the presence of quantum side information (Mathematical Foundations and Applications of Computer Science and Algorithms)

Anindya De, Christopher Portmann, Thomas Vidick +1 more

Randomness extraction involves the processing of purely classical information and is therefore usually studied in the framework of classical probability theory.However, such a classical treatment is generally too restrictive for applications, where side information about the values taken by classical random variables may be represented by the state of a quantum system.This is particularly relevant in the context of cryptography, where an adversary may make use of quantum devices.Here, we show that the well known construction paradigm for extractors proposed by hevisan is sound in the presence of quantum side information.We exploit the modularity of this paradigm to give several concrete extractor construc- tions, which.e.g, extract all the conditional (smooth) min-entropy of the source using a seed of length poly-logarithmic in the input, or only require the seed to be weakly random.

•Jun 1, 2011•0 citations

Near-optimal extractors against quantum storage

Anindya De, Thomas Vidick

We show that Trevisan's extractor and its variants \cite{T99,RRV99} are secure against bounded quantum storage adversaries. One instantiation gives the first such extractor to achieve an output length $Θ(K-b)$, where $K$ is the source's entropy and $b$ the adversary's storage, together with a poly-logarithmic seed length. Another instantiation achieves a logarithmic key length, with a slightly smaller output length $Θ((K-b)/K^γ)$ for any $γ>0$. In contrast, the previous best construction \cite{TS09} could only extract $(K/b)^{1/15}$ bits. Some of our constructions have the additional advantage that every bit of the output is a function of only a polylogarithmic number of bits from the source, which is crucial for some cryptographic applications. Our argument is based on bounds for a generalization of quantum random access codes, which we call \emph{quantum functional access codes}. This is crucial as it lets us avoid the local list-decoding algorithm central to the approach in \cite{TS09}, which was the source of the multiplicative overhead.

arXiv:0911.4680•Nov 24, 2009•1 citation

Quantum-proof multi-source randomness extractors in the Markov model

Rotem Arnon-Friedman, Christopher Portmann, Volkher B. Scholz

Randomness extractors, widely used in classical and quantum cryptography and other fields of computer science, e.g., derandomization, are functions which generate almost uniform randomness from weak sources of randomness. In the quantum setting one must take into account the quantum side information held by an adversary which might be used to break the security of the extractor. In the case of seeded extractors the presence of quantum side information has been extensively studied. For multi-source extractors one can easily see that high conditional min-entropy is not sufficient to guarantee security against arbitrary side information, even in the classical case. Hence, the interesting question is under which models of (both quantum and classical) side information multi-source extractors remain secure. In this work we suggest a natural model of side information, which we call the Markov model, and prove that any multi-source extractor remains secure in the presence of quantum side information of this type (albeit with weaker parameters). This improves on previous results in which more restricted models were considered and the security of only some types of extractors was shown.

arXiv:1510.06743•Oct 22, 2015•0 citations

Quantum-Proof Multi-Source Randomness Extractors in the Markov Model

Rotem Arnon-Friedman, Christopher Portmann, Volkher B. Scholz

Randomness extractors, widely used in classical and quantum cryptography and other fields of computer science, e.g., derandomization, are functions which generate almost uniform randomness from weak sources of randomness. In the quantum setting one must take into account the quantum side information held by an adversary which might be used to break the security of the extractor. In the case of seeded extractors the presence of quantum side information has been extensively studied. For multi-source extractors one can easily see that high conditional min-entropy is not sufficient to guarantee security against arbitrary side information, even in the classical case. Hence, the interesting question is under which models of (both quantum and classical) side information multi-source extractors remain secure. In this work we suggest a natural model of side information, which we call the Markov model, and prove that any multi-source extractor remains secure in the presence of quantum side information of this type (albeit with weaker parameters). This improves on previous results in which more restricted models were considered or the security of only some types of extractors was shown.

Leibniz international proceedings in informatics•Jan 1, 2016•11 citations
Informally, an extractor delivers perfect randomness from a source that may be far away from the uniform distribution, yet contains some randomness. This task is a crucial ingredient of any attempt to produce perfectly random numbers---required, for instance, by cryptographic protocols, numerical simulations, or randomised computations. Trevisan's extractor raised considerable theoretical interest not only because of its data parsimony compared to other constructions, but particularly because it is secure against quantum adversaries, making it applicable to quantum key distribution. We discuss a modular, extensible and high-performance implementation of the construction based on various building blocks that can be flexibly combined to satisfy the requirements of a wide range of scenarios. Besides quantitatively analysing the properties of many combinations in practical settings, we improve previous theoretical proofs, and give explicit results for non-asymptotic cases. The self-contained description does not assume familiarity with extractors.
Randomness extraction involves the processing of purely classical information and is therefore usually studied with in the framework of classical probability theory. However, such a classical treatment is generally too restrictive for applications where side information about the values taken by classical random variables may be represented by the state of a quantum system. This is particularly relevant in the context of cryptography, where an adversary may make use of quantum devices. Here, we show that the well-known construction paradigm for extractors proposed by Trevisan is sound in the presence of quantum side information. We exploit the modularity of this paradigm to give several concrete extractor constructions, which, e.g., extract all the conditional (smooth) min-entropy of the source using a seed of length polylogarithmic in the input, or only require the seed to be weakly random.
Randomness is widely used in various fields, including encryption, statistical analysis, and numerical simulations. Randomness is also a fundamental resource in science and engineering. For such applications, we usually need to provide unbiased and independent random bits. This raises the issue of where to get these supposed random bits. Quantum random number generators (QRNGs) generate real random numbers based on the inherent randomness of quantum measurements. In practice, unfortunately, quantum randomness is inevitably mixed with classical randomness due to classical noise. Also, randomness is often correlated and biased. It is necessary to process the resulting raw bits sequence and convert them to good-quality output values that are as close to uniform distribution as possible. Random extractors are required for this. We analyze the randomness obtained by quantum random number generators as well as various examples of post-processing. We discuss the types of randomness extractors. Also, we use information-theoretically secure extractors and present improved novel randomness extraction.
Randomness extraction involves the processing of purely classical information and is therefore usually studied in the framework of classical probability theory.However, such a classical treatment is generally too restrictive for applications, where side information about the values taken by classical random variables may be represented by the state of a quantum system.This is particularly relevant in the context of cryptography, where an adversary may make use of quantum devices.Here, we show that the well known construction paradigm for extractors proposed by hevisan is sound in the presence of quantum side information.We exploit the modularity of this paradigm to give several concrete extractor construc- tions, which.e.g, extract all the conditional (smooth) min-entropy of the source using a seed of length poly-logarithmic in the input, or only require the seed to be weakly random.
We show that Trevisan's extractor and its variants \cite{T99,RRV99} are secure against bounded quantum storage adversaries. One instantiation gives the first such extractor to achieve an output length Θ(K−b)Θ(K-b)Θ(K−b), where KKK is the source's entropy and bbb the adversary's storage, together with a poly-logarithmic seed length. Another instantiation achieves a logarithmic key length, with a slightly smaller output length Θ((K−b)/Kγ)Θ((K-b)/K^γ)Θ((K−b)/Kγ) for any γ>0γ>0γ>0. In contrast, the previous best construction \cite{TS09} could only extract (K/b)1/15(K/b)^{1/15}(K/b)1/15 bits. Some of our constructions have the additional advantage that every bit of the output is a function of only a polylogarithmic number of bits from the source, which is crucial for some cryptographic applications. Our argument is based on bounds for a generalization of quantum random access codes, which we call \emph{quantum functional access codes}. This is crucial as it lets us avoid the local list-decoding algorithm central to the approach in \cite{TS09}, which was the source of the multiplicative overhead.
Randomness extractors, widely used in classical and quantum cryptography and other fields of computer science, e.g., derandomization, are functions which generate almost uniform randomness from weak sources of randomness. In the quantum setting one must take into account the quantum side information held by an adversary which might be used to break the security of the extractor. In the case of seeded extractors the presence of quantum side information has been extensively studied. For multi-source extractors one can easily see that high conditional min-entropy is not sufficient to guarantee security against arbitrary side information, even in the classical case. Hence, the interesting question is under which models of (both quantum and classical) side information multi-source extractors remain secure. In this work we suggest a natural model of side information, which we call the Markov model, and prove that any multi-source extractor remains secure in the presence of quantum side information of this type (albeit with weaker parameters). This improves on previous results in which more restricted models were considered and the security of only some types of extractors was shown.
Randomness extractors, widely used in classical and quantum cryptography and other fields of computer science, e.g., derandomization, are functions which generate almost uniform randomness from weak sources of randomness. In the quantum setting one must take into account the quantum side information held by an adversary which might be used to break the security of the extractor. In the case of seeded extractors the presence of quantum side information has been extensively studied. For multi-source extractors one can easily see that high conditional min-entropy is not sufficient to guarantee security against arbitrary side information, even in the classical case. Hence, the interesting question is under which models of (both quantum and classical) side information multi-source extractors remain secure. In this work we suggest a natural model of side information, which we call the Markov model, and prove that any multi-source extractor remains secure in the presence of quantum side information of this type (albeit with weaker parameters). This improves on previous results in which more restricted models were considered or the security of only some types of extractors was shown.