Moni Naor
The Judith Kleeman Professor
The main thrust of my research lies
in the foundations of cryptography and its relationship with complexity theory.
Computational complexity theory studies the intrinsic resources needed to perform
various computational tasks. The term resource refers not just to traditional
measures such as (computer) time and memory, but also to things such as the
amount of coordination needed between processors trying to perform some task.
My research goal is to investigate these requirements. In particular I am interested
in cases where the a lower bound on the required resources needed to solve one
task implies an efficient solution to another one. Much of the research in Cryptography,
which is the study of methods for maintaining the secrecy and integrity of information
in computer and communication systems, is based on this idea. Recent directions
I have been pursuing include the application of moderately hard functions to
abuse prevention and spam fighting.
Recent Publications
- [with O. Reingold] Number-theoretic constructions of efficient pseudo-random functions. J. ACM 51(2) (2004) 231-262.
- On Cryptographic Assumptions and Challenges. Proceedings of CRYPTO 2003, Lecture Notes in Computer Science 2729, Springer, 2003, 96-109.
- [with R. Fagin and A. Lotem] Optimal aggregation algorithms for middleware. J. Comput. Syst. Sci. 66(4) (2003) 614-656.