The 2018 International Symposium on Information Theory and Its Applications (ISITA2018)
Tree-based Secure Comparison of Secret Shared Data
Hiraku Morita, Nuttapong Attrapadung, Satsuya Ohata, Shota Yamada, Koji Nuida, Goichiro Hanaoka,
A secure integer comparison protocol is one of the most fundamental building blocks to construct protocols of rich functionality in multi-party computation. It allows parties to compute the less-than functionality on shared values in privacy preserving manner. In this paper, we present a tree-based secure two-party comparison protocol in the client-aided client-server model, which outperforms existing approaches in terms of round complexity when it is used for 64-bit data. Our proposed protocol requires only 9 communication rounds to compare 64-bit data, which is at least 3 times fewer rounds than existing protocols. This suggests that our protocol is adequate to be used in lowlatency networks such as WAN.