A Constructive Treatment of Enhanced Encryption Schemes

Abstract

Encryption is a tool that has traditionally been used to allow confidential communication between two parties. Over the years, several types of encryption have been proposed, including public-key encryption, identity-based encryption, deniable encryption, and functional encryption. These variants provide different features and security guarantees. Their security is typically defined by a game between an adversary and a challenger. Even for ordinary public-key encryption, several different security definitions have been proposed and identifying the right one is a nontrivial task. For more complex primitives such as functional encryption, security definitions are far more involved and it is way more difficult to evaluate whether a given definition is appropriate. The goal of this thesis is to better understand these definitions for several types of encryption by analyzing them in the constructive cryptography framework. In this framework, a cryptographic primitive can be seen as providing a construction of a so-called ideal resource from a so-called real resource, for a well-defined notion of construction. The real resource formalizes what is available to the involved parties, e.g., a shared secret key and an authenticated communication channel, and the ideal resource formalizes what should be achieved by applying the encryption scheme, e.g., a secure channel that does not leak the sent messages to eavesdroppers. This paradigm makes the requirements and the achieved guarantees explicit and helps to decide whether a given scheme is suitable for a certain application. The first and simplest encryption scheme we consider in this thesis is the one-time pad. We show that it provides a guarantee that deniable encryption targets, namely it remains secure if the receiver reveals the secret key to the adversary after receiving the message. We model this in constructive cryptography by allowing the receiver to become dishonest after receiving the message. We next consider identity-based encryption (IBE). In contrast to deniable encryption, it does not provide stronger security guarantees, but rather simplifies the key distribution. We formalize the standard application of IBE, namely non-interactive secure communication, as constructing an ideal resource that allows parties to be registered for an identity, and to securely sent messages to other parties only known by their identity. Quite surprisingly, we show that it is impossible to construct this resource in the standard model. We show, however, how to adjust any IBE scheme that satisfies the standard security definition to achieve this goal in the random oracle model. We also show that the impossibility result can be avoided in the standard model by considering a weaker ideal resource. Functional encryption is a very general concept, which encompasses public-key encryption and identity-based encryption as special cases. It allows the generation of restricted secret keys that enable to learn only a specific function of the encrypted data. We formalize the security of functional encryption as constructing an ideal resource that corresponds to a repository with fine-grained access control, and compare this to existing security notions. Again, we show that constructing the most desirable ideal resource is impossible without random oracles, possible in the random oracle model, and that constructing weaker ideal resources is possible in the standard model. Finally, we consider access control encryption (ACE). While the encryption schemes discussed above allow to control which users can read the encrypted data, ACE additionally allows to restrict write access. As we argue, however, existing security notions are insufficient to provide meaningful security guarantees in realistic settings. We therefore propose new, substantially stronger security definitions and an ACE scheme that provably satisfies them under standard assumptions.