Looking for fast OpenSource algorithms on lattices? Try fpLLL!

Dear ECRYPT-NET fellows and readers,
I have some news from CWI @ Science Park in Amsterdam where fplll-days-3, organized by Leo Ducas and Marc Stevens, are currently taking place!

Previously held at ENS Lyon, this is the third time already for such a combined effort to enhance the fplll OpenSource project. fplll has become a lively project with many suggestions that help to debug and feature requests for continuously improving the code-base in various directions.

As a brief history of fplll it can be noted that the first code was written by Damien Stehlé. It is now written by many active contributors (according to GitHub, the most active developers are: Martin Albrecht, Shi Bai, Damien Stehlé, Guillaume Bonnoron, Marc Stevens and Koen de Boer) and maintained by Martin Albrecht and Shi Bai.

What does fplll do?

What fplll does, depending on additionally specified parameters, is performing its implementation of the LLL algorithm using fast floating-point arithmetic under the hood. Other available lattice reduction algorithms are HKZ, BKZ reduction and variants. These algorithms can be applied on an input lattice represented by a matrix, given i.e. in a file as a set of row vectors, to obtain a reduced representation --- a versatile starting point of numerous applications. Furthermore, fplll allows to solve (arbitrarily adjustable approximate-) SVP and CVP instances, when used to find a shortest lattice vector relative to a user-chosen center.

To get started, one can not only use and compile the fplll C++ sources to run experiments, but the often dubbed 'user-friendlier variant' fpylll which provides Python access to the underlying, fast C++ functions. Finally, every mathematician's dear, Sage, (at least for anyone who isn't fully satisfied by pure Python) benefits from an improved fpylll as well, because importing the fpylll module seamlessly allows direct usage within Sage. Soon a new Sage version, SageMath 8.0, will be released, which ships the current fpylll module that accesses said, fast C++ routines.

The significance of lattice-based cryptography is repeatedly mentioned in paper's abstracts and has been explored in past ECRYPT-NET blog posts i.e. on 'What are lattices?' and 'Learning problems and cryptography: LPN, LWE and LWR'.

Significance for cryptanalysis

From a cryptanalysts point of view, the significance lies in the fact that most security models of lattice-based cryptography typically assume lattice reduction to be the most promising attack-vector against the underlying lattice-based primitive. Some security models are able to immediately (and provably) rule out certain classes of attacks and, for instance, a few others can be argued to be less promising than known formulations as lattice problems. Such arguing hence leads to fplll basically representing the SVP/CVP-oracle and it's performance is deemed as a lower bound for the practical performance of an attack. Typically attacks require many calls to such an oracle function, thus such an approach of taking the time of a single run as a lower bound is used to set parameters in experimental cryptosystems, when commonly a more conservative

lower bound including a security margin is chosen. Specifically, many proposed lattice-based crypto-schemes have been parametrized such that these best known-attacks are taken into account.

I suppose, I do not need to point out the numerous advantages of OpenSource software (over closed-source projects) but and its value to the research community the significance of having freely-available, fast lattice reduction routines is manifold.

To begin with, there is a discrepancy between what theory predicts and algorithmic performance in practice. Techniques described in the literature, summarized as BKZ2.0, leave a broad range of implementation choices. Different groups using different software and metrics where their approach is supreme, naturally lead to results that are hard to compare. If there was software that comes with meaningful defaults for many standard lattice tasks, is customizable, and extensible to individual lattice solutions, then there is hope that the community can agree on problem instances. Ideally, problem instances should cover deployed or model experimental cryptosystems such that they embody a meaningful benchmark for new designs.

Originally, fplll was trying to provide such algorithms with reasonable speed. Recently, developers broadened theirs goals and try to fill gaps of cryptanalytic research. Concretely, now fplll strives for speed from low level optimizations, and by implementing diverse techniques from the literature hence catching up with the state of the art. Additionally, it can be easily tweaked on a high algorithmic level with the Python layer fpylll, yet easily exploiting all the available optimized routines boosting the performance. One can argue that together with diverse lattice challanges this project helps to benchmark and compare various efforts to cryptanalyze cryptographic primitives used in cryptosystem's constructions.

A couple of Lattice Challenges have been proposed (SVP-, Ideal-, LWE- and Ring-Challenges) and it seems that researchers also test their code on these instances, which aids a comparison of approaches.

Having them conveniently accessible and high-level, fast lattice operations allows to quickly try out a new idea, or slightly different approach which saves time and hopefully makes researchers willing to share their tweaks and algorithmic tricks more often in the future.

The workshop

To come back to the start, the fplll-days are meant to be a hands-on, work-oriented workshop that enables direct discussions with core developers and with the goal to improve existing functions and the many algorithms involved. The general idea behind this meeting is to optimize often used routines, make it user-friendlier and accessible to cryptanalysts, for example.

