{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,20]],"date-time":"2025-12-20T22:12:22Z","timestamp":1766268742131},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,4,30]],"date-time":"2022-04-30T00:00:00Z","timestamp":1651276800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,4,30]],"date-time":"2022-04-30T00:00:00Z","timestamp":1651276800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["AAECC"],"published-print":{"date-parts":[[2024,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>We prove that the Ring Learning With Errors (RLWE) and the Polynomial Learning With Errors (PLWE) problems over the cyclotomic field <jats:inline-formula><jats:alternatives><jats:tex-math>$${\\mathbb {Q}}(\\zeta _n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>Q<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msub>\n                      <mml:mi>\u03b6<\/mml:mi>\n                      <mml:mi>n<\/mml:mi>\n                    <\/mml:msub>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> are not equivalent. Precisely, we show that reducing one problem to the other increases the noise by a factor that is more than polynomial in <jats:italic>n<\/jats:italic>. We do so by providing a lower bound, holding for infinitely many positive integers <jats:italic>n<\/jats:italic>, for the condition number of the Vandermonde matrix of the <jats:italic>n<\/jats:italic>th cyclotomic polynomial.<\/jats:p>","DOI":"10.1007\/s00200-022-00552-9","type":"journal-article","created":{"date-parts":[[2022,5,2]],"date-time":"2022-05-02T15:03:52Z","timestamp":1651503832000},"page":"351-358","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["RLWE and PLWE over cyclotomic fields are not equivalent"],"prefix":"10.1007","volume":"35","author":[{"given":"Antonio J.","family":"Di Scala","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Carlo","family":"Sanna","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Edoardo","family":"Signorini","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,4,30]]},"reference":[{"key":"552_CR1","doi-asserted-by":"crossref","unstructured":"Ajtai, M.: Generating hard instances of lattice problems. In: Proceedings of the Twenty-Eighth Annual ACM Symposium on Theory of Computing, pp.\u00a099\u2013108 (1996)","DOI":"10.1145\/237814.237838"},{"key":"552_CR2","unstructured":"Alkim, E.,\u00a0Ducas, L., P\u00f6ppelmann, T., Schwabe, P.: Post-quantum key exchange a new hope. In: 25Th USENIX Security Symposium (USENIX Security 16), pp.\u00a0327\u2013343 (2016)"},{"key":"552_CR3","unstructured":"Avanzi, R., Bos, J., Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schanck, J.M., Schwabe, P., Seiler, G., Stehl\u00e9, D.: CRYSTALS-Kyber: Algorithm specifications and supporting documentation, Tech. report"},{"key":"552_CR4","unstructured":"Bai, S., Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schwabe, P., Seiler, G., Stehl\u00e9, D.: CRYSTALS-Dilithium: Algorithm specifications and supporting documentation, Tech. report, (2021) https:\/\/pq-crystals.org\/dilithium\/data\/dilithium-specification-round3-20210208.pdf"},{"key":"552_CR5","unstructured":"Basso, A., Bermudo\u00a0Mera, J.M., D\u2019Anvers, J.-P., Karmakar, A. Roy, S.S., Van\u00a0Beirendonck, M., Vercauteren, F.: SABER: Algorithm specifications and supporting documentation, Tech. report, (2020), https:\/\/www.esat.kuleuven.be\/cosic\/pqcrypto\/saber\/files\/saberspecround3.pdf"},{"key":"552_CR6","doi-asserted-by":"crossref","unstructured":"Blanco-Chac\u00f3n, I.: On the RLWE\/PLWE equivalence for cyclotomic number fields. Appl. Algebra Eng. Commun. Comput. (2020)","DOI":"10.1007\/s00200-020-00433-z"},{"key":"552_CR7","doi-asserted-by":"publisher","first-page":"17","DOI":"10.33232\/BIMS.0086.17.46","volume":"86","author":"I Blanco-Chac\u00f3n","year":"2020","unstructured":"Blanco-Chac\u00f3n, I.: Ring learning with errors: a crossroads between post-quantum cryptography, machine learning and number theory. Irish Math. Soc. Bull. 86, 17\u201346 (2020)","journal-title":"Irish Math. Soc. Bull."},{"key":"552_CR8","doi-asserted-by":"crossref","unstructured":"Blanco-Chac\u00f3n, I.: RLWE\/PLWE equivalence for totally real cyclotomic subextensions via quasi-Vandermonde matrices. J. Algebra Appl. (2021)","DOI":"10.1142\/S0219498822502188"},{"key":"552_CR9","unstructured":"Blanco-Chac\u00f3n , I., L\u00f3pez-Hernanz, L.: RLWE\/PLWE equivalence for the maximal totally real subextension of the $$2^r pq$$ -th cyclotomic field, arXiv:2111.13484"},{"key":"552_CR10","doi-asserted-by":"crossref","unstructured":"Bos, J., Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schanck, J.M., Schwabe, P., Seiler, G., Stehl\u00e9, D.: CRYSTALS-Kyber: A CCA-secure module-lattice-based KEM. In: 2018 IEEE European Symposium on Security and Privacy (EuroS&P), IEEE, pp.\u00a0353\u2013367 (2018)","DOI":"10.1109\/EuroSP.2018.00032"},{"key":"552_CR11","unstructured":"Chen, C., Danba, O., Rijneveld, J., Schanck, J.M., Saito, T., Schwabe, P., Whyte, W., Xagawa, K., Yamakawa, T., Zhang, Z.: NTRU: Algorithm specifications and supporting documentation, Tech. report (2020) http:\/\/web.archive.org\/web\/20211110120032\/https:\/\/ntru.org\/release\/NIST-PQ-Submission-NTRU-20201016.tar.gz"},{"issue":"1","key":"552_CR12","doi-asserted-by":"publisher","first-page":"174","DOI":"10.1515\/jmc-2020-0009","volume":"15","author":"AJ Di Scala","year":"2021","unstructured":"Di Scala, A.J., Sanna, C., Signorini, E.: On the condition number of the Vandermonde matrix of the $$n$$th cyclotomic polynomial. J. Math. Cryptol. 15(1), 174\u2013178 (2021)","journal-title":"J. Math. Cryptol."},{"key":"552_CR13","doi-asserted-by":"publisher","first-page":"238","DOI":"10.46586\/tches.v2018.i1.238-268","volume":"2018","author":"L Ducas","year":"2018","unstructured":"Ducas, L., Kiltz, E., Lepoint, T., Lyubashevsky, V., Schwabe, P., Seiler, G., Stehl\u00e9, D.: CRYSTALS-Dilithium: a lattice-based digital signature scheme. IACR Trans. Cryptograph. Hardw. Embed. Syst. 2018, 238\u2013268 (2018)","journal-title":"IACR Trans. Cryptograph. Hardw. Embed. Syst."},{"key":"552_CR14","doi-asserted-by":"crossref","unstructured":"Elias, Y., Lauter, K.E., Ozman, E., Stange, K.E.: Ring-LWE cryptography for the number theorist, Directions in Number Theory, Assoc. Women Math. Ser., vol.\u00a03, Springer, Cham, pp.\u00a0271\u2013290 (2016)","DOI":"10.1007\/978-3-319-30976-7_9"},{"key":"552_CR15","unstructured":"Fouque, P.-A., Hoffstein, J., Kirchner, P., Lyubashevsky, V., Pornin, T., Prest, T., Ricosset, T., Seiler, G., Whyte, W., Zhang, Z.: Falcon: Algorithm specifications and supporting documentation, Tech. report (2020) https:\/\/web.archive.org\/web\/20211215114823\/https:\/\/falcon-sign.info\/falcon.pdf"},{"key":"552_CR16","doi-asserted-by":"crossref","unstructured":"H\u00fclsing, A., Rijneveld, J., Schanck, J., Schwabe, P.: High-speed key encapsulation from NTRU. In: International Conference on Cryptographic Hardware and Embedded Systems. Springer, pp.\u00a0232\u2013252 (2017)","DOI":"10.1007\/978-3-319-66787-4_12"},{"issue":"3","key":"552_CR17","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1007\/s10623-014-9938-4","volume":"75","author":"A Langlois","year":"2015","unstructured":"Langlois, A., Stehl\u00e9, D.: Worst-case to average-case reductions for module lattices. Des. Codes Crypt. 75(3), 565\u2013599 (2015)","journal-title":"Des. Codes Crypt."},{"key":"552_CR18","first-page":"3","volume-title":"Learning with Errors over Rings, Algorithmic Number Theory","author":"V Lyubashevsky","year":"2010","unstructured":"Lyubashevsky, V., Peikert, C., Regev, O.: Learning with Errors over Rings, Algorithmic Number Theory, vol. 6197, pp. 3\u20133. Springer, Berlin (2010)"},{"key":"552_CR19","first-page":"84","volume":"56","author":"O Regev","year":"2005","unstructured":"Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. J. ACM 56, 84\u201393 (2005)","journal-title":"J. ACM"},{"key":"552_CR20","doi-asserted-by":"publisher","unstructured":"Sanna, C.: A survey on coefficients of cyclotomic polynomials. Expo. Math. https:\/\/doi.org\/10.1016\/j.exmath.2022.03.002","DOI":"10.1016\/j.exmath.2022.03.002"},{"key":"552_CR21","unstructured":"Signorini, E.: Condition number of cyclotomic Vandermonde matrices, (2022), v1.0.0, GitHub: https:\/\/github.com\/edoars\/cyclovandermonde"},{"key":"552_CR22","doi-asserted-by":"crossref","unstructured":"Stehl\u00e9, D., Steinfeld, R., Tanaka, K., Xagawa, K.: Efficient public key encryption based on ideal lattices. In: International Conference on the Theory and Application of Cryptology and Information Security. Springer, pp.\u00a0617\u2013635 (2009)","DOI":"10.1007\/978-3-642-10366-7_36"},{"issue":"1974","key":"552_CR23","first-page":"289","volume":"21","author":"RC Vaughan","year":"1975","unstructured":"Vaughan, R.C.: Bounds for the coefficients of cyclotomic polynomials. Michigan Math. J. 21(1974), 289\u2013295 (1975)","journal-title":"Michigan Math. J."},{"key":"552_CR24","doi-asserted-by":"crossref","unstructured":"Rosca, M., Stehl\u00e9, D., Wallet, A.: On the ring-LWE and polynomial-LWE problems. In: EUROCRYPT 2018-37th Annual International Conference on the Theory and Applications","DOI":"10.1007\/978-3-319-78381-9_6"},{"issue":"3","key":"552_CR25","doi-asserted-by":"publisher","first-page":"180","DOI":"10.46586\/tches.v2019.i3.180-201","volume":"2019","author":"V Lyubashevsky","year":"2019","unstructured":"Lyubashevsky, V., Seiler, G.: NTTRU: truly fast NTRU using NTT. TCHES 2019(3), 180\u2013201 (2019)","journal-title":"TCHES"}],"container-title":["Applicable Algebra in Engineering, Communication and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00200-022-00552-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00200-022-00552-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00200-022-00552-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,5]],"date-time":"2024-04-05T16:02:00Z","timestamp":1712332920000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00200-022-00552-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,4,30]]},"references-count":25,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,5]]}},"alternative-id":["552"],"URL":"https:\/\/doi.org\/10.1007\/s00200-022-00552-9","relation":{},"ISSN":["0938-1279","1432-0622"],"issn-type":[{"value":"0938-1279","type":"print"},{"value":"1432-0622","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,4,30]]},"assertion":[{"value":"21 January 2022","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"14 March 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 March 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 April 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 July 2022","order":5,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":6,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Missing Open Access funding information has been added in the Funding Note","order":7,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}}]}}