New Complexity-Theoretic Techniques in Cryptography

Harvard University, Cambridge MA

Investigators

Abstract

Proposal CNS-0430336 Title: New Complexity-Theoretic Techniques in Cryptography PI: Salil P. Vadhan The research focuses on several powerful techniques from computational complexity (the study of problems that are computationally intractable) that they may help in addressing important open problems in cryptography and security. These techniques include randomness extractors, Nisan-Wigderson-type pseudorandom generators, complete problems, diagonalization, and non-black-box use of an algorithm's code. The efforts include both strengthening existing applications of these complexity-theoretic techniques, such as doing cryptography with human-memorizable passwords, mitigating the effect of key exposure, and biometrics; and seeking new applications, especially to problems that have remained beyond the scope of standard techniques in cryptography, such as proving the security of Fiat-Shamir-type digital signatures, doing public-key cryptography from one-way functions with no trapdoor, and understanding the extent to which obfuscation, watermarking, and homomorphic encryption are possible. The research is foundational in nature, yet it can impact a variety of problems of practical interest in trustworthy computing. The research will be closely integrated with educational efforts, through new courses developed at Harvard and the involvement of both graduate and undergraduate students in the research.