research-article

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

Authors:

Johannes Buchmann,

Niklas Büscher,

Florian Göpfert,

Stefan Katzenbeisser,

Juliane Krämer,

Daniele Micciancio,

Christine van Vredendaal,

Michael WalterAuthors Info & Claims

AsiaPKC '16: Proceedings of the 3rd ACM International Workshop on ASIA Public-Key Cryptography

Pages 11 - 20

https://doi.org/10.1145/2898420.2898422

Published: 30 May 2016 Publication History

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.

References

[1]

Certicom ECC challenge. https://www.certicom.com/images/pdfs/challenge-2009.pdf. Accessed: 2015-12-21.

[2]

NTRU challenge. https://www.securityinnovation.com/uploads/ntru-challenge-parameter-sets-and-public-keys-new.pdf. Accessed: 2015-12-21.

[3]

The RSA factoring challenge. http://www.emc.com/emc-plus/rsa-labs/historical/the-rsa-factoring-challenge.htm. Accessed: 2015-12-18.

[4]

M. R. Albrecht, C. Cid, J. Faugère, R. Fitzpatrick, and L. Perret. Algebraic algorithms for LWE problems. IACR Cryptology ePrint Archive, 2014:1018, 2014.

[5]

M. R. Albrecht, C. Cid, J. Faugère, R. Fitzpatrick, and L. Perret. On the complexity of the BKW algorithm on LWE. Des. Codes Cryptography, 74(2):325--354, 2015.

Digital Library

[6]

M. R. Albrecht, R. Fitzpatrick, and F. Göpfert. On the efficacy of solving LWE by reduction to unique-svp. In H. Lee and D. Han, editors, Information Security and Cryptology - ICISC 2013 - 16th International Conference, Seoul, Korea, November 27-29, 2013, Revised Selected Papers, volume 8565 of Lecture Notes in Computer Science, pages 293--310. Springer, 2013.

[7]

M. R. Albrecht, R. Player, and S. Scott. On the concrete hardness of learning with errors. Cryptology ePrint Archive, Report 2015/046, 2015. http://eprint.iacr.org/.

[8]

S. Arora and R. Ge. New algorithms for learning in presence of errors. In L. Aceto, M. Henzinger, and J. Sgall, editors, Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4--8, 2011, Proceedings, Part I, volume 6755 of Lecture Notes in Computer Science, pages 403--415. Springer, 2011.

Digital Library

[9]

Y. Aumann and Y. Lindell. Security against covert adversaries: Efficient protocols for realistic adversaries. J. Cryptology, 23(2):281--343, 2010.

Digital Library

[10]

L. Babai. On lovász' lattice reduction and the nearest lattice point problem. Combinatorica, 6(1):1--13, 1986.

Digital Library

[11]

S. Bai and S. D. Galbraith. An improved compression technique for signatures based on learning with errors. In J. Benaloh, editor, Topics in Cryptology - CT-RSA 2014 - The Cryptographer's Track at the RSA Conference 2014, San Francisco, CA, USA, February 25--28, 2014. Proceedings, volume 8366 of Lecture Notes in Computer Science, pages 28--47. Springer, 2014.

[12]

S. Bai and S. D. Galbraith. Lattice decoding attacks on binary LWE. In W. Susilo and Y. Mu, editors, Information Security and Privacy - 19th Australasian Conference, ACISP 2014, Wollongong, NSW, Australia, July 7--9, 2014. Proceedings, volume 8544 of Lecture Notes in Computer Science, pages 322--337. Springer, 2014.

[13]

D. J. Bernstein, J. Buchmann, and E. Dahmen, editors. Post-quantum cryptography. Mathematics and Statistics. 2009.

Digital Library

[14]

A. Blum, A. Kalai, and H. Wasserman. Noise-tolerant learning, the parity problem, and the statistical query model. J. ACM, 50(4):506--519, July 2003.

Digital Library

[15]

