Movatterモバイル変換

Part of the book series:Lecture Notes in Computer Science ((LNCS,volume 14154))

Included in the following conference series:

International Conference on Post-Quantum Cryptography

1115Accesses

Abstract

The original NTRU cryptosystem from 1998 can be considered the starting point of the great success story of lattice-based cryptography. Modern NTRU versions like NTRU-HPS and NTRU-HRSS are round-3 finalists in NIST’s selection process, and alsoCrystals-Kyber and especiallyFalcon are heavily influenced by NTRU.

Coppersmith and Shamir proposed to attack NTRU via lattice basis reduction, and variations of the Coppersmith-Shamir lattice have been successfully applied to solve official NTRU challenges by Security Innovations, Inc. up to dimension$n=173$.

In our work, we provide the tools to attack modern NTRU versions, both by the design of a proper lattice basis, as well as by tuning the modernBKZ with lattice sieving algorithm from the G6K library to NTRU needs.

Letn be prime,$\varPhi _n := (X^n-1)/(X-1)$, and let$\mathbb {Z}_q[X]/(\varPhi _n)$ be the cyclotomic ring. As opposed to the common belief, we show that switching from the Coppersmith-Shamir lattice to a basis for the cyclotomic ring provides benefits. To this end, we slightly enhance theLWE with Hints framework by Dachman-Soled, Ducas, Gong, Rossi with the concept of projections againstalmost-parallel hints.

Using our new lattice bases, we set the first cryptanalysis landmarks for NTRU-HPS with$n \in [101,171]$ and for NTRU-HRSS with$n \in [101,211]$. As a numerical example, we break our largest HPS-171 instance using the cyclotomic ring basis within 83 core days, whereas the Coppersmith-Shamir basis requires 172 core days.

We also break one more official NTRU challenges by Security Innovation, Inc., originally worth 1000$, in dimension$n=181$ in 20 core years. Our experiments run up to BKZ blocksizes beyond 100, a regime that has not been reached in analyzing cryptosystems so far.

This is a preview of subscription content,log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic

¥17,985 /Month

Get 10 units per month
Download Article/Chapter or eBook
1 Unit = 1 Article or 1 Chapter
Cancel anytime

Subscribe now

Buy Now

Chapter: JPY 3498; Price includes VAT (Japan)

eBook: JPY 12583; Price includes VAT (Japan)

Softcover Book: JPY 15729; Price includes VAT (Japan)

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

On Dual Lattice Attacks Against Small-Secret LWE and Parameter Choices in HElib and SEAL

NTRU Prime: Reducing Attack Surface at Low Cost

NFLlib: NTT-Based Fast Lattice Library

Notes

1.
As opposed to the set$\mathcal {T}(\omega )$, defined in Eq. (3), the elements of$\mathcal {T}_{\mathsf {Ch.}}(d_i)$ are of degree at most$n-1$, instead of$n-2$. In addition, they have$2d_i$ non-zero coefficients, instead of$\omega $.
2.
We assume that a multiple of$\textbf{v}$ is included in$\mathcal {L}$. For an integral vector$\textbf{v}$ and aq-ary lattice$\mathcal {L}$, this certainly is the case, since$q \textbf{v} \in \mathcal {L}$. If$\mathcal {L}$ contains no multiple of$\textbf{v}$, then$\pi _\textbf{v}(\mathcal {L})$ might not be a lattice.
3.
Notice that there is no monomial of degree$k-1$ in Eq. (19), sincep has no monomial of degree$n-1$.
4.
Even thoughg is not a ternary polynomial in NTRU-HRSS, Lemma 3.1 still implies thatg is invertible, sinceg is the product of two ternary (and therefore invertible) polynomials, see Eq. (8).
5.
In [ADH+19], the crossover point between enumeration and sieving was observed at dimension 70. However, we gain additional speed-up from parallelized sieving.
6.
When DSD and SKR happen at the same blocksize, we are still in the overstretched regime. We are in the non-overstretched regime only if SKR happensbefore DSD.
7.
Equation (31) easily follows from the Chinese Remainder Theorem.

References

