Share Email Print
cover

Proceedings Paper

Searching for hard instances of CVP problem-cryptographic perspective
Author(s): Jacek Pardyak
Format Member Price Non-Member Price
PDF $14.40 $18.00
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

Paper Abstract

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.

Paper Details

Date Published: 28 December 2007
PDF: 7 pages
Proc. SPIE 6937, Photonics Applications in Astronomy, Communications, Industry, and High-Energy Physics Experiments 2007, 693723 (28 December 2007); doi: 10.1117/12.784765
Show Author Affiliations
Jacek Pardyak, Warsaw Univ. of Technology (Poland)


Published in SPIE Proceedings Vol. 6937:
Photonics Applications in Astronomy, Communications, Industry, and High-Energy Physics Experiments 2007

© SPIE. Terms of Use
Back to Top