Yael Tauman Kalai
From Theory
As of summer 08, I'm no longer at Georgia Tech. See my new homepage here.
College of Computing
Georgia Institute of Technology
266 Ferst Drive, office 2134
Atlanta, GA 30332-0765
Contents |
About me
I am 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
CS 8803FC - Foundations of Cryptography. Spring 2008
Publications
- Probabilistically Checkable Arguments. With Ran Raz. ( Manuscript. )
- Interactive PCP. With Ran Raz. ( Submitted. )
- One-time programs. With Shafi Goldwasser and Guy Rothblum. ( Submitted. )
- Delegating Computation: Interactive Proofs for Muggles. With Shafi Goldwasser and Guy Rothblum.
To appear in Proc. 40th ACM Symposium on Theory of Computing (STOC 2008).
We study the problem of delegating polynomial time computations to an untrusted party. The challenge is: How can a delegator verify that the delegatee performed the computation correctly, using less resources than it takes to
actually run the computation, and without the delegatee working too hard.
(The celebrated result IP=SPCASE implies that any PSPACE computation can be delegated to a PSPACE-powerful delegatee and verified in polynomial time and communication complexity). We give a delegation protocol for a broad class of polynomial-time computations, where the delegatee runs in polynomial time, and where the communication complexity and verifier's run-time is significantly smaller than would be required to do the actual computation.
- Attacks on the Fiat-Shamir Paradigm and Program Obfuscation. Ph.D. Thesis, Massachusetts Institute of Technology, August 2006.
Winner of the George M. Sprowls Award (see below).
In Proc. 46th
IEEE Symposium on Foundations of Computer Science (FOCS 2006), pp. 355-366.
Zero-knowledge proofs are pervasive in modern cryptography. An important goal is to construct short zero-knowledge protocols. We show that with a small preprocessing phase, interesting classes of languages (with poly-logarithmic sized witnesses) admit short (poly-logarithmic sized) non-interactive zero-knowledge protocols.
- On the Impossibility of Obfuscation with Auxiliary Inputs. With Shafi Goldwasser.
In Proc. 46th
IEEE Symposium on Foundations of Computer Science (FOCS 2005).
The goal of obfuscation is to make a program unintelligible
while preserving its functionality. It has been shown that there exist
(contrived) classes of functions that are not obfuscatable, while the
(trivial) class of point functions can be obfuscated. This leaves open
the question of whether most programs of interest are obfuscatable. We
show that this is unlikely to be the case by giving natural classes of
functions that cannot be obfuscated w.r.t. auxiliary input.
In Advances in Cryptology - EUROCRYPT 05, LNCS vol. 3494 (EUROCRYPT 2005). Oblivious transfer is a fundamental cryptographic primitive. We present a general framework for constructing two-message oblivious transfer protocols using a modification of Cramer and Shoup's notion of smooth projective hashing. Our framework can be viewed as an abstraction of the two-message oblivious transfer protocol of Naor and Pinkas and Aiello et al.
- 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.
In multiparty computation, a set of mutually distrustful parties wish
to jointly and securely compute some function of their inputs.
In the stand-alone setting (where the protocol runs in isolation), it
has been shown that every efficient function can be securely computed.
We show that in the concurrent setting (where protocols are run
concurrently), every function can be securely computed, assuming that
all parties have local clocks that run at
approximately the same rate. (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.)
In 1986, Fiat and Shamir proposed a general method for
transforming identification schemes
into digital signature schemes, by replacing the random message of the
verifier
in the identification scheme, with the value of some deterministic hash
function evaluated on various quantities in the protocol and on the
message to
be signed. This methodology quickly gained popularity both in theory
and in
practice, as it yields efficient and easy to implement digital
signature
schemes. The most important question however remained open: are
the digital signatures produced by the Fiat-Shamir methodology
secure?
We answer this question negatively. We show that there exist secure identification schemes for which the Fiat-Shamir transformation yields insecure digital signature schemes for any hash function used by the transformation. (Long version)
- 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.
This comprehensive survey of ring signatures includes our original
work (the paper below) as well as a summary of many follow-up
papers.
- 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.
In this paper we introduce the notion of a ring signature, which makes
it possible to sign a message anonymously by
specifying a set of possible signers, without revealing which member
actually produced the signature. Any user can choose any set of
possible signers that includes himself, and sign any message by using
his secret key and the others' public keys, without any coordination or
setup (even without their approval or assistance). We present a very
efficient construction of such signatures which is unconditionally
signer-ambiguous and provably secure in the random oracle model.
- Improved Online/Offline Signature Schemes. With Adi Shamir.
In Advances in Cryptology - CRYPTO 01, LNCS vol. 2139 (CRYPTO
2001), pp. 355-357.
We give a procedure for converting any signature scheme into a highly
efficient online/offline signature scheme (a notion introduced by Even,
Goldreich, and Micali), whose online phase requires about 0.1 modular
exponentiations, whose signature-size blowup is only a factor of two,
and whose security is enhanced (security against random message attacks
leads to security against adaptive chose message attacks).
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.
