Nir Bitansky

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 2024 Conference Paper

Dot-Product Proofs and Their Applications

• Nir Bitansky
• Prahladh Harsha
• Yuval Ishai
• Ron D. Rothblum
• David J. Wu 0001

A dot-product proof (DPP) is a simple probabilistic proof system in which the input statement $\boldsymbol{x}$ and the proof $\boldsymbol{\pi}$ are vectors over a finite field $\mathbb{F}$, and the proof is verified by making a single dot-product query $\langle \boldsymbol{q}, (\boldsymbol{x}\Vert\boldsymbol{\pi})\rangle$ jointly to $\boldsymbol{x}$ and $\boldsymbol{\pi}$. A DPP can be viewed as a 1-query fully linear PCP. We study the feasibility and efficiency of D PPs, obtaining the following results: •Small-field DPP. For any finite field $\mathbb{F}$ and Boolean circuit $C$ of size $S$, there is a D PP for proving that there exists $\boldsymbol{w}$ such that $C(\boldsymbol{x}, \ \boldsymbol{w})=1$ with a proof $\boldsymbol{\pi}$ of length $S\cdot \text{poly}(\vert \mathbb{F}\vert)$ and soundness error $\varepsilon=O(1/\sqrt{\vert \mathbb{F}\vert })$. We show this error to be asymptotically optimal. In particular, and in contrast to the best known PCPs, there exist strictly linear-length DPPs over constant-size fields. •Large-field DPP. If $\vert \mathbb{F}\vert\geq$ poly $(S/\varepsilon)$, there is a similar DPP with soundness error $\varepsilon$ and proof length $O(S)$ (in field elements). The above results do not rely on the PCP theorem and their proofs are considerably simpler. We apply our DPP constructions toward two kinds of applications. •Hardness of approximation. We obtain a simple proof for the NP-hardness of approximating MAXLIN (with dense instances) over any finite field $\mathbb{F}$ up to some constant factor $c > 1$, independent of F. Unlike previous PCP-based proofs, our proof yields exponential-time hardness under the exponential time hypothesis (ETH). •Succinct arguments. We improve the concrete efficiency of succinct interactive arguments in the generic group model using input-independent preprocessing. In particular, the communication is comparable to sending two group elements and the verifier's computation is dominated by a single group exponentiation. We also show how to use DPPs together with linear-only encryption to construct succinct commit-and-prove arguments.

STOC Conference 2020 Conference Paper

Post-quantum zero knowledge in constant rounds

• Nir Bitansky
• Omri Shmueli

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

Indistinguishability Obfuscation from Functional Encryption

• Nir Bitansky
• Vinod Vaikuntanathan

Indistinguishability obfuscation (IO) is a tremendous notion, powerful enough to give rise to almost any known cryptographic object. So far, candidate IO constructions were based on specific assumptions on algebraic objects called multi-linear graded encodings. We present a generic construction of indistinguishability obfuscation from public-key functional encryption with succinct cipher texts and sub-exponential security. This shows the equivalence of indistinguishability obfuscation and public-key functional encryption, a primitive that has so far seemed to be much weaker, lacking the power and the staggering range of applications of indistinguishability obfuscation. As an application, we obtain a new candidate IO construction based on the functional encryption scheme of Garg, Gentry, Halevi, and Zhan dry [Eprint 14] under their assumptions on multi-linear graded encodings. We also show that, under the Learning with Errors assumptions, our techniques imply that any indistinguishability obfuscator can be converted to one where obfuscated circuits are of linear size in the size of the original circuit plus a polynomial overhead in its depth. Our reduction highlights the importance of cipher text succinctness in functional encryption schemes, which we hope will serve as a pathway to new IO constructions based on solid cryptographic foundations.

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 2015 Conference Paper

Succinct Randomized Encodings and their Applications

• Nir Bitansky
• Sanjam Garg
• Huijia Lin
• Rafael Pass
• Sidharth Telang

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

STOC Conference 2013 Conference Paper

Recursive composition and bootstrapping for SNARKS and proof-carrying data

• Nir Bitansky
• Ran Canetti
• Alessandro Chiesa
• Eran Tromer

Succinct non-interactive arguments of knowledge (SNARKs) enable verifying NP statements with complexity that is essentially independent of that required for classical NP verification. In particular, they provide strong solutions to the problem of verifiably delegating computation. We construct the first fully-succinct publicly-verifiable SNARK. To do that, we first show how to "bootstrap" any SNARK that requires expensive preprocessing to obtain a SNARK that does not, while preserving public verifiability. We then apply this transformation to known SNARKs with preprocessing. Moreover, the SNARK we construct only requires of the prover time and space that are essentially the same as that required for classical NP verification. Our transformation assumes only collision-resistant hashing; curiously, it does not rely on PCPs. We also show an analogous transformation for privately-verifiable SNARKs, assuming fully-homomorphic encryption. At the heart of our transformations is a technique for recursive composition of SNARKs. This technique uses in an essential way the proof-carrying data (PCD) framework, which extends SNARKs to the setting of distributed networks of provers and verifiers. Concretely, to bootstrap a given SNARK, we recursively compose the SNARK to obtain a "weak" PCD system for shallow distributed computations, and then use the PCD framework to attain stronger notions of SNARKs and PCD systems.

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.