Omer Paneth

FOCS Conference 2025 Conference Paper

On Succinct Obfuscation via Propositional Proofs

• Abhishek Jain 0002
• Zhengzhong Jin
• Surya Mathialagan
• Omer Paneth

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. 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 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, which is known from super-polynomially hard IO for circuits and LWE, 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 $\mathbf{p v}$-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: (i)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. (ii)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. (iii)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.

STOC Conference 2024 Conference Paper

Batch Proofs Are Statistically Hiding

• Nir Bitansky
• Chethan Kamath
• Omer Paneth
• Ron D. Rothblum
• Prashant Nalini Vasudevan

Batch proofs are proof systems that convince a verifier that x 1 ,…, x t ∈ L , for some NP language L , with communication that is much shorter than sending the t witnesses. In the case of statistical soundness (where the cheating prover is unbounded but the honest prover is efficient given the witnesses), interactive batch proofs are known for UP , the class of unique-witness NP languages. In the case of computational soundness (where both honest and dishonest provers are efficient), non-interactive solutions are now known for all of NP , assuming standard lattice or group assumptions. We exhibit the first negative results regarding the existence of batch proofs and arguments: - Statistically sound batch proofs for L imply that L has a statistically witness indistinguishable ( SWI ) proof, with inverse polynomial SWI error, and a non-uniform honest prover. The implication is unconditional for obtaining honest-verifier SWI or for obtaining full-fledged SWI from public-coin protocols, whereas for private-coin protocols full-fledged SWI is obtained assuming one-way functions. This poses a barrier for achieving batch proofs beyond UP (where witness indistinguishability is trivial). In particular, assuming that NP does not have SWI proofs, batch proofs for all of NP do not exist. - Computationally sound batch proofs (a.k.a batch arguments or BARG s) for NP , together with one-way functions, imply statistical zero-knowledge ( SZK ) arguments for NP with roughly the same number of rounds, an inverse polynomial zero-knowledge error, and non-uniform honest prover. Thus, constant-round interactive BARG s from one-way functions would yield constant-round SZK arguments from one-way functions. This would be surprising as SZK arguments are currently only known assuming constant-round statistically-hiding commitments. We further prove new positive implications of non-interactive batch arguments to non-interactive zero knowledge arguments (with explicit uniform prover and verifier): - Non-interactive BARG s for NP , together with one-way functions, imply non-interactive computational zero-knowledge arguments for NP . Assuming also dual-mode commitments, the zero knowledge can be made statistical. Both our negative and positive results stem from a new framework showing how to transform a batch protocol for a language L into an SWI protocol for L .

FOCS Conference 2022 Conference Paper

Incrementally Verifiable Computation via Rate-1 Batch Arguments

• Omer Paneth
• Rafael Pass

Non-interactive delegation schemes enable producing succinct proofs (that can be efficiently verified) that a machine M transitions from c 1 to c 2 in a certain number of deterministic steps. We here consider the problem of efficiently merging such proofs: given a proof Π 1 that M transitions from c 1 to c 2, and a proof Π 2 that M transitions from c 2 to c 3, can these proofs be efficiently merged into a single short proof (of roughly the same size as the original proofs) that M transitions from c 1 to c 3? To date, the only known constructions of such a mergeable delegation scheme rely on strong non-falsifiable “knowledge extraction” assumptions. In this work, we present a provably secure construction based on the standard LWE assumption. As an application of mergeable delegation, we obtain a construction of incrementally verifiable computation (IVC) (with polylogarithmic length proofs) for any (unbounded) polynomial number of steps based on LWE; as far as we know, this is the first such construction based on any falsifiable (as opposed to knowledge-extraction) assumption. The central building block that we rely on, and construct based on LWE, is a rate-l batch argument (BARG): this is a non-interactive argument for NP that enables proving k NP statements $x_{1}, \ldots, x_{k}$ with communication/verifier complexity m + o(m), where m is the length of one witness. rate-1 BARGs are particularly useful as they can be recursively composed a super-constant number of times.

STOC Conference 2019 Conference Paper

How to delegate computations publicly

• Yael Tauman Kalai
• Omer Paneth
• Lisa Yang 0001

