Testing isomorphism of lattices over CM-orders

A CM-order is a reduced order equipped with an involution that mimics complex conjugation. The Witt-Picard group of such an order is a certain group of ideal classes that is closely related to the "minus part" of the class group. We present a deterministic polynomial-time algorithm for the following problem, which may be viewed as a special case of the principal ideal testing problem: given a CM-order, decide whether two given elements of its Witt-Picard group are equal. In order to prevent coefficient blow-up, the algorithm operates with lattices rather than with ideals. An important ingredient is a technique introduced by Gentry and Szydlo in a cryptographic context. Our application of it to lattices over CM-orders hinges upon a novel existence theorem for auxiliary ideals, which we deduce from a result of Konyagin and Pomerance in elementary number theory.

• Publication year

  2017

• Venue

  SIAM journal on computing (Print)

• Publication date

  2017-06-22

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1137/17M115390XarXiv 1706.07373
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Universal gradings of orders

  2017cited by this paper
• Algorithms on Ideal over Complex Multiplication order

  2016cited by this paper
• Roots of Unity in Orders

  2015influential reference
• Algorithms for Commutative Algebras Over the Rational Numbers

  2015influential reference
• Revisiting the Gentry-Szydlo Algorithm

  2014influential reference
• Lattices with Symmetry

  2014cited by this paper
• Determining cyclicity of finite modules

  2014cited by this paper
• On Primes Recognizable in Deterministic Polynomial Time

  2013influential reference
• Candidate Multilinear Maps from Ideal Lattices

  2013cited by this paper
• Algorithmic Number Theory: Lattices, Number Fields, Curves and Cryptography

  2011cited by this paper
• Factoring into coprimes in essentially linear time

  2005cited by this paper
• Cryptanalysis of the Revised NTRU Signature Scheme

  2002cited by this paper
• Abelian Varieties with Complex Multiplication and Modular Functions

  1997influential reference
• Algorithms in algebraic number theory

  1992influential reference
• Computing the Structure of Finite Algebras

  1990cited by this paper
• Factoring polynomials with rational coefficients

  1982cited by this paper
• Introduction to commutative algebra

  1969influential reference

• A search to distinguish reduction for the isomorphism problem on direct sum lattices

  2025cites this paper
• Exploiting the Symmetry of Zn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathbb {Z}^n$$\end{document}: Randomizat

  2025cites this paper
• Cryptanalysis of rank-2 module-LIP: a single real embedding is all it takes

  2025cites this paper
• Commitment Schemes Based on Module-LIP

  2025cites this paper
• HAWK: Having Automorphisms Weakens Key

  2025cites this paper
• Special Genera of Hermitian Lattices and Applications to HAWK

  2025influential citation
• Ideally HAWKward: How Not to Break Module-LIP

  2025cites this paper
• Cryptanalysis of Rank-2 Module-LIP with Symplectic Automorphisms

  2024influential citation
• A reduction from Hawk to the principal ideal problem in a quaternion algebra

  2024influential citation
• Cryptanalysis of rank-2 module-LIP in Totally Real Number Fields

  2024influential citation
• On hermitian decomposition lattices and the module-LIP problem in rank 2

  2024cites this paper
• Generating cryptographically-strong random lattice bases and recognizing rotations of Zn

  2021cites this paper
• Fast Reduction of Algebraic Lattices over Cyclotomic Fields

  2020cites this paper
• Algebraic and Euclidean Lattices: Optimal Lattice Reduction and Beyond

  2019cites this paper
• Universal gradings of orders

  2017cites this paper
• Rank-2 module-LIP with special matrices

  year unknowncites this paper
• Dimension-Reducing Algorithms for Quaternion Ideal-SVP

  year unknowncites this paper