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.Category / Keywords: Ring-LWE, Ring-LWR, challenges, cryptanalysis Date: received 16 Aug 2016, last revised 21 Feb 2017 Contact author: cpeikert at alum mit edu Available format(s): PDF | BibTeX Citation Note: Added BKZ block size estimates, minor edits and updates throughout. Version: 20170222:043438 (All versions of this report) Short URL: ia.cr/2016/782 Discussion forum: Show discussion | Start new discussion