Post-Quantum Cryptography: Cryptanalysis and Implementation

Post-quantum cryptography is the field of study and development of cryptographic primitives providing security in the presence of adversaries capable of running large-scale error-tolerant quantum computations. Works in this area span from theoretical analysis of security definitions and protocols, to the research of classical and quantum cryptanalytic algorithms, to the development of cryptographic schemes that can be deployed for real-world usage.

In this thesis, we investigate three topics in practical post-quantum cryptography. First, we research quantum circuit depth-width trade-offs in the case of Grover’s algorithm and how these impact the cost of running key-search attacks against block ciphers. Such attacks have been proposed by the US National Institute of Standards and Technology as benchmarks to define quantum security, and hence their cost should be well understood. Furthermore, Grover speed-ups are a component of many quantum attacks, making the study of these trade-offs of independent interest.

Second, we study the "primal attack" on lattice-based cryptosystems. This consists of using lattice reduction to recover an unusually short vector in a q-ary lattice, which results in a break of LWE- and NTRU-based schemes. We compare two alternative heuristics used to estimate the expected cost of this attack due to Gama et al. (Eurocrypt 2008) and Alkim et al. (USENIX 2016) and provide experimental evidence of the validity of the latter. Then, using the techniques introduced in Dachman-Soled et al. (Crypto 2020), we continue this line of work to provide estimates on the full probability distribution of the cost of the attack, providing further experimental validation.

In the last chapter, we move our focus from cryptanalysis to implementation. We implement a lattice-based actively secure key encapsulation mechanism on a currently commercially available smart card from the SLE 78 family by Infineon. We do this by repurposing classic arithmetic techniques that enable us to take advantage of the card’s RSA coprocessor to compute polynomial multiplications in Z_q [x]/(x^256 +1). The resulting scheme, a variant of Kyber768, runs key generation in 79.6 ms, encapsulation in 102.4 ms, and decapsulation in 132.7 ms. Our techniques can be adapted to other RSA/ECC coprocessors and demonstrate the feasibility of repurposing already deployed cryptographic coprocessors to run post-quantum encryption with reasonable performances.