The rise of quantum computing poses a significant threat to digital security, as encryption algorithms currently used in public-key cryptography (e.g., RSA and ECC) are vulnerable to quantum attacks. The ability of quantum computers to drastically reduce the time needed to factor large integers undermines the security of encrypted messages; hence, there is an urgency to transition to a new set of quantum-resistant encryption mechanisms. The National Institute of Standards and Technology (NIST) has begun the standardization process for post-quantum cryptography, which has identified lattice-based cryptography as a viable foundation for new algorithms. The resulting standardized lattice-based algorithms include Kyber and Dilithium, which present significant opportunities but also engineering challenges for organizations and users of legacy encryption mechanisms. Lattice-based cryptography is a type of post-quantum cryptography that is based upon mathematical problems related to multidimensional lattices. A lattice is a set of points in n-dimensional space that are arranged in a grid-like structure. Commonly used lattice-based cryptography problems are Learning with Errors and Shortest Vector problems. The security of such encryption mechanisms derives from the mathematical hardness of finding the shortest vector in a high-dimensional lattice or distinguishing between specially crafted error distributions. The advantage of utilizing lattice-based cryptography mechanisms is that these problems are not susceptible to known forms of quantum or classical attack methods, unlike integer factorization, which can be easily performed by quantum computers using Shor’s algorithm. While lattice-based cryptography provides a robust foundation for post-quantum cryptography, it does pose some significant implementation headwinds and overheads. Source: https://utimaco.com/service/knowledge-base/post-quantum-cryptography/what-lattice-based-cry ptography Lattice algorithms commonly utilize polynomial-based mathematical operations, which have significant memory overheads. Algorithms such as Kyber utilize Learning with Errors to perform encryption, which requires a series of operations on polynomials of considerable degree (e.g.,
256) with operands represented as large numbers. Compared to legacy elliptic curve
cryptography (ECC) mechanisms, which have public keys of only a few hundred bytes, a lattice algorithm’s public key will be significantly larger, requiring more memory and bandwidth to process. The computational overheads of lattice algorithms would also drastically impact performance, specifically CPU utilization, of common processes that require encryption such as Transport Layer Security (TLS) handshakes and Internet Protocol Security (IPsec) Internet Key Exchange (IKE). The increased packet size of lattice encryption methods (sometimes multiple kilobytes) can cause significant performance degradation and packet fragmentation at the common 1500-byte Maximum Transmission Unit (MTU) size that is commonly used in networking equipment. The performance impacts of lattice-based cryptography can be severe in some embedded systems, especially Internet of Things (IoT) devices or automobiles where the cryptographic functions run on a general-purpose processor. Polynomial operations with large numbers are typically implemented with specialized cryptographic instruction sets or mathematical co-processors. Unless the operating environment has such processors, there may be unacceptable computational overheads incurred when implementing such lattice algorithms. Compared to elliptic curve algorithms, which have very efficient mathematical operations built directly into the processor instruction sets, lattice algorithms have to rely on Number Theoretic Transform (NTT) algorithms to perform polynomial multiplication. The CPU utilization of lattice algorithms would impact how many TLS/IPsec connections can be terminated on a server. Additionally, most such algorithms have to be implemented in a constant-time fashion to prevent side-channel attacks by analyzing the power consumption of the system during lattice operations. Such implementations may lead to significant increases in memory utilization as well. Standardizing lattice-based cryptography as a method for post-quantum cryptography requires organizations to make significant changes to their IT infrastructures. Systems that currently rely on cryptography are designed around the performance characteristics of legacy algorithms and may have significant overheads when transitioning to new algorithms. Specifically, utilizing larger public key sizes may impact the memory or buffer sizes of various functions within the software or hardware devices. Hence, organizations may seek to implement hybrid solutions using both classical and lattice cryptography algorithms. Such solutions add complexity to the implementation and operation of the systems but are required, as purely classical algorithms are vulnerable to future quantum computer attacks. The use of hybrid algorithms means that both cryptographic algorithms will need to be processed, impacting the performance of systems using such connections and increasing latency. Lattice-based cryptography algorithms provide a robust framework for post-quantum security but require significant engineering investment from organizations to implement. While generally safe from attacks by quantum computers due to the nature of the mathematical problems involved, such algorithms require more memory, bandwidth, and computational power than classical algorithms like ECC or RSA. Organizations around the world are currently working on methods of either optimizing the utilization of lattice algorithms or developing hybrid approaches to ensure maximum security for a given processing budget.
Sources
https://csrc.nist.gov/projects/post-quantum-cryptography https://www.paloaltonetworks.com/cyberpedia/pqc-standards