At Eurocrypt 2003, Szydlo presented a search to distinguish reduction for the Lattice Isomorphism Problem (LIP) on the integer lattice \(\mathbb {Z}^n\) . Here the search problem asks to find an isometry between \(\mathbb {Z}^n\) and an isomorphic lattice, while the distinguish variant asks to distinguish between a list of auxiliary lattices related to \(\mathbb {Z}^n\) . In this work we generalize Szydlo’s search to distinguish reduction in two ways. Firstly, we generalize the reduction to any lattice isomorphic to \(\varGamma ^n\) , where \(\varGamma \) is a fixed base lattice. Secondly, we allow \(\varGamma \) to be a module lattice over any number field. Assuming the base lattice \(\varGamma \) and the number field K are fixed, our reduction is polynomial in n. As a special case we consider the module lattice \(\mathcal {O}^2\) used in the module-LIP based signature scheme HAWK, and we show that one can solve the search problem, leading to a full key recovery, with less than \(2d^2\) distinguishing calls on two lattices each, where d is the degree of the power-of-two cyclotomic number field and \(\mathcal {O}\) its ring of integers.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

A Search to Distinguish Reduction for the Isomorphism Problem on Direct Sum Lattices

  • Daniël van Gent,
  • Wessel van Woerden

摘要

At Eurocrypt 2003, Szydlo presented a search to distinguish reduction for the Lattice Isomorphism Problem (LIP) on the integer lattice \(\mathbb {Z}^n\) . Here the search problem asks to find an isometry between \(\mathbb {Z}^n\) and an isomorphic lattice, while the distinguish variant asks to distinguish between a list of auxiliary lattices related to \(\mathbb {Z}^n\) . In this work we generalize Szydlo’s search to distinguish reduction in two ways. Firstly, we generalize the reduction to any lattice isomorphic to \(\varGamma ^n\) , where \(\varGamma \) is a fixed base lattice. Secondly, we allow \(\varGamma \) to be a module lattice over any number field. Assuming the base lattice \(\varGamma \) and the number field K are fixed, our reduction is polynomial in n. As a special case we consider the module lattice \(\mathcal {O}^2\) used in the module-LIP based signature scheme HAWK, and we show that one can solve the search problem, leading to a full key recovery, with less than \(2d^2\) distinguishing calls on two lattices each, where d is the degree of the power-of-two cyclotomic number field and \(\mathcal {O}\) its ring of integers.