While modern research in cryptography has transformed a significant portion of computer security from an art into a science, ultimately the security guarantees for all current cryptographic protocols (encryption, digital signatures, etc.) rely on conjectures, such as the intractability of factoring large integers is intractable or of finding collisions in certain "hash functions". The possibility that these conjectures are false (as was recently discovered for some popular hash functions) is a genuine threat to cybersecurity.
This project aims to reduce this threat by minimizing the assumptions needed for specific cryptographic primitives (such as commitment schemes, which can be viewed as "digital safes"), and attempting to base cryptography on the hardness of an entire class of problems. More generally, the project aims to strengthen the foundations of cryptography and cybersecurity using techniques from computational complexity theory.
Society benefits from this project because of the enabling role that cryptography plays in electronic commerce. Stronger foundations for cryptography help prevent electronic commerce from becoming vulnerable to unforeseen attack. Further impact of this project comes through the training of graduate and undergraduate students, both through their attendance in courses taught by the PI and through their direct involvement in the research.
Modern research in cryptography has transformed a significant portion of computer security from an art into a science, but the security guarantees it provides currently rely on unproven mathematical conjectures (e.g that factoring large integers is computationally intractable). The possibility that these conjectures are false is a genuine threat to cybersecurity. We have worked towards reducing this threat by designing new cryptographic algorithms based on the weakest possible conjectures. These algorithms are substantially simpler and more efficient than previous ones. In addition, we have obtained new results on the possibilities and limits of data privacy. Here the goal is to be able to allow the analysis of sensitive datasets while both protecting the privacy of the individuals whose data is present and maintaining high accuracy for statistics of interest. Our results have shown that limitations on computational power significantly affect what can be achieved. Certain kinds of data summaries can be produced while protecting privacy, but doing so inherently requires an exponential amount of computing time. On the other hand, if we assume that the adversary also has limited computing time, then this allows some statistics to be privately computed with greater accuracy than if the adversary has unlimited computing power. Three Ph.D. students and four undergraduates were trained under this project, most of whom achieved publications and/or presentations at leading conferences and journals, and have continued in research after graduation. The PI taught two courses related to the project, whose materials (including lecture notes and a draft textbook) are publicly available from the PI’s webpage (http://seas.harvard.edu/~salil). The PI engaged in a variety of outreach activities, including writing an article for the Encyclopedia of Cryptography & Security (aimed at practitioners and laypeople), leading the development of "vision nuggets" to illustrate research directions in theoretical computer science to a lay audience (http://thmatters.wordpress.com/vision-nuggets/), organizing conferences, and serving as Director of the Harvard Center for Research on Computation and Society (which fosters interaction between computer science and other disciplines).
