Maciej Obremski

Multi-source-extractors are functions that extract uniform randomness from multiple (weak) sources of randomness. With the advent of quantum computers, it is natural to investigate the security of multi-source-extractors against adversaries with quantum side-information on the sources of randomness (potentially generated using quantum entanglement). Quantum multi- source-extractors were considered by Kasher and Kempe (for the quantum-independent- adversary and the quantum-bounded-storage-adversary), Chung, Li, and Wu (for the general- entangled-adversary), and Arnon-Friedman, Portmann, and Scholz (for the quantum-Markov- adversary). In this work, we propose two new models of adversaries, the quantum-measurement-adversary (qm-adv) and the quantum-communication-adversary (qc-adv). qm-adv generates side-information post-measurement outcomes and qc-adv generates side-information using a communication protocol. We show that: 1. qm-adv is the strongest adversary among all the known adversaries, in the sense that the side-information of all other adversaries can be generated by qm-adv. 2. The (generalized) inner-product function (in fact a general class of two-wise independent functions) continue to work as a good extractor against qm-adv (with matching parameters as that of Chor and Goldreich against classical-adversaries). 3. A non-malleable extractor proposed by Li (against classical-adversaries) continues to be secure against quantum side-information. A non-malleable extractor (nm-ext) for two sources (X, Y) is an extractor such that nm-ext(X, Y) is uniform and independent of nm-ext(X, Y')YY', where Y' is not equal to Y and Y' is generated by the adversary using Y and the side-information on X. 4. A modification (not needing any local uniform randomness) of the Dodis and Wich's protocol for privacy-amplification is secure against active quantum adversaries. This strengthens on a recent result due to Aggarwal, Chung, Lin, and Vidick which uses local uniform randomness. 5. As a byproduct, we reproduce the quantum communication complexity lower bound for the (generalized) inner-product function via different proof techniques.