Authors Ph.B. Burtyka
Month, Year 08, 2014 @en
Index UDC 004.056.55: 003.26
Abstract This paper presents a new symmetric compact fully homomorphic encryption scheme, based on usage of matrix polynomials. Its encryption algorithm proceeds in two steps: at the first step plaintexts being elements of residue class ring are encoded into matrices using a secret vector k, then these matrices are mapped into matrix polynomials using secret irreducible matrix polynomial K(X). Decryption also proceeds in two steps: first reduction modulo K(X), and then obtained matrix is multiplied by k. Decryption function is a ring homomorphism. All algorithms of encryption scheme are polynomial in security parameter λ. Time overhead of homomorphic computations using this encryption scheme is also polynomial in  λ. Special refresh key that depends on secret key allows keeping sizes of ciphertexts during computations over them within a fixed polynomial in  λ bound. In real life implementation the cryptosystem enables effective parallelization. The paper analyzes the security of the proposed scheme against ciphertext only attack, known plaintext attack and refresh key attack. We demonstrate that all this attacks may be reduced to a problem of solving a system of polynomial equations over residue class ring. We discuss whether it is complex to solve it by existing methods.

Download PDF

Keywords Fully homomorphic encryption scheme; matrix polynomials; system of polynomial equations; known plaintext attack; secure cloud computing.
References 1. Rivest R.L., Adleman L., Dertouzos M. L. On data banks and privacy homomorphisms, Foundations of secure computation, 1978, Vol. 4, № 11, pp. 169-180.
2. Paillier P. Public-key cryptosystems based on composite degree residuosity classes, Advances in cryptology-EUROCRYPT’99. Springer Berlin Heidelberg, 1999, pp. 223-238.
3. Rivest R. L., Shamir A., Adleman L. A method for obtaining digital signatures and public-key cryptosystems, Communications of the ACM, 1983, Vol. 26, No. 1, pp. 96-99.
4. Gentry C. Fully homomorphic encryption using ideal lattices, STOC, 2009, Vol. 9, pp. 169-178.
5. Vaikuntanathan V. Computing blindfolded: New developments in fully homomorphic encryption, Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on IEEE, 2011, pp. 5-16.
6. Gentry C., Halevi S. Fully homomorphic encryption without squashing using depth-3 arithmetic circuits, Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on IEEE, 2011, pp. 107-109.
7. Jing-Li H., Ming Y., Zhao-Li W. Fully homomorphic encryption scheme extended to large message space, Instrumentation, Measurement, Computer, Communication and Control, International Conference on IEEE, 2011. pp. 533-536.
8. Alperin-Sheriff J., Peikert C. Practical bootstrapping in quasilinear time, Advances in Cryptology–CRYPTO 2013. Springer Berlin Heidelberg, 2013, pp. 1-20.
9. Alperin-Sheriff J., Peikert C. Faster Bootstrapping with Polynomial Error, IACR Cryptology ePrint Archive, 2014, Vol. 2014, pp. 94.
10. Orsini E., van de Pol J., Smart N.P. Bootstrapping BGV Ciphertexts With A Wider Choice of p and q.
11. Smart N.P., Vercauteren F. Fully homomorphic SIMD operations, Designs, codes and cryptography, 2014, Vol. 71, No. 1, pp. 57-81.
12. Stehlй D., Steinfeld R. Faster fully homomorphic encryption, Advances in Cryptology-ASIACRYPT 2010. Springer Berlin Heidelberg, 2010, pp. 377-394.
13. Brakerski Z., Gentry C., Vaikuntanathan V. (Leveled) fully homomorphic encryption without bootstrapping, Proceedings of the 3rd Innovations in Theoretical Computer Science Conference. ACM, 2012, pp. 309-325.
14. Bogdanov A., Lee C. H. Limits of provable security for homomorphic encryption, Advances in Cryptology–CRYPTO 2013. Springer Berlin Heidelberg, 2013, pp. 111-128.
15. Domingo-Ferrer J. A Provably Secure Additive and Multiplicative Privacy Homomorphism, Information Security. Springer Berlin Heidelberg, 2002, pp. 471-483.
16. Hojsнk M., Půlpбnovб V. A fully homomorphic cryptosystem with approximate perfect secrecy, Topics in Cryptology–CT-RSA 2013. Springer Berlin Heidelberg, 2013, pp. 375-388.
17. Gel'fand S.I. O chisle resheniy kvadratnogo uravneniya [The number of solutions of a quadratic equation], Izdanie osushchestvleno pri podderzhke RFFI (izdatel'skiy proekt № 01-01-14022). 2004, pp. 124.
18. Knut D. Iskusstvo programmirovaniya [The art of computer programming]. T. 2. Poluchislennye algoritmy [Poluchyennyye algorithms]. St. Petersburg: Vil'yams, 2007, 788 p.
19. Williams V.V. Multiplying matrices faster than Coppersmith-Winograd, Proceedings of the forty-fourth annual ACM symposium on Theory of computing. ACM, 2012, pp. 887-898.
20. Olsson R.A., Keen A.W. Parallel Matrix Multiplication, The JR Programming Language: Concurrent Programming in an Extended Java. 2004, pp. 211-225.
21. Schaefer T.J. The complexity of satisfiability problems, Proceedings of the tenth annual ACM symposium on Theory of computing. ACM, 1978, pp. 216-226.
22. Bard G. Algebraic cryptanalysis. Springer, 2009.
23. Gao X.S., Huang Z. Characteristic set algorithms for equation solving in finite fields, Journal of Symbolic Computation, 2012, Vol. 47, No. 6, pp. 655-679.

Comments are closed.