More Web Proxy on the site http://driver.im/

Article

Estimate All the {LWE, NTRU} Schemes!

Authors:

Martin R. Albrecht,

Benjamin R. Curtis,

Eamonn W. Postlethwaite,

Fernando Virdia,

Thomas WundererAuthors Info & Claims

Security and Cryptography for Networks: 11th International Conference, SCN 2018, Amalfi, Italy, September 5–7, 2018, Proceedings

Pages 351 - 367

https://doi.org/10.1007/978-3-319-98113-0_19

Published: 05 September 2018 Publication History

Abstract

We consider all LWE- and NTRU-based encryption, key encapsulation, and digital signature schemes proposed for standardisation as part of the Post-Quantum Cryptography process run by the US National Institute of Standards and Technology (NIST). In particular, we investigate the impact that different estimates for the asymptotic runtime of (block-wise) lattice reduction have on the predicted security of these schemes. Relying on the “LWE estimator” of Albrecht et al., we estimate the cost of running primal and dual lattice attacks against every LWE-based scheme, using every cost model proposed as part of a submission. Furthermore, we estimate the security of the proposed NTRU-based schemes against the primal attack under all cost models for lattice reduction.

References

[1]

Ajtai, M.: Generating hard instances of lattice problems (extended abstract). In: 28th ACM STOC, pp. 99–108. ACM Press, New York, May 1996

[2]

Ajtai, M., Kumar, R., Sivakumar, D.: A sieve algorithm for the shortest lattice vector problem. In: 33rd ACM STOC, pp. 601–610. ACM Press, New York, July 2001

[3]

Albrecht MR Coron J-S and Nielsen JB On dual lattice attacks against small-secret LWE and parameter choices in HElib and SEAL Advances in Cryptology – EUROCRYPT 2017 2017 Cham Springer 103-129

[4]

Albrecht, M.R., Cid, C., Faugère, J., Perret, L.: Algebraic algorithms for LWE. Cryptology ePrint Archive, Report 2014/1018 (2014). http://eprint.iacr.org/2014/1018

[5]

Albrecht MR, Faugère J-C, Fitzpatrick R, and Perret L Krawczyk H Lazy modulus switching for the BKW algorithm on LWE Public-Key Cryptography – PKC 2014 2014 Heidelberg Springer 429-445

Digital Library

[6]

Albrecht MR, Göpfert F, Virdia F, and Wunderer T Takagi T and Peyrin T Revisiting the expected cost of solving uSVP and applications to LWE Advances in Cryptology – ASIACRYPT 2017 2017 Cham Springer 297-322

[7]

Albrecht MR, Player R, and Scott S On the concrete hardness of learning with errors J. Math. Cryptol. 2015 9 3 169-203

[8]

Alkim, E., Ducas, L., Pöppelmann, T., Schwabe, P.: Post-quantum key exchange - a new hope. In: Holz, T., Savage, S. (eds.) 25th USENIX Security Symposium, USENIX Security 2016, pp. 327–343. USENIX Association (2016)

[9]

Applebaum B, Cash D, Peikert C, and Sahai A Halevi S Fast cryptographic primitives and circular-secure encryption based on hard learning problems Advances in Cryptology - CRYPTO 2009 2009 Heidelberg Springer 595-618

Digital Library

[10]

Arora S and Ge R Aceto L, Henzinger M, and Sgall J New algorithms for learning in presence of errors Automata, Languages and Programming 2011 Heidelberg Springer 403-415

[11]

Bai S and Galbraith SD Susilo W and Mu Y Lattice decoding attacks on binary LWE Information Security and Privacy 2014 Cham Springer 322-337

[12]

Bansarkhani, R.E.: Kindi. Technical report, NIST (2017)

[13]

Becker, A., Ducas, L., Gama, N., Laarhoven, T.: New directions in nearest neighbor searching with applications to lattice sieving. In: Krauthgamer, R. (ed.) 27th SODA, pp. 10–24. ACM-SIAM, New York (2016)

[14]

Bernstein, D.J.: Table of ciphertext and key sizes for the NIST candidate algorithms (2017). https://groups.google.com/a/list.nist.gov/d/msg/pqc-forum/1lDNio0sKq4/xjqy4K6SAgAJ

