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.

Batch proofs are proof systems that convince a verifier that x1,…,xt ∈ 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 BARGs) 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 BARGs 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 BARGs 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.

Non-interactive delegation schemes enable producing succinct proofs (that can be efficiently verified) that a machine M transitions from c1to c2in a certain number of deterministic steps. We here consider the problem of efficiently merging such proofs: given a proof Π1that M transitions from c1to c2, and a proof Π2that M transitions from c2to c3, can these proofs be efficiently merged into a single short proof (of roughly the same size as the original proofs) that M transitions from c1to c3? 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.

Abstract Succinct non-interactive arguments (SNARGs) enable verifying NP statements with lower complexity than required for classical NP verification. Traditionally, the focus has been on minimizing the length of such arguments; nowadays, researchers have focused also on minimizing verification time, by drawing motivation from the problem of delegating computation. A common relaxation is a preprocessing SNARG, which allows the verifier to conduct an expensive offline phase that is independent of the statement to be proven later. Recent constructions of preprocessing SNARGs have achieved attractive features: they are publicly-verifiable, proofs consist of only O (1) encrypted (or encoded) field elements, and verification is via arithmetic circuits of size linear in the NP statement. Additionally, these constructions seem to have “escaped the hegemony” of probabilistically-checkable proofs (PCPs) as a basic building block of succinct arguments. We present a general methodology for the construction of preprocessing $$\text{ SNARG } $$ SNARG s, as well as resulting new efficiency features. Our contribution is threefold: (1) We introduce and study a natural extension of the interactive proof model that considers algebraically-bounded provers; this new setting is analogous to the common study of algebraically-bounded “adversaries” in other fields, such as pseudorandomness and randomness extraction. More concretely, in this work we focus on linear (or affine) provers, and provide several constructions of (succinct two-message) linear interactive proofs (LIPs) for NP. Our constructions are based on general transformations applied to both linear PCPs (LPCPs) and traditional “unstructured” PCPs. (2) We give conceptually simple cryptographic transformations from LIPs to preprocessing SNARGs, whose security can be based on different forms of linear targeted malleability (implied by previous knowledge assumptions). Our transformations convert arbitrary (two-message) LIPs into designated-verifier SNARGs, and LIPs with degree-bounded verifiers into publicly-verifiable SNARGs. We also extend our methodology to obtain zero-knowledge LIPs and SNARGs. Our techniques yield SNARGs of knowledge and thus can benefit from known recursive composition and bootstrapping techniques. (3) Following this methodology, we exhibit several constructions achieving new efficiency features, such as “single-ciphertext preprocessing SNARGs.” We also offer a new perspective on existing constructions of preprocessing SNARGs, revealing a direct connection of these to LPCPs and LIPs.

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.

The round complexity of zero-knowledge protocols is a long-standing open question, yet to be settled under standard assumptions. So far, the question has appeared equally challenging for relaxations such as weak zero-knowledge and witness hiding. Protocols satisfying these relaxed notions under standard assumptions have at least four messages, just like full-fledged zero-knowledge. The difficulty in improving round complexity stems from a fundamental barrier: none of these notions can be achieved in three messages via reductions (or simulators) that treat the verifier as a black box.

We introduce a new notion of multi-collision resistance for keyless hash functions. This is a natural relaxation of collision resistance where it is hard to find multiple inputs with the same hash in the following sense. The number of colliding inputs that a polynomial-time non-uniform adversary can find is not much larger than its advice. We discuss potential candidates for this notion and study its applications.

Time-lock puzzles are a mechanism for sending messages "to the future". A sender can quickly generate a puzzle with a solution s that remains hidden until a moderately large amount of time t has elapsed. The solution s should be hidden from any adversary that runs in time significantly less than t, including resourceful parallel adversaries with polynomially many processors.

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 nonstandard knowledge assumption on certain functions. We make headway in the study of the existence of extractable one-way functions (EOWFs) along two directions. On the negative side, we show that if there exist indistinguishability obfuscators for 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 (such as subexponential 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 verifiers in the same class of adversarial programs, from essentially the same assumptions.

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.

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 technique has given rise to various powerful applications and is a key component in all known protocols with non-black-box simulation. We present the first non-black-box simulation technique that does not rely on Barak's technique (or on nonstandard assumptions). Invoking this technique, we obtain new and improved protocols resilient to various resetting attacks. These improvements include weaker computational assumptions and better round complexity. A prominent feature of our technique is its compatibility with rewinding techniques from classic black-box zero-knowledge protocols. The combination of rewinding with non-black-box simulation has proven instrumental in coping with challenging goals such as simultaneously resettable zero-knowledge, proofs of knowledge, and resettable security from one-way functions. While previous works required tailored modifications to Barak's technique, we give a general recipe for combining our technique with rewinding. This yields simplified resettable protocols in the above settings, as well as improvements in round complexity and required computational assumptions. The main ingredient in our technique is a new impossibility result for general program obfuscation. The results extend the impossibility result of Barak et al. (CRYPTO 2001) to the case of obfuscation with approximate functionality, thus settling a question left open by Barak et al. In the converse direction, we show a generic transformation from any resettably sound zero-knowledge protocol to a family of functions that cannot be obfuscated.

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.

The traditional notion of program obfuscation requires that an obfuscation ~Prog of a program Prog computes the exact same function as Prog, but beyond that, the code of ~Prog should not leak any information about Prog. This strong notion of virtual black-box security was shown by Barak et al. (CRYPTO 2001) to be impossible to achieve, for certain unobfuscatable function families. The same work raised the question of approximate obfuscation, where the obfuscated ~Prog is only required to approximate Prog; that is, ~Prog only agrees with Prog with high enough probability on some input distribution.

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.