Obfuscation for Evasive Functions

An

evasive circuit family

is a collection of circuits

$\mathcal{C}$

such that for every input

x

, a random circuit from

$\mathcal{C}$

outputs 0 on

x

with overwhelming probability. We provide a combination of definitional, constructive, and impossibility results regarding obfuscation for evasive functions:

1

The (average case variants of the) notions of

virtual black box

obfuscation (Barak et al, CRYPTO ’01) and

virtual gray box

obfuscation (Bitansky and Canetti, CRYPTO ’10) coincide for evasive function families. We also define the notion of

input-hiding

obfuscation for evasive function families, stipulating that for a random

$C \in{\mathcal{C}}$

it is hard to find, given

$\mathcal{O}(C)$

, a value outside the preimage of 0. Interestingly, this natural definition, also motivated by applications, is likely not implied by the seemingly stronger notion of average-case virtual black-box obfuscation.

2

If there exist average-case virtual gray box obfuscators for all evasive function families, then there exist (quantitatively weaker) average-case virtual gray obfuscators for

all

function families.

3

There does not exist a

worst-case

virtual black box obfuscator even for evasive circuits, nor is there an average-case virtual gray box obfuscator for evasive

Turing machine

families.

4

Let

$\mathcal{C}$

be an evasive circuit family consisting of functions that test if a low-degree polynomial (represented by an efficient arithmetic circuit) evaluates to zero modulo some large prime

p

. Then under a natural analog of the discrete logarithm assumption in a group supporting multilinear maps, there exists an input-hiding obfuscator for

$\mathcal{C}$

. Under a new

perfectly-hiding multilinear encoding

assumption, there is an average-case virtual black box obfuscator for the family

$\mathcal{C}$

.