Abstract

We consider the problem of recovering the entries of diagonal matrices ${\left\{U_a\right\}}_a$ for $a=1,\dots ,t$ from multiple “incomplete” samples ${\left\{W_a\right\}}_a$ of the form $W_a=P{U}_{a}Q$, 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.

Keywords

Mathematical Subject Classification 2010

Milestones

Authors