Results 571 - 580 of 24339
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.
Abstract not available.
Succinct randomized encodings allow encoding the input $x$ of a time-$t$ uniform computation $M(x)$ in sub-linear time $o(t)$. The resulting encoding $\Tilde{x}$ allows recovering the result of the computation $M(x)$, but hides any other information about $x$. These encodings have powerful applications, including time-lock puzzles, reducing communication in MPC, and bootstrapping advanced encryption schemes.
Until not long ago, the only known constructions were based on indistinguishability obfuscation, and in particular were not based on standard post-quantum assumptions. In terms of efficiency, these constructions' encoding time is $\rm{polylog}(t)$, essentially the best one can hope for. Recently, a new construction was presented based on Circular Learning with Errors, an assumption similar to the one used in fully-homomorphic encryption schemes, and which is widely considered to be post-quantum resistant. However, the encoding efficiency significantly falls behind obfuscation-based scheme and is $\approx \sqrt{t} \cdot s$, where $s$ is the space of the computation.
We construct, under the same assumption, succinct randomized encodings with encoding time $\approx t^{\varepsilon} \cdot s$ for arbitrarily small constant $\varepsilon<1$. Our construction is relatively simple, generic and relies on any laconic function evaluation scheme that satisfies a natural {\em efficiency preservation} property.
Under sub-exponential assumptions, the encoding time can be further reduced to $\approx \sqrt{s}$, but at the account of a huge security loss.
As a corollary, assuming also bounded-space languages that are worst-case hard-to-parallelize, we obtain time-lock puzzles with an arbitrary polynomial gap between encoding and decoding times.
This is a joint work with Nir Bitansky.