Tightness of the error bound in Ring-LWE

About two months ago we have posted a short paper on eprint sharing some thoughts on the error size used in Ring-LWE, an increasingly important hard problem that was proposed by Lyubashevsky, Peikert and Regev [LPR] as a building block for cryptography. Besides resistance against quantum computers, one of the main features of Ring-LWE for HEAT is that it enables homomorphic encryption.

Very briefly, in Ring-LWE one fixes a degree $n$ number field $K$ with ring of integers $R$ and discriminant $\Delta$. One also fixes an integer modulus $q$ and an error parameter $r \in \mathbb{R}_{> 0}$, which we think of as depending on $n$ only. We write $R_q$ and $R_q^\vee$ for the reduction of $R$ and its codifferent (or `dual') modulo $q$. The Ring-LWE problem is about guessing a secret $\mathbf{s} \in R_q^\vee$ from a number of samples of the form $(\mathbf{a}, \mathbf{a} \cdot \mathbf{s} + \mathbf{e} )$, where $\mathbf{a} \in R_q$ is random and $\mathbf{e}$ is sampled from the distribution on $(K \otimes \mathbb{R})/q\mathbb{Z}$ that one obtains by pulling back a spherical Gaussian of width $r$ under the canonical embedding $K \hookrightarrow \mathbb{R}^n$.

In a recent series of papers Elias, Lauter, Ozman and Stange [ELOS], and Chen, Lauter and Stange [CLS1], [CLS2] investigated whether the existence of a homomorphism $\phi : R_q \rightarrow S$ to some small ring $S$ can be exploited to leak information about the secret $\mathbf{s}$. For instance if $R_q$ is of the form $\mathbb{Z}[x]/(q,f(x))$ for some $f(x) \in \mathbb{Z}[x]$ satisfying $f(1) = 0$ mod $q$, then $\phi$ could be evaluation at $1$: $$ \phi : R_q \rightarrow \mathbb{F}_q: \mathbf{a} \mapsto \mathbf{a}(1).$$ Although this idea is attractive, the concrete vulnerable instances proposed by [ELOS], [CLS1], [CLS2] do not follow the original set-up from [LPR]. Instead they

1. sample the secrets from the ring $R_q$, rather than its dual $R_q^\vee$,
2. use an error parameter of the form $|\Delta|^{1/2n}\cdot r$, rather than just $r$.

It is not entirely clear to us what the implications of 1. are, but at least one should scale up the error parameter in order to compensate for the relative sparseness of $R$, as is indeed done in 2. However the scalar $|\Delta|^{1/2n}$ is chosen from a Polynomial-LWE point of view and is not adapted to the way the Ring-LWE errors are generated. Indeed, the canonical embedding may be very skew, so even though `on average' things will be okay, there could exist a basis of $R$ with respect to which some of the coordinates of $\mathbf{e}$ are negligible. This in turn leads to exact linear equations in the secret $\mathbf{s}$, obtained by merely rounding, which allows for a recovery of the secret using elementary linear algebra.

In a previous paper (reported upon in a blogpost below) we showed that the families from [ELOS] indeed suffer from this skewness, and therefore were easy to start from. To some extent this also seems to apply to the examples from [CLS1] and [CLS2], as is discussed in the last section of our current paper, where we make a more systematic analysis of the skewness phenomenon. Our main contributions are as follows:

• We first give an informal motivation for why the most natural choice of scalar is $|\Delta|^{1/n}$, rather than $|\Delta|^{1/2n}$, if one wants to set up a non-dual version of Ring-LWE as in 1.
• Next we provide for any $\varepsilon > 0$ a family of number fields in which non-dual Ring-LWE can again be broken using elementary linear algebra as soon as the errors are scaled up by $|\Delta|^{(1 - \varepsilon)/n}$ only.
• Finally we show that also the actual (i.e., dual) Ring-LWE problem is easily broken for the same families, as soon as the errors proposed by [LPR] as scaled down by $|\Delta|^{\varepsilon/n}$.

So our conclusions strongly suggest that the problems with the examples from [ELOS] are related to 2., rather than 1. They also provide a tightness statement on the error size proposed by [LPR], at least from a discriminant point of view. Immediate research questions that arise are whether there exist weak instances of non-dual Ring-LWE, when set up with the scalar $|\Delta|^{1/n}$, and, more specifically, whether there exist attacks involving a homomorphism $\phi : R_q \rightarrow S$ that apply here? Or that apply to the actual Ring-LWE problem as introduced in [LPR]?

About a month ago Peikert posted a paper sharing similar (but more detailed) thoughts on the vulnerability of the Ring-LWE instantiations described in [ELOS], [CLS1] and [CLS2].

Wouter Castryck, Ilia Iliashenko, Frederik Vercauteren

CryptoExperts is hiring a Post-Doc Researcher

CryptoExperts (Paris, France) is looking for an excellent postdoctoral fellow to work on the design, the analysis, and the implementation of homomorphic encryption and lattice-based cryptography, who will be primarily involved in the HEAT project.

In this position, the candidate will also be involved in the French CryptoComp project on homomorphic encryption, which aims at developing a fully automated “source to source” compiler which convert any function into a “secure” version of this function able to run on encrypted data. 

In both projects, the challenging industrial use-cases will allow to ground the research in practical issues. The candidate will be able to carry research according to its research interests (theoretical and/or practical), and will be offered multiple travel opportunities and interactions with scientists all over Europe (including the HEAT partners). Participation to the open-source libraries on homomorphic encryption and proof-of-concept demonstrators, main outcomes of the HEAT project, will be expected.

Applicants should have a Ph.D. in a relevant subject or equivalent, have a strong publication record and interest in practical protocols. Implementation and coding experience are required.

The position is fully funded for two years (with a flexible starting date). Review of applications will begin immediately until the position has been filled. Knowledge of French is not mandatory. To apply, please send an e-mail to jobs (at) cryptoexperts.com with the following documents:

• Curriculum vitae, with publication list
• Reference letters

NIST Draft on Post Quantum Cryptography

On February 4th 2016, the National Institute of Standards and Technology (NIST) released a draft entitled Report on Post-Quantum Cryptography. This draft presents NIST's current understanding about the status of quantum computers and post-quantum cryptography, and its initial plan to move forward.

In particular, the NIST has decided that time has come to prepare for the transition to quantum-resistant cryptography. Some striking facts reported in the draft are:

• "researchers working on building a quantum computer have estimated that it is likely that a quantum computer capable of breaking RSA-2048 in a matter of hours could be built by 2030 for a budget of about a billion dollars" (p.6)
• "transitioning from 112 to 128 bits of security is perhaps less urgent than transitioning from existing cryptosystems to post-quantum cryptosystems." (p.6)

This engagement of the NIST to standardize post-quantum cryptography is a true opportunity for everyone to react before practical quantum computing is imminent. The NIST plan is as follows:

1. Feb. 3 2016 - Mar. 9 2016: public comment period for the draft Report on Post-Quantum Cryptography.
2. 2016: proposition of a draft on the evaluation criteria for quantum-resistant public key cryptography, and public comment period.
3. until late 2017: the NIST will accept proposals for quantum-resistant public key encryption, digital signatures, and key exchange algorithms.
4. 2018 + 3/5 years: public scrutiny of the candidates to be standardized.

The NIST emphasizes that this process should not be considered as a competition. The institute see its role as a manager of a transparent process engaging with the cryptographic community, that will eventually reach a consensus on cryptographic standards to be endorsed by industry and other standards organizations around the world.

The HEAT project focuses on bringing fully homomorphic encryption one step further, into products and standards. Obviously, this cannot be, and is not, orthogonal to the quantum-resistant cryptography process. In particular, most of the fully homomorphic encryption schemes belong to one of the main family of post-quantum cryptographic primitives: lattice-based cryptography. As a consequence, all the research that is, and will be, done on fully homomorphic encryption goes hand in hand with the process initiated by the NIST. 

In particular, the Security analysis and parameter recommendations outcome will directly feed the research on analysis of post-quantum primitives. Our open-source software and hardware libraries will include algorithms that will help better understand the performance potential of lattice-based cryptography. Also a member of the HEAT consortium is involved in the ISO standardization, and the main editor of the upcoming WG 2 standard on Homomorphic Encryption, that is, encryption that supports computing over encrypted data. A workshop on Cryptographic Standards and Evaluations  (AWACS 2016) will be organized by CryptoExperts, on behalf of the ECRYPT-CSA project, on May 8 2016, and will include talks and a panel discussion on the present and near-future trends in crypto standards (with an emphasis on the post-quantum rush). 

Last but not least, many members of the HEAT consortium are actively involved in the research on post-quantum primitives such as key-exchange or digital signatures.

Satellite Applications of Homomorphic Encryption

Thales UK has been investigating the use of Homomorphic Encryption (HE) in satellite scenarios. In particular, our assessment has focused on the data processing of imaging products; one of the many types of signal processing applications which could have been chosen.  

It is relatively simple to find signal processing satellite applications where HE could, in theory at least, provide real benefit. In particular, to provide end-to-end security of data from the sensor on the satellite to the end user, while allowing the potentially complex and specialised signal processing to be performed on shared (and less trusted from the end user’s point of view) infrastructure. The real challenge has been to find such applications that are potentially practical in the near term, using Somewhat Homomorphic Encryption (SHE).

Consider the Sentinel 2 Multi Spectral Imager which is a representative example of an earth observation satellite (in this case designed for environmental monitoring). In order to be suitable for the application of HE to provide sensor to end user security, all the signal processing algorithms would have to be amenable to HE. It turns out that many of them potentially are, in particular the deconvolution algorithms that use Fourier Transforms. However, other parts of the processing are more difficult to deal with in HE. For example, processing to deal with imperfections such as:

• saturated pixels
• no data pixels and partially corrected pixels (crosstalk correction)
• defective pixels

These are very simple algorithms, but involve a lot of conditional operators (<, >, etc. to test pixel values) that would be expensive when implemented on HE encrypted data.

A much more promising candidate is Synthetic Aperture Radar (SAR) (e.g. Envisat). SAR is used to provide high precision, and often 3D, imaging for applications such as sea ice and glacier monitoring, vegetation coverage analysis, disaster monitoring and traffic surveillance. Being a radio-based technique, it is not affected by weather or the lack of daylight. The raw data collected by the satellite consists of a series of radar echoes, and these must be processed to form an image. On examining the details of this processing, it can be seen that the core functionality consists of a series of:

• Fourier Transforms (and their inverses)
• Hadamard products of matrices

These can be implemented, in theory at least, with a low multiplicative depth, and without the need for conditional operators. This is therefore a good candidate application for SHE, but much work needs to be done to demonstrate its practicality. 

Provably Weak Instances of Ring-LWE Revisited

In Crypto 2015, Elias, Lauter, Ozman and Stange [ELOS15] proposed a successful attack on the decision version of the non-dual Ring-LWE problem over number fields $K$ for two specific families of defining polynomials. Both families have the common feature that the coefficients of the polynomials are dependent on the modulus $q$.

We extended this attack to the search version of Ring-LWE by using that the error distributions in such number fields are very skewed by moving away from the Minkowski space. Particularly, the largest errors either wrap around modulo $q$ (and thus make it impossible to decrypt the secret), or the smallest ones are so negligible that we obtain exact linear equations that reveal the secret. Our attack applies to every modulus up to $q$, and requires less samples.

Let $M$ be the $n \times n$ matrix of the canonical embedding $K \to \mathbb{C}^n$ with respect to the polynomial basis of $K$, and let $N$ be its inverse. The "skewness" of the errors can be nicely described by the singular value decomposition (SVD) of the matrix $N$ and the condition number $k(N) = s_1(N)/s_n(N)$, where $s_1$ and $s_n$ are the biggest and the smallest singular values correspondingly.

Recall that the SVD is given by $N = U \cdot \Sigma \cdot \overline{V}^t$, where $U$, $V$ are unitary matrices and $\Sigma$ is a diagonal matrix containing the singular values. The image of a unit sphere under $N$ will result in an ellipsoid whose axes are defined by the columns of $U$, with length equal to the corresponding singular value. Hence, the condition number captures how heavily this ellipsoid is deformed.

All vulnerable instances in [ELOS15] are defined by polynomials $f_{n, a, b} = x^n +ax + b$, where $a$ and $b$ are such that  $f(1) = 0 \bmod q$, which is the property that they exploit, but that our attack does not need. If we consider their first family of samples, where $a = 0$ and $b = q - 1$, the SVD of $N$ is of the form $I_{n \times n} \cdot \Sigma \cdot \overline{V}^t$. Thus a spherical error distribution on the Minkowski space with the parameter $\sigma$ induces an elliptical distribution on the number field, where the $i$th coordinate is distributed by a Gaussian with $\sigma_i = s_i(N) \cdot \sigma$. Moreover, the condition number is close to the modulus $q$, that is, the elliptical distribution is stretched along axes whose lengths range roughly from $\sigma_1$ to $q \cdot \sigma_1$. For the second family we did not find such an explicit form of the SVD. Nevertheless, the unitary matrix $U$ remains close to being diagonal (see the heat map below) and the singular values form a near-geometric series again leading to a condition number close to $q$.

It can be easily seen that for both families and for the choices of $\sigma$ made in [ELOS15], the Ring-LWE distribution generates negligible errors in the higher terms of the polynomial basis. More precisely each Ring-LWE sample $(a, b = a \cdot s + e)$ can be written as

\[ M_{a} \cdot (s_0, s_1, \dots, s_{n-1})^t = (b_{0}, b_{1}, \dots, b_{n-1})^t - (e_{0}, e_{1}, \dots, e_{n-1})^t , \]

where $M_{a}$ corresponds to multiplication by $a$. By rounding, the higher error terms are removed and the last equations become exact equations in the coefficients of the secret. If the highest $\left\lceil n/k \right\rceil$ error terms round to zero then we need only $k$ Ring-LWE samples to reveal the secret (for these concrete examples 10 samples amply suffice).

The corresponding paper will appear soon on the Eprint.

Wouter Castryck, Ilia Iliashenko and Fre Vercauteren.

Workshop on Lattice Cryptography

It is the day after AsiaCrypt 2015 and there are two workshops being held in Auckland. The one which is most relevant for my research is that on Lattice Based Cryptography; which consists of four talks. One by Jung Hee Cheon on "Multilinear Maps and Their Cryptanalysis", one by Amit Sahai on "Obfuscation", one by Fre Vercauteren on "Weak Instances of RLWE" and one by Martin Albrecht on "Small Secret LWE".

---

Cheon first described a very naive version of multi-linear maps and then went on to show how this can be attacked by creating non-trivial encodings of zero, and then taking greatest common divisors. Then he went on to generalise this naive scheme to the CLT scheme (which is a bit like the DGHV FHE scheme). The naive attack does not apply to CLT as the dimension increased, meaning taking naive greatest common divisors would not work. Cheon then showed how to extend the naive attack to the CLT case by turning the gcd extraction into an eigenvalue extraction problem. This done by building quadratic forms which represent encodings of zero. The result is that for the CLT scheme one can break the equivalent of the DLP problem.

Cheon then went on to present the GGH scheme, which is a bit like the NTRU FHE scheme; except the instead of encrypting via c=[(m+r*p)/z] for an integer p, one encodes via c=[(m+r*g)/z] for a polynomial g which generates the ideal lattice <g>. Modifying the prior attack in this situation allows us to recover a basis of this ideal. But finding a short vector in this lattice can be hard. However, by utilizing encodings of zero one can actually solve the equivalent of the CDH problem.

Both attacks rely heavily on the presence of encodings of zero. So the attacks do not apply to situations in which one does not publish such encodings; i.e. applications such as indistinguishability Obfuscation (iO).

---

Amit Sahai then gave an introduction to iO; he motivated it via an analogy of an attacker who captures your brain and is able to read and tamper with every neuron, yet we still do not want the attacker to know what we are thinking about. This is the problem which obfuscation tries to solve in the computing realm. Martin pointed out that this would be a great way to produce malware!

Amit then put Multi-Party Computation within this analogy. He suggested we can think of MPC as protecting our brain against the tampering adversary, by dividing the brain up into portions. As long as one portion is kept out of the adversaries control we can use MPC to protect our thoughts. Obfuscation tries to do the same, without there needing to be an honest part of the brain.

Any program which is suitable for obfuscation must be unlearnable from query access to the program. Since otherwise the adversary could learn the program from the input/output behaviour. However, black-box obfuscation has been shown to be impossible; essentially because their are contrived programs which are unlearnable but for which one cannot produce an obfuscation, since any obfuscated program has an explicit attack against it.

This is why iO as a concept was presented; since it at least seems possible to achieve. The idea is that if you have two equivalent programs and we obfuscate one of them, then the adversary cannot tell which one we obfuscated. One way of thinking of this is as a psuedo-canonicalizer. The question is what useful can one do if we could create an obfuscator which satisfied the iO definition. Amit gave the application of building demo versions of software, without needing to re-engineer the software.

---

Fre Vercauteren then discussed a more in depth analysis of a paper from CRYPTO this year on Weak Instances of Ring-LWE. The CRYPTO paper gave instances where decision Ring-LWE was easy, but search appeared to be hard. However, Fre's talk showed that the search problem was in fact easy from the start, and thus the CRYPTO paper was less surprising than it at first seemed to be. As with all things on Ring-LWE the question arises as to how to choose the error distributions.

Fre spend the first part of his talk discussing the geometry of number fields, and in particular the Minkowski embedding. The Ring-LWE problem generates errors according to a discrete Gaussian distribution in the Minkowski embedding, Poly-LWE is to generate the errors according to a discrete Gaussian in the polynomial embedding.

Eisentrager et al discussed cases for which Poly-LWE was easy, these were then extended by Elias et al to special cases of decision Ring-LWE. They did this by mapping the special Ring-LWE instance to a special Poly-LWE instance.This is done by pulling back the problem from Ring-LWE to Poly-LWE via the matrix which defines the Minkowski embedding. The Poly-LWE attack requires that q is larger than f(1), and hence q will "kind of show up" in the coefficients of the defining polynomial f. So the fields being attacked, are very special indeed.


(This post originally appeared in the BristolCrypto blog)

C++ Library dedicated to arithmetic on cyclotomic rings: NFLlib

As a new Phd student working on the HEAT project at the UPMC, I spent the last two months reading some stuff about Fully Homomorphic Encryption. Among my different readings, I have noticed an article presenting a new promising open-source C++ library: NFLlib. It has been developed for both the HEAT project and CRYPTOCOMP and is dedicated to ideal lattice cryptography.

This library deals with the arithmetic on the wide spread cyclotomic rings $\mathbb{Z}_q[X]/(X^n+1)$ with $n$ a power of two. At the difference of the Microsoft library SEAL which implements the YASHE encryption scheme, NFLlib provides the elementary functions to build any cryptosystems on those cyclotomic rings. By using Chinese Reminder Theorem, an optimized Number Theoretic Transform and different implementation optimization techniques for SIMD instructions it achieves better performances than the classical libraries NTL and FLINT.

This library will be available soon on https://github.com/quarkslab/NFLlib, in the meantime the Francophones can refer to the article "Quatre millions d'échanges de clés par seconde" (Four millions key-exchanges per second) https://www.sstic.org/media/SSTIC2015/SSTIC-actes/4M_kx_per_sec/SSTIC2015-Article-4M_kx_per_sec-guinet_aguilar_guelton_lepoint.pdf which presents it as well as the performances of a key-exchange protocol using a lattice based encryption scheme. For the non-french speakers an english version has been accepted at CT-RSA 2016 and will be available soon on the Eprint.