In its decisional form, the module-Lattice Isomorphism Problem (decision module-LIP) has received first attention in [12]. The authors gave a polynomial-time algorithm to distinguish spinor genera within the genus of a quadratic binary \(\mathcal {O}_F\) -lattice, assuming that \(\mathcal {O}_F\) is a principal ideal domain. However, this algorithm would not impact cryptographic schemes based on decision module-LIP for lattices such as those employed in HAWK [5], i.e., for binary \(\mathcal {O}_K\) -lattices equipped with a Hermitian form (with K a cyclotomic number field). Motivated by HAWK’s framework, we investigate a concept that serves as an analogue of the spinor genus for Hermitian lattices, called special genus. This notion was studied by Shimura [20] who provided a complete set of invariants for describing special genera. Building on this result, we propose an algorithm to determine whether two Hermitian lattices belong to the same special genus. Specifically for HAWK’s lattice and siblings, our algorithm runs in classical polynomial-time. Nevertheless we provide numerical evidence suggesting that the ability to distinguish special genera does not, in practice, constitute a significative advantage for solving decision module-LIP.

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

Special Genera of Hermitian Lattices and Applications to HAWK

  • Guilhem Mureau

摘要

In its decisional form, the module-Lattice Isomorphism Problem (decision module-LIP) has received first attention in [12]. The authors gave a polynomial-time algorithm to distinguish spinor genera within the genus of a quadratic binary \(\mathcal {O}_F\) -lattice, assuming that \(\mathcal {O}_F\) is a principal ideal domain. However, this algorithm would not impact cryptographic schemes based on decision module-LIP for lattices such as those employed in HAWK [5], i.e., for binary \(\mathcal {O}_K\) -lattices equipped with a Hermitian form (with K a cyclotomic number field). Motivated by HAWK’s framework, we investigate a concept that serves as an analogue of the spinor genus for Hermitian lattices, called special genus. This notion was studied by Shimura [20] who provided a complete set of invariants for describing special genera. Building on this result, we propose an algorithm to determine whether two Hermitian lattices belong to the same special genus. Specifically for HAWK’s lattice and siblings, our algorithm runs in classical polynomial-time. Nevertheless we provide numerical evidence suggesting that the ability to distinguish special genera does not, in practice, constitute a significative advantage for solving decision module-LIP.