We construct a delegation scheme for all polynomial time computations. Our scheme is publicly verifiable and completely non-interactive in the common reference string (CRS) model. Our scheme is based on an efficiently falsifiable decisional assumption on groups with bilinear maps. Prior to this work, publicly verifiable non-interactive delegation schemes were only known under knowledge assumptions (or in the Random Oracle model) or under non-standard assumptions related to obfuscation or multilinear maps. We obtain our result in two steps. First, we construct a scheme with a long CRS (polynomial in the running time of the computation) by following the blueprint of Paneth and Rothblum (TCC 2017). Then we bootstrap this scheme to obtain a short CRS. Our bootstrapping theorem exploits the fact that our scheme can securely delegate certain non-deterministic computations.

STOC Conference 2019 Conference Paper

Weak zero-knowledge beyond the black-box barrier

• Nir Bitansky
• Dakshita Khurana
• Omer Paneth

STOC Conference 2018 Conference Paper

Multi-collision resistance: a paradigm for keyless hash functions

• Nir Bitansky
• Yael Tauman Kalai
• Omer Paneth

FOCS Conference 2015 Conference Paper

On the Cryptographic Hardness of Finding a Nash Equilibrium

• Nir Bitansky
• Omer Paneth
• Alon Rosen

We prove that finding a Nash equilibrium of a game is hard, assuming the existence of indistinguishability obfuscation and one-way functions with sub-exponential hardness. We do so by showing how these cryptographic primitives give rise to a hard computational problem that lies in the complexity class PPAD, for which finding Nash equilibrium is complete. Previous proposals for basing PPAD-hardness on program obfuscation considered a strong "virtual black-box" notion that is subject to severe limitations and is unlikely to be realizable for the programs in question. In contrast, for indistinguishability obfuscation no such limitations are known, and recently, several candidate constructions of indistinguishability obfuscation were suggested based on different hardness assumptions on multilinear maps. Our result provides further evidence of the intractability of finding a Nash equilibrium, one that is extrinsic to the evidence presented so far.

STOC Conference 2014 Conference Paper

On the existence of extractable one-way functions

• Nir Bitansky
• Ran Canetti
• Omer Paneth
• Alon Rosen

A function f is extractable if it is possible to algorithmically "extract," from any adversarial program that outputs a value y in the image of f; a preimage of y . When combined with hardness properties such as one-wayness or collision-resistance, extractability has proven to be a powerful tool. However, so far, extractability has not been explicitly shown. Instead, it has only been considered as a non-standard knowledge assumption on certain functions. We make two headways in the study of the existence of extractable one-way functions (EOWFs). On the negative side, we show that if there exist indistinguishability obfuscators for a certain class of circuits then there do not exist EOWFs where extraction works for any adversarial program with auxiliary-input of unbounded polynomial length. On the positive side, for adversarial programs with bounded auxiliary input (and unbounded polynomial running time), we give the first construction of EOWFs with an explicit extraction procedure, based on relatively standard assumptions (e.g., sub-exponential hardness of Learning with Errors). We then use these functions to construct the first 2-message zero-knowledge arguments and 3-message zero-knowledge arguments of knowledge, against the same class of adversarial verifiers, from essentially the same assumptions.

STOC Conference 2013 Conference Paper

On the impossibility of approximate obfuscation and applications to resettable cryptography

• Nir Bitansky
• Omer Paneth

FOCS Conference 2012 Conference Paper

From the Impossibility of Obfuscation to a New Non-Black-Box Simulation Technique

• Nir Bitansky
• Omer Paneth

The introduction of a non-black-box simulation technique by Barak (FOCS 2001) has been a major landmark in cryptography, breaking the previous barriers of black-box impossibility. Barak's techniques were subsequently extended and have given rise to various powerful applications. We present the first non-black-box simulation technique that does not rely on Barak's technique (or on nonstandard assumptions). Our technique is based on essentially different tools: it does not invoke universal arguments, nor does it rely on collision-resistant hashing. Instead, the main ingredient we use is the impossibility of general program obfuscation (Barak et al. , CRYPTO 2001). Using our technique, we construct a new resettably-sound zero-knowledge (rsZK) protocol. rsZK protocols remain sound even against cheating provers that can repeatedly reset the verifier to its initial state and random tape. Indeed, for such protocols black-box simulation is impossible. Our rsZK protocol is the first to be based solely on semi-honest oblivious transfer and does not rely on collision-resistant hashing; in addition, our protocol does not use PCP machinery. In the converse direction, we show a generic transformation from any rsZK protocol to a family of functions that cannot be obfuscated.