Paper 2015/704

Indistinguishability Obfuscation: from Approximate to Exact

Nir Bitansky and Vinod Vaikuntanathan

Abstract

We show general transformations from subexponentially-secure approximate indistinguishability obfuscation (IO) where the obfuscated circuit agrees with the original circuit on a $1/2+\epsilon$ fraction of inputs, into exact indistinguishability obfuscation where the obfuscated circuit and the original circuit agree on all inputs (except for a negligible probability over the coin tosses of the obfuscator). 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 (Eprint 2015), and Mahmoody, Mohammed and Nemathaji (Eprint 2015), we show how to convert indistinguishability obfuscation schemes in various ideal models into exact obfuscation schemes in the plain model.

Note: - Added almost exact to exact transformation. - Added missing details to section 5.

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in TCC 2016
Keywords
ObfusactionFunctional-EncryptionSecure-Function-EvaluationError-Correction
Contact author(s)
nirbitan @ csail mit edu
History
2017-09-25: last of 6 revisions
2015-07-14: received
See all versions
Short URL
https://ia.cr/2015/704
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/704,
      author = {Nir Bitansky and Vinod Vaikuntanathan},
      title = {Indistinguishability Obfuscation: from Approximate to Exact},
      howpublished = {Cryptology ePrint Archive, Paper 2015/704},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/704}},
      url = {https://eprint.iacr.org/2015/704}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.