Day one - part one - two

The third talk of Monday was given by Chris Peikert on ring-LWE.  Lattice cryptography bases security mainly on SIS and LWE problemS. Whereas they enjoy worst-case security, this approach typically leads to constructions where key sizes and runtimes are big, roughly quadratic on the security parameter (Omega(n^2)). It turns out that their analogous on the ring  setting are more efficient (Omega(n)), so it is important to understand until what extent, without compromising security, the ring counterpart can be  employed.

A key part in the security reduction of RLWE to lattices problems is that the underlying ring should have a particular algebraic structure.  Namely, the class of rings considered are cyclotomic rings, defined as the quotient of polynomial rings with integers coefficents over  cyclotomic polynomials, (the m-th cyclotomic polynomial is that with its  roots being exactly all nth-primitive roots of unity). So unless one is able to provide a reduction for any number field, the question is, what cyclotomic rings and what representations of the  ring elements are best suitable for efficiency purposes?

Many applications  require the degree to be a power of two. This work is on extending the setting to more general cyclotomic rings.  From a practical point of view, the most obvious reason for doing so is that the security level of an application may not need to call to the next power of two in the ring dimension. Working with rings with tighter dimensions allows e.g. to have smaller keys. Also on the power of two case, improvements on  efficiency like SIMD operations cannot be applied.

Using any cyclotomic field would not comprOmise security at all, but other  difficulties arise if we do not restrict to some nicer structures. For example, reduction modulo general or irregular cyclotomic polynomials is  ususally cumbersome because the polynomial can take any shape. The  situation is different if the order is prime.

In the talk, three features were presented which in somehow also determine  the ring structure; the canonical embedding, the tensorial decomposition,  and the dual ring. A crucial quantity when trading security by efficiency is  the expansion factor of the ring; it controls the noise growth after arithmetic  operations. The size of this term can be given in different ways, for example one is tempted to consider the norm of the vector associated to the noise. This way, one is using the so-called coefficient embedding. Unfortunately this yields expansion factors depending on the cyclotomic polynomial, and they are usually quite loose, getting too large  with high composite m. Another important caveat is that security  decreases with the expansion factor. On the other hand we may use the  canonical embedding. It maps the ring element (seen as a polynomial) to the vector of its evaluation at each primitive root, seated on the complex vectorial space. A nice property is that the expansion factor is very small and independent of the base ring. One might suspect that tensorial decomposition will allow SIMD operations. The decomposition is done via an old theorem that states that the m-th cyclotomic  ring can be  expressed as an multivariate quotient depending on the factorization of m. It turns out that this characterization with a basis of the ring called 'powerful basis' renders much efficient  constructions, than if one uses the univariate version with the standard basis (sometimes called power basis). Lastly, under the canonical embedding the  cylotomic ring is not self dual. In the formalization of the RLWE problem  it was shown that the dual was necessary, and although it is possible to  get rid of it DD12, it seems better to keep it since the error tolerance  in decryption is larger when using the dual.

The take-home message of the talk was that mathematical objects (canonical embedding) and representations (tensorial bases) yields provable hardness, fast algorithms and tighter analysis.