We propose a solution to the secure integer comparison problem by reducing it to the secure set membership problem on a set where the elements occur in consecutive order. Our protocol provides flexibility due to this reduction such that it can easily be modified to support more complex boolean functions other than the function evaluating the 'Less Than' predicate (LT). In the paper we show one such boolean function, 'IsInInterval', which checks if an integer is in an interval (3I). We also show that our protocols can be easily extended to support shared outputs so that each party would hold a share of the result. Our generic solution can be applied to many e-commerce and data-mining applications requiring one or more such boolean functions to be computed securely. Our protocol not only is adaptable to different boolean functions but also is experimentally more efficient than the state-of-the-art integer comparison protocols supporting shared outputs.
We propose a solution to the secure integer comparison problem by reducing it to the secure set membership problem on a set where the elements occur in consecutive order. Our protocol provides flexibility due to this reduction such that it can easily be modified to support more complex boolean functions other than the function evaluating the 'Less Than' predicate (LT). In the paper we show one such boolean function, 'IsInInterval', which checks if an integer is in an interval (3I). We also show that our protocols can be easily extended to support shared outputs so that each party would hold a share of the result. Our generic solution can be applied to many e-commerce and data-mining applications requiring one or more such boolean functions to be computed securely. Our protocol not only is adaptable to different boolean functions but also is experimentally more efficient than the state-of-the-art integer comparison protocols supporting shared outputs.
Abstract We consider the problem of securely evaluating the Greater Than (GT) predicate and its extension – transferring one of two secrets, depending on the result of comparison. We generalize our solutions and show how to securely decide membership in the union of a set of intervals. We then consider the related problem of comparing two encrypted numbers. We show how to efficiently apply our solutions to practical settings, such as auctions with the semi-honest auctioneer, proxy selling, etc. All of our protocols are one round. We propose new primitives, Strong Conditional Oblivious Transfer (SCOT) and Conditional Encrypted Mapping (CEM), which capture common security properties of one round protocols in a variety of settings, which may be of independent interest.
Secure comparison is a fundamental problem in multiparty computation. There are two different parties, each holding an l-bit integer, denoted by a and b, respectively. The goal of secure comparison is to compute the order relationship between a and b, say (a>b)∈{0,1}, without revealing their inputs to any others. Since previous solutions based on homomorphic encryption need at least Ω(l) encryptions for each l-bit comparison, the total encryption time leads to a computational bottleneck for these protocols. This work presents a fast, semi-honest, secure comparison protocol based on the BFV encryption scheme. With its vector-like plaintext space, the number of required encryptions can be significantly reduced; actually, only six encryptions are needed for each comparison in our protocol. In other words, the proposed protocol can achieve the time complexity O˜(λ+l) for a given security parameter λ. As a result, 4096-bit integers can be securely compared within 12.08 ms, which is 280 times faster than the state-of-the-art homomorphic encryption-based secure comparison protocol. Furthermore, we can compare k pairs of l⋅k−1-bit integers with almost the same execution time as comparing l-bit integers and achieve higher throughput regardless of the compared integer size.
Secure two-party comparison plays a crucial role in many privacy-preserving applications, such as privacy-preserving data mining and machine learning. In particular, the available comparison protocols with the appropriate input/output configuration have a significant impact on the performance of these applications. In this paper, we firstly describe a taxonomy of secure two-party comparison protocols which allows us to describe the different configurations used for these protocols in a systematic manner. This taxonomy leads to a total of 216 types of comparison protocols.We then describe conversions among these types. While these conversions are based on known techniques and have explicitly or implicitly been considered previously, we show that a combination of these conversion techniques can be used to convert a perhaps less-known two-party comparison protocol by Nergiz et al. (IEEE SocialCom 2010) into a very efficient protocol in a configuration where the two parties hold shares of the values being compared, and obtain a share of the comparison result. This setting is often used in multi-party computation protocols, and hence in many privacy-preserving applications as well. We furthermore implement the protocol and measure its performance. Our measurement suggests that the protocol outperforms the previously proposed protocols for this input/output configuration, when off-line pre-computation is not permitted.
Secure two-party comparison plays a crucial role in many privacy-preserving applications, such as privacy-preserving data mining and machine learning. In particular, the available comparison protocols with the appropriate input/output configuration have a significant impact on the performance of these applications. In this paper, we firstly describe a taxonomy of secure two-party comparison protocols which allows us to describe the different configurations used for these protocols in a systematic manner. This taxonomy leads to a total of 216 types of comparison protocols. We then describe conversions among these types. While these conversions are based on known techniques and have explicitly or implicitly been considered previously, we show that a combination of these conversion techniques can be used to convert a perhaps less-known two-party comparison protocol by Nergiz et al. (IEEE SocialCom 2010) into a very efficient protocol in a configuration where the two parties hold shares of the values being compared, and obtain a share of the comparison result. This setting is often used in multi-party computation protocols, and hence in many privacy-preserving applications as well. We furthermore implement the protocol and measure its performance. Our measurement suggests that the protocol outperforms the previously proposed protocols for this input/output configuration, when off-line pre-computation is not permitted.
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 low-latency networks such as WAN.
It is becoming more and more important to make use of personal or classified information while keeping it confidential. A promising tool for meeting this challenge is secure multi-party computation (MPC). It enables multiple parties, each given a snippet of a secret s, to compute a function f(s) by communicating with each other without revealing s. However, one of the biggest problems with MPC is that it requires a vast amount of communication. Much research has gone into making each protocol (equality testing, interval testing, etc.) more efficient. In this work, we make a set of multiple protocols more efficient by transforming them into their equivalent batch processing form and propose two protocols: “Batch Logical OR” and “Batch Logical AND.” Using proposed protocols recursively, we also propose “Batch Logical OR-AND” and “Batch Logical AND-OR,” and show arbitrary formula consisting of Boolean protocols, OR gates, and AND gates can be batched. Existing logical OR and logical AND protocols consisting of t equality testing invocations have a communication complexity of O(lt), where l is the bit length of the secrets. Our batched versions of these protocols reduce it to O(l+t). For t interval testing invocations, they reduce both communication and round complexity. Thus they can make the queries on a secret shared database more efficient. For example, the use of the proposed protocols reduces the communication complexity for a query consisting of equality testing and interval testing by approximately 70% compared to the use of the corresponding existing protocols. The concept of the proposed protocols is versatile and can be applied to logical formulae consisting of protocols other than equality testing and interval testing, thereby making them more efficient as well.