Author(s)

Lanxuan Xia ¹

Affiliation(s)

¹ 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).

Sponsors, Associates, and Links

---

• International Journal of Power Engineering and Engineering Thermophysics
  
  
• Numerical Algebra and Scientific Computing
  
  
• Journal of Physics Through Computation
  
  
• Transactions on Particle and Nuclear Physics
  
  
• Journal of Probability and Mathematical Statistics
  
  
• Multibody Systems, Nonlinear Dynamics and Control
  
  
• Complex Analysis and Geometry
  
  
• Dynamical Systems and Differential Equations
  
  
• Acoustics, Optics and Radio Physics
  
  
• Progress in Atomic and Molecular Physics
  
  
• Transactions on Condensed Matter Physics
  
  
• Progress in Plasma Physics
  
  
• Combinatorics and Graph Theory
  
  
• Research and Practice of Mathematics & Statistics
  
  
• Nuclear Techniques and Applications
  
  
• Journal of Photonics Research
  
  
• Journal of Compressors and Refrigeration
  
  
• Journal of Theoretical Physics Frontiers
  
  
• Journal of Nonlinear Science and Complexity
  
  
• Vacuum Science Journal
  
  
• Computational Fluid Dynamics