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:

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.

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.