UC San Diego

Lattice-based cryptography is an extraordinarily popular subfield of cryptography. But since it is also a very young field, practical proposals for lattice-based cryptographic primitives have only recently started to emerge. Turning a cryptographic scheme into an implementation poses a range of questions, the arguably most important one being its concrete security: how do we ensure that any practically conceivable adversary is unable to break the scheme? In this thesis, we address two issues that arise in this context.

Part I is concerned with basing cryptanalytic tools on a sound theoretical foundation. The common approach to analyzing a concrete cryptographic primitive is to analyze the performance of known algorithms to estimate the attack complexity of a hypothetical adversary. This requires a thorough theoretical understanding of the best performing algorithms. Unfortunately, for many subclasses of lattice algorithms there is a gap in our understanding, which leads to problems in the cryptanalytic process. In this part of the thesis we address these issues in two closely related subclasses of such algorithms. We develop new algorithms and analyze existing ones and show that in both cases it is possible to obtain algorithms that are simultaneously well understood in theory and competitive in practice.

In Part II we focus on an integral part of most lattice-based schemes: sampling from a specific distribution over the integers. Implementing such a sampler securely and efficiently can be challenging for distributions commonly used in lattice-based schemes. We introduce new tools and security proofs that reduce the precision requirements for samplers, allowing more efficient implementations in a wide range of settings while maintaining high levels of security. Finally, we propose a new sampling algorithms with a unique set of properties desirable for implementations of cryptographic primitives.