Author |
Topic: compare secret numbers (Read 1082 times) |
|
cuckoo
Junior Member
Gender: 
Posts: 57
|
 |
compare secret numbers
« on: Feb 16th, 2009, 6:34pm » |
 Quote  Modify
|
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.
|
|
 IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: compare secret numbers
« Reply #1 on: Feb 17th, 2009, 1:29am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: compare secret numbers
« Reply #2 on: Feb 17th, 2009, 2:49am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
cuckoo
Junior Member
Gender:
Posts: 57
|
|
Re: compare secret numbers
« Reply #3 on: Feb 19th, 2009, 12:37am » |
Quote Modify
|
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 Feb 17th, 2009, 2:49am, 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. |
|
|
|
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: compare secret numbers
« Reply #4 on: Feb 19th, 2009, 1:49am » |
Quote Modify
|
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: Bob sends F(i,b) for all i, but encoded in such a way that Alice can only decode the value F(a,b).
Alice: Picks a random number x and sends Bob the value X = E(x) - a.
Bob: Sends the sequence Yi = H(D(X+i)) + F(i,b), for each i in S.
Alice: Computes F(a,b) = Ya - H(x)
|
| « Last Edit: Feb 19th, 2009, 1:52am by Eigenray » |
IP Logged |
|
|
|
cuckoo
Junior Member
Gender:
Posts: 57
|
|
Re: compare secret numbers
« Reply #5 on: Feb 19th, 2009, 2:06am » |
Quote Modify
|
handsome! 
on Feb 19th, 2009, 1:49am, 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: Bob sends F(i,b) for all i, but encoded in such a way that Alice can only decode the value F(a,b).
Alice: Picks a random number x and sends Bob the value X = E(x) - a.
Bob: Sends the sequence Yi = H(D(X+i)) + F(i,b), for each i in S.
Alice: Computes F(a,b) = Ya - H(x) |
|
|
|
IP Logged |
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: compare secret numbers
« Reply #6 on: Apr 14th, 2009, 4:38am » |
Quote Modify
|
on Feb 19th, 2009, 1:49am, 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: Bob sends F(i,b) for all i, but encoded in such a way that Alice can only decode the value F(a,b).
Alice: Picks a random number x and sends Bob the value X = E(x) - a.
Bob: Sends the sequence Yi = H(D(X+i)) + F(i,b), for each i in S.
Alice: Computes F(a,b) = Ya - H(x) |
|
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??
|
|
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: compare secret numbers
« Reply #7 on: Apr 14th, 2009, 5:58am » |
Quote Modify
|
on Apr 14th, 2009, 4:38am, 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.
|
|
IP Logged |
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: compare secret numbers
« Reply #8 on: Apr 14th, 2009, 7:12am » |
Quote Modify
|
on Feb 19th, 2009, 1:49am, 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: Bob sends F(i,b) for all i, but encoded in such a way that Alice can only decode the value F(a,b).
Alice: Picks a random number x and sends Bob the value X = E(x) - a.
Bob: Sends the sequence Yi = H(D(X+i)) + F(i,b), for each i in S.
Alice: Computes F(a,b) = Ya - H(x) |
|
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.
|
|
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: compare secret numbers
« Reply #9 on: Apr 14th, 2009, 3:33pm » |
Quote Modify
|
on Apr 14th, 2009, 7:12am, 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 here. But there are efficient methods that are linear in the number of bits.
|
|
IP Logged |
|
|
|
idontknow
Newbie
Posts: 8
|
|
Re: compare secret numbers
« Reply #10 on: Apr 14th, 2009, 10:53pm » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
oldspy
Newbie
Posts: 9
|
|
Re: compare secret numbers
« Reply #11 on: May 15th, 2009, 4:25pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: compare secret numbers
« Reply #12 on: May 15th, 2009, 10:09pm » |
Quote Modify
|
on May 15th, 2009, 4:25pm, 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
|
| « Last Edit: May 15th, 2009, 10:10pm by R » |
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
justicezyx
Newbie
Posts: 2
|
|
Re: compare secret numbers
« Reply #13 on: May 20th, 2009, 7:08pm » |
Quote Modify
|
how about add a constant to both of their ages?...
|
|
IP Logged |
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: compare secret numbers
« Reply #14 on: May 20th, 2009, 9:40pm » |
Quote Modify
|
on May 20th, 2009, 7:08pm, 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.
|
|
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print