Simultaneous Diagonalization of Incomplete Matrices and Applications

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

Paper 2020/631

Simultaneous Diagonalization of Incomplete Matrices and Applications

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

Abstract

We consider the problem of recovering the entries of diagonal matrices ${U_{a}}_{a}$ for $a = 1, \dots, 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.

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: Published elsewhere. Fourteenth Algorithmic Number Theory Symposium ANTS-XIV
Keywords: Linear Algebra Cryptanalysis Approximate Common Divisor Problem Multilinear Maps
Contact author(s): jean-sebastien coron @ uni lu
luca notarnicola @ uni lu
gabor wiese @ uni lu
History: 2021-06-24: revised; 2020-06-03: received; See all versions
Short URL: https://ia.cr/2020/631
License: CC BY

BibTeX

@misc{cryptoeprint:2020/631,
      author = {Jean-Sébastien Coron and Luca Notarnicola and Gabor Wiese},
      title = {Simultaneous Diagonalization of Incomplete Matrices and Applications},
      howpublished = {Cryptology {ePrint} Archive, Paper 2020/631},
      year = {2020},
      url = {https://eprint.iacr.org/2020/631}
}