Running Circuits of Unbounded Depth over Encrypted Data, Securely, Using Lattices...
summary
Introduces a lattice-only bootstrapping that converts large-noise BGG+ encodings into fresh, moderate-noise encodings so homomorphic evaluation proceeds to unlimited depth, yielding depth-unbounded ABE and depth-unbounded laconic function evaluation and reusable garbling. Technique combines a bootstrapping BGG+ encodings noise‑removal (LWE→LWR rounding plus modulus restoration), matrix‑valued homomorphic evaluation (GSW/BGV-style), and circular ciphertexts (encrypt secret under itself) to produce s·A − remove_noise so format is restored. Result removes depth factors from efficiency but relies on the stronger evasive circular LWE assumption; open problems include falsifiable assumptions and recent attacks on evasive variants. Joint work with Yao‑Ching Hsieh and Huijia (Rachel) Lin.
AI-written summary · about
chapters (12)
- 0:00Introduction
- 2:18Depth-bounded vs unbounded
- 5:11Laconic function evaluation
- 7:01Attribute-based LFE security
- 11:00Attribute-based encryption
- 16:12BGG+ encoding recap
- 21:56Bootstrapping unbounded depth
- 26:19Noise removal function
- 34:48Noise reduction details
- 39:40Unbounded evaluation
- 44:46Summary and open problems
- 45:51Q&A
related talks
01h 07mLattices and Encrypted Computation
57mTutorial: Encrypted Computation from Lattices
01h 03mLockable Obfuscation
01h 29mLattices, Multilinear Maps and Program Obfuscation
01h 04mFully Homomorphic Encryption II
54mGraph-Induced Multilinear Maps from Lattices
01h 07mGarbled Circuits I
54mAttribute-based Encryption for Circuits