О соотношениях между атаками на симметричные шифры, гомоморфные над кольцом вычетов

Aлина B. Трепачева

Аннотация


Работа посвящена изучению криптостойкости симметричных гомоморфных шифров над кольцами вычетов. Основной задачей является выяснить, возможно ли установить эквивалентность между атакой только по шифртекстам (АТШ) и атакой по известным открытым текстам (АИОТ) для таких шифров. Для этого вводится понятие сводимости между атаками и дается достаточное условие сводимости от АТШ к АИОТ. Основная идея заключается в том, что для доказательства сводимости от АТШ к АИОТ необходимо найти функцию над кольцом вычетов, которая является эффективно вычислимой и имеет небольшой размер образа по сравнению с размером всего кольца вычетов. Исследование наличия сводимости интересно тем, что оно может позволить лучше понять уровень криптостойкости существующих симметричных гомоморфных криптосистем (ГК). Поскольку для большинства из них в литературе уже установлена уязвимость к АИОТ, то доказательство существования сводимости может показать, что эти криптосистемы нестойки даже к АТШ, а следовательно, совсем нестойки и непригодны для применения. Приводится пример сводимости АТШ к АИОТ для случая, когда кольцо вычетов является простым полем. На основе этого примера описывается эффективная АТШ на одну симметричную ГК в случае кольца вычетов небольшого размера. Также отдельно рассматривается случай, когда кольцо вычетов для ГК строится по трудно- факторизуемому модулю п. Для таких п на данный момент не известен эффективный алгоритм построения эффективно вычислимых функций с «небольшим» образом. Ввиду этого дальнейшая работа по криптоанализу существующих симметричных ГК будет направлена на изучение свойств функций над кольцами вычетов по труднофакторизуемым модулям.


Ключевые слова


гомоморфное шифрование над кольцом вычетов; полностью гомоморфное шифрование; задача RSA; задача факторизации чисел; атака только по шифртекстам; атака по известным открытым текстам

Полный текст:

PDF

Литература


