Yael Tauman Kalai

About me

I have recently joined as a researcher at Microsoft Research New England, coming from being an Assistant Professor of Computer Science at Georgia Tech. Before this, I was a postdoc at the Weizmann Institute in Israel and Microsoft Research in Redmond. I recently graduated from MIT, working in cryptography under the superb supervision of Shafi Goldwasser. I was also extremely fortunate to have the guidance of Adi Shamir for my master's degree.

Courses

At Georgia Tech, Spring 2008:

CS 8803FC - Foundations of Cryptography. Spring 2008

Publications

• 2-Source Extractors Under Computational Assumptions and Cryptography with Defective Randomness . With Xin Li and Anup Rao. In Proc. 47th IEEE Symposium on Foundations of Computer Science (FOCS 2009).
• Probabilistically Checkable Arguments. With Ran Raz. In Advances in Cryptology - CRYPTO 09, LNCS vol. 5677 (CRYPTO 2008). 
• Network Extractor Protocols.  With Xin Li, Anup Rao, and David Zuckerman. In Proc. 46th IEEE Symposium on Foundations of Computer Science (FOCS 2008).
• Interactive PCP. With Ran Raz. Lecture Notes in Computer Science 5126 (ICALP 2008), pp. 536-547.
• One-time programs. With Shafi Goldwasser and Guy Rothblum. In Advances in Cryptology - CRYPTO 08, LNCS vol. 5157 (CRYPTO 2008).

• Delegating Computation: Interactive Proofs for Muggles. With Shafi Goldwasser and Guy Rothblum. In Proc. 40th ACM Symposium on Theory of Computing (STOC 2008).

• Attacks on the Fiat-Shamir Paradigm and Program Obfuscation. Ph.D. Thesis, Massachusetts Institute of Technology, August 2006.
• Succinct Non-Interactive Zero-Knowledge Proofs with Preprocessing for LOGSNP. With Ran Raz. In Proc. 46th IEEE Symposium on Foundations of Computer Science (FOCS 2006), pp. 355-366.
• On the Impossibility of Obfuscation with Auxiliary Inputs. With Shafi Goldwasser. In Proc. 46th IEEE Symposium on Foundations of Computer Science (FOCS 2005).
• Smooth Projective Hashing and Two-Message Oblivious Transfer. In Advances in Cryptology - EUROCRYPT 05, LNCS vol. 3494 (EUROCRYPT 2005).
• Concurrent general composition of secure protocols in the timing model. With Yehuda Lindell and Manoj Prabhakaran. In Proc. 37th ACM Symposium on Theory of Computing (STOC 2005), pp. 644-653.
  • Long version
• On the (In)security of the Fiat-Shamir Paradigm. With Shafi Goldwasser. In Proc. 44th IEEE Symposium on Foundations of Computer Science (FOCS 2003), pp. 102-113. (Invited to a special issue of Journal of Computer and System Sciences.)
  • Long version
• How to Leak a Secret. With Ronald Rivest and Adi Shamir. In Advances in Cryptology - ASIACRYPT 01, LNCS vol. 2248 (ASIACRYPT 2001), pp. 552-565.
  • How to Leak a Secret: Theory and Applications of Ring Signatures. With Ronald Rivest and Adi Shamir. A chapter in Essays in Theoretical Computer Science: in Memory of Shimon Even.
• Improved Online/Offline Signature Schemes. With Adi Shamir. In Advances in Cryptology - CRYPTO 01, LNCS vol. 2139 (CRYPTO 2001), pp. 355-357. 

Program Committees

• Computational Complexity 2008 (CCC)
• Theory of Cryptography 2007 (TCC)

Education

• 2006-2007 Microsoft Research Redmond and Weizmann Institute of Science. Postdoctoral fellow. (half year each)
• 2002–2006 Massachusetts Institute of Technology. Ph.D. Computer Science.
• 1998–2001 The Weizmann Institute of Science. M.Sc. Computer Science and Applied Mathematics.
• 1994–1997 The Hebrew University of Jerusalem. B.Sc. Mathematics, Summa Cum Laude.

Awards

• 2007 M.I.T.: George M. Sprowls Award for the best doctoral thesis in computer science.
• I.B.M. Ph.D. Fellowship (2004-2006).
• M.I.T. Presidential Graduate Fellowship (2003-2004).
• Weizmann Institute: Outstanding master’s thesis prize, 2001.
• Vatat scholarship 2001.
• Hebrew University: Summa Cum Laude award, 1997.