Paris Crypto Day

June 30 @ ENS

The second Paris Area Crypto Day will be held on 30.06.16 (Thur) at ENS.

• Amphi Rataud, ENS
• Please register (free, lunch included). Deadline 27.06.16

Program

Organizers. Michel Abdalla and Hoeteck Wee (ENS)

Acknowledgements. ERC CryptoCloud, aSCEND, and ECRYPT-NET

Abstracts

Algebraic Distinguishers against Symmetric Primitives
Anne Canteaut, INRIA

Higher-order differential attacks, introduced by Knudsen in 1994, are the first family of attacks against block ciphers which exploit some specific property of the polynomial representation of the cipher. Indeed, these attacks rely on the fact that, for all keys, the involved multivariate polynomial does not have maximal degree. This idea has then been generalized by several authors and has led to the notion of cube distinguishers, and more recently to the so-called division property. Both generalizations actually exploit the fact that some given monomials do not appear in the polynomials. In this talk, I will present some unified view of these attacks, and I will show how such algebraic properties propagate through the successive layers of iterated primitives.

Joint work with Christina Boura (Université de Versailles St Quentin)

On Memory Hardness of SCrypt
Leonid Reyzin, BU

The key derivation function scrypt (Percival, 2009) is defined as the result of n steps, where each step consists of selecting one or two previously computed values (the selection depends on the values themselves) and hashing them. It is conjectured that this function is memory-hard.

We show that indeed scrypt is maximally memory-hard in the parallel random oracle model. Specifically, we show that the product of memory and time used during the computation of scrypt must be Theta(n^2). Moreover, even if the amount of memory used fluctuates during the computation, we show that the sum of memory usage over time (a.k.a. “cumulative memory complexity” introduced by Alwen and Serbinenko in 2015) is Theta(n^2). This suggests that computation of multiple instances of scrypt in cannot be improved via amortization. Our result holds even if the adversary is allowed to make an unlimited number of parallel random oracle queries at each step.

Previous work (Alwen, Chen, Kamath, Kolmogorov, Pietrzak, Tessaro 2016) showed a lowerbounds of Omega( n^2 / log^2 n) on the memory complexity of scrypt in more restricted models, where the adversary was assumed to store only random oracle outputs or specific functions of them. Our result improves the bound quantitatively by eliminating the log^2 n factor and qualitatively by allowing arbitrary storage by the adversary.

Joint work with Joel Alwen, Jeremiah Blocki, and Krzysztof Pietrzak.

Hash Proof Systems, Old and New
Victor Shoup, NYU

This talk will be an exposition on hash proof systems and their applications. I will review the basic definitions, constructions, and applications of hash proof systems, focusing on the original application to chosen ciphertext secure public key encryption, as well as more recent applications to password authenticated key exchange.

Analysis of the Blockchain Protocol in Asynchronous Networks
Rafael Pass, Cornell

Nakamoto’s famous blockchain protocol enables achieving consensus in a so-called permissionless setting—anyone can join (or leave) the protocol execution, and the protocol instructions do not depend on the identities of the players. His ingenious protocol prevents “sybil attacks” (where an adversary spawns any number of new players) by relying on computational puzzles (a.k.a. “moderately hard functions”) introduced by Dwork and Naor (Crypto’92).

Prior works that analyze the blockchain protocol either make the simplifying assumption that network channels are fully synchronous (i.e. messages are instantly delivered without delays) (Garay et al, Eurocrypt’15) or only consider specific attacks (Nakamoto’08; Sampolinsky and Zohar, FinancialCrypt’15); additionally, as far as we know, none of them deal with players joining or leaving the protocol.

We prove that the blockchain consensus mechanism satisfies a strong forms of consistency and liveness in an asynchronous network with adversarial delays that are a-priori bounded, within a formal model allowing for adaptive corruption and spawning of new players, assuming that the computational puzzle is modeled as a random oracle. (We complement this result by showing a simple attack against the blockchain protocol in a fully asynchronous setting, showing that the “puzzle-hardness” needs to be appropriately set as a function of the maximum network delay.)

As an independent contribution, we define an abstract notion of a blockchain protocol and identify appropriate security properties of such protocols; we prove that Nakamoto’s blockchain protocol satisfies them and that these properties are sufficient for typical applications. We finally show how to use our analysis to build new blockchain protocols that overcome some of the bottlenecks in Nakamoto’s original protocol.

The analysis of Nakamoto’s blockchain is based on joint work with Lior Seeman and abhi shelat, and new blockchain protocols are based on joint work with Elaine Shi. No prior knowledge of Bitcoin or the blockchain will be assumed.