LPN Based IO Part 2

on YouTube ↗53m

" summary

Constructs a semi-compact functional encryption for NC0 by combining three concrete tools: an LWE-based secret-key homomorphic scheme with almost-linear decryption (ciphertext = A·S'+2E+X, S' one-time), a bilinear-map partially-hiding FE for degree‑2-in-secret, constant‑degree-in-public polynomials (outputs must be polynomially small modulo a subexponential modulus), and a structured‑seed (degree 2.5) PRG built from LPN over large fields plus an NC0 PRG. Resulting FE has sublinear ciphertexts but only weak security (distinguishing advantage ≈ 1/λ); bootstrapping and amplification are required to obtain IO with subexponential loss.

AI-written summary · about

" chapters (13)

1. 0:00Intro
2. 1:23Difficulty in constructing IO
3. 5:16Template
4. 7:04Homomorphic Encryption
5. 15:00Functional Encryption
6. 23:20Homophilic Encryption
7. 26:25Homomorphism
8. 30:20Implementation
9. 33:20Hiding the noise
10. 35:37Hiding the rows
11. 37:09Pseudorandom noise
12. 41:12PRGs
13. 46:29Weak Security

" related talks

• 58mObfuscation 2Aayush Jain · Cryptography 10 Years Later: Obfuscation, Proof Systems, and Secure Computation Boot Camp 2025
• 46mIndistinguishability Obfuscation from Bilinear Maps and LPN VariantsNeekon Vafa · Obfuscation
• 01h 08mExpedition to Obfustopia: Indistinguishability Obfuscation from Well-Studied Assumptions to New...Rachel Lin · Obfuscation
• 01h 04mTutorial on obfuscationRachel Lin · Minimal Complexity Assumptions for Cryptography 2023
• 31mHow to Construct Indistinguishability Obfuscation from Compact Functional EncryptionAbhishek Jain · Securing Computation (Simons Institute, June 2015)
• 01h 03mLockable ObfuscationVenkata Koppula · Lattices: New Cryptographic Capabilities 2020
• 01h 05mObfuscation from Noisy Linear FEShweta Agrawal · Lattices: New Cryptographic Capabilities 2020
• 01h 07mLattices and Encrypted ComputationVinod Vaikuntanathan · Lattices: Algorithms, Complexity, and Cryptography Boot Camp 2020