Randomization has proved to be a vital part in building essentially any kind of secure cryptographic system: secret keys should be randomly generated and most cryptographic primitives, such as encryption, must be probabilistic. As a common abstraction, it is typically assumed that ideal randomness is available to all the participants of the system. In many situations, this assumption is highly unrealistic, and cryptographic systems have to be built based on *imperfect* sources of randomness.
Intellectual Merits of the Project: The research will address the question as to what extent cryptographic protocols can be adapted to work with imperfect sources of randomness. In particular, it will concentrate on the feasibility of cryptography imperfect sources of randomness and exposure-resilient cryptography. For the first topic, the PI will address the question if nearly ideal randomness is *necessary* for building various cryptographic primitives, such as encryption and authentication, or, perhaps, one can base such applications on more realistic imperfect sources. For the second topic, in many settings the adversary can gain partial knowledge of some secret information (e.g., a cryptographic key). The exact nature of this knowledge is often unknown, except that it is ``bounded''. Therefore, even if the secret was originally random, it looks like an imperfect random source to the adversary, given his partial knowledge about the secret. The PI will design novel protocols which are resilient to such leakage of partial information in the recently proposed Bounded Retrieval Model.
Broader Impacts of the Project: The availability of ideal randomness is a common assumption used not only in cryptography, but in many other areas of computer science, and engineering in general. Questioning the validity of this assumption and designing techniques to base a given system on weaker, more *realistic* assumptions will surely be useful in many other disciplines. Additionally, given the increasing spread of viruses, Internet worms and Trojan horses, the use of exposure-resilient protocols will result in more stable and secure application environments. Furthermore, because the research in this project will use tools from information theory and pseudorandomness to solve cryptographic questions, it will help find new connections among these fields.
The PI also regularly teaches courses on cryptography and network security, and will be able to incorporate the new results into such courses. In addition, the project has a significant graduate student training component.
