We generalise our previous work [5] by giving a polynomial upper bound on the condition number of certain quasi-Vandermonde matrices to establish the equivalence between the RLWE and PLWE problems for the totally real subfield of the cyclotomic fields of conductor $ 2^r $, $ 2^rp $ and $ 2^rpq $ with $ r\geq 1 $ and $ p $, $ q $ arbitrary primes. Moreover, we give some cryptographic motivations for the study of these subfields.
Citation: |
[1] |
K. A. Loper and N. J. Werner, Resultants of minimal polynomials of maximal real cyclotomic extensions, J. Number Theory, 158 (2016), 298-315.
doi: 10.1016/j.jnt.2015.06.002.![]() ![]() ![]() |
[2] |
O. Bernard and A. Roux-Langlois, Twisted-PHS: Using the product formula to solve approx-SVP in ideal lattices, in: S. Moriai, H. Wang (eds) Advances in Cryptology - ASIACRYPT 2020. Part II, Lecture Notes in Computer Science, 12492, Springer, 2020, 349-380.
doi: 10.1007/978-3-030-64834-3_12.![]() ![]() ![]() |
[3] |
I. Blanco-Chacón, On the RLWE/PLWE equivalence for cyclotomic number field, Appl. Algebra Engrg. Comm. Comput., 33 (2020), 53-71.
doi: 10.1007/s00200-020-00433-z.![]() ![]() ![]() |
[4] |
I. Blanco-Chacón, Ring learning with errors: a crossroads between post-quantum cryptography, machine learning and number theory, Irish Math. Soc. Bull., 86 (2020), 17-46.
![]() ![]() |
[5] |
I. Blanco-Chacón, RLWE/PLWE equivalence for totally real cyclotomic subextensions via quasi-Vandermonde matrices, J. Algebra Appl., 21 (2022), Paper No. 2250218, 18 pp.
doi: 10.1142/S0219498822502188.![]() ![]() ![]() |
[6] |
M. Bolboceanu, Z. Brakerski and D. Sharma, On algebraic embedding for unstructured lattices, Cryptology ePrint Archive, Report 2021/053, 2021. https://ia.cr/2021/053.
![]() |
[7] |
K. Boudgoust, E. Gachon and A. Pellet-Mary, Some easy instances of ideal-SVP and implications on the partial Vandermonde Knapsack Problem, in: CRYPTO 2022, Preprint, 2022. https://eprint.iacr.org/2022/709.
![]() |
[8] |
B. Bzdega, A. Herrera-Poyatos and P. More, Cyclotomic polynomials at roots of unity, Acta Arith., 184 (2018), 215-230.
doi: 10.4064/aa170112-20-12.![]() ![]() ![]() |
[9] |
W. Castryck, I. Iliashenko and F. Vercauteren, Provably weak instances of ring-LWE revisited, in: Advances in Cryptology - EUROCRYPT 2016, Lecture Notes in Computer Science, 9665. Springer, (2016), 147-167.
doi: 10.1007/978-3-662-49890-3_6.![]() ![]() ![]() |
[10] |
H. Chen, K. Lauter and K. E. Stange, Attacks on the search RLWE problem with small errors, SIAM J. Appl. Algebra Geometry, 1 (2017), 665-682.
doi: 10.1137/16M1096566.![]() ![]() ![]() |
[11] |
R. Cramer, L. Ducas and B. Wesolowski, Short Stickelberger class relations and application to ideal-SVP, in: Coron, JS., Nielsen, J. (eds) Advances in Cryptology - EUROCRYPT 2017. Part I, 324-348, Lecture Notes in Computer Science, 10210. Springer, 2017.
doi: 10.1007/978-3-319-56620-7_12.![]() ![]() ![]() |
[12] |
L. Ducas and A. Durmus., Ring-LWE in polynomial rings, in: Fischlin M., Buchmann J., Manulis M. (eds) Public Key Cryptography. PKC 2012, 34-51, Lecture Notes in Computer Science, 7293. Springer, 2012.
doi: 10.1007/978-3-642-30057-8_3.![]() ![]() ![]() |
[13] |
L. Ducas, M. Plancon and B. Wesolowski, On the shortness of vectors to be found by the ideal-SVP quantum algorithm, in: Advances in Cryptology—CRYPTO 2019. Part I, 322-351, Lecture Notes in Computer Science, 11692. Springer, 2019.
doi: 10.1007/978-3-030-26948-7_12.![]() ![]() ![]() |
[14] |
K. Eisenträger, S. Hallgre and K. Lauter, Weak instances of PLWE,, In: Joux A., Youssef A. (eds) Selected Areas in Cryptography–SAC 2014, 183-194, Lecture Notes in Computer Science, 8781. Springer, 2014.
doi: 10.1007/978-3-319-13051-4_11.![]() ![]() ![]() |
[15] |
Y. Elias, K. E. Lauter, E. Ozman and K. E. Stange, Ring-LWE cryptography for the number theorist, in: E. Eischen, L. Long, R. Pries, K. Stange (eds) Directions in Number Theory, 271-290, Association for Women in Mathematics Series, 3. Springer, 2016.
doi: 10.1007/978-3-319-30976-7_9.![]() ![]() ![]() |
[16] |
P.-A. Fouqué, P. Kirchner, M. Tibouchi, A. Wallet and Y. Yu, Key recovery from Gram-Schmidt norm leakage in hash-and-sign signatures over NTRU lattices, Advances in Cryptology—EUROCRYPT 2020. Part III, 34-63, Lecture Notes in Comput. Sci., 12107, Springer, Cham, 2020. https://eprint.iacr.org/2019/1180.
doi: 10.1007/978-3-030-45727-3_2.![]() ![]() ![]() |
[17] |
W. Gautschi and G. Inglese, Lower bounds for the condition number of Vandermonde matrices, Numer. Math., 52 (1988), 241-250.
doi: 10.1007/BF01398878.![]() ![]() ![]() |
[18] |
M. Kuian, L. Reichel and S. Shiyanovskii, Optimally conditioned Vandermonde-like matrices, SIAM J. Matrix Anal. Appl., 40 (2019), 1399-1424.
doi: 10.1137/19M1237272.![]() ![]() ![]() |
[19] |
V. Lyubashevsky, C. Peikert and O. Regev, On ideal lattices and learning with errors over rings, in: Gilbert H. (eds) Advances in Cryptology-EUROCRYPT 2010, 1-23, Lecture Notes in Computer Science, 6110. Springer, 2010.
doi: 10.1007/978-3-642-13190-5_1.![]() ![]() ![]() |
[20] |
M. Mosca and M. Piani, 2021 Quantum Threat Timeline Report, Available from: https://globalriskinstitute.org/publications/2021-quantum-threat-timeline-report/.
![]() |
[21] |
Y. Pan, J. Xu, N. Wadleigh, and Q. Cheng, On the ideal shortest vector problem over random rational primes, Advances in Cryptology—EUROCRYPT 2021. Part I, 559-583, Lecture Notes in Comput. Sci., 12696, Springer, Cham, 2021. https://eprint.iacr.org/2021/245.
doi: 10.1007/978-3-030-77870-5_20.![]() ![]() ![]() |
[22] |
C. Peikert, How (not) to instantiate ring-LWE, in: Zikas, V.; de Prisco, R. (eds.) Security and Cryptography for Networks 2016, Lecture Notes in Computer Science, 9841. Springer, 2016, 411-430.
doi: 10.1007/978-3-319-44618-9_22.![]() ![]() ![]() |
[23] |
C. Peikert, O. Regev and N. Stephens-Davidowitz, Pseudorandomness of ring-LWE for any ring and modulus, Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017, 461-473.
doi: 10.1145/3055399.3055489.![]() ![]() ![]() |
[24] |
A. Pellet-Mary, G. Hanrot and D. Stehlé, Approx-SVP in ideal lattices with pre-processing,, in: EUROCRYPT 2019: Advances in Cryptology - EUROCRYPT 2019, Lecture Notes in Computer Science, 11477. Springer, 2019, 685-716.
![]() ![]() |
[25] |
M. Rosca, D. Stehlé and A. Wallet, On the Ring-LWE and polynomial-LWE problems, in: Nielsen J., Rijmen V. (eds) Advances in Cryptology - EUROCRYPT 2018, Part I, Lecture Notes in Computer Science, 10820. Springer, 2018, 146-173.
doi: 10.1007/978-3-319-78381-9_6.![]() ![]() ![]() |
[26] |
A. J. Di Scala, C. Sanna and E. Signorini, RLWE and PLWE over cyclotomic number fields are not equivalent, Appl. Algebra Engrg. Comm. Comput. (online), (2020). Available from: https://link.springer.com/article/10.1007/s00200-022-00552-9.
![]() |
[27] |
D. Stehlé, R. Steinfeld, K. Tanaka and K. Xagaw, Efficient public key encryption based on ideal lattices, in: Matsui M. (eds) Advances in Cryptology-ASIACRYPT 2009, 617-635, Lecture Notes in Computer Science, 5912. Springer, 2009.
doi: 10.1007/978-3-642-10366-7_36.![]() ![]() ![]() |
[28] |
I. Stewart and D. Tall, Algebraic Number Theory (Second Edition), Chapman and Hall/CRC Press, Chapman & Hall, London, 1987.
![]() ![]() |
[29] |
W. F. Trench, Inverses of Lower Triangular Toeplitz Matrices, 2009. Available from: http://ramanujan.math.trinity.edu/wtrench/research/papers/TRENCH_TN_6.PDF.
![]() |
[30] |
L. C. Washington, Introduction to Cyclotomic Fields, Springer GTM, 1997.
doi: 10.1007/978-1-4612-1934-7.![]() ![]() ![]() |
[31] |
National institute for standards and technology, Round 3 submissions, 2022. Available from: https://csrc.nist.gov/projects/post-quantum-cryptography.
![]() |