Results 771 - 780 of 23787
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.
Abstract not available.
Obfuscation of quantum programs is emerging as a fascinating and still largely mysterious frontier in cryptography. In this talk, I will present recent progress in this area: a new obfuscation scheme capable of handling any quantum program that implements a unitary transformation, even those involving auxiliary quantum states. I will give a high-level overview of the core techniques and discuss where these ideas might take us next.
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.