Статья

Название статьи СИММЕТРИЧНОЕ ПОЛНОСТЬЮ ГОМОМОРФНОЕ ШИФРОВАНИЕ С ИСПОЛЬЗОВАНИЕМ НЕПРИВОДИМЫХ МАТРИЧНЫХ ПОЛИНОМОВ
Автор Ф.Б. Буртыка
Рубрика РАЗДЕЛ II. КРИПТОГРАФИЧЕСКИЕ МЕТОДЫ ЗАЩИТЫ ИНФОРМАЦИИ
Месяц, год 08, 2014
Индекс УДК 004.056.55: 003.26
DOI
Аннотация Представлена новая симметричная компактная полностью гомоморфная криптосхема, основанная на использовании матричных полиномов и производящая шифрование в два раунда: сначала открытые тексты, являющиеся элементами кольца вычетов, кодируются в матрицы с помощью секретного вектора k, а затем эти матрицы отображаются в матричные полиномы с использованием секретного неприводимого матричного полинома K(X). Расшифрование также происходит в два раунда: сначала осуществляется приведение по модулю K(X), а затем умножение полученной в результате матрицы на k. Отображение расшифрования является гомоморфизмом колец. Время работы всех алгоритмов криптосхемы зависит полиномиально от параметра защищенности λ. Временные издержки при её использовании для вычисления над зашифрованными данными также полиномиальны от λ. Введение специального ключа перешифрования, зависящего от секретного ключа, позволило добиться того, что при вычислениях над шифровками их размеры всегда остаются ограниченными фиксированным полиномом от λ. При практической реализации возможно эффективное распараллеливание. Проводится анализ криптостойкости предложенной криптосхемы относительно атак на основе только шифротекстов, по известным открытым текстам и на ключ перешифрования. Продемонстрировано то, что все эти атаки могут быть сведены к решению системы полиномиальных уравнений от многих переменных над кольцом вычетов. Рассматривается вопрос о сложности решения этих систем существующими методами.

Скачать в PDF

Ключевые слова Полностью гомоморфная криптосхема; матричные полиномы; системы полиномиальных уравнений; атака по известным открытым текстам; защищённые облачные вычисления.
Библиографический список 1. Rivest R.L., Adleman L., Dertouzos M. L. On data banks and privacy homomorphisms // Foundations of secure computation. – 1978. – Vol. 4, № 11. – P. 169-180.
2. Paillier P. Public-key cryptosystems based on composite degree residuosity classes // Advances in cryptology-EUROCRYPT’99. – Springer Berlin Heidelberg, 1999. – P. 223-238.
3. Rivest R. L., Shamir A., Adleman L. A method for obtaining digital signatures and public-key cryptosystems // Communications of the ACM. – 1983. – Vol. 26, No. 1. – P. 96-99.
4. Gentry C. Fully homomorphic encryption using ideal lattices // STOC. – 2009. – Vol. 9. – P. 169-178.
5. Vaikuntanathan V. Computing blindfolded: New developments in fully homomorphic encryption // Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on IEEE. – 2011. – P. 5-16.
6. Gentry C., Halevi S. Fully homomorphic encryption without squashing using depth-3 arithmetic circuits // Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on IEEE, 2011. – P. 107-109.
7. Jing-Li H., Ming Y., Zhao-Li W. Fully homomorphic encryption scheme extended to large message space // Instrumentation, Measurement, Computer, Communication and Control, International Conference on IEEE, 2011. – P. 533-536.
8. Alperin-Sheriff J., Peikert C. Practical bootstrapping in quasilinear time // Advances in Cryptology–CRYPTO 2013. – Springer Berlin Heidelberg, 2013. – P. 1-20.
9. Alperin-Sheriff J., Peikert C. Faster Bootstrapping with Polynomial Error // IACR Cryptology ePrint Archive. – 2014. – Vol. 2014. – P. 94.
10. Orsini E., van de Pol J., Smart N.P. Bootstrapping BGV Ciphertexts With A Wider Choice of p and q.
11. Smart N.P., Vercauteren F. Fully homomorphic SIMD operations // Designs, codes and cryptography. – 2014. – Vol. 71, No. 1. – P. 57-81.
12. Stehlй D., Steinfeld R. Faster fully homomorphic encryption // Advances in Cryptology-ASIACRYPT 2010. – Springer Berlin Heidelberg, 2010. – P. 377-394.
13. Brakerski Z., Gentry C., Vaikuntanathan V. (Leveled) fully homomorphic encryption without bootstrapping // Proceedings of the 3rd Innovations in Theoretical Computer Science Conference. – ACM, 2012. – P. 309-325.
14. Bogdanov A., Lee C. H. Limits of provable security for homomorphic encryption // Advances in Cryptology–CRYPTO 2013. – Springer Berlin Heidelberg, 2013. – P. 111-128.
15. Domingo-Ferrer J. A Provably Secure Additive and Multiplicative Privacy Homomorphism // Information Security. – Springer Berlin Heidelberg, 2002. – P. 471-483.
16. Hojsнk M., Půlpбnovб V. A fully homomorphic cryptosystem with approximate perfect secrecy // Topics in Cryptology–CT-RSA 2013. – Springer Berlin Heidelberg, 2013. – P. 375-388.
17. Гельфанд С.И. О числе решений квадратного уравнения // Издание осуществлено при поддержке РФФИ (издательский проект № 01-01-14022). – 2004. – С. 124.
18. Кнут Д. Искусство программирования. Т. 2. Получисленные алгоритмы. – СПб.: Вильямс, 2007. – 788 с.
19. Williams V.V. Multiplying matrices faster than Coppersmith-Winograd // Proceedings of the forty-fourth annual ACM symposium on Theory of computing. – ACM, 2012. – P. 887-898.
20. Olsson R.A., Keen A.W. Parallel Matrix Multiplication // The JR Programming Language: Concurrent Programming in an Extended Java. – 2004. – P. 211-225.
21. Schaefer T.J. The complexity of satisfiability problems // Proceedings of the tenth annual ACM symposium on Theory of computing. – ACM, 1978. – P. 216-226.
22. Bard G. Algebraic cryptanalysis. – Springer, 2009.
23. Gao X. S., Huang Z. Characteristic set algorithms for equation solving in finite fields // Journal of Symbolic Computation. – 2012. – Vol. 47, No. 6. – P. 655-679.

Comments are closed.