Paper 2021/1646

A Method for Securely Comparing Integers using Binary Trees

Anselme Tueno and Jonas Janneck


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)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
multi-party computationhomomorphic encryptioninteger comparison
Contact author(s)
anselme tueno @ sap com
jonas janneck @ sap com
2021-12-17: received
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.