Top

Hint

Swipe to navigate through the articles of this issue

Published in:

28-04-2020 | Original Paper

On the RLWE/PLWE equivalence for cyclotomic number fields

Author: Iván Blanco-Chacón

Published in: Applicable Algebra in Engineering, Communication and Computing | Issue 1/2022

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.

previous article Self-dual cyclic codes over of length 4n

next article On Euclidean self-dual codes and isometry codes

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.

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.

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|\)

Bang, A.S.: Om ligningen \(\Phi _m(X)=0\). Afdeling B, Nyt tidsskrift for Matematik 6, 6–12 (1895)

Bateman, P.T.: Note on the coefficients of cyclotomic polynomials. Bull. Am. Math. Soc. 55(12), 1180–1181 (1949) MathSciNetCrossRef

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

Bernstein, D.J., Chuengsatiansup, C., Lange, T., van Vredendaal, C.: NTRU Prime (2016). http://eprint.iacr.org/2016/461. Accessed 27 Apr 2020

Bloom, D.M.: On the coefficients of the cyclotomic polynomial. Am. Math. Mon. 75(4), 372–377 (1968) CrossRef

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)

Ducas, L., Durmus, A.: Ring-LWE in polynomial rings. In: PKC (2012)

Erdös, P.: On the coefficients of the cyclotomic polynomial. Portugaliae Mathematica 8(2), 63–71 (1949) MathSciNetMATH

Gautschi, W., Inglese, G.: Lower bounds for the condition number of Vandermonde matrices. Numerische Mathematik 52, 241–250 (1988) MathSciNetCrossRef

10.

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.

Maier, H.: Cyclotomic polynomials with large coefficients. Acta arithmetica 64(3), 227–235 (1993) MathSciNetCrossRef

12.

Pan, V.Y.: How bad are Vandermonde matrices? SIAM J. Matrix Anal. Appl. 37(2), 679–694 (2016) MathSciNetCrossRef

13.

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

14.

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

15.

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.

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.

Stewart, I.: Algebraic Number Theory and Fermat’s Last Theorem. AK Peters Ltd, Natick (2002) MATH

18.

Vaughan, R.C.: Bounds for the coefficients of cyclotomic polynomials. Michigan Math. J. 21(4), 289–295 (1975) MathSciNetCrossRef

19.

Washington, L.C.: Introduction to Cyclotomic Fields. Springer GTM, Berlin (1997) CrossRef

Title: On the RLWE/PLWE equivalence for cyclotomic number fields
Author: Iván Blanco-Chacón
Publication date: 28-04-2020
Publisher: Springer Berlin Heidelberg
Published in: Applicable Algebra in Engineering, Communication and Computing / Issue 1/2022
Print ISSN: 0938-1279
Electronic ISSN: 1432-0622
DOI: https://doi.org/10.1007/s00200-020-00433-z

Springer Professional

Hint

Swipe to navigate through the articles of this issue

On the RLWE/PLWE equivalence for cyclotomic number fields

Abstract

Premium Partner

Springer Professional

Hint

Swipe to navigate through the articles of this issue

Abstract

Please log in to get access to this content

Other articles of this Issue 1/2022

On Euclidean self-dual codes and isometry codes

A partial characterization of Hilbert quasi-polynomials in the non-standard case

Self-dual cyclic codes over of length 4n

Acknowledgment

Premium Partner