Exploring Super Singular Isogeny Graphs and Cryptographic Protocols

Episode 129

I spoke with Kristin Lauter about:

* Elliptic curve cryptography and homomorphic encryption

* Standardizing cryptographic protocols

* Machine Learning on encrypted data

* Attacking post-quantum cryptography with AI

Enjoy—and let me know what you think!

Kristin is Senior Director of FAIR Labs North America (2022—present), based in Seattle. Her current research areas are AI4Crypto and Private AI. She joined FAIR (Facebook AI Research) in 2021, after 22 years at Microsoft Research (MSR). At MSR she was Partner Research Manager on the senior leadership team of MSR Redmond. Before joining Microsoft in 1999, she was Hildebrandt Assistant Professor of Mathematics at the University of Michigan (1996-1999). She is an Affiliate Professor of Mathematics at the University of Washington (2008—present). She received all her advanced degrees from the University of Chicago, BA (1990), MS (1991), PhD (1996) in Mathematics. She is best known for her work on Elliptic Curve Cryptography, Supersingular Isogeny Graphs in Cryptography, Homomorphic Encryption (SEALcrypto.org), Private AI, and AI4Crypto. She served as President of the Association for Women in Mathematics from 2015-2017 and on the Council of the American Mathematical Society from 2014-2017.

Find me on Twitter for updates on new episodes, and reach me at editor@thegradient.pub for feedback, ideas, guest suggestions.

I spend a lot of time on this podcast—if you like my work, you can support me on Patreon :) You can also support upkeep for the full Gradient team/project through a paid subscription on Substack!

Subscribe to The Gradient Podcast: Apple Podcasts  | Spotify | Pocket Casts | RSSFollow The Gradient on Twitter

Outline:

* (00:00) Intro

* (01:10) Llama 3 and encrypted data — where do we want to be?

* (04:20) Tradeoffs: individual privacy vs. aggregated value in e.g. social media forums

* (07:48) Kristin’s shift in views on privacy

* (09:40) Earlier work on elliptic curve cryptography — applications and theory

* (10:50) Inspirations from algebra, number theory, and algebraic geometry

* (15:40) On algebra vs. analysis and on clear thinking

* (18:38) Elliptic curve cryptography and security, algorithms and concrete running time

* (21:31) Cryptographic protocols and setting standards

* (26:36) Supersingular isogeny graphs (and higher-dimensional supersingular isogeny graphs)

* (32:26) Hard problems for cryptography and finding new problems

* (36:42) Guaranteeing security for cryptographic protocols and mathematical foundations

* (40:15) Private AI: Crypto-Nets / running neural nets on homomorphically encrypted data

* (42:10) Polynomial approximations, activation functions, and expressivity

* (44:32) Scaling up, Llama 2 inference on encrypted data

* (46:10) Transitioning between MSR and FAIR, industry research

* (52:45) An efficient algorithm for integer lattice reduction (AI4Crypto)

* (56:23) Local minima, convergence and limit guarantees, scaling

* (58:27) SALSA: Attacking Lattice Cryptography with Transformers

* (58:38) Learning With Errors (LWE) vs. standard ML assumptions

* (1:02:25) Powers of small primes and faster learning

* (1:04:35) LWE and linear regression on a torus

* (1:07:30) Secret recovery algorithms and transformer accuracy

* (1:09:10) Interpretability / encoding information about secrets

* (1:09:45) Future work / scaling up

* (1:12:08) Reflections on working as a mathematician among technologists

Links:

* Kristin’s Meta, Wikipedia, Google Scholar, and Twitter pages

* Papers and sources mentioned/referenced:

* The Advantages of Elliptic Curve Cryptography for Wireless Security (2004)

* Cryptographic Hash Functions from Expander Graphs (2007, introducing Supersingular Isogeny Graphs)

* Families of Ramanujan Graphs and Quaternion Algebras (2008 — the higher-dimensional analogues of Supersingular Isogeny Graphs)

* Cryptographic Cloud Storage (2010)

* Can homomorphic encryption be practical? (2011)

* ML Confidential: Machine Learning on Encrypted Data (2012)

* CryptoNets: Applying neural networks to encrypted data with high throughput and accuracy (2016)

* A community effort to protect genomic data sharing, collaboration and outsourcing (2017)

* The Homomorphic Encryption Standard (2022)

* Private AI: Machine Learning on Encrypted Data (2022)

* SALSA: Attacking Lattice Cryptography with Transformers (2022)

* SalsaPicante: A Machine Learning Attack on LWE with Binary Secrets

* SALSA VERDE: a machine learning attack on LWE with sparse small secrets

* Salsa Fresca: Angular Embeddings and Pre-Training for ML Attacks on Learning With Errors

* The cool and the cruel: separating hard parts of LWE secrets

* An efficient algorithm for integer lattice reduction (2023)