nach oben

Erschienen in:

2023 | OriginalPaper | Buchkapitel

Ideal-SVP is Hard for Small-Norm Uniform Prime Ideals

verfasst von : Joël Felderhoff, Alice Pellet-Mary, Damien Stehlé, Benjamin Wesolowski

Erschienen in: Theory of Cryptography

Verlag: Springer Nature Switzerland

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

The presumed hardness of the Shortest Vector Problem for ideal lattices (Ideal-SVP) has been a fruitful assumption to understand other assumptions on algebraic lattices and as a security foundation of cryptosystems. Gentry [CRYPTO’10] proved that Ideal-SVP enjoys a worst-case to average-case reduction, where the average-case distribution is the uniform distribution over the set of inverses of prime ideals of small algebraic norm (below \(d^{O(d)}\) for cyclotomic fields, where d refers to the field degree). De Boer et al. [CRYPTO’20] obtained another random self-reducibility result for an average-case distribution involving integral ideals of norm \(2^{O(d^2)}\).

In this work, we show that Ideal-SVP for the uniform distribution over inverses of small-norm prime ideals reduces to Ideal-SVP for the uniform distribution over small-norm prime ideals. Combined with Gentry’s reduction, this leads to a worst-case to average-case reduction for the uniform distribution over the set of small-norm prime ideals. Using the reduction from Pellet-Mary and Stehlé [ASIACRYPT’21], this notably leads to the first distribution over NTRU instances with a polynomial modulus whose hardness is supported by a worst-case lattice problem.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel On the Multi-user Security of LWE-Based NIKE

Nächstes Kapitel Revocable Cryptography from Learning with Errors

For the sake of simplicity, we assume for the introduction that we are given a basis of the ring of integers \({\mathcal {O}_K}\) whose vectors have norms \(\le \varDelta _K^{O(1/d)}\cdot d^{O(1)}\).

The bound on the norm is obtained by combining Lemma 4.1 and Theorem 4.5 from [BDPW20].

A replete ideal is a subset of \(K_\mathbb {R}:= K \otimes _\mathbb {Q}\mathbb {R}\) of the form \(\alpha \cdot I\) where \(I \subseteq \mathcal {O}_K\) is an integral ideal of \(\mathcal {O}_K\) and \(\alpha \in K_\mathbb {R}^\times \) is invertible. More details can be found in the preliminaries.

The choice of 4A for the upper bound on the norm of the ideals is not a strict requirement of this theorem. We instantiated the theorem with this value in order to simplify its statement.

[ABD16]

Albrecht, M., Bai, S., Ducas, L.: A subfield lattice attack on overstretched NTRU assumptions. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9814, pp. 153–178. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53018-4_6CrossRef

[Bab86]

Babai, L.: On Lovász’ lattice reduction and the nearest lattice point problem. Combinatorica (1986)

[BDPW20]

de Boer, K., Ducas, L., Pellet-Mary, A., Wesolowski, B.: Random self-reducibility of ideal-SVP via Arakelov random walks. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12171, pp. 243–273. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56880-1_9CrossRef

[BEP22]

Boudgoust, K., Gachon, E., Pellet-Mary, A.: Some easy instances of Ideal-SVP and implications on the partial Vandermonde knapsack problem. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022, vol. 13508. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-15979-4_17CrossRef

[BL94]

Buchmann, J.A., Lenstra, H.W.: Computing maximal orders and factoring over \(\mathbb{Z} _p\). Preprint (1994)

[Boe22]

de Boer, K.: Random Walks on Arakelov Class Groups. Ph.D. thesis, Leiden University (2022). Available on request from the author

[BS96]

Bach, E., Shallit, J.O.: Algorithmic Number Theory: Efficient Algorithms. MIT Press (1996)

[BST+20]

Bhargava, M., Shankar, A., Taniguchi, T., Thorne, F., Tsimerman, J., Zhao, Y.: Bounds on 2-torsion in class groups of number fields and integral points on elliptic curves. J. AMS (2020)

[CDPR16]

Cramer, R., Ducas, L., Peikert, C., Regev, O.: Recovering short generators of principal ideals in cyclotomic rings. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 559–585. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49896-5_20CrossRefMATH

[CDW17]

