Search Results

Annihilation attacks, introduced in the work of Miles, Sahai, and Zhandry (CRYPTO 2016), are a class of polynomial-time attacks against several candidate indistinguishability obfuscation (IO) schemes, built from Garg, Gentry, and Halevi (EUROCRYPT 2013) multilinear maps. In this work, we provide a general efficiently-testable property for two single-input branching programs, called partial inequivalence, which we show is sufficient for our variant of annihilation attacks on several obfuscation constructions based on GGH13 multilinear maps. We give examples of pairs of natural NC1 circuits, which - when processed via Barrington's Theorem - yield pairs of branching programs that are partially inequivalent. As a consequence we are also able to show examples of "bootstrapping circuits,'' (albeit somewhat artificially crafted) used to obtain obfuscations for all circuits (given an obfuscator for NC1 circuits), in certain settings also yield partially inequivalent branching programs. Prior to our work, no attacks on any obfuscation constructions for these settings were known.

Non-malleable codes, introduced by Dziembowski, Pietrzak, and Wichs (ICS'10) provide the guarantee that if a codeword c of a message m, is modified by a tampering function f to c', then c' either decodes to m or to "something unrelated" to m. In recent literature, a lot of focus has been on explicitly constructing such codes against a large and natural class of tampering functions such as split-state model in which the tampering function operates on different parts of the codeword independently. In this work, we consider a stronger adversarial model called block-wise tampering model, in which we allow tampering to depend on more than one block: if a codeword consists of two blocks c = (c1, c2), then the first tampering function f1 could produce a tampered part c'_1 = f1(c1) and the second tampering function f2 could produce c'_2 = f2(c1, c2) depending on both c2 and c1. The notion similarly extends to multiple blocks where tampering of block ci could happen with the knowledge of all cj for j <= i. We argue this is a natural notion where, for example, the blocks are sent one by one and the adversary must send the tampered block before it gets the next block. A little thought reveals that it is impossible to construct such codes that are non-malleable (in the standard sense) against such a powerful adversary: indeed, upon receiving the last block, an adversary could decode the entire codeword and then can tamper depending on the message. In light of this impossibility, we consider a natural relaxation called non-malleable codes with replacement which requires the adversary to produce not only related but also a valid codeword in order to succeed. Unfortunately, we show that even this relaxed definition is not achievable in the information-theoretic setting (i.e., when the tampering functions can be unbounded) which implies that we must turn our attention towards computationally bounded adversaries. As our main result, we show how to construct a block-wise non-malleable code (BNMC) from sub-exponentially hard one-way permutations. We provide an interesting connection between BNMC and non-malleable commitments. We show that any BNMC can be converted into a nonmalleable (w.r.t. opening) commitment scheme. Our techniques, quite surprisingly, give rise to a non-malleable commitment scheme (secure against so-called synchronizing adversaries), in which only the committer sends messages. We believe this result to be of independent interest. In the other direction, we show that any non-interactive non-malleable (w.r.t. opening) commitment can be used to construct BNMC only with 2 blocks. Unfortunately, such commitment scheme exists only under highly non-standard assumptions (adaptive one-way functions) and hence can not substitute our main construction.