Computational Notions of Entropy: Classical, Quantum, and Applications

Abstract

Entropy notions from information theory have many applications in cryptographic analyses and constructions, where it is most common to consider adversaries with only (polynomially) bounded computational power. Therefore, some computational relaxations of entropy, which capture some properties of entropy from the view of computationally bounded parties are also useful in cryptography and computational complexity. In this thesis, we study computational notions of entropy from several different angles. First, in many constructions of basic cryptographic primitives, computational entropies serve as key ingredients. For instance, "next-block pseudoentropy" and "next-block accessible entropy" are used in the best known constructions of pseudorandom generators and statistically hiding commitments from one-way functions, respectively. We contribute along these lines in two aspects: - We introduce a new notion of hardness for one-way functions called KL-hardness, which implies both next-block pseudoentropy and inaccessible entropy, and formalizes the duality between them. By the new notion, we also obtain a more modular and illuminating proof that one-way functions imply next-block inaccessible entropy, similar in structure to the proof that one-way functions imply next-block pseudoentropy (Vadhan and Zheng, STOC 2012). - One common step in the constructions of basic primitives (including pseudorandom generators, statistically hiding commitments, and universal one-way hash functions) from one-way functions is entropy flattening, which converts an average-case entropy (e.g., Shannon) to a worst-case entropy (e.g., min-entropy). We show that any flattening algorithm has to make Omega(n^2) queries to the function serving as the entropy sources (analogues to the one-way functions in the constructions of cryptographic primitives) where n is the input length of the functions. The result can be viewed as a step towards proving that the current best construction of pseudorandom generators from arbitrary one-way functions (Vadhan and Zheng, STOC 2012) has optimal efficiency. Then we study the complexity of the problem "simulating auxiliary input": given a joint distribution (X, Z) on X x {0, 1}^l and a class of distinguishers F : X x {0, 1}^l -> {0, 1}, construct an "efficient" simulator h : X -> {0, 1}^l such that (X, Z) and (X, h(X)) are indistinguishable by any distinguisher f in F up to advantage eps. The efficiency of h is measured by circuit size of relative to F, the optimal complexity was known to be poly(1/eps,2^l). The existence of such a simulator implies many theorems connected to computational entropies such as the Dense Model Theorem, Impagliazzo's Hardcore Lemma, and the Leakage Chain Rule for "relaxed-HILL pseudoentropy". We improve the existing results from both directions showing a tight complexity bound Theta(2^l/eps^2) for h, which in particular improves the security analysis of some stream-cipher protocols in leakage-resilient cryptography. Finally, we initiate the study of computational entropies in the quantum setting by proposing several quantum computational notions of entropy that generalize classical notions, studying which classical properties of computational entropies extend to the quantum case and which does not, and illustrating the application of quantum computational entropy in post-quantum cryptography. Specifically, we develop the Quantum Nonuniform Min-max Theorem to prove some properties of quantum computational entropies such as the equivalence between quantum HILL entropy and metric entropy. Notably, we also solve the problem of simulating auxiliary quantum input, which we further use for proving the security of Dziembowski and Pietrzak's (FOCS 2008) leakage-resilient stream-cipher against quantum adversaries with quantum leakage in the bounded-quantum-storage model.