Constant-round client-aided secure comparison protocol

Hiraku Morita, Nuttapong Attrapadung, Tadanori Teruya, Satsuya Ohata, Koji Nuida, Goichiro Hanaoka

Research output: Chapter in Book/Report/Conference proceedingConference contribution

15 Citations (Scopus)


We present an improved constant-round secure two-party protocol for integer comparison functionality, which is one of the most fundamental building blocks in secure computation. Our protocol is in the so-called client-server model, which is utilized in real-world MPC products such as Sharemind, where any number of clients can create shares of their input and distribute to the servers who then jointly compute over the shares and return the shares of result to the client. In the client-aided client-server model, as mentioned briefly by Mohassel and Zhang (S&P’17), a client further generates and distributes some necessary correlated randomness to servers. Such correlated randomness admits efficient protocols since otherwise servers have to jointly generate randomness by themselves, which can be inefficient. In this paper, we improve the state-of-the-art constant-round comparison protocols by Damgård et al. (TCC’06) and Nishide and Ohta (PKC’07) in the client-aided model. Our techniques include identifying correlated randomness in these comparison protocols. Along the way, we also use tree-based techniques for a building block, which deviate from the above two works. Our proposed protocol requires only 5 communication rounds, regardless of the bit length of inputs. This is at least 5 times fewer rounds than existing protocols. We implement our secure comparison protocol in C++. Our experimental results show that this low-round complexity benefits in low-latency networks such as WAN.

Original languageEnglish
Title of host publicationComputer Security - 23rd European Symposium on Research in Computer Security, ESORICS 2018, Proceedings
EditorsJianying Zhou, Miguel Soriano, Javier Lopez
PublisherSpringer Verlag
Number of pages21
ISBN (Print)9783319989884
Publication statusPublished - 2018
Externally publishedYes
Event23rd European Symposium on Research in Computer Security, ESORICS 2018 - Barcelona, Spain
Duration: Sept 3 2018Sept 7 2018

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume11099 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference23rd European Symposium on Research in Computer Security, ESORICS 2018

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Constant-round client-aided secure comparison protocol'. Together they form a unique fingerprint.

Cite this