Preview

Труды Института системного программирования РАН

Расширенный поиск

Пакетное симметричное полностью гомоморфное шифрование на основе матричных полиномов

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

Просмотров: 80


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2079-8156 (Print)
ISSN 2220-6426 (Online)