Publications
2014

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).

Elette Boyle, Yael Tauman Kalai, and Shafi Goldwasser
LeakageResilient Coin Tossing
In Proc. of 25th Distributed Computing Symposium (DISC), pp. 181196, 2011.
abstract
pdf
The ability to collectively toss a common coin among n parties in the presence of faults is an important primitive in the arsenal of randomized distributed protocols. In the case of dishonest majority, it was shown to be impossible to achieve less than 1/r bias in O(r) rounds (Cleve STOC '86). In the case of honest majority, in contrast, unconditionally secure O(1)round protocols for generating common unbiased coins follow from general completeness theorems on multiparty secure protocols in the secure channels model (e.g., BGW, CCD STOC '88).
However, in the protocols with honest majority, parties must generate and hold local secret values which are assumed to be perfectly hidden from malicious parties: an assumption which is crucial to proving the resulting common coin is unbiased. This assumption unfortunately does not seem to hold in practice, as attackers can launch sidechannel attacks on the local state of honest parties and leak information on their secrets.
In this work, we present an O(1)round protocol for collectively generating an unbiased common coin, in the presence of leakage on the local state of the honest parties. We tolerate t <= ( 1/3  epsilon)n computationallyunbounded Byzantine faults and in addition a Omega(1)fraction leakage on each (honest) party's secret state. Our results hold in the memory leakage model (of Akavia, Goldwasser, Vaikuntanathan '08) adapted to the distributed setting.
Additional contributions of our work are the tools we introduce to achieve the collective coin toss: a procedure for disjoint committee election, and leakageresilient verifiable secret sharing
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.

Zvika Brakerski, Shafi Goldwasser, Yael Tauman Kalai
BlackBox CircularSecure Encryption Beyond Affine Functions
iacr.org.
abstract 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.
abstract 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.

Shafi Goldwasser, Yael Tauman Kalai and Guy N. Rothblum
Delegating computation: interactive proofs for muggles
STOC '08 Proceedings of the 40th annual ACM symposium on Theory of computing .
abstract pdf
In this work we study interactive proofs for tractable languages. The (honest) prover should be efficient and run in polynomial time, or in other words a "muggle". The verifier should be superefficient and run in nearlylinear time. These proof systems can be used for delegating computation: a server can run a computation for a client and interactively prove the correctness of the result. The client can verify the result's correctness in nearlylinear time (instead of running the entire computation itself). Previously, related questions were considered in the Holographic Proof setting by Babai, Fortnow, Levin and Szegedy, in the argument setting under computational assumptions by Kilian, and in the random oracle model by Micali. Our focus, however, is on the original interactive proof model where no assumptions are made on the computational power or adaptiveness of dishonest provers. Our main technical theorem gives a public coin interactive proof for any language computable by a logspace uniform boolean circuit with depth d and input length n. The verifier runs in time (n+d) • polylog(n) and space O(log(n)), the communication complexity is d • polylog(n), and the prover runs in time poly(n). In particular, for languages computable by logspace uniform NC (circuits of polylog(n) depth), the prover is efficient, the verifier runs in time n • polylog(n) and space O(log(n)), and the communication complexity is polylog(n). Using this theorem we make progress on several questions: We show how to construct short (polylog size) computationally sound noninteractive certificates of correctness for any logspace uniform NC computation, in the publickey model. The certificates can be verified in quasilinear time and are for a designated verifier: each certificate is tailored to the verifier's public key. This result uses a recent transformation of Kalai and Raz from publiccoin interactive proofs to oneround arguments. The soundness of the certificates is based on the existence of a PIR scheme with polylog communication. Interactive proofs with publiccoin, logspace, polytime verifiers for all of P. This settles an open question regarding the expressive power of proof systems with such verifiers. Zeroknowledge interactive proofs with communication complexity that is quasilinear in the witness, length for any NP language verifiable in NC, based on the existence of oneway functions. Probabilistically checkable arguments (a model due to Kalai and Raz) of size polynomial in the witness length (rather than the instance length) for any NP language verifiable in NC, under computational assumptions.

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

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
abstract pdf
Barak et al. formalized the notion of obfuscation, and showed that there exist (contrived) classes of functions that cannot be obfuscated. In contrast, Canetti and Wee showed how to obfuscate point functions, under various complexity assumptions. Thus, it would seem possible that most programs of interest can be obfuscated even though in principle general purpose obfuscators do not exist.
We show that this is unlikely to be the case. In particular, we consider the notion of obfuscation w.r.t. auxiliary input, which corresponds to the setting where the adversary, which is given the obfuscated circuit, may have some additional a priori information. This is essentially the case of interest in any usage of obfuscation we can imagine. We prove that there exist many natural classes of functions that cannot be obfuscated w.r.t. auxiliary input, both when the auxiliary input is dependent of the function being obfuscated and even when the auxiliary input is independent of the function being obfuscated.
We also give a positive result. In particular, we show that any obfuscator for the class of point functions is also an obfuscator w.r.t. independent auxiliary input.

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).
2004

