Division between encrypted integers by means of garbled circuits

Available protocols for dividing encrypted numbers in a privacy preserving framework are quite onerous. Different solutions based on Homomorphic Encryption were proposed in the past years, but only a few of them - addressing specific cases - can be implemented efficiently so that division is often the bottleneck in protocols for privacy preserving computation. Moreover, no efficient solution for integer division between two secret values is available, thus making it difficult to compute the division between the result of previous computations whose output has to be kept secret to all the involved parties. In this paper we propose a novel solution for privacy preserving integer division that relies on Garbled Circuit theory. The protocol can be easily adapted to work with public, private and secret inputs and included in hybrid protocols wherein primitives relying on Homomorphic Encryption and Garbled Circuits coexist. We analyze the complexity of the new protocol, comparing it with existing homomorphic solutions. The execution time of a real implementation of the protocol is also provided. © 2011 IEEE.