Title :
Finding short vectors in a lattice of Voronoi´s first kind
Author :
McKilliam, Robby ; Grant, Alex
Author_Institution :
Inst. for Telecommun. Res., Univ. of South Australia, Mawson Lakes, SA, Australia
Abstract :
We show that for those lattices of Voronoi´s first kind with known obtuse superbasis, a vector of shortest nonzero Euclidean length can computed in polynomial time by computing a minimum cut in a graph.
Keywords :
computational complexity; computational geometry; graph theory; lattice theory; vectors; Voronoi first kind lattices; n-dimensional lattice; obtuse superbasis; polynomial time; short vector finding; shortest nonzero Euclidean length; weighted graph; Cryptography; Information theory; Lattices; Multiuser detection; Polynomials; Telecommunications; Vectors; Lattices; minimum cut; short vectors;
Conference_Titel :
Information Theory Proceedings (ISIT), 2012 IEEE International Symposium on
Conference_Location :
Cambridge, MA
Print_ISBN :
978-1-4673-2580-6
Electronic_ISBN :
2157-8095
DOI :
10.1109/ISIT.2012.6283833