论文标题
不完整矩阵和应用的对角线化
Simultaneous Diagonalization of Incomplete Matrices and Applications
论文作者
论文摘要
我们考虑恢复对角线矩阵的条目$ \ {u_a \} _ a $ for $ a = 1，\ ldots，\ ldots，t $从多个“不完整”样本中$ \ {w_a \} _ a $ a $ a $ a $ w_a = pu_aq $，其中$ p $ p $和$ q $ q $ q是低位的，我们根据$ p $和$ Q $的排名来为此问题设计实用算法。这个问题发现了它在加密分析中的动机：我们展示了如何显着改善以前的算法来解决近似的常见分裂问题并打破CLT13密码多线性图。
We consider the problem of recovering the entries of diagonal matrices $\{U_a\}_a$ for $a = 1,\ldots,t$ from multiple "incomplete" samples $\{W_a\}_a$ of the form $W_a=PU_aQ$, where $P$ and $Q$ are unknown matrices of low rank. We devise practical algorithms for this problem depending on the ranks of $P$ and $Q$. This problem finds its motivation in cryptanalysis: we show how to significantly improve previous algorithms for solving the approximate common divisor problem and breaking CLT13 cryptographic multilinear maps.
