Paris Crypto Day

Sep 6 @ INRIA

The third Paris Area Crypto Day will be held on 06.09.16 (Tue) at INRIA.

• Salle JL Lions, INRIA
• Please register (free, lunch included). Deadline 01.09.2016

Program

Abstracts

Directions in Lattice Cryptography
Vadim Lyubashevsky (IBM Zurich)

In the past 20 years, lattice cryptography went from a purely theoretical research area to actually being implemented inside of Google Chrome today. I will describe the state-of-the-art results in practical lattice cryptography and sketch out what I consider to be interesting directions for further research.

HE Circuit Privacy Almost For Free
Michele Minelli (ENS)

Circuit privacy is an important property for many applications of fully homomorphic encryption. Prior approaches for achieving circuit privacy rely on superpolynomial noise flooding or on bootstrapping. In this work, we present a conceptually different approach to circuit privacy based on a novel characterization of the noise distribution. In particular, we show that a variant of the GSW FHE for branching programs already achieves circuit privacy; this immediately yields a circuit-private FHE for NC1 circuits under the standard LWE assumption with polynomial modulus-to-noise ratio. Our analysis relies on a variant of the discrete Gaussian leftover hash lemma which states that $e^t G^{−1}(v)$ + small noise does not depend on $v$. We believe that this result is of independent interest.

Joint work with Florian Bourse, Rafaël Del Pino and Hoeteck Wee

Cryptanalysis of the FLIP Family of Stream Ciphers
Virginie Lallemand (INRIA)

At Eurocrypt 2016, Méaux et al. proposed FLIP, a new family of stream ciphers intended for use in Fully Homomorphic Encryption systems. Unlike its competitors which either have a low initial noise that grows at each successive encryption, or a high constant noise, the FLIP family of ciphers achieves a low constant noise thanks to a new construction called filter permutator. In this paper, we present an attack on the early version of FLIP that exploits the structure of the filter function and the constant internal state of the cipher. Applying this attack to the two instantiations proposed by Méaux et al. allows for a key recovery in $2^{54}$ basic operations (resp. $2^{68}$), compared to the claimed security of $2^{80}$ (resp. $2^{128}$).

Joint work with Sébastien Duval and Yann Rotella

Assumptions in Cryptography
Chris Brzuska (TU Hamburg)

EWCDM: An Efficient, Beyond-Birthday Secure, Nonce-Misuse Resistant MAC
Benoît Cogliati (University of Versailles)

We propose a nonce-based MAC construction called EWCDM (Encrypted Wegman-Carter with Davies-Meyer), based on an almost xor-universal hash function and a block cipher, with the following properties: (i) it is simple and efficient, requiring only two calls to the block cipher, one of which can be carried out in parallel to the hash function computation; (ii) it is provably secure beyond the birthday bound when nonces are not reused; (iii) it provably retains security up to the birthday bound in case of nonce misuse. Our construction is a simple modification of the Encrypted Wegman-Carter construction, which is known to achieve only (i) and (iii) when based on a block cipher. Underlying our new construction is a new PRP-to-PRF conversion method coined Encrypted Davies-Meyer, which turns a pair of secret random permutations into a function which is provably indistinguishable from a perfectly random function up to at least $2^{2n/3}$ queries, where $n$ is the bit-length of the domain of the permutations.

Joint work with Yannick Seurin

Encryption Switching Protocols
Geoffroy Couteau (ENS)

We put forth a novel cryptographic primitive: encryption switching protocol (ESP), allowing to switch between two encryption schemes. Intuitively, this two-party protocol converts given ciphertexts from one scheme into ciphertexts of the same messages in the other scheme, for any polynomial number of switches, in any direction. Although ESP is a special kind of two-party computation protocol, it turns out that ESP implies general two-party computation under natural conditions. In particular, our new paradigm is tailored to the evaluation of functions over rings. Indeed, assuming the compatibility of two additively and multiplicatively homomorphic encryption schemes, switching ciphertexts makes it possible to efficiently reconcile the two internal laws. Since no such pair of schemes appeared in the literature, except for the non-interactive case of fully homomorphic encryption which still remains prohibitive in practice, we build the first ElGamal-like encryption scheme over $(Z_n;\times)$ as a complement to the Paillier encryption scheme over $(Z_n;+)$, where $n$ is a strong RSA modulus. Eventually, we also instantiate secure ESP between the two schemes, in front of malicious adversaries. Thanks to a pre-processing step, we manage to get an online communication in terms of group elements which neither depends on the security parameter nor on the modulus $n$. This makes use of a new technique called refreshable twin-ciphertext pool that is of independent interest.

Joint work with Thomas Peters and David Pointcheval