International Association for Cryptologic Research

Ph.D. Database

The aim of the IACR Ph.D. database is twofold. On the first hand, we want to offer an overview of Ph.D. already completed in the domain of cryptology. Where possible, this should also include a subject classification, an abstract, and access to the full text. On the second hand, it deals with Ph.D. subjects currently under investigation. This way, we provide a timely map of contemporary research in cryptology. All entries or changes need to be approved by an editor. You can contact them via phds (at)


Chun-Yuan Hsiao (#663)
Name Chun-Yuan Hsiao
Personal Homepage
Institution Boston University
Topic of his/her doctorate. Butterfly Effect in Cryptography: Consequences of Changes in Definitions
Category foundations
Keywords hash functions, pseudo-randomness
Ph.D. Supervisor(s) Leonid Reyzin
Year of completion 2010
Abstract Modern cryptography places a great deal of emphasis on de nitions, because a precise de nition formalizes our intuition about a cryptographic primitive.

This dissertation consists of two parts. The first part demonstrates the importance of de nitional precision by examining a previously overlooked subtlety in de ning a widelyused 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 identi es a precise and broad set of such conditions.

The second part of this dissertation investigates two known de nitions of entropy. Shannon has shown the equivalence of these two de nitions 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 boundedvobservers (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 di er 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.

E-Mail Address cyhsiao (at)
Last Change 2011-08-23 11:25:12
To provide an update on this entry, please click .

Contact: phds (at)

[ IACR home page ] [ IACR PhDs page ] © IACR