wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> compare secret numbers
        
(Message started by: cuckoo on Feb 16th, 2009, 6:34pm)
Title: compare secret numbers
Post by cuckoo on Feb 16th, 2009, 6:34pm
Alice and Bob want to know who is older, but they don't want to let the other one know their real age. please propse a scheme.
Title: Re: compare secret numbers
Post by towr on Feb 17th, 2009, 1:29am
A trusted third party would sure make it easy.

They could probably find a number that falls in between their ages, but that might still give away quite a bit of information. For example, say they are 30 and 35, and we use a binary search:
50 : both younger
25 : both older
37 : both younger
31 : A is younger, B is older.
But we know much more than which is the older one, A is between 25 and 31, B between 31 and 37. Even if our first guess had been 31, more information would have been disclosed than we'd want.
Title: Re: compare secret numbers
Post by Grimbal on Feb 17th, 2009, 2:49am
A and B each prepare a tin box containing one lump of sugar for each year of age.  Then they compare the boxes on a 2-pan scale.
Title: Re: compare secret numbers
Post by cuckoo on Feb 19th, 2009, 12:37am
Yes, your method is practically good. But if the box is not trustworthy?(for example, somebody secretly put a cmemra in the box).
I think, only if your real age do not pop out from your head, it can be thought as safe.


on 02/17/09 at 02:49:18, Grimbal wrote:
A and B each prepare a tin box containing one lump of sugar for each year of age.  Then they compare the boxes on a 2-pan scale.
Title: Re: compare secret numbers
Post by Eigenray on Feb 19th, 2009, 1:49am
This is the millionaire's problem.

Here is one method: suppose Alice and Bob want to determine the value of F(a,b), where F is some function on a finite set S x S.  Let E,D be a public-key cryptographic system: D(E(x)) = x; anyone can compute E, but only Bob can compute D.  Let H be a hash.

The idea is: [hide]Bob sends F(i,b) for all i, but encoded in such a way that Alice can only decode the value F(a,b)[/hide].

Alice: [hide]Picks a random number x and sends Bob the value X = E(x) - a[/hide].
Bob: [hide]Sends the sequence Yi = H(D(X+i)) + F(i,b), for each i in S[/hide].
Alice: Computes F(a,b) = [hide]Ya - H(x)[/hide]
Title: Re: compare secret numbers
Post by cuckoo on Feb 19th, 2009, 2:06am
handsome! :o


on 02/19/09 at 01:49:10, Eigenray wrote:
This is the millionaire's problem.

Here is one method: suppose Alice and Bob want to determine the value of F(a,b), where F is some function on a finite set S x S.  Let E,D be a public-key cryptographic system: D(E(x)) = x; anyone can compute E, but only Bob can compute D.  Let H be a hash.

The idea is: [hide]Bob sends F(i,b) for all i, but encoded in such a way that Alice can only decode the value F(a,b)[/hide].

Alice: [hide]Picks a random number x and sends Bob the value X = E(x) - a[/hide].
Bob: [hide]Sends the sequence Yi = H(D(X+i)) + F(i,b), for each i in S[/hide].
Alice: Computes F(a,b) = [hide]Ya - H(x)[/hide]
Title: Re: compare secret numbers
Post by R on Apr 14th, 2009, 4:38am

on 02/19/09 at 01:49:10, Eigenray wrote:
This is the millionaire's problem.

Here is one method: suppose Alice and Bob want to determine the value of F(a,b), where F is some function on a finite set S x S.  Let E,D be a public-key cryptographic system: D(E(x)) = x; anyone can compute E, but only Bob can compute D.  Let H be a hash.

The idea is: [hide]Bob sends F(i,b) for all i, but encoded in such a way that Alice can only decode the value F(a,b)[/hide].

Alice: [hide]Picks a random number x and sends Bob the value X = E(x) - a[/hide].
Bob: [hide]Sends the sequence Yi = H(D(X+i)) + F(i,b), for each i in S[/hide].
Alice: Computes F(a,b) = [hide]Ya - H(x)[/hide]

In Public key cryptograph, D(E(x)) = x this condition holds. Is this also true: E(D(x)) = x?
I mean after generating E and D from RSA algorithm, one can choose anyone of E or D to be his public key and the other one private key.

Right??
Title: Re: compare secret numbers
Post by Eigenray on Apr 14th, 2009, 5:58am

on 04/14/09 at 04:38:11, R wrote:
In Public key cryptograph, D(E(x)) = x this condition holds. Is this also true: E(D(x)) = x?
I mean after generating E and D from RSA algorithm, one can choose anyone of E or D to be his public key and the other one private key.

