METHOD OF IMPLEMENTING HOMOMORPHIC DIVISION
Abstract
The article deals with the problems of homomorphic cryptography. Homomorphic cryptography
is one of the young directions of cryptography. Its peculiarity lies in the fact that it is possible
to process encrypted data without preliminary decryption in such a way that the result of operations
on encrypted data is equivalent, after decryption, to the result of operations on open data.
The article provides a brief overview of the areas of application of homomorphic encryption. To
solve various applied problems, support for all mathematical operations is required, including the
division operation, and the ability to perform this operation homomorphically will expand the
possibilities of using homomorphic encryption. The paper proposes a method of homomorphic
division based on an abstract representation of the ciphertext in the form of an ordinary fraction.
The paper describes in detail the proposed method. In addition, the article contains an example of
the practical implementation of the proposed method. It is proposed to divide the levels of data
processing into 2 levels – cryptographic and mathematical. At the cryptographic level, a completely homomorphic encryption algorithm is used and the basic homomorphic mathematical operations
are performed – addition, multiplication and difference. The mathematical level is a superstructure
on top of the cryptographic level and expands its capabilities. At the mathematical level,
the ciphertext is represented as a simple fraction and it becomes possible to perform the
homomorphic division operation. The paper also provides a practical example of applying the
homomorphic division method based on the Gentry algorithm for integers. Conclusions and possible
ways of further development are given.
References
of secure computation, 1978, Vol. 32, No. 4, pp. 169-178.
2. Gentry C. A fully homomorphic encryption scheme, A dissertation submitted to the department
of computer science and the committee on graduate students of Standford University,
2009.
3. Diffie W. and Hellman M. New directions in cryptography, IEEE Transactions on Information
Theory, 1976, Vol. IT-22, pp. 644-654.
4. Gentry C. Fully homomorphic encryption using ideal lattices, STOC, 2009, pp. 169-178.
5. Rivest R., Adleman L., Dertouzos M. On data banks and privacy homomorphisms, Foundations
of Secure Computation. Academic Press, 1978, pp. 169-177.
6. Goldwasser S., Micali S. Probabilistic encryption, Journal of Computer and System Sciences,
1984, Vol. 28, No. 2, pp. 270-299.
7. Babenko L.K., Burtyka F.B., Makarevich O.B., Trepacheva A.V. Metody polnost'yu
gomomorfnogo shifrovaniya na osnove matrichnykh polinomov [Methods of fully
homomorphic encryption based on matrix polynomials], Voprosy kiberbezopasnosti
[Cybersecurity issues], 2015, No. 1, pp. 17-20.
8. Babenko L.K., Burtyka F.B., Makarevich O.B., Trepacheva A.V. Polnost'yu gomomorfnoe
shifrovanie (obzor) [Fully Homomorphic Encryption (Overview)], Voprosy zashchity
informatsii [Information Security Issues], 2015, No. 3, pp. 3-26.
9. Babenko L.K., Burtyka F.B., Makarevich O.B., Trepacheva A.V. Zashchishchennye
vychisleniya i gomomorfnoe shifrovanie [Secure computing and homomorphic encryption],
Programmnye sistemy: teoriya i prilozheniya [Software systems: theory and applications],
2014, 25 p.
10. Makarevich O.B., Burtyka F.B. Zashchishchennaya oblachnaya baza dannykh s primeneniem
gomomorfnoy kriptografii [Secure cloud database using homomorphic cryptography], Tez.
dokl. 6-y Ross. mul'tikonferentsii «Informatsionnye tekhnologii v upravlenii» (ITU–2014)
[Proceedings of 6th Russian multiconference «Information Technologies in Control»
(ITU-2014). Saint Petersburg, 2014, pp. 567-572.
11. Burtyka F.B. Paketnoe simmetrichnoe polnost'yu gomomorfnoe shifrovanie na osnove
matrichnykh polinomov [Batch symmetric fully homomorphic encryption based on matrix
polynomials], Tr. Instituta sistemnogo programmirovaniya RAN [Proceedings of the Institute
for System Programming RAS], 2014, Vol. 26, No. 5, pp. 99-116.
12. Burtyka F.B. Simmetrichnoe polnost'yu gomomorfnoe shifrovanie s ispol'zovaniem
neprivodimykh matrichnykh polinomov [Symmetric fully homomorphic encryption using irreducible
matrix polynomials], Izvestiya YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering
Sciences], 2014, No. 8 (157), pp. 107-122.
13. Trepacheva A.V. Kriptoanaliz simmetrichnykh polnost'yu gomomorfnykh lineynykh
kriptosistem na osnove zadachi faktorizatsii chisel [Cryptanalysis of symmetric fully
homomorphic linear cryptosystems based on the number factorization problem], Izvestiya
YuFU. Tekhnicheskie nauki [Izvestiya SFedU. Engineering Sciences], 2015, No. 5 (166),
pp. 89-102.
14. Brakerski Vaikuntanathan. Efficient fully homomorphic encryption from (standard) LWE,
FOCS, 2011.
15. Rao G.V., Kakulapati V., Purushoththaman M. Privacy homomorphism in mobile ad hoc networks,
International Journal of Research & Reviews in Computer Science, 2011.
16. Zhirov A.O., Zhirova A.O., Krendelev S.F. Bezopasnye oblachnye vychisleniya s pomoshch'yu
gomomorfnoy kriptografii [Secure Cloud Computing with Homomorphic Cryptography],
Bezopasnost' informatsionnykh tekhnologiy [Information technology security], 2013, № 1, pp. 6-12.
17. Regev O. New lattice-based cryptographic constructions, J. ACM, 2004, Vol. 51, No. 6,
pp. 899-942.
18. Regev O. On lattices, learning with errors, random linear codes, and cryptography, STOC,
2005, pp. 84-93.
19. Helib. Available at: https://github.com/homenc/HElib (accessed 01 June 2020).
20. FHEW. Available at: https://github.com/lducas/FHEW (accessed 01 June 2020).
21. Gentry C., Halevi S. Implementing gentry’s fully-homomorphic encryption scheme,
EUROCRYPT, ser. Lecture Notes in Computer Science, K.G. Paterson, Ed.,Vol. 6632. Springer,
2011, pp. 129-148.
22. Dijk M., Gentry C., Halevi S., Vaikuntanathan V. Fully Homomorphic Encryption over the
Integers, Eurocrypt, 2010.