[15]

Bernstein, D.J.: Comment on PQC forum (2018). https://groups.google.com/a/list.nist.gov/d/msg/pqc-forum/h4_LCVNejCI/FyV5hgnqBAAJ

[16]

Bernstein, D.J., Chuengsatiansup, C., Lange, T., van Vredendaal, C.: Ntru prime. Technical report, NIST (2017)

[17]

Bindel, N., et al.: qTESLA. Technical report, NIST (2017)

[18]

Bos, J.W., et al.: Frodo: Take off the ring! practical, quantum-secure key exchange from LWE. In: Weippl, E.R., Katzenbeisser, S., Kruegel, C., Myers, A.C., Halevi, S. (eds.) ACM CCS 16, pp. 1006–1018. ACM Press, New York, October 2016

[19]

Chen, Y.: Réduction de réseau et sécurité concréte du chiffrement complétement homomorphe. Ph.D. thesis, Paris 7 (2013)

[20]

Chen Y and Nguyen PQ Lee DH and Wang X BKZ 2.0: better lattice security estimates Advances in Cryptology – ASIACRYPT 2011 2011 Heidelberg Springer 1-20

Digital Library

[21]

Cheon JH, Han K, Kim J, Lee C, and Son Y Hong S and Park JH A practical post-quantum public-key cryptosystem based on

spLWE

Information Security and Cryptology – ICISC 2016 2017 Cham Springer 51-74

Digital Library

[22]

Cheon, J.H., et al.: Lizard. Technical report, NIST (2017)

[23]

Coppersmith D and Shamir A Fumy W Lattice attacks on NTRU Advances in Cryptology — EUROCRYPT 1997 1997 Heidelberg Springer 52-61

[24]

D’Anvers, J., Karmakar, A., Roy, S.S., Vercauteren, F.: Saber. Technical report, NIST (2017)

[25]

The FPLLL Development Team: fplll, a lattice reduction library (2017). https://github.com/fplll/fplll

[26]

Ding, J., Takagi, T., Gao, X., Wang, Y.: Ding key exchange. Technical report, NIST (2017)

[27]

Fincke U and Pohst M Improved methods for calculating vectors of short length in a lattice, including a complexity analysis Math. Comput. 1985 44 170 463-463

[28]

Fujita, R.: Table of underlying problems of the NIST candidate algorithms (2017). https://groups.google.com/a/list.nist.gov/d/msg/pqc-forum/1lDNio0sKq4/7zXvtfdZBQAJ

[29]

Gama, N., Nguyen, P.Q.: Finding short lattice vectors within Mordell’s inequality. In: Ladner, R.E., Dwork, C. (eds.) 40th ACM STOC, pp. 207–216. ACM Press, New York, May 2008

[30]

Garcia-Morchon, O., Zhang, Z., Bhattacharya, S., Rietman, R., Tolhuizen, L., Torre-Arce, J.: Round2. Technical report, NIST (2017)

[31]

Grover, L.K.: A fast quantum mechanical algorithm for database search. In: 28th ACM STOC, pp. 212–219. ACM Press, New York, May 1996

[32]

Guo Q, Johansson T, Mårtensson E, and Stankovski P Takagi T and Peyrin T Coded-BKW with sieving Advances in Cryptology – ASIACRYPT 2017 2017 Cham Springer 323-346 Lecture Notes in Computer Science

[33]

Guo Q, Johansson T, and Stankovski P Gennaro R and Robshaw M Coded-BKW: solving LWE using lattice codes Advances in Cryptology – CRYPTO 2015 2015 Heidelberg Springer 23-42 Lecture Notes in Computer Science

Digital Library

[34]

Hamburg, M.: Three bears. Technical report, NIST (2017)

[35]

Hoffstein, J., Pipher, J., Schanck, J.M., Silverman, J.H., Whyte, W., Zhang, Z.: Choosing parameters for NTRUEncrypt. Cryptology ePrint Archive, Report 2015/708 (2015). http://eprint.iacr.org/2015/708

[36]

Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: a new high speed public-key cryptosystem. Technical report, Draft distributed at CRYPTO96 (1996). https://cdn2.hubspot.net/hubfs/49125/downloads/ntru-orig.pdf

