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

Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE

Device-independent randomness extraction for arbitrarily weak min-entropy source

Jan Bouda, Marcin Pawłowski, Matej Pivoluska, Martin Plesch

Published Oct 13, 2014• 6 citations
Publisher

Abstract

In this paper we design a protocol to extract random bits with an arbitrarily low bias from a single arbitrarily weak min-entropy block source in a device independent setting. The protocol employs Mermin devices that exhibit super-classical correlations. Number of devices used scales polynomially in the length of the block n, containing entropy of at least two bits. Our protocol is robust, it can tolerate devices that malfunction with a probability dropping polynomially in n at the cost of constant increase of the number of devices used.

DOI
10.1117/12.2071568

Related papers

Device-independent Randomness Extraction for Arbitrarily Weak Min-entropy Source

Jan Bouda, Marcin Pawłowski, Matej Pivoluska +1 more

In this paper we design a protocol to extract random bits with an arbitrarily low bias from a single arbitrarily weak min-entropy block source in a device independent setting. The protocol employs Mermin devices that exhibit super-classical correlations. Number of devices used scales polynomially in the length of the block n, containing entropy of at least two bits. Our protocol is robust, it can tolerate devices that malfunction with a probability dropping polynomially in n at the cost of constant increase of the number of devices used.

Leibniz international proceedings in informatics•Jan 1, 2014•0 citations

Device-independent randomness extraction from an arbitrarily weak min-entropy source

Jan Bouda, Marcin Pawłowski, Matej Pivoluska +1 more

Expansion and amplification of weak randomness play a crucial role in many security protocols. Using quantum devices, such procedure is possible even without trusting the devices used, by utilizing correlations between outcomes of parts of the devices. We show here how to extract random bits with an arbitrarily low bias from single arbitrarily weak min-entropy block source in a device independent setting. To do this we use Mermin devices that exhibit superclassical correlations. The number of devices used scales polynomially in the length of the random sequence $n$. Our protocol is robust; it can tolerate devices that malfunction with probability decreasing polynomially in $n$ at the cost of minor increase in the number of devices used.

arXiv:1402.0974•Physical Review A•Sep 12, 2014•26 citations

Finite Device-Independent Extraction of a Block Min-Entropy Source against Quantum Adversaries

Ravishankar Ramanathan

The extraction of randomness from weakly random seeds is a problem of central importance with multiple applications. In the device-independent setting, this problem of quantum randomness amplification has been mainly restricted to specific weak sources of Santha-Vazirani type, while extraction from the general min-entropy sources has required a large number of separated devices which is impractical. In this paper, we present a device-independent protocol for amplification of a single min-entropy source (consisting of two blocks of sufficiently high min-entropy) using a device consisting of two spatially separated components and show a proof of its security against general quantum adversaries.

arXiv:2304.09643•Apr 19, 2023•0 citations

Network Extractor Protocols

Yael Tauman Kalai, Xin Li, Anup Rao +1 more

We design efficient protocols for processors to extract private randomness over a network with Byzantine faults, when each processor has access to an independent weakly-random n-bit source of sufficient min-entropy.We give several such network extractor protocols in both the information theoretic and computational settings.For a computationally unbounded adversary, we construct protocols in both the synchronous and asynchronous settings.These network extractors imply efficient protocols for leader election (synchronous setting only) and Byzantine agreement which tolerate a linear fraction of faults,even when the min-entropy is only 2(logn)Omega(1).For larger min-entropy,in the synchronous setting the fraction of tolerable faults approaches the bounds in the perfect-randomness case.Our network extractors for a computationally bounded adversary work in the synchronous setting even when 99% of the parties are faulty, assuming trapdoor permutations exist. Further, assuming a strong variant of the Decisional Diffie-Hellman Assumption, we construct a network extractor in which all parties receive private randomness. This yields an efficient protocol for secure multi-party computation with imperfect randomness, when the number of parties is at least polylog (n) and where the parties only have access to an independent source with min-entropy nOmega(1).

Annual Symposium on Foundations of Computer Science•Oct 1, 2008•34 citations

2-Source Extractors under Computational Assumptions and Cryptography with Defective Randomness

Yael Tauman Kalai, Xin Li, Anup Rao

We show how to efficiently extract truly random bits from two independent sources of linear min-entropy, under a computational assumption. The assumption we rely on is the existence of an efficiently computable permutation f1, such that for any source X ¿ {0, 1}nwith linear min-entropy, any circuit of size poly(n) cannot invert f(X) with non-negligible probability. Under the stronger assumption that f(X) cannot be inverted even by circuits of size poly(nlog n) with nonnegligible probability, we design a lossless computational network extractor protocol. Namely, we design a protocol for a set of players, each with access to an independent source of linear min-entropy, with the guarantee that at the end of the protocol, each honest player is left with bits that are computationally indistinguishable from being uniform and private. Our protocol succeeds as long as there are at least two honest players. Our results imply that if such one-way permutations exist, and enhanced trapdoor permutations exist, then secure multiparty computation with imperfect randomness is possible for any number of players, as long as at least two of them are honest. We also construct a network extractor protocol for the case where each source has only polynomially-small min-entropy (n¿for some constant ¿ > 0). For this we need at least a constant u(¿) (which depends on ¿) number of honest players, and we need that the one-way permutation is hard to invert even on polynomially small min-entropy sources.

Annual Symposium on Foundations of Computer Science•Oct 1, 2009•38 citations

