YoVDO

Mutual Empowerment Between Circuit Obfuscation and Circuit Minimization

Offered By: Simons Institute via YouTube

Tags

Indistinguishability Obfuscation Courses Cryptography Courses Algorithm Design Courses Theoretical Computer Science Courses

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

Natural Language Processing
Columbia University via Coursera
Intro to Algorithms
Udacity
Conception et mise en œuvre d'algorithmes.
École Polytechnique via Coursera
Paradigms of Computer Programming
Université catholique de Louvain via edX
Data Structures and Algorithm Design Part I | 数据结构与算法设计(上)
Tsinghua University via edX