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) iacr.org.
Chun-Yuan Hsiao (#663)
Topic of his/her doctorate.
Butterfly Effect in Cryptography: Consequences of Changes in Definitions
hash functions, pseudo-randomness
Year of completion
Modern cryptography places a great deal of emphasis on denitions, because a precise
denition formalizes our intuition about a cryptographic primitive.
This dissertation consists of two parts. The first part demonstrates the importance of
denitional precision by examining a previously overlooked subtlety in dening 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 identies a precise and broad set of such conditions.
The second part of this dissertation investigates two known denitions of entropy. Shannon has shown the equivalence of these two denitions 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 dier 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.
cyhsiao (at) cs.bu.edu