Learning with Errors from Nonassociative Algebras

Andrew Mendelsohn; Cong Ling

doi:10.62056/aee0wa3y6

Learning with Errors from Nonassociative Algebras

Authors

Andrew Mendelsohn, Cong Ling

Andrew Mendelsohn

Department of Electrical and Electronic Engineering, Imperial College London, London, UK
am3518 at ic dot ac dot uk

Cong Ling

Department of Electrical and Electronic Engineering, Imperial College London, London, UK
c dot ling at imperial dot ac dot uk

Abstract

We construct a provably-secure structured variant of Learning with Errors (LWE) using nonassociative cyclic division algebras, assuming the hardness of worst-case structured lattice problems, for which we are able to give a full search-to-decision reduction, improving upon the construction of Grover et al. named `Cyclic Learning with Errors' (CLWE). We are thus able to create structured LWE over cyclic algebras without any restriction on the size of secret spaces, which was required for CLWE as a result of its restricted security proof. We reduce the shortest independent vectors problem in ideal lattices, obtained from ideals in orders of such algebras, to the decision variant of LWE defined for nonassociative CDAs. We believe this variant has greater security and greater freedom with parameter choices than CLWE, and greater asymptotic efficiency of multiplication than module LWE. Our reduction requires new results in the ideal theory of such nonassociative algebras, which may be of independent interest. We then adapt an LPR-like PKE scheme to hold for nonassociative spaces, and discuss the efficiency and security of our construction, showing that it is immune to certain subfield attacks. Finally, we give example parameters to construct algebras for cryptographic use.

References

[AD97]

Miklós Ajtai and Cynthia Dwork. A Public-Key Cryptosystem with Worst-Case/Average-Case Equivalence. In 29th ACM STOC, pages 284–293. May 1997. ACM Press. DOI: 10.1145/258533.258604

Google Scholar ePrint

[Ajt96]

M. Ajtai. Generating Hard Instances of Lattice Problems. Electron. Colloquium Comput. Complex., TR96, 1996. DOI: 10.1145/237814.237838

Google Scholar ePrint

[Alb39]

A.A. Albert. Structure of Algebras. Number v. 24 in AMS colloquium publications. American Mathematical Society 1939.

Google Scholar ePrint

[APS15]

M. Albrecht, R. Player, and S. Scott. On the concrete hardness of Learning with Errors. Journal of Mathematical Cryptology, 9(3):169–203, 2015. DOI: doi:10.1515/jmc-2015-0016

Google Scholar ePrint

[BCV20]

C. Bootland, W. Castryck, and F. Vercauteren. On the security of the multivariate ring learning with errors problem. In ANTS XIV. 2020. MSP. DOI: 10.2140/obs.2020.4.57

Google Scholar ePrint

[BP21]

C. Brown and S. Pumplun. How a nonassociative algebra reflects the properties of a skew polynomial. Glasgow Mathematical Journal, 63(1):6–26, 2021. DOI: 10.1017/S0017089519000478

Google Scholar ePrint

[BV11]

Z. Brakerski and V. Vaikuntanathan. Efficient Fully Homomorphic Encryption from (Standard) LWE. In FOCS 2011, pages 97-106. 2011. DOI: 10.1109/FOCS.2011.12

Google Scholar ePrint

[CGGI19]

Ilaria Chillotti, Nicolas Gama, Mariya Georgieva, and Malika Izabachène. TFHE: Fast Fully Homomorphic Encryption Over the Torus. Journal of Cryptology, 33:34 - 91, 2019.

Google Scholar ePrint

[CKKS17]

J. H. Cheon, A. Kim, M. Kim, and Y. Song. Homomorphic Encryption for Arithmetic of Approximate Numbers. In T. Takagi and T. Peyrin, editors, ASIACRYPT 2017, volume 10624 of LNCS, pages 409–437. 2017. Springer International Publishing. DOI: 10.1007/978-3-319-70694-8_15

Google Scholar ePrint

[CL17]

X. Caruso and J. Le Borgne. Fast Multiplication for Skew Polynomials. In Proceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation, pages 77–84. 2017. Assoc. for Computing Machinery. DOI: 10.1145/3087604.3087617

Google Scholar ePrint

[DDLL13]

L. Ducas, A. Durmus, T. Lepoint, and V. Lyubashevsky. Lattice Signatures and Bimodal Gaussians. In R. Canetti and J. A. Garay, editors, CRYPTO 2013, volume 8042 of LNCS, pages 40–56. 2013. Springer Berlin Heidelberg. DOI: 10.1007/978-3-642-40041-4_3

Google Scholar ePrint

[DLL⁺17]

L. Ducas, T. Lepoint, V. Lyubashevsky, P. Schwabe, G. Seiler, and D. Stehle. CRYSTALS-Dilithium: Digital Signatures from Module Lattices. 2017.

Google Scholar ePrint

[GMLV22]

Charles Grover, Andrew Mendelsohn, Cong Ling, and Roope Vehkalahti. Non-commutative Ring Learning with Errors from Cyclic Algebras. Journal of Cryptology, 35(3):22, July 2022. DOI: 10.1007/s00145-022-09430-6

Google Scholar ePrint

[GSW13]

Craig Gentry, Amit Sahai, and Brent Waters. Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based. In Ran Canetti and Juan A. Garay, editors, CRYPTO 2013, Part I, volume 8042 of LNCS, pages 75–92. August 2013. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-40041-4_5

Google Scholar ePrint

[HKS21]

W.C. Huffman, J.L. Kim, and P. Solé. Concise Encyclopedia of Coding Theory. CRC Press 2021.

Google Scholar ePrint

[HLL08]

C. Hollanti, J. Lahtonen, and H. F. Lu. Maximal Orders in the Design of Dense Space-Time Lattice Codes. IEEE Transactions on Information Theory, 54(10):4493-4510, 2008. DOI: 10.1109/TIT.2008.928998

Google Scholar ePrint

[KL14]

J. Katz and Y. Lindell. Introduction to Modern Cryptography, Second Edition. Chapman & Hall/CRC Cryptography and Network Security Series. Taylor & Francis 2014.

Google Scholar ePrint

[LM23]

C. Ling and A. Mendelsohn. NTRU In Quaternion Algebras Of Bounded Discriminant. In PQCrypto 2023, volume 14154 of LNCS, pages 256–290. 2023. Springer-Verlag. DOI: 10.1007/978-3-031-40003-2_10

Google Scholar ePrint

[LM24]

C. Ling and A. Mendelsohn. Middle-Products of Skew Polynomials and Learning with Errors. In E. A. Quaglia, editor, IMACC 2023, volume 14421 of LNCS, pages 199–219. 2024. Springer. DOI: 10.1007/978-3-031-47818-5_11

Google Scholar ePrint

[LÖ16]

P. Lundström and J. Öinert. Simple Graded Rings, Non-Associative Crossed Products and Cayley-Dickson Doublings. Journal of Algebra and Its Applications, 19, October 2016. DOI: 10.1142/S021949882050231X

Google Scholar ePrint

[LPR13a]

V. Lyubashevsky, C. Peikert, and O. Regev. A Toolkit for Ring-LWE Cryptography. In T. Johansson and P. Q. Nguyen, editors, EUROCRYPT 2013, volume 7881 of LNCS, pages 35–54. 2013. Springer Berlin Heidelberg. DOI: 10.1007/978-3-642-38348-9_3

Google Scholar ePrint

[LPR13b]

V. Lyubashevsky, C. Peikert, and O. Regev. On Ideal Lattices and Learning with Errors over Rings. J. ACM, 60(6), 2013. DOI: 10.1145/2535925

Google Scholar ePrint

[LS15]

A. Langlois and D. Stehlé. Worst-case to average-case reductions for module lattices. Designs, Codes and Cryptography, 75(3):565-599, June 2015. DOI: 10.1007/s10623-014-9938-4

Google Scholar ePrint

[LW92]

H. J. Lee and W. C. Waterhouse. Maximal orders in nonassociative quaternion algebras. Journal of Algebra, 146(2):441-453, 1992. DOI: 10.1016/0021-8693(92)90077-Y

Google Scholar ePrint

[Lyu12]

V. Lyubashevsky. Lattice Signatures without Trapdoors. In D. Pointcheval and T. Johansson, editors, EUROCRYPT 2012, volume 7237 of LNCS, pages 738–755. 2012. Springer Berlin Heidelberg. DOI: 10.1007/978-3-642-29011-4_43

Google Scholar ePrint

[ML]

C Mendelsohn A and Ling. On the Hardness of Cryptographic Problems from Cyclic Algebras. To appear..

Google Scholar ePrint

[ML23]

A. Mendelsohn and C. Ling. Fractional non-norm elements for division algebras, and an application to Cyclic Learning with Errors. Adv. Math. Commun., 2023. DOI: 10.3934/amc.2023043

Google Scholar ePrint

[MP15]

D. Miccancio and C. Peikert. The Mathematics of Modern Cryptography Workshop. https://simons.berkeley.edu/workshops/mathematics-modern-cryptography. July 2015.

Google Scholar ePrint

[MR04]

D. Micciancio and O. Regev. Worst-case to average-case reductions based on Gaussian measures. In FOCS 2004, volume 37 of SIAM J. Comput., pages 372-381. 2004. DOI: 10.1137/S0097539705447360

Google Scholar ePrint

[NIS22]

NIST. Post-Quantum Cryptography: Selected Algorithms 2022. https://csrc.nist.gov/Projects/post-quantum-cryptography/selected-algorithms-2022. December 2022.

Google Scholar ePrint

[Ore33]

O. Ore. Theory of Non-Commutative Polynomials. Annals of Mathematics, 34(3):480–508, 1933.

Google Scholar ePrint

[OS13]

F. Oggier and B. A. Sethuraman. Quotients of orders in cyclic algebras and space-time codes. Adv. Math. Commun., 7(4):441-461, 2013. DOI: 10.3934/amc.2013.7.441

Google Scholar ePrint

[PTP16]

A. Pedrouzo-Ulloa, J. R. Troncoso-Pastoriza, and F. Pérez-González. On Ideal Lattices over the Tensor Product of Number Fields and Ring Learning with Errors over Multivariate Rings. CoRR, abs/1607.05244, 2016.

Google Scholar ePrint

[PU11]

S. Pumplün and T. Unger. Space-time block codes from nonassociative division algebras. Adv. Math. Commun., 5(3):449-471, 2011. DOI: 10.3934/amc.2011.5.449

Google Scholar ePrint

[Pum16]

S. Pumplün. How to obtain lattices from $(f, \sigma, \delta)$-codes via a generalization of Construction A. Applicable Algebra in Engineering, Communication and Computing, 29:313-333, 2016. DOI: 10.1007/s00200-017-0344-9

Google Scholar ePrint

[Pum17]

S. Pumplün. Finite nonassociative algebras obtained from skew polynomials and possible applications to ($f$, $\sigma$, $\delta$)-codes. Advances in Mathematics of Communications, 11(3):615-634, 2017. DOI: 10.3934/amc.2017046

Google Scholar ePrint

[Pum18]

S. Pumplün. Quotients of orders in algebras obtained from skew polynomials with applications to coding theory. Communications in Algebra, 46(11):5053-5072, 2018. DOI: 10.1080/00927872.2018.1461882

Google Scholar ePrint

[PW16]

S. Puchinger and A. Wachter-Zeh. Sub-quadratic decoding of Gabidulin codes. In 2016 IEEE International Symposium on Information Theory (ISIT), pages 2554-2558. 2016. DOI: 10.1109/ISIT.2016.7541760

Google Scholar ePrint

[PW18]

S. Puchinger and A. Wachter-Zeh. Fast operations on linearized polynomials and their applications in coding theory. Journal of Symbolic Computation, 89:194-215, 2018. DOI: 10.1016/j.jsc.2017.11.012

Google Scholar ePrint

[Reg09]

O. Regev. On lattices, learning with errors, random linear codes, and cryptography. J. of the ACM, 56, 2009. DOI: 10.1145/1568318

Google Scholar ePrint

[Sch10]

R. Schafer. An Introduction to Nonassociative Algebras. Benediction Classics 2010.

Google Scholar ePrint

[SPO12]

A. Steele, S. Pumplün, and F. Oggier. MIDO space-time codes from associative and nonassociative cyclic algebras. In 2012 IEEE Information Theory Workshop, pages 192-196. September 2012. DOI: 10.1109/ITW.2012.6404655

Google Scholar ePrint

[SRS03]

B. A. Sethuraman, B. S. Rajan, and V. Shashidhar. Full-diversity, high-rate space-time block codes from division algebras. IEEE Trans. Inf. Theory, 49(10):2596-2616, 2003. DOI: 10.1109/TIT.2003.817831

Google Scholar ePrint

[SSTX09]

Damien Stehlé, Ron Steinfeld, Keisuke Tanaka, and Keita Xagawa. Efficient Public Key Encryption Based on Ideal Lattices. In Mitsuru Matsui, editor, ASIACRYPT 2009, volume 5912 of LNCS, pages 617–635. December 2009. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-10366-7_36

Google Scholar ePrint

[Ste14a]

A. Steele. Nonassociative cyclic algebras. Israel Journal of Mathematics, 200, June 2014. DOI: 10.1007/s11856-014-0021-7

Google Scholar ePrint

[Ste14b]

A. Steele. Some new classes of division algebras and potential applications to space-time block coding. PhD thesis, Univeristy of Nottingham, 2014.

Google Scholar ePrint

[Wat87]

W. C. Waterhouse. Nonassociative quarternion algebras. Algebras, Groups, Geometries, 4(3):365-378, 1987.

Google Scholar ePrint

PDF Open access

DOI: https://doi.org/10.62056/aee0wa3y6

History

Submitted: 2024-10-09
Accepted: 2024-12-03
Published: 2025-01-13

How to cite

Andrew Mendelsohn and Cong Ling, Learning with Errors from Nonassociative Algebras. IACR Communications in Cryptology, vol. 1, no. 4, Jan 13, 2025, doi: 10.62056/aee0wa3y6.

License

Copyright is held by the author(s)

This work is licensed under a Creative Commons Attribution (CC BY) license.

@article{CiC-1-4-16,
    author = "Mendelsohn, Andrew and Ling, Cong",
    journal = "{IACR} {C}ommunications in {C}ryptology",
    publisher = "{I}nternational {A}ssociation for {C}ryptologic {R}esearch",
    title = "Learning with Errors from Nonassociative Algebras",
    volume = "1",
    number = "4",
    date = "2025-01-13",
    year = "2025",
    issn = "3006-5496",
    doi = "10.62056/aee0wa3y6"
}

TY - JOUR
AU - Mendelsohn, Andrew
AU - Ling, Cong
PY - 2025
TI - Learning with Errors from Nonassociative Algebras
JF - IACR Communications in Cryptology
JA - CIC
VL - 1
IS - 4
DO - 10.62056/aee0wa3y6
UR - https://doi.org/10.62056/aee0wa3y6
AB - <p>We construct a provably-secure structured variant of Learning with Errors (LWE) using nonassociative cyclic division algebras, assuming the hardness of worst-case structured lattice problems, for which we are able to give a full search-to-decision reduction, improving upon the construction of Grover et al. named `Cyclic Learning with Errors' (CLWE). We are thus able to create structured LWE over cyclic algebras without any restriction on the size of secret spaces, which was required for CLWE as a result of its restricted security proof. We reduce the shortest independent vectors problem in ideal lattices, obtained from ideals in orders of such algebras, to the decision variant of LWE defined for nonassociative CDAs. We believe this variant has greater security and greater freedom with parameter choices than CLWE, and greater asymptotic efficiency of multiplication than module LWE. Our reduction requires new results in the ideal theory of such nonassociative algebras, which may be of independent interest. We then adapt an LPR-like PKE scheme to hold for nonassociative spaces, and discuss the efficiency and security of our construction, showing that it is immune to certain subfield attacks. Finally, we give example parameters to construct algebras for cryptographic use. </p>
ER -

Andrew Mendelsohn and Cong Ling, Learning with Errors from Nonassociative Algebras. IACR Communications in Cryptology, vol. 1, no. 4, Jan 13, 2025, doi: 10.62056/aee0wa3y6.