Preview

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

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

Улучшенная атака по известным открытым текстам на гомоморфную криптосистему Доминго-Феррера

https://doi.org/10.15514/ISPRAS-2014-26(5)-4

Полный текст:

Аннотация

Данная работа посвящена криптоанализу по известным открытым текстам гомоморфной криптосистемы, предложенной Доминго-Феррером. В предыдущих работах было показано, что для раскрытия секретного ключа необходимо перехватить по меньшей мере пару (открытый текст, шифртекст), где - степень полиномов, являющихся шифртекстами. Здесь мы проводим анализ существующей атаки по известным открытым текстам, а также показываем, как можно её модифицировать так, чтобы значительно уменьшить нужное количество перехваченных пар. А именно, оказывается, что достаточно всего лишь двух пар для раскрытия секретного ключа. Время работы предложенной атаки так же, как и для уже существующей, зависит полиномиально от и логарифмически от размера пространства открытых текстов. Представлены результаты компьютерных экспериментов.

Об авторе

А. В. Трепачева
Южный федеральный университет
Россия


Список литературы

1. R. L. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 1978, vol. 21, no. 2, pp. 120-126.

2. S. Goldwasser and S. Micali. Probabilistic encryption & how to play mental poker keeping secret all partial information. Proceedings of the fourteenth annual ACM symposium on Theory of computing. ACM, 1982, pp. 365-377.

3. P. Paillier. Public-key cryptosystems based on composite degree residuosity classes. Advances in cryptologyEUROCRYPT99. Springer, 1999, pp. 223-238.

4. D. Boneh, E.-J. Goh, and K. Nissim. Evaluating 2-dnf formulas on ciphertexts. Theory of cryptography. Springer, 2005, pp. 325-341.

5. Damgård I., Jurik M. A generalisation, a simplification and some applications of Paillier's probabilistic public-key system. Public Key Cryptography. - Springer Berlin Heidelberg, 2001, pp. 119-136.

6. Rivest R. L., Adleman L., Dertouzos M. L. On data banks and privacy homomorphisms. Foundations of secure computation, 1978, vol. 4, no. 11, pp. 169-180.

7. Brickell E. F., Yacobi Y. On privacy homomorphisms. Advances in Cryptology-EUROCRYPT’87. - Springer Berlin Heidelberg, 1988, pp. 117-125.

8. Fellows M., Koblitz N. Combinatorial cryptosystems galore //Contemporary Mathematics, 1993, vol. 168, no. 2, pp. 51-61.

9. Жиров А.О., Жирова О.В., Кренделев С.Ф. Безопасные облачные вычисления с помощью гомоморфной криптографии. Безопасность информационных технологий, 2013, Т. 1, С. 6-12.

10. J. D. i. Ferrer, A new privacy homomorphism and applications. Information Processing Letters, vol. 60, no. 5, pp. 277-282, 1996.

11. J. Domingo-Ferrer. A provably secure additive and multiplicative privacy homomorphism. Information Security. Springer, 2002, pp.471-483.

12. A. Trepacheva and L. Babenko. Known plaintexts attack on polynomial based homomorphic encryption. Proceedings of the Seventh International Conference on Security of Information and Networks. ACM, 2014.

13. M. R. Albrecht, P. Farshim, J.-C. Faugere, and L. Perret. Polly cracker, revisited. Advances in Cryptology-ASIACRYPT 2011. Springer, 2011, pp. 179-196.

14. C. Gentry. A fully homomorphic encryption scheme. Ph.D. dissertation, Stanford University, 2009.

15. M. Van Dijk, C. Gentry, S. Halevi, and V. Vaikuntanathan. Fully homomorphic encryption over the integers. in Advances in Cryptology-EUROCRYPT 2010. Springer, 2010, pp. 24-43.

16. Z. Brakerski, C. Gentry, and V. Vaikuntanathan,. (Leveled) Fully homomorphic encryption without bootstrapping. Proceedings of the 3rd Innovations in Theoretical Computer Science Conference. ACM, 2012, pp. 309-325.

17. N. P. Smart and F. Vercauteren. Fully homomorphic SIMD operations. Designs, Codes and Cryptography, pp. 1-25, 2011.

18. M. Naehrig, K. Lauter, and V. Vaikuntanathan. Can homomorphic encryption be practical?. Proceedings of the 3rd ACM workshop on Cloud computing security workshop. ACM, 2011, pp. 113-124.

