Skip to main content
added 441 characters in body
Source Link

How do I uniquely determine a standard Gram matrix for a lattice? Are there any other definitions of "standard Gram matrix" for lattices? Do you have any literature references in which "standard Gram matrix" is defined for any reason?

Yes, this has been done in A Canonical Form for Positive Definite Matrices. In particular, for positive definite $A$ (Gram matrices of positive definite lattices are positive definite), they first define $A, B$ to be arithmetically equivalent if $A = U^tBU$ for uniomdular $U$.

They then define a mapping

$$A\mapsto Can(A)$$ such that

  1. $Can(A)$ is equivalent to $A$, and
  2. For any unimodular $U$, $Can(U^tAU)=Can(A)$.

Their (broad) strategy is to reduce to the case of graphs, for which there are recent quasi-polynomial time algorithms. This somewhat limits the maximum dimension they can handle (computationally) --- it appears they go up to dimension 40 at the most.

As for adNote that this problem is thought to be hard though -hoc approaches-- it would imply a solution to the Lattice Isomorphism Problem. Efficient algorithms for canonical formsthis have been open for gram matricesquite a while (there has been some interest for lattices10+ years), it is apparently a knownand recently two cryptosystems have been proposed assuming (variants of) this problem are hard, see section 1.2so now one can concretely say that efficient algorithms would break cryptographic proposals (so if you find one, there is a more obvious motivation to write it up).

How do I uniquely determine a standard Gram matrix for a lattice? Are there any other definitions of "standard Gram matrix" for lattices? Do you have any literature references in which "standard Gram matrix" is defined for any reason?

Yes, this has been done in A Canonical Form for Positive Definite Matrices. In particular, for positive definite $A$ (Gram matrices of positive definite lattices are positive definite), they first define $A, B$ to be arithmetically equivalent if $A = U^tBU$ for uniomdular $U$.

They then define a mapping

$$A\mapsto Can(A)$$ such that

  1. $Can(A)$ is equivalent to $A$, and
  2. For any unimodular $U$, $Can(U^tAU)=Can(A)$.

Their (broad) strategy is to reduce to the case of graphs, for which there are recent quasi-polynomial time algorithms. This somewhat limits the maximum dimension they can handle (computationally) --- it appears they go up to dimension 40 at the most.

As for ad-hoc approaches for canonical forms for gram matrices for lattices, it is apparently a known problem, see section 1.2.

How do I uniquely determine a standard Gram matrix for a lattice? Are there any other definitions of "standard Gram matrix" for lattices? Do you have any literature references in which "standard Gram matrix" is defined for any reason?

Yes, this has been done in A Canonical Form for Positive Definite Matrices. In particular, for positive definite $A$ (Gram matrices of positive definite lattices are positive definite), they first define $A, B$ to be arithmetically equivalent if $A = U^tBU$ for uniomdular $U$.

They then define a mapping

$$A\mapsto Can(A)$$ such that

  1. $Can(A)$ is equivalent to $A$, and
  2. For any unimodular $U$, $Can(U^tAU)=Can(A)$.

Their (broad) strategy is to reduce to the case of graphs, for which there are recent quasi-polynomial time algorithms. This somewhat limits the maximum dimension they can handle (computationally) --- it appears they go up to dimension 40 at the most.

Note that this problem is thought to be hard though --- it would imply a solution to the Lattice Isomorphism Problem. Efficient algorithms for this have been open for quite a while (there has been some interest for 10+ years), and recently two cryptosystems have been proposed assuming (variants of) this problem are hard, so now one can concretely say that efficient algorithms would break cryptographic proposals (so if you find one, there is a more obvious motivation to write it up).

Source Link

How do I uniquely determine a standard Gram matrix for a lattice? Are there any other definitions of "standard Gram matrix" for lattices? Do you have any literature references in which "standard Gram matrix" is defined for any reason?

Yes, this has been done in A Canonical Form for Positive Definite Matrices. In particular, for positive definite $A$ (Gram matrices of positive definite lattices are positive definite), they first define $A, B$ to be arithmetically equivalent if $A = U^tBU$ for uniomdular $U$.

They then define a mapping

$$A\mapsto Can(A)$$ such that

  1. $Can(A)$ is equivalent to $A$, and
  2. For any unimodular $U$, $Can(U^tAU)=Can(A)$.

Their (broad) strategy is to reduce to the case of graphs, for which there are recent quasi-polynomial time algorithms. This somewhat limits the maximum dimension they can handle (computationally) --- it appears they go up to dimension 40 at the most.

As for ad-hoc approaches for canonical forms for gram matrices for lattices, it is apparently a known problem, see section 1.2.