Security of the Goldreich–Goldwasser– Halevi (GGH) Scheme There is a statement in the article of &quot;Public-Key Cryptosystems from Lattice Reduction Problems&quot; that presents GGH encryption scheme:
&quot;The cryptanalytic problem underlying our scheme is to approximate the closest vector problem (CVP) in a lattice, given a &quot;non-reduced&quot; basis for that lattice&quot;
On the other hand, in his survey Peikert says:
&quot; Unlike the works of Ajtai and Ajtai-Dwork [AD97], the GGH proposals did not come with any worst-case security guarantees; their conjectured security was merely heuristic. &quot;
Also he says &quot;Because no cryptosystem has yet been proved secure based on CVPγ, we do not formally define that problem here&quot;
Which one is true?
If you look at the GGH paper, they explicitly say that they reduce to a random instance of CVP. At the end of the paragraph on CVP in Section 2.1, it explicitly says: &quot;As we explain in Section 3, an attack against our trapdoor function amounts to finding an exact solution for some random instance of CVP.&quot; Peikert is referring to worst-case guarantees (i.e., hardness for any instance of CVP) whereas GGH considered an average-case problem (when the instance is generated at random).