By using code profiling tools, performance and memory usage bottlenecks can be spotted in a first overview, which allows to direct efforts where they might lead to significant speed-ups. After discussing know issues and useful features, this workshop tries to provide an implementation of numerically stable algorithmic variants to push the dimension LLL can handle (like Givens rotations while resorting only to machine floating point type), sophisticated pruning strategies to speed-up enumeration, and implementing sieving algorithms --- all as a promising new direction in finding short vectors faster.

It is exciting to join and shape such a project so let's hope for many interesting projects that got started and delegated here to be completed during this week and further interested researchers turning into active users joining the party and coming up with meaningful, reproducible research results. Remember that Newton "has seen further, by standing on the shoulders of giants" thus achieving progress, and so you too are encouraged to become active, using an already established framework!

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.

The Subset-Sum Problem

The Subset-Sum problem (also known as knapsack problem) we want to review in this blog-post is defined as follows: Given $n, S, a_1, a_2, \dots a_n \in \mathbb{N}$, find \begin{align} I \subseteq [n] = \{1,2, \dots, n\}: \sum_{i \in I} a_i = S. \quad (1) \label{s} \end{align}
Historical Remarks

This old problem was first studied in 1897, the same year the first airborne mission to completely reach the geographical north pole (NP) started (and ended...), and was one of the first proven to be NP-complete -- worst-case instances of this problem are computationally intractable. Subset-Sum was proved to be NP-complete by reducing '3-SAT' to the 'Graph Coloring Problem' which was reduced to 'Exact cover' which was reduced to Knapsack and close variants thereof. These proofs were carried out during the early 1970's rigorous reduction proofs and Subset-Sum problem is featured on Karp's somewhat famous list of 21 NP-complete problems, all infeasible to solve on current computers & algorithms thus a possible basis for cryptographic primitives. In the following table one can see how the expected time/space requirements of algorithms solving (1) in hard cases evolved as the techniques were refined by modern research:

Expected time and space requirements of algorithms solving (1) in average hard instances.

The time and space requirements of current approaches are considerably less than for performing exhaustive search, a generic meet in the middle attack or even a finer combinatorial split into four (or multiple) lists. The currently best known algorithm, asymptotically speaking, is a quantum algorithm. The problem of determining a lower bound of the run-time is still an open research question. It seems more difficult than to see a possible link between the declining polar bear population in the arctic regions and the retreating sea ice accelerated by the observable rapid climate change.

Let us review two classical techniques that led to remarkable speed-ups:

Technique 1 - Meet in the Middle

Schröppel-Shamir: Combining disjoint sub-problems of smaller weight.

Hard instances of the Subset-Sum problem are characterized by relatively large elements $(\log_2 a_i \approx n)$ and a balanced solution, i.e. $|I| \approx \frac n 2$ in Equation (1). Identifying subsets of $[n]$ with length $n$ vectors $x$ over the 'number-set' $\{0,1\}$ via $i \in I \Leftrightarrow x[i] = 1$ one constructs lists $L_1, L_2$ of pairs merged to a solution in $L_0$:
Algorithms based on the birthday-paradox construct expected collisions in the second component of the sub-problems in the lists $L_1, L_2$ forcing any $x \in L_0$ to fulfill (1). The difficulty is to estimate the list-size needed to observe the existence of one solution with high probability. It is desirable to ensure that it is more likely to terminate the algorithm with a non-empty $|L_0| \geq 1$ (i.e. have a solution) than the chance to see a polar bear towards the north-east or meet one in the middle of Svalbard, Norway.

Technique 2 - Enlarge Number Set

BCJ11: Adding length $n$ sub-solutions increases the number-set.

The idea in Howgrave-Graham-Joux (2010) that was later extended by Becker-Coron-Joux (2011) was to allow multiple representations. This comes at the price of enlarging the number-set, i.e. having $$x_0[i] = x_1[i] + x_2[i] \not \in \{0, 1\}.$$ Additionally to the first improvements due to constructing colliding sums, constructing too many potential solutions and introducing a non-trivial filtering step to remove 'inconsistent' ones when merging the two lists $L_1$ and $L_2$ back into one, still gave an overall speed-up asymptotically. 
The number-set used by the authors was $\{-1,0,1\}$, indicating a summand appearing on both sides of Equation (1).
After constructing sufficiently many sub-problems and their respective partial solutions a collision can be expected thus the combination forms a solution for the given instance.  


Applications 
The cryptanalytic methods for structurally approaching the Subset-Sum problem are valuable algorithmic meta-techniques also applicable to other NP-complete problems like lattice- or code-based problems.

Credits: http://fav.me/d3a1n08

Such problems are promising candidates for the construction of post-quantum cryptosystems, cloud security applications and encrypted Polar Bear TV broadcasts. There is a conference focusing on such topics (Polar bears and NP-complete problems) coming up - stay tuned.



PS: The bad image quality, is due to blogger wouldn't let me include vector-graphics like .pdf or .eps nor directly render them giving latex code... :-(

Post-Quantum Cryptography: Why? What is it?

Why Post-Quantum Cryptography?

