Constant-Round Client-Aided Two-Server Secure Comparison Protocol and Its Applications

Hiraku MORITA  Nuttapong ATTRAPADUNG  Tadanori TERUYA  Satsuya OHATA  Koji NUIDA  Goichiro HANAOKA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E103-A    No.1    pp.21-32
Publication Date: 2020/01/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.2019CIP0023
Type of Manuscript: Special Section PAPER (Special Section on Cryptography and Information Security)
multi-party computation,  client-server model,  client-aided method,  less-than comparison,  constant rounds,  GMW secret sharing,  

Full Text: PDF(2MB)>>
Buy this Article

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 the 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 high-latency networks such as WAN. We also present secure Min/Argmin protocols using the secure comparison protocol.