1. Бабенко Л.К., Буртыка Ф.Б., Макаревич О.Б., Трепачева А.В. Полностью гомоморфное шифрование (обзор) // Вопросы защиты информации. 2016. № 3. С. 3-25.
2. Gentry, Craig. Fully homomorphic encryption using ideal lattices.STOC.Vol. 9.No. 2009. 2009.
3. Vaikuntanathan V. Computing blindfolded: New developments in fully homomorphic encryption. // Proceedings of IEEE 52nd Annual Symposium on Foundations of Computer Science (FOCS), 2011.
4. Жиров A.O., Жирова О.В., Кренделев С.Ф. Безопасные облачные вычисления с помощью гомоморфной криптографии // Безопасность информационных технологий. 2013. № 1. С. 6-12.
5. Zhirov A., Zhirova О, Krendelev S. Practical fully homomorphic encryption over polynomial quotient ring // Proceedings of World congress on internet security (WorldCIS), IEEE. 2013, C. 70-75. DOI: 10.1109/WorldCIS.2013.6751020.
6. Ростовцев А., Богданов А., Михайлов M. Метод безопасного вычисления полинома в недоверенной среде с помощью гомоморфизмов колец // Проблемы информационной безопасности. Компьютерные системы. 2011. № 2. С. 76-85.
7. Yagisawa М. Fully Homomorphic Encryption with Composite Number Modulus //IACR Cryptology ePrint Archive. 2015. № 1040. URL: https://eprint.iacr.org/2015/1040.pdf (дата обращения: 25.01.2017).
8. Kipnis A., Hibshoosh E. Efficient Methods for Practical Fully Homomorphic Symmetric-key Encrypton, Randomization and Verification //IACR Cryptology ePrint Archive. 2012. № 637. URL: https://eprint.iacr.org/2012/637.pdf (дата обращения: 25.01.2017).
9. Xiao L., Bastani O., Yen I. L. An Efficient Homomorphic Encryption Protocol for Multi-User Systems //IACR Cryptology ePrint Archive. 2012. №. 193 URL: https://eprint.iacr.org/2012/193.pdf (дата обращения: 22.01.2017).
10. Gupta С. P., Sharma I. Department of Computer Sciences and Engineering Rajasthan Technical University, Kota, India //Network of the Future (NOF), 2013 Fourth International Conference on the. - IEEE, 2013. C. 1-4.
11. Gupta C.P. Fully Homomorphic Encryption Scheme with Symmetric Keys: - Department of Computer Science & Engineering University College of Engineering, Rajasthan Technical University, Kota, 2013.
12. Domingo-Ferrer J. A new privacy homomorphism and applications // Information Processing Letters. 1996.Vol. 60. No. 5. C. 277-282.
13. Chan A.C.F. Symmetric-key homomorphic encryption for encrypted data processing //Communications, 2009. ICC09.IEEE International Conference on. IEEE, 2009. C. 1-5.
14. Gavin G. A general framework for building noise-free homomorphic cryptosystems // IACR Cryptology ePrint Archive. 2015. № 821. URL: https://eprint.iacr.org/2015/821.pdf (дата обращения: 25.01.2017).
15. Domingo-Ferrer J. A provably secure additive and multiplicative privacy homomorphism // Information Security. 2002. C. 471-483.
16. Rivest R.L., Kaliski Jr.B. RSA problem //Encyclopedia of cryptography and security. Springer US, 2011. C. 1065-1069.
17. Shatilov K., Boiko V., Krendelev S., Anisutina D., Sumaneev A. Solution for secure private data storage in a cloud // Proceedings of Federated Conference on Computer Science and Information Systems (FedCSIS), IEEE. 2014. C. 885-889. DOI: 10.15439/2014F43.
18. Ertaul L., Yang J. H. Implementation of Domingo-Ferrer’s a new privacy homomorphism (df a new ph) in securing wireless sensor networks (wsn). // Security and Management. Citeseer. 2008. C. 498-504.
19. Jariwala V., Jinwala D. Evaluating homomorphic encryption algorithms for privacy in wireless sensor networks // International Journal of Advancements in Computing Technology. 2011. Vol. 3, No. 6.
20. Трепачева А.В. О криптоанализе одной полностью гомоморфной криптосистемы на основе задачи факторизации // Безопасность информационных технологий. 2015. № 4. С. 19-25.
21. Трепачева А.В. Улучшенная атака по известным открытым текстам на гомоморфную криптосистему Доминго- Феррера // Труды Института системного программирования Российской академии наук. 2014. Т. 25. Вып. 5. С. 83-98. DOI: 10.15514/ISPRAS-2014-26(5)-4.
22. Трепачева А.В. Криптоанализ шифров, основанных на гомоморфизмах полиномиальных колец // ИзвестияЮж- ногофедеральногоуниверситета. Технические науки. 2014. Т. 157. №. 8. С. 96-107.
23. Trepacheva A., Babenko L. Known plaintexts attack on polynomial based homomorphic encryption //Proceedings of the 7th International Conference on Security of Information and Networks. ACM. 2014. C. 157.
24. Трепачева А.В. Криптоанализ симметричных полностью гомоморфных линейных криптосистем на основе задачи факторизации чисел // Известия Южного федерального университета. Технические науки. 2015. Т. 16. № 5.
25. Трепачева А.В. Криптоанализ полностью гомоморфных криптосистем, основанных на алгебре октонионов // Обозрение прикладной и промышленной математики. 2016.
26. Vizar D., Vaudenay S. Analysis of Chosen Symmetric Homomorphic Schemes //Central European Crypto Conference. 2014. № EPFL-CONF-198992.
27. Tsaban B., Lifshitz N. Cryptanalysis of the MORE symmetric key fully homomorphic encryption scheme //Journal of Mathematical Cryptology. 2014.
28. Cheon J.H., Kim W.-H., and 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.
29. Wagne. Cryptanalysis of an algebraic privacy homomorphism // in Information Security. Springer. 2003. Pp. 234-239.
30. Babenko L.K., Trepacheva A.V. Analiz zashhishhennosti odnoj kriptograficheskoj sistemy dlja zashhity konfiden- cial'nosti dannyh v oblachnyh vychislenijah // Bezopasnosf informacionnyhtehnologij. 2016. № 1. S. 11-15.
31. Gordon D.M. A survey of fast exponentiation methods //Journal of algorithms. 1998. V. 27. №. 1. S. 129-146.
32. Goldreich, Oded. Foundations of Cryptography-A Primer. Foundations and Trends® in Theoretical Computer Science 1.1 (2005): 1-116.
33. Gari M., and Dzhonson D. Vichisliternie mashini I trudnoreshaemye zadachi. M.: Mir. 1982.
34. Altmann K., Jager T., Rupp A. On black-box ring extraction and integer factorization // International Colloquium on Automata, Languages, and Programming. 2008. S. 437-448. DOI: 10.1007/978-3-540-70583-3_36.




DOI: http://dx.doi.org/10.26583/bit.2017.2.09

Ссылки

  • На текущий момент ссылки отсутствуют.


Лицензия Creative Commons
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.