Results 781 - 790 of 23787
We consider indistinguishability obfuscation (iO) for multi-output circuits of size s, where s is the number of AND/OR/NOT gates in C. Under the worst-case assumption that NP not in BPP, we establish that there is no efficient indistinguishability obfuscation scheme that outputs circuits of size s+ o(s/log s). In other words, to be secure, an efficient iO scheme must incur an s/log s additive overhead in the size of the obfuscated circuit.
The proof of our main result builds on a connection between obfuscation and meta-complexity, and on the NP-hardness of circuit minimization for multi-output circuits established by Loff, Ilango, and Oliveira [ILO20], together with other techniques from cryptography and complexity theory.
Based on a joint work with Zhenjian Lu, Igor C. Oliveira and Rafael Pass.
A central line of inquiry in the study of indistinguishability obfuscation (IO) is to minimize the size of the obfuscation. Today we know how to obfuscate programs represented as Turing machines, where the size of the obfuscation grows only with the input size and not with the machine's running time. Jain and Jin [FOCS 2022] showed how to remove the dependency on the input size for functionally equivalent programs where equivalence can be proven in Cook's theory PV, assuming IO for circuits and LWE.
In this work we investigate the limits of the pursuit of succinct obfuscation. We consider the task of obfuscating a program with a large description, most of which can be made public while some portion of the description is secret. We put forth a new notion of \emph{fully succinct IO} where the size of obfuscated program only grows with the size of the program's secret part and not with the public part or with the input size.
Starting with input-succinct IO for PV-equivalent machines, we construct fully succinct IO for the same class of programs. We refer to such an obfuscation as fully succinct pv-IO. Next, we show how to bootstrap our fully succinct pv-IO to achieve full IO security. Our bootstrapping theorems are based on succinct cryptographic primitives with seemingly weaker functionality: either succinct witness encryption or SNARGs for NP with unique proofs. We also require that the correctness of these primitives can be proven in theory PV. We show that these assumptions are sufficient and necessary.
We demonstrate several applications of fully succinct IO and pv-IO:
We give the first IO construction where the size of the obfuscated program is less than twice the size of the original program for a large class of useful programs.
We show how to avoid padding the program before obfuscating it -- a step often necessitated by security analysis -- by replacing the padding with a public random string.
Assuming only fully succinct pv-IO and other standard assumptions, we give the first construction of succinct computational secret sharing for access structures represented by polynomial-size monotone circuits where the share size does not grow with the size of the access structure.
Although we have known fully homomorphic encryption (FHE) from circular security assumptions for over a decade, there is still a significant gap in understanding related homomorphic primitives supporting all unrestricted polynomial-size computations. One prominent example is attribute-based encryption (ABE). Previous constructions either only support bounded-depth circuits or require the heavy machinery of indistinguishability obfuscation. In this work, we introduce new lattice-based techniques to overcome this limitation. In this talk, I will introduce the background, explain our new constructions, and discuss interesting open questions. Joint work with Yao-Ching Hsieh and Huijia (Rachel) Lin.
Indistinguishability obfuscation (iO) has emerged as a central object in cryptography, enabling a wide range of applications from functional encryption to advanced proof systems. Moreover, recent breakthrough work has demonstrated that iO can be realized from well-founded assumptions. A thorn to all this remarkable progress is a limitation of all known constructions of general-purpose iO: the security reduction incurs a loss that is exponential in the input length of the function. This "input-length barrier'' to iO stems from the non-falsifiability of the iO definition and is discussed in folklore as being possibly inherent. It has many negative consequences; notably, constructing iO for programs with inputs of unbounded length remains elusive due to this barrier.
We present a new framework aimed towards overcoming the input-length barrier. Our approach relies on short mathematical proofs of functional equivalence of circuits (and Turing machines) to avoid the brute-force "input-by-input'' check employed in prior works. We show how to obfuscate Turing machines with unbounded length inputs, whose functional equivalence can be proven in Cook's Theory PV.
To realize our approach, we depart from prior work and develop a new gate-by-gate obfuscation template that preserves the topology of the input circuit. Our techniques are found useful in other settings, such as recent progress in SNARGs.
Based on the joint work with Abhishek Jain in FOCS'22.
In this talk, I'll discuss new techniques for constructing cryptographic objects using indistinguishability obfuscation (iO). As a taste, our techniques enable us to construct
- public-key encryption with optimal hardness guarantees, and
- one-way functions with optimal direct product hardness (i.e., simultaneously solving independent instances scales according to the naive bound).
A key theme in our work is to combine iO with complexity-theoretic assumptions that go beyond P \neq NP. For instance, some of our results assume the co-non-deterministic hardness of SAT.
We also prove results of interest to complexity theory. For example, we use obfuscation to give a reduction from non-deterministically solving UNSAT to a solving a direct product version of Search-SAT.
This is joint work with Alex Lombardi.