Indistinguishability obfuscation: From approximate to exact

Nir Bitansky, Vinod Vaikuntanathan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We show general transformations from subexponentiallysecure approximate indistinguishability obfuscation (IO) where the obfuscated circuit agrees with the original circuit on a 1/2 + ε fraction of inputs on a certain samplable distribution, into exact indistinguishability obfuscation where the obfuscated circuit and the original circuit agree on all inputs. As a step towards our results, which is of independent interest, we also obtain an approximate-to-exact transformation for functional encryption. At the core of our techniques is a method for “fooling” the obfuscator into giving us the correct answer, while preserving the indistinguishability-based security. This is achieved based on various types of secure computation protocols that can be obtained from different standard assumptions. Put together with the recent results of Canetti, Kalai and Paneth (TCC 2015), Pass and Shelat (TCC 2016), and Mahmoody, Mohammed and Nemathaji (TCC 2016), we show how to convert indistinguishability obfuscation schemes in various ideal models into exact obfuscation schemes in the plain model.

Original languageEnglish (US)
Title of host publicationTheory of Cryptography - 13th International Conference, TCC 2016-A, Proceedings
EditorsEyal Kushilevitz, Tal Malkin
PublisherSpringer Verlag
Pages67-95
Number of pages29
ISBN (Print)9783662490952
DOIs
StatePublished - 2016
Event13th International Conference on Theory of Cryptography, TCC 2016 - Tel Aviv, Israel
Duration: Jan 10 2016Jan 13 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9562
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other13th International Conference on Theory of Cryptography, TCC 2016
Country/TerritoryIsrael
CityTel Aviv
Period1/10/161/13/16

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science

Fingerprint

Dive into the research topics of 'Indistinguishability obfuscation: From approximate to exact'. Together they form a unique fingerprint.

Cite this