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. / Thesis / Master of Science (MSc) / The advent of quantum computing poses a serious threat to modern cryptography, as most cryptosystems in use today are vulnerable to attacks by quantum algorithms. Recently proposed cryptosystems based on lattices are conjectured to be resistant to attacks by quantum computers. These cryptosystems also have a conditional security guarantee: if the cryptosystem can be broken by an attack, then a reduction exists which uses that attack to solve variants of the shortest vector problem (Regev, STOC 2005; Peikert, ePrint 2008). As these problems have no known efficient solutions, breaking the cryptosystem should be hard. However this guarantee only holds if the cryptosystem is constructed using parameters which satisfy conditions given in the reduction. Current proposals do not do this, and so cannot claim even a conditional security guarantee. We analyze two reductions and select parameters for a cryptosystem which satisfy these conditions. We also investigate the runtime necessary for a reduction to give meaningful security assurances for current cryptosystems.
| Identifer | oai:union.ndltd.org:mcmaster.ca/oai:macsphere.mcmaster.ca:11375/24466 |
| Date | January 2018 |
| Creators | Gates, Fletcher |
| Contributors | Stebila, Douglas, Mathematics and Statistics |
| Source Sets | McMaster University |
| Language | English |
| Detected Language | English |
| Type | Thesis |
Page generated in 0.0021 seconds