+Ajtai in 1996, he could have titled .... he titled it "The fall and rise of knapsack cryptography". Not only is this... it's a worst case to average case reduction. Even if you put aside the assumption that LLL works, and is an exact oracle, which seems to be the case, the biggest experiments you could run were in the range where LLL would run well. In the 90s, I wasn't doing much at first part of the 90s, but.. no, not even that. I had a driver's license, though. But at that point, we knew LLL, er, the shortest vector problem is not polytime solvable. In 1998, I proved it was also NP-hard. Before the NP-hard conjecture that maybe LLL solves the shortest vector problem in polytime, before that it was a reasonable conjecture. If there is some hardness at all, then knapsack is the technique you want to use, because you don't have to guess or bet on one or another distribution. So he titled his paper "The fall and rise of knapsack cryptography" (laughter). How come this paper started after Ajtai's result? Are people still suggesting knapsack cryptosystems even though ... why are they proposing bad cryptosystems after Ajtai found how to do it correctly? Some of these works were attacking Ajtai's functions. "[A converse of the Ajtai-Dwork security proof](http://diyhpl.us/~bryan/papers2/security/cryptography/A%20converse%20to%20the%20Atjai-Dwork%20security%20proof%20and%20its%20cryptographic%20implications%20-%201999.pdf)" and "[Cryptanalysis of the Ajtai-Dwork cryptosystem](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.52.7504&rep=rep1&type=pdf)". The attack was a reduction in the other direction. And for the conference they chose a more aggressiv title (the one with "cryptanalysis" in the title). And that's how crypto goes on- they are gladiators; 400 people go to Crypto, and they want to see people going there and killing each other just for the sake of the show. But anyway, the punchline is that, these attacks, these reductions, you could always look at them in both ways. When you give a reduction between the two problems, you can think of it as saying, knapsack problem is easy because it's no harder than the other one. But you could also think that we are showing the knapsack problem is hard, you can give reductions in both directions. Either they fail at the same time, or they stand together. This was kind of clear at that point.

+A: So... depends on which problem you start from. There have been classic reductions that show hardness of .. for this function. So the difference is that Ajtai proved that the problem was as hard as [finding short linear independent vectors in the worst case](http://www.csie.nuk.edu.tw/~cychen/Lattices/On%20the%20complexity%20of%20computing%20short%20linearly%20independent%20vectors%20and%20short%20bases%20in%20a%20lattice.pdf). The classic reductions only show you that it is as hard as computing the length of the shortest vector, but we don't find it. So it's still a pretty interesting and ... so this was achieved first by ..Peikert and Eksgreeees... proving this sort of classic hardness for this problem, starting from short vector problem.... quantized version of that proof, but it's not really... the part where quantum was used, it was a part we didn't know how to make classical. But that reinforces our confidence in the problem. These kinds of proofs do not carry over to the algebraic setting. It's an area that is not completely solved.