Variants of LWE : reductions, attacks and a construction

In this thesis, we cover various topics in lattice-based cryptography. This means that the scope of this thesis is wider than it is deep, with contributions in the areas of cryptanalysis, hardness assumptions and cryptographic constructions. For the cryptanalytic contribution, we present techniques that allow an attacker to recover a secret key when given a leakage profile practically achievable by means of a cold boot attack. In particular, we focus on the case where a number theoretic transform (NTT) is used for key storage. This is a common choice made in efficient implementations of lattice-based cryptography. In addition to describing the attack in detail, we run experiments attesting to the practicality and efficiency of our methods using realistic parameters. Our techniques rely heavily on the divide and conquer structure of the NTT and lattice basis reduction. The second main contribution considers reductions between variants of the standard learning with errors (LWE) problem. The variants of interest are Ring-LWE (RLWE) and Module-LWE (MLWE). The content presented in this thesis improves on our original paper published at Asiacrypt 2017 by way of an improved analysis of the reduction. In particular, a main result in our original paper states that for power-oftwo cyclotomic rings of dimension n, there is a reduction from the MLWE problem in module rank d, modulus q and error rate α to the RLWE problem in modulus q^d and error rate α' = n²√d·α. However, this thesis shows that a smaller error rate of α' = n¹/²+c√d·α is possible for any constant c > 0. In addition, the original RLWE to RLWE dimensions that halve the ring dimension while squaring the modulus are improved upon by way of shrinking the growth factor in error rate. Our final contribution is to construct a verifiable oblivious pseudorandom function (VOPRF) protocol whose security is based on lattice assumptions. To our knowledge, this is the first construction of a post-quantum secure VOPRF. A VOPRF allows a client to obtain a pseudorandom function evaluation on a point of its choice using a server's secret key. Importantly, the server does not learn anything about the client's input and the client does not learn anything about the server's key. Our protocol manages to achieve security against adversaries that may deviate arbitrarily from the protocol and consists of a single round of interaction. Our protocol should be interpreted as showing the feasibility of round-optimal VOPRFs from lattice assumptions rather than being a practical construction.