LIFE: Lattice-Based Implementation For Encryption

Post quantum cryptography through the implementation of the LWE problem.

Comment

Inspiration

Post quantum cryptography has been defined by trying to construct new algorithms that don't rely on the discrete logarithm problem, which has been shown to be solvable with Shor's algorithm in O(log n) time. We've decided to further our learning by building our own custom implementation of a lattice based cryptography scheme named Lattice-Based Implementation For Encryption.

What it does

LIFE leverages the learning with errors (LWE) problem to implement an asymmetric cryptography algorithm in Rust, which is a distinctly different mathematical problem than the discrete logarithm, and has been demonstrated to be a difficult problem to solve by quantum computers by Oded Regev in 2005.

How we built it

We researched NIST's post quantum standards for cryptography, and settled on attempting to implement a lattice based scheme, as the underlying mathematics is approachable, and the selected winning algorithm (CRYSTALS-kyber) is a lattice based cryptography solution. We spent most of the hackathon researching and validating the underlying mathematics of our approach, and looking for any attack vectors. Once we reached a good high-level implementation, we started prototyping in Python, and wrote our final project in Rust.

Challenges we ran into

The scope of our project was rather ambitious, and we ran into some difficulty researching due to the dense mathematics that provide the foundation for quantum resistant algorithms. We spent quite a bit of time simply researching cryptography schemes to find something that we could reasonably implement in the amount of time we had available for the hackathon. Once we did settle on a lattice based problem, we then had multiple hours of discussion so that everyone had a good understanding of how the scheme worked, and how we were going to implement it. All in all, there was an excessive amount of time spent planning rather than prototyping.

Accomplishments that we're proud of

Throughout the course of the hackathon, our team was able to quickly dive into a very in-depth field involving computation and mathematics, and were able to successfully understand and discuss these problems as a group. Once we settled on a problem, the group conducted high-level discussions about the methodology and exactly how it worked, and questioned every aspect of the problem until we all had a fundamental understanding of the complex mathematics underlying lattice problems.

What we learned

We learned a great deal about the theory behind why lattice problems are some of the most promising mathematical problems for creating quantum resistant encryption. In addition, we also gained expertise in implementing a LWE approach for cryptography, and the necessary requirements to make the mathematical problem difficult enough to be secure.

What's next for LIFE: Lattice-Based Implementation For Encryption

We'd like to start researching and implementing further improvements we can make, such as implementing a quantum resistant key exchange, allowing for multiple keys to be utilized, different ways of generating a unimodular matrix(a square integer matrix having determinant +1 or -1) for our algorithm. In addition to this, we would love to open our project up to any red-team attacks that anyone wishes to attempt to help find vulnerabilities so that we can improve our algorithm further.

Built With

Share this project:

Updates