Searching for hard instances of CVP problem-cryptographic perspective
Jacek Pardyak · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 2007
Lattice is regular arrangement of points in Rn. The Closest Vector Problem (CVP) is defined as follow: given a point y in Rn and a lattice basis B find lattice vector Bx closest to y . The CVP problem is believed to be computationally intractable in average. Here we propose a new way to generate hard instances of CVP and a method that allows us to construct a cryptographic trapdoor function based on it. We start with brief introduction to lattices. Next we present a very natural application of lattices in cryptography, i.e. GGH cryptosystem and the way the system was broken. Finally we present our modifications way to generate hard instances of CVP, harder than previously proposed in GGH.