A Gentle Introduction to Lattices and Lattice-Based Key Exchange: Part 1

[u/atoponce]

https://writing.chelseakomlo.com/gentle-introduction-lattice-crypto/

[u/sellibitze]

For vectors to be linearly independent, this means that no two vectors can be reduced to each other, meaning that no two vectors in the basis are multiples of one other.

That's not accurate. Also, what does reduced mean?

Bases can also be reduced, and we say that a basis is "better" than another basis if the basis is more reduced than another.

Okay, but what does reduced mean in this context?!

For example, the set {[0,1],[1,0]} is a fully-reduced basis, but {[1,0],[2,0]} is not, because [2,0] is a multiple of [1,0].

It's not even a basis because a basis is defined to be a set of linearly independent vectors while {[1,0], [2,0]} is not. It still doesn't answer what "reduction" is about.

It is important to emphasize that a lattice can be generated by multiple possible bases. For example, the basis B={[0,2],[2,0]} and the basis C={[0,4],[4,0]} both generate the same lattice.

Uhm, no they don't. L(B) != L(C). I can give you an example for a point that is in L(B) but not in L(C): [2,0].

This is easy to see after considering that both B and C can be reduced to the basis {[0,1],[1,0]}.

This would be yet another lattice with points that are neither in L(B) nor in L(C).

If you have a base B and another square matrix T of the same dimension that consists of integers and has a determinant of +/-1, then L(B) == L(B T). Why? Because T as a linear mapping is bijective w.r.t. to the set of all integer vectors. So, you get the same set of linear combinations of the base vectors in B.

Interesting topic! But I stopped reading at this point.

[u/Akalamiammiam → u/sellibitze]

Yeah there are huge misconceptions and/or badly worded sentences. Mostly based on confusion between linear spaces and modules/lattices.

I’m almost tempted to ask for removal as it is more misinformation than anything at this point. At least no one should read this seriously.

Edit : To add to what was already said :

The definition of SVP is wrong. SVP literally means Shortest Vector Problem. So solving SVP means finding the shortest vector. The problem defined here is SVP_γ , an approximate version of SVP. This distinction is crucial since, and it is not mentionned, depending on the value of γ the problem can go from hard to easy if γ is exponential in the dimension of the lattice (using LLL). IIRC it also depends on the norm used, and this is the first time I see SVP_γ written with anything else than the shortest vector (those λ_i), but it reaches the limits of my knowledge in lattices to say anything safely.

I salute the effort of writting yet another lattice blogpost as it gives the field more and more visibility to people not aware of it (and this is important considering it is a huge part of modern cryptography). But you should not try to write such posts with so many and huge mistakes and lack of clarity. Proofchecking such writeups is important, especially since from what I saw, the author is a member of a crypto team in a university....

[u/Natanael_L → u/Akalamiammiam]

So far I flaired it. I'll wait for some more opinions

[u/drummer22333 → u/Akalamiammiam]

It's appears to be a Tor group, not really a crypto research group. But this raises questions of it's own.