# Cryptolux Seminars

## Contents

## January 20th, 2016

**Provable Security for Cryptocurrencies**

by '**Andrew Miller** (*Universities of Maryland and Cornell*)

ABSTRACT: The recent success of Bitcoin and cryptocurrencies have whet appetites (of financial institutions, for example) for ambitious crypto-infused technology. It even seems plausible that these decentralized systems will become reliable fixtures of society.

This optimistic view is justified partly due to the success of cryptography itself, both as a discipline of rigorous validation and as a powerful toolbox for protocol designers. But cryptographic tools are notoriously difficult to use correctly, and actually very little of the “cryptocurrency design” has undergone any such rigorous analysis. Can cryptographic methods rise to this challenge?

In this talk I’ll explain two ways of using provable security (aka, “reductionism”!) to understand and improve cryptocurrencies.

First, provable security offers a principled way to explore broad new design spaces. I’ll talk about Permacoin and Nonoutsourceable puzzles, two designs for alternative mining puzzles that have various useful side effects while still providing the basic guarantees needed for the backbone of a cryptocurrency.

Second, provable security and programming language design go hand-in-hand. By encapsulating cryptographic primitives within a provably secure compiler, even non-expert programmers can generate correct protocols just by writing a specification in a familiar language. I’ll describe Hawk, a new language for privacy-preserving smart contracts that puts the power of zero knowledge proofs in the hands of blockchain application developers.

http://oblivm.com/hawk/ http://dl.acm.org/citation.cfm?id=2813621

## June 11th, 2015

**"How to Reach Unreachable Computers"**

by **Prof.Adi Shamir** (*Weizmann Institute of Science, Rehovot, Israel*)

ABSTRACT: Highly sensitive computers are usually unreachable in the sense that they are located in isolated facilities surrounded by armed guards, and are not connected to the internet or to any other external communication networks. In addition, they are protected from standard side channel attacks by receiving their electricity from local generators and by being surrounding by Faraday cages to prevent any leakage of electromagnetic radiation. The holy grail of cyber attacks is to find a way to reach such unreachable computers. In this talk, I will describe some new experimentally verified techniques which can be used by an outside attacker to establish long range (>1 kilometer) bidirectional communication with such an airgapped computer system that contains only standard untampered hardware components. It is a joint work with Yuval Elovici and Moti Guri.

## October 10th, 2014

**"High Parallel Complexity Graphs and Memory-Hard Functions"**

by **Joel Alwen** (*IST, Vienna, Austria*)

ABSTRACT: Motivated by the growing prevalence ASICs (and other highly parallel computational environments with non-trivial memory costs) we introduce a very natural definition of "memory-hardness": that is a measure of the amount of runtime memory needed to compute a particular function. To motivate it, we first demonstrate a significant shortcoming of a similar definition by Percival. In particular we show how the new definition allows for much stronger bounds on the Area/Time-complexity of any (parallel) circuit computing *many* copies of a given function; a common task in solving most proof-of-work protocols and when brute-forcing password files. The Area/Time-complexity of a circuit is an common measure, in the VLSI literature, of the efficiency of the circuit.

Motivated by the above security applications we turn to constructing functions with as high memory-hardness as possible (in a variant of the random oracle model). As a key tool we use a new pebbling game over directed acyclic graphs (DAGs). In particular we introduce a new complexity notion, called "cumulative complexity (CC)", for DAGs in terms of the pebbling game. Then, given a DAG G, we provide a transformation to a function f_G in the ROM and prove a lower-bound on the memory-hardness of f_G in terms of the CC of G.

This reduces the problem of finding functions with large memory requirements to finding a DAG with high CC. A simple observation shows that any DAG with N nodes can have CC no greater than O(N^2). We provide a family of graphs (one per possible number of nodes) such that the graph of size N has CC of at least Omega(N^2). That is, each graphs has optimally high CC, within a polylogarithmic factor, for any graph of equal size.

## December 17th, 2013

**"Structural Evaluation of AES and Chosen-Key Distinguisher of 9-round AES-128"**

by **Jeremy Jean** (*École Normale Supérieure, Paris, France*)

ABSTRACT: While the symmetric-key cryptography community has now a good experience on how to build a secure and efficient fixed permutation, it remains an open problem how to design a key-schedule for block ciphers, as shown by the numerous candidates broken in the related-key model or in a hash function setting. Provable security against differential and linear cryptanalysis in the related-key scenario is an important step towards a better understanding of its construction.

