Crypto events in Île-de-France

The sunny weather and the general feeling of holiday were not impeding crypto-enthusiasts around Paris to meet and discuss the advancements in this topic. On one hand, the Paris Crypto Day brought together people working on different aspects of cryptography, who are based in the Paris area. The last such meeting was organized by ENS on 30.06.2016 and was fortunate to have Anne Canteaut (INRIA Paris), Leo Reyzin (BU), Victor Shoup (NYU) and Rafael Pass (Cornell) speaking about their research. On July 5-7, Paris also hosted a workshop organized within the HEAT (Homomorphic Encryption Applications and Technology) programme. It was held at Universite Pierre et Marie Curie (a.k.a. Paris 6) and it was composed of six invited talks given by famous researchers within the homomorphic encryption community and ten "regular" talks given by younger researchers and students.

Paris Crypto Day

The first presentation was given by Anne Canteaut on Algebraic Distinguishers against Symmetric Primitives. The talk focused on presenting a unified view about the notions of cube distinguishers and the more recently introduced division property. The aforementioned attacks are based on Knudsen's higher-order differential attacks which exploit properties of the polynomial representation of the cipher. The presentation was very appreciated by the symmetric and asymmetric cryptographers.

Victor Shoup gave a talk about hash proof systems¹ and their applications, in which he reviewed definitions, constructions and applications. Hash proof systems can be seen as a family of keyed hash functions $H_{sk}$ associated to a language $L$ defined over a domain $D$. The secret hashing key $sk$ is used to compute a hash value for every input $x \in D$. Magically, there is a second way to compute the same hash value: it uses a projection key $pk$ (derived from the $sk$) and also a witness $w$ for $x \in L$. The original definition of hash proof systems requires that the projection key does not depend on the word $x$, but later, smooth projective hash functions allow for this change. Smooth projective hash functions have found applications, among others, in password authenticated key exchange.

Leo Reyzin from Boston University (joint work with Joel Alwen, Jeremiah Blocki, and Krzysztof Pietrzak), presented an analysis of SCrypt (originally introduced by Colin Percival in 2009 for Tarsnap), a tool whose potential applications include the realization of time-lock puzzles from memory-hard problems. The starting point for their work was the key derivation function in SCrypt. As stated by Leo during the talk, SCrypt is defined as the result of $n$ steps, where each step consists of selecting one of two previously computed values (the selection depends on the values themselves) and hashing them. It is conjectured that this function is memory-hard. The new result shows that in the Parallel Random Oracle Model, SCrypt is maximally memory-hard. One metric used is the product of time and memory used during the execution of SCrypt, for which the authors show the bound must be $\Theta(n^2)$. Interestingly, for a non-constant amount of memory used during the computation (this scenario simulates real applications), a more accurate metric - defined by the sum of memory usage over time - is again proven to be bounded by $\Theta(n^2)$ and this holds even if the adversary is allowed to make an unbounded number of parallel random oracle queries at each step.

The last speaker was Rafael Pass, from Cornell, who gave an gripping talk about the Analysis of the Blockchain Protocol in Asynchronous Networks. During his talk, Rafael defined the notions of consistency and liveness in asynchronous networks. In what followed, he explained his result that proves the blockchain consensus mechanism satisfies a strong forms of consistency and liveness in an asynchronous network with adversarial delays that are a-priori bounded.

HEAT Workshop

The workshop was really interesting because, besides new theoretical advances in the field, many talks were about the practical-side of FHE: how to set the parameters, concrete results in cryptanalysis, libraries and real-world applications. The part about lattice reduction techniques was especially interesting.

In particular, Antoine Joux gave a talk named "The prehistory of lattice-based cryptanalysis" where he reviewed some lattice reduction algorithms (Gauss's algorithm for two dimensions and LLL for higher dimensions) and gave some cryptanalytic results, e.g. Shamir's attack against the knapsack problem and the low-density attack against Merkle-Hellman knapsack. Basically, lattice-reduction aims at finding a "good" basis, made of short and almost orthogonal vectors, from a "bad" one, made of long and non-orthogonal vectors. In fact, with a good basis problems like SVP or CVP become easy and it is possible to break cryptosystems based on these problems. There are algorithms that do this (like the famous LLL) but the conclusion was that lattice-base cryptography remains secure as long as lattices are big enough: in fact, all the lattice-reduction algorithms work well if the dimension is not too high. With higher dimension many problems appear and lattice-reduction remains hard.

Another interesting talk about this kind of topic was "An overview of lattice reduction algorithms" by Damien Stehlé, who pointed out that lattice reduction has mainly two goals: beside the predictable one of cryptanalysing lattice-based cryptosystems (such as NTRU and all those based on SIS and LWE), it is useful for cryptanalysing other cryptosystems as well, like variants of RSA. He then presented the two main algorithms in this field, i.e. BKZ and LLL, and outlined their differences, like the global strategy used by BKZ versus the local one used by LLL. He also introduced faster-LLL², an improvement of the LLL algorithm which is the subject of one of his most recent works. In the conclusions, he mentioned some open problems and finding a "quantum acceleration" is certainly one of the most interesting ones. In fact, as far as we know, lattice problems are not easier for quantum computers, and this is the reason why they are considered the most promising candidate for post-quantum cryptography.

If someone is into coding, this may be interesting: Shi Bai gave a short talk about FPLLL, an implementation of Floating-Point LLL and BKZ reduction algorithms created by Damien Stehlé. It is a C++ library (also available in Python under the name of FPyLLL) which is also used by the popular Sage. Its goal, as stated by the authors, is to provide benchmarks for lattice reduction algorithms and, more in general, lattice reduction for everyone. More details can be found at https://github.com/fplll/fplll and contributions are welcome!

Besides lattice reduction algorithms, another interesting talk was given by Florian Bourse, who presented a recent work³ about circuit privacy for FHE. The main result is that it is possible to homomorphically evaluate branching programs over GSW ciphertext's without revealing anything about the computation, i.e. the branching program, except for the result and a bound on the circuit's size, by adding just a small amount of noise at each step of computation. This means that the "price" to pay is quite low, especially if compared to other techniques based on bootstrapping. Also, this method does not rely on not-so-well-understood assumptions like circular security and only assumes the hardness of LWE with polynomial modulus-to-noise ratio.

References

^{1. Cramer R, Shoup V. Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption. In Advances in Cryptology— EUROCRYPT 2002, vol. 2332, LNCS. Springer: New York, NY, 2002; 45–64.↩}

^{2. Arnold Neumaier and Damien Stehlé. Faster LLL-type reduction of lattice bases. ISSAC 2016.↩}

^{3. Florian Bourse, Rafael Del Pino, Michele Minelli and Hoeteck Wee. FHE circuit privacy almost for free. CRYPTO 2016, to appear.↩}

This blog post has been collaboratively written by Michele and Razvan.