What does "Worst-case hardness" mean in lattice-based cryptography?

Question

In the wiki page of Lattice-based Cryptography the "Worst-case hardness" is defined as below:

Worst-case hardness of lattice problems means that breaking the cryptographic construction (even with some small non-negligible probability) is provably at least as hard as solving several lattice problems (approximately, within polynomial factors) in the worst case. In other words, breaking the cryptographic construction implies an efficient algorithm for solving any instance of some underlying lattice problem.

But what is the difference between "worst case hardness" in lattice-based cryptography and "average case hardness" in standard cryptography based on discrete logarithm, say ElGamal Encryption?

It's seems to be confusing. For instance, breaking into ElGamal Encryption also leads to breaking several other cryptographic constructions and solving well-known number theoretic hard problem: computational Diffie-Hellman. However, that one does not considered a "worst case hardness".

Answer 1

One line: worst means any and average means random.

Lattice-based cryptosystem

Let me restate. Fix security parameter $n$. What the reduction shows is the existence of a solver for the lattice problem on input any $n$-dimensional lattice using the adversary breaking a lattice-based cryptosystem with the security parameter $n$ on the average case.

Since we can solve any instance, we can solve the hardest one of dimension $n$.

ElGamal encryption - average-case

We have a reduction that converts a random instance of the CDH/DDH problem into a random problem of one-wayness/indistinguishability game. This means that the security is based on the average-case hardness of the problem.

ElGamal encryption - worst-case

Correctly speaking, the security of the El Gamal encryption scheme can be based on the worst-case hardness of the DL-like problems over the group instead of the security parameter.

Fix a prime-order group. We can convert any instance of the DL/CDH/DDH problem on the group to a random instance of the problem on the same group. ( This property is as known as the random self reducibility.) Combining it with the previous reduction, we can say the security is based on the worst-case hardness of the problem over the fixed group.

Answer 2

Worst case hardness means that the whatever problem you use and is based in lattice base problems then it is hard in worst case (means it is verrrry hard to solve by polynomial and quantum(exists?) computing. In contrast RSA (prime factoring) and discrete log cryptosystems are not in all instances hard in worst case but in average that means that if for instance i give you an instance of the problem ($N=21$) you know the solution ($p=7$,$q=3$ or $p=21$ and $p=1$). Thus the problems are "hard" under certain circumstances (big prime number factors, and appropriate groups where discrete log is hard to be solves) and not every time as in lattice based problems