19. L. Ertaul and J. H. Yang. Implementation of domingo ferrer’s a new privacy homomorphism (df a new ph) in securing wireless sensor networks (wsn)/ Security and Management. Citeseer, 2008, pp. 498-504.

20. L. Ertaul, Vaidehi. Implementation of Homomorphic Encryption Schemes for Secure Packet Forwarding in Mobile Ad Hoc Networks (MANETs). IJCSNS International Journal of Computer Science and Network Security, 2007, vol. 7, no. 11 pp. 132-141.

21. V. Jariwala and D. Jinwala. Evaluating homomorphic encryption algorithms for privacy in wireless sensor networks. International Journal of Advancements in Computing Technology, vol. 3, no. 6, 2011.

22. Vaghasia and K. Bathwar.Public key encryption algorithms for wireless sensor networks in tinyos. IJITEE, 2013, vol. 2, no. 4.

23. Sorniotti, L. Gomez, K. Wrona, and L. Odorico. Secure and trusted in-network data processing in wireless sensor networks: a survey. Journal of Information Assurance and Security, 2007, vol. 2, no. 3, pp. 189-199.

24. Westhoff, J. Girao, and M. Acharya. Concealed data aggregation for reverse multicast traffic in sensor networks: Encryption, key distribution, and routing adaptation. Mobile Computing, IEEE Transactions on , 2006, vol. 5, no. 10, pp. 1417-1431.

25. J. H. Cheon, W.-H. Kim, and H. S. Nam. Known-plaintext cryptanalysis of the domingo-ferrer algebraic privacy homomorphism scheme. Information Processing Letters, 2006, vol. 97, no. 3, pp. 118-123.

26. T. Benjamin and C. D. Bennett. The probability of relatively prime polynomials. Mathematics Magazine, 2007, pp. 196-202

27. Davenport, James H., Y. Siret, and E. Tournier. Computer algebra. London: Academic Press, 1988, 263 p.

28. Shoup V. NTL: A library for doing number theory. - 2001.

29. Wagner. Cryptanalysis of an algebraic privacy homomorphism. Information Security. Springer, 2003, pp. 234-239.

30. R. L. Rivest, A. Shamir, and L. Adleman. A method for obtaining digital signatures and public-key cryptosystems. Communications of the ACM, 1978, vol. 21, no. 2, pp. 120-126.

31. S. Goldwasser and S. Micali. Probabilistic encryption & how to play mental poker keeping secret all partial information. Proceedings of the fourteenth annual ACM symposium on Theory of computing. ACM, 1982, pp. 365-377.

32. P. Paillier. Public-key cryptosystems based on composite degree residuosity classes. Advances in cryptologyEUROCRYPT99. Springer, 1999, pp. 223-238.

33. D. Boneh, E.-J. Goh, and K. Nissim. Evaluating 2-dnf formulas on ciphertexts. Theory of cryptography. Springer, 2005, pp. 325-341.

34. Damgård I., Jurik M. A generalisation, a simplification and some applications of Paillier's probabilistic public-key system. Public Key Cryptography. - Springer Berlin Heidelberg, 2001, pp. 119-136.

35. Rivest R. L., Adleman L., Dertouzos M. L. On data banks and privacy homomorphisms. Foundations of secure computation, 1978, vol. 4, no. 11, pp. 169-180.

36. Brickell E. F., Yacobi Y. On privacy homomorphisms. Advances in Cryptology-EUROCRYPT’87. - Springer Berlin Heidelberg, 1988, pp. 117-125.

37. Fellows M., Koblitz N. Combinatorial cryptosystems galore //Contemporary Mathematics, 1993, vol. 168, no. 2, pp. 51-61.

38. O. Zhirov, O. V. Zhirova, and S. F. Krendelev. Bezopasnye oblachnye vychisleniya s pomoshh'yu gomomorfnoj kriptografii. [Secure cloud computing using homomorphic cryptography]. Bezopasnost' informatsionnykh tekhnologij. [The security of information technologies], vol. 1, pp. 6-12, 2013 (in Russian).

39. J. D. i. Ferrer, A new privacy homomorphism and applications. Information Processing Letters, vol. 60, no. 5, pp. 277-282, 1996.

40. J. Domingo-Ferrer. A provably secure additive and multiplicative privacy homomorphism. Information Security. Springer, 2002, pp.471-483.

41. A. Trepacheva and L. Babenko. Known plaintexts attack on polynomial based homomorphic encryption. Proceedings of the Seventh International Conference on Security of Information and Networks. ACM, 2014.

42. M. R. Albrecht, P. Farshim, J.-C. Faugere, and L. Perret. Polly cracker, revisited. Advances in Cryptology-ASIACRYPT 2011. Springer, 2011, pp. 179-196.

43. C. Gentry. A fully homomorphic encryption scheme. Ph.D. dissertation, Stanford University, 2009.

44. M. Van Dijk, C. Gentry, S. Halevi, and V. Vaikuntanathan. Fully homomorphic encryption over the integers. in Advances in Cryptology-EUROCRYPT 2010. Springer, 2010, pp. 24-43.

45. Z. Brakerski, C. Gentry, and V. Vaikuntanathan,. (Leveled) Fully homomorphic encryption without bootstrapping. Proceedings of the 3rd Innovations in Theoretical Computer Science Conference. ACM, 2012, pp. 309-325.

46. N. P. Smart and F. Vercauteren. Fully homomorphic SIMD operations. Designs, Codes and Cryptography, pp. 1-25, 2011.

47. M. Naehrig, K. Lauter, and V. Vaikuntanathan. Can homomorphic encryption be practical?. Proceedings of the 3rd ACM workshop on Cloud computing security workshop. ACM, 2011, pp. 113-124.

48. L. Ertaul and J. H. Yang. Implementation of domingo ferrer’s a new privacy homomorphism (df a new ph) in securing wireless sensor networks (wsn)/ Security and Management. Citeseer, 2008, pp. 498-504.

49. L. Ertaul, Vaidehi. Implementation of Homomorphic Encryption Schemes for Secure Packet Forwarding in Mobile Ad Hoc Networks (MANETs). IJCSNS International Journal of Computer Science and Network Security, 2007, vol. 7, no. 11 pp. 132-141.

50. V. Jariwala and D. Jinwala. Evaluating homomorphic encryption algorithms for privacy in wireless sensor networks. International Journal of Advancements in Computing Technology, vol. 3, no. 6, 2011.

51. Vaghasia and K. Bathwar.Public key encryption algorithms for wireless sensor networks in tinyos. IJITEE, 2013, vol. 2, no. 4.

52. Sorniotti, L. Gomez, K. Wrona, and L. Odorico. Secure and trusted in-network data processing in wireless sensor networks: a survey. Journal of Information Assurance and Security, 2007, vol. 2, no. 3, pp. 189-199.

53. Westhoff, J. Girao, and M. Acharya. Concealed data aggregation for reverse multicast traffic in sensor networks: Encryption, key distribution, and routing adaptation. Mobile Computing, IEEE Transactions on , 2006, vol. 5, no. 10, pp. 1417-1431.

54. J. H. Cheon, W.-H. Kim, and H. S. Nam. Known-plaintext cryptanalysis of the domingo-ferrer algebraic privacy homomorphism scheme. Information Processing Letters, 2006, vol. 97, no. 3, pp. 118-123.

55. T. Benjamin and C. D. Bennett. The probability of relatively prime polynomials. Mathematics Magazine, 2007, pp. 196-202.

56. Davenport, James H., Y. Siret, and E. Tournier. Computer algebra. London: Academic Press, 1988, 263 p.

57. Shoup V. NTL: A library for doing number theory. - 2001.

58. Wagner. Cryptanalysis of an algebraic privacy homomorphism. Information Security. Springer, 2003, pp. 234-239.


Для цитирования:


Трепачева А.В. Улучшенная атака по известным открытым текстам на гомоморфную криптосистему Доминго-Феррера. Труды Института системного программирования РАН. 2014;26(5):83-98. https://doi.org/10.15514/ISPRAS-2014-26(5)-4

For citation:


Trepacheva A.V. Improved known plaintexts attack on Domingo-Ferrer homomorphic cryptosystem. Proceedings of the Institute for System Programming of the RAS (Proceedings of ISP RAS). 2014;26(5):83-98. (In Russ.) https://doi.org/10.15514/ISPRAS-2014-26(5)-4

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


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


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