Simultaneous Diagonalization of Incomplete Matrices and Applications

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 de...

Full description

Saved in:
Bibliographic Details
Published in:arXiv.org 2020-05
Main Authors: Coron, Jean-Sébastien, Notarnicola, Luca, Wiese, Gabor
Format: Article
Language:English
Subjects:
Algorithms
Cryptography
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2331-8422