Education, Science, Technology, Innovation and Life
Open Access
Sign In

Linear Congruence and Reduction on the Learning with Errors Problem

Download as PDF

DOI: 10.23977/tracam.2024.040101 | Downloads: 5 | Views: 330

Author(s)

Lanxuan Xia 1

Affiliation(s)

1 St. Mark's School, 25 Marlboro Road Southborough, Massachusetts, United States

Corresponding Author

Lanxuan Xia

ABSTRACT

We propose an algorithm to solve general linear Diophantine equations and an algorithm to solve linear congruence problems efficiently using LU decomposition, which means unsafety of cryptography systems based on linear congruence equations. Thus, we focus on the generalization of the argument for a specific reduction of the Learning with Error (LWE) problem established in a previous work ([BLP13]) so that LWE can accommodate for more general choices of matrices. More specifically, we relaxed [BLP13]'s constraint on the choice of the identity matrix to general diagonal matrices. Two examples are presented here to show the validity of our results further.

KEYWORDS

Linear Diophantine equations, linear congruence, LU decomposition, LWE, lattice-based cryptography, matrices

CITE THIS PAPER

Lanxuan Xia, Linear Congruence and Reduction on the Learning with Errors Problem. Transactions on Computational and Applied Mathematics (2024) Vol. 4: 1-10. DOI: http://dx.doi.org/10.23977/tracam.2024.040101.

REFERENCES

[1] John R. Silvester (1980) A Matrix Method for Solving Linear Congruences, Mathematics Magazine, 53:2, 90-92, DOI: 10.1080/0025570X.1980.11976833. 
[2] O. Regev. On lattices, learning with errors, random linear codes, and cryptography. J. ACM, 56(6):1–40, 2009. Preliminary version in STOC 2005. 
[3] C. Peikert. Public-key cryptosystems from the worst-case shortest vector problem. In STOC, pages 333–342. 2009.
[4] Z. Brakerski, A. Langlois, C. Peikert, O. Regev, D. Stehlé, Classical hardness of learning with errors, In Proc. of 45th STOC, pp. 575–584 (ACM, 2013).

Downloads: 203
Visits: 12548

Sponsors, Associates, and Links


All published work is licensed under a Creative Commons Attribution 4.0 International License.

Copyright © 2016 - 2031 Clausius Scientific Press Inc. All Rights Reserved.