# Journée crypto-complexité

ENS## Bummer! Sales have ended.

Unfortunately, tickets for this event are no longer on sale.

## Event Details

Journée Crypto-Complexité

LIAFA-LIENS

21 juin 2012

Amphithéâtre Rataud/Evariste Galois

Niveau PB, Nouvel Immeuble Rataud, ENS, 45 rue d’Ulm

Program

9h15: Welcome

9h30 - 10h15 – Yevgeniy Dodis

10h15 - 10h45 – David Pointcheval

10h45 - 11h00 – break

11h00 - 12h00 – Vadim Lyubashevsky

12h - 13h30 – Lunch (ENS cafeteria)

13h30 - 14h30 – Iordanis Kerenidis

14h30 - 15h00 – Adi Rosen

15h00 - 15h30 – Sophie Laplante

15h30 - 16h00 – break

16h00 - 16h30 – Michel Abdalla

16h30 - 17h00 – David Xiao

17h00 - 17h30 – Duong Hieu Phan

Talk abstracts

* Yevgeniy Dodis

Title: Overcoming Weak Expectations (45 mn)

Recently, there has been renewed interest in basing cryptographic primitives on weak secrets, where the only information about the secret is some non-trivial amount of (min-)entropy. From a formal point of view, such results require to upper bound the expectation of some function f(X), where X is a weak source in question. We show an elementary inequality which essentially upper bounds such "weak expectation" by two terms, the first of which is *independent* of f, while the second only depends on the "variance" of f under *uniform* distribution. Quite remarkably, as relatively simple corollaries of this elementary inequality, we obtain some "unexpected" results, in several cases noticeably simplifying/improving prior techniques for the same problem. Examples include non-malleable extractors, leakage-resilient symmetric encryption, seed-dependent condensers and improved entropy loss for the leftover hash lemma.

* David Pointcheval (30 mn)

Title: Smooth Projective Hash Functions and Applications

In this talk, we review the Smooth Projective Hash Function Systems, initially proposed by Cramer and Shoup in 2002, and later revisited by Gennaro and Lindell in 2003. We first show how they can be used to replace some zero-knowledge proofs, with additional privacy properties. Then, we how vast is the family of languages that can be addressed by these systems. Eventually, we illustrate with some concrete applications.

This covers several works done, or in progress, with Michel Abdalla, Fabrice Ben Hamouda, Olivier Blazy, Céline Chevalier, and Damien Vergnaud

* Vadim Lyubashevsky (1 hour)

Title: Fully Homomorphic Encryption

In this talk, I will present the basics of ideal lattices and show how they are connected to the NTRU cryptosystem. Then I will proceed to show how the NTRU cryptosystem can be easily modified into a "somewhat-homomorphic" scheme that can support additions and a limited number of multiplication operations. Finally, I will describe Gentry's bootsrapping technique that converts certain somewhat-homomorphic schemes into fully-homomorphic ones, and briefly hint at how the described NTRU scheme can be modified in order to support bootsrapping.

* Iordanis Kerenidis (1 hour)

Title: Introduction to quantum cryptography

We will describe some of the main results in quantum cryptography, including protocols for Key Distribution, Coin Flipping and Bit Commitment. All the necessary background in quantum information will be given in the talk, so no prior knowledge is expected. We will conclude with some main open problems in the area.

* Adi Rosen (30 mn)

Title: Randomness in Private Computation - some (older) results and some open problems

We consider a setting of information-theoretic private computation. $n$ players, each holding a secret input $x_i$, cooperate using a protocol in order to compute, for some function $f$, the value of $f(x_1,\ldots,x_n)$. The protocol is private if no player learns anything except what is implied by its own input and the value of the function.

We are specifically interested in the amount of randomness required for such computations. We review some (older) results relating the amount of randomness used by the players, to various complexity measures of the protocol (such as the number of rounds of communication) and various complexity measures of the computed function (such as its circuit size, or the sensitivity of the function). We then discuss a number of open problems related to randomness in private computation.

* Sophie Laplante (30 mn)

Title: Merkle puzzles in a quantum world

Ralph Merkle proposed a scheme for secure communications over insecure channels in which legitimate communicating parties make N queries to a random source, but an eavesdropper provably cannot guess the key they agree upon without making N^2 queries. This scheme is easily broken in N queries if the adversary's queries are quantum. We give two new protocols. The first requires one of the players to be quantum, but breaking it requires N^{5/3} queries. In our second scheme the players are classical, yet it cannot be broken by a quantum eavesdropper using fewer than N^{7/6} queries.

* Michel Abdalla (30 mn)

Title: From Selective to Full Security: Semi-Generic Transformations in the Standard Model

In this talk, I will present an efficient, standard model, semi-generic transformation of selective-secure (Hierarchical) Identity-Based Encryption schemes into fully secure ones. The main step is a procedure that uses admissible hash functions (whose existence is implied by collision-resistant hash functions) to convert any selective-secure wildcarded identity-based encryption (WIBE) scheme into a fully secure (H)IBE scheme. Since building a selective-secure WIBE, especially with a selective-secure HIBE already in hand, is usually much less involved than directly building a fully secure HIBE, this transform already significantly simplifies the latter task. Furthermore, I will show that if a selective-secure HIBE scheme satisfies a particular security notion, then it can be generically transformed into a selective-secure WIBE. Interestingly, several current schemes already fit this new definition, while some others that do not obviously satisfy it can still be easily modified into a selective-secure WIBE.

This is joint work with Dario Fiore and Vadim Lyubashevsky

* David Xiao (30 mn)

Title: Basing cryptography on SZK?

Constructing cryptographic primitives based on robust complexity assumptions is a central task of theoretical cryptography. Diffie and Hellman proposed early on the goal of basing cryptography on NP-hard problems, but subsequent research has shown that this goal is unlikely to be attained using standard techniques. In this talk we explore the possibility of basing cryptography on another complexity class: SZK, the class of languages that have statistical zero knowledge proofs. SZK contains many interesting problems such as Graph Non-isomorphism and Quadratic Residuosity, and it has relatively natural complete problems. Furthermore, it is not susceptible to subexponential or quantum algorithms. We will see in several other ways that it is a good candidate to serve as a basis for cryptography, and we speculate on some approaches that may be worth pursuing.

* Duong Hieu Phan (30 mn)

Title: A Code for Trace & Revoke Systems

Broadcast Encryption enables a center to broadcast digital information to a specific set of subscribers for decrypting contents (we found it in many real-world applications such as Pay-TV, satellite radio, and the distribution of copyrighted materials). Two natural requirements arise in such settings. Firstly, the broadcast system should be able to revoke the receiving rights of an arbitrary subset of subscribers, either because they have unsubscribed from the service or have violated some rules. Secondly, as users might collude to build and distribute pirate decoders, it is desirable for the system to be able to trace at least one traitor by examining the pirate decoder. Among the combinatorial schemes in the literature, those based on codes (collusion-secure codes, IPP codes) support black-box tracing capacity but not revocation, while those based on ESS (exclusive set systems) mainly support revocation.

In this work, we address the problem of designing an efficient broadcast encryption scheme which is capable of simultaneously revoking users and tracing traitors. We first introduce a code framework that generalizes both IPP codes and ESS. We then propose a construction for a class of k-conjunction code that fits our framework and finally, we combine the proposed code with a k-out of -n secret sharing to achieve a black-box trace and revoke system.

Joint work with Hung Q. Ngo (SUNY at Buffalo) and David Pointcheval (ENS).