TY - GEN

T1 - On the lattice isomorphism problem

AU - Haviv, Ishay

AU - Regev, Oded

PY - 2014

Y1 - 2014

N2 - We study the Lattice Isomorphism Problem (LIP), in which given two lattices L1 and L2 the goal is to decide whether there exists an orthogonal linear transformation mapping L1 to L2. Our main result is an algorithm for this problem running in time n O(n)times a polynomial in the input size, where n is the rank of the input lattices. A crucial component is a new generalized isolation lemma, which can isolate n linearly independent vectors in a given subset of Zn and might be useful elsewhere. We also prove that LIP lies in the complexity class SZK.

AB - We study the Lattice Isomorphism Problem (LIP), in which given two lattices L1 and L2 the goal is to decide whether there exists an orthogonal linear transformation mapping L1 to L2. Our main result is an algorithm for this problem running in time n O(n)times a polynomial in the input size, where n is the rank of the input lattices. A crucial component is a new generalized isolation lemma, which can isolate n linearly independent vectors in a given subset of Zn and might be useful elsewhere. We also prove that LIP lies in the complexity class SZK.

UR - http://www.scopus.com/inward/record.url?scp=84902089885&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84902089885&partnerID=8YFLogxK

U2 - 10.1137/1.9781611973402.29

DO - 10.1137/1.9781611973402.29

M3 - Conference contribution

AN - SCOPUS:84902089885

SN - 9781611973389

T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms

SP - 391

EP - 404

BT - Proceedings of the 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014

PB - Association for Computing Machinery

T2 - 25th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014

Y2 - 5 January 2014 through 7 January 2014

ER -