Design and Implementation Aspects of Post-Quantum Cryptography

The security of public-key cryptography depends on the computational intractability of some hard problems. The integer factorization and elliptic curve discrete logarithm problems are two such problems which are at the core of our current public-key infrastructure. However, quantum computers can solve these problems \emph{easily}. Therefore, the arrival of practical quantum computers will render such security assurance invalid. Post-quantum cryptography aspires to mitigate this disruptive effect of quantum computers and facilitate a smooth transition to a post-quantum world. This thesis focuses on several aspects of post-quantum cryptography such as practical design, efficient implementation, and side channel security. For a long time, constant-time efficient sampling from discrete Gaussian distributions had been an open problem. We first observed that when using the Knuth-Yao sampling there exists a unique mapping between input random bits and generated samples. We utilize this mapping to express the samples as Boolean functions of input random bits. Constant-time sampling can be achieved by executing these Boolean functions. We also propose a single-instruction-multiple-data based batch sampling method to increase the efficiency of constant-time sampling. Our method achieves approximately 37% speed up compared to the best known previous method in constant-time. We describe our design rationales that lead to the post-quantum key-encapsulation mechanism Saber that has been submitted to NIST's post-quantum standardization procedure. We show that due to our choice of power-of-two fields instead of more conventional prime fields, meticulously chosen parameters, and efficient implementation, Saber is able to provide adequate post-quantum as well as classical security while being efficient in implementation cost compared to other key-encapsulation mechanism schemes. We further show using Cortex-M4 and Cortex-M0 microcontrollers that Saber is suitable for IoT devices and in general for devices with very constrained resources. We describe multiple speed optimization methods such as schoolbook multiplication using DSP instructions, vertical Toom-Cook multiplication and memory optimization methods such as in-memory Karatsuba multiplication, just-in-time public matrix generation etc. Compared to the initial reference implementation our methods can reduce the run time by approximately $6.2-8$ times and the memory footprint by 2.5-3 times. Post-quantum cryptography based on finding an isogeny on supersingular elliptic curves suffers from high computational cost. We are the first to provide a method to speed up the most computationally expensive modular multiplication operation by exploiting the special prime structure used in such cryptography. We show that our methods can reduce the cost of modular multiplication by half compared to the previously known best methods.

Jaar van publicatie:2020

Toegankelijkheid:Open