[37]

Hoffstein J, Pipher J, and Silverman JH Buhler JP NTRU: a ring-based public key cryptosystem Algorithmic Number Theory 1998 Heidelberg Springer 267-288

[38]

Howgrave-Graham N Menezes A A hybrid lattice-reduction and meet-in-the-middle attack against NTRU Advances in Cryptology - CRYPTO 2007 2007 Heidelberg Springer 150-169

[39]

Kannan, R.: Improved algorithms for integer programming and related lattice problems. In: 15th ACM STOC, pp. 193–206. ACM Press, New York, April 1983

[40]

Kannan, R.: Minkowski’s convex body theorem and integer programming. Math. Oper. Res. 415–440 (1987)

[41]

Kirchner P and Fouque P-A Gennaro R and Robshaw M An improved BKW algorithm for LWE with applications to cryptography and lattices Advances in Cryptology – CRYPTO 2015 2015 Heidelberg Springer 43-62

Digital Library

[42]

Kirchner P and Fouque P-A Coron J-S and Nielsen JB Revisiting lattice attacks on overstretched NTRU parameters Advances in Cryptology – EUROCRYPT 2017 2017 Cham Springer 3-26

[43]

Laarhoven, T.: Search problems in cryptography: from fingerprinting to lattice sieving. Ph.D. thesis, Eindhoven University of Technology (2015)

[44]

Laarhoven T Gennaro R and Robshaw M Sieving for shortest vectors in lattices using angular locality-sensitive hashing Advances in Cryptology – CRYPTO 2015 2015 Heidelberg Springer 3-22

Digital Library

[45]

Laarhoven T, Mosca M, and van de Pol J Finding shortest lattice vectors faster using quantum search Des. Codes Crypt. 2015 77 2–3 375-400

Digital Library

[46]

Langlois A and Stehlé D Worst-case to average-case reductions for module lattices Des. Codes Crypt. 2015 75 3 565-599

Digital Library

[47]

Lindner R and Peikert C Kiayias A Better key sizes (and attacks) for LWE-based encryption Topics in Cryptology – CT-RSA 2011 2011 Heidelberg Springer 319-339

[48]

Lu, X., Liu, Y., Jia, D., Xue, H., He, J., Zhang, Z.: Lac. Technical report, NIST (2017)

[49]

Lyubashevsky, V., et al.: Crystals-dilithium. Technical report, NIST (2017)

[50]

Lyubashevsky V, Peikert C, and Regev O Gilbert H On ideal lattices and learning with errors over rings Advances in Cryptology – EUROCRYPT 2010 2010 Heidelberg Springer 1-23

Digital Library

[51]

May A and Silverman JH Silverman JH Dimension reduction methods for convolution modular lattices Cryptography and Lattices 2001 Heidelberg Springer 110-125

[52]

Micciancio D and Regev O Bernstein DJ, Buchmann J, and Dahmen E Lattice-based cryptography Post-Quantum Cryptography 2009 Heidelberg Springer 147-191

[53]

Micciancio, D., Walter, M.: Fast lattice point enumeration with minimal overhead. In: Indyk, P. (ed.) 26th SODA, pp. 276–294. ACM-SIAM, New York, January 2015

[54]

Moody, D.: The NIST post quantum cryptography “competition” (2017). https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/asiacrypt-2017-moody-pqc.pdf

[55]

Naehrig, M., et al.: Frodokem. Technical report, NIST (2017)

[56]

Nguyen, P.: Comment on PQC forum (2018). https://groups.google.com/a/list.nist.gov/forum/#!topic/pqc-forum/nZBIBvYmmUI

[57]

NIST: Submission requirements and evaluation criteria for the Post-Quantum Cryptography standardization process, December 2016. http://csrc.nist.gov/groups/ST/post-quantum-crypto/documents/call-for-proposals-final-dec-2016.pdf

[58]

NIST: Performance testing of the NIST candidate algorithms (2017). https://drive.google.com/file/d/1g-l0bPa-tReBD0Frgnz9aZXpO06PunUa/view

[59]

Phong, L.T., Hayashi, T., Aono, Y., Moriai, S.: Lotus. Technical report, NIST (2017)

