Пакетное симметричное полностью гомоморфное шифрование на основе матричных полиномов
https://doi.org/10.15514/ISPRAS-2014-26(5)-5
Аннотация
Методы полностью гомоморфного шифрования (ПГШ) - общепризнанный способ организации криптографической защиты облачных вычислений. Однако существующие криптосхемы ПГШ по своим характеристикам не достаточны для применения на практике - одни криптосхемы имеют слишком малую криптостойкость, другие требуют слиш-ком больших вычислительных ресурсов. Для развития последних исследователями из IBM был предложен метод «упаковывания шифртекстов», который был применен ими к криптосхеме с открытым ключом, стойкость которой основана на сложности задач теории решеток. В данной работе метод «упаковки шифртекстов» применен к симметричной криптосхеме на основе матричных полиномов: приводится описание возможных способов организации такой упаковки, представлено описание одного из вариантов таких криптосистем с оценкой сложности алгоритма умножения шифртекстов. В заключение приведено сравнение эффективности полученной криптосхемы с криптосхемами исследователей из IBM.
Список литературы
1. R. L. Rivest, L. Adleman, M. L. Dertouzos. On data banks and privacy homomorphisms. Foundations of secure computation. 1978, Vol. 4, №. 11. pp. 169-180
2. C. Gentry. Fully homomorphic encryption using ideal lattices. Proceedings of the 41st annual ACM symposium on Symposium on theory of computing-STOC'09. - ACM Press, 2009. Vol. 9, pp. 169-169. doi:10.1145/1536414.1536440
3. A. Silverberg. Fully homomorphic encryption for mathematicians. Women in Numbers 2: Research Directions in Number Theory, 2013. Vol. 606. p. 111.
4. N.P. Varnovskij, А.V. Shokurov. Gomomorfnoe shifrovanie. [Homomorphic encryption]. Trudy ISP RАN [The Proceedings of ISP RAS], 2007. Vol. 12, pp. 27-36. (in Russian).
5. O. Zhirov, O. V. Zhirova, and S. F. Krendelev. Bezopasnye oblachnye vychisleniya s pomoshhyu homomorfnoj cryptographii. [Secure cloud computing using homomorphic cryptography]. BIT (bezopasnost’ informacionnyx technology) journal [Security of Information Technologies Magazine], 2013, Vol. 1, pp. 6-12. (in Russian).
6. Nigel P. Smart, F. Vercauteren. 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.
7. Naehrig M., Lauter K., Vaikuntanathan V. Can homomorphic encryption be practical? Proceedings of the 3rd ACM workshop on Cloud computing security workshop. - ACM, 2011. pp. 113-124. doi: 10.1145/2046660.2046682
8. C. Gentry, S. Halevi, N. P. Smart. Fully homomorphic encryption with polylog overhead. Advances in Cryptology-EUROCRYPT 2012. - Springer Berlin Heidelberg, 2012. pp. 465-482. doi: 10.1007/978-3-642-29011-4_28
9. 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. pp. 315-335. doi: 10.1007/978-3-642-38348-9_20
10. Z. Brakerski, C. Gentry, S. Halevi. Packed ciphertexts in LWE-based homomorphic encryption. Public-Key Cryptography-PKC 2013. - Springer Berlin Heidelberg, 2013. - pp. 1-13. doi: 10.1007/978-3-642-36362-7_1
11. 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. pp. 55-74.
12. Nigel P. Smart, F. Vercauteren. Fully homomorphic SIMD operations. Designs, codes and cryptography, 2014. Vol. 71, №. 1. - pp. 57-81. doi: 10.1007/s10623-012-9720-4
13. Yasuda, M., Shimoyama, T., Kogure, J., Yokoyama, K., Koshiba, T. Practical packing method in somewhat homomorphic encryption. Data Privacy Management and Autonomous Spontaneous Security. - Springer Berlin Heidelberg, 2014. pp. 34-50.
14. Zhirov A., Zhirova O., Krendelev S. F. Practical fully homomorphic encryption over polynomial quotient rings. Internet Security (WorldCIS), 2013 World Congress on. - IEEE, 2013. pp. 70-75. doi: 10.1109/WorldCIS.2013.6751020
15. 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. pp. 375-388. doi: 10.1007/978-3-642-36095-4_24
16. J. Domingo-Ferrer. A Provably Secure Additive and Multiplicative Privacy Homomorphism*. Information Security. - Springer Berlin Heidelberg, 2002. pp. 471-483.
17. Gavin G. An efficient FHE based on the hardness of solving systems of non-linear multivariate equations. IACR Cryptology ePrint Archive, 2013. №. 262.
18. Albrecht, M. R., Farshim, P., Faugere, J. C., Perret, L. Polly cracker, revisited. Advances in Cryptology-ASIACRYPT 2011. - Springer Berlin Heidelberg, 2011. pp. 179-196.
19. Herold G. Polly cracker, revisited, revisited. Public Key Cryptography-PKC 2012. - Springer Berlin Heidelberg, 2012. - pp. 17-33.
20. Armknecht, F., Augot, D., Perret, L., Sadeghi, A. R. On constructing homomorphic encryption schemes from coding theory. Cryptography and Coding. - Springer Berlin Heidelberg, 2011. - pp. 23-40.
21. Rostovtsev A., Bogdanov A., Mikhaylov M. Metod bezopasnogo vychislenija polinoma v nedoverennoj srede s pomowqju gomomorfizmov kolec [Secure evaluation of polynomial using privacy ring homomorphisms]. Problemy informacionnoj bezopasnosti. Kompqjuternye sistemy [Information security issues. Computer systems], 2011. Vol. 2. - pp. 76-85. (in Russian).
22. Wagner D. Cryptanalysis of an algebraic privacy homomorphism. Proc. of 6th Information Security Conference (ISC'03). - 2003. doi: 10.1.1.5.1420
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. - pp. 157. doi: 10.1145/2659651.2659692
24. Ph. Burtyka, O. Makarevich. Symmetric Fully Homomorphic Encryption Using Decidable Matrix Equations. Proceedings of the 7th International Conference on Security of Information and Networks. ACM, 2014, pp. 186-196. doi: 10.1145/2659651.2659693
25. F. B. Burtyka. Simmetrichnoe polnost'ju gomomorfnoe shifrovanie s ispol'zovaniem neprivodimyh matrichnyh polinomov [Symmetric fully homomorphic encryption using irreducible matrix polynomials]. Izvestija Juzhnogo federal'nogo universiteta. Tehnicheskie nauki [Proceedings of Southern Federal University. Engineering sciences], 2014, Vol. 158, №. 9, pp. 107-122. (in Russian).
26. 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. - pp. 102-118. doi: 10.1007/978-3-642-38980-1_7
27. S. Halevi, V. Shoup. Algorithms in HElib. IACR Cryptology ePrint Archive, 2014. №. 106.
28. S. Halevi. (2012) Performance of HElib. [Online]. Available: http://mpclounge.files.wordpress.com/2013/04/hespeed.pdf (Visited on 18.12.2014)
29. Burtyka Ph. B. O slozhnosti naxozhdenija kornej bulevyx matrichnyx polinomov [On the complexity of finding the roots of Boolean matrix polynomials]. Matematicheskoe modelirovanie [Matematical modelling], 2015. Vol. 27, №. 7. (in Russian).
30. Dennis, Jr J. E., Traub J. F., Weber R. P. The algebraic theory of matrix polynomials. SIAM Journal on Numerical Analysis, 13(6), 1976. pp. 831-845.
31. Dennis, Jr J. E., Traub J. F., Weber R. P. Algorithms for solvents of matrix polynomials. SIAM Journal on Numerical Analysis, 1978. Vol. 15. - №. 3. - pp. 523-533.
32. Antoine Guellier. Can Homomorphic Cryptography ensure Privacy? [Research Report] RR-8568, 2014, pp.111. https://hal.inria.fr/hal-01052509v1
33. R. L. Rivest, L. Adleman, M. L. Dertouzos. On data banks and privacy homomorphisms. Foundations of secure computation. 1978, Т. 4. №. 11. pp. 169-180.
34. C. Gentry. Fully homomorphic encryption using ideal lattices. Proceedings of the 41st annual ACM symposium on Symposium on theory of computing-STOC'09. Vol. 9 - ACM Press, 2009. pp. 169-169. doi:10.1145/1536414.1536440
35. A. Silverberg. Fully homomorphic encryption for mathematicians. Women in Numbers 2: Research Directions in Number Theory. - 2013. - Т. 606. - pp. 111.
36. Н. П. Варновский, А. В. Шокуров. Гомоморфное шифрование. Труды ИСП РАН, том 12, 2007 г. стр. 27-36.
37. А. О. Жиров, О. В. Жирова, С. Ф. Кренделев. Безопасные облачные вычисления с помощью гомоморфной криптографии. Журнал БИТ (безопасность информационных технологий), том 1, 2013. стр. 6-12.
38. Nigel P. Smart, F. Vercauteren. 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.
39. M. Naehrig, K. Lauter, V. Vaikuntanathan. Can homomorphic encryption be practical? Proceedings of the 3rd ACM workshop on Cloud computing security workshop. - ACM, 2011. pp. 113-124. doi: 10.1145/2046660.2046682
40. C. Gentry, S. Halevi, N. P. Smart. Fully homomorphic encryption with polylog overhead. Advances in Cryptology-EUROCRYPT 2012. - Springer Berlin Heidelberg, 2012. pp. 465-482. doi: 10.1007/978-3-642-29011-4_28
41. J. H. Cheon, J. S. Coron, J. Kim, M. S. Lee, T. Lepoint, M. Tibouchi, A. Yun. Batch Fully Homomorphic Encryption over the Integers. Advances in Cryptology-EUROCRYPT 2013. - Т. 7881. - 2013. pp. 315-335. doi: 10.1007/978-3-642-38348-9_20
42. Z. Brakerski, C. Gentry, S. Halevi. Packed ciphertexts in LWE-based homomorphic encryption. Public-Key Cryptography-PKC 2013. - Springer Berlin Heidelberg, 2013. - pp. 1-13. doi: 10.1007/978-3-642-36362-7_1
43. M. Yasuda, T. Shimoyama, J. Kogure, K. Yokoyama, T. Koshiba. Packed homomorphic encryption based on ideal lattices and its application to biometrics. Security Engineering and Intelligence Informatics. - Springer Berlin Heidelberg, 2013. pp. 55-74.
44. Nigel P. Smart, F. Vercauteren. Fully homomorphic SIMD operations. Designs, codes and cryptography, 2014. - Т. 71. - №. 1. - pp. 57-81. doi: 10.1007/s10623-012-9720-4
45. M. Yasuda, T. Shimoyama, J. Kogure, K. Yokoyama, T. Koshiba. Practical packing method in somewhat homomorphic encryption. Data Privacy Management and Autonomous Spontaneous Security. - Springer Berlin Heidelberg, 2014. pp. 34-50.
46. A. Zhirov, O. Zhirova, S. F. Krendelev. Practical fully homomorphic encryption over polynomial quotient rings. Internet Security (WorldCIS), 2013 World Congress on. - IEEE, 2013. pp. 70-75. doi: 10.1109/WorldCIS.2013.6751020
47. M. Hojsík, V. Půlpánová. A fully homomorphic cryptosystem with approximate perfect secrecy. Proceedings of the 13th international conference on Topics in Cryptology. - Springer-Verlag, 2013. pp. 375-388. doi: 10.1007/978-3-642-36095-4_24
48. J. Domingo-Ferrer. A Provably Secure Additive and Multiplicative Privacy Homomorphism*. Information Security. - Springer Berlin Heidelberg, 2002. pp. 471-483.
49. G. Gavin. An efficient FHE based on the hardness of solving systems of non-linear multivariate equations. IACR Cryptology ePrint Archive, 2013. №. 262.
50. M. R. Albrecht, P. Farshim, J. C. Faugere, L. Perret. Polly cracker, revisited. Advances in Cryptology-ASIACRYPT 2011. - Springer Berlin Heidelberg, 2011. pp. 179-196.
51. G. Herold. Polly cracker, revisited, revisited. Public Key Cryptography-PKC 2012. - Springer Berlin Heidelberg, 2012. - pp. 17-33.
52. F. Armknecht, D. Augot, L. Perret, A. R. Sadeghi. On constructing homomorphic encryption schemes from coding theory. Cryptography and Coding. - Springer Berlin Heidelberg, 2011. - pp. 23-40.
53. А. Г. Ростовцев, А. Богданов, М. Михайлов. Метод безопасного вычисления полинома в недоверенной среде с помощью гомоморфизмов колец. Проблемы информационной безопасности. Компьютерные системы, том 2, 2011, стр. 76-85.
54. D. Wagner. Cryptanalysis of an algebraic privacy homomorphism. Proc. of 6th Information Security Conference (ISC'03). - 2003. doi: 10.1.1.5.1420
55. A. Trepacheva, L. Babenko. Known plaintexts attack on polynomial based homomorphic encryption. Proceedings of the 7th International Conference on Security of Information and Networks. - ACM, 2014. - pp. 157. doi: 10.1145/2659651.2659692
56. Ph. Burtyka, O. Makarevich. Symmetric Fully Homomorphic Encryption Using Decidable Matrix Equations. Proceedings of the 7th International Conference on Security of Information and Networks. ACM, 2014, pp. 186-196. doi: 10.1145/2659651.2659693
57. Ф. Б. Буртыка. Симметричное полностью гомоморфное шифрование с использованием неприводимых матричных полиномов. Известия Южного федерального университета. Технические науки, том 158, №. 9, стр. 107-122, 2014.
58. D. Boneh, C. Gentry, S. Halevi, F. Wang, D. J. Wu. Private database queries using somewhat homomorphic encryption. Applied Cryptography and Network Security. - Springer Berlin Heidelberg, 2013. - pp. 102-118. doi: 10.1007/978-3-642-38980-1_7
59. S. Halevi, V. Shoup. Algorithms in HElib. IACR Cryptology ePrint Archive, 2014. № 106.
60. S. Halevi. (2012) Performance of HElib. [Online]. Available: http://mpclounge.files.wordpress.com/2013/04/hespeed.pdf (Дата обращения 18.12.2014)
61. Ф. Б. Буртыка. О сложности нахождения корней булевых матричных полиномов. Математическое моделирование, том 27, 2015. - №. 7.
62. Jr J. E. Dennis, J. F. Traub, R. P. Weber. The algebraic theory of matrix polynomials. SIAM Journal on Numerical Analysis, 13(6), 1976. pp. 831-845.
63. Jr J. E. Dennis, J. F. Traub, R. P. Weber. Algorithms for solvents of matrix polynomials. SIAM Journal on Numerical Analysis, 1978. - Т. 15. - №. 3. - pp. 523-533.
64. Antoine Guellier. Can Homomorphic Cryptography ensure Privacy? [Research Report] RR-8568, 2014, pp.111. https://hal.inria.fr/hal-01052509v1
Рецензия
Для цитирования:
Буртыка Ф.Б. Пакетное симметричное полностью гомоморфное шифрование на основе матричных полиномов. Труды Института системного программирования РАН. 2014;26(5):99-116. https://doi.org/10.15514/ISPRAS-2014-26(5)-5
For citation:
Burtyka P. Batch Symmetric Fully Homomorphic Encryption Using Matrix Polynomials. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2014;26(5):99-116. (In Russ.) https://doi.org/10.15514/ISPRAS-2014-26(5)-5
Послать статью по эл. почте 