Статья

Название статьи КРИПТОАНАЛИЗ СИММЕТРИЧНЫХ ПОЛНОСТЬЮ ГОМОМОРФНЫХ ЛИНЕЙНЫХ КРИПТОСИСТЕМ НА ОСНОВЕ ЗАДАЧИ ФАКТОРИЗАЦИИ ЧИСЕЛ
Автор А.В. Трепачева
Рубрика РАЗДЕЛ III. КРИПТОГРАФИЧЕСКАЯ ЗАЩИТА ИНФОРМАЦИИ
Месяц, год 05, 2015
Индекс УДК 519.7: 004: 681.5
DOI
Аннотация Рассматриваются полностью гомоморфные схемы шифрования, криптостойкость которых их авторы обосновывают с использованием сложности решения задачи факторизации больших чисел. В частности, проводится анализ стойкости криптосистем, в которых шифртексты представляют собой матрицы над кольцом вычетов по составному модулю, трудному для факторизации, а шифрование и расшифрование являются преобразованиями подобия. Проводится подробный анализ основных свойств шифртекстов, производимых алгоритмами шифрования этих криптосистем. На основе этого анализа выделяются основные уязвимости, которым они подвержены. Наиболее подробно анализируется криптостойкость двух недавно предложенных криптосистем указанного вида против атаки по известным открытым текстам. Рассматривается ранее описанная в литературе стратегия атаки на одну из этих криптосистем, основанная на решении системы линейных уравнений по составному модулю. Основным результатом настоящей работы является то, что по сравнению с предшественниками даются строгие теоретические оценки вероятности раскрытия секретного ключа при использовании этой стратегии. А также приводятся практические оценки вероятности раскрытия ключа, которые хорошо согласуются с теоретическими предсказаниями. Проведенный анализ показал, что первая из рассмотренных криптосистем является нестойкой к рассмотренной атаке по известным открытым текстам. Однако для раскрытия ключа с вероятностью ≈1 необходимо иметь количество пар (открытый текст, шифртекст), зависящее полилогарифмически от числа сомножителей, образующих составное число, по модулю которого ведутся вычисления. При числе пар меньшем данной величины криптосистема является защищенной, что частично соответствует оценкам защищенности, данным её авторами. Для взлома же второй криптосистемы нужно гораздо меньшее количество пар и уровень её криптостойкости совсем не соответствует заявленному.

Скачать в PDF

Ключевые слова Полностью гомоморфная криптосистема; атака по известным открытым текстам; защищённые облачные вычисления; задача факторизация чисел.
Библиографический список 1. Armbrust M. et al. A view of cloud computing // Communications of the ACM. – 2010. – Vol. 53, №. 4. – P. 50-58.
2. Guellier A. Can Homomorphic Cryptography ensure Privacy?: diss. – Inria; IRISA; Supélec Rennes, équipe Cidre; Université de Rennes 1, 2014.
3. Gentry C. A fully homomorphic encryption scheme: diss. – Stanford University, 2009.
4. Burtyka P., Makarevich O. Symmetric Fully Homomorphic Encryption Using Decidable Matrix Equations // Proceedings of the 7th International Conference on Security of Information and Networks. – ACM, 2014. – P. 186.
5. Nuida K. A Simple Framework for Noise-Free Construction of Fully Homomorphic Encryption from a Special Class of Non-Commutative Groups // IACR Cryptology ePrint Archive. – 2014. – Vol. 2014. – P. 97.
6. Tamayo-Rios M. Method for fully homomorphic encryption using multivariate cryptography: заяв. пат. 13/915,500 США. – 2013.
7. Rostovtsev A., Bogdanov A., Mikhaylov M. Secure evaluation of polynomial using privacy ring homomorphisms // IACR Cryptology ePrint Archive. – 2011. – Vol. 2011. – P. 24.
8. Zhirov A., Zhirova O., Krendelev S. F. Practical fully homomorphic encryption over polynomial quotient rings // Internet Security (WorldCIS), 2013 World Congress on. – IEEE, 2013. – P. 70-75.
9. Kipnis A., Hibshoosh E. Efficient Methods for Practical Fully Homomorphic Symmetric-key Encrypton, Randomization and Verification // IACR Cryptology ePrint Archive. – 2012. – №. 637.
10. Chan A.C.F. Symmetric-key homomorphic encryption for encrypted data processing // Communications, 2009. ICC'09. IEEE International Conference on. – IEEE, 2009. – P. 1-5.
11. Xiao L., Bastani O., Yen I. L. An Efficient Homomorphic Encryption Protocol for Multi-User Systems // IACR Cryptology ePrint Archive. – 2012. – № 193.
12. Gupta C. 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. – P. 1-4.
13. Gupta C.P. Fully Homomorphic Encryption Scheme with Symmetric Keys: diss. – Department of Computer Science & Engineering University College of Engineering, Rajasthan Technical University, Kota, 2013.
14. Rivest R. L., Kaliski Jr B. RSA problem // Encyclopedia of cryptography and security. – Springer US, 2011. – P. 1065-1069.
15. Трепачева А.В. Криптоанализ шифров, основанных на гомоморфизмах полиномиальных колец // Известия ЮФУ. Технические науки. – 2014. – № 8 (157). – C. 96-107.
16. 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. – P. 157.
17. Vizár D., Vaudenay S. Analysis of Chosen Symmetric Homomorphic Schemes // Central European Crypto Conference. – 2014. – №. EPFL-CONF-198992.
18. Tsaban B., Lifshitz N. Cryptanalysis of the MORE symmetric key fully homomorphic encryption scheme // Journal of Mathematical Cryptology. – 2014.
19. Ленг С. Алгебра: Пер. с англ. / Под ред. А.И. Кострикина. – М.: Мир, 1968. – 564 c.
20. Виноградов И.М. Основы теории чисел. – М.: Наукa, 1972. – 510 c.
21. Klivans A. Factoring polynomials modulo composites. – CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE, 1997. – №. CMU-CS-97-136.
22. Arvind V., Vijayaraghavan T. C. The complexity of solving linear equations over a finite ring // STACS 2005. – Springer Berlin Heidelberg, 2005. – P. 472-484.

Comments are closed.