%0 Conference Proceedings
%T Linear Depth Integer-Wise Homomorphic Division
%+ KDDI R&D Laboratories Inc. [Saitama]
%+ Royal Holloway [University of London] (RHUL)
%A Okada, Hiroki
%A Cid, Carlos
%A Hidano, Seira
%A Kiyomoto, Shinsaku
%Z Part 3: Cryptography
%< avec comité de lecture
%( Lecture Notes in Computer Science
%B 12th IFIP International Conference on Information Security Theory and Practice (WISTP)
%C Brussels, Belgium
%Y Olivier Blazy
%Y Chan Yeob Yeun
%I Springer International Publishing
%3 Information Security Theory and Practice
%V LNCS-11469
%P 91-106
%8 2018-12-10
%D 2018
%R 10.1007/978-3-030-20074-9_8
%K Fully homomorphic encryption
%K HElib
%K Secure integer arithmetic
%K Circuit depth
%Z Computer Science [cs]Conference papers
%X We propose a secure integer-wise homomorphic division algorithm on fully homomorphic encryption schemes (FHE). For integer-wise algorithms, we encrypt plaintexts as integers without encoding them into bit values, while in bit-wise algorithms, plaintexts are encoded into binary and bit values are encrypted one by one. All the publicly available division algorithms are constructed in bit-wise style, and to the best of our knowledge there are no known integer-wise algorithm for secure division. We derive some empirical results on the FHE library HElib and show that our algorithm is 2.45x faster than the fastest bit-wise algorithm. We also show that the multiplicative depth of our algorithm is O(l), where l is the integer bit length, while that of existing division algorithms is $$O(l^2)$$. Furthermore, we generalise our secure division algorithm and propose a method for secure calculation of a general 2-variable function. The order of multiplicative depth of the algorithm, which is a main factor of the complexity of a FHE algorithm, is exactly the same as our secure division algorithm.
%G English
%Z TC 11
%Z WG 11.2
%2 https://hal.science/hal-02294597/document
%2 https://hal.science/hal-02294597/file/484602_1_En_8_Chapter.pdf
%L hal-02294597
%U https://hal.science/hal-02294597
%~ IFIP-LNCS
%~ IFIP
%~ IFIP-TC
%~ IFIP-TC11
%~ IFIP-WISTP
%~ IFIP-WG11-2
%~ IFIP-LNCS-11469