Ron Rivest, Yael Tauman Kalai
Advanced Topics in Cryptography: Lecture 18: Mixnet Voting Systems, 2004
where?
abstract pdf
In the previous lecture, we defined the notion of an electronic voting system, and specified the requirements from such a system. In particular, we required an electronic voting system to be verifiable and robust. Loosely speaking, a voting system is said to be verifiable if any individual can verify that his vote was counted. A voting system is said to be robust if there does not exist any small set of servers that can disrupt the election. The voting systems that appear in the literature can be roughly categorized into three groups: one based on mixnets, one based on homomorphic encryptions, and one based on blind signatures. In this lecture we concentrate on mixnet protocols. We describe two types of mixnet protocols: decryption mixnets and reencryption mixnets. The general structure of mixnets was illustrated in the previous lecture. They begin with an initial encryption phase E, whose outputs are posted on a bulletin board, in order to achieve verifiability. The initial encryption phase is followed by several mix phases mix1, . . . , mixk . The reason we need several of them is to achieve robustness. In decryption mixnets, the mix phases mix and partially decrypt, whereas in reencryption mixnets, the mix phases mix and reencrypt. In reencryption mixnets a final decryption phase D is added.

Yael Tauman Kalai
Advanced Topics in Cryptography: Lecture 22: Voter Verification in Mixnet Voting Systems, 2004
where?
abstract pdf
Any voting system is required to be verifiable. Namely, it is required that each voter can verify that his vote was counted correctly. On the other hand, it is also required that a voter cannot produce a receipt that allows him to prove to others how he voted. Thus, a voting system is required to be voter verifiable but not publicly verifiable. Our goal is to construct a voting system that satisfies both, seemingly contradictory, requirements.
In previous lectures, the notion of a mixnet voting system was presented. Recall that such a system consists of an initial encryption phase, followed by several mix phases and a final decryption phase. So far, we have focused on constructing verifiable mix phases. Note however, that all the mixing protocols that we considered were publicly verifiable. Namely, each mix server produced a receipt that proves the fact that a legal mix occurred.
Today, we are going to focus on constructing the encryption phase. This phase, as opposed to the mix phases, cannot be publicly verifiable, because if it were publicly verifiable then it could have been used as a receipt to a vote. Thus, this phase should be voter verifiable yet not publicly verifiable. Note that the voter is a human, and thus the encryption phase is required to be verifiable by a human. Constructing any protocol that a human can verify is very tricky, as humans, as opposed to servers, are very limited computationally.
Chaum proposed an encryption phase which is voter verifiable yet not publicly verifiable. Two main tools are used in his construction: visual cryptography and the cut and choose technique. In this lecture we present a variant of Chaum's scheme.
2003

Shafi Goldwasser and Yael Tauman
On the (In)security of the FiatShamir Paradigm
Electronic Colloquium on Computational Complexity, TR03015
abstract pdf
In 1986, Fiat and Shamir suggested a general method for transforming secure 3round publiccoin identification schemes into digital signature schemes. The significant contribution of this method is a means for designing efficient digital signatures, while hopefully achieving security against chosen message attacks. All other known constructions which achieve such security are substantially more inefficient and complicated in design.
In 1996, Pointcheval and Stern proved that the signature schemes obtained by the FiatShamir transformation are secure in the so called 'Random Oracle Model'. The question is: does the proof of the security of the FiatShamir transformation in the Random Oracle Model, imply that the transformation yields secure signature schemes in the "realworld"?
In this paper we answer this question negatively. We show that there exist secure 3round publiccoin identification schemes for which the FiatShamir methodology produces insecure digital signature schemes for any implementation of the 'Random Oracle Model' in the 'realworld' by a function ensemble.

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.
2001

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.