About me
I joined Microsoft Research New England in 2008 after being an Assistant Professor of Computer Science at Georgia Tech and a postdoc at the Weizmann Institute in Israel and Microsoft Research in Redmond. I 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.
short biography contact details
Yael Tauman Kalai received her BA (1997) from the Hebrew University in Jerusalem, MA (2001) under the supervision of Adi Shamir at the Weizmann Institute, and PhD (2006) under the supervision of Shafi Goldwasser at MIT. After postdoctoral positions at Microsoft Research and the Weizmann Institute, she is now a Researcher at
Microsoft Research New England.
Her honors include an outstanding master's thesis prize, a Sprowl's award (cowinner) for best PhD Thesis at MIT. Her research focuses on cryptography.
My main research interests are Cryptography, the Theory of Computation, and Security & Privacy.
Publications
2014

Yael Tauman Kalai, Ran Raz, and Ron D. Rothblum
How to delegate computations: the power of nosignaling proofs
In Proceedings of the 46th annual ACM symposium on Theory of computing (STOC), pp. 485494, 2014.
pdf

Zvika Brakerski, Yael Tauman Kalai, Moni Naor
Fast Interactive Coding Against Adversarial Noise
Accepted to J. ACM.
pdf

Shafi Goldwasser, Yael Tauman Kalai and Guy N. Rothblum
Delegating computation: interactive proofs for muggles
Accepted to J. ACM (also appears in STOC '08).
pdf

Elette Boyle, Yael Tauman Kalai, and Shafi Goldwasser
LeakageResilient Coin Tossing
In Distributed Computing 27(3), pp. 147164, 2014 (also appears in DISC '11).
pdf

Nir Bitansky, Ran Canetti, Yael Tauman Kalai, and Omer Paneth
On Virtual Grey Box Obfuscation for General Circuits
In Advances in Cryptology (CRYPTO), pp. 108125, 2014.
pdf

Nir Bitansky, Ran Canetti, Henry Cohn, Shafi Goldwasser, Yael Tauman Kalai, Omer Paneth, and Alon Rosen
The Impossibility of Obfuscation with Auxiliary Input or a Universal Simulator
In Advances in Cryptology (CRYPTO), pp. 7189, 2014.
pdf

Boaz Barak, Sanjam Garg, Yael Tauman Kalai, Omer Paneth, and Amit Sahai
Protecting Obfuscation against Algebraic Attacks
In Advances in Cryptology (EUROCRYPTO), LNCS vol. 8441, pp. 221238, 2014.
pdf

Boaz Barak, Nir Bitansky, Ran Canetti, Yael Tauman Kalai, Omer Paneth, and Amit Sahai
Obfuscation for Evasive Functions
To appear in In Proceedings of the 11th Theory of Cryptography Conference (TCC), 2014.
pdf

Yael Tauman Kalai and Dana DachmanSoled
Securing Circuits and Protocols Against 1/poly(k) Tampering Rate
To appear in In Proceedings of the 11th Theory of Cryptography Conference (TCC), 2014.
2013

Elette Boyle, Sanjam Garg, Abhishek Jain, Yael Tauman Kalai, and Amit Sahai
Secure Computation against Adaptive Auxiliary Information
In Advances in Cryptology (CRYPTO), pp. 316334, 2013.
pdf

Shafi Goldwasser, Yael Tauman Kalai, Raluca A. Popa, Vinod Vaikuntanathan, and Nickolai Zeldovich
How to Run Turing Machines on Encrypted Data
In Advances in Cryptology (CRYPTO), pp. 536553, 2013.
pdf

Shafi Goldwasser, Yael Tauman Kalai, Raluca A. Popa, Vinod Vaikuntanathan, and Nickolai Zeldovich
Reusable garbled circuits and succinct functional encryption
In Proceedings of the 45th annual ACM symposium on Theory of computing (STOC), pp. 555564, 2013.
pdf

Yael Tauman Kalai, Ran Raz, and Ron D. Rothblum
Delegation for bounded space
In Proceedings of the 45th annual ACM symposium on Theory of computing (STOC), pp. 565574, 2013.
pdf

Nir Bitansky, Dana DachmanSoled, Sanjam Garg, Abhishek Jain, Yael Tauman Kalai, Adriana LÓpezAlt, and Daniel Wichs
Why "FiatShamir for Proofs" Lacks a Proof
In Proceedings of the 10th Theory of Cryptography Conference (TCC), pp. 182201, 2013.
pdf
2012

Shai Halevi and Yael Tauman Kalai
Smooth Projective Hashing and TwoMessage Oblivious Transfer
J. Cryptology 25(1): 158193, 2012.
pdf

Dana DachmanSoled and Yael Tauman Kalai
Securing Circuits against ConstantRate Tampering
In Advances in Cryptology (CRYPTO), pp. 533551, 2012.
pdf

Zvika Brakerski and Yael Tauman Kalai
Efficient Interactive Coding against Adversarial Noise
In Proc. 53rd IEEE Symposium on Foundations of Computer Science (FOCS), pp. 160166, 2012.
pdf

Yael Tauman Kalai, Allison B. Lewko, and Anup Rao
Formulas Resilient to ShortCircuit Errors
In Proc. 53rd IEEE Symposium on Foundations of Computer Science (FOCS), pp. 490499, 2012.
pdf

Elette Boyle, Shafi Goldwasser, Abhishek Jain, and Yael Tauman Kalai
Multiparty computation secure against continual memory leakage
In Proceedings of the 44th annual ACM symposium on Theory of computing (STOC), pp. 12351254, 2012.
pdf

Zvika Brakerski and Yael Tauman Kalai
A Parallel Repetition Theorem for Leakage Resilience
In Proceedings of the 9th Theory of Cryptography Conference (TCC), pp. 248265, 2012.
pdf
2011

Zvika Brakerski, Shafi Goldwasser, and Yael Tauman Kalai
BlackBox CircularSecure Encryption beyond Affine Functions
In Theory of Cryptography  8th Theory of Cryptography Conference (TCC), volume 6597 of Lecture Notes in Computer Science, pp. 201218, 2011.
pdf

Nir Bitansky, Ran Canetti, Shafi Goldwasser, Shai Halevi, Yael Tauman Kalai, and Guy N. Rothblum
Program Obfuscation with Leaky Hardware
In Advances in Cryptology (ASIACRYPT), pp. 722739, 2011.
pdf

KaiMin Chung, Yael Tauman Kalai, FengHao Liu, and Ran Raz
Memory Delegation
In Advances in Cryptology (CRYPTO), pp. 151168, 2011.
pdf

Yael Tauman Kalai, Bhavana Kanukurthi, and Amit Sahai
Cryptography with Tamperable and Leaky Memory
In Advances in Cryptology (CRYPTO), pp. 373390, 2011.
pdf

Mark Braverman, Avinatan Hassidim, and Yael Tauman Kalai
Leaky pseudoentropy functions
In Proc. of the Innovations in Computer Science (ICS), pp. 353366, 2011.
abstract
pdf
Pseudorandom functions (PRFs) introduced by Goldwasser, Goldreich, and Micali (FOCS 1984), are one of the most important building blocks in cryptography. A PRF family is a family of seeded functions {fs}, with the property that no efficient adversary can tell the difference between getting oracle access to a random PRF function fs, and getting oracle access to a truly random function.
In this work, we consider the problem of constructing pseudorandom functions that are resilient to leakage. Unfortunately, even if a single bit about the secret seed s ∈ {0, 1}k is leaked, then there is no hope to construct a PRF, since the leakage can simply be the first bit of fs(0), and thus fs(0) is distinguishable from uniform. Therefore, when dealing with leakage, we must relax the definition.
We consider the following relaxation: Instead of requiring that for each input x, the value fs(x) looks random, we require that it looks like it has high minentropy, even given oracle access to fs everywhere except point x. We call such a function family a pseudoentropy function (PEF) family. In particular, a leakageresilient PEF family has the property that given leakage L(s) and given oracle access to fs, it is hard to predict fs on any input that was not queried. We construct such a leakageresilient PEF family under the DDH assumption (or more generally, assuming the existence of lossy functions with the property that the output size is not much larger than the input size).
We also show that leakageresilient PEFs imply leakageresilient randominput PRFs, where the requirement is that for a random input r, the value fs(r) looks uniform, even given the leakage L(s) and given oracle access to fs anywhere accept at point r (the leakage L(s) is independent of r, but the oracle fs is present even after the pair (r, fs(r)) is given).
2010

Zvika Brakerski, Yael Tauman Kalai, Jonathan Katz, Vinod Vaikuntanathan
Overcoming the Hole in the Bucket: PublicKey Cryptography Resilient to Continual Memory Leakage
October 2010: IEEE 51st Annual Symposium on Foundations of Computer Science
abstract
pdf
In recent years, there has been a major effort to design cryptographic schemes that remain secure even if part of the secret key is leaked. This is due to a recent proliferation of side channel attacks which, through various physical means, can recover part of the secret key. We explore the possibility of achieving security even with continual leakage, i.e., even if some information is leaked each time the key is used.
We show how to securely update a secret key while information is leaked: We construct schemes that remain secure even if an attacker, at each time period, can probe the entire memory (containing a secret key) and "leak" up to a (1  o(1)) fraction of the secret key. The attacker may also probe the memory during the updates, and leak O(log k) bits, where k is the security parameter (relying on subexponential hardness allows kε bits of leakage during each update process). All of the above is achieved without restricting the model as is done in previous works (e.g. by assuming that "only computation leaks information" [MicaliReyzin, TCC04]).
Specifically, under the decisional linear assumption on bilinear groups (which allows for a leakage rate of (½o(1))) or the symmetric external DiffieHellman assumption (which allows for a leakage rate of (½  o(1))), we achieve the above for public key encryption, identitybased encryption, and signature schemes. Prior to this work, it was not known how to construct publickey encryption schemes even in the more restricted model of [MR].
The main contributions of this work are (1) showing how to securely update a secret key while information is leaked (in the more general model) and (2) giving a public key encryption (and IBE) schemes that are resilient to continual leakage.

Shafi Goldwasser, Yael Tauman Kalai, Chris Peikert and Vinod Vaikuntanathan
Robustness of the Learning with Errors Assumption
Innovations in Computer Science, 2010.
abstract pdf
Starting with the work of IshaiSahaiWagner and MicaliReyzin, a new goal has been set within the theory of cryptography community, to design cryptographic primitives that are secure against large classes of sidechannel attacks. Recently, many works have focused on designing various cryptographic primitives that
are robust (retain security) even when the secret key is "leaky", under various intractability assumptions. In this work we propose to take a step back and ask a more basic question: which of our cryptographic assumptions (rather than cryptographic schemes) are robust in presence of leakage of their underlying secrets?
Our main result is that the hardness of the learning with error (LWE) problem implies its hardness with leaky secrets. More generally, we show that the standard LWE assumption implies that LWE is secure even if the secret is taken from an arbitrary distribution with sufficient entropy, and even in the presence of hardtoinvert
auxiliary inputs. We exhibit various applications of this result.
1. Under the standard LWE assumption, we construct a symmetrickey encryption scheme that is robust to secret key leakage, and more generally maintains security even if the secret key is taken from an arbitrary distribution with sufficient entropy (and even in the presence of hardtoinvert auxiliary inputs).
2. Under the standard LWE assumption, we construct a (weak) obfuscator for the class of point functions with multibit output.
We note that in most schemes that are known to be robust to leakage, the parameters of the scheme depend on the maximum leakage the system can tolerate, and hence the efficiency degrades with the maximum anticipated leakage, even if no leakage occurs at all! In contrast, the fact that we rely on a robust assumption allows us to
construct a single symmetrickey encryption scheme, with parameters that are independent of the anticipated leakage, that is robust to any leakage (as long as the secret key has sufficient entropy left over). Namely, for any k < n (where n is the size of the secret key), if the secret key has only entropy k, then the security relies on the LWE assumption with secret size roughly k.

KaiMin Chung, Yael Tauman Kalai, and Salil Vadhan
Improved Delegation of Computation Using Fully Homomorphic Encryption
Advances in Cryptology  CRYPTO 2010;
Lecture Notes in Computer Science, 2010, Volume 6223/2010, 483501, DOI: 10.1007/9783642146237_26.
abstract pdf
Following Gennaro, Gentry, and Parno (Cryptology ePrint Archive 2009/547), we use fully homomorphic encryption to design improved schemes for delegating computation. In such schemes, a delegator outsources the computation of a function F on many, dynamically chosen inputs x i to a worker in such a way that it is infeasible for the worker to make the delegator accept a result other than F(x i ). The "online stage" of the Gennaro et al. scheme is very efficient: the parties exchange two messages, the delegator runs in time poly(logT), and the worker runs in time poly(T), where T is the time complexity of F. However, the "offline stage" (which depends on the function F but not the inputs to be delegated) is inefficient: the delegator runs in time poly(T) and generates a public key of length poly(T) that needs to be accessed by the worker during the online stage.
Our first construction eliminates the large public key from the Gennaro et al. scheme. The delegator still invests poly(T) time in the offline stage, but does not need to communicate or publish anything. Our second construction reduces the work of the delegator in the offline stage to poly(logT) at the price of a 4message (offline) interaction with a poly(T)time worker (which need not be the same as the workers used in the online stage). Finally, we describe a "pipelined" implementation of the second construction that avoids the need to rerun the offline construction after errors are detected (assuming errors are not too frequent).

Zvika Brakerski and Yael Tauman Kalai
A Framework for Efficient Signatures, Ring Signatures and Identity Based Encryption in the Standard Model
Cryptology ePrint Archive: Report 2010/086; November 2010
abstract
pdf
In this work, we present a generic framework for constructing efficient signature schemes, ring signature schemes, and identity based encryption schemes, all in the standard model (without relying on random oracles).
We start by abstracting the recent work of Hohenberger and Waters (Crypto 2009), and specifically their "prefix method". We show a transformation taking a signature scheme with a very weak security guarantee (a notion that we call apriorimessage unforgeability under static chosen message attack) and producing a fully secure signature scheme (i.e., existentially unforgeable under adaptive chosen message attack). Our transformation uses the notion of chameleon hash functions, defined by Krawczyk and Rabin (NDSS 2000) and the "prefix method". Constructing such weakly secure schemes seems to be significantly easier than constructing fully secure ones, and we present simple constructions based on the RSA assumption, the short integer solution (SIS) assumption, and the computational DiffieHellman (CDH) assumption over bilinear groups.
Next, we observe that this general transformation also applies to the regime of ring signatures. Using this observation, we construct new (provably secure) ring signature schemes: one is based on the short integer solution (SIS) assumption, and the other is based on the CDH assumption over bilinear groups. As a building block for these constructions, we define a primitive that we call ring trapdoor functions. We show that ring trapdoor functions imply ring signatures under
a weak definition, which enables us to apply our transformation to achieve full security.
Finally, we show a connection between ring signature schemes and identity based encryption (IBE) schemes. Using this connection, and using our new constructions of ring signature schemes, we obtain two IBE schemes: The first is based on the learning with error (LWE) assumption, and is similar to the recently introduced IBE scheme of CashHofheinzKiltzPeikert; The second is based on the dlinear assumption over bilinear groups.

Yevgeniy Dodis, Shafi Goldwasser, Yael Tauman Kalai, Chris Peikert and Vinod Vaikuntanathan
PublicKey Encryption Schemes with Auxiliary Inputs
Theory of Cryptography Conference: Lecture Notes in Computer Science, 2010, Volume 5978/2010, 361381, DOI: 10.1007/9783642117992_22.
abstract pdf
We construct publickey cryptosystems that remain secure even when the adversary is given any computationally uninvertible function of the secret key as auxiliary input (even one that may reveal the secret key informationtheoretically). Our schemes are based on the decisional DiffieHellman (DDH) and the Learning with Errors (LWE) problems.
As an independent technical contribution, we extend the GoldreichLevin theorem to provide a hardcore (pseudorandom) value over large fields.

Ran Canetti, Yael Tauman Kalai, Mayank Varia, Daniel Wichs
On Symmetric Encryption and Point Obfuscation
Theory of Cryptography Conference: Lecture Notes in Computer Science, 2010, Volume 5978/2010, 5271, DOI: 10.1007/9783642117992_4.
abstract pdf
We show tight connections between several cryptographic primitives, namely encryption with weakly random keys, encryption with keydependent messages (KDM), and obfuscation of point functions with multibit output (which we call multibit point functions, or MBPFs, for short). These primitives, which have been studied mostly
separately in recent works, bear some apparent similarities, both in the flavor of their security requirements and in the flavor of their constructions and assumptions. Still, rigorous connections have not been drawn.
Our results can be interpreted as indicating that MBPF obfuscators imply a very strong form of encryption that simultaneously achieves security for weaklyrandom keys and keydependent messages as special cases.
Similarly, each one of the other primitives implies a certain restricted form of MBPF obfuscation. Our results carry both constructions and impossibility results from one primitive to others. In particular:
 The recent impossibility result for KDM security of Haitner and Holenstein (TCC '09) carries over to MBPF obfuscators.
 The CanettiDakdouk construction of MBPF obfuscators based on a strong variant of the DDH assumption (EC '08) gives an encryption scheme which is secure w.r.t. any weak key distribution of superlogarithmic minentropy (and in particular, also has very strong leakage resilient properties).
 All the recent constructions of encryption schemes that are secure w.r.t. weak keys imply a weak form of MBPF obfuscators.
2009

Yevgeniy Dodis, Yael Tauman Kalai, Shachar Lovett
On Cryptography with Auxiliary Input
STOC '09: Proceedings of the 41st annual ACM symposium on Theory of computing
abstract
pdf
We study the question of designing cryptographic schemes which are secure even if an arbitrary function f(sk) of the secret key is leaked, as long as the secret key sk is still (exponentially) hard to compute from this auxiliary input. This setting of auxiliary input is more general than the more traditional setting, which assumes that some of information about the secret key sk may be leaked, but sk still has high minentropy left. In particular, we deal with situations where f(sk) informationtheoretically determines the entire secret key sk.
As our main result, we construct CPA/CCA secure symmetric encryption schemes that remain secure with exponentially hardtoinvert auxiliary input. We give several applications of such schemes.
* We construct an averagecase obfuscator for the class of point functions, which remains secure with exponentially hardtoinvert auxiliary input, and is reusable.
* We construct a reusable and robust extractor that remains secure with exponentially hardtoinvert auxiliary input. Our results rely on a new cryptographic assumption, Learning SubspacewithNoise (LSN), which is related to the well known Learning ParitywithNoise (LPN) assumption.

Yael Tauman Kalai, Xin Li, and Anup Rao
2Source Extractors Under Computational Assumptions and Cryptography with Defective Randomness
In Proc. 50th IEEE Symposium on Foundations of Computer Science (FOCS), pp. 617626, 2009.
pdf

Yael Tauman Kalai and Ran Raz
Probabilistically Checkable Arguments
Advances in Cryptology  CRYPTO 2009; Lecture Notes in Computer Science, 2009, Volume 5677/2009, 143159, DOI: 10.1007/9783642033568_9.
pdf
2008

Yael Tauman Kalai, and Ran Raz
Interactive PCP
Automata, Languages and Programming; Lecture Notes in Computer Science, 2008, Volume 5126/2008, 536547, DOI: 10.1007/9783540705833_44.
abstract pdf

Shafi Goldwasser, Yael Tauman Kalai and Guy N. Rothblum
OneTime Programs
Advances in Cryptology  CRYPTO 2008: Lecture Notes in Computer Science, 2008, Volume 5157/2008, 3956, DOI: 10.1007/9783540851745_3.
abstract pdf
In this work, we introduce onetime programs, a new computational paradigm geared towards security applications. A onetime program can be executed on a single input, whose value can be specified at run time. Other than the result of the computation on this input, nothing else about the program is leaked. Hence, a onetime program is like a black box function that may be evaluated once and then "self destructs". This also extends to ktime programs, which are like black box functions that can be evaluated k times and then self destruct.
Onetime programs serve many of the same purposes of program obfuscation, the obvious one being software protection, but also including applications such as temporary transfer of cryptographic ability. Moreover, the applications of onetime programs go well beyond those of obfuscation, since onetime programs can only be executed once (or more generally, a limited number of times) while obfuscated programs have no such bounds. For example, onetime programs lead naturally to electronic cash or token schemes: coins are generated by a program that can only be run once, and thus cannot be double spent.
Most significantly, the new paradigm of onetime computing opens new avenues for conceptual research. In this work we explore one such avenue, presenting the new concept of "onetime proofs", proofs that can only be verified once and then become useless and unconvincing.
All these tasks are clearly impossible using software alone, as any piece of software can be copied and run again, enabling the user to execute the program on more than one input. All our solutions employ a secure memory device, inspired by the cryptographic notion of interactive oblivious transfer protocols, that stores two secret keys (k 0,k 1). The device takes as input a single bit b∈{0,1}, outputs k b , and then self destructs. Using such devices, we demonstrate that for every input length, any standard program (Turing machine) can be efficiently compiled into a functionally equivalent onetime program. We also show how this memory device can be used to construct onetime proofs. Specifically, we show how to use this device to efficiently convert a classical witness for any NP statement, into "onetime proof" for that statement.

Yael Tauman Kalai, Xin Li, David Zuckerman, Anup Rao
Network Extractor Protocols
FOCS 2008: 49th Annual IEEE Symposium on Foundations of Computer Science
abstract pdf
2007

Yael Tauman Kalai, Ran Raz
Interactive PCP
Electronic Colloquium on Computational Complexity, Report No. 31, 2007
abstract pdf

Yael Tauman Kalai, Yehuda Lindell and Manoj Prabhakaran
Concurrent Composition of Secure Protocols in the Timing Model
Journal of Cryptology: Volume 20, Number 4, 431492, DOI: 10.1007/s0014500705671.
abstract pdf ps
In the setting of secure multiparty computation, a set of mutually distrustful parties wish to securely compute some joint function of their inputs. In the standalone case it has been shown that every efficient function can be securely computed. However, in the setting of concurrent composition, broad impossibility results have been proven for the case of no honest majority and no trusted setup phase. These results hold both for the case of general composition (where a secure protocol is run many times concurrently with arbitrary other protocols) and selfcomposition (where a single secure protocol is run many times concurrently). In this paper we investigate the feasibility of obtaining security in the concurrent setting, assuming that each party has a local clock and that these clocks proceed at approximately the same rate. We show that under this mild timing assumption, it is possible to securely compute any multiparty functionality under concurrent selfcomposition. Loosely speaking, we also show that it is possible to securely compute any multiparty functionality under concurrent general composition, as long as the secure protocol is run only with protocols whose messages are delayed by a specified amount of time. On the negative side, we show that it is impossible to achieve security under concurrent general composition with no restrictions whatsoever on the network (like the aforementioned delays), even in the timing model.
2006

Ronald L Rivest, Adi Shamir, Yael Tauman
How to leak a secret: Theory and Applications of Ring Signatures
Essays in Theoretical Computer Science: in Memory of Shimon Even, volume 3895 of LNCS Festschrift.
abstract pdf
In this work we formalize the notion of a ring signature, which makes it possible to specify a set of possible signers without revealing which member actually produced the signature. Unlike group signatures, ring signatures have no group managers, no setup procedures, no revocation procedures, and no coordination: 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 getting their approval or assistance. Ring signatures provide an elegant way to leak authoritative secrets in an anonymous way, to sign casual email in a way that can only be verified by its intended recipient, and to solve other problems in multiparty computations. Our main contribution lies in the presentation of efficient constructions of ring signatures; the general concept itself (under different terminology) was first introduced by Cramer et al. [CDS94]. Our constructions of such signatures are unconditionally signerambiguous, secure in the random oracle model, and exceptionally efficient: adding each ring member increases the cost of signing or verifying by a single modular multiplication and a single symmetric encryption. We also describe a large number of extensions, modifications and applications of ring signatures which were published after the original version of this work (in Asiacrypt 2001).

Yael Tauman Kalai, Ran Raz
Succinct NonInteractive ZeroKnowledge Proofs with Preprocessing for LOGSNP
Electronic Colloquium on Computational Complexity, Report No. 31, 2007
abstract pdf

Yael Tauman Kalai
Attacks on the FiatShamir Paradigm and Program Obfuscation
PhD thesis, 2006
abstract pdf
2005 and earlier

Yael Tauman Kalai
Smooth Projective Hashing and TwoMessage Oblivious Transfer
In EUROCRYPT 2005, SpringerVerlag (LNCS 3494)
abstract pdf
We present a general framework for constructing twomessage oblivious transfer protocols using a modification of Cramer and Shoup's notion of smooth projective hashing (2002). Our framework is actually an abstraction of the twomessage oblivious transfer protocols of Naor and Pinkas (2001) and Aiello et. al. (2001), whose security is based on the Decisional Diffie Hellman Assumption. In particular, this framework gives rise to two new oblivious transfer protocols. The security of one is based on the N'thResiduosity Assumption, and the security of the other is based on both the Quadratic Residuosity Assumption and the Extended Riemann Hypothesis.
When using smooth projective hashing in this context, we must deal with maliciously chosen smooth projective hash families. This raises new technical difficulties that did not arise in previous applications, and in particular it is here that the Extended Riemann Hypothesis comes into play.
Similar to the previous twomessage protocols for oblivious transfer, our constructions give a security guarantee which is weaker than the traditional, simulation based, definition of security. Nevertheless, the security notion that we consider is nontrivial and seems to be meaningful for some applications in which oblivious transfer is used in the presence of malicious adversaries.

Shafi Goldwasser and Yael Tauman Kalai
On the Impossibility of Obfuscation with Auxiliary Input
In Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS'05
pdf

Yael Tauman Kalai, Yehuda Lindell, Manoj Prabhakaran
Concurrent General Composition of Secure Protocols in the Timing Model
STOC '05 Proceedings of the thirtyseventh annual ACM symposium on Theory of computing.
abstract pdf ps
In the setting of secure multiparty computation, a set of mutually distrustful parties wish to jointly compute some function of their input (i.e., they wish to securely carry out some distributed task). The joint computation should be such that even In the standalone case, it has been shown that every efficient function can be securely computed. However, in the setting of concurrent composition, broad impossibility results have been proven for the case where there is no honest majority (or trusted setup).In this paper, we investigate the feasibility of obtaining secure multiparty protocols in a network where certain time bounds are assumed. Specifically, the security of our protocols rely on the very reasonable assumption that local clocks do not "drift" too much (i.e., it is assumed that they proceed at approximately the same rate). We show that under this mild timing assumption, it is possible to securely compute any functionality under concurrent general composition (as long as messages from the arbitrary other protocols are delayed for a specified amount of time).

Shafi Goldwasser and Yael Tauman
On the (In)security of the FiatShamir Paradigm
Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science
abstract pdf
In 1986, Fiat and Shamir proposed a general method for transforming secure 3round publiccoin identification schemes into digital signature schemes. The idea of the transformation was to replace 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.
The FiatShamir methodology for producing digital signature schemes quickly gained popularity 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 FiatShamir methodology secure?
In this paper, we answer this question negatively. We show that there exist secure 3round publiccoin identification schemes for which the FiatShamir transformation yields insecure digital signature schemes for any "hash" function used by the transformation. This is in contrast to the work of Pointcheval and Stern which proved that the FiatShamir methodology always produces digital signatures secure against chosen message attack in the "Random Oracle Model"  when the hash function is modelled by a random oracle.
Among other things, we make new usage of Barak's technique for taking advantage of non blackbox access to a program, this time in the context of digital signatures.

Ron Rivest, Adi Shamir and Yael Tauman
How to leak a secret
Proceedings of the 7th International Conference on the Theory and Application of Cryptology and Information Security: Advances in Cryptology.
abstract pdf
In this paper we formalize the notion of a ring signature, which makes it possible to specify a set of possible signers without revealing which member actually produced the signature. Unlike group signatures, ring signatures have no group managers, no setup procedures, no revocation procedures, and no coordination: 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 getting their approval or assistance. Ring signatures provide an elegant way to leak authoritative secrets in an anonymous way, to sign casual email in a way which can only be verified by its intended recipient, and to solve other problems in multiparty computations. The main contribution of this paper is a new construction of such signatures which is unconditionally signerambiguous, provably secure in the random oracle model, and exceptionally efficient: adding each ring member increases the cost of signing or verifying by a single modular multiplication and a single symmetric encryption.

Adi Shamirand Yael Tauman
Improved online/offline signature schemes
Advances in Cryptology  CRYPTO 2001: Lecture Notes in Computer Science, 2001, Volume 2139/2001, 355367, DOI: 10.1007/3540446478_21.
abstract pdf
The notion of online/offline signature schemes was introduced in 1990 by Even, Goldreich and Micali. They presented a general method for converting any signature scheme into an online/offline signature scheme, but their method is not very practical as it increases the length of each signature by a quadratic factor. In this paper we use the recently introduced notion of a trapdoor hash function to develop a new paradigm called hashsignswitch, which can convert any signature scheme into a highly efficient online/offline signature scheme: In its recommended implementation, the online complexity is equivalent to about 0.1 modular multiplications, and the size of each signature increases only by a factor of two. In addition, the new paradigm enhances the security of the original signature scheme since it is only used to sign random strings chosen offline by the signer. This makes the converted scheme secure against adaptive chosen message attacks even if the original scheme is secure only against generic chosen message attacks or against random message attacks.