Hardware Implementation of a Post-Quantum Key Exchange

Recent progresses in research and development of quantum computers may pose a threat to modern cryptography. When powerful enough quantum computers will be available, quantum algorithms will be able to easily break public-key cryptosystems that are used today in many different applications, like secure browsing. Fortunately, using some particular algebraic structures like lattices it is possible to build cryptosystems that are supposed to be quantum-resistant. In the last few decades several proposals of post-quantum key exchange protocols have appeared in literature, still they need some improvements in speed and data transfer for practical applications. Some of the performance bottlenecks of pure software implementations could be mitigated if custom hardware blocks are designed to accelerate part of the algorithms. In this work, the Saber key encapsulation method has been used as a basis for speed evaluation and optimization. Among all the functional blocks composing the protocol, the polynomial multiplication has been selected as the optimization target because it is well-suited to adoption of better and more parallel designs. Firstly, software solutions have been explored to improve multiplication. In particular, the Toom-Cook algorithm used in the provided software implementation has been extended to perform efficient sub-multiplications with the Karatsuba algorithm. Then, a hardware accelerator has been designed to allow further speedup of the operation. Highly parallel designs based on the school-book method and the Karatsuba algorithm have been experimented with different combinations of complexity. The electronic board used for implementation of the accelerator is the Avnet ZedBoard, powered by a Xilinx SoC which includes a programmable logic together with the CPU. Finally, the developed hardware block has been put in communication with the processing unit through the AXI standard interface. Tests and evaluations have been conducted on the complete system in the final phase of this work.