DOI: https://doi.org/10.30837/2522-9818.2018.6.005

ГОМОМОРФНЕ ШИФРУВАННЯ ДАНИХ У ХМАРНИХ СХОВИЩАХ МЕТОДОМ МАТРИЧНИХ ПОЛІНОМІВ

Олександр Ігорович Белей

Анотація


Предметом дослідження є шифрування інформації в хмарних обчисленнях і сховищах даних. Хмарні технології дозволяють значно скоротити витрати на ІТ-інфраструктуру і гнучко реагувати на зміни обчислювальних потреб. В такому випадку має бути забезпечено можливість проведення обчислень над зашифрованими даними без їх дешифрування. Таку властивість має повністю гомоморфне шифрування. Метою даної статті є підвищення ефективності повністю гомоморфного шифрування (ПГШ) на основі матричних поліномів за допомогою методу пакетного шифрування в один шифротекст декількох відкритих текстів з наступною комплексною обробкою зашифрованих даних. Пакетне шифрування зводиться до того, що при одній операції над двома шифротекстами відбувається одночасне виконання операцій покоординатно над усіма даними, що містяться в цих шифротекстах у вигляді відкритих текстів (SIMD). Завданнями визначено побудову алгоритмів повністю гомоморфного шифрування даних за допомогою матричних поліномів. У статті використано методи шифрування: з використанням китайської теореми про залишки; шляхом запису в одній матриці декількох різних власних значень при різних власних векторах; за допомогою інтерполяції матричних поліномів. В результаті описано та проаналізовано можливі підходи до побудови пакетних ПГШ на підставі матричних поліномів, а також представлено набір алгоритмів, що реалізують криптосхему ПГШ з інтерполяцією матричних поліномів. Наведені алгоритми і криптосхеми дозволяють передавати інформацію в повідомленнях і дані в запитах як відкритий текст, бо над шифрованими даними можна здійснювати необмежену кількість складних алгебраїчних операцій. Це, у свою чергу, ускладнює можливість дешифрування і зчитування даних без знання всього алгоритму. Було показано, що побудовані криптосхеми перевершують аналоги по ефективності, які розроблені дослідниками з IBM. Можна зробити наступний висновок: пакетне повністю е шифрування на основі матричних поліномів здатне виключити необхідність хоча б часткового дешифрування даних для несанкціонованих обчислень над зашифрованими масивами даних у хмарних сховищах.

Ключові слова


повністю гомоморфне шифрування; сховище даних; алгоритм; шифротекст; криптографічні методи; криптосхеми; матричні поліноми

Повний текст:

PDF

Посилання


Albrecht, M. R., Farshim, P., Faugere, J. C., Perret, L. (2011), "Polly cracker, revisited. Advances in Cryptology", Springer Berlin Heidelberg, P. 179-196.

Armknecht, F., Augot, D., Perret, L., Sadeghi, A. R. (2011) "On constructing homomorphic encryption schemes from coding theory", Cryptography and Coding, Springer Berlin Heidelberg, P. 23-40.

Boneh, D., Gentry, C., Halevi, S., Wang, F., Wu, D. J. (2013), "Private database queries using somewhat homomorphic encryption", Applied Cryptography and Network Security. Springer Berlin Heidelberg, P. 102–118. DOI: https://doi.org/10.1007/978-3-642-38980-1_7.

Cheon, J. H., Coron, J. S., Kim, J., Lee, M. S., Lepoint, T., Tibouchi, M., Yun, A. (2013), "Batch Fully Homomorphic Encryption over the Integers", Advances in Cryptology, EUROCRYPT, Vol. 7881, P. 315–335. DOI: https://doi.org/ 10.1007/978-3-642-38348-9_20.

Dennis, Jr J. E., Traub, J. F., Weber, R. P. (1978), "Algorithms for solvents of matrix polynomials", SIAM Journal on Numerical Analysis, Vol. 15, No. 3, P. 523–533.

Domingo-Ferrer, J. (2002), "A Provably Secure Additive and Multiplicative Privacy Homomorphism", Information Security, Springer Berlin Heidelberg, P. 471–483.

Gavin, G. (2013), "An efficient FHE based on the hardness of solving systems of non-linear multivariate equations", IACR Cryptology ePrint Archive, No. 262.

Gentry, S., Halevi, N. P. Smart (2012), "Fully homomorphic encryption with polylog overhead" Advances in Cryptology, EUROCRYPT, Springer Berlin Heidelberg, P. 465-482. DOI: https://doi.org/ 10.1007/978-3-642-29011-4_28.

