Cryptology ePrint Archive: Report 2020/631

Simultaneous Diagonalization of Incomplete Matrices and Applications

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

Abstract: 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.

Category / Keywords: public-key cryptography / Linear Algebra, Cryptanalysis, Approximate Common Divisor Problem, Multilinear Maps

Original Publication (in the same form): Fourteenth Algorithmic Number Theory Symposium ANTS-XIV

Date: received 27 May 2020

Contact author: jean-sebastien coron at uni lu,luca notarnicola@uni lu,gabor wiese@uni lu

Available format(s): PDF | BibTeX Citation

Version: 20200603:093425 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]