## Abstract

An evasive circuit family is a collection of circuits such that for every input x, a random circuit from 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 it is hard to find, given, 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 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. Under a new perfectly-hiding multilinear encoding assumption, there is an average-case virtual black box obfuscator for the family.

Original language | English (US) |
---|---|

Title of host publication | Theory of Cryptography - 11th Theory of Cryptography Conference, TCC 2014, Proceedings |

Publisher | Springer Verlag |

Pages | 26-51 |

Number of pages | 26 |

ISBN (Print) | 9783642542411 |

DOIs | |

State | Published - 2014 |

Event | 11th Theory of Cryptography Conference on Theory of Cryptography, TCC 2014 - San Diego, CA, United States Duration: Feb 24 2014 → Feb 26 2014 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 8349 LNAI |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 11th Theory of Cryptography Conference on Theory of Cryptography, TCC 2014 |
---|---|

Country/Territory | United States |

City | San Diego, CA |

Period | 2/24/14 → 2/26/14 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- General Computer Science