Cryptography via Burnside Groups

on YouTube ↗01h 10m

" summary

Introduces a concrete crypto assumption: learning homomorphism with noise (LHN) instantiated with Burnside group B_n,3 (exponent 3) into a small B_r (r≈4–5). Elements have a compact normal form of length Θ(n^3) and group multiplication uses a collecting process cubic time in n. Noise is a random-walk “ball” in the Cayley graph. Proves random self-reducibility for randomly chosen homomorphisms (surjective w.h.p.), gives a one-time encryption construction using a large Kali-norm element, and reports limits for public-key extensions.

AI-written summary · about

" chapters (18)

1. 0:00Start
2. 1:07Talk Preview
3. 3:19Burnside Problem (Informal)
4. 4:02Burnside group of exponent m
5. 5:07Burnside Groups (cont'd)
6. 14:45Commutators Identities in B
7. 20:14Example: The Structure of B2
8. 24:04The Collecting Process (3/3)
9. 27:51Burnside Groups: Recap
10. 30:56Learning With Errors (LWE)
11. 36:12Learning Homomorphisms with Noise (LHN)
12. 38:12B-LHN: Instantiating LHN over Burnside Groups
13. 43:35Random Self-Reducibility (RSR) of B-LHN
14. 45:02Understanding Burnside Homomorphisms
15. 55:07Step 1: Domain Reshuffling
16. 56:53Step 2: Completeness for Surjections
17. 57:37Proving Completeness
18. 59:46Proving Transitivity (cont'd)

" related talks

• 54mFine-Grained CryptographyMarshall Ball · Minimal Complexity Assumptions for Cryptography 2023
• 46mRunning Circuits of Unbounded Depth over Encrypted Data, Securely, Using Lattices...Ji Luo · Obfuscation
• 58mObfuscation 2Aayush Jain · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 01h 04mFully Homomorphic Encryption IIShai Halevi · Cryptography Boot Camp 2015
• 23mSmall-Box CryptographyYevgeniy Dodis, Harish Karthikeyan, Daniel Wichs · ITCS 2022
• 38mRecent Advances on Foundations of Program ObfuscationRachel Lin · Lattices: New Cryptographic Capabilities 2020
• 01h 06mObfuscation: Past, Present, and Possible FuturesAmit Sahai · Securing Computation (Simons Institute, June 2015)
• 46mIndistinguishability Obfuscation from Bilinear Maps and LPN VariantsNeekon Vafa · Obfuscation