Mutual Empowerment Between Circuit Obfuscation and Circuit Minimization
Offered By: Simons Institute via YouTube
Course Description
Overview
Explore the intricate connections between Indistinguishability Obfuscation (IO) and the Minimum Circuit Size Problem (MCSP) in this 37-minute lecture by Ilya Volkovich from Boston College. Delve into the mutual empowerment of circuit obfuscation and circuit minimization, examining how algorithms for one can enhance the other. Discover key findings, including fixed-polynomial lower bounds against NP and MA, super-polynomial lower bounds against NEXP, and implications for ZPEXP and BPP. Learn about the construction of an optimal universal distinguisher and its applications in cryptography. Gain insights into the equivalence of statistical and computational security for IO when MCSP is in BPP, and understand the significance of these results in the field of minimal complexity assumptions for cryptography.
Syllabus
Mutual Empowerment Between Circuit Obfuscation and Circuit Minimization
Taught by
Simons Institute
Related Courses
Automata TheoryStanford University via edX Intro to Theoretical Computer Science
Udacity Computing: Art, Magic, Science
ETH Zurich via edX 理论计算机科学基础 | Introduction to Theoretical Computer Science
Peking University via edX Quantitative Formal Modeling and Worst-Case Performance Analysis
EIT Digital via Coursera