Back to search

McMaster University

Reduction-Respecting Parameters for Lattice-Based Cryptosystems

Abstract

dc:description.abstract

One attractive feature of lattice-based cryptosystems is the existence of security reductions relating the difficulty of breaking the cryptosystem to the difficulty of solving variants of the shortest vector problem (Regev, STOC 2005; Peikert, ePrint 2008). As there are no known polynomial-time algorithms which solve these lattice problems, this implies the asymptotic security of the cryptosystem. However, current lattice-based cryptosystems using the learning with errors (LWE) problem select parameters for which the reduction to the underlying lattice problem gives no meaningful assurance of concrete security. We analyze the runtime of the algorithm constructed in the reductions and select parameters for a cryptosystem under which the reductions give 128-bit security. While the resulting LWE-based cryptosystem is somewhat cumbersome, requiring a dimension of n = 1460, this is less than 2 times the dimension in the recently proposed Frodo cryptosystem (Bos et al., ACM CCS 2016), and could be implemented without catastrophic damage to communication times. We also investigate the runtime necessary for a reduction to give meaningful security assurances for current cryptosystems.

Degree

thesis:*
Department dc:contributor.department
Mathematics and Statistics
Year dc:date.issued
2018

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Gates, Fletcher
Advisor dc:contributor.advisor
  • Stebila, Douglas

Subjects

dc:subject × 4

Rights

Language dc:language.iso
en

Identifiers

dc:identifier.*

Chain of custody

source
Harvested from
McMaster University
Base URL
macsphere.mcmaster.ca/server/oai/request
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Gates, Fletcher. Reduction-Respecting Parameters for Lattice-Based Cryptosystems. 2018. http://hdl.handle.net/11375/24466