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.
Category / Keywords: foundations / lattices, ring-LWE Publication Info: Extended abstract appears in Eurocrypt 2013 Date: received 16 May 2013, last revised 16 May 2013 Contact author: cpeikert at cc gatech edu Available format(s): PDF | BibTeX Citation Version: 20130523:162730 (All versions of this report) Short URL: ia.cr/2013/293