Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I already found a protocol to find between two party who is richer (older), but Is there any protocol to find the youngest person among 3 parties, without revealing actual ages?

share|improve this question
    
i am not sure which one you have, but intuitively, can think of a reduction with $money \equiv \frac{1}{age}$? –  Subhayan May 8 at 17:30
1  
@Subhayan : $\:$ That ignores the main issue, which is going from 2 to 3 parties. $\hspace{1.67 in}$ –  Ricky Demer May 8 at 17:34
1  
That would reveal too much information. $\;$ –  Ricky Demer May 8 at 17:35
2  
What security properties do you need? Specifically: active or passive security? Fairness? –  mikeazo May 8 at 18:00
1  
Also, if there's a tie for the youngest, should it give them all or break the tie at random? $\hspace{1.15 in}$ –  Ricky Demer May 8 at 18:03
show 3 more comments

1 Answer 1

There might be better ways to do this, but I wanted to do it with only primitives found in VIFF (why? because it is the MPC framework I am most familiar with). There could be specialized protocols which are better.

In VIFF, we have access a primitive >= which returns 0 or 1 (false or true). We can do the comparison you seek using that plus some simple arithmetic on secret shared values. I think these are all passive protocols and do not guarantee fairness (if fairness even makes sense in the passive world).

Let the three parties be alice, bob and charlie. They have each secret shared their ages with the others. We'll let a,b,c be the variables that represent the secret shared ages.

We can compute who is the youngest as follows:


ab = (b>=a) # is a younger than b?
ba = 1-ab # is b younger than a?
ac = (c>=a) # is a younger than c?
ca = 1-ac # is c younger than a?
bc = (c>=b) # is b younger than c?
cb = 1-bc # is c younger than b?

a_score = ab + ac
b_score = ba + bc
c_score = ca + cb

# At this point we are guaranteed to have a score of 2, a score of 1, and a score of 0.
# Whoever has the score of 2 is the youngest.
reveal(a_score>=2) # if this is 1, then Alice is youngest
reveal(b_score>=2) # if this is 1, then Bob is youngest
reveal(c_score>=2) # if this is 1, then Charlie is youngest

This computation only reveals who is the youngest. It does not reveal ages or the overall order. It requires 6 calls to >=. This will also only return 1 person as youngest. To get all of the youngest, you would replace the 2nd, 4th, and 6th lines with another >= instead of a 1-XX.

share|improve this answer
    
how do you compute ab? do you assume a third party or the Millionaire Solution OP was talking about? –  Subhayan May 8 at 18:53
    
I'm assuming a secure >= comparison function like what is implemented in VIFF. I don't think taking a simple 2-party millionaire solution will work. –  mikeazo May 8 at 18:58
    
Regarding fairness&passiveness, one could restrict to adversaries whose only misbehavior is aborting partway through the protocol run. $\;$ –  Ricky Demer May 8 at 19:07
    
I don't know this MPC framework, but the millionaire's problem is just one example for MPC, and you can proceed in a similar way: Express the algorithm as a circuit, then use methods like garbled circuits and oblivious transfer for the execution. –  tylo May 15 at 14:48
    
@tylo, correct me if I am wrong, but aren't garbled circuits typically only used for 2 party computation? I think there are constructions for more than 2 party computation which use garbled circuits, but they tend to be less efficient than secret sharing based constructions. –  mikeazo May 15 at 15:29
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.