4 ms·

Meta: I can understand the math problems behind RSA and DH, and the general concepts of EC, but all stuff for post-quantum algorithms I have yet to have a intui

Meta: I can understand the math problems behind RSA and DH, and the general concepts of EC, but all stuff for post-quantum algorithms I have yet to have a intuitive understanding even after reading / watching a bunch of videos trying to explain things.

WaitWaitWha 2y ago
I was in the same exact boat. I just could not digest it. I found AI (combo Grok & ChatPPT 4o) to be the best resource for this. It was able to break it down to digestible chunks, then pull it together that made sense. It even made suggestions what math areas I need to brush up on.
- bryan0 2y ago
  I just did the same thing. Claude (sonnet 3.7) walked me through a toy implementation of the algorithm.
FateOfNations 2y ago
Yeah, I'm going to have to spend some time trying to understand the math too. I was mostly waiting for things to calm down standardization wise. This newly selected algorithm is based on error correction codes (the same ones used in communications protocols), which look interesting.
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 ago
  Solving `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`).
iovoid 2y ago
The hash-based one (SPHINCS+) is probably the easiest to understand as its security hinges on hashes being secure, and some statistics. I found https://er4hn.info/blog/2023.12.16-sphincs_plus-step-by-step/ https://er4hn.info/blog/2023.12.16-sphincs_plus-step-by-step... to be a nice introduction.

WaitWaitWha 2y ago

I was in the same exact boat. I just could not digest it. I found AI (combo Grok & ChatPPT 4o) to be the best resource for this. It was able to break it down to digestible chunks, then pull it together that made sense. It even made suggestions what math areas I need to brush up on.

bryan0 2y ago
I just did the same thing. Claude (sonnet 3.7) walked me through a toy implementation of the algorithm.

FateOfNations 2y ago

Yeah, I'm going to have to spend some time trying to understand the math too. I was mostly waiting for things to calm down standardization wise. This newly selected algorithm is based on error correction codes (the same ones used in communications protocols), which look interesting.

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 ago
Solving `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`).

iovoid 2y ago

The hash-based one (SPHINCS+) is probably the easiest to understand as its security hinges on hashes being secure, and some statistics. I found https://er4hn.info/blog/2023.12.16-sphincs_plus-step-by-step/ https://er4hn.info/blog/2023.12.16-sphincs_plus-step-by-step... to be a nice introduction.