| The thesis integrates several results that bring together analysis of algorithms and cryptography. The first chapter covers two results about domain extenders for hash functions. It introduces is a continuum of function classes bridging universal one-way hash functions and collision-resistant hash functions. From the complexity-theoretic point of view, the continuum is divided into two classes of equivalence, only one of which admits the Merkle-Damgaard construction for domain extension. Secondly, we prove a lower bound via a combinatorial argument on the key length of the Shoup construction (applicable to the other class) in some natural model.; The next chapter analyzes a popular stream cipher, modeling it as a random walk on the symmetric group. The internal state of RC4 is a secret permutation that is shuffled during the key initialization step and by the pseudo-random number generator during the execution of the cipher. We observe that the mixing rate of the shuffling is important for security of the cipher. In particular, since the first byte of RC4 is output before the internal state is fully mixed, there is a detectable bias in the first byte. We bound the mixing rate of the shuffle and some experimental evidence that corroborates the conjecture that the upper bound is asymptotically tight.; The last chapter of the thesis presents an average-case analysis of an important scheme for broadcast encryption for stateless receivers with user revocation. Additionally, we present an algorithm for computing optimal parameters of the extension of that scheme. |
