Статья

Название статьи КРИПТОАНАЛИЗ ШИФРОВ, ОСНОВАННЫХ НА ГОМОМОРФИЗМАХ ПОЛИНОМИАЛЬНЫХ КОЛЕЦ
Автор А.В. Трепачева
Рубрика РАЗДЕЛ II. КРИПТОГРАФИЧЕСКИЕ МЕТОДЫ ЗАЩИТЫ ИНФОРМАЦИИ
Месяц, год 08, 2014
Индекс УДК 003.26.09
DOI
Аннотация Проводится анализ защищенности симметричных гомоморфных криптосхем шифрования, построенных на гомоморфизмах полиномиальных колец. Предлагается простой метод вычисления секретного ключа при наличии у криптоаналитика нескольких пар (шифртекст, открытый текст) в случае, когда пространство открытых текстов – конечное поле Fq. Он позволяет определить правильный ключ с вероятностью, равной единице, при наличии хотя бы пяти пар в случае небольших q. Для больших же значений q достаточно уже двух пар. Обсуждается, каким образом можно адаптировать этот метод для случая, когда пространство открытых текстов – кольцо вычетов Zn , где n – составное число. Также обсуждается метод, позволяющий скорректировать вычисленное с использованием пар значение ключа в случае, когда количество пар (шифротекст, открытый текст) меньше пяти. Для его работы необходимо знание вероятностного распределения на множестве открытых текстов и наличие дополнительной последовательности шифртекстов, зашифрованных на том же ключе. Данный метод успешно раскрывает ключ практически в 100 % случаев, если на открытых текстах задано распределение, достаточно сильно отличающееся от равномерного (например, нормальное распределение с небольшой дисперсией).

Скачать в PDF

Ключевые слова Атака по известным открытым текстам; гомоморфное шифрование; облачные вычисления; полиномы.
Библиографический список 1. Gentry C. A fully homomorphic encryption scheme: diss. – Stanford University, 2009.
2. Van Dijk M. et al. Fully homomorphic encryption over the integers // Advances in Cryptology–EUROCRYPT 2010. – Springer Berlin Heidelberg, 2010. – P. 24-43.
3. Brakerski Z., Vaikuntanathan V. Efficient fully homomorphic encryption from (standard) LWE // Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on. – IEEE, 2011. – P. 97-106.
4. Gentry C., Sahai A., Waters B. Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based // Advances in Cryptology–CRYPTO 2013. – Springer Berlin Heidelberg, 2013. – P. 75-92.
5. Stehlй D., Steinfeld R. Faster fully homomorphic encryption //Advances in Cryptology-ASIACRYPT 2010. – Springer Berlin Heidelberg, 2010. – P. 377-394.
6. Gentry C., Halevi S. Implementing gentry’s fully-homomorphic encryption scheme // Advances in Cryptology–EUROCRYPT 2011. – Springer Berlin Heidelberg, 2011. – P. 129-148.
7. Жиров А.О., Жирова О.В., Кренделев С.Ф. Безопасные облачные вычисления с помощью гомоморфной криптографии // Безопасность информационных технологий. – 2013. – Т. 1. – С. 6-12.
8. Rostovtsev A., Bogdanov A., Mikhaylov M. Secure evaluation of polynomial using privacy ring homomorphisms // IACR Cryptology ePrint Archive. – 2011. – Vol. 2011. – P. 24.
9. Lidl R., Niderreiter H. Finite Fields (Vol. 20, Encyclopedia of Math. and its Appl.) // Englewood Cliffs, NJ: Addison~ lVesley. – 1983. – P. 74-85.
10. Klivans A. Factoring polynomials modulo composites. – CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE, 1997. – №. CMU-CS-97-136.
11. Benjamin A.T., Bennett C.D. The probability of relatively prime polynomials // Mathematics Magazine. – 2007. – P. 196-202.
12. Shoup V. NTL: A library for doing number theory. – 2001.

Comments are closed.