Results 1891 - 1900 of 23883
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.
We construct an adaptively-sound succinct non-interactive argument (SNARG) for NP in the CRS model from sub-exponentially-secure indistinguishability obfuscation (iO) and sub-exponentially-secure one-way functions. Previously, Waters and Wu (STOC 2024), and subsequently, Waters and Zhandry (CRYPTO 2024) showed how to construct adaptively-sound SNARGs for NP by relying on sub-exponentially-secure indistinguishability obfuscation, one-way functions, and an additional algebraic assumption
(i.e., discrete log, factoring, or learning with errors). In this work, we show that no additional algebraic assumption is needed and vanilla (sub-exponentially-secure) one-way functions already suffice in combination with iO.
Martha is a student assistant at the Simons Institution and a current fourth year Architecture student at UC Berkeley. She likes to hike, go to sporting events and travel. Her favorite places she’s visited are Greece and Turkey.
Nicole Megow is a faculty member at the Faculty of Mathematics and Computer Science at the University of Bremen, Germany. She is interested in combinatorial optimization, approximation algorithms, algorithms under uncertainty.
Indistinguishability obfuscation (iO) has seen notable recent advances, yet it remains largely a theoretical cryptographic primitive because existing constructions are still complex and inefficient. Specifically, most state-of-the-art iO constructions rely on costly bootstrapping from functional encryption (FE) to iO, which invokes the FE encryption algorithm recursively for every input bit. Consequently, the size and complexity of that algorithm impose a lower bound on the complexity of the functions that the underlying FE scheme must evaluate, creating a major obstacle to practical iO.
We address this bottleneck with Diamond iO, a new iO construction that replaces FE-to-iO bootstrapping with simple matrix multiplications. We prove security in the pseudorandom oracle model under the learning with errors (LWE) and evasive LWE assumptions, as well as our new assumption that we call all-product LWE. The construction leverages a non-black-box use of the compact pseudorandom FE scheme introduced by Agrawal, Kumari, and Yamada (ePrint ’24).
In this talk, we outline the core ideas behind Diamond iO and its security proof, together with a cryptanalysis of the non-standard assumptions on which the construction relies. We will also present benchmark results from our prototype implementation, along with its current limitations and simplifications, highlighting concrete progress toward practical iO.
Indistinguishability obfuscation (iO) is a powerful cryptographic primitive with numerous impactful applications. However, constructing post-quantum iO under simple and well-founded assumptions remains a significant challenge. Following the framework initiated by Brakerski et al. (Eurocrypt 2020), recent work has explored building post-quantum (x)iO by combining fully homomorphic encryption (FHE) with carefully designed “decryption hints” for homomorphically evaluated ciphertexts. The security of these constructions typically reduces to "LWE-with-hint" type assumptions, which assert the security of certain LWE samples even when specific auxiliary information is revealed. Unfortunately, subsequent cryptanalysis has identified structural weaknesses in all previously proposed variants of these assumptions, casting doubt on their soundness.
In response, we introduce a new assumption - Circular Security with Random Opening (CRO) - which overcomes key vulnerabilities in prior LWE-with-hint formulations. The CRO assumption features two critical properties: (1) the hint distribution is marginally uniform, and (2) natural uses of the hint do not give any noise leakage. These properties rule out important classes of attack strategies, including those that have broken earlier assumptions. Therefore, our new lattice-based assumption for iO provides a qualitatively different target for cryptanalysis compared to existing assumptions.
In this talk, I will begin by reviewing key ideas from earlier iO constructions and highlighting the problematic leakages that have been exploited in attacks. I will then present our new construction and explain the core insights that eliminate the known vulnerable structures.
Based on joint work with Aayush Jain and Huijia Lin.