The cryptanalysis of Gentry and Szydlo of the revised NTRU signature scheme requires the computation of the integer matrix decomposition $M = U U^t$. We propose a heuristic algorithm to compute this decomposition and investigate its properties. Our test implementation of this algorithm in Magma is able to deal with matrices up to $158$ rows and columns.
|Translated title of the contribution||Computing the $M = U U^t$ integer matrix decomposition|
|Title of host publication||Cryptography and Coding - IMACC 2003|
|Publisher||Springer Berlin Heidelberg|
|Pages||223 - 233|
|Number of pages||10|
|Publication status||Published - Dec 2003|