Cryptography from Learning with Errors – CLE

One of the most exciting recent developments in cryptography has been the application of the Learning
with Errors (LWE) problem to the construction of a variety of new schemes. Stated simply, the LWE
problem is to solve a system of linear equations whose outputs have been perturbed by small errors.
Over the past several years, researchers have shown that virtually any cryptographic primitive that one
may wish to build, can in fact be built with security based on the presumed hardness of this problem. The
majority of this recent effort, however, focused on building schemes that have very powerful capabilities
but are very impractical when actually instantiated. The main objective of this project is to explore the potential practical implications of the LWE problem and its variants. We plan to focus our attention on the constructions of essential primitives whose
use is prevalent in the real world. Toward the end of the project, we hope to propose and standardize
several public key and symmetric key schemes that have specific advantages over ones that are currently
deployed.
Public Key Cryptography. Digital signatures schemes are arguably the most ubiquitous public-key
primitives in use today. Unfortunately, almost every efficient such scheme is based on number-theoretic
problems, such as factoring or discrete log, and becomes completely insecure in the advent of quantum
computers. The LWE problem, however, is believed to be exponentially-hard even for quantum algo-rithms. There has been some ongoing effort in constructing a practical digital signature scheme based on LWE, and one of the goals of the project CLÉ is to bring this line of work to a conclusion in the form of a concrete, standardized instantiation that will have the required security for the quantum world.
Symmetric Key Cryptography. Symmetric key cryptography deals with constructions of primitives
such as pseudo-random number generators, authentication schemes, and symmetric key encryption
schemes. For efficiency reasons, such primitives are not constructed using the same techniques as their
public key counterparts. In this project, we hope to show that there are certain scenarios in which public
key techniques may be useful.
For example, if one wants to build an authentication scheme where a prover convinces the verifier
of his identity, one can simply use a block cipher such as AES. The problem with this construction is
that the resulting scheme will be very vulnerable to side channel attacks. To prevent such attacks, it is
essential for the prover to change his key after every invocation. Attempts to solve this problem by masking the key in AES
has been a major research area, but the state-of-the art techniques end up slowing down
AES by several orders of magnitude. Very recent authentication schemes based on LWE
(or its variants) are slightly slower than AES, but the added algebraic structure of these constructions
may lend itself much better to masking. Thus it is reasonable to believe that masked schemes using LWE
could be more efficient than those using AES.
We believe that in addition to the problems that we are addressing in this project being important in their
own right, the techniques that will be developed towards their solutions will open up new directions
in cryptographic research. While we will be starting our research by looking at ways that the LWE
problem can be applied, we do not plan to constrain ourselves to this approach. We will consider all
possible approaches, whether they use techniques from symmetric or public key cryptography, to achieve
the task at hand. There is currently very little collaboration between people working on the practical aspects of symmetric and public key cryptography. Our hope is that by building an interdisciplinary group and exploring problems that span between these two areas, more common ground will emerge that will lead to tighter collaborative work in the near future.