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.
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.
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.
contact details
Microsoft Research, Office 14063
One Memorial Drive
Cambridge, MA 02142
One Memorial Drive
Cambridge, MA 02142
Phone: (857) 453-6322
Fax: (425) 93MSFAX (be sure to specify my name on the cover sheet)
Fax: (425) 93MSFAX (be sure to specify my name on the cover sheet)
My main research interests are: Security & Privacy, Algorithms & Theory, Scientific Computing.
Lecture
-
Yael Tauman Kalai
Cryptography with Leakey Keys
"Women in Theory" workshop; Center for Computational Intractability, Princeton University, June 2010
video
There is no abstract available for this presentation.
Publications
2010
-
Zvika Brakerski, Yael Tauman Kalai, Jonathan Katz, Vinod Vaikuntanathan
Overcoming the Hole in the Bucket: Public-Key Cryptography Resilient to Continual Memory Leakage
October 2010: IEEE 51st Annual Symposium on Foundations of Computer Science
abstract pdf
-
Shafi Goldwasser,Yael Tauman Kalai, Chris Peikert and Vinod Vaikuntanathan
Robustness of the Learning with Errors Assumption
Innovations in Computer Science, 2010.
abstract pdf
-
Kai-Min Chung, Yael Tauman Kalai, Salil Vadhan
Improved Delegation of Computation Using Fully Homomorphic Encryption
Advances in Cryptology - CRYPTO 2010; Lecture Notes in Computer Science, 2010, Volume 6223/2010, 483-501, DOI: 10.1007/978-3-642-14623-7_26.
abstract pdf
-
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
-
Yevgeniy Dodis, Shafi Goldwasser, Yael Tauman Kalai, Chris Peikert and Vinod Vaikuntanathan
Public-Key Encryption Schemes with Auxiliary Inputs
Theory of Cryptography: Lecture Notes in Computer Science, 2010, Volume 5978/2010, 361-381, DOI: 10.1007/978-3-642-11799-2_22.
abstract pdf
-
Ran Canetti, Yael Tauman Kalai, Mayank Varia, Daniel Wichs
On Symmetric Encryption and Point Obfuscation
Theory of Cryptography: Lecture Notes in Computer Science, 2010, Volume 5978/2010, 52-71, DOI: 10.1007/978-3-642-11799-2_4.
abstract pdf
- The recent impossibility result for KDM security of Haitner and Holenstein (TCC '09) carries over to MBPF obfuscators.
- The Canetti-Dakdouk 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 super-logarithmic min-entropy (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.
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" [Micali-Reyzin, TCC04]).
Specifically, under the decisional linear assumption on bilinear groups (which allows for a leakage rate of (½-o(1))) or the symmetric external Diffie-Hellman assumption (which allows for a leakage rate of (½ - o(1))), we achieve the above for public key encryption, identity-based encryption, and signature schemes. Prior to this work, it was not known how to construct public-key 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.
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" [Micali-Reyzin, TCC04]).
Specifically, under the decisional linear assumption on bilinear groups (which allows for a leakage rate of (½-o(1))) or the symmetric external Diffie-Hellman assumption (which allows for a leakage rate of (½ - o(1))), we achieve the above for public key encryption, identity-based encryption, and signature schemes. Prior to this work, it was not known how to construct public-key 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.
Starting with the work of Ishai-Sahai-Wagner and Micali-Reyzin, a new goal has been set within the theory of cryptography community, to design cryptographic primitives that are secure against large classes of side-channel 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 hard-to-invert auxiliary inputs. We exhibit various applications of this result.
1. Under the standard LWE assumption, we construct a symmetric-key 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 hard-to-invert auxiliary inputs).
2. Under the standard LWE assumption, we construct a (weak) obfuscator for the class of point functions with multi-bit 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 symmetric-key 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.
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 hard-to-invert auxiliary inputs. We exhibit various applications of this result.
1. Under the standard LWE assumption, we construct a symmetric-key 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 hard-to-invert auxiliary inputs).
2. Under the standard LWE assumption, we construct a (weak) obfuscator for the class of point functions with multi-bit 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 symmetric-key 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.
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 4-message (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 re-run the offline construction after errors are detected (assuming errors are not too frequent).
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 4-message (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 re-run the offline construction after errors are detected (assuming errors are not too frequent).
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 a-priori-message 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 Diffie-Hellman (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 Cash-Hofheinz-Kiltz-Peikert; The second is based on the d-linear assumption over bilinear groups.
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 a-priori-message 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 Diffie-Hellman (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 Cash-Hofheinz-Kiltz-Peikert; The second is based on the d-linear assumption over bilinear groups.
We construct public-key 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 information-theoretically). Our schemes are based on the decisional Diffie-Hellman (DDH) and the Learning with Errors (LWE) problems.
As an independent technical contribution, we extend the Goldreich-Levin theorem to provide a hard-core (pseudorandom) value over large fields.
As an independent technical contribution, we extend the Goldreich-Levin theorem to provide a hard-core (pseudorandom) value over large fields.
We show tight connections between several cryptographic primitives, namely encryption with weakly random keys, encryption with key-dependent messages (KDM), and obfuscation of point functions with multi-bit output (which we call multi-bit 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 weakly-random keys and key-dependent 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:
Our results can be interpreted as indicating that MBPF obfuscators imply a very strong form of encryption that simultaneously achieves security for weakly-random keys and key-dependent 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:
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
-
Zvika Brakerski, Shafi Goldwasser, Yael Tauman Kalai
Black-Box Circular-Secure 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, 143-159, DOI: 10.1007/978-3-642-03356-8_9.
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 min-entropy left. In particular, we deal with situations where f(sk) information-theoretically determines the entire secret key sk.
As our main result, we construct CPA/CCA secure symmetric encryption schemes that remain secure with exponentially hard-to-invert auxiliary input. We give several applications of such schemes.
* We construct an average-case obfuscator for the class of point functions, which remains secure with exponentially hard-to-invert auxiliary input, and is reusable.
* We construct a reusable and robust extractor that remains secure with exponentially hard-to-invert auxiliary input. Our results rely on a new cryptographic assumption, Learning Subspace-with-Noise (LSN), which is related to the well known Learning Parity-with-Noise (LPN) assumption.
As our main result, we construct CPA/CCA secure symmetric encryption schemes that remain secure with exponentially hard-to-invert auxiliary input. We give several applications of such schemes.
* We construct an average-case obfuscator for the class of point functions, which remains secure with exponentially hard-to-invert auxiliary input, and is reusable.
* We construct a reusable and robust extractor that remains secure with exponentially hard-to-invert auxiliary input. Our results rely on a new cryptographic assumption, Learning Subspace-with-Noise (LSN), which is related to the well known Learning Parity-with-Noise (LPN) assumption.
2008
-
Yael Tauman Kalai, and Ran Raz
Interactive PCP
Automata, Languages and Programming; Lecture Notes in Computer Science, 2008, Volume 5126/2008, 536-547, DOI: 10.1007/978-3-540-70583-3_44.
abstract pdf
-
Shafi Goldwasser, Yael Tauman Kalai and Guy N. Rothblum
One-Time Programs
Advances in Cryptology - CRYPTO 2008: Lecture Notes in Computer Science, 2008, Volume 5157/2008, 39-56, DOI: 10.1007/978-3-540-85174-5_3.
abstract pdf
-
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
-
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
In this work, we introduce one-time programs, a new computational paradigm geared towards security applications. A one-time 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 one-time program is like a black box function that may be evaluated once and then "self destructs". This also extends to k-time programs, which are like black box functions that can be evaluated k times and then self destruct.
One-time 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 one-time programs go well beyond those of obfuscation, since one-time programs can only be executed once (or more generally, a limited number of times) while obfuscated programs have no such bounds. For example, one-time 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 one-time computing opens new avenues for conceptual research. In this work we explore one such avenue, presenting the new concept of "one-time 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 one-time program. We also show how this memory device can be used to construct one-time proofs. Specifically, we show how to use this device to efficiently convert a classical witness for any NP statement, into "one-time proof" for that statement.
One-time 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 one-time programs go well beyond those of obfuscation, since one-time programs can only be executed once (or more generally, a limited number of times) while obfuscated programs have no such bounds. For example, one-time 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 one-time computing opens new avenues for conceptual research. In this work we explore one such avenue, presenting the new concept of "one-time 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 one-time program. We also show how this memory device can be used to construct one-time proofs. Specifically, we show how to use this device to efficiently convert a classical witness for any NP statement, into "one-time proof" for that statement.
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 super-efficient and run in nearly-linear 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 nearly-linear 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 log-space 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 log-space 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 non-interactive certificates of correctness for any log-space uniform NC computation, in the public-key model. The certificates can be verified in quasi-linear 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 public-coin interactive proofs to one-round arguments. The soundness of the certificates is based on the existence of a PIR scheme with polylog communication. Interactive proofs with public-coin, log-space, poly-time verifiers for all of P. This settles an open question regarding the expressive power of proof systems with such verifiers. Zero-knowledge interactive proofs with communication complexity that is quasi-linear in the witness, length for any NP language verifiable in NC, based on the existence of one-way 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.
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, 431-492, DOI: 10.1007/s00145-007-0567-1.
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 stand-alone 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 self-composition (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 self-composition. 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
-
Yael Tauman Kalai, Ran Raz
Succinct Non-Interactive Zero-Knowledge Proofs with Preprocessing for LOGSNP
Electronic Colloquium on Computational Complexity, Report No. 31, 2007
abstract pdf
-
Yael Tauman Kalai
Attacks on the Fiat-Shamir Paradigm and Program Obfuscation
PhD thesis, 2006
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 signer-ambiguous, 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).
2005
-
Yael Tauman Kalai
Smooth Projective Hashing and Two-Message Oblivious Transfer
In EUROCRYPT 2005, Springer-Verlag (LNCS 3494)
abstract pdf
-
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
-
Yael Tauman Kalai, Yehuda Lindell, Manoj Prabhakaran
Concurrent General Composition of Secure Protocols in the Timing Model
STOC '05 Proceedings of the thirty-seventh annual ACM symposium on Theory of computing.
abstract pdf ps
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 (2002). Our framework is actually an abstraction of the two-message 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'th-Residuosity 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 two-message 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.
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 two-message 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.
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.
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.
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 stand-alone 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
-
Yael Tauman Kalai
Advanced Topics in Cryptography: Lecture 22: Voter Verification in Mix-net 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 mix-nets, one based on homomorphic encryptions, and one based on blind signatures. In this lecture we concentrate on mix-net protocols. We describe two types of mix-net protocols: decryption mix-nets and re-encryption mix-nets. The general structure of mix-nets 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 mix-nets, the mix phases mix and partially decrypt, whereas in re-encryption mixÂnets, the mix phases mix and re-encrypt. In re-encryption mixÂnets a final decryption phase D is added.
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 mix-net 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.
In previous lectures, the notion of a mix-net 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 Fiat-Shamir Paradigm
Electronic Colloquium on Computational Complexity, TR03-015
abstract pdf
-
Shafi Goldwasser and Yael Tauman
On the (In)security of the Fiat-Shamir Paradigm
Proceedings of the 44th Annual IEEE Symposium on Foundations of Computer Science
abstract pdf
In 1986, Fiat and Shamir suggested a general method for transforming secure 3-round public-coin 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 Fiat-Shamir transformation are secure in the so called 'Random Oracle Model'. The question is: does the proof of the security of the Fiat-Shamir transformation in the Random Oracle Model, imply that the transformation yields secure signature schemes in the "real-world"?
In this paper we answer this question negatively. We show that there exist secure 3-round public-coin identification schemes for which the Fiat-Shamir methodology produces insecure digital signature schemes for any implementation of the 'Random Oracle Model' in the 'real-world' by a function ensemble.
In 1996, Pointcheval and Stern proved that the signature schemes obtained by the Fiat-Shamir transformation are secure in the so called 'Random Oracle Model'. The question is: does the proof of the security of the Fiat-Shamir transformation in the Random Oracle Model, imply that the transformation yields secure signature schemes in the "real-world"?
In this paper we answer this question negatively. We show that there exist secure 3-round public-coin identification schemes for which the Fiat-Shamir methodology produces insecure digital signature schemes for any implementation of the 'Random Oracle Model' in the 'real-world' by a function ensemble.
In 1986, Fiat and Shamir proposed a general method for transforming secure 3-round public-coin identification schemes into digital signature schemes. The idea of the trans-formation 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 Fiat-Shamir 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 Fiat-Shamir methodology secure?
In this paper, we answer this question negatively. We show that there exist secure 3-round public-coin identification schemes for which the Fiat-Shamir 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 Fiat-Shamir 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 black-box access to a program, this time in the context of digital signatures.
The Fiat-Shamir 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 Fiat-Shamir methodology secure?
In this paper, we answer this question negatively. We show that there exist secure 3-round public-coin identification schemes for which the Fiat-Shamir 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 Fiat-Shamir 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 black-box 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
-
Adi Shamirand Yael Tauman
Improved online/offline signature schemes
Advances in Cryptology - CRYPTO 2001: Lecture Notes in Computer Science, 2001, Volume 2139/2001, 355-367, DOI: 10.1007/3-540-44647-8_21.
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 signer-ambiguous, 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.
The notion of on-line/off-line signature schemes was introduced in 1990 by Even, Goldreich and Micali. They presented a general method for converting any signature scheme into an on-line/off-line 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 hash-sign-switch, which can convert any signature scheme into a highly efficient on-line/off-line signature scheme: In its recommended implementation, the on-line 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 off-line 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.