Obfuscation of Probabilistic Circuits and Applications

on YouTube ↗31m

" summary

Defines and studies indistinguishability obfuscation for randomized programs (PIO/XPIO), shows correctness needs joint-output indistinguishability across multiple queries and that security requires a distinguishing gap negligible relative to the number of inputs. Construction derandomizes programs with a puncturable PRF and obfuscates them, proving sub-exponential iO ⇒ XPIO via an exponential-hybrid argument. Application: transforms a re-randomizable CPA scheme into FHE by obfuscating layered re-encryption circuits, avoids circular security assumption using perfectly lossy public keys to prevent ciphertext blowup.

AI-written summary · about

" chapters (11)

1. 0:00Intro
2. 0:28Program Obfuscation
3. 2:47Motivating Examples
4. 7:19plo Intuition: Correctness
5. 8:56plo Intuition: Security
6. 10:06Dynamically-IND
7. 13:03X-indistinguishability
8. 18:01Variants of plo
9. 19:23plo for single-input prog's
10. 21:25Application of plo
11. 24:16CPA-Security

" related talks

• 01h 12mApplications of Obfuscation ICraig Gentry · Cryptography Boot Camp 2015
• 50mApplications of Obfuscation IICraig Gentry · Cryptography Boot Camp 2015
• 52mIndistinguishability Obfuscation via Mathematical Proofs of EquivalenceZhengzhong Jin · Proof Complexity and Meta-Mathematics 2023
• 01h 08mExpedition to Obfustopia: Indistinguishability Obfuscation from Well-Studied Assumptions to New...Rachel Lin · Obfuscation
• 01h 06mPseudorandom ObfuscationNico Döttling · Obfuscation
• 48mTales of Obfuscation in Bounded Arithmetic, Metacomplexity, and Differential PrivacyRahul Ilango · Minimal Complexity Assumptions for Cryptography 2023
• 59mBeyond P versus NP: Using Complexity Theory in Obfuscation and Vice-VersaAlex Lombardi, Rahul Ilango · Obfuscation
• 01h 04mTutorial on obfuscationRachel Lin · Minimal Complexity Assumptions for Cryptography 2023