Creating cryptographic challenges using multi-party computation : the LWE challenge

J. Buchmann, N. Buscher, F. Göpfert, S. Katzenbeisser, J. Kramer, D. Micciancio, S. Siim, C. van Vredendaal, M. Walter

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

10 Citations (Scopus)


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.
Original languageEnglish
Title of host publicationAsiaPKC '16 Proceedings of the 3rd ACM International Workshop on ASIA Public-Key Cryptography, 30 May 2016, Xi'an, China
Place of PublicationNew York
PublisherAssociation for Computing Machinery, Inc
ISBN (Print)978-1-4503-4286-5
Publication statusPublished - 2016


Dive into the research topics of 'Creating cryptographic challenges using multi-party computation : the LWE challenge'. Together they form a unique fingerprint.

Cite this