4 ms·
The intuition for ML-KEM-style lattice cryptography is actually kind of straightforward. Generate a secret vector x and a random matrix A; multiply Ax, then cor
by tptacek 2y ago
The intuition for ML-KEM-style lattice cryptography is actually kind of straightforward. Generate a secret vector x and a random matrix A; multiply Ax, then corrupt it with a random vector of errors e, so instead of Ax=b you have Ax+e=b.
Solving Ax=b is like week 2 of undergraduate linear algebra. Solving Ax+e=b, in a lattice setting, is Hard in the same sense factoring is: as you run the steps of elimination to attempt to solve it, the errors compound catastrophically.
- j_chance 2y agoSolving `Ax=b` is easy if `x` can be any value. But if you bound `x` such that all entries must be small (e.g. only zeroes and ones) then the problem is hard: https://en.wikipedia.org/wiki/Short_integer_solution_problem https://en.wikipedia.org/wiki/Short_integer_solution_problem What you described would be closer to learning with errors (https://en.m.wikipedia.org/wiki/Learning_with_errors https://en.m.wikipedia.org/wiki/Learning_with_errors) combined with SIS/SVP. Learning with errors is based on the parity learning problem (https://en.m.wikipedia.org/wiki/Parity_learning https://en.m.wikipedia.org/wiki/Parity_learning) in machine learning, which I take as a positive sign of security. Interestingly you can get information theoretically secure constructions using lattices by tuning the parameters. For example, if you make the `A` matrix large enough it becomes statistically unlikely that more than 1 solution exists (e.g. generate a random binary vector `x` and it's unlikely that an `x'` exists that solves for `b`).