Download pdf
From learning with errors (LWE) problem to CLWE problem
- 1 Shenzhen MSU-BIT University
* Author to whom correspondence should be addressed.
Abstract
The main purpose of this paper is to introduce the learning with errors problem on cyclic algebras, i.e., the CLWE problem, and to fully discuss and utilize the well-proven LWE-related conclusions and assumptions in cryptography theory. Firstly, this paper provides the basic framework of Learning with Errors (LWE) problems for cyclic algebra samples. Then lattices generated by the two-sided ideal of cyclic algebra with natural order are applied to cryptography. Based on the above contents, the so-called CLWE problem is introduced to point out the dimensions and structures suitable for constructing cryptographic systems for explicit algebra, and the security of corroding problems is discussed in the CLWE samples. Finally, this paper also discusses some possible future research directions, some natural routes to further research the construction and application of CLWE problems, for example, how to choose parameters for a specific security level, so as to offer some references for future study.
Keywords
Learning with Errors(LWE), cyclic algebra, CLWE, lattice problem
[1]. Chris Peikert and Brent Waters. (2008) Lossy trapdoor functions and their applications. In Proceedings of the fortieth annual ACM symposium on Theory of computing, pp. 187-196.
[2]. Chris Peikert. (2009) Public-key cryptosystems from the worst-case shortest vector problem. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pp. 333-342.
[3]. Daniele Micciancio and Chris Peikert. (2012) Trapdoors for lattices: Simpler, tighter, faster, smaller. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer, pp. 700-718.
[4]. Richard Lindner and Chris Peikert. (2011) Better key sizes (and attacks) for lwe-based encryption. In Cryptographers’ Track at the RSA Conference, Springer, pp. 319-339.
[5]. Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. (2014) (leveled) fully homomorphic encryption without bootstrapping. ACM Transactions on Computation Theory (TOCT), 6(3):1-36.
[6]. Craig Gentry. (2009) Fully homomorphic encryption using ideal lattices. In Proceedings of the forty-first annual ACM symposium on Theory of computing, pp. 169-178.
[7]. Zvika Brakerski and Vinod Vaikuntanathan. (2012) Efficient fully homomorphic encryption from (standard) LWE. SIAM Journal on computing, 43(2):831-871.
[8]. David Cash, Dennis Hofheinz, Eike Kiltz, and Chris Peikert. (2012) Bonsai trees, or how to delegate a lattice basis. Journal of cryptology, 25(4):601-639.
[9]. Miklós Ajtai. (1996) Generating hard instances of lattice problems. In Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, pp. 99-108.
[10]. Oded Regev. (2009) On lattices, learning with errors, random linear codes, and cryptography. Journal of the ACM (JACM), 56(6):1-40.
[11]. Avrim Blum, Adam Kalai, and Hal Wasserman. (2003) Noise-tolerant learning, the parity problem, and the statistical query model. Journal of the ACM (JACM), 50(4):506-519.
[12]. Vadim Lyubashevsky, Chris Peikert, and Oded Regev. (2013) On ideal lattices and learning with errors over rings. Journal of the ACM (JACM), 60(6):1-35.
[13]. Adeline Langlois and Damien Stehlé. Worst-case to average-case reductions for module lattices. Designs, Codes and Cryptography, 75(3):565- 599, 2015.
[14]. Gilbert Baumslag, Nelly Fazio, Antonio R Nicolosi, Vladimir Shpilrain, and William E Skeith. (2011) Generalized learning problems and applications to non-commutative cryptography. In International Conference on Provable Security, Springer, pp.324-339.
[15]. Roope Vehkalahti, Camilla Hollanti, Jyrki Lahtonen, and Kalle Ranto. (2009) On the densest mimolattices from cyclic division algebras. IEEE Transactions on Information Theory, 55(8):3751-3780.
[16]. Frederique Oggier and BA Sethuraman. (2012) Quotients of orders in cyclic algebras and space-time codes. arXiv preprint arXiv:1210.7044.
[17]. Chris Peikert, Oded Regev, and Noah Stephens-Davidowitz. (2017) Pseudorandomness of ring-lwe for any ring and modulus. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 461-473.
[18]. Chris Peikert. (2010) An efficient and parallel gaussian sampler for lattices. In Annual Cryptology Conference, Springer, pp. 80-97.
[19]. Frédérique Oggier, Jean-Claude Belfiore, Emanuele Viterbo, et al. (2007) Cyclic division algebras: A tool for space--time coding. Foundations and Trends® in Communications and Information Theory, 4(1):1-95.
[20]. Irving Reiner. (1975) Maximal orders. New York-London.
[21]. Charles Everitt Grover. (2020) LWE over cyclic algebras: A novel structure for lattice cryptography.
[22]. Charles Grover, Andrew Mendelsohn, Cong Ling, and Roope Vehkalahti. (2022) Non-commutative ring learning with errors from cyclic algebras. Journal of Cryptology, 35(3):1-67.
[23]. László Babai. (1986) On lovász’lattice reduction and the nearest lattice point problem. Combinatorica, 6(1):1-13.
[24]. Chris Peikert and Zachary Pepin. (2019) Algebraically structured LWE, revisited. In Theory of Cryptography: 17th International Conference, TCC 2019, Nuremberg, Germany, December 1-5, 2019, Proceedings, Part I 17, Springer, pp. 1-23.
[25]. Nathan Jacobson. (2009) Finite-dimensional division algebras over fields. Springer Science & Business Media.
[26]. Carl Bootland, Wouter Castryck, and Frederik Vercauteren. (2020) On the security of the multivariate ring learning with errors problem. Open Book Series, 4(1):57-71.
[27]. Jyrki Lahtonen, Nadya Markin, and Gary McGuire. (2008) Construction of multiblock space--time codes from division algebras with roots of unity as nonnorm elements. IEEE transactions on information theory, 54(11):5231-5235.
Cite this article
Zhao,J. (2023). From learning with errors (LWE) problem to CLWE problem. Theoretical and Natural Science,26,286-298.
Data availability
The datasets used and/or analyzed during the current study will be available from the authors upon reasonable request.
Disclaimer/Publisher's Note
The statements, opinions and data contained in all publications are solely those of the individual author(s) and contributor(s) and not of EWA Publishing and/or the editor(s). EWA Publishing and/or the editor(s) disclaim responsibility for any injury to people or property resulting from any ideas, methods, instructions or products referred to in the content.
About volume
Volume title: Proceedings of the 3rd International Conference on Computing Innovation and Applied Physics
© 2024 by the author(s). Licensee EWA Publishing, Oxford, UK. This article is an open access article distributed under the terms and
conditions of the Creative Commons Attribution (CC BY) license. Authors who
publish this series agree to the following terms:
1. Authors retain copyright and grant the series right of first publication with the work simultaneously licensed under a Creative Commons
Attribution License that allows others to share the work with an acknowledgment of the work's authorship and initial publication in this
series.
2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the series's published
version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgment of its initial
publication in this series.
3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and
during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See
Open access policy for details).