Are there any hard problems related to matrix factorization?

Suppose $E$ is hermitian with public eigenvectors such that $U^T\Lambda U = E$ with $U$ public but $E,\Lambda$ secret. Given $X$ secret, we would "encrypt" it as $EX = U^T\Lambda UX$ can you create instances such that $f(U,EX) \rightarrow X$ is not polynomial time?

I believe matrix inversion is polytime, but I am not sure if this is worst case or average case. First thing you can do is knock off the first term so $UEX = \Lambda UX$, and with $U$ public, but $\Lambda,X$ chosen perhaps to make the problem hard, is this still possible in polytime?


1 Answer 1


This is not related to your particular factorization problem (I believe), but is related to a hard matrix factorization problem (I believe). It is known as the "Lattice Isometry Problem" (or perhaps it is the "Lattice isomorphism problem" --- I will call it LIP either way). Stated in matrix terms, this problem is, given two matrices $\mathbf{B}_1, \mathbf{B}_2\in\mathbb{R}^{n\times k}$, determine if they generate isometric lattices.

A lattice generated by some basis $\mathbf{B}\in\mathbb{R}^{n\times k}$ is defined as:

$$\mathcal{L}(\mathbf{B}) = \{\vec x\in\mathbb{R}^n\mid \exists \vec y\in\mathbb{Z}^k\text{ s.t. }\vec x = \mathbf{B}\vec y\} = \mathbf{B}\mathbb{Z}^k$$

As defined, basis of a given lattice are specified up to multiplication by an (integer) change-of-basis matrix on the right, i.e. if $\mathbf{B}\in\mathbb{R}^{n\times k}$ is the basis of a lattice, and $\mathbf{U}\in\mathsf{SL}_k(\mathbb{Z})$, then $\mathbf{BU}$ is a basis of the same lattice.

Two lattices $L, L'$ are said to be isometric if they are related by an orthogonal transformation of determinant 1. In terms of matrices, $\mathcal{L}(\mathbf{B})$ is isometric to $\mathcal{L}(\mathbf{B}')$ if there exists some $\mathbf{O}\in SO(n)$ such that $\mathbf{O}\mathbf{B} = \mathbf{B}'$.

All combined, this means that the lattice isometry problem takes as input two matrices $\mathbf{B}, \mathbf{B}'$, and attempts to factor $\mathbf{B}' = \mathbf{OBU}$ for $\mathbf{O}\in SO(n)$, $\mathbf{U}\in\mathsf{SL}_k(\mathbb{Z})$, so can be seen as a certain matrix factorization problem. I don't know precise results for the hardness of LIP, but a certain "natural" extension of it to the ideal lattice setting becomes easier than one would hope for. This is the content of the Gentry-Szydlo algorithm, which determines whether a certain ideal lattice is isometric to $\mathbb{Z}^k$, which can also be described as "having an orthonormal basis".

  • $\begingroup$ Thank you very much. This gives me a place to start googling. $\endgroup$ Apr 14, 2021 at 20:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.