We will (a) Describe the hard average-case problems on lattices (Ajtai's subset-sum problem and Regev's learning with errors problem). Show how to achieve minicrypt from these problems. (in particular, OWF, PRG and collision-resistant hashing). (b) Describe a trapdoor structure underlying these problems (the trapdoor sampling procedure of Ajtai'99 -- as much details as time permits) Show how to achieve cryptomania using this. (in particular, trapdoor functions, efficient encryption schemes, identity-based encryption etc.)

Most of the work in the formal analysis of cryptographic schemes traditionally concentrated in abstract adversarial models that do not capture side-channel attacks. Such attacks exploit various forms of unintended information leakage, which is inherent to almost all physical implementations. In light of the prevalence of such attacks there are several attempts to model them and suggest schemes that are resistant to them. Inspired by recent side-channel attacks, especially the "cold boot attacks", Akavia, Goldwasser and Vaikuntanathan (TCC '09) suggested a framework for modeling the security of encryption schemes against a wide class of side-channel attacks, in which adversarially chosen functions of the secret key are leaked to the attacker. The functions may be chosen after the public key is known but there total length is limited. We revisit this framework and our main results are as follows:

* We present a generic construction of a public-key encryption scheme that is resilient to key leakage from any universal hash proof system. The construction does not rely on additional computational assumptions, and the resulting scheme is as efficient as the underlying proof system. Existing constructions of such proof systems imply that our construction can be based on a variety of number-theoretic assumptions, including the decisional Diffie-Hellman assumption (and its progressively weaker d-Linear variants), the quadratic residuosity assumption, and Paillier's composite residuosity assumption.

* We construct a new hash proof system based on the decisional Diffie-Hellman assumption (and its d-Linear variants), and show that the resulting scheme is resilient to any leakage of L(1-o(1)) bits. In addition, we prove that the recent scheme of Boneh et al. (CRYPTO '08), constructed to be a "circular-secure" encryption scheme, is resilient to any leakage of L(1-o(1)) bits. These two proposed schemes complement each other in terms of efficiency.

* We extend the framework of key leakage to the setting of chosen-ciphertext attacks. On the theoretical side, we prove that the Naor-Yung paradigm is applicable in this setting as well, and obtain as a corollary encryption schemes that are CCA2-secure with any leakage of L(1 -o(1)) bits. On the practical side, we prove that variants of the Cramer-Shoup cryptosystem (along the lines of our generic construction) are CCA1-secure with any leakage of L/4 bits, and CCA2-secure with any leakage of L/6 bits.

Joint work with Gil Segev.

Randomness extractors convert a dirty source of randomness into a clean source of randomness. We consider a natural extension of randomness extraction and the related notion of privacy amplification to the case of two correlated sources. Our main result is an efficient, interactive two-party protocol which extracts $m$ clean independent instances of a given joint distribution $(X,Y)$ from $n=O(m)$ dirty (or "leaky") instances of the same distribution. The classical case corresponds to $X$ and $Y$ which are an identical random bit.

This talk will present several applications of correlation extractors to cryptography with leakage and elsewhere.

(To appear, FOCS 2009; Joint work with Yuval Ishai, Eyal Kushilevitz, and Rafail Ostrovsky.)

Building on the approach of Ishai, Sahai, and Wagner (CRYPTO'03), we present a general transformation that compiles any circuit into one that provably resists well-defined classes of side-channel leakage. Our transformation works as long as the side-channel leakage is computationally bounded (i.e., cannot compute a certain function), and we rely only on a minimal leakage-proof device: one that draws random elements from a simple distribution. We thus reduce the problem of shielding arbitrary complex circuits to the problem of shielding a single simple device.

In contrast to previous works, we allow the side-channel leakage to depend on the whole state and all the wires of the circuit, and to grow unbounded over time. Even though the side-channel leakage function is assumed to be computationally bounded, the observer receiving the leakage may be powerful and adaptive.

We prove a general composition theorem that shows how to build a provably secure circuit of arbitrary complexity out of components that satisfy a simple condition. Using circuit lower bounds, we then describe a specific transformation that is unconditionally secure against all leakage functions in the complexity class AC0.

Joint work with Sebastian Faust and Leo Reyzin.

Today's computers typically run numerous processes of varying sensitivity and trustworthiness. The platform purports to separate these by means of mechanisms such as memory protection and virtualization. However, side channels arise from lower architectural layers: contention for shared resources, such as memory caches, creates inadvertent cross-talk between processes. These leakages can be exploited for stealing cryptographic keys and other sensitive information.

Two trends magnify and power and impact of these attacks: increasing parallelism (e.g., multicore and multithreading CPUs), and diversification of workload. The situation is especially worrisome where the two trends converge: cloud computing.

In this talk we will discuss architectural side channel attacks, and cache attacks in particular. We will then present an empirical study case on cloud computing. We show that it is possible to map the internal cloud infrastructure, identify where a particular target virtual machine is likely to reside, and instantiate new virtual machines that are co-resident with the target on the same physical machine. We then show that such co-residence allows attackers to exfiltrate information across virtual machine boundaries by use of side channels and covert channels.

Includes joint works with Dag Arne Osvik, Thomas Ristenpart, Stephan Savage, Adi Shamir and Hovav Shacham.

We consider what constitutes identities in cryptography. Typical examples include your name and your social-security number, or your fingerprint/iris-scan, or your address, or your (non-revoked) public-key coming from some trusted public-key infrastructure. In many situations, however, where you are defines your identity. For example, we know the role of a bank-teller behind a bullet-proof bank window not because she shows us her credentials but by merely knowing her location. In this paper, we initiate the study of cryptographic protocols where the identity (or other credentials and inputs) of a party are derived from its geographic location.

We start by considering the central task in this setting, i.e., securely verifying the position of a device. Despite much work in this area, we show that in the Vanilla (or standard) model, the above task (i.e., of secure positioning) is impossible to achieve. In light of the above impossibility result, we then turn to the Bounded Retrieval Model (a variant of the Bounded Storage Model) and formalize and construct information theoretically secure protocols for two fundamental tasks: secure positioning and position based key-exchange.

We then show that these tasks are in fact universal in this setting -- we show how we can use them to realize Secure Multi-Party Computation.

Our main contribution in this paper is threefold: to place the problem of secure positioning on a sound theoretical footing; to prove a strong impossibility result that simultaneously shows the insecurity of previous attempts at the problem; and to present positive results by showing that the bounded-retrieval framework is, in fact, one of the "right" frameworks (there may be others) to study the foundations of position-based cryptography.

This is joint work with Vipul Goyal, Ryan Moriarty and Rafail Ostrovsky and will appear at CRYPTO'09 .

Recently Standaert et al. (eprint 2009/341) propose and motivate a restricted model of leakage-resilience where the leakage functions must be "non-adaptive". They show the GGM construction of a PRF from a PRG gives a PRF which is "non-adaptively" leakage-resilient if the PRG is modelled as a random oracle (RO) and moreover the leakage-functions are not allowed to query the RO.

In this talk I will show several constructions of PRFs which are "non-adaptively" leakage-resilient in the standard model.

Thin I will shortly discuss the possibility of constructing a fully leakage-resilient PRF. Standaert et al. argue that this is impossible, but this seems too pessimistic.

We study the design of cryptographic primitives resilient to key leakage attacks, where an attacker can repeatedly and adaptively learn information about the secret key, subject only to the constraint that the overall amount of such information is bounded by some parameter $\ell$. We construct a variety of leakage-resilient public-key systems including the first known identification schemes (ID), signature schemes and authenticated key agreement protocols (AKA). Our main result is an efficient three-round leakage-resilient AKA in the Random Oracle model. This protocol ensures that session-keys are private and authentic even if (1) the adversary leaks a large fraction of the long-term secret keys of both users prior to the protocol execution and (2) the adversary completely learns the long-term secret keys after the protocol execution. In particular, our AKA protocol provides qualitatively stronger privacy guarantees than leakage-resilient public-encryption schemes (constructed in prior and concurrent works), since such schemes necessarily become insecure if the adversary can perform leakage attacks after seing a ciphertext.

Moreover, our schemes can be flexibly extended to the Bounded-Retrieval Model, allowing us to tolerate very large absolute amount of adversarial leakage $\ell$ (potentially many gigabytes of information), only by increasing the size of the secret key and without any other loss of efficiency in communication or computation. Concretely, given any leakage parameter $\ell$, security parameter $\lambda$, and any desired fraction $0< \delta \leq 1$, our schemes have the following properties:

(1) Secret key size is $\ell(1+\delta)+O(\lambda)$. In particular, the attacker can learn an approximately $(1-\delta)$ fraction of the secret key.

(2) Public key size is $O(\lambda)$, and independent of $\ell$.

(3) Communication complexity is $O(\lambda/\delta)$, and independent of $\ell$.

(4) All computation reads at most $O(\lambda/\delta^2)$ locations of the secret key, independently of $\ell$.

Lastly, we show that our schemes allow for repeated ``invisible updates'' of the secret key, allowing us to tolerate up to $\ell$ bits of leakage in between any two updates, and an unlimited amount of leakage overall. These updates require that the parties can securely store a short ``master update key'' (e.g. on a separate secure device protected against leakage), which is only used for updates and not during protocol execution. The updates are invisible in the sense that a party can update its secret key at any point in time, without modifying the public key or notifying the other users.

We consider the following problem. A "computationally weak" client C wants to compute a function F on various inputs x_1,...,x_k and delegates the computation to a "computationally powerful" server S. The client requests that S provides a proof that the value y_i=F(x_i) is correct, but the verification of such proof should take substantially less computational effort than computing F(x_i) from scratch. We present a non-interactive argument (i.e. secure against a polynomially bounded S) that y_i is indeed F(x_i) which can be verified in constant time. Our scheme also provides input privacy, i.e. C can provide S with an encrypted form of the input x_i over which to compute F. The scheme is based on Gentry's doubly-homomorphich encryption and does not use PCP techniques.

HAIL (High-Availability and Integrity Layer) is a distributed cryptographic system that allows a set of servers to prove to a client that a file dispersed across servers is intact and available for retrieval. Proofs in HAIL are efficiently computable by servers and highly compact---typically tens or hundreds of bytes, irrespective of file size. HAIL cryptographically verifies and reactively reallocates file shares when corruption is detected. It is robust against an active, mobile adversary that may progressively corrupt the full set of servers. HAIL improves on the security and efficiency of existing tools, like Proofs of Retrievability (PORs) deployed on individual servers.

We give general constructions of Lossy Encryption from rerandomizable encryption, and from statistical OT. Applying the recent results of Bellare, Hofheinz and Yilek, this gives efficient, general constructions of Selective Opening secure encryption from a wide variety of primitives, including Rerandomizable encryption, Homomorphic Encryption, PIR and statistical OT.

We extend the definition of Selective Opening Security, to Selective Opening Security against a Chosen Ciphertext attack in both the indistinguishability-based model, and give a construction that satisfies this definition based on Lossy-Trapdoor Functions.

We extend the definition of Selective Opening Security, to Selective Opening Security against a Chosen Ciphertext attack in both the simulation-based model, and give a construction that satisfies this definition based on statistical NIZKs.

We describe a public-key encryption system that remains secure even encrypting messages that depend on the secret keys in use. In particular, it remains secure under a "key cycle" usage, where we have a cycle of public/secret key-pairs $(\PK_i,\SK_i)$ for $i=1,\ldots,n$, and we encrypt each $\SK_i$ under $\PK_{(i \bmod n)+1}$. Such usage scenarios sometimes arise in key-management systems and in the context of anonymous credential systems. Also, security against key cycles plays a role when relating "axiomatic security" of protocols that use encryption to the "computational security" of concrete instantiations of these protocols.

The existence of encryption systems that are secure in the presence of key cycles was wide open until now: on the one hand we had no constructions that provably meet this notion of security (except by relying on the random-oracle heuristic); on the other hand we had no examples of secure encryption systems that become demonstrably insecure in the presence of key-cycles of length greater than one.

Here we construct an encryption system that is circular-secure against chosen-plaintext attacks under the Decision Diffie-Hellman assumption (without relying on random oracles). Our proof of security holds even if the adversary obtains an encryption clique, that is, encryptions of $\SK_i$ under $\PK_j$ for all $1 \leq i,j \leq n$. We also construct a circular counterexample: a one-way secure encryption scheme that breaks completely if an encryption cycle (of any size) is published.

Joint work with Dan Boneh, Mike Hamburg and Rafail Ostrovsky.