矩阵分解的硬实例

Question

是否存在与矩阵分解有关的困难问题？

假设E是带有公共特征向量的hermitian，因此U^T\Lambda U = E与U公开，但E,\Lambda秘密。考虑到X的秘密，我们会“加密”它，因为EX = U^T\Lambda UX --您能创建这样的实例，使得f(U,EX) \rightarrow X不是多项式时间吗？

我相信矩阵反演是多时间的，但我不确定这是最坏的情况还是一般的情况。你可以做的第一件事是取消第一个学期所以UEX = \Lambda UX，并与U公开，但\Lambda,X选择可能使问题更难，这仍然有可能在多时间？

Answer 1

这与您的特定分解问题(我相信)无关，而是与硬矩阵分解问题(我相信)有关。它被称为“格Isometry问题”(或者它可能是“格同构问题”-我称它为LIP )。这个问题用矩阵表示，给出两个矩阵\mathbf{B}_1, \mathbf{B}_2\in\mathbb{R}^{n\times k}，确定它们是否生成等距格。

由某个基\mathbf{B}\in\mathbb{R}^{n\times k}生成的格定义为：

\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

根据定义，一个给定格的基由右(整数)基矩阵所指定，即如果\mathbf{B}\in\mathbb{R}^{n\times k}是格的基，而\mathbf{U}\in\mathsf{SL}_k(\mathbb{Z})则\mathbf{BU}是同一格的基。

如果两个格与行列式1的正交变换相关，则称两个格为等距。在矩阵方面，如果存在某种L, L'，则\mathcal{L}(\mathbf{B})与\mathcal{L}(\mathbf{B}')是等距的。

这就意味着格等距问题以两个矩阵\mathbf{B}, \mathbf{B}'为输入，并试图对\mathbf{O}\in SO(n)，\mathbf{U}\in\mathsf{SL}_k(\mathbb{Z})进行因子分解，从而可以看作是一个矩阵分解问题。我不知道嘴唇硬度的精确结果，但它的某种“自然”延伸到理想的格形设置比人们所期望的要容易。这是Gentry-Szydlo算法的内容，它决定了某个理想格是否是\mathbb{Z}^k的等距，这也可以描述为“有一个正交基”。