О возможности стойкой обфускации программ в одной модели облачных вычислений
Александр Владимирович Шокуров,
Ирина Валерьевна Абрамова,
Николай Павлович Варновский,
Владимир Анатолиевич Захаров https://doi.org/10.15514/ISPRAS-2019-31(6)-8
Аннотация
В данной статье проведено исследование возможности применения одной модели облачных вычислений, использующей криптосерверы, для обфускации программ. Ранее эта модель облачных вычислений была предложена нами в связи с изучением задачи обеспечения информационной безопасности мультиклиентских распределенных вычислений над зашифрованными данными. На основе этой модели нами предложен новый подход, предусматривающий использование пороговых гомоморфных криптосистем для обфускации программ. Основным результатом статьи являются новое определение стойкости обфускации программ в модели облачных вычислений и теорема, доказывающая криптографическую стойкость предложенного алгоритма обфускации программ в предположении существования криптографически стойких пороговых гомоморфных систем шифрования.
При поддержке: Исследования, результаты которых представлены в этой статье, выполнены при поддержке Российского Фонда Фундаментальных Исследований (проект 19-01-00702).
Об авторах
Александр Владимирович Шокуров
Институт системного программирования им. В.П. Иванникова РАН,
Московский физико-технический институт
Россия
Кандидат физико-математических наук, доцент, ведущий научный сотрудник отдела прикладной математики и информатики ИСП РАН, доцент кафедры системного программирования МФТИ
Россия
Кандидат физико-математических наук, доцент, ведущий научный сотрудник отдела прикладной математики и информатики ИСП РАН, доцент кафедры системного программирования МФТИ
Ирина Валерьевна Абрамова
Московский государственный университет имени М.В. Ломоносова
Россия
Студентка магистратуры факультета вычислительной математики и кибернетики
Россия
Студентка магистратуры факультета вычислительной математики и кибернетики
Николай Павлович Варновский
Институт системного программирования им. В.П. Иванникова РАН,
Московский физико-технический институт,
Московский государственный университет имени М.В. Ломоносова
Россия
Россия
Владимир Анатолиевич Захаров
Институт системного программирования им. В.П. Иванникова РАН,
Московский физико-технический институт,
Московский государственный университет имени М.В. Ломоносова,
НИУ Высшая школа экономики
Россия
Доктор физико-математических наук, профессор, старший научный сотрудник отдела прикладной математики и информатики ИСП РАН; профессор кафедры математической кибернетики МГУ; ведущий научный сотрудник лаборатории процессно-ориентированных информационных ВШЭ; доцент кафедры системного программирования МФТИ
Россия
Доктор физико-математических наук, профессор, старший научный сотрудник отдела прикладной математики и информатики ИСП РАН; профессор кафедры математической кибернетики МГУ; ведущий научный сотрудник лаборатории процессно-ориентированных информационных ВШЭ; доцент кафедры системного программирования МФТИ
Список литературы
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.
Рецензия
Для цитирования:
Шокуров А.В., Абрамова И.В., Варновский Н.П., Захаров В.А. О возможности стойкой обфускации программ в одной модели облачных вычислений. Труды Института системного программирования РАН. 2019;31(6):145-162. https://doi.org/10.15514/ISPRAS-2019-31(6)-8
For citation:
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
Послать статью по эл. почте 