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
- 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:
- arbitrary matrices A1, …, An that may not share the same eigenvector t, and
- 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|