Computing securely with untrusted resources
Fabian Monrose, Seny Kamara · 2008
When designing and analyzing cryptosystems, it is usually assumed that the computational devices used by the honest parties have access to resources that are outside of the malicious parties' control. In such a model, it is known, under standard cryptographic assumptions, that essentially any operation can be performed securely as long as a majority of the parties are honest. In many practical settings, however, the assumption that computational resources can be protected from an adversary does not hold. This dissertation explores various security problems in settings where honest parties wish to make use of computational resources that are under adversarial control. We focus on resources that are fundamental to cryptography, such as randomness and storage. We first consider the problem of encrypting with a malicious random number generator. We introduce the notions of security against chosen-randomness attacks (CRA) and security against chosen-ciphertext and randomness attacks (CCRA), which formally capture the security of private-key encryption when used with sources of randomness that are under adversarial control. We study the relationships between these notions and the traditional notions of security for encryption. We also show how to design efficient schemes that are CRA-secure, and how to transform any CPA-secure scheme into a CRA-secure one, and any CRA-secure scheme into a CCRA-secure one. We then turn to the task of authenticating data stored in unreliable memory. We propose a general framework for designing efficient proofs of data possession, which are proof systems that enable one to convince a verifier that it stores a particular piece of data. We give a compiler that transforms any sigma-protocol (i.e., a three-round public-coin zero-knowledge proof of knowledge) into a proof of data possession. Finally, we consider the problem of storing private data in untrusted memory. We show how to design private-key encryption schemes that allow one to search over encrypted content. Our constructions are optimal in terms of search time. We also introduce searchable encryption in the multi-user setting, where search privileges can be delegated to a set of authorized users.