Abstract
Postquantum cryptography is the field of study and development of cryptographic primitives providing security in the presence of adversaries capable of running largescale errortolerant 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 realworld usage.
In this thesis, we investigate three topics in practical postquantum cryptography. First, we research quantum circuit depthwidth tradeoffs in the case of Grover’s algorithm and how these impact the cost of running keysearch 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 speedups are a component of many quantum attacks, making the study of these tradeoffs of independent interest.
Second, we study the "primal attack" on latticebased cryptosystems. This consists of using lattice reduction to recover an unusually short vector in a qary lattice, which results in a break of LWE and NTRUbased 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 DachmanSoled 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 latticebased 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 postquantum encryption with reasonable performances.
In this thesis, we investigate three topics in practical postquantum cryptography. First, we research quantum circuit depthwidth tradeoffs in the case of Grover’s algorithm and how these impact the cost of running keysearch 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 speedups are a component of many quantum attacks, making the study of these tradeoffs of independent interest.
Second, we study the "primal attack" on latticebased cryptosystems. This consists of using lattice reduction to recover an unusually short vector in a qary lattice, which results in a break of LWE and NTRUbased 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 DachmanSoled 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 latticebased 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 postquantum encryption with reasonable performances.
Original language  English 

Qualification  Ph.D. 
Awarding Institution 

Supervisors/Advisors 

Award date  1 Jun 2021 
Publication status  Unpublished  2021 
Keywords
 Postquantum cryptography
 Latticebased cryptography
 Cryptanalysis
 Lattice reduction