Practical lattice-based cryptography over structured lattices
type: CreativeWork
description: Alongside the growth of technology is the increasing demand for security of data and communication channels. As attacking power grows, devices become smaller and data expands, the security needs to be stronger yet less resource-consuming than ever before. Public key cryptography (PKC) is used in the majority of today's communications systems. The security of public-key cryptographic schemes, such as RSA and elliptic curve cryptography (ECC), is based on underlying mathematical problems such as factoring large integers or solving the discrete log problem. However, the discovery of Shor's Algorithm in 1994 insinuates that these schemes will be insecure when a full-scale quantum computer is developed, as these problems will be solvable in polynomial time. Therefore attention has moved towards post-quantum, or quantum-safe, cryptography (QSC). In 2016, the National Institute of Standards and Technology (NIST) announced the beginning of their efforts to migrate to QSC, a standardisation process which has involved the cryptographic community worldwide. There are five main types of QSC being considered for standardisation; lattice-based, code-based, multivariate-based, hash-based and isogeny-based. Lattice-based cryptography (LBC) offers a promising alternative to today's classical approaches. Hard problems based on lattices are believed to be unsolvable, even by a quantum-computer, in a feasible amount of time. In 1995, Ajtai showed that the average case complexity of these problems is at least as hard as solving the problems in the worst case. Furthermore, lattice-based schemes are the only remaining contender in the NIST process to provide the important primitives of encryption, key encapsulation and digital signature schemes (DSSs). A well-recognised open problem surrounding quantum-safe cryptography is its increase in bandwidth and computational complexity in comparison to existing cryptography. However, in comparison to other quantum-safe schemes, LBC has been shown …
abstract: Alongside the growth of technology is the increasing demand for security of data and communication channels. As attacking power grows, devices become smaller and data expands, the security needs to be stronger yet less resource-consuming than ever before. Public key cryptography (PKC) is used in the majority of today's communications systems. The security of public-key cryptographic schemes, such as RSA and elliptic curve cryptography (ECC), is based on underlying mathematical problems such as factoring large integers or solving the discrete log problem. However, the discovery of Shor's Algorithm in 1994 insinuates that these schemes will be insecure when a full-scale quantum computer is developed, as these problems will be solvable in polynomial time. Therefore attention has moved towards post-quantum, or quantum-safe, cryptography (QSC). In 2016, the National Institute of Standards and Technology (NIST) announced the beginning of their efforts to migrate to QSC, a standardisation process which has involved the cryptographic community worldwide. There are five main types of QSC being considered for standardisation; lattice-based, code-based, multivariate-based, hash-based and isogeny-based. Lattice-based cryptography (LBC) offers a promising alternative to today's classical approaches. Hard problems based on lattices are believed to be unsolvable, even by a quantum-computer, in a feasible amount of time. In 1995, Ajtai showed that the average case complexity of these problems is at least as hard as solving the problems in the worst case. Furthermore, lattice-based schemes are the only remaining contender in the NIST process to provide the important primitives of encryption, key encapsulation and digital signature schemes (DSSs). A well-recognised open problem surrounding quantum-safe cryptography is its increase in bandwidth and computational complexity in comparison to existing cryptography. However, in comparison to other quantum-safe schemes, LBC has been shown …
author: McCarthy, Sarah
language: eng
keywords: cryptography, post-quantum, lattices, implementation, cyber-security, identity-based encryption
date published: 2020-7
date modified: 2026-07-24T03:55:25Z
provider: Queen's University Belfast
publisher: Networked Digital Library of Theses and Dissertations
type: WebPage
source organization: Queen's University Belfast