An Overview on the Secure Program Obfuscation

doi:10.3969/j.issn.1671-1122.2014.08.002

Abstract

Abstract: Program obfuscation is a compiler that transfers the original program into an unintelligible form while preserving the functionality. The concept of obfuscation was first introduced in code obfuscation, which is used for software protection, digital watermarking, etc. However, it lacks formal analysis and security proof. Obfuscation for cryptographic purposes was proposed by Barak et al., and they gave the formal definition of `virtual black-box obfuscation and its security requirements. General obfuscation of cryptographic functions has important meaning in theoretical research and has close relation with other cryptographic primitives such as random oracle, fully homomorphic encryption, zero knowledge, etc. Besides, secure obfuscation of specific cryptographic functions has practical use in cloud computing and delegate computing. In recent years, secure program obfuscation has become one of the hottest topics in the progress of cryptographic research. As obfuscation of general function families was proved impossible under Barak’s standard definition, thus following researches are mainly focused on realizing secure obfuscation of specific families of functions, new definition models of obfuscation, and relations and applications of obfuscation in other cryptographic primitives. In this paper, we give an overview on the study of secure obfuscation, which includes constructions of secure obfuscation of specific cryptographic functions, studies on special models of obfuscation and generalization and applications of secure obfuscation.

Key words: cryptography, program obfuscation, virtual black-box property

CLC Number:

TP309

CHENG Rong, ZHANG Fang-guo. An Overview on the Secure Program Obfuscation[J]. 信息网络安全, 2014, 14(8): 6-11.

References

[1] G. Wroblewski. General method of program code obfuscation[D]. Doctoral dissertation, WroclawUniversity of Technology, Institute of Engineering Cybernetics, 2002.
[2] C. Linn, S. Debray. Obfuscation of executable code to improve resistance to static disassembly[C]. The 10th ACM conference on Computer and communications security, pp.290-299, 2003.
[3] W. Zhu, C. Thomborson. A provable scheme for homomorphic obfuscation in softwaresecurity[M]. CNIS 2005, 5: 208-212, 2005.
[4] W. Zhu, C. Thomborson, F. Y. Wang. Applications of homomorphic functions to softwareobfuscation[J]. Intelligence and Security Informatics, LNCS 3917, pp. 152-153, Springer,2006.
[5] A. Amarilli, D. Naccache, P. Rauzy, et al. Can a program reverse-engineer itself?[J]. Cryptography and Coding, LNCS 7089, pp. 1-9, Springer, 2011.
[6] R. Giacobazzi. Hiding information in completeness holes: New perspectives in code obfuscation and watermarking[C]. SEFM 2008, pp. 7-18, 2008.
[7] C. S. Collberg, C. Thomborson. Watermarking, tamper-proofing, and obfuscation-tools for software protection[M]. IEEE Transactions on Software Engineering, 28(8): 735-746,2002.
[8] Z. A. Kissel. Obfuscation of the standard XOR encryption algorithm[J]. Crossroads, 11(3):6-6, 2005.
[9] J. Bringer, H. Chabanne, T. Icart. On physical obfuscation of cryptographic algorithms[C]. INDOCRYPT 2009, LNCS 5922, pp. 88-103, Springer, 2009.
[10] T. Ogiso, Y. Sakabe, M. Soshi, et al. Software obfuscation on a theoretical basis and its implementation[J]. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 86(1): 176-186, 2003.
[11] 史扬, 曹立明, 王小平. Java 混淆器的设计与实现[J]. 计算机应用, 24(11): 63-65, 2004.
[12] N. Kuzurin, A. Shokurov, N. Varnovsky, et al. On the concept of software obfuscation in computer security[J]. Information Security, LNCS 4779, pp. 281-298, Springer,2007.
[13] 刘晓英, 沈金龙. 软件开发中的一个重要环节——混淆[J]. 南京邮电学院学报: 自然科学版,24(1): 59-63, 2004.
[14] H. E. Link, W. D. Neumann. Clarifying obfuscation: improving the security of white-box DES[M]. ITCC 2005, 1: 679-684, 2005.
[15] L. Goubin, J. M. Masereel, M. Quisquater. Cryptanalysis of white box DES implementations[J]. Selected Areas in Cryptography, LNCS 4876, pp. 278-295, Springer, 2007.
[16] B. Barak, O. Goldreich, R. Impagliazzo, et al. On the (im)possibility of obfuscating programs[M]. Crypto 2001, LNCS 2139, pp. 1-18, Springer,2001.
[17] M. D. Preda, R. Giacobazzi. Semantic-based code obfuscation by abstract interpretation[J]. Automata, Languages and Programming, LNCS 3580, pp. 1325-1336, Springer,2005.
[18] F. Koushanfar, Y. Alkabani. Provably secure obfuscation of diverse watermarks for sequential circuits[M]. HOST 2010, pp. 42-47, 2010.
[19] N. Mavrogiannopoulos, N. Kisserli, B. Preneel. A taxonomy of self-modifying code for obfuscation[J]. Computers and Security, 30(8): 679-691, 2011.
[20] S. Schrittwieser, S. Katzenbeisser. Code obfuscation against static and dynamic reverse engineering[J]. Information Hiding, LNCS 6958, pp. 270-284, Springer, 2011.
[21] S. Schrittwieser, S. Katzenbeisser, P. Kieseberg, et al. Covert computation: hiding code in code for obfuscation purposes[C]. ACM SIGSAC symposium on Information, computer and communications security, pp. 529-534,2013.
[22] A. R. Desai, M. S. Hsiao, C. Wang, et al. Interlocking obfuscation for antitamper hardware[C]. The Eighth Annual Cyber Security and Information Intelligence Research Workshop, No.8, 2013.
[23] Z. Vrba, P. Halvorsen, C. Griwodz. Program obfuscation by strong cryptography[M]. ARES 2010, pp. 242-247, 2010.
[24] J. Li, J. Li, et al. Enabling efficient and secure data sharing in cloud computing[J]. Concurrency and Computation: Practice and Experience, doi:10.1002/cpe.3067,2013.
[25] S. Tu, S. Niu, H. Li. A fine-grained access control and revocation scheme on clouds[J]. Concurrency and Computation: Practice and Experience, doi:10.1002/cpe.2956, 2012.
[26] G. Wang, Q. Liu, J. Wu. Achieving fine-grained access control for secure data sharing on cloud servers[J]. Concurrency and Computation: Practice and Experience, 23(12): 1443-1464, 2011.
[27] X. Chen, J. Li, J. Ma, et al. New algorithms for secure outsourcing of modular exponentiations[M]. ESORICS 2012, LNCS 7459, pp. 541-556, Springer, 2012.
[28] X. Chen, J. Li, W. Susilo. Efficient fair conditional payments for outsourcing computations[J]. IEEE Transactions on Information Forensics and Security, 7(6): 1687-1694,2012.
[29] M. Mowbray, S. Pearson, Y. Shen. Enhancing privacy in cloud computing via policybased obfuscation[J]. The Journal of Supercomputing, 61(2): 267-291, 2012.
[30] M. Rosulek. Must you know the code of f to securely compute f?[M]. CRYPTO 2012, LNCS 7417, pp. 87-104, Springer, 2012.
[31] C. Gentry. A fully homomorphic encryption scheme[D]. Doctoral dissertation, Stanford University, 2009.
[32] Z. Brakerski, V. Vaikuntanathan. Efficient fully homomorphic encryption from (standard) LWE[M]. FOCS 2011, pp. 97-106, IEEE, 2011.
[33] S. Hada, K. Sakurai. A note on the (im)possibility of using obfuscators to transform private-key encryption into public-key encryption[J]. Advances in Information and Computer Security, LNCS 4752, pp. 1-12, Springer, 2007.
[34] S. Hohenberger, G. N. Rothblum, A. Shelat,et al. Securely obfuscating re-encryption[M]. TCC 2007, LNCS 4392, pp. 233-252, Springer, 2007.
[35] S. Goldwasser, Y. T. Kalai. On the impossibility of obfuscation with auxiliary input[M]. FOCS 2005, pp. 553-562, 2005.
[36] S. Garg, C. Gentry, S. Halevi, et al. Candidate indistinguishability obfuscation and functional encryption for all circuits[M]. FOCS 2013, pp. 40-49,2013.
[37] N. Bitansky, R. Canetti, O. Paneth, et al. More on the impossibility of virtualblack-box obfuscation with auxiliary input[J]. Cryptology ePrint Archive, Report 701, 2013.
[38] Y. Dodis, Y. T. Kalai, S. Lovett. On cryptography with auxiliary input[C]. The 41st annual ACM symposium on Theory of computing, pp. 621-630, 2009.
[39] R. Canetti. Towards realizing random oracles: Hash functions that hide all partial information[M]. Crypto 1997, LNCS 1294, pp. 455-469, Springer, 1997.
[40] B. Lynn, M. Prabhakaran, A. Sahai. Positive results and techniques for obfuscation[M]. Eurocrypt 2004, LNCS 3027, pp. 20-39, Springer, 2004.
[41] H. Wee. On obfuscating point funtions[C]. The 37th ACM symposium on theory of computing, pp. 523-532, 2005.
[42] R. Canetti, R. R. Dakdouk. Obfuscation point functions with multibit output[M]. Eurocrypt 2008, LNCS 4965, pp. 489-508, Springer, 2008.
[43] N. Bitansky, R. Canetti. On strong simulation and composable point obfuscation[M]. Crypto 2010, LNCS 6223, pp. 520-537, Springer, 2010.
[44] R. Canetti, Y. T. Kalai, M. Varia, et al. On symmetric encryption and point obfuscation[M]. TCC 2010, LNCS 5978, pp. 52-71, Springer, 2010.
[45] 龚高翔, 袁征, 李超. 基于多比特输出点函数混淆器的消息认证码[J]. 计算机工程, 39(1):144-148, 2013.
[46] W. E. Anderson. On the secure obfuscation of deterministic finite automata[J]. Cryptology ePrint Archive, Report 184, 2008.
[47] R. Canetti, G. Rothblum, M. Varia. Obfuscation of hyperplane membership[M]. TCC 2010, LNCS 5978, pp. 72-89, Springer, 2010.
[48] Z. Brakerski, G. N. Rothblum. Obfuscating conjunctions[M]. CRYPTO 2013, LNCS 8043, pp. 416-434, Springer, 2013.
[49] N. Chandran, M. Chase, V. Vaikuntanathan. Functional re-encryption and collusionresistant obfuscation[J]. Theory of Cryptography, LNCS 7194, pp. 404-421, Springer, 2012.
[50] S. Hada. Secure obfuscation for encrypted signatures[M]. Eurocrypt 2010, LNCS 6110, pp.92-112, Springer, 2010.
[51] B. Waters. Efficient identity-based encryption without random oracles[M]. Eurocrypt 2005,LNCS 3494, pp. 114-127, Springer, 2005.
[52] D. Boneh, X. Boyen, H. Shacham. Short group signatures[M]. Crypto 2004, LNCS 3152,pp. 41-55, Springer, 2004.
[53] 陈兴发, 高崇志, 姚正安. 安全加密的环签名混淆器[J]. 中山大学学报自然科学版, 53(1):8-17, 2014.
[54] X. Feng, Z. Yuan. A secure obfuscator for encrypted blind signature functionality[J].Cryptology ePrint Archive, Report 716, 2013.
[55] C. Li, Z. Yuan, M. Mao. Secure obfuscation of a two-step oblivious signature[J]. Network Computing and Information Security, Volume 345, pp. 680-688, Springer, 2012.
[56] N. Ding, D. Gu. A note on obfuscation for cryptographic functionalities of secretoperation then public-encryption[J]. Theory and Applications of Models of Computation, LNCS 6648, pp. 377-389, Springer, 2011.
[57] R. Ostrovsky, W. E. Skeith. Private searching on streaming data[M]. CRYPTO 2005, LNCS 3621, pp. 223-240, Springer, 2005.
[58] B. Adida, D. Wikstro¨m. Obfuscated ciphertext mixing[J]. Cryptology ePrint Archive,Report 394, 2005.
[59] B. Adida and D. Wikstro¨m. How to shuffle in public[J]. Theory of Cryptography, LNCS 4392, pp. 555-574, Springer, 2007.
[60] V. Goyal, Y. Ishai, A. Sahai. Founding cryptography on tamper-proof hardware tokens[M]. TCC 2010, LNCS 5978, pp. 308-326, Springer, 2010.
[61] S. Goldwasser. Program obfuscation and one-time programs[M]. CT-RSA 2008, LNCS 4964, pp. 333-334, Springer, 2008.
[62] N. D¨ottling, T. Mie, J. M¨uller-Quade. Basing obfuscation on simple tamper-proofhardware assumptions[J]. Cryptology ePrint Archive, Report 675, 2011.
[63] K. Fukushima, S. Kiyomoto, T. Tanaka. Obfuscation mechanism in conjunction with tamper-proof module[M]. CSE 2009, 2: 665-670, 2009.
[64] N. Bitansky, R. Canetti, S. Goldwasser, et al. Program obfuscation with leaky hardware[M]. ASIACRYPT 2011, LNCS 7073, pp. 722-739, Springer, 2011.
[65] D. A. Barrington. Bounded-width polynomial-size branching programs recognize exactly those languages in NC1[J]. Journal of Computer and System Sciences, 38(1): 150-164,1989.
[66] R. Canetti, V. Vaikuntanathan. Obfuscating branching programs using black-box pseudo-free groups[J]. Cryptology ePrint Archive, Report 500, 2013.
[67] R. Pass, S. Telang, K. Seth. Obfuscation from semantically-secure multi-linear encodings[J]. Cryptology ePrint Archive, Report 781, 2013.
[68] Z. Brakerski, G. N. Rothblum. Virtual black-box obfuscation for all circuits via generic graded encoding[J]. Cryptology ePrint Archive, Report 563, 2013.
[69] E. Boyle, K. M. Chung, R. Pass. On extractability obfuscation[J]. Cryptology ePrint Archive, Report 650, 2013.
[70] S. Goldwasser, G. N. Rothblum. On best-possible obfuscation[J]. Theory of Cryptography, LNCS 4392, pp. 194-213, Springer, 2007.
[71] R. Canetti, M. Varia. Non-malleable obfuscation[J]. Theory of Cryptography, LNCS 5444, pp. 73-90, Springer, 2009.
[72] S. Hada. Zero-knowledge and code obfuscation[M]. ASIACRYPT 2000, LNCS 1976, pp.443-457, Springer, 2000.
[73] D. Hofheinz, J. Malone-Lee, M. Stam. Obfuscation for cryptographic purposes[M]. TCC 2007, LNCS 4392, pp. 214-232, Springer, 2007.
[74] N. Bitansky, O. Paneth. Point obfuscation and 3-round zero-knowledge[M]. TCC 2012, LNCS 7194, pp. 190-208, Springer, 2012.
[75] N. Bitansky, O. Paneth. From the impossibility of obfuscation to a new non-black-box simulation technique[M]. FOCS 2012, pp. 223-232, 2012.
[76] O. Pandey, M. Prabhakaran, A. Sahai. Obfuscation-based non-black-box simulation and four message concurrent zero knowledge for NP[J]. Cryptology ePrint Archive, Report 754,2013.
[77] B. Barak, O. Goldreich, S. Goldwasser, et al. Resettably-sound zero-knowledge and its applications[M]. FOCS 2001, pp. 116-125, 2001.
[78] B. Barak. How to go beyond the black-box simulation barrier[M]. FOCS 2001, pp. 106-115,2001.
[79] S. Hohenberger, A. Sahai, B. Waters. Replacing a random oracle: Full domain hash from indistinguishability obfuscation[J]. Cryptology ePrint Archive, Report 509, 2013.
[80] D. Boneh, M. Zhandry. Multiparty key exchange, efficient traitor tracing, and more from indistinguishability obfuscation[J]. Cryptology ePrint Archive, Report 642, 2013.
[81] A. Sahai, B. Waters. How to use indistinguishability obfuscation: Deniable encryption, and more[J]. Cryptology ePrint Archive, Report 454, 2013.
[82] S. Garg, C. Gentry, S. Halevi, et al. Two-round secure mpc from indistinguishability obfuscation[J]. Cryptology ePrint Archive, Report 601, 2013.
[83] R. P. Hooker. Functional encryption as mediated obfuscation[D]. Doctoral dissertation, the University of Montana, 2012.
[84] S. Garg, C. Gentry, S. Halevi, et al. On the implausibility of differing-inputs obfuscation and extractable witness encryption with auxiliary input[J]. Cryptology ePrint Archive, Report 860, 2013.
[85] A. Marcedone, C. Orlandi. Obfuscation)(ind-cpa security ; circular security)[J].Cryptology ePrint Archive, Report 690, 2013.