Lattice Crypto worst case to average case

Question

I am currently reading the ETSI white paper Quantum Safe Cryptography and Security

On page 24 one finds the following statement:

Lattice problems also benefit from something called worst-case to average-case reduction, which means that all keys are as hard to break in the easiest case as in the worst case when setting up any of the parameters of a lattice based cryptosystem. In a crypto system like RSA, generating keys involves picking two very large random numbers, that should be prime and should yield a hard instance of the factorization problem, but there is a certain degree of probability of choosing wrong and resulting in a weak security level. In lattice-based cryptography, all possible key selections are strong and hard to solve.

This puzzled me, because I had a different understanding of worst-case to average case reduction in lattices. According to my understanding it means the following:

A lattice cryptosystem on the average (i.e. with randomly chosen keys) is as hard as the hardest problem of the underlying lattice problem. This does not imply that all possible key selections are strong and hard to solve.

Now, who is wrong? Me or ETSI ?

Answer 1

You are right. A worst-case to average-case reduction from problem P to a distribution D over instances of problem Q would mean roughly that $$\Pr_{q\leftarrow D(Q)}[q\text{ is hard} ~|~ \exists~\text{any instance of P that is hard}]>1-\text{negligible}.$$ So even if the support of distribution D is the entire set of instances of problem Q, this does not of course imply that every instance of problem Q is hard.

As an aside, it should be pointed out that the way in which parameters are set for lattice problems does not result in a particularly meaningful worst-case to average-case reduction because the reduction is not tight -- the dimension of the lattices in problem P is smaller than in problem Q.

Still, the big utility of having had such a reduction was that it was this reduction that led people to the problems of (Ring/Module)-SIS and (Ring/Module)-LWE and distributions over these problem instances (uniform) that are currently used in practical lattice cryptography. Analyzing the hardness of random instances of these problems became an independent matter.