Paper 2018/179 Original: eprint.iacr.org/2018/179 ↗

Efficient and Constant-Rounds Secure Comparison through Dynamic Groups and Asymmetric Computations

Abstract

Within recent years, secure comparison protocols have been proposed using binary decomposition and properties of algebraic fields. These have been repeatedly optimized and increased in efficiency, but have seemingly reached a plateau. We propose a new approach to this problem that takes advantage of dynamic group sizes for intermediate calculations and asymmetric computations among participating parties. As a consequence, according to our analysis, communication and computation costs have been brought to a very low and efficient level. Particularly, the communication costs have been considerably reduced both in order as well as the dominating term's order of magnitude. In addition, our proposed protocol requires no secure multi-party multiplication invocations in contrast to those required by the existing protocols, leading to inefficient constructions of secure comparisons.