A Method for Securely Comparing Integers using Binary Trees

Anselme Tueno and Jonas Janneck

Abstract

In this paper, we propose a new protocol for secure integer comparison which consists of parties having each a private integer. The goal of the computation is to compare both integers securely and reveal to the parties a single bit that tells which integer is larger. Nothing more should be revealed. To achieve a low communication overhead, this can be done by using homomorphic encryption (HE). Our protocol relies on binary decision trees that is a special case of branching programs and can be implemented using HE. We assume a client-server setting where each party holds one of the integers, the client also holds the private key of a homomorphic encryption scheme and the evaluation is done by the server. In this setting, our protocol outperforms the original DGK protocol of Damgård et al. and reduces the running time by at least 45%. In the case where both inputs are encrypted, our scheme reduces the running time of a variant of DGK by 63%.

Available format(s)
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
multi-party computationhomomorphic encryptioninteger comparison
Contact author(s)
anselme tueno @ sap com
jonas janneck @ sap com
History
Short URL
https://ia.cr/2021/1646

CC BY

BibTeX

@misc{cryptoeprint:2021/1646,
author = {Anselme Tueno and Jonas Janneck},
title = {A Method for Securely Comparing Integers using Binary Trees},
howpublished = {Cryptology ePrint Archive, Paper 2021/1646},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/1646}},
url = {https://eprint.iacr.org/2021/1646}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.