\`x^2+y_1+z_12^34\`
Advanced Search
Article Contents
Article Contents

RLWE/PLWE equivalence for the maximal totally real subextension of the $ 2^rpq $-th cyclotomic field

  • *Corresponding author: Iván Blanco-Chacón

    *Corresponding author: Iván Blanco-Chacón 

The first author is supported by Ministerio de Ciencia e Innovación, Spain, MTM2016-79400-P and PID2019-104855RBI00/ AEI/10.13039/501100011033. The second author is supported by Ministerio de Ciencia e Innovación, Spain, PID2019-105621GB-I00

Abstract / Introduction Full Text(HTML) Related Papers Cited by
  • 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.

    Mathematics Subject Classification: Primary: 11H71, 11R18; Secondary: 11Y16, 15A12, 94.

    Citation:

    \begin{equation} \\ \end{equation}
  • 加载中
  • [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. BzdegaA. 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. ChenK. 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. KuianL. 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. TallAlgebraic 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.
  • 加载中
SHARE

Article Metrics

HTML views(2654) PDF downloads(687) Cited by(0)

Access History

Other Articles By Authors

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return