There is a statement in the article of "Public-Key Cryptosystems from Lattice Reduction Problems" that presents GGH encryption scheme:

"The cryptanalytic problem underlying our scheme is to approximate the closest vector problem (CVP) in a lattice, given a "non-reduced" basis for that lattice"

On the other hand, in his survey Peikert says:

" 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. "

Also he says "Because no cryptosystem has yet been proved secure based on CVPγ, we do not formally define that problem here"

Which one is true?


1 Answer 1


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: "As we explain in Section 3, an attack against our trapdoor function amounts to finding an exact solution for some random instance of CVP." 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).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.