While the mathematical study of cryptography has yielded a rich theory, and while the use of cryptography has become quite widespread, there is unfortunately still a significant gap between the theory and practice of cryptography. The goal of this research is to try to bridge this gap. The emphasis is on the design and analysis of fundamental cryptographic primitives that are practical yet theoretically sound. This research focuses on two specific areas: the design and use of secure hash functions, and the design of more efficient privacy-preserving protocols.
Because of recently discovered weaknesses in industry-standard hash functions, there is renewed interest and urgency to study the basic design principles of hash functions, as well as how such hash functions should be appropriately used in applications. Indeed, although hash functions were originally designed to serve as message digests, which should provide a form of security known as collision resistance, they are actually used in many different types of applications where the security requirements may be somewhat different: sometimes the security requirement of the hash function in a given application may be weaker than, stronger than, or perhaps just incomparable to collision resistance. This project investigates new methodologies for constructing hash functions that satisfy the various security requirements required in applications, as well as how the applications themselves may be adapted so as to minimize the security requirements placed on the hash function.
With the widespread use of computers and the Internet in daily transactions, concerns about privacy issues have taken on new urgency. One key aspect of privacy is deniability: if a user runs a protocol, it should not be possible for an eavesdropper, or even another participant in the protocol, to convince a third party that the transaction actually occurred. While there are compelling reasons to focus on this area for its own sake, there are also a number of technical issues that arise that overlap with some of the subproblems associated with hash functions.
Hash functions are special algorithms which take as input an arbitrarily long string and compress to to a short output string. Not suprisingly, hash functions have a wide variety of cryptographic applications, ranging from message digests, key derivation functions, message authentication codes, biometric-based randomness extractors, and random oracles. Unfotunately, many applications of hash functions do not explicitly specify which security property of such functions they need. Correspondingly, some applications end up using hash functions which are either too weak (maining some surprising attacks might be found in the future) or too strong (meaning that simpler, more efficient hash functions would siffice) for the talk at hand. Moreover, there is a significant gap between the theory and practice of cryptographic hash functions. The goal of this research was to try to bridge this gap, with the emphasis on the design and analysis of hash functions that are practical yet theoretically sound. Our outcomes are the following. First, we have developed a new design criteria for Hash functions, called indifferentiability from random oracle. This design criteria is stronger that previously studied properties like collision-resistance, and it became widely adopted in the hashing community. For example, it became a requirment for the new SHA3 competition on hash function design. We also showed how to modify existing hash functions to meet our new notion. We also asked the question of understanding minimal assumptions on the compression functions of current standard hash function SHA, or other cascade-based hash functions, so that existing hash functions (or close variants of them) can satisfy various important properties, such as pseudorandomness, collision-resistance, etc. In a related note, we developed novel properties of hash functions, such as preimage awareness and public-use random oracle, which are: (a) satisfied by existing hash functions, such as SHA; (b) are sufficient for proving the security of various cryptographic applications, such as signature schemes. Our notion of preimage awareness is also very useful for building new hash functions. This was demonstrated by the PI Dodis by formally proving the security of MD6 - a new hash functions submitted to the hash function competition - and also by other researchers designing a hash function SKEIN. In a related domain of building secure message authentication codes, we have initiated a question of building variable-input length message authentication codes (MACs) from block ciphers under minimal assumptions on the security of the block cipher. No previous constructions satisfied our notion. We managed to build several constructions achieving our notion. Based on our construction, we advocated a new design criteria for building a mode of operations for block ciphers, and built the first such mode of operation, called enciphered CBC. We later improved the security of our mode by designing a new mode of operation, called SS-NMAC, achieving 'birthday security'. Most recently, we built a new mode of operation which achieves optimal, 'beyond-birthday' security. We have also studied new modes of operations of hash functions which are somewhat resistant to the so called 'side-channel attacks'. Such attacks leak unexpected information about the secret key/inputs to the attacker. We also developed the first 'leakage-resilient' block cipher under natural assumption on the leakage function available to the attacker. As the less central part of this project, we have developed new methods for enabling secure protocols that provide anonymity. In particular, we have developed new, more practical protocols that can be securely run on the Internet, even in the precense of other, possible malicious protocols. These protocols provide anonymity for participants and, more generally, provide a very high level of security. We have also developed new methods for constructing (so called chosen-ciphertext secure) public-key encryption schemes. These new methods use a novel variation of the 'hash proof system' methodology developed by Cramer and Shoup. They give rise to new systems that enjoy very strong security properties, and have a number of other applications in protocol design. We have also developed new methods for constructing public key encryption schemes with even stronger security properties, namely, security against key dependent chosen plaintext and adaptive chosen ciphertext attack. We have also initiated research into privacy-preserving protocols that allow two users to authenticate each other and establish a shared session key, based on possession of appropriate credentials, rather than a public-key infrastructure. We called this new type of protocol a CAKE protocol (Credential Authenticated Key Exchange), and developed the first proptocol satisfying this notion. We have also shown how to implement secure protocols for using anonymous credentials on standard, current generation smart card The two PIs regularly teach courses on cryptography and network security, and are actively incorporating the new results into the courses they teach. In addition, the proposal had a significant graduate student training component, and resulted in graduating several new PhD students.
