Quantum Measurement Adversary
Divesh Aggarwal, Naresh Goud Boddu, Rahul Jain, Maciej Obremski · IEEE Transactions on Information Theory · 2023
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).