Advanced

Solving NTRU Challenges Using the New Progressive BKZ Library

Mårtensson, Erik LU (2016) EITM01 20161
Department of Electrical and Information Technology
Abstract
NTRU is a public-key cryptosystem, where the underlying mathematical problem is currently safe against large-scale quantum computer attacks. The system is not as well investigated, as for example RSA, and the company behind NTRU has created the NTRU Challenges, to remedy this. These challenges consist of 27 different public keys of increasing size, where the task in each challenge is to calculate (something similar to) the private key. The goal of this thesis was to examine different attacks against the NTRU Challenges and solve as many challenges as possible. By lattice reduction attacks, using a recently published new progressive BKZ algorithm, the first five challenges were solved, while the current biggest solved challenge by any... (More)
NTRU is a public-key cryptosystem, where the underlying mathematical problem is currently safe against large-scale quantum computer attacks. The system is not as well investigated, as for example RSA, and the company behind NTRU has created the NTRU Challenges, to remedy this. These challenges consist of 27 different public keys of increasing size, where the task in each challenge is to calculate (something similar to) the private key. The goal of this thesis was to examine different attacks against the NTRU Challenges and solve as many challenges as possible. By lattice reduction attacks, using a recently published new progressive BKZ algorithm, the first five challenges were solved, while the current biggest solved challenge by any researcher is challenge number seven. (Less)
Please use this url to cite or link to this publication:
author
Mårtensson, Erik LU
supervisor
organization
course
EITM01 20161
year
type
H2 - Master's Degree (Two Years)
subject
keywords
NTRU Challenge, Progressive BKZ, BDD, Enumeration, SVP
report number
LU/LHT-EIT 2016-536
language
English
id
8889328
date added to LUP
2016-08-25 11:53:25
date last changed
2016-08-25 11:53:25
@misc{8889328,
  abstract     = {NTRU is a public-key cryptosystem, where the underlying mathematical problem is currently safe against large-scale quantum computer attacks. The system is not as well investigated, as for example RSA, and the company behind NTRU has created the NTRU Challenges, to remedy this. These challenges consist of 27 different public keys of increasing size, where the task in each challenge is to calculate (something similar to) the private key. The goal of this thesis was to examine different attacks against the NTRU Challenges and solve as many challenges as possible. By lattice reduction attacks, using a recently published new progressive BKZ algorithm, the first five challenges were solved, while the current biggest solved challenge by any researcher is challenge number seven.},
  author       = {Mårtensson, Erik},
  keyword      = {NTRU Challenge,Progressive BKZ,BDD,Enumeration,SVP},
  language     = {eng},
  note         = {Student Paper},
  title        = {Solving NTRU Challenges Using the New Progressive BKZ Library},
  year         = {2016},
}