> that's not really what he's saying. he's saying that adding structure for speed also tends to add structure for breaking.

I may not have been clear in my reasoning. Modern crypto research does rely on stress testing newly crafted cryptosystems against peer researshers, who will try to find a flaw in the system, think of a way of applying an existing attack, or make a new adapted one. It is to say that published hash function or block cipher schemes are not necessarily secure; the process of peer-reviewing before publication only (partially) ensures the good-redaction of the article and checks for blatant scientific errors. The consequence is then that every single change to a cryptosystem, like using optimized structures for speed, memory, sizes of keys, …, changing the key generation algorithm, using parallelism or even creating an additional functionality using private data (e.g. the secret key) may result in a partial or total compromise in security.

So, in clear: yes, using time-optimized structures for crypto mays lead to new attacks, but this is just a particular case and it does not in any tell that faster necessarily means weaker, just that crypto is hard, since anything can go wrong (consider timing attacks for instance).

> it makes you wonder whether all this new-fangled crypto based on clever maths is such a good idea. maybe the old school block ciphers that simply throw enough non-commuting, non-linear operations at the problem to make it "too hard" are smarter than they look. but of course, they tend to be symmetric only (and i am not sure the distinction above is real; you can try to formalise why old block cipher systems are hard, and if you do so you come up with things like aes, and then again you open the door to worrying about algebraic attacks...)

This is an usual rant against “post-quantum” crypto. Old schemes were not all bad, but they were actually impractical when studying their security. Consider DES, that basically just mangles bits with other bits depending on previous bits. There is virtually no connection between studying the difficulty of cracking DES and the rest of research. You will have to look for individual bit propagation and other dirty stuff (and of course check for obvious attacks using linear cryptanalysis). Well, the point is that, this way, you only some public research of the matter. Maybe a few hundreds will seriously try and find a way to decrypt DES. And they won't dedicate their career to this. This means that the probability that an effective attack being privately (say, by the NSA) discovered is not so low.

On the other hand, when you know most attacks against your cryptosystem would imply the solving of a NP-problem, you can rely on a ton of research material (mathematics and computer science). The point is that solving any NP-problem would be a revolution in lots of mathematics fields (especially CS-related). In other words, you have thousands over thousands of researchers devoting a lot of their time to try and break your cipher. And the probability that a lone organization finds a solution first is very low.

Of course, as noted by the original author, you could still have other attacks, that would not compromise the NP-hardness:

> The same theoreticians also say that lattice-based cryptography has "strong provable security guarantees". If this istaken literally then it is false advertising. The correct advertising is that a broad class of attacks against various attice-based cryptosystems can be converted, with limited loss of speed and success probability, into attacks against ertain standard lattice problems.

This is exactly what happens when adding "structure" to your keys. Relying on the NP-problem basically means that what your adversary sees is indistinguishable from random (when solving a NP-problem, your solution must work for all instances). So the "mangling" from old crypto is brought back here. However, this way better, as the part that is to be studied is smaller and more flexible since we are now considering controlled data and we can make sure that a mangling brings a good distribution.

The attack which was presented here basically does that. It found a flaw in the way one lattice-based crypto scheme relied on a NP-problem.

Note: by solving an NP-problem, I mean find a polynomial-time solution to a question known as "NP-hard"

tl;dr: "this new-fangled crypto" is not about using "clever maths" but having a more important pool of knowledge to rely on