Aragon, N., et al.: BIKE: bit flipping key encapsulation (2020).https://bikesuite.org/files/v5.0/BIKE_Spec. 2022.10.10.1.pdf
Albrecht, M.R., et al.: Classic McEliece: conservative code-based cryptography (2020).https://classic.mceliece.org/nist/mceliece-20201010.pdf
Albrecht, M.R., Bai, S., Fouque, P.-A., Kirchner, P., Stehlé, D., Wen, W.: Faster enumeration-based lattice reduction: root Hermite factor $k^{1/(2k)}$ Time $k^{k/8+o(k)}$. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12171, pp. 186–212. Springer, Cham (2020).https://doi.org/10.1007/978-3-030-56880-1_7
Chapter Google Scholar
Albrecht, M.R., Ducas, L.: Lattice attacks on NTRU and LWE: a history of refinements, pp. 15–40 (2021)
Google Scholar
Albrecht, M.R., Ducas, L., Herold, G., Kirshanova, E., Postlethwaite, E.W., Stevens, M.: The general sieve kernel and new records in lattice reduction. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11477, pp. 717–746. Springer, Cham (2019).https://doi.org/10.1007/978-3-030-17656-3_25
Chapter MATH Google Scholar
Alkim, E., Ducas, L., Pöppelmann, T., Schwabe, P.: Post-quantum key exchange - a new hope. In: 25th USENIX Security Symposium, pp. 327–343 (2016)
Google Scholar
Ajtai, M., Kumar, R., Sivakumar, D.: A sieve algorithm for the shortest lattice vector problem. In: STOC 2001, pp. 601–610 (2001)
Google Scholar
Aono, Y., Wang, Y., Hayashi, T., Takagi, T.: Improved progressive BKZ algorithms and their precise cost estimation by sharp simulator. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9665, pp. 789–819. Springer, Heidelberg (2016).https://doi.org/10.1007/978-3-662-49890-3_30
Chapter Google Scholar
Bos, J.W., et al.: CRYSTALS - Kyber: a CCA-secure module-lattice-based KEM. In: 2018 IEEE EuroS &P, pp. 353–367 (2018)
Google Scholar
Chen, C., et al.: PQC round-3 candidate: NTRU. technical report (2019).https://ntru.org/f/ntru-20190330.pdf
Chen, Y., Nguyen, P.Q.: BKZ 2.0: better lattice security estimates. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 1–20. Springer, Heidelberg (2011).https://doi.org/10.1007/978-3-642-25385-0_1
Chapter Google Scholar
Coppersmith, D., Shamir, A.: Lattice attacks on NTRU. In: Fumy, W. (ed.) EUROCRYPT 1997. LNCS, vol. 1233, pp. 52–61. Springer, Heidelberg (1997).https://doi.org/10.1007/3-540-69053-0_5
Chapter Google Scholar
Dachman-Soled, D., Ducas, L., Gong, H., Rossi, M.: LWE with side information: attacks and concrete security estimation. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12171, pp. 329–358. Springer, Cham (2020).https://doi.org/10.1007/978-3-030-56880-1_12
Chapter Google Scholar
Ducas, L., Stevens, M., van Woerden, W.: Advanced lattice sieving on GPUs, with tensor cores. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12697, pp. 249–279. Springer, Cham (2021).https://doi.org/10.1007/978-3-030-77886-6_9
Chapter Google Scholar
The FPLLL development team. FPYLLL, a Python wraper for the FPLLL lattice reduction library, Version: 0.5.7 (2021).https://github.com/fplll/fpylll
The G6K development team. The general sieve kernel (G6K) (2021).https://github.com/fplll/g6k
Ducas, L.: Shortest vector from lattice sieving: a few dimensions for free. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10820, pp. 125–145. Springer, Cham (2018).https://doi.org/10.1007/978-3-319-78381-9_5
Chapter Google Scholar
Ducas, L., van Woerden, W.: NTRU fatigue: how stretched is overstretched? In: Tibouchi, M., Wang, H. (eds.) ASIACRYPT 2021. LNCS, vol. 13093, pp. 3–32. Springer, Cham (2021).https://doi.org/10.1007/978-3-030-92068-5_1
Chapter Google Scholar
Fouque, P.-A., et al.: FALCON: fast-Fourier lattice-based compact signatures over NTRU (2018).https://www.di.ens.fr/~prest/Publications/falcon.pdf
Gentry, C.: Key recovery and message attacks on NTRU-composite. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 182–194. Springer, Heidelberg (2001).https://doi.org/10.1007/3-540-44987-6_12
Chapter Google Scholar
Gama, N., Nguyen, P.Q., Regev, O.: Lattice enumeration using extreme pruning. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 257–278. Springer, Heidelberg (2010).https://doi.org/10.1007/978-3-642-13190-5_13
Chapter Google Scholar
Howgrave-Graham, N.: A hybrid lattice-reduction and meet-in-the-middle attack against NTRU. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 150–169. Springer, Heidelberg (2007).https://doi.org/10.1007/978-3-540-74143-5_9
Chapter MATH Google Scholar
Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: a ring-based public key cryptosystem. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol. 1423, pp. 267–288. Springer, Heidelberg (1998).https://doi.org/10.1007/BFb0054868
Chapter Google Scholar
Hülsing, A., Rijneveld, J., Schanck, J., Schwabe, P.: High-speed key encapsulation from NTRU. In: Fischer, W., Homma, N. (eds.) CHES 2017. LNCS, vol. 10529, pp. 232–252. Springer, Cham (2017).https://doi.org/10.1007/978-3-319-66787-4_12
Chapter Google Scholar
NTRU Securty Innovation Inc. NTRU challenge - answers.https://web.archive.org/web/20151229220714/https://www.securityinnovation.com/uploads/ntru-challenge-parameter-sets-and-public-keys-answers.pdf
NTRU Securty Innovation Inc. NTRU challenge parameter sets and public keys.https://web.archive.org/web/20160310141551/https://www.securityinnovation.com/uploads/ntru-challenge-parameter-sets-and-public-keys-new.pdf
Kannan, R.: Improved algorithms for integer programming and related lattice problems. In: STOC 1983 (1983)
Google Scholar
Kirchner, P., Fouque, P.-A.: Revisiting lattice attacks on overstretched NTRU parameters. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10210, pp. 3–26. Springer, Cham (2017).https://doi.org/10.1007/978-3-319-56620-7_1
Chapter Google Scholar
Lenstra, A.K., Lenstra, H.W., Lovász, L.: Factoring polynomials with rational coefficients. Math. Ann.261, 515–534 (1982)
Article MathSciNet MATH Google Scholar
Liu, M., Nguyen, P.Q.: Solving BDD by enumeration: an update. In: Dawson, E. (ed.) CT-RSA 2013. LNCS, vol. 7779, pp. 293–309. Springer, Heidelberg (2013).https://doi.org/10.1007/978-3-642-36095-4_19
Chapter Google Scholar
Melchor, C.A., et al.: Hamming quasi-cyclic (HQC) (2021).https://pqc-hqc.org/doc/hqc-specification_2021-06-06.pdf
May, A., Silverman, J.H.: Dimension reduction methods for convolution modular lattices. In: Silverman, J.H. (ed.) CaLC 2001. LNCS, vol. 2146, pp. 110–125. Springer, Heidelberg (2001).https://doi.org/10.1007/3-540-44670-2_10
Chapter MATH Google Scholar
Micciancio, D., Voulgaris, P.: Faster exponential time algorithms for the shortest vector problem. In: SODA 2010, pp. 1468–1480 (2010)
Google Scholar
Nguyen, P.Q., Vidick, T.: Sieve algorithms for the shortest vector problem are practical. J. Math. Cryptol.2(2), 181–207 (2008)
Article MathSciNet MATH Google Scholar
Schnorr, C.-P.: A hierarchy of polynomial time lattice basis reduction algorithms. Theor. Comput. Sci.53, 201–224 (1987)
Article MathSciNet MATH Google Scholar
Schnorr, C.P.: Lattice reduction by random sampling and birthday methods. In: Alt, H., Habib, M. (eds.) STACS 2003. LNCS, vol. 2607, pp. 145–156. Springer, Heidelberg (2003).https://doi.org/10.1007/3-540-36494-3_14
Chapter Google Scholar

