Paper 2016/782

Challenges for Ring-LWE

Eric Crockett and Chris Peikert

Abstract

As lattice cryptography becomes more widely used in practice, there is an increasing need for further cryptanalytic effort and higher-confidence security estimates for its underlying computational problems. Of particular interest is a class of problems used in many recent implementations, namely, Learning With Errors (LWE), its more efficient ring-based variant Ring-LWE, and their ``deterministic error'' counterparts Learning With Rounding (LWR) and Ring-LWR. To facilitate such analysis, in this work we give a broad collection of challenges for concrete Ring-LWE and Ring-LWR instantiations over cyclotomics rings. The challenges cover a wide variety of instantiations, involving two-power and non-two-power cyclotomics; moduli of various sizes and arithmetic forms; small and large numbers of samples; and error distributions satisfying the bounds from worst-case hardness theorems related to ideal lattices, along with narrower errors that still appear to yield hard instantiations. We estimate the hardness of each challenge by giving the approximate Hermite factor and BKZ block size needed to solve it via lattice-reduction attacks. A central issue in the creation of challenges for LWE-like problems is that dishonestly generated instances can be much harder to solve than properly generated ones, or even impossible. To address this, we devise and implement a simple, non-interactive, publicly verifiable protocol which gives reasonably convincing evidence that the challenges are properly distributed, or at least not much harder than claimed.

Note: Small revisions and additions.