1
$\begingroup$

I am trying to find a protocol for this problem:

Three persons, $A$, $B$, and $C$, know secret numbers $s_{A}, s_{B}$, and $s_{C}$, respectively. They want to know whether their numbers are all different, but none of them wants to reveal his number to any of the others.

If there are equal numbers between the three, this fact should be known, but no one shall discover which numbers are equal.

There is no trusted center (i.e. they can't use a fourth party doing calculations or similar), they only can communicate with each other.

Improve this question
$\endgroup$
8
  • $\begingroup$ actually, there is no fourth person to compare the values(trusted center), every thing should be done only between the three persons.. and therefore depending in your comment, if two numbers are equal then two of the persons will know which numbers are equal. $\endgroup$
    – user4252
    Commented Dec 11, 2012 at 21:02
  • $\begingroup$ Are they to communicate sequentially? Therefore the last party will be the one to report whether the secrets are equal? Or must everyone communicate with everyone else and each determine individually the (non)equivalence of their secrets? $\endgroup$
    – ampersand
    Commented Dec 11, 2012 at 21:05
  • $\begingroup$ For better understanding, can you give an example where such a protocol would be used? $\endgroup$
    – Paŭlo Ebermann
    Commented Dec 11, 2012 at 21:19
  • $\begingroup$ they communicate sequentially, and the last person may tell the others the result .... but i am also interested in protocols where everyone of them can communicate with everyone else ... $\endgroup$
    – user4252
    Commented Dec 11, 2012 at 21:20
  • 1
    $\begingroup$ @Sam When you say "If there are equal numbers between the three, this fact should be known, but no one shall discover which numbers are equal.", suppose A and B are the same age, do you mean it should be known that "there are two people in the group that have the same age", or that "A and B have the same age" (without disclosing their age, of course). $\endgroup$
    – Thomas
    Commented Dec 11, 2012 at 23:12

2 Answers 2

Reset to default
1
$\begingroup$

A minor extension of the dining cryptographers protocol ( a b ) can be used to reveal 1 bit of information: "all 3 keys are identical", or "at least 1 of the keys is different".

(If only 2 are identical, and the third is different, this protocol only indicates "at least 1 of the keys is different". So this doesn't completely answer your question, since it seems you want to reveal more information in that case).

4 persons A, B, C, and D sit around a circular table; each one knows the secret numbers sA, sB, sC, and sD.

There are also 4 fair coins on the table, halfway between each pair of neighbors: cAB, cBC, cCD, cDA.

One round goes something like this:

Each person generates a fresh new random number and announces it everyone else. Everyone combines the 4 new random numbers to generate a common random number R = rA xor rB xor rC xor rD.

Each person uses some cryptographic hash function to deterministically produce 1 bit hX from their secret number and the common random number, perhaps hA = least_significant_bit_of( SHA256( sA concatenate R ) ).

Each pair of neighbors secretly chooses a bit at random. In other words, A and B use the coin cAB between them to choose a bit at random, not telling anyone else what that bit is, and so on for the other 3 coins.

Each person calculates a message mX from their hX value and the bits from the coins to their left and right. In particular, D calculates mD = cCD xor sD xor cDA.

Then everyone announces their messages, and then computes the xor of all 4 announced messages: M = mA xor mB xor mC xor mD.

If everyone's secret value is the same, then M will always be zero for every round.

So as soon as M is calculated to be 1, everyone knows that "at least 1 of the keys is different".

If everyone's secret value is the different, then about half the time M will be 1 on the first round. And if everyone's secret value is different and they find M is 0 on the first round, then about half the time M will be 1 on the second round.

So you have to run through several times to gain confidence that the values really are the same.

The above protocol only directly applies when there is an even number of people around the table. If there is an odd number of people, then you could have each person pretend to be 2 people in the above protocol -- 3 people could pretend to be 6 people in the above protocol.

Improve this answer
$\endgroup$
2
$\begingroup$

You should easily be able to do this using a generic multi-party computation framework. For more info on what frameworks are available see Practical implementations of Multiparty computations.

From what I have seen, VIFF is pretty easy to get up and running to experiment with.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.