| Modern cryptography places a great deal of emphasis on definitions, because a precise definition formalizes our intuition about a cryptographic primitive.This dissertation consists of two parts. The first part demonstrates the importance of definitional precision by examining a previously overlooked subtlety in defining a widely-used primitive: the Collision Resistant Hash Function, or CRHF. The subtlety lies in the method by which the CRHF key is generated: namely, whether a trusted party needs to perform key generation (the "secret-coin" variant), or whether any public random string can be used as the key (the "public-coin" variant). Adding a new technique to the so-called "black-box separation" methodology, this thesis shows that these two variants of CRHF, which were sometimes used interchangeably, are actually distinct in general. However, they are also equivalent under certain conditions the thesis identifies a precise and broad set of such conditions.The second part of this dissertation investigates two known definitions of entropy. Shannon has shown the equivalence of these two definitions by proving that the shortest compression length of a distribution is equivalent to the amount of randomness it contains. Cryptographers are often interested in distributions that appear random to computationally-bounded observers (for example, ciphertexts often have this property). In an attempt to quantify the amount of this computational randomness, analogues of Shannon's notions of compressibility and entropy have been proposed for the computationally-bounded setting. Whether these two notions remain equivalent is an interesting open question, with potential applications to pseudorandom generation and cryptographic primitives that rely on it. This thesis shows that they can differ vastly in a common cryptographic setting. One interesting corollary of our work is that we can extract more pseudorandom bits from a distribution if we choose the less commonly used notion of compressibility. In addition to presenting this result, the thesis studies how to better extract pseudorandomness from distributions that are computationally hard to compress. |