[60]

Poppelmann, T., et al.: Newhope. Technical report, NIST (2017)

[61]

Prest, T., et al.: Falcon. Technical report, NIST (2017)

[62]

Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: Gabow, H.N., Fagin, R. (eds.) 37th ACM STOC, pp. 84–93. ACM Press, New York, May 2005

[63]

Saarinen, M.O.: Hila5. Technical report, NIST (2017)

[64]

Schanck, J.: Practical lattice cryptosystems: NTRUEncrypt and NTRUMLS. Master’s thesis, University of Waterloo (2015)

[65]

Schanck, J.M., Hulsing, A., Rijneveld, J., Schwabe, P.: Ntru-hrss-kem. Technical report, NIST (2017)

[66]

Schnorr C and Euchner M Lattice basis reduction: improved practical algorithms and solving subset sum problems Math. Program. 1994 66 181-199

Digital Library

[67]

Schnorr CP Alt H and Habib M Lattice reduction by random sampling and birthday methods STACS 2003 2003 Heidelberg Springer 145-156

[68]

Schwabe, P., et al.: Crystals-kyber. Technical report, NIST (2017)

[69]

Seo, M., Park, J.H., Lee, D.H., Kim, S., Lee, S.: Emblem and r.emblem. Technical report, NIST (2017)

[70]

Smart, N.P., et al.: Lima. Technical report, NIST (2017)

[71]

Stehlé D, Steinfeld R, Tanaka K, and Xagawa K Matsui M Efficient public key encryption based on ideal lattices Advances in Cryptology – ASIACRYPT 2009 2009 Heidelberg Springer 617-635

Digital Library

[72]

Steinfeld, R., Sakzad, A., Zhao, R.K.: Titanium. Technical report, NIST (2017)

[73]

Wunderer, T.: Revisiting the hybrid attack: improved analysis and refined security estimates. Cryptology ePrint Archive, Report 2016/733 (2016). http://eprint.iacr.org/2016/733

[74]

Zhang, Z., Chen, C., Hoffstein, J., Whyte, W.: NTRUEncrypt. Technical report, NIST (2017)

[75]

Zhang, Z., Chen, C., Hoffstein, J., Whyte, W.: pqNTRUSign. Technical report, NIST (2017)

[76]

Zhao, Y., Jin, Z., Gong, B., Sui, G.: KCL (pka OKCN/AKCN/CNKE). Technical report, NIST (2017)

Cited By

Kundu SNorga QKarmakar AGangopadhyay SBermudo Mera JVerbauwhede I(2024)Scabbard: An Exploratory Study on Hardware Aware Design Choices of Learning with Rounding-based Key Encapsulation MechanismsACM Transactions on Embedded Computing Systems10.1145/369620824:1(1-40)Online publication date: 20-Sep-2024
https://dl.acm.org/doi/10.1145/3696208
Narisada SOkada HFukushima KNishide TBergamaschi FCostache ARohloff K(2024)Time-Memory Trade-off Algorithms for Homomorphically Evaluating Look-up Table in TFHEProceedings of the 12th Workshop on Encrypted Computing & Applied Homomorphic Cryptography10.1145/3689945.3694801(1-10)Online publication date: 19-Nov-2024
https://dl.acm.org/doi/10.1145/3689945.3694801
Krastev ASamardzic NLangowski SDevadas SSanchez D(2024)A Tensor Compiler with Automatic Data Packing for Simple and Efficient Fully Homomorphic EncryptionProceedings of the ACM on Programming Languages10.1145/36563828:PLDI(126-150)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656382
Show More Cited By

Recommendations

NTWE: A Natural Combination of NTRU and LWE
Post-Quantum Cryptography
Abstract
Lattice-based cryptosystems are some of the primary post-quantum secure alternatives to the asymmetric cryptography that is used today. These lattice-based cryptosystems typically rely on the hardness of some version of either the NTRU or the LWE ...
FINAL: Faster FHE Instantiated with NTRU and LWE
Advances in Cryptology – ASIACRYPT 2022
Abstract
The NTRU problem is a promising candidate to build efficient Fully Homomorphic Encryption (FHE). However, all the existing proposals (e.g. LTV, YASHE) need so-called ‘overstretched’ parameters of NTRU to enable homomorphic operations. It was shown ...
AKC-Based Revocable ABE Schemes from LWE Assumption
The emergence of quantum computing threatens many classical cryptographic schemes, leading to the innovations in public-key cryptography for postquantum cryptography primitives and protocols that resist to quantum attacks. Lattice-based cryptography is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

Security and Cryptography for Networks: 11th International Conference, SCN 2018, Amalfi, Italy, September 5–7, 2018, Proceedings

Sep 2018

579 pages

ISBN:978-3-319-98112-3

DOI:10.1007/978-3-319-98113-0

Editors:
Dario Catalano
University of Catania, Catania, Italy
,
Roberto De Prisco
University of Salerno, Fisciano, Italy

© Springer Nature Switzerland AG 2018.

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 05 September 2018

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 16 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kundu SNorga QKarmakar AGangopadhyay SBermudo Mera JVerbauwhede I(2024)Scabbard: An Exploratory Study on Hardware Aware Design Choices of Learning with Rounding-based Key Encapsulation MechanismsACM Transactions on Embedded Computing Systems10.1145/369620824:1(1-40)Online publication date: 20-Sep-2024
https://dl.acm.org/doi/10.1145/3696208
Narisada SOkada HFukushima KNishide TBergamaschi FCostache ARohloff K(2024)Time-Memory Trade-off Algorithms for Homomorphically Evaluating Look-up Table in TFHEProceedings of the 12th Workshop on Encrypted Computing & Applied Homomorphic Cryptography10.1145/3689945.3694801(1-10)Online publication date: 19-Nov-2024
https://dl.acm.org/doi/10.1145/3689945.3694801
Krastev ASamardzic NLangowski SDevadas SSanchez D(2024)A Tensor Compiler with Automatic Data Packing for Simple and Efficient Fully Homomorphic EncryptionProceedings of the ACM on Programming Languages10.1145/36563828:PLDI(126-150)Online publication date: 20-Jun-2024
https://dl.acm.org/doi/10.1145/3656382
Samardzic NSanchez DTsafrir DMusuvathi MGupta RAbu-Ghazaleh N(2024)BitPacker: Enabling High Arithmetic Efficiency in Fully Homomorphic Encryption AcceleratorsProceedings of the 29th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 210.1145/3620665.3640397(137-150)Online publication date: 27-Apr-2024
https://dl.acm.org/doi/10.1145/3620665.3640397
Tang YPan DYe QLi YYu J(2024)Event-Oriented Linkable Group Signature From LatticeIEEE Transactions on Consumer Electronics10.1109/TCE.2024.336418870:1(2224-2234)Online publication date: 5-Mar-2024
https://dl.acm.org/doi/10.1109/TCE.2024.3364188
Bindel NBonnetain XTiepelt MVirdia F(2024)Quantum Lattice Enumeration in Limited DepthAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68391-6_3(72-106)Online publication date: 18-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-68391-6_3
Jain ALin HSaha S(2024)A Systematic Study of Sparse LWEAdvances in Cryptology – CRYPTO 202410.1007/978-3-031-68382-4_7(210-245)Online publication date: 18-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-68382-4_7
Xia WWang LWang GGu DWang B(2024)A Refined Hardness Estimation of LWE in Two-Step ModePublic-Key Cryptography – PKC 202410.1007/978-3-031-57725-3_1(3-35)Online publication date: 15-Apr-2024
https://dl.acm.org/doi/10.1007/978-3-031-57725-3_1
Albrecht MBai SLi JRowell J(2021)Lattice Reduction with Approximate Enumeration OraclesAdvances in Cryptology – CRYPTO 202110.1007/978-3-030-84245-1_25(732-759)Online publication date: 16-Aug-2021
https://dl.acm.org/doi/10.1007/978-3-030-84245-1_25
Postlethwaite EVirdia F(2021)On the Success Probability of Solving Unique SVP via BKZPublic-Key Cryptography – PKC 202110.1007/978-3-030-75245-3_4(68-98)Online publication date: 10-May-2021
https://dl.acm.org/doi/10.1007/978-3-030-75245-3_4
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents