Cryptology ePrint Archive: Report 2017/606

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

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

Abstract: 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.

Category / Keywords: public-key cryptography / lattices, learning with errors, LWE, secure multi-party computation, MPC

Original Publication (with minor differences): AsiaPKC@AsiaCCS

Date: received 22 Jun 2017, last revised 23 Jun 2017

Contact author: jkraemer at cdc informatik tu-darmstadt de

Available format(s): PDF | BibTeX Citation

Version: 20170626:152454 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]