Title: Encrypted integer division and secure comparison

Authors: Thijs Veugen

Addresses: Multimedia Signal Processing Group, Delft University of Technology, The Netherlands; Technical Sciences, TNO, P.O. Box 5050, 2600 GB Delft, The Netherlands

Abstract: When processing data in the encrypted domain, homomorphic encryption can be used to enable linear operations on encrypted data. Integer division of encrypted data however requires an additional protocol between the client and the server and will be relatively expensive. We present new solutions for dividing encrypted data in the semi-honest model using homomorphic encryption and additive blinding, having low computational and communication complexity. In most of our protocols we assume the divisor is publicly known. The division result is not only computed exactly, but may also be approximated leading to further improved performance. The idea of approximating the result of an integer division is extended to similar results for secure comparison, secure minimum, and secure maximum in the client-server model, yielding new efficient protocols with demonstrated application in biometrics. The exact minimum protocol is shown to outperform existing approaches.

Keywords: homomorphic encryption; integer division; secure comparison; secure minimum; secure maximum; approximation; client-server model; secure multi-party computations; cryptography; additive blinding; security.

DOI: 10.1504/IJACT.2014.062738

International Journal of Applied Cryptography, 2014 Vol.3 No.2, pp.166 - 180

Accepted: 24 Dec 2013
Published online: 16 Aug 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article