# CSE206A Project guidelines

The guidelines below are provided to help you getting started with the project. There is much flexibity about the scope of the project, and the following guidelines are provided primarily to help you getting started. If you are unsure about what to do, below is also a default project which offers more guidance, but still leaves some room for creativity. If you want to do something else, just talk to the instructor and propose your idea. The main requirements are the following:

• You can work on the project individually or in pairs. Working in pairs is encouraged, but if you want to work in a bigger group you need to explain why and get instructor approval.
• You should produce a written report describing your work.

Here are some links to lattice-based constructions of various advanced cryptographic primitives like Identity Based Encryption, Fully Homomoprhic Encryption and Functional Encryption.

In order to get started, proceed as follows:

1. Select one or more papers in lattice cryptography, possibly following the links above.
2. Read the papers, and try to do something original. This could be a critical comparison between different approaches to solve the same problem, or implement a construction described in a paper.

## Default project: efficient public key encryption

The goal of this project is to explore design choices and related efficiency issues in the construction of lattice-based public key encryption. The starting point in the cryptosystem described in class, or its close variant described in the paper Better Key Sizes (and Attacks) for LWE-Based Encryption (Lindner & Peikert, CT-RSA 2011).

Design space: The cryptosystem as described above leaves many open choices to the designer. One of them is how to pack many input bits in a single ciphertext, and at the same time avoid decryption errors. Recall that using the secret key, one can compute a noisy encoding of the message (q/2) m + e, where m is the message vector, and e is an error vector.

• You can encrypt longer messages by increasing the number of coordinates in m or by modifying the encoding to (q/t) m for t>2 and let m be a vector with entries in {0,..,t-1}
• For correctness of decryption, one needs the entries of e to be smaller than q/(2t), and you can prove precise probabilitic bounds on this event using the fourier analsysis methods studied in class.
• Another possible tradeoff between message length and probability of error is offered by using error correcting code: instead of insiting that every coordinate of e is small enough to avoid decryption errors, you can set the parameters in such a way that most coordinates are small, so you will recover m with a small number of errors. You can then use a diginal error correcting code to encode m is a redundant way so that you can recover from this small number of errors.

We didn't study error correcting codes in this course, but you may know about them from other classes, or you can research the topic on your own. Again, this is a course project, and it is rather open ended. As long as you learn something in the process of working on it, you are on the right track!

In the last weeks of the course we will study the use of algebraic lattices to substantially improve the efficiency of lattice cryptography (including the cryptosystem above). The use of algebraic lattices is largely orthogonal to the issues studied in this project. You may choose to incorporate algebraic lattices in it if you like, or stick to general lattices. Also, depending on your inclication, the project may range from a pure theoretical project with only pencil and paper calculation of the bounds, to something more experimental involving some implementation and experimentation with your lattice encryption scheme.