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.