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 [1] (for the quantum independent adversary and the quantum bounded storage adversary ), Chung, Li and Wu [2] (for the general entangled adversary ) and Arnon-Friedman, Portmann and Scholz [3] (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), which generates side information using entanglement and on post-measurement and 2) the quantum communication adversary (qca), which generates side information using entanglement and communication between multiple sources. We show that, 1) 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 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 [4] against classical adversaries. 3) A non-malleable extractor proposed by Li [5] (against classical adversaries) continues to be secure against quantum side information. This result implies a non-malleable extractor result of Aggarwal, Chung, Lin and Vidick [6] 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 [7] 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, Chung, Lin and Vidick [6] 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).
Non-malleable codes are a natural relaxation of error correction and error detection codes applicable in scenarios where error-correction or error-detection is impossible. Over the last decade, non-malleable codes have been studied for a wide variety of tampering families. Among the most well studied of these is the split-state family of tampering channels, where the codeword is split into two or more parts and each part is tampered with independently. We survey various constructions and applications of non-malleable codes in the split-state model.
26 July 2022 in IEEE Transactions on Information Theory
We show that the most common flavors of noisy leakage can be simulated in the information-theoretic setting using a single query of bounded leakage, up to a small statistical simulation error and a slight loss in the leakage parameter. The latter holds true in particular for one of the most used noisy-leakage models, where the noisiness is measured using the conditional average min-entropy (Naor and Segev, CRYPTO’09 and SICOMP’12). Our reductions between noisy and bounded leakage are achieved in two steps. First, we put forward a new leakage model (dubbed the dense leakage model) and prove that dense leakage can be simulated in the information-theoretic setting using a single query of bounded leakage, up to small statistical distance. Second, we show that the most common noisy-leakage models fall within the class of dense leakage, with good parameters. Third, we prove lower bounds on the amount of bounded leakage required for simulation with sub-constant error, showing that our reductions are nearly optimal. In particular, our results imply that useful general simulation of noisy leakage based on statistical distance and mutual information is impossible. We also provide a complete picture of the relationships between different noisy-leakage models. Our result finds applications to leakage-resilient cryptography, where we are often able to lift security in the presence of bounded leakage to security in the presence of noisy leakage, both in the information-theoretic and in the computational setting. Remarkably, this lifting procedure makes only black-box use of the underlying schemes. Additionally, we show how to use lower bounds in communication complexity to prove that bounded-collusion protocols (Kumar, Meka, and Sahai, FOCS’19) for certain functions do not only require long transcripts, but also necessarily need to reveal enough information about the inputs.