In RSA, yes.  But the actual cryptosystem used doesn't matter, as long as D(E(x))=x and Alice can't compute D (otherwise she could determine Bob's number.)

But there are some cryptosystems that have an element of randomness to the encryption process (e.g., ElGamal, or systems based on solving the word problem for groups).  Then E isn't really a well-defined function, but we can still say D(E(x))=x, even though E(D(x))=x doesn't really make sense.
Title: Re: compare secret numbers
Post by R on Apr 14th, 2009, 7:12am

on 02/19/09 at 01:49:10, Eigenray wrote:
This is the millionaire's problem.

Here is one method: suppose Alice and Bob want to determine the value of F(a,b), where F is some function on a finite set S x S.  Let E,D be a public-key cryptographic system: D(E(x)) = x; anyone can compute E, but only Bob can compute D.  Let H be a hash.

The idea is: [hide]Bob sends F(i,b) for all i, but encoded in such a way that Alice can only decode the value F(a,b)[/hide].

Alice: [hide]Picks a random number x and sends Bob the value X = E(x) - a[/hide].
Bob: [hide]Sends the sequence Yi = H(D(X+i)) + F(i,b), for each i in S[/hide].
Alice: Computes F(a,b) = [hide]Ya - H(x)[/hide]

Ok.
Don't you think your method will be computationally expensive, in-efficient in terms of number of messages sent to Alice, the computation done by Bob?
Here the question is to compare the ages, so there will be around 100 numbers in the sequence of Yi. But if they want to compare some other value (say their bank balance, or some ID) which can be large (say in millions), then there will be million values in the sequence, and Bob will have to do a lot of computation. His steps for each value of i will be:
1. Add X to i
2. Decrypt it with D (very slow process)
3. Calculate the Message Digest using one way Hash function H (Also slow)
4. Add the result of F(i,b) to H(D(X+i))

Step 2 and 3 will make the process slow.
Is there any better solution for this? I am working on it.
Title: Re: compare secret numbers
Post by Eigenray on Apr 14th, 2009, 3:33pm

on 04/14/09 at 07:12:57, R wrote:
Ok.
Don't you think your method will be computationally expensive, in-efficient in terms of number of messages sent to Alice, the computation done by Bob?

Yes, I do.  It's essentially Yao's original solution; see the description [link=http://www.proproco.co.uk/million.html]here[/link].  But there are efficient methods that are linear in the number of bits.
Title: Re: compare secret numbers
Post by idontknow on Apr 14th, 2009, 10:53pm
Hey Eigenray, I think the problem with title "Bourne Ultimatum, also is in line with the current problem (though not very similar).

Can you try and tell if you can solve it using Public-key Cryptography
Title: Re: compare secret numbers
Post by oldspy on May 15th, 2009, 4:25pm
It says they don't want the other to know the real age, but other info may be OK to give such as older than 20 or younger than 50. If this assumption is right, use binary search will solve it.



1. Set lower = 1 and upper = 250 (no one is that old I guess), and choose any positive number between these two. Ask Alice and Bob if they are older, younger, not older or not younger than it. If their answer can determine who is older, stop.
2. If not, figure out the next trial age:
 1) If they answer either older or "not younger", update lower to this number, and try a number lower and new upper.
 2) If they answers either younger or "not older", set upper to this number, and try a smaller number between lower and the new upper.
3. Continue until their answer can determine who is older.
Title: Re: compare secret numbers
Post by R on May 15th, 2009, 10:09pm

on 05/15/09 at 16:25:33, oldspy wrote:
It says they don't want the other to know the real age, but other info may be OK to give such as older than 20 or younger than 50. If this assumption is right, use binary search will solve it.

Read towr's reply#1. He has pointed out the problem. Also there are some cases where in binary search they will be able to find out each other's actual ages. Example:
Alice(16) Bob(18.)
start with 1 and 60....
mid = 30 (both younger)
mid = 15 (both elder)
mid = 23 (both younger)
mid = 19 (both younger)
mid = 17 (Alice younger and bob elder)

now Bob knows that Alice's age is >15 and <17 implies it's 16
similarly Alice knows that bob's age is >17 and <19..implies it's 18
Title: Re: compare secret numbers
Post by justicezyx on May 20th, 2009, 7:08pm
how about add a constant to both of their ages?...
Title: Re: compare secret numbers
Post by R on May 20th, 2009, 9:40pm

on 05/20/09 at 19:08:46, justicezyx wrote:
how about add a constant to both of their ages?...

They still need to have the constant shared, and as long as they both know it, it is useless.


Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board