Finally, we're thinking about high-assurance. We're working on a formally verified constant-time implementation of client-side FHE operations (in Jasmin+EasyCrypt), and we're exploring how to best use high-assurance tools (hax/hacspec, Jasmin, Lean) for lattirust. Stay tuned!
At the moment we're relying on existing lattice estimators to set concrete parameters, but Xavier Marchon did a semester project to write a SIS-specific, Rust lattice estimator, which will be directly integrated in lattirust.
What's next? Emile Hreich already explored GPU acceleration in a semester project, based on @ingonyama.com's Icicle, since lattice crypto is basically linear algebra over rings. We have promising results, with more coming up soon.
Lattirust implements LaBRADOR and Lova, and we'll soon have implementations for the Greyhound PCS. I'll also upstream Nethermind's Latticefold implementation (which actually started from a fork of an early version of lattirust). We're working on some new schemes too 😉
Lattirust implements fast (arkworks-compatible!) arithmetic for rings and polynomial rings, various challenge spaces, linear algebra and norms, and interfaces with spongefish for effortless Fiat–Shamir. It also has nice interfaces for relations and interactive reductions.
I'm happy to finally open-source lattirust, a library for lattice-based zero-knowledge/succinct arguments! Lattirust is somewhat like arkworks, but for lattices; and like lattigo, but for arguments.
➔ github.com/lattirust
Read the paper on ePrint ia.cr/2024/1964, my blog post at cknabs.github.io/post/lova, or watch Tu’s presentation at Asiacrypt!
I’ll also make the code open-source soon™, along with a lot more lattice implementations. Stay tuned! (8/8)
Finally, an open problem:
Lova is very algebraic but uses plain SIS, Latticefold uses MSIS but relies on sumcheck, which is a powerful tool (too powerful?). Can we get a scheme that uses MSIS and barely does more than a single random linear combination? (7/8)
Lova vs Latticefold
In a concurrent work, @danboneh
and @charles_chen533
build a lattice folding scheme from MSIS. It's not implemented yet, but we can expect Latticefold to be more concretely efficient. We’ll have to see how they compare on recursion-friendliness. (6/8)
However, since Lova uses the unstructured SIS assumption, and because we’re constrained to a small challenge set, we need to amplify soundness quite a bit, leading to large-ish proofs (dozens of MB) and proving times >10 minutes. (5/8)
Is Lova concretely efficient?
Lova has some nice features: it is very algebraic (great for prover parallelism!) and only requires a single challenge matrix, which makes it recursion-friendly. We also use the modulus q=2^64 and get rid of modular reduction. (4/8)
One thing I’m proud of in this paper is the notation: while lattice crypto papers are typically heavy notationally, we use matrix notation throughout which leads to a very concise (and imho elegant) notation. Here’s the entire protocol for our core folding step! (3/8)
Lattice folding schemes face two issues: witness norm growth (completeness), and norm growth when extracting (non-relaxed knowledge soundness). We use a split-and-fold technique to get around #1, and we use witness cross-terms (which we also fold) for #2. (2/8)
Lova 💕 (aka lattice Nova): Duc Tu Pham, @giacomofenzi.bsky.social, Ngoc Khanh Nguyen
and I built a folding scheme from (unstructured) lattice assumptions, which will be presented at Asiacrypt this week! (1/8)
