Skip to main content

Computing the $M = U U^t$ integer matrix decomposition

Nigel Smart, Katharina Geissler, Computing the $M = U U^t$ integer matrix decomposition. Proc. Cryptography and Coding, pp. 223–233. December 2003. No electronic version available.


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.

Bibtex entry.

Contact details

Publication Admin