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 in computer science

Two-Source Extractors Secure against Quantum Adversaries

Roy Kasher, Julia Kempe

Published Jan 1, 2010• 11 citations
Publisher
DOI
10.1007/978-3-642-15369-3_49

Related papers

A Quantum-Proof Non-malleable Extractor: With Application to Privacy Amplification Against Active Quantum Adversaries

Divesh Aggarwal, Kai-Min Chung, Han-Hsuan Lin +1 more

Lecture notes in computer science•Jan 1, 2019•4 citations

Encryption against Storage-Bounded Adversaries from On-Line Strong Extractors

Chi-Jen Lu

Journal of Cryptology•Aug 6, 2003•71 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•6 citations

Secure Quantum Extraction Protocols

Prabhanjan Ananth, Rolando L. La Placa

arXiv:1911.07672•Lecture notes in computer science•Jan 1, 2020•16 citations

Security Analysis of Quantum Obfuscation

Tao Shang, Jianwei Liu

Springer eBooks•Jan 1, 2020•0 citations

Quantum Measurement Adversary

Divesh Aggarwal, Naresh Goud Boddu, Rahul Jain +1 more

Multi-source extractors are functions that extract uniform randomness from multiple (weak) sources of randomness. Quantum multi-source extractors were considered by Kasher and Kempe (2010) (for the quantum independent adversary and the quantum bounded storage adversary), Chung et al. (2014) (for the general entangled adversary) and Arnon-Friedman et al. (2016) (for the quantum Markov adversary). One of the main objectives of this work is to unify all the existing quantum multi-source adversary models. We propose two new models of adversaries: 1) the quantum measurement adversary ($\mathsf {qma}$), which generates side information using entanglement and on post-measurement; and 2) the quantum communication adversary ($\mathsf {qca}$), which generates side information using entanglement and communication between multiple sources. We show that: 1)$\mathsf {qma}$is the strongest adversary among all the known adversaries, in the sense that the side information of all other adversaries can be generated by$\mathsf {qma}$; 2) The (generalized) inner-product function (in fact a general class of two-wise independent functions) continues to work as a good extractor with matching parameters as that of Chor and Goldreich (1985) against classical adversaries; 3) A non-malleable extractor proposed by Li (2012) (against classical adversaries) continues to be secure against quantum side information. This result implies a non-malleable extractor result of Aggarwal et al. (2019) with uniform seed. We strengthen their result via a completely different proof to make the non-malleable extractor of Li secure against quantum side information even when the seed is not uniform; 4) A modification (working with weak local randomness instead of uniform local randomness) of the Dodis and Wichs (2009) protocol for privacy-amplification is secure against active quantum adversaries (those who arbitrarily modify the messages exchanged in the protocol). This strengthens on a recent result due to Aggarwal et al. (2019) which uses uniform local randomness; 5) A tight efficiency lower bound for the (generalized) inner-product function (in fact a general class of two-wise independent functions).

arXiv:2106.02766•IEEE Transactions on Information Theory•Sep 8, 2023•7 citations
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.
Multi-source extractors are functions that extract uniform randomness from multiple (weak) sources of randomness. Quantum multi-source extractors were considered by Kasher and Kempe (2010) (for the quantum independent adversary and the quantum bounded storage adversary), Chung et al. (2014) (for the general entangled adversary) and Arnon-Friedman et al. (2016) (for the quantum Markov adversary). One of the main objectives of this work is to unify all the existing quantum multi-source adversary models. We propose two new models of adversaries: 1) the quantum measurement adversary (qma\mathsf {qma}qma), which generates side information using entanglement and on post-measurement; and 2) the quantum communication adversary (qca\mathsf {qca}qca), which generates side information using entanglement and communication between multiple sources. We show that: 1)qma\mathsf {qma}qmais the strongest adversary among all the known adversaries, in the sense that the side information of all other adversaries can be generated byqma\mathsf {qma}qma; 2) The (generalized) inner-product function (in fact a general class of two-wise independent functions) continues to work as a good extractor with matching parameters as that of Chor and Goldreich (1985) against classical adversaries; 3) A non-malleable extractor proposed by Li (2012) (against classical adversaries) continues to be secure against quantum side information. This result implies a non-malleable extractor result of Aggarwal et al. (2019) with uniform seed. We strengthen their result via a completely different proof to make the non-malleable extractor of Li secure against quantum side information even when the seed is not uniform; 4) A modification (working with weak local randomness instead of uniform local randomness) of the Dodis and Wichs (2009) protocol for privacy-amplification is secure against active quantum adversaries (those who arbitrarily modify the messages exchanged in the protocol). This strengthens on a recent result due to Aggarwal et al. (2019) which uses uniform local randomness; 5) A tight efficiency lower bound for the (generalized) inner-product function (in fact a general class of two-wise independent functions).