#### Vol. 4, No. 1, 2020

 Recent Volumes 5: Gauge Theory and Low-Dimensional Topology 4: ANTS XIV 3: Hillman: Poincaré Duality 2: ANTS XIII 1: ANTS X
 The Open Book Series All Volumes About the Series Ethics Statement Purchase Printed Copies Author Index ISSN (electronic): 2329-907X ISSN (print): 2329-9061 MSP Books and Monographs Other MSP Publications
Simultaneous diagonalization of incomplete matrices and applications

### Jean-Sébastien Coron, Luca Notarnicola and Gabor Wiese

Vol. 4 (2020), No. 1, 127–142
##### 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
simultaneous diagonalization, cryptanalysis, linear algebra, multilinear maps in cryptography, approximate common divisor problem
##### Mathematical Subject Classification 2010
Primary: 15A06, 94A60