< Back to previous page


Implementation Aspects of Lattice-based Cryptography

Book - Dissertation

In a modern world where our lives are all digital and connected, cryptography has become the fundamental pillar to guarantee our security. Over the coming decades, the impact of digital technologies in everyday life is going to increase even further. Cryptography protects the privacy and integrity of our data and communications in a hostile environment. The security of the cryptographic schemes depends on the computational intractability of certain underlying hard problems. Another technology that may become feasible in the coming years is quantum computation. The mathematical problems that are used to build our currently deployed key exchange protocols and digital signature algorithms can be solved efficiently by quantum computers, and thus break the cryptosystems, which poses an important threat for long term security. Fortunately, there exist cryptographic schemes that rely upon problems that cannot be solved efficiently even by quantum computers, namely post-quantum cryptography. Lattice-based cryptography is one type of post-quantum cryptography. The development of lattice-based schemes is less mature than other type of algorithms but more promising in terms of efficiency and flexibility. In this thesis, we study the implementation aspects of lattice-based cryptography. Operations in lattice-based schemes are typically performed in polynomial rings. Hence, the core operation is the polynomial multiplication. We study the efficiency of different polynomial multiplication algorithms. We propose algorithmic optimizations to improve performance. We use our polynomial multiplication algorithm to accelerate software implementations of Saber, a post-quantum key encapsulation mechanism. Additionally, we explore memory efficiency which is an often underestimated but important metric for embedded applications. Lastly, hardware implementation aspects are also considered. First, we propose a hardware architecture for a compact yet flexible polynomial multiplier. Then, we implement Saber on hardware utilizing this multiplier to accelerate the execution. We design a dedicated processor to accelerate Saber which requires 38% less power than state-of-the art post-quantum cores, utilizing x4 less memory, consuming 37% less energy in the multiplier and achieving the lowest reported area despite fabrication process disadvantages with respect to state-of-the-art processors.
Publication year:2022