D. Bogdanov, M. Jõemets, S. Siim, and M. Vaht. How the estonian tax and customs board evaluated a tax fraud detection system based on secure multi-party computation. In Financial Cryptography and Data Security - 19th International Conference, FC 2015, San Juan, Puerto Rico, January 26-30, 2015, Revised Selected Papers, volume 8975 of LNCS, pages 227--234. Springer, 2015.

[16]

D. Bogdanov, P. Laud, S. Laur, and P. Pullonen. From input private to universally composable secure multi-party computation primitives. In IEEE 27th Computer Security Foundations Symposium, CSF 2014, pages 184--198. IEEE, July 2014.

Digital Library

[17]

D. Bogdanov, S. Laur, and J. Willemson. Sharemind: A framework for fast privacy-preserving computations. In S. Jajodia and J. López, editors, Computer Security - ESORICS 2008, 13th European Symposium on Research in Computer Security, Málaga, Spain, October 6-8, 2008. Proceedings, volume 5283 of Lecture Notes in Computer Science, pages 192--206. Springer, 2008.

Digital Library

[18]

Z. Brakerski, A. Langlois, C. Peikert, O. Regev, and D. Stehlé. Classical hardness of learning with errors. In D. Boneh, T. Roughgarden, and J. Feigenbaum, editors, Symposium on Theory of Computing Conference, STOC'13, Palo Alto, CA, USA, June 1-4, 2013, pages 575--584. ACM, 2013.

Digital Library

[19]

Z. Brakerski and V. Vaikuntanathan. Efficient fully homomorphic encryption from (standard) LWE. In R. Ostrovsky, editor, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, pages 97--106. IEEE Computer Society, 2011.

Digital Library

[20]

J. A. Buchmann, R. Lindner, and M. Rückert. Explicit hard instances of the shortest vector problem. In J. A. Buchmann and J. Ding, editors, Post-Quantum Cryptography, Second International Workshop, PQCrypto 2008, Cincinnati, OH, USA, October 17-19, 2008, Proceedings, volume 5299 of Lecture Notes in Computer Science, pages 79--94. Springer, 2008.

Digital Library

[21]

C. Chekuri, K. Jansen, J. D. P. Rolim, and L. Trevisan, editors. Approximation, Randomization and Combinatorial Optimization, Algorithms and Techniques, 8th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2005 and 9th InternationalWorkshop on Randomization and Computation, RANDOM 2005, Berkeley, CA, USA, August 22-24, 2005, Proceedings, volume 3624 of Lecture Notes in Computer Science. Springer, 2005.

[22]

A. Duc, F. Tramèr, and S. Vaudenay. Better algorithms for LWE and LWR. In E. Oswald and M. Fischlin, editors, Advances in Cryptology - EUROCRYPT 2015 - 34th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Sofia, Bulgaria, April 26-30, 2015, Proceedings, Part I, volume 9056 of Lecture Notes in Computer Science, pages 173--202. Springer, 2015.

[23]

L. Ducas, A. Durmus, T. Lepoint, and V. Lyubashevsky. Lattice signatures and bimodal gaussians. In R. Canetti and J. A. Garay, editors, Advances in Cryptology - CRYPTO 2013 - 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part I, volume 8042 of Lecture Notes in Computer Science, pages 40--56. Springer, 2013.

[24]

L. Kamm. Privacy-preserving statistical analysis using secure multi-party computation. PhD thesis, University of Tartu, 2015.

[25]

A. Langlois, S. Ling, K. Nguyen, and H. Wang. Lattice-based group signature scheme with verifier-local revocation. In PKC 2014, Buenos Aires, Argentina, March 26-28, 2014. Proceedings, pages 345--361, 2014.

Digital Library

[26]

R. Lindner and C. Peikert. Better key sizes (and attacks) for LWE-based encryption. In A. Kiayias, editor, Topics in Cryptology - CT-RSA 2011 - The Cryptographers' Track at the RSA Conference 2011, San Francisco, CA, USA, February 14-18, 2011. Proceedings, volume 6558 of Lecture Notes in Computer Science, pages 319--339. Springer, 2011.

Digital Library

[27]

