On the possibility of secure program obfuscation in some model of cloud computing
Alexander Vladimirovich Shokurov,
Irina Valerievna Abramova,
Nikolay Pavlovich Varnovsky,
Vladimir Anatolyevich Zakharov https://doi.org/10.15514/ISPRAS-2019-31(6)-8
Abstract
In this paper we study the possibility of using a certain cloud computing model supplied with cryptoservers to obfuscate software programs. Earlier, we proposed this cloud computing model in our study of some information security problems for multi-client distributed computing over encrypted data. Based on this model, we proposed a new approach involving the use of threshold homomorphic cryptosystems for program obfuscation. The main result of this paper is a new definition of the resistance of obfuscation of programs in the cloud computing model and a theorem proving the cryptographic strength of the proposed algorithm of obfuscation of programs under the assumption of the existence of cryptographically strong threshold homomorphic encryption systems. The paper is organized as follows. In the introducing section we discuss the main aspects of the information security problems for cloud computing systems. Section 2 provides a description of the obfuscation program objectives, as well as a brief overview of the main achievements in its study. The next section provides general information about homomorphic cryptosystems. Section 4 describes a more special class of homomorphic cryptosystems - threshold homomorphic encryption systems. Section 5 introduces the cloud computing model, which is used as framework for our program obfuscation techniques. For this computing environment, in Section 6, the definition of the cryptographic strength of program obfuscation is formulated, a new method of program obfuscation using threshold homomorphic cryptosystems is described, and the cryptographic strength of the proposed obfuscation algorithm is proved.
Supporting agencies: The studies, the results of which are presented in this article, were supported by the Russian Foundation for Basic Research (project 19-01-00702).
About the Authors
Alexander Vladimirovich Shokurov
Ivannikov Institute for System Programming of the Russian Academy of Sciences,
Moscow Institute of Physics and Technology (State University)
Russian Federation
Candidate of Physics and Mathematics, Associate Professor, Leading Researcher of the Department of Applied Mathematics and Computer Science, ISP RAS, Associate Professor of the Department of System Programming at MIPT
Russian Federation
Candidate of Physics and Mathematics, Associate Professor, Leading Researcher of the Department of Applied Mathematics and Computer Science, ISP RAS, Associate Professor of the Department of System Programming at MIPT
Irina Valerievna Abramova
Lomonosov Moscow State University
Russian Federation
Master of Science, faculty of computational mathematics and cybernetics
Russian Federation
Master of Science, faculty of computational mathematics and cybernetics
Nikolay Pavlovich Varnovsky
Ivannikov Institute for System Programming of the Russian Academy of Sciences,
Moscow Institute of Physics and Technology (State University),
Lomonosov Moscow State University
Russian Federation
Senior Researcher, Department of Applied Mathematics and Informatics, ISP RAS; Senior Researcher, Institute of Information Security Problems, Moscow State University; Lecturer, Department of System Programming, MIPT
Russian Federation
Senior Researcher, Department of Applied Mathematics and Informatics, ISP RAS; Senior Researcher, Institute of Information Security Problems, Moscow State University; Lecturer, Department of System Programming, MIPT
Vladimir Anatolyevich Zakharov
Ivannikov Institute for System Programming of the Russian Academy of Sciences,
Moscow Institute of Physics and Technology (State University),
Lomonosov Moscow State University,
National Research University Higher School of Economics
Russian Federation
Doctor of Physics and Mathematics, Professor, Senior Researcher, Department of Applied Mathematics and Computer Science, ISP RAS; Professor, Department of Mathematical Cybernetics, Moscow State University; Leading Researcher, HSE Laboratory of Process-Oriented Information Systems; Associate Professor, Department of System Programming, MIPT
Russian Federation
Doctor of Physics and Mathematics, Professor, Senior Researcher, Department of Applied Mathematics and Computer Science, ISP RAS; Professor, Department of Mathematical Cybernetics, Moscow State University; Leading Researcher, HSE Laboratory of Process-Oriented Information Systems; Associate Professor, Department of System Programming, MIPT
References
1. Goldwasser S., Micali S. Probabilistic encryption and how to play mental poker keeping secret all partial information. In Proc. of the 14th ACM Symposium on the Theory of Computing, 1982, pp. 365–377.
2. Ostrovsky R. Efficient computation on oblivious RAMs. Proceedings of the 22nd Annual ACM Symposium on Theory of Computing, 1990, p. 514-523.
3. Ostrovsky R., Skeith III W.E. Private searching on streaming data. Lecture Notes in Computer Science, vol. 3621, 2005, p. 223-240.
4. Barak B., Goldreich O., Impagliazzo R., Rudich S., Sahai A., Vedhan S., Yang K. On the (Im)possibility of obfuscating programs. Journal of the ACM, vol, 59, no, 2, 2012, article no. 6
5. Collberg C., Thomborson C., Low D. A taxonomy of obfuscating transformations. Technical Report, no. 148, Department of Computer Science, University. of Auckland, 1997.
6. Collberg C, Thomborson C. Watermarking, tamper-proofing, and obfuscation - tools for software protection. IEEE Transactions on Software Engineering, vol. 28, no. 6, 2002, pp. 735 - 746.
7. D’Anna L., Matt B., Reisse A., Van Vleck T., Schwab S., LeBlanc P. Self-protecting mobile agents obfuscation report. Report 03-015, Network Associates Laboratories, 2003.
8. Diffie W., Hellman M. New directions in cryptography. IEEE Transactions on Information Theory, vol. 22, issue 6, 1976, pp. 644–654.
9. Sahai A., Waters B. How to Use Indistinguishability Obfuscation: Deniable Encryption, and More. In Proc. of the 46th Annual ACM Symposium on Theory of Computing, 2014, pp. 475–484.
10. Varnovsky N.P. A note on the concept of obfuscation. Trudy ISP RAN/Proc. ISP RAS, vol. 6, 2004, pp. 127-136.
11. Garg S., Gentry C., Halevi S., Raykova M., Sahai M., Waters B. Candidate Indistinguishability Obfuscation and Functional Encryption for all circuits. SIAM Journal on Computing, vol. 45, no. 3, 2016, pp. 882-929.
12. Hofheinz D., Malone-Lee J., Stam M. Obfuscation for cryptographic purposes. Lecture Notes in Computer Science, vol. 4392, 2007, pp. 214-232.
13. Hohenberger S., Rothblum G. N., Shelat A., Vaikuntanathan V. Securely obfuscating reencryption. Lecture Notes in Computer Science, vol 4392, 2007, pp. 233-252.
14. Pass К., Seth K., Telang S. Indistinguishability Obfuscation from Semantically-Secure Multilinear Encodings. Lecture Notes in Computer Science, vol. 8616, 2014, p. 500-517.
15. Goldwasser S., Rothblum G.N. On best possible obfuscation. Lecture Notes in Computer Science, vol 4392, 2007, pp. 194-213.
16. Hada S. Secure obfuscation for encrypted signatures. Lecture Notes in Computer Science, vol. 6110, 2010, pp. 92-112..
17. Lynn B., Prabhakaran M., Sahai A. Positive results and techniques for obfuscation. Lecture Notes in Computer Science, vol. 3027, 2004, pp. 20-39.
18. Varnovsky N.P., Zakharov V.A. On the possibility of provably secure obfuscating programs. Lecture Notes in Computer Science, vol. 2890, 2003, pp. 91-102.
19. Goldwasser S., Micali S. Probabilistic encryption and how to play mental poker keeping secret all partial information. In Proc. of the 14th ACM Symposium on the Theory of Computing, 1982, pp. 365–377.
20. Goldwasser S., Tauman Kalai Y. On the impossibility of obfuscation with auxiliary input. In Proc. of the 46th IEEE Symposium on Foundations of Computer Science, 2005, pp. 553-562..
21. Варновский Н.П., Захаров В.А., Кузюрин Н.Н., Шокуров А.В. Современное состояние исследований в области обфускации программ: определения стойкости обфускации. Труды ИСП РАН, том 26, вып. 3, 2014 г., стр. 167-198 / Varnovsky N.P., Zakharov V.A.., Kuzurin N.N., Shokurov A.V. The current state of art in program obfuscations:definitions of obfuscation security. . Trudy ISP RAN/Proc. ISP RAS, vol. 26, issue 3, 2014, pp. 167-198 (in Russian). DOI: 10.15514/ISPRAS-2014-26(3)-9.
22. Kuzurin N.N., Shokurov A.V., Varnovsky N.P., Zakharov V.A. On the concept of software obfuscation in computer security. Lecture Notes in Computer Science, vol.4779, 2008, pp. 281-298.
23. Min. Zao E, Yang Ceng. Homomorphic Encryption Technology for Cloud Computing. Procedia Computer Science, vol. 154, 2019, pp. 73-83.
24. Wee H. On obfuscating point functions. In Proc. of 37th ACM Symposium on Theory of Computing, 2005, p. 523-532.
25. Gentry C. Computing Arbitrary Functions of Encrypted Data. Communication of the ACM, vol. 53, no. 3, 2010. pp. 97-105.
26. Gentry C., Halevi S. Implementing Gentry’s Fully-Homomorphic Encryption Scheme. Lecture Notes in Computer Science, vol. 6632, 2011, pp. 129-148.
27. Rivest R.L., Adleman L., Dertouzos M.L. On data banks and privacy homomorphisms. In DeMillo R.A., ed., Foundations on Secure Computation, Academia Press, 1978, pp. 169-179.
28. Paillier P. Public-key cryptosystems based on composite degree residuosity classes. Lecture Notes in Computer Science, vol. 1592, 1999, pp. 223–238.
29. Boneh D., Goh Eu-Jin, Nissim K. Evaluating 2-DNF formulas on ciphertexts. Lecture Notes in Computer Science, vol. 3378, 2005, pp. 325-341.
30. Smart N., Verkauteren F. Fully homomorphic encryption with relatively small ciphertext and key size. Lecture Notes in Computer Science, vol. 6056, 2010, pp. 420-443.
31. Gentry C., Halevi S., Smart N. Homomorphic Evaluation of the AES Circuit. Lecture Notes in Computer Science, vol. 7417. 2012, pp. 850-867.
32. Gentry C., Halevi S., Smart N. Better Bootstrapping in Fully Homomorphic Encryption. Lecture Notes in Computer Science, vol. 7293, 2012, pp. 1-16.
33. Stehle D., Steinfeld R. Faster Fully Homomorphic Encryption. Lecture Notes in Computer Science, vol. 6477, 2010, pp. 377-394.
34. Brakerski Z., Vaikuntanathan V. Fully Homomorphic Encryption from Ring-LWE and Security for Key Dependent Messages. Lecture Notes in Computer Science, vol. 6841, 2011, pp. 505-524.
35. Brakerski Z. Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP. Lecture Notes in Computer Science, vol. 7417, 2012, pp. 868-886.
36. Brakerski Z., Gentry C., Vaikuntanathan V. (Leveled) Fully Homomorphic Encryption without Bootstrapping. ACM Transactions on Computation Theory, vol. 18, no. 3, 2014, article no. 13.
37. Brakerski Z., Gentry C., Halevi S. Packed Ciphertexts in LWE-based Homomorphic Encryption.. Lecture Notes in Computer Science, vol 7778, 2013, pp. 1-13.
38. Brakerski Z. When Homomorphism Becomes a Liability. Lecture Notes in Computer Science, vol. 7785, 2013, pp. 143-161.
39. Brakerski Z., Vaikuntanathan V. Lattice-Based FHE as Secure as PKE. In Proc. of the 5th Conference on Innovations in Theoretical Computer Science, 2014, pp.1-12.
40. Brakerski Z., Rothblum G.N. Virtual Black-Box Obfuscation for All Circuits via Generic Graded Encoding. Lecture Notes in Computer Science, vol. 8349, 2014, pp. 1-25.
41. Gentry C., Halevi S., Smart N. Fully Homomorphic Encryption with Polylog Overhead. Lecture Notes in Computer Science, vol. 7237, 2012, pp. 465-482.
42. Gentry C., Sahai A., Waters B. Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based. Lecture Notes in Computer Science, vol. 8042, 2013, pp. 75-92. DOI: 10.1007/978-3-642-40041-4_5.
43. Boneh B., Gentry C., Gorbunov S., Halevi S., Nikolaenko V., Segev G., Vaikuntanathan V., Vinayagamurthy D. Lecture Notes in Computer Science, vol. 8441, 2014, pp. 533-556.
44. Gentry C. Fully homomorphic encryption using ideal lattices. In Proc. of the 41st ACM Symposium on Theory of Computing, 2009, pp. 169-178.
45. Barak B., Garg S., Tauman Kalai Y., Paneth O., Sahai A. Protecting Obfuscation against Algebraic Attacks. Lecture Notes in Computer Science, vol. 8441, 2014, pp. 221–238.
46. Canetti R., Dwork C., Naor M., Ostrovsky R. Deniable encryption. Lecture Notes in Computer Science, vol. 1294, 1997, p. 90-104.
47. Van Dijk M., Juels A. On the impossibility of cryptography alone for privacy preserving cloud computing. On Proc. of the 5th USENIX Conference on Hot Topics in Security, 2010, pp. 1–8.
48. Варновский Н.П., Мартишин С.А., Храпченко М.В., Шокуров А.В. Методы пороговой криптографии для защиты облачных вычислений. Труды ИСП РАН, том 26, вып. 2, 2014, стр. 269-274 / Varnovskij N.P., Martishin S.А., Khrapchenko M.V., Shokurov А.V. A Threshold Cryptosystem in Secure Cloud Computations. Trudy ISP RAN/Proc. ISP RAS, vol. 26, issue 2, 2014, pp. 269-274 (in Russian). DOI: 10.15514/ISPRAS-2014-26(2)-12.
49. Варновский Н.П., Захаров В.А., Шокуров А.В. К вопросу о существовании доказуемо стойких систем облачных вычислений. Вестник Московского университета. Серия 15: Вычислительная математика и кибернетика, 2016, no. 2, стр. 32-37 / Varnovsky N.P., Zakharov V.A., Shokurov A.V. On the Existence of Provably Secure Cloud Computing Systems. Moscow University Computational Mathematics and Cybernetics, vol. 40, no. 2, 2016, pp. 83–88.
Review
For citations:
Shokurov A.V., Abramova I.V., Varnovsky N.P., Zakharov V.A. On the possibility of secure program obfuscation in some model of cloud computing. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2019;31(6):145-162. (In Russ.) https://doi.org/10.15514/ISPRAS-2019-31(6)-8
Email this article 