International Association
for Cryptologic Research

Recent advances in lattice cryptography, mainly stemming from the

development of ring-based primitives such as ring-$\\lwe$, have made it

possible to design cryptographic schemes whose efficiency is

competitive with that of more traditional number-theoretic ones, along

with entirely new applications like fully homomorphic encryption.

Unfortunately, realizing the full potential of ring-based cryptography

has so far been hindered by a lack of practical algorithms and

analytical tools for working in this context. As a result, most

previous works have focused on very special classes of rings such as

power-of-two cyclotomics, which significantly restricts the possible

applications.

We bridge this gap by introducing a toolkit of fast, modular

algorithms and analytical techniques that can be used in a wide

variety of ring-based cryptographic applications, particularly those

built around ring-\\lwe. Our techniques yield applications that work

in \\emph{arbitrary} cyclotomic rings, with \\emph{no loss} in their

underlying worst-case hardness guarantees, and very little loss in

computational efficiency, relative to power-of-two cyclotomics. To

demonstrate the toolkit\'s applicability, we develop two illustrative

applications: a public-key cryptosystem and a ``somewhat homomorphic\'\'

symmetric encryption scheme. Both apply to arbitrary cyclotomics, have

tight parameters, and very efficient implementations.