Paper 2022/1023

SIM: Secure Interval Membership Testing and Applications to Secure Comparison

Albert Yu, Purdue University West Lafayette
Donghang Lu, TikTok
Aniket Kate, Purdue University West Lafayette, Supra Research
Hemanta K. Maji, Purdue University West Lafayette

The offline-online model is a leading paradigm for practical secure multi-party computation (MPC) protocol design that has successfully reduced the overhead for several prevalent privacy-preserving computation functionalities common to diverse application domains. However, the prohibitive overheads associated with secure comparison -- one of these vital functionalities -- often bottlenecks current and envisioned MPC solutions. Indeed, an efficient secure comparison solution has the potential for significant real-world impact through its broad applications. This work identifies and presents SIM, a secure protocol for the functionality of interval membership testing. This security functionality, in particular, facilitates secure less-than-zero testing and, in turn, secure comparison. A key technical challenge is to support a fast online protocol for testing in large rings while keeping the precomputation tractable. Motivated by the map-reduce paradigm, this work introduces the innovation of (1) computing a sequence of intermediate functionalities on a partition of the input into input blocks and (2) securely aggregating the output from these intermediate outputs. This innovation allows controlling the size of the precomputation through a granularity parameter representing these input blocks' size -- enabling application-specific automated compiler optimizations. To demonstrate our protocols' efficiency, we implement and test their performance in a high-demand application: privacy-preserving machine learning. The benchmark results show that switching to our protocols yields significant performance improvement, which indicates that using our protocol in a plug-and-play fashion can improve the performance of various security applications. Our new paradigm of protocol design may be of independent interest because of its potential for extensions to other functionalities of practical interest.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Euro S&P 23
Secure Multiparty ComputationSecure Interval Membership TestingSecure ComparisonPrecomputed Function Tables
Contact author(s)
yu646 @ purdue edu
lu562 @ purdue edu
aniket @ purdue edu
hmaji @ purdue edu
2023-04-26: last of 3 revisions
2022-08-08: received
See all versions
Short URL
Creative Commons Attribution


      author = {Albert Yu and Donghang Lu and Aniket Kate and Hemanta K. Maji},
      title = {SIM: Secure Interval Membership Testing and Applications to Secure Comparison},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1023},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.