Paris Crypto Day (Part I)

Following the tradition of organizing Crypto Days in New York, Boston, DC, Tel Aviv and Bay areas, the crypto community of Paris decided to start organizing similar events. The first one¹ took place on 16th of February 2016, was hosted by ENS Paris and consisted of six talks given by senior researchers and PhD students.

The morning session was opened by Antoine Joux, his presentation surveying the key historical and recent approaches to solving the Discrete Logarithm Problem (DLP), but also emphasizing the progress that has been made in considering this problem over small characteristic finite fields. The motivation for such a study resides in the large number of schemes based on the DLP (e.g. the Diffie-Hellman key exchange). In short, the DLP problem is to find $x$ such that $g^x=h$, where $g, h$ and a description of a group $G$ are given as input. Here, the underlying group $G$ is a multiplicative group (e.g. the group of invertible elements in a finite field or the group of points on an elliptic curve).

The audience was guided through the following general and index-calculus methods of solving the DLP:

1. Pohlig–Hellman²
2. Baby Step/Giant Step²
3. Pollard-Rho
4. Hellman-Reyneri
5. Coppersmith's algorithm

before the quasi-polynomial heuristic for finite fields of small characteristics $F_{q^k}$ was described. For the case when $q$ is of size at most comparable with $k$ the time complexity of the heuristic is $q^{O(log(q))}$. More details about the techniques used can be accessed here. The result has important implications for cryptographic schemes that are based on pairings where the fields have small characteristics. It will be interesting to see if this major breakthrough in DLP will have implications in the problem of integer factorization.

Pierrick Meaux - PhD student at ENS Paris - brought a different topic to our attention during his morning session presentation. The subject of the talk was the EuroCrypt 2016 paper Pierrick worked on:

Towards Stream Ciphers for Efficient FHE with Low-Noise Ciphertexts (a joint work with A. Journault, F.-X. Standaert, C. Carlet)

One of the most interesting aspects of this work is that it combines the (mostly) theoretical paradigm of fully homomorphic encryption (FHE) with concrete symmetric constructions, therefore aiming to bring FHE in the practical realm. The main result was a new symmetric construction designed to allow homomorphic operations on ciphertexts. The FHE paradigm is motivated by the ability to outsource storage and processing of encrypted data to a more computationally powerful third party. The first generation FHE systems lack efficiency. An inherent goal is to make such constructions time and memory efficient. A comparison between the previous symmetric FHE constructs and the current work was given (summarized in the following table):

Algorithm	Reference	Multiplicative depth
AES-128	[GHS12]	40
SIMON-64/128	[LN14]	44
Prince	[DSE+14]	24
Kreyvium-12	[CCF+15]	12
LowMC-12	[ARS+15]	12
FLIP	presented work	4

The cipher is based on a new framework, called FLIP - a Filter Permutator. Three main parts are used: a PRNG, a Permutation Generator and a Filtering function. The proposed construction instantiates the PRNG from AES-128; it uses the Knuth Shuffle as a Permutation Generator and introduces a new filtering function. The team built the filtering function having in mind minimality and analysability of such a filtering function, and is built from linear, quadratic and triangular functions.

Another blog entry will follow soon and will cover the afternoon talks!

Notes

^{1. Paris Crypto Day Website↩}

^{2. A link to a talk by Antoine Joux, CryptoAction School on Cryptographic Attacks, Porto, 2014↩}