M. Liu and P. Q. Nguyen. Solving BDD by enumeration: An update. In E. Dawson, editor, Topics in Cryptology - CT-RSA 2013 - The Cryptographers' Track at the RSA Conference 2013, San Francisco,CA, USA, February 25-March 1, 2013. Proceedings, volume 7779 of Lecture Notes in Computer Science, pages 293--309. Springer, 2013.

Digital Library

[28]

V. Lyubashevsky. The parity problem in the presence of noise, decoding random linear codes, and the subset sum problem. In Chekuri et al.citeDBLP:conf/approx/2005, pages 378--389.

Digital Library

[29]

T. Plantard and M. Schneider. Creating a challenge for ideal lattices. IACR Cryptology ePrint Archive, 2013:39, 2013.

[30]

O. Regev. On lattices, learning with errors, random linear codes, and cryptography. In H. N. Gabow and R. Fagin, editors, Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005, pages 84--93. ACM, 2005.

Digital Library

[31]

O. Regev. On lattices, learning with errors, random linear codes, and cryptography. J. ACM, 56(6):34:1--34:40, Sept. 2009.

Digital Library

[32]

T. Yasuda, X. Dahan, Y. Huang, T. Takagi, and K. Sakurai. MQ challenge: Hardness evaluation of solving multivariate quadratic problems. IACR Cryptology ePrint Archive, 2015:275, 2015.

Cited By

Chua LChen HSong YLauter K(2024)On the Concrete Security of LWE With Small SecretLa Matematica10.1007/s44007-024-00111-33:3(1032-1068)Online publication date: 7-Jun-2024
https://doi.org/10.1007/s44007-024-00111-3
Nolte NMalhou MWenger EStevens SLi CCharton FLauter K(2024)The Cool and the Cruel: Separating Hard Parts of LWE SecretsProgress in Cryptology - AFRICACRYPT 202410.1007/978-3-031-64381-1_19(428-453)Online publication date: 3-Jul-2024
https://doi.org/10.1007/978-3-031-64381-1_19
Malina LDzurenda PRicci SHajny JSrivastava GMatulevicius RAffia ALaurent MSultan NTang Q(2021)Post-Quantum Era Privacy Protection for Intelligent InfrastructuresIEEE Access10.1109/ACCESS.2021.30622019(36038-36077)Online publication date: 2021
https://doi.org/10.1109/ACCESS.2021.3062201
Show More Cited By

Index Terms

Creating Cryptographic Challenges Using Multi-Party Computation: The LWE Challenge
1. Security and privacy
  1. Cryptography
    1. Cryptanalysis and other attacks
    2. Public key (asymmetric) techniques
      1. Digital signatures
      2. Public key encryption
  2. Security services
    1. Privacy-preserving protocols

Recommendations

Revocable attribute-based encryption from standard lattices
Abstract
Attribute-based encryption (ABE) is an attractive extension of public key encryption, which provides fine-grained and role-based access to encrypted data. In its key-policy flavor, the secret key is associated with an access policy and ...
Highlights
- Our scheme is based on the learning with errors (LWE) problem, which is believed to be quantum-resistant.
(Leveled) Fully Homomorphic Encryption without Bootstrapping
Special issue on innovations in theoretical computer science 2012 - Part II

We present a novel approach to fully homomorphic encryption (FHE) that dramatically improves performance and bases security on weaker assumptions. A central conceptual contribution in our work is a new way of constructing leveled, fully homomorphic ...
Anonymous lattice-based broadcast encryption
ICT-EurAsia'13: Proceedings of the 2013 international conference on Information and Communication Technology

In this paper we propose a lattice-based anonymous broadcast encryption scheme obtained by translating the broadcast encryption scheme of Paterson et al. [7] into the lattices environment. We use two essential cryptographic primitives for our ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

AsiaPKC '16: Proceedings of the 3rd ACM International Workshop on ASIA Public-Key Cryptography

May 2016

70 pages

ISBN:9781450342865

DOI:10.1145/2898420