Guellier, Antoine (2014), "Can Homomorphic Cryptography ensure Privacy?" [Research Report], RR-8568, P. 111, available at : URL : https://hal.inria.fr/hal-01052509v1 (last accessed 11.11.2018).

Halevi, S., Shoup, V. (2014), "Algorithms in HElib", IACR Cryptology ePrint Archive, No. 106.

Herold, G. (2012), "Polly cracker, revisited, revisited. Public Key Cryptography", PKC, Springer Berlin Heidelberg, P. 17–33.

Hojsík, M., Půlpánová, V. (2013), "A fully homomorphic cryptosystem with approximate perfect secrecy", Proceedings of the 13th international conference on Topics in Cryptology, Springer-Verlag, P. 375–388. DOI: https://doi.org/10.1007/978-3-642-36095-4_24.

Naehrig, M., Lauter, K., Vaikuntanathan, V. (2011), "Can homomorphic encryption be practical?", Proceedings of the 3rd ACM workshop on Cloud computing security workshop, ACM, P. 113–124. DOI: https://doi.org/10.1145/2046660.2046682.

Poteya, Manish, M., Dhoteb, C. A., Sharmac Deepak H. (2016), "Homomorphic Encryption for Security of Cloud Data", Procedia Computer Science 79, P. 175–181. DOI: https://doi.org/10.1016/j.procs.2016.03.023.

Rivest, R. L., Adleman, L., Dertouzos, M. L. (1978), "On data banks and privacy homomorphisms", Foundations of secure computation, Vol. 4, No. 11, P. 169–180.

Silverberg (2013), "Fully homomorphic encryption for mathematicians", Women in Numbers 2: Research Directions in Number Theory, Vol. 606, P. 111.

Smart, Nigel, P., Vercauteren, F. (2010), "Fully Homomorphic Encryption with Relatively Small Key and Ciphertext Sizes", Public Key Cryptography-PKC 2010: 13th International Conference on Practice and Theory in Public Key Cryptography, Paris, France, Proceedings, Springer, P. 420.

Wagner, D. (2003), "Cryptanalysis of an algebraic privacy homomorphism", Proc. of 6th Information Security Conference (ISC’03). DOI: https://doi.org/10.1.1.5.1420.

Yasuda, M., Shimoyama, T., Kogure, J., Yokoyama, K., Koshiba, T. (2013), "Packed homomorphic encryption based on ideal lattices and its application to biometrics", Security Engineering and Intelligence Informatics, Springer Berlin Heidelberg, P. 55–74.

Stupen, P. V., Sokolov, S. O., Zolkina, O. Yu. (2015), "Application of homomorphic encryption for the protection of numerical data in cloud storage", Scientific works of the Petro Mohyla Black Sea State University of the Kyiv-Mohyla Academy complex. Series: Computer Technology, Vol. 266, No. 254, P. 71–75, available at : http://nbuv.gov.ua/UJRN/Npchduct_2015_266_254_13 (last accessed: 28.11.2018).

Kvyetnyy, R. N., Tytarchuk, Ye. O. (2016), "The use of a partially homomorphic encryption algorithm on elliptic curves in a cloud-based electronic voting system", Optoelectronic information technology technologies, No. 32 (2), P. 14–22.

Kvyetnyy, R. N., Tytarchuk, Ye. O. (2017), "Analysis of cryptostability of partially homomorphic encryption algorithm on the basis of elliptic curves", Information Technology and Computer Engineering, No. 1 (38), P. 83–87.


Пристатейна бібліографія ГОСТ


1.   Albrecht M. R., Farshim P., Faugere J. C., Perret L. Polly cracker, revisited. Advances in Cryptology. Springer Berlin Heidelberg. 2011. P. 179–196.

2.   Armknecht F., Augot D., Perret L., Sadeghi A. R. On constructing homomorphic encryption schemes from coding theory. Cryptography and Coding. Springer Berlin Heidelberg. 2011. P. 23–40.

3.   Boneh D., Gentry C., Halevi S., Wang F., Wu D. J. Private database queries using somewhat homomorphic encryption. Applied Cryptography and Network Security. Springer Berlin Heidelberg. 2013. P. 102–118. DOI: https://doi.org/ 10.1007/978-3-642-38980-1_7.

4.   Cheon J. H., Coron J. S., Kim J., Lee M. S., Lepoint T., Tibouchi M., Yun A. Batch Fully Homomorphic Encryption over the Integers. Advances in Cryptology. EUROCRYPT. Vol. 7881. 2013. P. 315–335. DOI: https://doi.org/ 10.1007/978-3-642-38348-9_20.

