Monday, May 27, 2013
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.