Revisit and Challenge on Program Obfuscation with Provable Virtual Black-box Security
2017, Science Press. All right reserved. Currently, there are two kind of implementing the programs' functionality preservation in cryptographic and computationally complexity-theoretic level: functional encryption and program obfuscation. Program obfuscation is a semantic-preserving compiler algorithm that transforms a Boolean circuit/program into an obfuscated one while at the same time preserving its functionality, but it is impossible to obtain any information from the obfuscated program beyond black-box access to the original program. Obfuscation makes it hard to reverse the released software with cryptographic methodology, and thus can be used in strong software copyright protection, securely outsourcing computation, and sensitive proxy operation, etc. However, Barak et al. gave the negative result to show that it is impossible to gain an obfuscator for (natural) general-purpose circuits in (somewhat strong and idealized) virtual black-box security. In this paper, we investigate the state-of-the-art of the obfuscation, including the models, security, constructions and performance. Also, we give the (im-)possibilities for the concrete functions/circuits w.r.t the security definitions, and provide some constructions about the concrete functions, such as (multi-)point function and re-encryption functionality families. We also analyze and discuss some security models and requirements of program obfuscations, including virtual black-box secure obfuscation, virtual gray-box secure obfuscation, best-possible obfuscation, extractability obfuscation and indistinguishability obfuscation etc. Finally, we analyze the performance and compare the schemes in according to the computation cost, security models, and practical applications.