Program Chairs:
Keita Emura
National Institute of Information and Communications Technology, Japan
,
Goichiro Hanaoka
National Institute of Advanced Industrial Science and Technology, Japan
,
Rui Zhang
Chinese Academy of Sciences, China

Copyright © 2016 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGSAC: ACM Special Interest Group on Security, Audit, and Control

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 May 2016

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Deutsche Forschungsgemeinschaft

Conference

ASIA CCS '16

Sponsor:

SIGSAC

ASIA CCS '16: ACM Asia Conference on Computer and Communications Security

May 30, 2016

Xi'an, China

Acceptance Rates

AsiaPKC '16 Paper Acceptance Rate 7 of 24 submissions, 29%;

Overall Acceptance Rate 36 of 103 submissions, 35%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
255
Total Downloads

Downloads (Last 12 months)12
Downloads (Last 6 weeks)2

Reflects downloads up to 15 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Chua LChen HSong YLauter K(2024)On the Concrete Security of LWE With Small SecretLa Matematica10.1007/s44007-024-00111-33:3(1032-1068)Online publication date: 7-Jun-2024
https://doi.org/10.1007/s44007-024-00111-3
Nolte NMalhou MWenger EStevens SLi CCharton FLauter K(2024)The Cool and the Cruel: Separating Hard Parts of LWE SecretsProgress in Cryptology - AFRICACRYPT 202410.1007/978-3-031-64381-1_19(428-453)Online publication date: 3-Jul-2024
https://doi.org/10.1007/978-3-031-64381-1_19
Malina LDzurenda PRicci SHajny JSrivastava GMatulevicius RAffia ALaurent MSultan NTang Q(2021)Post-Quantum Era Privacy Protection for Intelligent InfrastructuresIEEE Access10.1109/ACCESS.2021.30622019(36038-36077)Online publication date: 2021
https://doi.org/10.1109/ACCESS.2021.3062201
Nakamura STateiwa NKinjo KIkematsu YYasuda MFujisawa K(2020)Solving the Search-LWE Problem by Lattice Reduction over Projected BasesProceedings of the Sixth International Conference on Mathematics and Computing10.1007/978-981-15-8061-1_3(29-42)Online publication date: 11-Dec-2020
https://doi.org/10.1007/978-981-15-8061-1_3
TAKAGI T(2018)Recent Developments in Post-Quantum CryptographyIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences10.1587/transfun.E101.A.3E101.A:1(3-11)Online publication date: 2018
https://doi.org/10.1587/transfun.E101.A.3
WANG YAONO YTAKAGI T(2018)Hardness Evaluation for Search LWE Problem Using Progressive BKZ SimulatorIEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences10.1587/transfun.E101.A.2162E101.A:12(2162-2170)Online publication date: 1-Dec-2018
https://doi.org/10.1587/transfun.E101.A.2162
Wang YAono YTakagi T(2018)An Experimental Study of Kannan’s Embedding Technique for the Search LWE ProblemInformation and Communications Security10.1007/978-3-319-89500-0_47(541-553)Online publication date: 10-Apr-2018
https://doi.org/10.1007/978-3-319-89500-0_47
Yasuda MYamaguchi JOoka MNakamura S(2018)Development of a Dual Version of DeepBKZ and Its Application to Solving the LWE ChallengeProgress in Cryptology – AFRICACRYPT 201810.1007/978-3-319-89339-6_10(162-182)Online publication date: 6-Apr-2018
https://doi.org/10.1007/978-3-319-89339-6_10
Mariano ALaarhoven TCorreia FRodrigues MFalcao G(2017)A Practical View of the State-of-the-Art of Lattice-Based CryptanalysisIEEE Access10.1109/ACCESS.2017.27481795(24184-24202)Online publication date: 2017
https://doi.org/10.1109/ACCESS.2017.2748179
Yasuda M(2017)Simple Analysis of Key Recovery Attack Against LWEMathematical Modelling for Next-Generation Cryptography10.1007/978-981-10-5065-7_12(221-238)Online publication date: 26-Jul-2017
https://doi.org/10.1007/978-981-10-5065-7_12

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents