О нестойкости двух симметричных гомоморфных криптосистем, основанных на системе остаточных классов
Ключевые слова:
гомоморфное шифрование, облачные вычисления, криптоанализ, атака с известными открытыми текстами, система остаточных классовАннотация
Одной из наиболее актуальных задач, связанных с защитой облачных вычислений, является анализ криптостойкости гомоморфных шифров. Данная статья посвящена изучению вопроса о защищенности двух недавно предложенных гомоморфных криптосистем, которые, в связи с их высокой вычислительной эффективностью, могут быть использованы для шифрования данных на облачных серверах. Обе криптосистемы основаны на системах остаточных классов, что позволяет рассмотреть их с единых позиций. Именно использование систем остаточных классов делает применение этих криптосистем в реальных приложениях заманчивым с точки зрения эффективности по сравнению с другими гомоморфными шифрами, так как появляется возможность легко распараллелить вычисления. Однако их криптостойкость не была в достаточной мере изучена в литературе и нуждается в анализе.
Отметим, что ранее предшественниками была рассмотрена криптосистема похожая на один из шифров, криптостойкость которого исследуется. Была предложена идея адаптивной атаки по выбранным открытым текстам на эту конструкцию и дана оценка необходимого для раскрытия ключа количества пар <<открытый текст, шифртекст>>. Здесь проводится анализ этой атаки и показываем, что иногда она может работать некорректно. Также описывается более общий алгоритм атаки с известными открытыми текстами. Приводятся теоретические оценки вероятности успешного раскрытия секретного ключа с его помощью и практические оценки этой вероятности, полученные в ходе вычислительного эксперимента.
Защищенность второй криптосистемы не была исследована ранее в литературе. Изучена её стойкость к атаке с известными открытыми текстами. Проанализирована зависимость необходимого для взлома количества пар <<открытый текст, шифртекст>> от параметров криптосистемы и даны рекомендации, которые могут помочь улучшить криптостойкость.
Итог проведенного анализа заключается в том, что обе криптосистемы являются уязвимыми к атаке с известными открытыми текстами. Поэтому использовать их для шифрования конфиденциальных данных может быть небезопасно.
Основным алгоритмом, используемым в предложенных атаках на криптосистемы, является алгоритм поиска наибольшего общего делителя. Как следствие, время, необходимое для реализации атак, является полиномиальным от размера входных данных.
Литература
1. Rivest R.L., Adleman L., Dertouzos M.L. On data banks and privacy homomorphisms // Foundations of secure computation. 1978. vol. 32. no. 4. pp. 169–178.
2. Brickell E.F., Yacobi Y. On privacy homomorphisms // Proceedings of Advances in Cryptology – EUROCRYPT’87. 1988. pp. 117–125.
3. Goldwasser G., Micali S. Probabilistic encryption & how to play mental poker keeping secret all partial information // Proceedings of the fourteenth annual ACM symposium on Theory of computing. 1982. pp. 365–377.
4. Paillier P. Public-key cryptosystems based on composite degree residuosity classes // Advances in cryptology – EUROCRYPT’99. 1999. pp. 223–238.
5. Rivest R.L., Shamir A., Adleman L. A method for obtaining digital signatures and public-key cryptosystems // Communications of the ACM. 1978. vol. 21. no. 2. pp. 120–126.
6. Gentry C. A fully homomorphic encryption scheme // PhD thesis. Stanford University. 2009. 209 p.
7. Cheon J.H. et al. Batch fully homomorphic encryption over the integers // Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2013. pp. 315–335.
8. Brakerski Z., Gentry C., Vaikuntanathan V. (Leveled) fully homomorphic encryption without bootstrapping // Proceedings of the 3rd Innovations in Theoretical Computer Science Conference (ACM). 2012. pp. 309–325.
9. Brakerski Z. Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP // Advances in cryptology – crypto 2012. 2012. pp. 868–886.
10. Chillotti I., Gama N., Georgieva M., Izabachene M. Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds // 22nd International Conference on the Theory and Application of Cryptology and Information Security. 2016. pp. 3–33.
11. Cheon J.H., Han K., Kim D. Faster Bootstrapping of FHE over the Integers // IACR Cryptology ePrint Archive. 2017. pp. 79.
12. Micciancio D., Sorrell J. Ring packing and amortized FHEW bootstrapping // IACR Cryptology ePrint Archive. 2018. 25 p.
13. Brakerski Z. Quantum FHE (Almost) As Secure As Classical // Annual International Cryptology Conference. 2018. pp. 67–95.
14. Бабенко Л.К., Буртыка Ф.Б., Макаревич О.Б., Трепачева А.В. Полностью гомоморфное шифрование (обзор) // Вопросы защиты информации. 2015. № 3. С. 3–25.
15. Kipnis A., Hibshoosh E. Efficient methods for practical fully homomorphic symmetrickey encrypton, randomization and verification // IACR Cryptology ePrint Archive. 2012. pp. 637.
16. Xiao L., Bastani O., Yen I.L. An efficient homomorphic encryption protocol for multi-user systems // IACR Cryptology ePrint Archive. 2012. pp. 193.
17. Sharma I. Fully homomorphic encryption scheme with symmetric keys // Master of Technology in Department of Computer Science & Engineering (with specialization in Computer Engineering). 2013. 64 p.
18. Yagisawa M. Fully Homomorphic Encryption without bootstrapping // IACR Cryptology ePrint Archive. 2015. pp. 474.
19. Yagisawa M. Improved Fully Homomorphic Encryption with Composite Number Modulus // IACR Cryptology ePrint Archive. 2016. pp. 50.
20. Ростовцев А.Г., Богданов А.Г., Михайлов М.Ю. Метод безопасного вычисления полинома в недоверенной среде с помощью гомоморфизмов колец // Проблемы информационной безопасности. Компьютерные системы. 2011. № 2. С. 76–85.
21. Zhirov A.O., Zhirova O.V., Krendelev S.F. Practical fully homomorphic encryption over polynomial quotient rings // 2013 World Congress on Internet Security (WorldCIS). 2013. pp. 70–75.
22. Жиров А.О., Жирова О.В., Кренделев С.Ф. Безопасные облачные вычисления с помощю гомоморфной криптографии // Безопасность информационных технологий. 2013. Т. 20. № 1. С. 6–12.
23. Dasgupta S., Pal S.K. Design of a polynomial ring based symmetric homomorphic encryption scheme // Perspectives in Science. 2016. vol. 8. pp. 692–695.
24. Domingo-Ferrer J. A provably secure additive and multiplicative privacy homomorphism // International Conference on Information Security. 2002. pp. 471–483.
25. Domingo-Ferrer J. A new privacy homomorphism and applications // Information Processing Letters. 1996. vol. 60. no. 5. pp. 277–282
26. Gomathisankaran M., Tyagi A., Namuduri K. HORNS: A homomorphic encryption scheme for Cloud Computing using Residue Number System // 2011 45th Annual Conference Information Sciences and Systems (CISS). 2011. pp. 1–5.
27. Вишневский А.К., Князев В.В. Комплексное применение гомоморфных криптографических преобразований для решения систем линейных алгебраических уравнений // Наукоемкие технологии. 2015. Т. 16. № 11. С. 28–35.
28. Бабенко М.Г., Кучеров Н.Н., Червяков Н.И. Разработка системы гомоморфного шифрования информации на основе полиномиальной системы остаточных классов // Сибирские электронные математические известия. Труды VI международной молодежной школы-конференции «Теория и численные методы решения обратных и некорректных задач». 2015. Т. 12 С. 33–41. URL: http://semr.math.nsc.ru/v12/c1-283.pdf (дата обращения: 02.12.2018).
29. Vizar D., Vaudenay S. Cryptanalysis of chosen symmetric homomorphic schemes // Studia Scientiarum Mathematicarum Hungarica. 2015. vol. 52. no. 2. pp. 288–306.
30. Tsaban B., Lifshitz N. Cryptanalysis of the MORE symmetric key fully homomorphic encryption scheme // Journal of Mathematical Cryptology. 2015. vol. 9. no. 2. pp. 75–78.
31. Трепачева А.В. Криптоанализ симметричных полностью гомоморфных линейных криптосистем на основе задачи факторизации чисел // Известия Южного федерального университета. Технические науки. 2015. № 5(166). C. 89–100.
32. El-Yahyaoui A., Elkettani M.D. Cryptanalysis of fully homomorphic encryption schemes // International Journal of Computer Science and Information Security. 2016. vol. 14. no. 5. pp. 677.
33. Cheon J.H., Kim W.H., Nam H.S. Known-plaintext cryptanalysis of the Domingo-Ferrer algebraic privacy homomorphism scheme // Information Processing Letters. 2006. vol. 97. no. 3. pp. 118–123.
34. Wagner D. Cryptanalysis of an algebraic privacy homomorphism // International Conference on Information Security. 2003. pp. 234–239.
35. Trepacheva A.V. Improved known plaintexts attack on Domingo-Ferrer homomorphic cryptosystem1 // Труды Института системного программирования РАН. 2014. Т. 26. № 5. С. 83–98.
36. Трепачева А.В. О криптоанализе одной полностью гомоморфной криптосистемы на основе задачи факторизации // Безопасность информационных технологий. 2015. Т. 22. № 2. С. 19–25.
37. Trepacheva A.V. Known plaintext attack on a fully homomorphic cryptosystem based on factorization // Proceedings of 4th Workshop on Current Trends in Cryptology (CTCrypt’2015). 2015. pp. 205–215.
38. Babenko L., Trepacheva A. Known plaintexts attack on polynomial based homomorphic encryption // Proceedings of the 7th International Conference on Security of Information and Networks. ACM. 2014. pp. 157.
39. Трепачева А.В. Криптоанализ полностью гомоморфных криптосистем, основанных на алгебре октонионов // Обозрение прикладной и промышленной математики. 2016. Т. 23. Вып. 4. 2 c.
40. Wang Y. Notes on Two Fully Homomorphic Encryption Schemes Without Bootstrapping // IACR Cryptology ePrint Archive. 2015. pp. 519.
41. Wang Y. Octonion Algebra and Noise-Free Fully Homomorphic Encryption (FHE) Schemes // IACR Cryptology ePrint Archive. 2016. pp. 68.
42. Babenko L.K., Trepacheva A.V. Cryptanalysis of factoring-based fully homomorphic encryption // Proceedings of the 8th International Conference on Security of Information and Networks. 2015. pp. 80–83.
43. Трепачева А.В. Атака по шифртекстам на одну линейную полностью гомоморфную криптосистему // Прикладная дискретная математика. Приложение. 2015. № 8. С. 75–78.
44. Трепачева А.В. О соотношениях между атаками на симметричные шифры, гомоморфные над кольцом вычетов // Безопасность информационных технологий. 2017. № 2. С. 82–91.
45. Babenko M. et al. Security analysis of homomorphic encryption scheme for cloud computing: Known-plaintext attack // 2018 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (EIConRus). 2018. pp. 270–274.
46. Бухштаб А.А. Теория чисел // M.: Просвещение. 1966. 384 c.
47. Nymann J.E. On the probability that k positive integers are relatively prime // Journal of Number Theory. 1972. vol 4. no. 5. pp. 469–473.
48. Benjamin A.T., Bennett C.D. The probability of relatively prime polynomials // Mathematics Magazine. 2007. vol. 80. no. 3. pp. 196–202.
49. Goldreich O. Foundations of Cryptography – Basic Tools // Cambridge University press. 2009. 393 p.
50. Weenink T. Deterministic primality testing // Technische Universiteit Eindhoven. 2015.
51. Knuth D.E. The Art of Computer Programming – Sorting and Searching // Addison-Wesley Professional. 1998. 800 p.
52. Ахо А. Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов // М.: Мир. 1979. 536 c.
53. Реализация криптосистемы Вишневского и Князева и атаки на нее. URL: https://github.com/alina1989malina/CryptanalysisVishnevskyKnyazev (дата обращения: 02.12.2018).
54. Реализация криптосистемы Бабенко, Кучерова и Червякова и атаки на нее. URL: https://github.com/alina1989malina/CryptanalysisBabenkoKucherovChervjakov (дата обращения: 02.12.2018).
2. Brickell E.F., Yacobi Y. On privacy homomorphisms // Proceedings of Advances in Cryptology – EUROCRYPT’87. 1988. pp. 117–125.
3. Goldwasser G., Micali S. Probabilistic encryption & how to play mental poker keeping secret all partial information // Proceedings of the fourteenth annual ACM symposium on Theory of computing. 1982. pp. 365–377.
4. Paillier P. Public-key cryptosystems based on composite degree residuosity classes // Advances in cryptology – EUROCRYPT’99. 1999. pp. 223–238.
5. Rivest R.L., Shamir A., Adleman L. A method for obtaining digital signatures and public-key cryptosystems // Communications of the ACM. 1978. vol. 21. no. 2. pp. 120–126.
6. Gentry C. A fully homomorphic encryption scheme // PhD thesis. Stanford University. 2009. 209 p.
7. Cheon J.H. et al. Batch fully homomorphic encryption over the integers // Annual International Conference on the Theory and Applications of Cryptographic Techniques. 2013. pp. 315–335.
8. Brakerski Z., Gentry C., Vaikuntanathan V. (Leveled) fully homomorphic encryption without bootstrapping // Proceedings of the 3rd Innovations in Theoretical Computer Science Conference (ACM). 2012. pp. 309–325.
9. Brakerski Z. Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP // Advances in cryptology – crypto 2012. 2012. pp. 868–886.
10. Chillotti I., Gama N., Georgieva M., Izabachene M. Faster fully homomorphic encryption: Bootstrapping in less than 0.1 seconds // 22nd International Conference on the Theory and Application of Cryptology and Information Security. 2016. pp. 3–33.
11. Cheon J.H., Han K., Kim D. Faster Bootstrapping of FHE over the Integers // IACR Cryptology ePrint Archive. 2017. pp. 79.
12. Micciancio D., Sorrell J. Ring packing and amortized FHEW bootstrapping // IACR Cryptology ePrint Archive. 2018. 25 p.
13. Brakerski Z. Quantum FHE (Almost) As Secure As Classical // Annual International Cryptology Conference. 2018. pp. 67–95.
14. Бабенко Л.К., Буртыка Ф.Б., Макаревич О.Б., Трепачева А.В. Полностью гомоморфное шифрование (обзор) // Вопросы защиты информации. 2015. № 3. С. 3–25.
15. Kipnis A., Hibshoosh E. Efficient methods for practical fully homomorphic symmetrickey encrypton, randomization and verification // IACR Cryptology ePrint Archive. 2012. pp. 637.
16. Xiao L., Bastani O., Yen I.L. An efficient homomorphic encryption protocol for multi-user systems // IACR Cryptology ePrint Archive. 2012. pp. 193.
17. Sharma I. Fully homomorphic encryption scheme with symmetric keys // Master of Technology in Department of Computer Science & Engineering (with specialization in Computer Engineering). 2013. 64 p.
18. Yagisawa M. Fully Homomorphic Encryption without bootstrapping // IACR Cryptology ePrint Archive. 2015. pp. 474.
19. Yagisawa M. Improved Fully Homomorphic Encryption with Composite Number Modulus // IACR Cryptology ePrint Archive. 2016. pp. 50.
20. Ростовцев А.Г., Богданов А.Г., Михайлов М.Ю. Метод безопасного вычисления полинома в недоверенной среде с помощью гомоморфизмов колец // Проблемы информационной безопасности. Компьютерные системы. 2011. № 2. С. 76–85.
21. Zhirov A.O., Zhirova O.V., Krendelev S.F. Practical fully homomorphic encryption over polynomial quotient rings // 2013 World Congress on Internet Security (WorldCIS). 2013. pp. 70–75.
22. Жиров А.О., Жирова О.В., Кренделев С.Ф. Безопасные облачные вычисления с помощю гомоморфной криптографии // Безопасность информационных технологий. 2013. Т. 20. № 1. С. 6–12.
23. Dasgupta S., Pal S.K. Design of a polynomial ring based symmetric homomorphic encryption scheme // Perspectives in Science. 2016. vol. 8. pp. 692–695.
24. Domingo-Ferrer J. A provably secure additive and multiplicative privacy homomorphism // International Conference on Information Security. 2002. pp. 471–483.
25. Domingo-Ferrer J. A new privacy homomorphism and applications // Information Processing Letters. 1996. vol. 60. no. 5. pp. 277–282
26. Gomathisankaran M., Tyagi A., Namuduri K. HORNS: A homomorphic encryption scheme for Cloud Computing using Residue Number System // 2011 45th Annual Conference Information Sciences and Systems (CISS). 2011. pp. 1–5.
27. Вишневский А.К., Князев В.В. Комплексное применение гомоморфных криптографических преобразований для решения систем линейных алгебраических уравнений // Наукоемкие технологии. 2015. Т. 16. № 11. С. 28–35.
28. Бабенко М.Г., Кучеров Н.Н., Червяков Н.И. Разработка системы гомоморфного шифрования информации на основе полиномиальной системы остаточных классов // Сибирские электронные математические известия. Труды VI международной молодежной школы-конференции «Теория и численные методы решения обратных и некорректных задач». 2015. Т. 12 С. 33–41. URL: http://semr.math.nsc.ru/v12/c1-283.pdf (дата обращения: 02.12.2018).
29. Vizar D., Vaudenay S. Cryptanalysis of chosen symmetric homomorphic schemes // Studia Scientiarum Mathematicarum Hungarica. 2015. vol. 52. no. 2. pp. 288–306.
30. Tsaban B., Lifshitz N. Cryptanalysis of the MORE symmetric key fully homomorphic encryption scheme // Journal of Mathematical Cryptology. 2015. vol. 9. no. 2. pp. 75–78.
31. Трепачева А.В. Криптоанализ симметричных полностью гомоморфных линейных криптосистем на основе задачи факторизации чисел // Известия Южного федерального университета. Технические науки. 2015. № 5(166). C. 89–100.
32. El-Yahyaoui A., Elkettani M.D. Cryptanalysis of fully homomorphic encryption schemes // International Journal of Computer Science and Information Security. 2016. vol. 14. no. 5. pp. 677.
33. Cheon J.H., Kim W.H., Nam H.S. Known-plaintext cryptanalysis of the Domingo-Ferrer algebraic privacy homomorphism scheme // Information Processing Letters. 2006. vol. 97. no. 3. pp. 118–123.
34. Wagner D. Cryptanalysis of an algebraic privacy homomorphism // International Conference on Information Security. 2003. pp. 234–239.
35. Trepacheva A.V. Improved known plaintexts attack on Domingo-Ferrer homomorphic cryptosystem1 // Труды Института системного программирования РАН. 2014. Т. 26. № 5. С. 83–98.
36. Трепачева А.В. О криптоанализе одной полностью гомоморфной криптосистемы на основе задачи факторизации // Безопасность информационных технологий. 2015. Т. 22. № 2. С. 19–25.
37. Trepacheva A.V. Known plaintext attack on a fully homomorphic cryptosystem based on factorization // Proceedings of 4th Workshop on Current Trends in Cryptology (CTCrypt’2015). 2015. pp. 205–215.
38. Babenko L., Trepacheva A. Known plaintexts attack on polynomial based homomorphic encryption // Proceedings of the 7th International Conference on Security of Information and Networks. ACM. 2014. pp. 157.
39. Трепачева А.В. Криптоанализ полностью гомоморфных криптосистем, основанных на алгебре октонионов // Обозрение прикладной и промышленной математики. 2016. Т. 23. Вып. 4. 2 c.
40. Wang Y. Notes on Two Fully Homomorphic Encryption Schemes Without Bootstrapping // IACR Cryptology ePrint Archive. 2015. pp. 519.
41. Wang Y. Octonion Algebra and Noise-Free Fully Homomorphic Encryption (FHE) Schemes // IACR Cryptology ePrint Archive. 2016. pp. 68.
42. Babenko L.K., Trepacheva A.V. Cryptanalysis of factoring-based fully homomorphic encryption // Proceedings of the 8th International Conference on Security of Information and Networks. 2015. pp. 80–83.
43. Трепачева А.В. Атака по шифртекстам на одну линейную полностью гомоморфную криптосистему // Прикладная дискретная математика. Приложение. 2015. № 8. С. 75–78.
44. Трепачева А.В. О соотношениях между атаками на симметричные шифры, гомоморфные над кольцом вычетов // Безопасность информационных технологий. 2017. № 2. С. 82–91.
45. Babenko M. et al. Security analysis of homomorphic encryption scheme for cloud computing: Known-plaintext attack // 2018 IEEE Conference of Russian Young Researchers in Electrical and Electronic Engineering (EIConRus). 2018. pp. 270–274.
46. Бухштаб А.А. Теория чисел // M.: Просвещение. 1966. 384 c.
47. Nymann J.E. On the probability that k positive integers are relatively prime // Journal of Number Theory. 1972. vol 4. no. 5. pp. 469–473.
48. Benjamin A.T., Bennett C.D. The probability of relatively prime polynomials // Mathematics Magazine. 2007. vol. 80. no. 3. pp. 196–202.
49. Goldreich O. Foundations of Cryptography – Basic Tools // Cambridge University press. 2009. 393 p.
50. Weenink T. Deterministic primality testing // Technische Universiteit Eindhoven. 2015.
51. Knuth D.E. The Art of Computer Programming – Sorting and Searching // Addison-Wesley Professional. 1998. 800 p.
52. Ахо А. Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов // М.: Мир. 1979. 536 c.
53. Реализация криптосистемы Вишневского и Князева и атаки на нее. URL: https://github.com/alina1989malina/CryptanalysisVishnevskyKnyazev (дата обращения: 02.12.2018).
54. Реализация криптосистемы Бабенко, Кучерова и Червякова и атаки на нее. URL: https://github.com/alina1989malina/CryptanalysisBabenkoKucherovChervjakov (дата обращения: 02.12.2018).
Опубликован
2019-02-15
Как цитировать
Бабенко, Л. К., & Трепачева, А. В. (2019). О нестойкости двух симметричных гомоморфных криптосистем, основанных на системе остаточных классов. Труды СПИИРАН, 18(1), 230-262. https://doi.org/10.15622/sp.18.1.230-262
Раздел
Информационная безопасность
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями:
Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале.
Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале.
Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).