Cramer, R., Ducas, L., Wesolowski, B.: Short stickelberger class relations and application to ideal-SVP. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10210, pp. 324–348. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56620-7_12CrossRef

[CJL16]

Cheon, J.H., Jeong, J., Lee, C.: An algorithm for NTRU problems and cryptanalysis of the GGH multilinear map without a low-level encoding of zero. LMS J. Comput. Math. (2016)

[Coh96]

Cohen, H.: A Course in Computational Algebraic Number Theory. Springer, Cham (1996)

[FPS22]

Felderhoff, J., Pellet-Mary, A., Stehlé, D.: On module unique-SVP and NTRU. In: Agrawal, S., Lin, D. (eds.) ASIACRYPT 2022. LNCS, vol. 13793, pp. 709–740. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-22969-5_24CrossRef

[Gen09a]

Gentry, C.: A Fully Homomorphic Encryption Scheme. Ph.D. thesis, Stanford University (2009)

[Gen09b]

Gentry, C.: Fully homomorphic encryption using ideal lattices. In: STOC (2009)

[Gen10]

Gentry, C.: Toward basing fully homomorphic encryption on worst-case hardness. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 116–137. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14623-7_7CrossRef

[KF17]

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_1CrossRef

[LM06]

Lyubashevsky, V., Micciancio, D.: Generalized compact knapsacks are collision resistant. In: ICALP (2006)

[LPR10]

Lyubashevsky, V., Peikert, C., Regev, O.: On ideal lattices and learning with errors over rings. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 1–23. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13190-5_1CrossRef

[MG02]

Micciancio, D., Goldwasser, S.: Complexity of Lattice Problems: A Cryptographic Perspective. Springer, New York (2002). https://doi.org/10.1007/978-1-4615-0897-7CrossRefMATH

[Mic02]

Micciancio, D.: Generalized compact knapsacks, cyclic lattices, and efficient one-way functions from worst-case complexity assumptions. In: FOCS (2002)

[Neu13]

Neukirch, J.: Algebraic Number Theory. Springer (2013)

[PHS19]

Pellet-Mary, A., Hanrot, G., Stehlé, D.: Approx-SVP in ideal lattices with pre-processing. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11477, pp. 685–716. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17656-3_24CrossRefMATH

[PML21]

Porter, C., Mendelsohn, A., Ling, C.: Subfield algorithms for Ideal- and Module-SVP based on the decomposition group. IACR Cryptol. ePrint Arch. (2021)

[PR06]

Peikert, C., Rosen, A.: Efficient collision-resistant hashing from worst-case assumptions on cyclic lattices. In: TCC (2006)

[PRS17]

Peikert, C., Regev, O., Stephens-Davidowitz, N.: Pseudorandomness of ring-LWE for any ring and modulus. In: STOC (2017)

[PS21]

Pellet-Mary, A., Stehlé, D.: On the hardness of the NTRU problem. In: Tibouchi, M., Wang, H. (eds.) ASIACRYPT 2021. LNCS, vol. 13090, pp. 3–35. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-92062-3_1CrossRef

[PXWC21]

Pan, Y., Xu, J., Wadleigh, N., Cheng, Q.: On the ideal shortest vector problem over random rational primes. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12696, pp. 559–583. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77870-5_20CrossRef

[Reg05]

Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: STOC (2005)

[Sho94]

Shor, P.W.: Algorithms for quantum computation: discrete logarithms and factoring. In: FOCS (1994)

[SSTX09]

Stehlé, D., Steinfeld, R., Tanaka, K., Xagawa, K.: Efficient public key encryption based on ideal lattices. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 617–635. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-10366-7_36CrossRef

[Web08]

Weber, H.: Lehrbuch der algebra, vol. ii. Vieweg und Sohn, Braunschweig (1908)

Titel: Ideal-SVP is Hard for Small-Norm Uniform Prime Ideals
verfasst von: Joël Felderhoff
Alice Pellet-Mary
Damien Stehlé
Benjamin Wesolowski
Verlag: Springer Nature Switzerland
Buch: Theory of Cryptography
Print ISBN: 978-3-031-48623-4

Electronic ISBN: 978-3-031-48624-1

Copyright-Jahr: 2023
DOI: https://doi.org/10.1007/978-3-031-48624-1_3

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner