This site provides cryptanalytic challenges for the Learning With Errors over Rings (Ring-LWE) problem.
The 516 challenges cover a wide variety of concrete Ring-LWE instantiations over cyclotomic rings, and represent a broad spectrum of estimated hardness levels, ranging from "toy" and "easy" to "very hard."
We give evidence that the challenges are properly generated via a non-interactive, publicly verifiable "cut and choose" protocol that uses the OriginStamp blockchain-based timestamping service and the NIST randomness beacon. See our paper for full details.
(All archives are cryptographically signed under the project's PGP/GPG public key, which was announced in this tweet. You should verify that the key has ID b8b2 45f5 and fingerprint 8126 1e02 fc1a 11c9 631a 65be b5b3 1682 b8b2 45f5.)
Each challenge corresponds to a certain instantiation, or parameterization, of the Ring-LWE problem, determined by: the choice of cyclotomic ring, the modulus, the "width" of the error, and the number of samples. In addition, there are instantiations for both continuous and discretized ("rounded off") error, and for the related "Learning With Rounding over Rings" (Ring-LWR) problem.
A challenge consists of 32 instances, each with a different secret, consisting of several Ring-LWE/LWR samples. As part of the cut-and-choose protocol, for each challenge we "spoiled" all but one of the instances by revealing their secrets; the choice of which ones remain unspoiled was made by the NIST randomness beacon after we published the challenges. One can verify that the spoiled challenges appear properly generated, which provides reasonably convincing evidence that the unspoiled instances were properly generated as well. The unspoiled instances are the ones that should be cryptanalyzed.
If you are willing to believe that we generated the challenges properly—and we did!—then the archive of the official ("unspoiled") challenges (and its digital signature under our public key) is all you need to start attacking the challenges.
The challenges are serialized using protocol buffers, Google's platform-independent, language-neutral mechanism for serializing structured data. The formats are defined in the Ring-LWE and Challenges specification files. These can be used to automatically generate parsers for the challenges in almost any popular programming language.
For convenience, we have provided pre-generated parsers for C++, Java, and Python. Each archive also includes a simple driver which demonstrates how to access the data in the challenges. (There is also a parser and verifier for Haskell.)
For reference, we have also provided a detailed example showing the format of the challenges.
If you would like reasonably convincing evidence that the challenges were properly generated, then you can act as the verifier in our cut-and-choose protocol.
The full challenges archive was made available on 13 Aug 2016, and corresponds to the "commit phase" of the cut-and-choose protocol. It contains 32 separate instances for each Ring-LWE/LWR instantiation. This makes it quite quite large (~2.7 GB), so we distribute it via BitTorrent. Please download and seed to help! Use this Torrent file or Magnet link.
(The archive rlwe-challenges-v1.tar.gz has SHA-256 hash value 07cd f744 5c9d 178c 8b13 5a42 47ca a143 5320 c104 8ee8 c634 8914 a915 5757 dcef, and was timestamped on 14 Aug 2016 via the Bitcoin blockchain. Its digital signature is also included in the torrent, and should be verified using the project's public key.)
On 19 Aug 2016 we revealed the secrets (with digital signature) for all but one of the instances for each Ring-LWE/LWR instantiation, as determined by the random NIST beacon values from 17 Aug 2016. These secrets can be used to verify that the corresponding challenges were properly generated.
The first person or group to submit the solution to any non-"toy" challenge will be listed here.
To submit a solution, email rlwe dot challenges at gmail dot com a file containing a message Secret (with any seed) following the protocol buffers message specifications for RLWE and our challenges.
Along with your solution, please also include any relevant information about how you found it, such as: algorithm used, amount of computation required (e.g., core-days and memory), root-Hermite factor obtained, etc.