Skip to main content
Erschienen in: Applicable Algebra in Engineering, Communication and Computing 1/2022

28.04.2020 | Original Paper

On the RLWE/PLWE equivalence for cyclotomic number fields

verfasst von: Iván Blanco-Chacón

Erschienen in: Applicable Algebra in Engineering, Communication and Computing | Ausgabe 1/2022

Einloggen

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

search-config
loading …

Abstract

We study the equivalence between the ring learning with errors and polynomial learning with errors problems for cyclotomic number fields, namely: we prove that both problems are equivalent via a polynomial noise increase as long as the number of distinct primes dividing the conductor is kept constant. We refine our bound in the case where the conductor is divisible by at most three primes and we give an asymptotic subexponential formula for the condition number of the attached Vandermonde matrix valid for arbitrary degree.

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!

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!

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!

Fußnoten
1
At https://​www.​safecrypto.​eu/​pqclounge/​ a summary of candidates and the history of all submissions, attacks and withdrawals is available to filter and check.
 
2
This is the definition of RLWE/PLWE in search version. As all this material is nowadays well known to the specialist we are sparing as many details as possible. We are taking this version as starting point, as it is more suitable for our argument. We refer the reader to [10] for the decisional version of the problem.
 
3
For \(p(x)=\displaystyle \sum _{i=0}^np_ix^i\in {\mathbb {R}}[x]\), the 1-norm is defined as \(||p||_1=\displaystyle \sum _{i=0}^n|p_i|\)
 
