{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T14:57:22Z","timestamp":1785596242317,"version":"3.56.0"},"reference-count":45,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2022,7,1]],"date-time":"2022-07-01T00:00:00Z","timestamp":1656633600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,7,13]],"date-time":"2022-07-13T00:00:00Z","timestamp":1657670400000},"content-version":"vor","delay-in-days":12,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2022,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The Learning with Errors (LWE) problem is the fundamental backbone of modern lattice-based cryptography, allowing one to establish cryptography on the hardness of well-studied computational problems. However, schemes based on LWE are often impractical, so Ring LWE was introduced as a form of \u2018structured\u2019 LWE, trading off a hard to quantify loss of security for an increase in efficiency by working over a well-chosen ring. Another popular variant, Module LWE, generalizes this exchange by implementing a module structure over a ring. In this work, we introduce a novel variant of LWE over cyclic algebras (CLWE) to replicate the addition of the ring structure taking LWE to Ring LWE by adding cyclic structure to Module LWE. We show that the security reductions expected for an LWE problem hold, namely a reduction from certain structured lattice problems to the hardness of the decision variant of the CLWE problem (under the condition of constant rank <jats:italic>d<\/jats:italic>). As a contribution of theoretic interest, we view CLWE as the first variant of Ring LWE which supports non-commutative multiplication operations. This ring structure compares favorably with Module LWE, and naturally allows a larger message space for error correction coding.<\/jats:p>","DOI":"10.1007\/s00145-022-09430-6","type":"journal-article","created":{"date-parts":[[2022,7,14]],"date-time":"2022-07-14T00:02:46Z","timestamp":1657756966000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Non-commutative Ring Learning with Errors from Cyclic Algebras"],"prefix":"10.1007","volume":"35","author":[{"given":"Charles","family":"Grover","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrew","family":"Mendelsohn","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Cong","family":"Ling","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Roope","family":"Vehkalahti","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2022,7,13]]},"reference":[{"key":"9430_CR1","doi-asserted-by":"crossref","unstructured":"G. Alagic, J. Alperin-Sheriff, D. Apon, D. Cooper, Q. Dang, J. Kelsey, Y.K. Liu, C. Miller, D. Moody, R. Peralta, R. Perlner, A. Robinson, D. Smith-Tone, Status report on the second round of the NIST post-quantum cryptography standardization process. Tech. rep., NIST (2020), https:\/\/nvlpubs.nist.gov\/nistpubs\/ir\/2020\/NIST.IR.8309.pdf","DOI":"10.6028\/NIST.IR.8240"},{"key":"9430_CR2","doi-asserted-by":"crossref","unstructured":"M.R. Albrecht, A. Deo, Large modulus Ring-LWE $$\\ge $$ Module-LWE, in Takagi, T., Peyrin, T. (eds.) Advances in Cryptology \u2013 ASIACRYPT 2017. pp. 267\u2013296. Springer, Cham (2017)","DOI":"10.1007\/978-3-319-70694-8_10"},{"key":"9430_CR3","unstructured":"E. Alkim, L. Ducas, T. P\u00f6ppelmann, P. Schwabe, Post-quantum key exchange: a new hope, in 25th USENIX Security Symposium (USENIX Security 16). pp. 327\u2013343 (2016)"},{"key":"9430_CR4","doi-asserted-by":"crossref","unstructured":"B. Applebaum, D. Cash, C. Peikert, A. Sahai, Fast cryptographic primitives and circular-secure encryption based on hard learning problems, in Advances in Cryptology-CRYPTO 2009, pp. 595\u2013618. Springer (2009)","DOI":"10.1007\/978-3-642-03356-8_35"},{"key":"9430_CR5","unstructured":"R. Avanzi, J. Bos, L. Ducas, E. Kiltz, T. Lepoint, V. Lyubashevsky, J.M. Schanck, P. Schwabe, G. Seiler, D. Stehl\u00e9, CRYSTALS-Kyber algorithm specifications and supporting documentation (version 2.0). https:\/\/pq-crystals.org\/kyber\/data\/kyber-specification-round2.pdf (2019)"},{"issue":"1","key":"9430_CR6","doi-asserted-by":"publisher","first-page":"625","DOI":"10.1007\/BF01445125","volume":"296","author":"W Banaszczyk","year":"1993","unstructured":"W. Banaszczyk, New bounds in some transference theorems in the geometry of numbers. Math. Annalen  296(1), 625\u2013635 (1993)","journal-title":"Math. Annalen"},{"key":"9430_CR7","doi-asserted-by":"crossref","unstructured":"A. Banerjee, C. Peikert, New and improved key-homomorphic pseudorandom functions. in Garay, J.A., Gennaro, R. (eds.) Advances in Cryptology \u2013 CRYPTO 2014. pp. 353\u2013370. Springer, Berlin, Heidelberg (2014)","DOI":"10.1007\/978-3-662-44371-2_20"},{"key":"9430_CR8","doi-asserted-by":"crossref","unstructured":"G. Baumslag, N. Fazio, A.R. Nicolosi, V. Shpilrain, W.E. Skeith\u00a0III, Generalized learning problems and applications to non-commutative cryptography, in Provable Security, pp. 324\u2013339. Springer (2011)","DOI":"10.1007\/978-3-642-24316-5_23"},{"key":"9430_CR9","doi-asserted-by":"crossref","unstructured":"G. Berhuy, F. Oggier, An Introduction to Central Simple Algebras and Their Applications to Wireless Communication. American Mathematical Society (2013)","DOI":"10.1090\/surv\/191"},{"key":"9430_CR10","unstructured":"J.F. Biasse, F. Song, On the quantum attacks against schemes relying on the hardness of finding a short generator of an ideal in Q ($${\\zeta _p^n}$$). Tech. rep. (2015)"},{"key":"9430_CR11","unstructured":"M. Bolboceanu, Z. Brakerski, R. Perlman, D. Sharma, Order\u2013LWE and the hardness of Ring\u2013LWE with entropic secrets. Cryptology ePrint Archive, Report 2018\/494 (2018), https:\/\/eprint.iacr.org\/2018\/494"},{"key":"9430_CR12","unstructured":"C. Bootland, W. Castryck, F. Vercauteren, On the Security of the Multivariate Ring Learning with Errors Problem (2018), published: Cryptology ePrint Archive, Report 2018\/966"},{"key":"9430_CR13","doi-asserted-by":"crossref","unstructured":"J. Bos, C. Costello, L. Ducas, I. Mironov, M. Naehrig, V. Nikolaenko, A. Raghunathan, D. Stebila, Frodo: Take off the ring! Practical, Quantum-Secure Key Exchange from LWE (2016), published: Cryptology ePrint Archive, Report 2016\/659","DOI":"10.1145\/2976749.2978425"},{"key":"9430_CR14","unstructured":"P. Campbell, M. Groves, D. Shepherd, Soliloquy: A cautionary tale (2015)"},{"key":"9430_CR15","doi-asserted-by":"crossref","unstructured":"X. Caruso, J. Le\u00a0Borgne, Fast multiplication for skew polynomials, in Proceedings of the 2017 ACM on International Symposium on Symbolic and Algebraic Computation, pp. 77\u201384. ACM (2017)","DOI":"10.1145\/3087604.3087617"},{"key":"9430_CR16","unstructured":"Q. Cheng, J. Zhuang, LWE from Non-commutative Group Rings. arXiv preprint arXiv:1612.06670 (2016)"},{"key":"9430_CR17","doi-asserted-by":"crossref","unstructured":"R. Cramer, L. Ducas, C. Peikert, O. Regev, Recovering short generators of principal ideals in cyclotomic rings, in Annual International Conference on the Theory and Applications of Cryptographic Techniques. pp. 559\u2013585. Springer (2016)","DOI":"10.1007\/978-3-662-49896-5_20"},{"key":"9430_CR18","doi-asserted-by":"crossref","unstructured":"R. Cramer, L. Ducas, B. Wesolowski, Short Stickelberger class relations and application to Ideal-SVP. in Annual International Conference on the Theory and Applications of Cryptographic Techniques. pp. 324\u2013348. Springer (2017)","DOI":"10.1007\/978-3-319-56620-7_12"},{"key":"9430_CR19","unstructured":"E. Crockett, C. Peikert, Challenges for Ring-LWE. IACR Cryptology ePrint Archive (2016)"},{"issue":"2","key":"9430_CR20","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1109\/5992.909000","volume":"3","author":"R Jozsa","year":"2001","unstructured":"R. Jozsa, Quantum factoring, discrete logarithms, and the hidden subgroup problem. Comput. Sci. Eng. 3(2), 34\u201343 (2001)","journal-title":"Comput. Sci. Eng."},{"issue":"11","key":"9430_CR21","doi-asserted-by":"publisher","first-page":"5231","DOI":"10.1109\/TIT.2008.929963","volume":"54","author":"J Lahtonen","year":"2008","unstructured":"J. Lahtonen, N. Markin, G. McGuire, Construction of multiblock space\u2013time codes from division algebras with roots of unity as nonnorm elements. IEEE Trans. Inf. Theory 54(11), 5231\u20135235 (2008)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"3","key":"9430_CR22","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1007\/s10623-014-9938-4","volume":"75","author":"A Langlois","year":"2015","unstructured":"A. Langlois, D. Stehl\u00e9, Worst-case to average-case reductions for module lattices. Designs Codes Cryptogr. 75(3), 565\u2013599 (2015)","journal-title":"Designs Codes Cryptogr."},{"issue":"8","key":"9430_CR23","doi-asserted-by":"publisher","first-page":"3790","DOI":"10.1109\/TIT.2008.926447","volume":"54","author":"H Lu","year":"2008","unstructured":"H. Lu, Constructions of multiblock space\u2013time coding schemes that achieve the diversity-multiplexing tradeoff. IEEE Trans. Inf. Theory 54(8), 3790\u20133796 (2008)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9430_CR24","unstructured":"X. Lu, X. Liu, Z. Zhang, D. Jia, H. Xue, J. He, B. Li, K. Wang, Z. Liu, H. Yang, LAC: Practical Ring\u2013LWE based public-key encryption with byte-level modulus (2018), https:\/\/eprint.iacr.org\/2018\/1009.pdf"},{"issue":"11","key":"9430_CR25","doi-asserted-by":"publisher","first-page":"7218","DOI":"10.1109\/TIT.2018.2857487","volume":"64","author":"L Luzzi","year":"2018","unstructured":"L. Luzzi, R. Vehkalahti, C. Ling, Almost universal codes for MIMO wiretap channels. IEEE Trans. Inf. Theory 64(11), 7218\u20137241 (2018)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9430_CR26","doi-asserted-by":"crossref","unstructured":"V. Lyubashevsky, C. Peikert, O. Regev, On ideal lattices and learning with errors over rings, in Gilbert, H. (Ed.) Advances in Cryptology \u2013 EUROCRYPT 2010, (Springer, Berlin, Heidelberg, 2010), pp. 1\u201323.","DOI":"10.1007\/978-3-642-13190-5_1"},{"key":"9430_CR27","doi-asserted-by":"crossref","unstructured":"V. Lyubashevsky, C. Peikert, O. Regev, On ideal lattices and learning with errors over rings. in Annual International Conference on the Theory and Applications of Cryptographic Techniques, (Springer, 2010), pp. 1\u201323.","DOI":"10.1007\/978-3-642-13190-5_1"},{"key":"9430_CR28","doi-asserted-by":"crossref","unstructured":"V. Lyubashevsky, C. Peikert, O. Regev, A toolkit for Ring-LWE cryptography. in Annual International Conference on the Theory and Applications of Cryptographic Techniques, (Springer, 2013), pp. 35\u201354.","DOI":"10.1007\/978-3-642-38348-9_3"},{"issue":"3","key":"9430_CR29","doi-asserted-by":"publisher","first-page":"180","DOI":"10.46586\/tches.v2019.i3.180-201","volume":"2019","author":"V Lyubashevsky","year":"2019","unstructured":"V. Lyubashevsky, G. Seiler, NTTRU: truly fast NTRU using NTT. IACR Trans. Cryptogr. Hardware Embed. Syst. 2019(3), 180\u2013201 (2019)","journal-title":"IACR Trans. Cryptogr. Hardware Embed. Syst."},{"issue":"7","key":"9430_CR30","doi-asserted-by":"publisher","first-page":"1827","DOI":"10.1016\/j.jpaa.2017.08.009","volume":"222","author":"C Maire","year":"2018","unstructured":"C. Maire, F. Oggier, Maximal order codes over number fields. J. Pure Appl. Algebra 222(7), 1827 \u2013 1858 (2018)","journal-title":"J. Pure Appl. Algebra"},{"issue":"1","key":"9430_CR31","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1137\/S0097539705447360","volume":"37","author":"D Micciancio","year":"2007","unstructured":"D. Micciancio, O. Regev, Worst-case to average-case reductions based on Gaussian measures. SIAM J. Comput. 37(1), 267\u2013302 (2007)","journal-title":"SIAM J. Comput."},{"key":"9430_CR32","doi-asserted-by":"crossref","unstructured":"F. Oggier, J.C. Belfiore, E. Viterbo, Cyclic Division Algebras: A Tool for Space-time Coding, (Now Publishers Inc, 2007)","DOI":"10.1561\/9781601980519"},{"key":"9430_CR33","doi-asserted-by":"crossref","unstructured":"F. Oggier, B.A.\u00a0Sethuraman, Quotients of orders in cyclic algebras and space-time codes. Adv. Math. Commun., 7 (2012)","DOI":"10.3934\/amc.2013.7.441"},{"key":"9430_CR34","doi-asserted-by":"crossref","unstructured":"F. Oggier, B. Sethuraman, Quotients of orders in cyclic algebras and space-time codes. arXiv preprint arXiv:1210.7044 (2012)","DOI":"10.3934\/amc.2013.7.441"},{"key":"9430_CR35","unstructured":"A. Pedrouzo-Ulloa, J.R. Troncoso-Pastoriza, F. P\u00e9rez-Gonz\u00e1lez, On Ring Learning with Errors over the Tensor Product of Number Fields. arXiv preprint arXiv:1607.05244 (2016)"},{"key":"9430_CR36","unstructured":"A. Pedrouzo-Ulloa, J.R. Troncoso-Pastoriza, N. Gama, M. Georgieva, F. P\u00e9rez-Gonz\u00e1lez, Revisiting multivariate ring learning with errors and its applications on lattice-based cryptography. Cryptology ePrint Archive, Report 2019\/1109 (2019), https:\/\/eprint.iacr.org\/2019\/1109"},{"key":"9430_CR37","doi-asserted-by":"crossref","unstructured":"C. Peikert, An efficient and parallel Gaussian sampler for lattices. in: Annual Cryptology Conference, (Springer, 2010), pp. 80\u201397","DOI":"10.1007\/978-3-642-14623-7_5"},{"key":"9430_CR38","doi-asserted-by":"crossref","unstructured":"C. Peikert, How (not) to instantiate ring-LWE. in International Conference on Security and Cryptography for Networks, (Springer, 2016), pp. 411\u2013430","DOI":"10.1007\/978-3-319-44618-9_22"},{"key":"9430_CR39","unstructured":"C. Peikert, Z. Pepin, Algebraically structured LWE, revisited. Cryptology ePrint Archive, Report 2019\/878 (2019), https:\/\/eprint.iacr.org\/2019\/878"},{"key":"9430_CR40","doi-asserted-by":"crossref","unstructured":"C. Peikert, O. Regev, Stephens-Davidowitz, N.: Pseudorandomness of ring-LWE for any ring and modulus. in Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, (ACM, 2017), pp. 461\u2013473","DOI":"10.1145\/3055399.3055489"},{"key":"9430_CR41","doi-asserted-by":"crossref","unstructured":"R.S. Pierce, Associative algebras. Graduate Texts in Mathematics, (Springer, New York, NY 1982)","DOI":"10.1007\/978-1-4757-0163-0"},{"issue":"6","key":"9430_CR42","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1145\/1568318.1568324","volume":"56","author":"O Regev","year":"2009","unstructured":"O. Regev, On lattices, learning with errors, random linear codes, and cryptography. J. ACM (JACM) 56(6), \u00a034 (2009)","journal-title":"J. ACM (JACM)"},{"key":"9430_CR43","unstructured":"I. Reiner, Maximal Orders. L.M.S. Monographs. Academic Press (1975)"},{"issue":"8","key":"9430_CR44","doi-asserted-by":"publisher","first-page":"3751","DOI":"10.1109\/TIT.2009.2023713","volume":"55","author":"R Vehkalahti","year":"2009","unstructured":"R. Vehkalahti, C. Hollanti, J. Lahtonen, K. Ranto, On the densest MIMO lattices from cyclic division algebras. IEEE Trans. Inf. Theory  55(8), 3751\u20133780 (2009)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9430_CR45","unstructured":"L.C. Washington, Introduction to Cyclotomic Fields. Graduate Texts in Mathematics, (Springer, New York, 2012)"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-022-09430-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00145-022-09430-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-022-09430-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,25]],"date-time":"2022-07-25T18:20:28Z","timestamp":1658773228000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00145-022-09430-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7]]},"references-count":45,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2022,7]]}},"alternative-id":["9430"],"URL":"https:\/\/doi.org\/10.1007\/s00145-022-09430-6","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,7]]},"assertion":[{"value":"19 November 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 May 2022","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 May 2022","order":3,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 July 2022","order":4,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"22"}}