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!

• schedule 8.20 am-noon PDT (4.20 – 8 pm, CET)
• zoom berkeley.zoom.us/j/912850168

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 A₁, A₂ be square matrices and t a row vector such that

tA₁ = x₁t, tA₂ = x₂t
Using high-school algebra lingo, we would refer to t as the eigenvector of A₁, A₂. It is easy to see that

t ⋅ (A₁ + A₂) = (x₁ + x₂)t, t ⋅ A₁A₂ = x₁x₂t
This extends readily to any polynomial p(x₁, …, x_n), namely: if tA_i = x_it, then

t ⋅ f(A₁, …, A_n) = f(x₁, …, x_n)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 A₁, …, A_n that may not share the same eigenvector t, and
2. a relaxation to “approximate” equality, namely tA_i ≈ x_it.

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

Bingo!

Here’s the 4×4 bingo puzzle: