Workshop “Lattices: New Cryptographic Capabilities”

On the behalf of the organizers, I am excited to announce that the next Simons workshop Lattices: New Cryptographic Capabilities will take place next week Mar 23-27, 2020 over Zoom!

The workshop will cover advanced lattice-based cryptographic constructions, while also highlighting some of the recurring themes and techniques, reiterated through a game of Bingo! The rest of this post provides a sneak preview along with the Bingo puzzle.

Looking forward to seeing everyone at the workshop!

Hoeteck, together with Shweta, Zvika and Vinod

Zoom Guidelines/Tips

  • To ask a question, use the “raise hand” feature.
  • If the speaker’s slide is not displaying in its entirety, try “side-by-side mode” under “view options”.
  • Please log in to Zoom with your full name.

A Sneak Preview

Let A1, A2 be square matrices and t a row vector such that

tA1 = x1t, tA2 = x2t
Using high-school algebra lingo, we would refer to t as the eigenvector of A1, A2. It is easy to see that

t ⋅ (A1 + A2) = (x1 + x2)t, t ⋅ A1A2 = x1x2t
This extends readily to any polynomial p(x1, …, xn), namely: if tAi = xit, then

t ⋅ f(A1, …, An) = f(x1, …, xn)t
As in turns out, much of advanced lattice-based crypto boils down to a generalization of this statement! The generalization is along two orthogonal dimensions:

  1. arbitrary matrices A1, …, An that may not share the same eigenvector t, and
  2. a relaxation to “approximate” equality, namely tAi ≈ xit.

The generalization underlies fully homomorphic encryption, homomorphic signatures, attribute-based encryption schemes and many more!


Here’s the 4×4 bingo puzzle:

GGH15 Bonsai AR+G noise growth
G − 1 LWE Vinod LHL
Gaussian Af FHE Dec linear noise flooding
homomorphic trapdoor smoothing parameter Hf, x

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.