New Complexity-Theoretic Techniques in Cryptography

提案CNS-0430336标题：密码学中的新复杂性理论技术PI：Salil P.Vadhan研究集中在几种强大的技术上，这些技术来自计算复杂性(对计算上难以处理的问题的研究)，它们可能有助于解决密码学和安全中的重要公开问题。这些技术包括随机性抽取器、Nisan-Wigderson类型的伪随机生成器、完全问题、对角化和算法代码的非黑盒使用。这些努力既包括加强这些复杂性理论技术的现有应用，如使用人类可记忆的密码进行密码学，减轻密钥暴露的影响，以及生物识别；又包括寻求新的应用，特别是对于密码学中标准技术范围之外的问题，如证明Fiat-Shamir类型数字签名的安全性，从没有陷门的单向函数进行公钥密码学，以及了解混淆、水印和同态加密的可能性。这项研究在本质上是基础性的，但它可以影响可信计算中的各种实际兴趣问题。研究将与教育努力紧密结合，通过哈佛大学开发的新课程以及研究生和本科生参与研究。

Proposal CNS-0430336Title: New Complexity-Theoretic Techniques in CryptographyPI: Salil P. VadhanThe 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.