An Explicit Non-Malleable Extraction Scheme for Quantum Randomness Amplification With Two Untrusted Devices

Mingfeng Xu, Wei Pan, Lianshan Yan +4 more

Quantum random number is a particularly important physical resource both for quantum communication and quantum cryptography. Quantum randomness amplification, as a key technology in quantum random number generation, has a significant counterintuitive effect: one can amplify weak randomness to almost perfect randomness by quantum systems, which is impossible in classical cryptography. In this letter, we propose an explicit quantum randomness amplification scheme with two untrusted devices, from which we could extract one single perfect random bit from weak random bits. An explicit non-malleable two-source extractor is introduced to extract perfect randomness from two independent min-entropy sources, which are derived from a Bell test with two untrusted devices. The universally composable security of the proposed protocol is proved.

IEEE Communications Letters•Oct 30, 2017•2 citations
In this paper we design a protocol to extract random bits with an arbitrarily low bias from a single arbitrarily weak min-entropy block source in a device independent setting. The protocol employs Mermin devices that exhibit super-classical correlations. Number of devices used scales polynomially in the length of the block n, containing entropy of at least two bits. Our protocol is robust, it can tolerate devices that malfunction with a probability dropping polynomially in n at the cost of constant increase of the number of devices used.
In this paper we design a protocol to extract random bits with an arbitrarily low bias from a single arbitrarily weak min-entropy block source in a device independent setting. The protocol employs Mermin devices that exhibit super-classical correlations. Number of devices used scales polynomially in the length of the block n, containing entropy of at least two bits. Our protocol is robust, it can tolerate devices that malfunction with a probability dropping polynomially in n at the cost of constant increase of the number of devices used.
Expansion and amplification of weak randomness play a crucial role in many security protocols. Using quantum devices, such procedure is possible even without trusting the devices used, by utilizing correlations between outcomes of parts of the devices. We show here how to extract random bits with an arbitrarily low bias from single arbitrarily weak min-entropy block source in a device independent setting. To do this we use Mermin devices that exhibit superclassical correlations. The number of devices used scales polynomially in the length of the random sequence nnn. Our protocol is robust; it can tolerate devices that malfunction with probability decreasing polynomially in nnn at the cost of minor increase in the number of devices used.
The extraction of randomness from weakly random seeds is a problem of central importance with multiple applications. In the device-independent setting, this problem of quantum randomness amplification has been mainly restricted to specific weak sources of Santha-Vazirani type, while extraction from the general min-entropy sources has required a large number of separated devices which is impractical. In this paper, we present a device-independent protocol for amplification of a single min-entropy source (consisting of two blocks of sufficiently high min-entropy) using a device consisting of two spatially separated components and show a proof of its security against general quantum adversaries.
We design efficient protocols for processors to extract private randomness over a network with Byzantine faults, when each processor has access to an independent weakly-random n-bit source of sufficient min-entropy.We give several such network extractor protocols in both the information theoretic and computational settings.For a computationally unbounded adversary, we construct protocols in both the synchronous and asynchronous settings.These network extractors imply efficient protocols for leader election (synchronous setting only) and Byzantine agreement which tolerate a linear fraction of faults,even when the min-entropy is only 2(logn)Omega(1).For larger min-entropy,in the synchronous setting the fraction of tolerable faults approaches the bounds in the perfect-randomness case.Our network extractors for a computationally bounded adversary work in the synchronous setting even when 99% of the parties are faulty, assuming trapdoor permutations exist. Further, assuming a strong variant of the Decisional Diffie-Hellman Assumption, we construct a network extractor in which all parties receive private randomness. This yields an efficient protocol for secure multi-party computation with imperfect randomness, when the number of parties is at least polylog (n) and where the parties only have access to an independent source with min-entropy nOmega(1).
We show how to efficiently extract truly random bits from two independent sources of linear min-entropy, under a computational assumption. The assumption we rely on is the existence of an efficiently computable permutation f1, such that for any source X ¿ {0, 1}nwith linear min-entropy, any circuit of size poly(n) cannot invert f(X) with non-negligible probability. Under the stronger assumption that f(X) cannot be inverted even by circuits of size poly(nlog n) with nonnegligible probability, we design a lossless computational network extractor protocol. Namely, we design a protocol for a set of players, each with access to an independent source of linear min-entropy, with the guarantee that at the end of the protocol, each honest player is left with bits that are computationally indistinguishable from being uniform and private. Our protocol succeeds as long as there are at least two honest players. Our results imply that if such one-way permutations exist, and enhanced trapdoor permutations exist, then secure multiparty computation with imperfect randomness is possible for any number of players, as long as at least two of them are honest. We also construct a network extractor protocol for the case where each source has only polynomially-small min-entropy (n¿for some constant ¿ > 0). For this we need at least a constant u(¿) (which depends on ¿) number of honest players, and we need that the one-way permutation is hard to invert even on polynomially small min-entropy sources.
Quantum random number is a particularly important physical resource both for quantum communication and quantum cryptography. Quantum randomness amplification, as a key technology in quantum random number generation, has a significant counterintuitive effect: one can amplify weak randomness to almost perfect randomness by quantum systems, which is impossible in classical cryptography. In this letter, we propose an explicit quantum randomness amplification scheme with two untrusted devices, from which we could extract one single perfect random bit from weak random bits. An explicit non-malleable two-source extractor is introduced to extract perfect randomness from two independent min-entropy sources, which are derived from a Bell test with two untrusted devices. The universally composable security of the proposed protocol is proved.