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

Nigel Smart; Katharina Geissler

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

Nigel Smart
, Katharina Geissler

Cryptography and Information Security

Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

Abstract

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
Original language	English
Title of host publication	Cryptography and Coding - IMACC 2003
Publisher	Springer Berlin Heidelberg
Pages	223 - 233
Number of pages	10
Volume	2898
Publication status	Published - Dec 2003

Bibliographical note

Conference Proceedings/Title of Journal: Proc. Cryptography and Coding

Access to Document

http://www.cs.bris.ac.uk/Publications/pub_info.jsp?id=2000027

Handle.net

Persistent link

Cite this

@inproceedings{7d062821c6bd4c9e801f4de48d3ddae1,

title = "Computing the \$M = U U\textasciicircum{}t\$ integer matrix decomposition",

abstract = " The cryptanalysis of Gentry and Szydlo of the revised NTRU signature scheme requires the computation of the integer matrix decomposition \$M = U U\textasciicircum{}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. ",

author = "Nigel Smart and Katharina Geissler",

note = "Conference Proceedings/Title of Journal: Proc. Cryptography and Coding",

year = "2003",

month = dec,

language = "English",

volume = "2898",

pages = "223 -- 233",

booktitle = "Cryptography and Coding - IMACC 2003",

publisher = "Springer Berlin Heidelberg",

address = "Germany",

}

TY - GEN

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

AU - Smart, Nigel

AU - Geissler, Katharina

N1 - Conference Proceedings/Title of Journal: Proc. Cryptography and Coding

PY - 2003/12

Y1 - 2003/12

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

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

M3 - Conference Contribution (Conference Proceeding)

VL - 2898

SP - 223

EP - 233

BT - Cryptography and Coding - IMACC 2003

PB - Springer Berlin Heidelberg

ER -

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

Abstract

Bibliographical note

Access to Document

Handle.net

Fingerprint

Cite this