Christian Knabenhans

encryptedspaces.orgEncrypted Spaces — Research previewAn architecture for collaborative applications where data is encrypted and operations are cryptographically verifiable.

12 June

I joined @msftresearch.bsky.social this week for a summer internship! Very excited to be working with Greg Zaverucha on encryptedspaces.org, an ambitious research agenda for the future of secure collaboration tools. Check out the whitepaper by Greg, @tumbolia.bsky.social, Nora, and Trevor!

github.comlattirustLattice zero-knowledge/succinct arguments, and more - lattirust

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

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.

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!

github.comlattirustLattice zero-knowledge/succinct arguments, and more - lattirust

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 😉

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.

github.comlattirustLattice zero-knowledge/succinct arguments, and more - lattirust

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.

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)

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)

ia.crLova: Lattice-Based Folding Scheme from Unstructured LatticesFolding schemes (Kothapalli et al., CRYPTO 2022) are a conceptually simple, yet powerful cryptographic primitive that can be used as a building block to realise incrementally verifiable computation (I...

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)

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)

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)

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)

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)

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)