Authors A.V. Trepacheva
Month, Year 05, 2015 @en
Index UDC 519.7: 004: 681.5
Abstract This paper considers the fully homomorphic cryptosystems based by their authors on a factorization problem. In particular, the paper analyses the security of cryptosystems whose ciphertexts are matrices with elements modulo composite number that is hard to factorize, while encryption and decryption procedures are similarity transformations. We carefully analyze the properties of ciphertexts produced by their encryption algorithms. And on the base of this analysis main vulnerabilities of the cryptosystems are highlighted. The main focus of this paper is placed on analysis of resistance against known plaintext attack of two recently proposed cryptosystems belonging to this type. In particular, we discuss one strategy of known plaintext attack on them proposed in literature. It is based on solving of linear system modulo composite number. Our main result in comparison with predecessors is providing a strict theoretical estimation of probability to recover secret key for different number of intercepted pairs (plaintext, ciphertext) using this strategy. Also practical estimations of probability to find a key based on computer experiments are given. They correlate well with theoretical predictions. Our analysis shows that the first considered cryptosystem is vulnerable to known plaintext attack based on linear system solving. However to recover key with probability ≈1 one needs to have the number of pairs (plaintext, ciphertext) depending polylogarithmically on the number of factors in exploiting composite modulus. And for the less number of pairs the cryptosystem is secure. This to some extent corresponds to security estimations given by the authors of cryptosystem. As for the second cryptosystem, its breaking requires much less number of pairs and thus its security level doesn’t match with level stated by the authors.

Download PDF

Keywords Fully homomorphic cryptosystem; known plaintext attack; secure cloud computing; factorization problem.
References 1. Armbrust M. et al. A view of cloud computing, Communications of the ACM, 2010, Vol. 53, No. 4, pp. 50-58.
2. Guellier A. Can Homomorphic Cryptography ensure Privacy?: diss. Inria; IRISA; Supélec Rennes, équipe Cidre; Université de Rennes 1, 2014.
3. Gentry C. A fully homomorphic encryption scheme: diss. Stanford University, 2009.
4. Burtyka P., Makarevich O. Symmetric Fully Homomorphic Encryption Using Decidable Matrix Equations, Proceedings of the 7th International Conference on Security of Information and Networks. ACM, 2014, pp. 186.
5. Nuida K. A Simple Framework for Noise-Free Construction of Fully Homomorphic Encryption from a Special Class of Non-Commutative Group, IACR Cryptology ePrint Archive, 2014, Vol. 2014, pp. 97.
6. Tamayo-Rios M. Method for fully homomorphic encryption using multivariate cryptography: application Pat. 13/915,500 USA, 2013.
7. Rostovtsev A., Bogdanov A., Mikhaylov M. Secure evaluation of polynomial using privacy ring homomorphisms, IACR Cryptology ePrint Archive, 2011, Vol. 2011, pp. 24.
8. 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.
9. Kipnis A., Hibshoosh E. Efficient Methods for Practical Fully Homomorphic Symmetric-key Encrypton, Randomization and Verification, IACR Cryptology ePrint Archive, 2012, No. 637.
10. Chan A.C.F. Symmetric-key homomorphic encryption for encrypted data processing, Communications, 2009. ICC'09. IEEE International Conference on. IEEE, 2009, pp. 1-5.
11. Xiao L., Bastani O., Yen I. L. An Efficient Homomorphic Encryption Protocol for Multi-User Systems, IACR Cryptology ePrint Archive, 2012, No. 193.
12. Gupta C.P., Sharma I. Department of Computer Sciences and Engineering Rajasthan Technical University, Kota, India, Network of the Future (NOF), 2013 Fourth International Conference on the. IEEE, 2013, pp. 1-4.
13. Gupta C.P. Fully Homomorphic Encryption Scheme with Symmetric Keys: diss. – Department of Computer Science & Engineering University College of Engineering, Rajasthan Technical University, Kota, 2013.
14. Rivest R. L., Kaliski Jr B. RSA problem, Encyclopedia of cryptography and security. Springer US, 2011, pp. 1065-1069.
15. Trepacheva A.V. Kriptoanaliz shifrov, osnovannykh na gomomorfizmakh polinomial'nykh kolets [Crypyoanalysis of cryptosytems based on polynomial ring homomorhisms], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2014, No. 8 (157), pp. 96-107.
16. 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.
17. Vizár D., Vaudenay S. Analysis of Chosen Symmetric Homomorphic Schemes, Central European Crypto Conference, 2014, No. EPFL-CONF-198992.
18. Tsaban B., Lifshitz N. Cryptanalysis of the MORE symmetric key fully homomorphic encryption scheme, Journal of Mathematical Cryptology, 2014.
19. Leng S. Algebra: Translation from English, Under ed. A.I. Kostrikina. Moscow: Mir, 1968, 564 p.
20. Vinogradov I.M. Osnovy teorii chisel [Fundamentals of the theory of numbers]. Moscow: Nauka, 1972, 510 p.
21. Klivans A. Factoring polynomials modulo composites. CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE, 1997. No. CMU-CS-97-136.
22. Arvind V., Vijayaraghavan T. C. The complexity of solving linear equations over a finite ring, STACS 2005. Springer Berlin Heidelberg, 2005, pp. 472-484.

Comments are closed.