Literatur
1.
Zurück zum Zitat Bang, A.S.: Om ligningen \(\Phi _m(X)=0\). Afdeling B, Nyt tidsskrift for Matematik 6, 6–12 (1895) Bang, A.S.: Om ligningen \(\Phi _m(X)=0\). Afdeling B, Nyt tidsskrift for Matematik 6, 6–12 (1895)
2.
Zurück zum Zitat Bateman, P.T.: Note on the coefficients of cyclotomic polynomials. Bull. Am. Math. Soc. 55(12), 1180–1181 (1949)MathSciNetCrossRef Bateman, P.T.: Note on the coefficients of cyclotomic polynomials. Bull. Am. Math. Soc. 55(12), 1180–1181 (1949)MathSciNetCrossRef
3.
Zurück zum Zitat Bateman, P.T.: On the size of the coefficients of the cyclotomic polynomial. Seminaire de Théorie des Nombres de Bordeaux 11(28), 1–18 (1982)MATH Bateman, P.T.: On the size of the coefficients of the cyclotomic polynomial. Seminaire de Théorie des Nombres de Bordeaux 11(28), 1–18 (1982)MATH
5.
Zurück zum Zitat Bloom, D.M.: On the coefficients of the cyclotomic polynomial. Am. Math. Mon. 75(4), 372–377 (1968)CrossRef Bloom, D.M.: On the coefficients of the cyclotomic polynomial. Am. Math. Mon. 75(4), 372–377 (1968)CrossRef
6.
Zurück zum Zitat Boas, P.E.: Another NP-Complete Problem and the Complexity of Computing Short Vectors in a Lattice. Technical Report 81-04, Mathematische Instituut, University of Amsterdam (1981) Boas, P.E.: Another NP-Complete Problem and the Complexity of Computing Short Vectors in a Lattice. Technical Report 81-04, Mathematische Instituut, University of Amsterdam (1981)
7.
Zurück zum Zitat Ducas, L., Durmus, A.: Ring-LWE in polynomial rings. In: PKC (2012) Ducas, L., Durmus, A.: Ring-LWE in polynomial rings. In: PKC (2012)
8.
Zurück zum Zitat Erdös, P.: On the coefficients of the cyclotomic polynomial. Portugaliae Mathematica 8(2), 63–71 (1949)MathSciNetMATH Erdös, P.: On the coefficients of the cyclotomic polynomial. Portugaliae Mathematica 8(2), 63–71 (1949)MathSciNetMATH
9.
Zurück zum Zitat Gautschi, W., Inglese, G.: Lower bounds for the condition number of Vandermonde matrices. Numerische Mathematik 52, 241–250 (1988)MathSciNetCrossRef Gautschi, W., Inglese, G.: Lower bounds for the condition number of Vandermonde matrices. Numerische Mathematik 52, 241–250 (1988)MathSciNetCrossRef
10.
Zurück zum Zitat Lyubashevsky, V., Peikert, C., Regev, O.: On ideal lattices and learning with errors over rings. In: Gilbert H. (eds) Advances in Cryptology EUROCRYPT 2010. Lecture Notes in Computer Science, 6110. Springer, Berlin Lyubashevsky, V., Peikert, C., Regev, O.: On ideal lattices and learning with errors over rings. In: Gilbert H. (eds) Advances in Cryptology EUROCRYPT 2010. Lecture Notes in Computer Science, 6110. Springer, Berlin
11.
13.
Zurück zum Zitat Peikert, C., Regev, O., Stephens-Davidowitz, N.: Pseudorandomness of Ring-LWE for any ring and modulus. In: STOC (2017) Peikert, C., Regev, O., Stephens-Davidowitz, N.: Pseudorandomness of Ring-LWE for any ring and modulus. In: STOC (2017)
14.
15.
Zurück zum Zitat Rosca, M., Stehlé, D., Wallet, A.: On the ring-LWE and polynomial-LWE problems. In: Nielsen J., Rijmen V. (eds) Advances in Cryptology EUROCRYPT 2018. Lecture Notes in Computer Science, vol. 10820. Springer, Berlin Rosca, M., Stehlé, D., Wallet, A.: On the ring-LWE and polynomial-LWE problems. In: Nielsen J., Rijmen V. (eds) Advances in Cryptology EUROCRYPT 2018. Lecture Notes in Computer Science, vol. 10820. Springer, Berlin
16.
Zurück zum Zitat Stehle, D.N., Steinfeld, R., Tanaka, K., Xagawa, K.: Efficient public key encryption based on ideal lattices. Adv. Cryptol. ASIACRYPT 2009, 617–635 (2009)MathSciNetMATH Stehle, D.N., Steinfeld, R., Tanaka, K., Xagawa, K.: Efficient public key encryption based on ideal lattices. Adv. Cryptol. ASIACRYPT 2009, 617–635 (2009)MathSciNetMATH
17.
Zurück zum Zitat Stewart, I.: Algebraic Number Theory and Fermat’s Last Theorem. AK Peters Ltd, Natick (2002)MATH Stewart, I.: Algebraic Number Theory and Fermat’s Last Theorem. AK Peters Ltd, Natick (2002)MATH
18.
Zurück zum Zitat Vaughan, R.C.: Bounds for the coefficients of cyclotomic polynomials. Michigan Math. J. 21(4), 289–295 (1975)MathSciNetCrossRef Vaughan, R.C.: Bounds for the coefficients of cyclotomic polynomials. Michigan Math. J. 21(4), 289–295 (1975)MathSciNetCrossRef
19.
Zurück zum Zitat Washington, L.C.: Introduction to Cyclotomic Fields. Springer GTM, Berlin (1997)CrossRef Washington, L.C.: Introduction to Cyclotomic Fields. Springer GTM, Berlin (1997)CrossRef
Metadaten
Titel
On the RLWE/PLWE equivalence for cyclotomic number fields
verfasst von
Iván Blanco-Chacón
Publikationsdatum
28.04.2020
Verlag
Springer Berlin Heidelberg
Erschienen in
Applicable Algebra in Engineering, Communication and Computing / Ausgabe 1/2022
Print ISSN: 0938-1279
Elektronische ISSN: 1432-0622
DOI
https://doi.org/10.1007/s00200-020-00433-z

Weitere Artikel der Ausgabe 1/2022

Applicable Algebra in Engineering, Communication and Computing 1/2022 Zur Ausgabe

Acknowledgment

Acknowledgment