Authors A.V. Trepacheva
Month, Year 08, 2014 @en
Index UDC 003.26.09
Abstract In this paper we analyze security issues of some symmetric homomorphic cryptosystems that are based on polynomial ring homomorphisms. We propose a method to recover a secret key of cryptosystem for plaintext space being a finite field Fq if several pairs (ciphertext, plaintext) were intercepted. For small values of q this method allows to find a correct key with probability ≈1, if the number of pairs is at least five. For large q two pairs are enough. We discuss how this method can be adapted for plaintext space being a set of integers modulo n, where n is a composite number. Also a method to correct the value of secret key computed using pairs (ciphertext, plaintexts) is discussed. It’s important for the case when the number of pairs is less than five. This method requires knowledge of probabilistic distribution over plaintext space and the presence of additional ciphertexts sequence encrypted on the same key. The method is successful with probability close to 1, if the distribution over plaintext space is not too close to uniform (for example, normal distribution with moderate dispersion).

Download PDF

Keywords Known plaintext attack; homomorphic encryption; cloud computations; polynomials.
References 1. Gentry C. A fully homomorphic encryption scheme: diss, Stanford University, 2009.
2. Van Dijk M. et al. Fully homomorphic encryption over the integers, Advances in Cryptology–EUROCRYPT 2010. Springer Berlin Heidelberg, 2010, pp. 24-43.
3. Brakerski Z., Vaikuntanathan V. Efficient fully homomorphic encryption from (standard) LWE, Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on, IEEE, 2011, pp. 97-106.
4. Gentry C., Sahai A., Waters B. Homomorphic encryption from learning with errors: Conceptually-simpler, asymptotically-faster, attribute-based, Advances in Cryptology–CRYPTO 2013. Springer Berlin Heidelberg, 2013, pp. 75-92.
5. Stehlй D., Steinfeld R. Faster fully homomorphic encryption, Advances in Cryptology-ASIACRYPT 2010. Springer Berlin Heidelberg, 2010, pp. 377-394.
6. Gentry C., Halevi S. Implementing gentry’s fully-homomorphic encryption scheme, Advances in Cryptology–EUROCRYPT 2011. Springer Berlin Heidelberg, 2011, pp. 129-148.
7. Zhirov A.O., Zhirova O.V., Krendelev S.F. Bezopasnye oblachnye vychisleniya s pomoshch'yu gomomorfnoy kriptografii, Bezopasnost' informatsionnykh tekhnologiy. 2013, Vol. 1, pp. 6-12.
8. Rostovtsev A., Bogdanov A., Mikhaylov M. Secure evaluation of polynomial using privacy ring homomorphisms, IACR Cryptology ePrint Archive, 2011, Vol. 2011, pp. 24.
9. Lidl R., Niderreiter H. Finite Fields (Vol. 20, Encyclopedia of Math. and its Appl.), Englewood Cliffs, NJ: Addison~ lVesley. 1983, pp. 74-85.
10. Klivans A. Factoring polynomials modulo composites. CARNEGIE-MELLON UNIV PITTSBURGH PA DEPT OF COMPUTER SCIENCE, 1997, No. CMU-CS-97-136.
11. Benjamin A.T., Bennett C.D. The probability of relatively prime polynomials, Mathematics Magazine, 2007, pp. 196-202.
12. Shoup V. NTL: A library for doing number theory, 2001.

Comments are closed.