Download references

Acknowledgments

Elena Kirshanova is supported by the Russian Science Foundation grant N 22-41-04411,https://rscf.ru/project/22-41-04411/. Alexander May and Julian Nowakowski are funded by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – grant 465120249. Alexander May is additionally supported by grant 390781972.

Author information

Authors and Affiliations

Technology Innovation Institute, Abu Dhabi, UAE
Elena Kirshanova
Ruhr-University Bochum, Bochum, Germany
Alexander May & Julian Nowakowski
I.Kant Baltic Federal University, Kaliningrad, Russia
Elena Kirshanova

Authors

Elena Kirshanova
View author publications
You can also search for this author inPubMed Google Scholar
Alexander May
View author publications
You can also search for this author inPubMed Google Scholar
Julian Nowakowski
View author publications
You can also search for this author inPubMed Google Scholar

Corresponding authors

Correspondence toElena Kirshanova,Alexander May orJulian Nowakowski.

Editor information

Editors and Affiliations

Lund University, Lund, Sweden
Thomas Johansson
National Institute of Standards and Technology, Gaithersburg, MD, USA
Daniel Smith-Tone

Rights and permissions

Reprints and permissions

Copyright information

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Kirshanova, E., May, A., Nowakowski, J. (2023). New NTRU Records with Improved Lattice Bases. In: Johansson, T., Smith-Tone, D. (eds) Post-Quantum Cryptography. PQCrypto 2023. Lecture Notes in Computer Science, vol 14154. Springer, Cham. https://doi.org/10.1007/978-3-031-40003-2_7

Download citation

DOI:https://doi.org/10.1007/978-3-031-40003-2_7
Published:10 August 2023
Publisher Name:Springer, Cham
Print ISBN:978-3-031-40002-5
Online ISBN:978-3-031-40003-2
eBook Packages:Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Movatterモバイル変換

New NTRU Records with Improved Lattice Bases

Abstract

Access this chapter

Subscribe and save

Buy Now

Similar content being viewed by others

On Dual Lattice Attacks Against Small-Secret LWE and Parameter Choices in HElib and SEAL

NTRU Prime: Reducing Attack Surface at Low Cost

NFLlib: NTT-Based Fast Lattice Library

Notes

References

Acknowledgments

Author information

Authors and Affiliations

Corresponding authors

Editor information

Editors and Affiliations

Rights and permissions

Copyright information

About this paper

Cite this paper

Download citation

Share this paper

Publish with us

Access this chapter

Subscribe and save

Buy Now