5.   Dennis, Jr J. E., Traub J. F., Weber R. P. Algorithms for solvents of matrix polynomials. SIAM Journal on Numerical Analysis. 1978. Vol. 15. No. 3. P. 523–533.

6.   Domingo-Ferrer J. A Provably Secure Additive and Multiplicative Privacy Homomorphism. Information Security. Springer Berlin Heidelberg. 2002. P. 471–483.

7.   Gavin G. An efficient FHE based on the hardness of solving systems of non-linear multivariate equations. IACR Cryptology ePrint Archive. 2013. No. 262.

8.   Gentry S., Halevi N. P. Smart. Fully homomorphic encryption with polylog overhead. Advances in Cryptology – EUROCRYPT Springer Berlin Heidelberg. 2012. P. 465–482. DOI: https://doi.org/ 10.1007/978-3-642-29011-4_28.

9.   Guellier Antoine. Can Homomorphic Cryptography ensure Privacy? [Research Report] RR-8568. 2014. P. 111. URL : https://hal.inria.fr/hal-01052509v1.

10. Halevi S., Shoup V. Algorithms in HElib. IACR Cryptology ePrint Archive. 2014. No. 106.

11. Herold G. Polly cracker, revisited, revisited. Public Key Cryptography. PKC. Springer Berlin Heidelberg. 2012. P. 17–33.

12. Hojsík M., Půlpánová V. A fully homomorphic cryptosystem with approximate perfect secrecy. Proceedings of the 13th international conference on Topics in Cryptology. Springer-Verlag. 2013. P. 375–388. DOI: https://doi.org/10.1007/978-3-642-36095-4_24.

13. Naehrig M., Lauter K., Vaikuntanathan V. Can homomorphic encryption be practical? Proceedings of the 3rd ACM workshop on Cloud computing security workshop. ACM. 2011. P. 113–124. DOI: https://doi.org/10.1145/2046660.2046682.

14. Poteya Manish M., Dhoteb C. A., Sharmac Deepak H. Homomorphic Encryption for Security of Cloud Data. Procedia Computer Science 79. 2016. P. 175 – 181. DOI: https://doi.org/10.1016/j.procs.2016.03.023.

15. Rivest R. L., Adleman L., Dertouzos M. L. On data banks and privacy homomorphisms. Foundations of secure computation. 1978. Vol. 4. No. 11. P. 169–180.

16. Silverberg. Fully homomorphic encryption for mathematicians. Women in Numbers 2: Research Directions in Number Theory. 2013. Т. 606. P. 111.

17. Smart Nigel P., Vercauteren F. Fully Homomorphic Encryption with Relatively Small Key and Ciphertext Sizes. Public Key Cryptography-PKC 2010: 13th International Conference on Practice and Theory in Public Key Cryptography, Paris, France,
May 26-28, 2010, Proceedings. Springer, 2010. P. 420.

18. Wagner D. Cryptanalysis of an algebraic privacy homomorphism. Proc. of 6th Information Security Conference (ISC’03). 2003. DOI: https://doi.org/10.1.1.5.1420.

19. Yasuda M., Shimoyama T., Kogure J., Yokoyama K., Koshiba T. Packed homomorphic encryption based on ideal lattices and its application to biometrics. Security Engineering and Intelligence Informatics. Springer Berlin Heidelberg. 2013. P. 55–74.

20. Ступень П. В., Соколов С. О., Золкіна О. Ю. Застосування гомоморфного шифрування для захисту числових даних у хмарних сховищах. Наукові праці Чорноморського державного університету імені Петра Могили комплексу "Києво-Могилянська академія". Серія: Комп’ютерні технології. 2015. Т. 266, Вип. 254. С. 71–75. URL : http://nbuv.gov.ua/UJRN/Npchduct_2015_266_254_13 (дата звернення : 28.11.2018).

21. Квєтний Р. Н., Титарчук Є. О. Використання частково гомоморфного алгоритму шифрування на еліптичних кривих у хмарній системі електронного голосування. Оптико-електроннiiнформацiйноенергетичнi технологiї. 2016. № 32 (2).
C. 14–22.

22. Квєтний Р. Н., Титарчук Є. О. Аналіз криптостійкості частково гомоморфного алгоритму шифрування на основі еліптичних кривих. Інформаційні технології та комп’ютерна інженерія. 2017. № 1 (38). C. 83–87.





Copyright (c) 2018 Олександр Ігорович Белей

Creative Commons License
Ця робота ліцензована Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

Всі статті, опубліковані в журналі ITSSI, доступні на умовах ліцензії CC BY-NC-SA 4.0