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**_{1}, **A**_{2} be square matrices and **t** a row vector such that

**t****A**_{1} = *x*_{1}**t**, **t****A**_{2} = *x*_{2}**t**

Using high-school algebra lingo, we would refer to **t** as the eigenvector of **A**_{1}, **A**_{2}. It is easy to see that

**t** ⋅ (**A**_{1} + **A**_{2}) = (*x*_{1} + *x*_{2})**t**, *t* ⋅ **A**_{1}**A**_{2} = *x*_{1}*x*_{2}**t**

This extends readily to any polynomial *p*(*x*_{1}, …, *x*_{n}), namely: if **t****A**_{i} = *x*_{i}**t**, then

**t** ⋅ *f*(**A**_{1}, …, **A**_{n}) = *f*(*x*_{1}, …, *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:

- arbitrary matrices
**A**_{1}, …,**A**_{n}that may not share the same eigenvector**t**, and - a relaxation to “approximate” equality, namely
**t****A**_{i}≈*x*_{i}**t**.

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

## Bingo!

Here’s the 4×4 bingo puzzle:

GGH15 | Bonsai | AR + G |
noise growth |

G^{ − 1} |
LWE | Vinod | LHL |

Gaussian | A_{f} |
FHE Dec ≈ linear | noise flooding |

homomorphic | trapdoor | smoothing parameter | H_{f, x} |