Public-key encryption secure in the presence of randomness failures

Public-key encryption (PKE) is a central tool for protecting the privacy of digital information. To achieve desirable strong notions of security like indistinguishability under chosen-plaintext attack (IND- CPA), it is essential for an encryption algorithm to have access to a source of fresh, uniform random bits. Further, these bits should never be revealed and never reused. In practice, our machines typically generate these random bits with software random number generators (RNGs). Unfortunately, RNGs are prone to problems. The resulting randomness failures can have disastrous consequences for the security of existing PKE schemes that rely on good randomness. In this dissertation we focus PKE security in the presence of three types of randomness failures: predictable randomness, repeated randomness, and revealed randomness. For predictable randomness, where the encryption algorithm is given random inputs that are predictable to an adversary, we argue that we want PKE schemes that are hedged against bad randomness: if the encryption scheme is given good randomness it provably meets traditional notions like IND-CPA, while if it is given poor randomness, it still provably provides some security. We formalize this security notion and give provably-secure constructions of hedged public-key encryption. Next, we show how repeated randomness failures, where the encryption algorithm is given random inputs that it was given previously, can occur in practice due to virtual machine snapshots. In particular, we show how many popular web browsers are vulnerable to these failures. We then turn to building PKE schemes that still provide provable security when given repeated randomness. We develop new models of security to capture this situation and prove that a simple and efficient modification to any existing secure scheme gives security under our new models. Finally, we study the strange effects revealed randomness failures, where the random inputs used for encryption are later revealed to an adversary, can have on public-key encryption security. Specifically, we focus on selective opening attacks. We show that a large class of PKE schemes, called lossy encryption schemes, provably resists selective opening attack