Using a structural analysis, we show that the full AES-128 cannot be proven secure unless the exact coefficients of the MDS matrix and the S-Box differential properties are taken into account since its structure is vulnerable to a related-key differential attack. We then exhibit a chosen-key distinguisher for AES-128 reduced to 9 rounds, which solves an open problem of the symmetric community. We obtain these results by revisiting algorithmic theory and graph-based ideas to compute all the best differential characteristics in SPN ciphers, with a special focus on AES-like ciphers subject to related-keys. We use a variant of Dijkstra's algorithm to efficiently find the most efficient related-key attacks on SPN ciphers with an algorithm linear in the number of rounds.

The content of this talk is a joint work with Pierre-Alain Fouque and Thomas Peyrin, and appeared in a CRYPTO 2013 paper.

## November 22th, 2013

**"Small Private Circuits"**

by **Alexey Pospelov** (*Yandex, Russia*)

ABSTRACT: "It is well known that implementing cryptographic algorithms on physical devices such as PCs, smart-cards or RFIDs is a challenging task, because in general such devices leak information through power consumption and electro-magnetic radiations, computer viruses, Internet worms and malware, and such information leakage can be exploited by an attacker in what is usually called a side-channel attack. It is well known that those attacks are extremely powerful and can lead to a complete break of the system. Ad-hoc arguments usually work as temporary solutions and result in insecure systems. Instead of relying on ad-hoc security patches, a better approach consists in working in the framework of provable security.

Ishai, Sahai, and Wagner initiated in 2003 the theoretical study of securing circuits against an adversary who can probe its wires. They presented a universal way of transforming an arbitrary boolean circuit of size s into a circuit of size O(s · t^2), with perfect security against an adversary who can read up to t wires of the circuit. We present a new algebraic approach for securing circuits against such an adversary with circuit size O(s · t · polylog(t)), and show some partial results on meeting the original privacy requirements. Our solution works for arithmetic circuits over arbitrary fields of positive characteristic. The potential improvements from quadratic to quasilinear complexity (in t) come from using the DFT instead of naive multiplication. The limitations on the privacy requirements depend on the ability to build a randomized circuit for the FFT which is secure against the t-limited adversary.

This is a joint work with Markus Bläser (Saarland University) and Jean-Sebastien Coron (University of Luxembourg).""

## September 12th, 2013

**"Polynomial Equivalence Problems"**

by **Charles Bouillaguet** (*University of Lille-1, France*).

ABSTRACT: Two linear functions A and B are said to be equivalent if there exist two linear bijections S and T such that B = T o A o S. Given two matrices representing A and B, checking whether they are equivalent is computationally easy, and additionally retrieving possible S and T is not much harder. However, the game changes completely as soon we drop the requirement that A and B shall be linear. Even when we restrict A and B to be quadratic functions, the resulting computational problems (Quadratic Maps Linear Equivalence, or QMLE) is not easy. The hardness of this particular problem has been invoked to provide security guarantees for some multivariate public-key schemes. It has also been claimed to be harder than graph isomorphism, for which no polynomial-time worst-case algorthim is known. As far as QMLE is concerned, only exponential algorithms with bad (or unknown) complexity are know to this day. In this talk, I will discuss that some subcases of QMLE are easy while some others are hard, and I will present the algorithms I designed to attack their hardness.

## June 28th, 2013

**"Low cost SCA countermeasures: a research proposal"**

by **Oscar Delgado-Mohatar** (*CriptoLab, Polytechnical University of Madrid*)

ABSTRACT: I will begin presenting some of my previous work on lightweight cryptographic primitives, both of encryption and authentication. The first one consists of an extension of the shrinking generator, translated from the binary world to Galois fields more suitable for modern processors registers size. On the other hand, the authentication protocol developed was specifically designed to be energy efficient and have a very small memory footprint. Both designs were implemented in a Arduino platform (Atmel 168). In the second part, I will discuss about the main threat to real sensor networks systems: physical intrusion and access to secret key material. It is widely considered that sensor networks nodes cannot be made tamper-proof because of cost, but both symmetric and asymmetric cryptographic primitives need to keep secrets in any case. Many protocols that do not need this kind of hardware have been proposed, but truth is that all of them remain vulnerable, in different degree, to physical intrusion. For this reason, design and develop new low-cost countermeasures, both hardware and software, is a must. Ideally these countermeasures should be adaptive, through tuneable parameters, in order to obtain different versions with different economic cost (for hardware versions), computational complexity or memory and CPU usage. This way, each of these versions could be implemented in devices with different computational power (RFID, motes,...) sharing just one original design. Finally, I will propose to develop a simple cryptographic chip, which collects some of these new (and the best of the existing) countermeasures. This design would be very useful both for academic and industry worlds.