Paper 2017/606

Creating Cryptographic Challenges Using Multi-Party Computation: The LWE Challenge

Johannes Buchmann, Niklas Büscher, Florian Göpfert, Stefan Katzenbeisser, Juliane Krämer, Daniele Micciancio, Sander Siim, Christine van Vredendaal, and Michael Walter


Practical hardness results are necessary to select parameters for cryptographic schemes. Cryptographic challenges proved to be useful for determining the practical hardness of computational problems that are used to build public-key cryptography. However, several of these problems have the drawback that it is not known how to create a challenge for them without knowing the solutions. Hence, for these problems the creators of the challenges are excluded from participating. In this work, we present a method to create cryptographic challenges without excluding anyone from participating. This method is based on secure multi-party computation (MPC). We demonstrate that the MPC-based approach is indeed feasible by using it to build a challenge for the learning with errors (LWE) problem. The LWE problem is one of the most important problems in lattice-based cryptography. The security of many cryptographic schemes that have been proposed in the last decade is directly based on it. We identify parameters for LWE instances that provide the appropriate hardness level for a challenge while representing instances used to instantiate encryption schemes as close as possible. The LWE challenge is designed to determine the practical hardness of LWE, to gain an overview of the best known LWE solvers, and to motivate additional research effort in this direction.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Minor revision. AsiaPKC@AsiaCCS
latticeslearning with errorsLWEsecure multi-party computationMPC
Contact author(s)
jkraemer @ cdc informatik tu-darmstadt de
2017-06-26: received
Short URL
Creative Commons Attribution


      author = {Johannes Buchmann and Niklas Büscher and Florian Göpfert and Stefan Katzenbeisser and Juliane Krämer and Daniele Micciancio and Sander Siim and Christine van Vredendaal and Michael Walter},
      title = {Creating Cryptographic Challenges Using Multi-Party Computation: The LWE Challenge},
      howpublished = {Cryptology ePrint Archive, Paper 2017/606},
      year = {2017},
      doi = {10.1145/2898420.2898422},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.