Recurring themes in my work include: (1) bringing provable security to bear on practical problems like entity authentication and session key distribution; (2) using finite pseudorandom functions (or finite pseudorandom permutations) as a way to bring provable-security to constructions based on confusion/diffusion (ie., DES-like) primitives; (3) paying close attention to exact security analysis, not only to understand how good an analysis is, but also to provide guidance in choosing among practical protocols, to lead to better protocols, and even to lead to better or sharper notions; and (4) using the random oracle paradigm when obtaining provable security in the standard model would involve a loss of efficiency or simplicity so great as to render the methods undesirable in the real world. I'm one of the few people who actually enjoys working on (5) definitions, and I believe that good definitions, all by themselves, can be of lasting value.
Amongst the topics on which I work (with links going to the corresponding paragraphs on this page):
Building on sensibilities, paradigms, and techniques that have arisen from the provable security tradition, I have worked to fashion a line of research that is simultaneously useful and foundationally strong. In large part, this line of research was developed in collaboration with Mihir Bellare. We have built on our experiences from MIT and IBM.
Practice-oriented provable security has been picking up steam. Over the last couple of years we've seen a lot of work by others following this line. Our [OEAP95] technique has been adopted for financial transactions on the Internet (in SET) and the emerging IEEE standard for public key cryptography (P1363). The contributions of provable security are, at last, finally starting to have a real impact on practice.
I now describe in a bit more detail the individual areas in which I have been working.
Entity authentication and session key distribution. The problem is how two parties can authenticate each other across the network and/or obtain a joint session key. The adversarial model envisages an active adversary who can, among other things, start multiple sessions of different entities. Many protocols for these problems have been proposed, but lots of them have turned out to be wrong. For the most part, the entire field has been rather ad. hoc. and unscientific. In a new approach to this subject, we bring provable security to entity authentication and associated problems of key distribution. In [EA93] we cover the two party symmetric case, where the parties hold a long-lived shared key either (1) want to authenticate one another, or (2) authenticate one another and simultaneously derive a shared session key. Then in [3PKD] we treat three party key distribution (the Needham-Schroeder, or Kerberos, setting), where each party shares a long-lived key with a trusted server, and they want to derive a shared session key. We provide a model, definitions, and protocols which are proved secure under standard assumptions. In addition to being proven secure, our protocols are as practical as currently implemented ones. Our approach brings under the umbrella of provable security a large area of research in which protocols either were given no justification for correctness whatsoever, or were justified in a rather weak sense, by first passing to a non-cryptographic abstraction about the underlying cryptography (e.g., the "logical approach"). We are currently extending our work for the asymmetric setting.
Message authentication. Message authentication lets communicating partners who share a secret key verify that a received message originates with the party who claims to have sent it. The sender computes, as a function of the message and the shared key, a "tag" (or "MAC", for "message authentication code") which he attaches to the message. The receiver can check the validity of the tag. In [CBCmac94] we provide the first analysis for the most widespread technique for message authentication, the so-called CBC MAC. This method is a US and International Standard, but it never received any sort of provable-security treatment. Roughly, we show that if the underlying block cipher is secure then so is the CBC MAC of that block cipher. Actually we do more: we present a quantitative analysis under which the security of the CBC MAC can be measured as a function of the strength of the underlying block cipher. This introduces a new approach to the analysis of block-cipher based constructions, based on modeling them as finite pseudorandom functions. It provides the foundation to bring into the realm of provable security constructions which prior to this were treated as heuristic. In [XORmac95] we introduced a new approach to MACing with a block ciphers. Unlike the CBC MAC, an XOR MAC is fully parallelizable, so that it is suitable for data authentication over high speed networks. Again, the security is analyzed assuming the block cipher is a finite pseudo-random function. But now the security bounds indicate that the construction is far better than the CBC MAC. In [Bucket95] I introduced bucket hashing, a fast-to-compute family of universal hash functions. The paper also advocates Wegman-Carter MACs for the next-generation of software-optimized MACs. In all three of the above papers, a crucial feature is the consideration of "exact" or "concrete" security." The resources of an adversary (its running time and the number of chosen message queries it can make) are quantified, and security is measured by an explicitly-given function of these resources. This concretization is essential for the practical applications of the provable security approach.
Asymmetric Encryption. Mathematical techniques such as the RSA primitive (f(x) = x^e mod N) are not used (and should not be used) to directly encrypt a string. (If you really tried to encrypt that way, information about the plaintext would be revealed.) Instead, asymmetric encryption is accomplished by an (often ignored) protocol which sits on top of a mathematical primitive such as RSA. For example, RSA-based encryption is often done using Public Key Cryptography Standard #1, which specifies how to format messages prior to applying the RSA primitive. In [OEAP95] we provide a different formatting approach, a solution that has subsequently been referred to as "OAEP" (Optimal Asymmetric Encryption Padding). It is just as efficient as methods like PKCS #1, but, in contrast, it is proven secure (in the random oracle model, to be discussed below). In fact, OAEP is not only proven to achieves semantic security (the customary requirement), but it goes further, achieving what we call plaintext awareness, a notion even stronger than non-malleability and chosen-ciphertext security. Our technique has been incorporated into the electronic payment protocol to be used for credit card transactions on the Internet, SET. And the method is in the emerging IEEE standard for public key cryptography, P1363. Some follow up work we did on OAEP is reported in [MinRo97].
Digital Signatures. Just as you should not encrypt a message by directly applying the RSA encryption primitive, so too you should not digitally sign a message by directly subjecting the message to a mathematical function such as the inverse RSA map, f(y) = y^d mod N. (If you really tried to sign that way, it would be possible to forge electronic signatures.) In [Sign96] we show a good way to sign using a primitive such as RSA. What sets apart our method is that it is proven to be secure in a very satisfying way. As usual, a reduction is demonstrated which shows that a way to break the higher-level protocol (the signature scheme) implies a way to break the lower-level primitive (the RSA primitive, say). But the reduction is tight: if you can break the signature scheme with a certain amount of computational resources, than you can compute break the RSA function, with essentially the identical computational resources. This seems to us the new "holly grail" for practical, scientific cryptography: to give provable-security results for practical protocols using completely tight reductions. However, note that the result is, once again, in the a random-oracle model.
Random Oracles. Many cryptographic goals have been solved in the provable-security tradition, but the demonstrated protocols are too inefficient to be competitive with what ad. hoc. techniques already provide. Indeed this has been one of the reasons that provable security has often been ignored by security practioners. In [RO93] we suggest that the random oracle paradigm can, in many cases, provide a way bridge cryptographic theory and cryptographic practice. The method (which has it's roots in [Fiat Shamir 86] and a variety of folklore) says to: (1) Assume the existence of a public random oracle; (2) Do provable security ( definition/protocol/proof) in this enriched model of computation; (3) Finally, instantiate the random oracle with an object like a cryptographic hash function. It is the thesis underlying the approach that, despite the heuristic instantiation step, substantial assurance benefits remain. Far better assurance than protocols that don't have admit any sort of provable security. In [RO93] we not explain the random oracle paradigm and we give examples which make clear the power and generality of the method. The paper is first place where asymmetric encryption and signature schemes are proven to be secure in the random oracle model. Subsequent work I have done in the random oracle model includes [OEAP95], [Sign96], and [MinRo97]. Nowadays several other authors have begun to use the random oracle model. For example, both Brickell and Schnoor each have recent papers giving security proofs for asymmetric schemes in the random oracle model.
Symmetric Encryption. Fifteen years after Goldwasser and Micali introduced the provable-security approach to cryptography, treating asymmetric (ie., public key) encryption, the case of symmetric (ie., private key) encryption was still un-addressed. Though similar to the asymmetric case, a careful treatment of symmetric encryption reveals that there are some important differences. In [Enc97] we give a concrete provable-security treatment of symmetric encryption. Building on the asymmetric treatment, we describe three definitions, all of them equivalent from the point of view of polynomial-time reductions, but which are not equivalent with respect to exact security. This allows one to select the "best" definition for existence results. Next we give a concrete security analysis for common modes of operation of a block cipher: CBC, CFB and CTR modes. We establish tight bounds on the success of adversaries attacking these schemes as a function of the resources they employ. This lets us say say which concrete schemes are best.
Fast Software Cryptography. One of the reasons that cryptography is not used more pervasively is the assumed-to-be-high computational cost for doing bulk software encryption and bulk software message authentication. In [SEAL93] we proposed what was (and remains) the fastest (published + seemingly secure) method for symmetric encryption. The algorithm SEAL-1 (Software Encryption ALgorithm) encrypts at a rate of about 5 machine instructions per byte. (This is even faster than a CRC checksum.) The SEAL paper is my only paper not in the provable-security tradition: it has no proofs or definitions. But I do pick up one important contribution from theoretical cryptography; it is in the type of cryptographic primitive which we choose to construct. Neither block cipher nor stream cipher, SEAL is a (length-increasing) pseudorandom function family. Such an object is easier to use than a stream cipher, yet more amenable than a block cipher, it seems, for achieving extreme software speeds than a block cipher. After SEAL we now knew how to encrypt messages faster than we knew how to authenticate them. To help right this, in [Bucket95] we initiated a new approach for high-speed software message authentication. Bucket hashing is a type of software-efficient Carter-Wegman hash family and, as such, it can serve as the basis for a fast Wegman-Carter MAC. [Bucket97] has inspired a good deal of follow-on work, while SEAL has become a well-known algorithm, described in the popular cryptography texts.
Secure Function Evaluation. In the Secure Function Evaluation (SFE) problem there is a group of "players," each of whom holds his own private input. They wish to evaluate some function on these private inputs in a way that reveals only the correctly-computed answer. Voting is a standard example. In the presence of a trusted party, each player could send his input to the trusted party, who would compute the function and return the answers. We want to make communication protocols which accomplish the same thing (in the absence of a trusted party). This is a classical problem, first proposed by [Yao92], and many lovely protocols have been devised, beginning with [GMW87] and [BGW88,CCD88]. My work in this domain has been in two directions. In [SFE97] Micali and I give a formal definition for the goal and prove some of the basic properties of the definition. We concentrate on the information-theoretic model and building a definition which mimics the "ideal" SFE in a very "tight" way. (For example, on each execution of the protocol, and not just in some distributional sense, there is a notion of what players -both good and bad- effectively contribute to the collaborative computation). Our notion enjoys the difficult-to-achieve property of reducibility. The other direction on SFE I have followed is to look at the efficiency of SFE protocols. In [SFE90] we show how SFE can be achieved in a constant number of rounds (computational setting with a complete network of private channels, broadcast, and honest majority). To do this, we abandon the gate-by-gate approach and use the generally-useful paradigm of issuing a "garbled circuit".
Complexity Theory. I haven't been doing much in complexity theory of late, but perhaps I will return to it. In [QP95] we show that, under a complexity assumption, there is no polynomial-time approximation algorithm (even with a terrible guarantee) for the problem of QUADRATIC PROGRAMMING. Compared to what came later, the techniques here are very simple. But the result was one of the first non-approximability results following [FGLSS], and the particular problem considered is of great interest to the mathematical programming community. The other complexity theory paper I have is [BGGHKMR], which shows that everything provable (IP) is provable in (computational) zero knowledge, either (1) under a complexity assumption, or (2) in the "envelope model." This result has a somewhat confused history, with [Ben-Or] and [Impagliazzo, Yung 87] deserving to be credited for (1).