Simultaneous Diagonalization of Incomplete Matrices and Applications

English

Coron, Jean-Sébastien[University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC) >]

Notarnicola, Luca[University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Computer Science and Communications Research Unit (CSC) >]

Wiese, Gabor[University of Luxembourg > Faculty of Science, Technology and Communication (FSTC) > Mathematics Research Unit >]

Dec-2020

Proceedings of the Fourteenth Algorithmic Number Theory Symposium (ANTS-XIV), edited by Steven Galbraith, Open Book Series 4, Mathematical Sciences Publishers, Berkeley, 2020

4

127-142

Yes

International

[en] We consider the problem of recovering the entries of diagonal matrices {U_a}_a for a = 1, . . . , t from multiple “incomplete” samples {W_a}_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.