How to Construct Indistinguishability Obfuscation from Compact Functional Encryption
summary
Claims IO for P/poly from compact FE assuming a sub-exponentially secure public-key compact functional-encryption scheme (selective security, one key). Construction builds secret-key multi-input FE by iterating a single-input compact FE instance into an iterated MIFE construction that encrypts positions and uses function-privacy to hide PRF keys and messages. Security proof uses hybrid steps over input combinations, needing about 2^n hybrids / sub-exponential security; result is conceptual, not yet a standalone candidate because compact FE currently relies on IO.
AI-written summary · about
chapters (22)
- 0:00Intro
- 0:21Cryptoland, pre 2013
- 0:43Crypto from io
- 1:18Building io
- 5:21Compact Functional Encryption
- 5:55Our Results
- 7:01Literature: Single-key FE
- 7:57Open Problem
- 8:25Main Result, restated
- 8:58Multi-Input Functional Encryption
- 12:04Coming up
- 12:15Our Approach
- 13:12Notation
- 16:19Construction of MIFE.
- 17:19Function Privacy
- 21:21The Cost of Iteration
- 22:02Security of MIFE
- 23:21Proof Strategy: First Attempt
- 25:04Problem: Cross Computations
- 25:27Main Idea
- 25:59Threshold index Technique
- 28:51Number of hybrids?
related talks
01h 12mApplications of Obfuscation I
50mApplications of Obfuscation II
23mBootstrapping Homomorphic Encryption via Functional Encryption
58mObfuscation 2
53mLPN Based IO Part 2
36mDiamond iO: Lattice-Based Obfuscation without Bootstrapping from Functional Encryption, toward...
01h 05mObfuscation from Noisy Linear FE
44mObfuscation III