You are here

FAU Collections » FAU Research Repository » FAU Theses and Dissertations

Deterministic and non-deterministic basis reduction techniques for NTRU lattices

Download pdf | Full Screen View

Date Issued:
2002
Summary:
Finding the shortest or a "short enough" vector in an integral lattice of substantial dimension is a difficult problem. The problem is not known to be but most people believe it is [7]. The security of the newly proposed NTRU cryptosystem depends solely on this fact. However, by the definition NTRU lattices possess a certain symmetry. This suggests that there may be a way of taking advantage of this symmetry to enable a new cryptanalytical approach in combination with existing good lattice reduction algorithms. The aim of this work is to exploit the symmetry inherent in NTRU lattices to design a non-deterministic algorithm for improving basis reduction techniques for NTRU lattices. We show how the non-trivial cyclic automorphism of an NTRU lattice enables further reduction. Our approach combines the recently published versions of the famous LLL algorithm for lattice basis reduction with our automorphism utilization techniques.
Title: Deterministic and non-deterministic basis reduction techniques for NTRU lattices.
121 views
31 downloads
Name(s): Socek, Daniel
Florida Atlantic University, Degree grantor
Magliveras, Spyros S., Thesis advisor
Type of Resource: text
Genre: Electronic Thesis Or Dissertation
Issuance: monographic
Date Issued: 2002
Publisher: Florida Atlantic University
Place of Publication: Boca Raton, Fla.
Physical Form: application/pdf
Extent: 57 p.
Language(s): English
Summary: Finding the shortest or a "short enough" vector in an integral lattice of substantial dimension is a difficult problem. The problem is not known to be but most people believe it is [7]. The security of the newly proposed NTRU cryptosystem depends solely on this fact. However, by the definition NTRU lattices possess a certain symmetry. This suggests that there may be a way of taking advantage of this symmetry to enable a new cryptanalytical approach in combination with existing good lattice reduction algorithms. The aim of this work is to exploit the symmetry inherent in NTRU lattices to design a non-deterministic algorithm for improving basis reduction techniques for NTRU lattices. We show how the non-trivial cyclic automorphism of an NTRU lattice enables further reduction. Our approach combines the recently published versions of the famous LLL algorithm for lattice basis reduction with our automorphism utilization techniques.
Identifier: 9780493912752 (isbn), 12933 (digitool), FADT12933 (IID), fau:9805 (fedora)
Collection: FAU Electronic Theses and Dissertations Collection
Note(s): Thesis (M.S.)--Florida Atlantic University, 2002.
Charles E. Schmidt College of Science
Subject(s): Cryptography
Lattice theory
Algorithms
Held by: Florida Atlantic University Libraries
Persistent Link to This Record: http://purl.flvc.org/fcla/dt/12933
Sublocation: Digital Library
Use and Reproduction: Copyright © is held by the author with permission granted to Florida Atlantic University to digitize, archive and distribute this item for non-profit research and educational purposes. Any reuse of this item in excess of fair use or other copyright exemptions requires permission of the copyright holder.
Use and Reproduction: http://rightsstatements.org/vocab/InC/1.0/
Host Institution: FAU
Is Part of Series: Florida Atlantic University Digital Library Collections.