Resaang

Eli is directionally correct that lattice-crypto has more algebraic structure than hash-crypto and that this structure could theoretically be used to break it, altho i think the newness of lattices is a bit overstated. Lattice crypto originally started as offensive cryptanalysis, not a defensive structure. In cryptography, you generally want all-or-nothing systems. If I try to guess your password and I’m even one character off, I should get no clue about how close I was or which characters were correct. In practice, this is difficult. For example, if I respond slightly slower depending on how many characters are correct, then you can use timing to gradually extract the complete password. This is where timing attacks come from. Lattices are like vector fields but instead of taking any linear combination of the basis vectors (with real coefficients) you only accept integer coefficients. So you have some building blocks and you can combine them but not shrink or stretch them. It’s similar to how crystals have evenly spaced atoms in multiple dimensions. The basic idea in lattice attacks is that you find a bunch of clues or partial solutions and make each one a basis vector. Then you try to find (“Learn”) a combination of them whose sum is small (Short Integer Solution, SIS), which simultaneously combines the partial solutions to make a complete solution. This method can be used to attack elliptic curve signatures when the nonces used are biased, not uniformly distributed. Lattice signatures and zk-proofs use similar ideas but defensively, to find problems that resist lattice attacks. Learning-With-Errors (LWE) essentially takes that short integer solution and adds noise to it so that an attacker cannot use straightforward linear algebra to solve it. Then you can prove you know the solution without revealing it by solving a related problem. Hash-crypto works quite differently. It basically uses one-way functions (hashes) as a building block and you prove you know a secret by selectively revealing the inputs to a publicly-committed output. Since hash-crypto doesn’t have any algebraic equations in its structure, people say it has less attack surface, which is true. The tradeoff is that you have much larger signatures and it doesn’t have nice threshold schemes or key exchange algorithms or encryption, which all rely on that missing algebraic structure. Both hash-crypto and lattice-crypto rely on the security of hash functions, tho, so the reduction in attack surface is a clear win for hash-crypto. It would be great if we just had full security-proofs for some crypto-system so we wouldn’t have to rely on heuristics like this, but that’s just where we are in our scientific knowledge as a species. Maybe AI will help us solve P =? NP and that will lead to provably secure systems.