Fractional non-norm elements for division algebras, and an application to Cyclic Learning with Errors

Andrew Mendelsohn; Cong Ling

doi:10.3934/amc.2023043

Article Contents

2024, Volume 18, Issue 2: 410-424. Doi: 10.3934/amc.2023043

This issue Previous Article Quasi-twisted codes as contractions of quasi-cyclic codes Next Article Certain binary minimal codes constructed using simplicial complexes

Fractional non-norm elements for division algebras, and an application to Cyclic Learning with Errors

Andrew Mendelsohn^, and
Cong Ling

Imperial College London, United Kingdom

^*Corresponding author: Andrew Mendelsohn
^*Corresponding author: Andrew Mendelsohn

Received: April 2023

Revised: October 2023

Early access: October 24, 2023

Published online: October 24, 2023

Abstract / Introduction Full Text(HTML) Related Papers Cited by

Abstract

Given a cyclotomic field $ K $ and a finite Galois extension $ L $, we discuss the construction of unit-magnitude elements in $ K $ which are not in the image of the field norm map $ N_{L/K}(L^\times) $. We observe that the construction of Elia, Sethuraman, and Kumar extends to all cyclotomic fields whose rings of integers are a principal ideal domain, a fact we have not seen appear elsewhere in the literature. We then prove a number of lemmas concerning non-norm elements, and extend the above results to hold for arbitrary cyclotomic ground fields. We give examples of towers of fields and corresponding non-norm elements in both instances. Finally, we apply this to cryptography, defining a novel variant of Learning with Errors, defined over cyclic division algebras with fractional unit-magnitude non-norm elements, and reduce lattice problems defined over ideals in maximal orders in such algebras to the search problem for this form of LWE.

Keywords:

Mathematics Subject Classification: Primary: 11R18, 11R54; Secondary: 94A60, 16H20.

Citation:

Full Text(HTML)

Related Papers

Cited by

References

[1]	A. Albert, Structure of Algebras, Amer. Math. Soc. Colloq. Publ., Vol. 24. American Mathematical Society, 1939.
[2]	A. Barreal, C. Corrales and C. Hollanti, Natural orders for asymmetric space–time coding: Minimizing the discriminant, Appl. Algebra Engrg. Comm. Comput., 29 (2018), 371-391. doi: 10.1007/s00200-017-0348-5.
[3]	M. Bolboceanu, Z. Brakerski, R. Perlman and D. Sharma, Order-lwe and the hardness of ring-lwe with entropic secrets, Advances in Cryptology-ASIACRYPT 2019. Part II, Lecture Notes in Comput. Sci., 11922 (2019), 91-120. doi: 10.1007/978-3-030-34621-8_4.
[4]	Z. Brakerski and V. Vaikuntanathan, Efficient fully homomorphic encryption from (standard) LWE, 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science—FOCS 2011, (2011), 97-106. doi: 10.1109/FOCS.2011.12.
[5]	P. Elia, B. A. Sethuraman and P. V. Kumar, Perfect space-time codes for any number of antennas, IEEE Trans. Inf. Theory, 53 (2007), 3853-3868. doi: 10.1109/TIT.2007.907502.
[6]	C. Frei, D. Loughran and R. Newton, Number fields with prescribed norms, Commentarii Mathematici Helvetici, 97 (2022), 133-181. doi: 10.4171/CMH/528.
[7]	C. Grover, A. Mendelsohn, C. Ling and R. Vehkalahti, Non-commutative ring learning with errors from cyclic algebras, J. of Cryptology, 35 (2022), Paper No. 22, 67 pp. doi: 10.1007/s00145-022-09430-6.
[8]	C. Hollanti, J. Lahtonen and H.-F. Lu, Maximal orders in the design of dense space-time lattice codes, IEEE Trans. Inf. Theory, 54 (2008), 4493-4510. doi: 10.1109/TIT.2008.928998.
[9]	G. Ivanyos and L. Rónyai, Finding maximal orders in semisimple algebras over $\mathbb{Q}$, Comput. Complex., 3 (1993), 245-261. doi: 10.1007/BF01271370.
[10]	T. Kiran and B. S. Rajan, Stbc-schemes with nonvanishing determinant for certain number of transmit antennas, IEEE Trans. Inf. Theory, 51 (2005), 2984-2992. doi: 10.1109/TIT.2005.851772.
[11]	A. Langlois and D. Stehlé, Worst-case to average-case reductions for module lattices, Designs, Codes and Cryptography, 75 (2015), 565-599. doi: 10.1007/s10623-014-9938-4.
[12]	V. Lyubashevsky, C. Peikert and O. Regev, On ideal lattices and learning with errors over rings, Advances in Cryptology-EUROCRYPT, Lecture Notes in Comput. Sci., Springer, Berlin, 6110 (2010), 1-23. doi: 10.1007/978-3-642-13190-5_1.
[13]	D. A. Marcus, Number Fields, Universitext, Springer Cham, 1977.
[14]	D. Micciancio and O. Regev, Worst-case to average-case reductions based on gaussian measures, 45th Annual IEEE Symposium on Foundations of Computer Science 2004, (2004), 372-381. doi: 10.1109/FOCS.2004.72.
[15]	O. Regev, On lattices, learning with errors, random linear codes, and cryptography, J. of the ACM, 56 (2009), Art. 34, 40 pp. doi: 10.1145/1568318.1568324.
[16]	I. Reiner, Maximal Orders, London Math. Soc. Monogr. (N.S.), 28. London Mathematical Society Monographs, Oxford University Press, 2003.
[17]	B. Sethuraman, B. Rajan and V. Shashidhar, Full-diversity, high-rate space-time block codes from division algebras, IEEE Trans. Inf. Theory, 49 (2003), 2596-2616. doi: 10.1109/TIT.2003.817831.
[18]	D. Stehlé, R. Steinfeld, K. Tanaka and K. Xagawa, Efficient public key encryption based on ideal lattices, Advances in Cryptology-ASIACRYPT 2009, (5912) (2009), 617-635. doi: 10.1007/978-3-642-10366-7_36.
[19]	R. Vehkalahti, C. Hollanti, J. Lahtonen and K. Ranto, On the densest mimo lattices from cyclic division algebras, IEEE Trans. Inf. Theory, 55 (2009), 3751-3780. doi: 10.1109/TIT.2009.2023713.
[20]	J. M. Voight, Quadratic Forms and Quaternion Algebras: Algorithms and Arithmetic, Thesis (Ph.D.)-University of California, Berkeley, ProQuest LLC, Ann Arbor, MI, 2005, https://www.proquest.com/docview/305032530.
[21]	L. C. Washington, Introduction to Cyclotomic Fields, Grad. Texts in Math., 83. Springer-Verlag, New York, 1982. doi: 10.1007/978-1-4684-0133-2.