When I wrote my first blog entry here ("Ola from Gustavo"), I gave a short description of what will happen when someone presents the first quantum computer, i.e., most of the actual cryptography (ECC, RSA) will be dead, see [1] for more details. One statement about quantum computers and cryptography is:
"Well, we don't have a quantum computer now and the expectation for one is around 15 years, why I should be worried now?"
I will give one good reason, imagine that you use some encryption (RSA, ECC or whatever) in your messages and someone starts storing these messages. Now, this agency/person/computer is not able to read your messages. However, in 15 years (around this) when a real quantum computer appears then, it will be possible to break the encryption and read everything about your past. For this reason, we need to be prepared against this threat now and we don't need to wait for the quantum computer to start to protect ourselves. For this protection, we have good guardians of the privacy that with the union of their powers started the research in Post-Quantum cryptography (PQC).

In the figure (see above), we can see that PQC divides into four big areas, i.e., Hash-based, Code-based, Multivariate-quadratic-equations-based and Lattice-based. There are other areas but these four became more important in the last 10 years. In the following, I will give a very brief explanation and examples of schemes of each area in PQC. There is a website about PQCrypto with initial recommendations and a list of publications in the area to access click here.

HASH-BASED Cryptography

In hash-based, we can see important signature schemes such as Lamport-Diffie OTS, Merkle's hash-tree, XMSS, SPHINCS and a lot of relevant work. I decided to talk about one of the newest works in the area, i.e., SPHINCS.
SPHINCS was presented in 2015 at EUROCRYPT under the title of "SPHINCS: practical stateless hash-based signatures". In order to understand better the idea behind this work, it is necessary to have a previous knowledge about hash signatures because they present two new ideas: replacement of the leaf OTS (One-time Signature) with a hash-based FTS (Few-time Signature) and Goldreich’s construction as a hyper-tree construction with h layers of trees of height 1. For more details about the implementation and construction of SPHINCS, it is possible to access here.
Also, if you have more interest in Hash-Based cryptography can be checked via pqcrypto hash-based and at this webpage of Andreas Hülsing.

CODE-BASED Cryptography

The classic name that appears in Code-based is McEliece’s hidden-Goppa-code public-key encryption system from 1978. However, there is new work in the area such as the work from Misoczki, Tillich, Sendrier, and Barreto using quasi-cyclic moderate-density-parity-check (QC-MDPC) codes for the McEliece encryption system. The principal contribution of this work for the area is the use of small key sizes.
Other relevant work, this time in the fast implementation area, came from Bernstein, Chou, and Schwabe under the name of "McBits: Fast constant-time code-based cryptography". The main contribution of this work is a constant-time in the implementation of code-based cryptography and they avoid time attacks.
The literature for code-based is very big and can be checked in this link.

MQ-BASED Cryptography

The Multivariate Cryptography schemes are based on the difficult to solve non-linear systems of equations over
finite fields. Finding a solution for these systems, in general, is considered a NP-complete/-hard problem. One of many
interesting examples is Patarin’s Hidden Fields , generalizing a proposal by Matsumoto and Imai (1988).
The original work from Paratin can be found at: Hidden Field Equations (HFE) andIsomorphisms of Polynomials (IP): two new Families of Asymmetric Algorithms.

If we want to see what happened recently in the MQ area, there is slides from the PQCrypto winter school are available online at PQCrypto . The slides from Jintai Ding gave a very nice overview of the state-of-art in the Multivariate
Public Key Cryptography (MPKC). In the slides, he gave an introduction MQ with a small example to understand
how MQ works. After that, the author gives the principal cryptosystems in MPKC.
The slides are available at this link and more material about MQ-based cryptography can be checked at PQCrypto project.

LATTICE-BASED Cryptography

The lattice area received a lot of attention in the past years, new cryptosystems, new attacks, and implementations. Everything is based on hard problems in lattices such as shortest-vector problem (SVP), Ideal Lattice, Closest-vector Problem (CVP) and others. There is a lattice challenge to show the shortest vector in a Lattice and the ideal Lattice given the dimension of it, more details about it can be checked at Lattice Challenge.

In the area of public-key cryptography, there are several schemes and mostly is based on SVP and Ideal lattices. That is the case for  the scheme described by Peikert and Stehlé et al.

Post-quantum Cryptography and ECRYPT-NET

One of the interests of the ECRYPT-NET project is in PQC and we have four fellowships working in this area. In Lattice-based, we have Marco Martinoli, Michele Minelli and Henry de Valence. In the quantum algorithms area I started work with this.

I started to read about all of the areas described before for two reasons. Firstly, I needed to understand the basic of each area to decide where I want to work. Secondly,  after all the reading I decided to work with quantum algorithms and attack each area using it. In the following months, I will start writing about quantum algorithms and the impact in the cryptography.


[1] Bernstein, Daniel J., Johannes Buchmann, and Erik Dahmen, eds. Post-quantum cryptography. Springer Science & Business Media, 2009.