# secure integer comparison

I have been going through a huge amount of papers to find a simple and a practical method to compare integer numbers without revealing their original values. I know that this falls within the area of secure multi party communication framework. However, I have very limited knowledge in cryptography and I can not really understand much of what the papers explains.

I have already tested the viff (viff.dk/‎) framework but the computation cost is quite high to compare just 5 numbers (about 500 milliseconds). I am looking for a solution with minimum security guarantees but low computation overhead. I would be grateful if someone point out a simple solution to start with or even an implementation which I can use. I know that my question may seem quite general, but I am kind of lost here and any pointers would help.

-------UPDATE--------

We would like to compare offers of different ISPs (internet service providers) in order to provide the best service to a customer (bidding). The ISPs don't want their offers to be revealed to the other ISPs but they want to know which one of them wins (the one with the best offer). They don't want to use a third party to do the comparison, they want to do it in a multi party fashion. The information provided by the ISPs currently is just a single integer of 8-bits length. The goal is to find the biggest integer. I don't know if this include multiple operations or just a single one !! ... And I guess it needs inequalities ... since this comparison needs to be done as fast as possible within 10th of milliseconds and we assume that the ISPs would be mostly honest, we are looking for as simple and as practical as possible protocol to do it. Our concern is is speed more than the security.

• Multiparty computation requires multiple parties (as the name implies). Since you haven't told us much about your application scenario, it is hard to know if the MPC paradigm is correct. Do you need other operations besides comparison? – mikeazo Mar 20 '14 at 17:45
• – user991 Mar 20 '14 at 23:57
• Is it OK to reveal the offer of the winning ISP (the one with the best offer), in identity to the winning ISP? Do you care more about computation time or latency (total time)? Is it OK to do an interactive computation that involves many round of interaction if this keeps the computation time down? – D.W. Mar 21 '14 at 6:06

I would suggest looking into sharemind. Their setup is a little different from VIFF, there are 3 computation servers and everyone shares their inputs with the computation servers. As long as the computation servers don't collude, privacy is guaranteed. They have also optimized many things. So it may work better for you.

That said, there are some optimizations you could do to VIFF to make things faster. I believe VIFF does comparison by splitting the shared secrets into shares of bits of the secrets. In otherwords, if you were sharing 8-bit integers, then instead you would have 8 sharings of the individual bits of each input. Splitting the shares is a costly operation, but once you have shares of the bits, comparison isn't too bad. So, you could just have the parties share the bits in the first place.

If you want to minimize computation time and are willing to use a protocol that involves many rounds of interaction, and if it is OK to disclose the offer of the winning ISP (not just its identity) and of all other ISPs that tied with it, here is one protocol. In an initial phase, each ISP does the following:

1. Convert the 8-bit value $x$ to a $2^8$-bit string $y$, where $y=1^x 0^{256-x}$, i.e., $y$ starts with $x$ ones and the rest is all zeros.

2. Broadcast commitments to the bits of $y$, namely, $C(y_0),C(y_1),\dots,C(y_{255})$.

Once all of the ISPs have broadcast their commitments, we proceed with up to 256 rounds. In the $i$th round, we do the following:

1. Each ISP opens up its commitment to $y_{255-i}$. Everyone checks that the commitments were opened properly.

2. If all of opened bits are $0$, then we continue on to the next round.

3. Alternatively, if one or more of the bits are $1$, we stop here. The ISP (or ISPs) whose bit was $1$ has "won" the auction. Now everyone knows the identity of the "winning" ISP. That ISP now provides the service to the customer.

Note that everyone also learns the amount offered by the winning ISP, so you'll have to decide whether this is OK.

This protocol requires very little computation. Unfortunately, this protocol requires up to 256 rounds of interaction, which may cause very high latencies in real life if the ISPs are distributed (e.g., they don't all have servers on the same subnet or in the same data center). Therefore, I suspect this protocol probably will not be competitive in a wide-area distributed system. However, I thought I'd mention it just in case.

If this is not useful, you could look at using any of the constructions for multiparty computation or garbled circuits. The circuit you are computing is relatively simple (doesn't require very many gates), so it might be fairly easy to compute it. See, e.g., Might Be Evil, FairPlay (an older system), and other libraries.

For two players, quid-pro-quo-tocols from Might Be Evil might be very attractive: it gives a scheme that is about twice as slow as the standard constructions in the honest-but-curious model, but that provides darn good security. So, this is a very attractive security-to-performance tradeoff: darn good security (not perfect, but within at most 1 bit of perfect), with performance that is excellent. I don't know if that scheme generalizes to an arbitrary number of players.

• revealing the winner ISP and its offer is fine for us, however, as you mentioned the number of rounds is high for wide area networks, I was wondering if you are aware of any other protocol which achieves the same purpose but with less rounds ? also, could you point out a reference to this protocol, maybe I could use it as a starting point to search further, Thanks. – ahmed Mar 24 '14 at 10:28
• @ahmed, alas, I don't know of a reference for this protocol, and unfortunately I don't know anything better -- sorry about that -- but if you want to explore further, it might be worth taking a look at the protocol I mention in the last paragraph. – D.W. Mar 28 '14 at 2:47