hi, If user A has the integer a and user B has the integer b, can a zero knowledge proof be developed to show that a>b,a<b or a=b. Thankyou, Sarad. Yahoo! Mail Stay connected, organized, and protected. Take the tour: http://tour.mail.yahoo.com/mailtour.html

On 5/9/05, Sarad AV <jtrjtrjtr2001@yahoo.com> wrote:

If user A has the integer a and user B has the integer b, can a zero knowledge proof be developed to show that a>b,a<b or a=b.

You've got two different things mixed up here. A zero knowledge proof is normally used by one person to show that he knows a value satisfying certain conditions, without revealing what the value is. What you are asking for involves two people who want to compute a function of their inputs, without revealing those inputs. That is known as a multi party computation or MPC. As was pointed out, Schneier has some good pointers on MPC calculations. There is a program you can download called Fairplay which will perform MPC calculations like this. One of them does exactly what you are asking for. See http://www.cs.huji.ac.il/labs/danss/Fairplay/ CP

hi, --- Adam Back <adam@cypherspace.org> wrote:

There is a simple protocol for this described in Schneier's Applied Crypto if you have one handy...

Yes, I found it. Thankyou. --- cypherpunk <cyphrpunk@gmail.com> wrote:

That is known as a multi party computation or MPC

True, Its a secure MPC protocol. I confused it with Zero knowledge protocols. --- Justin <justin-cypherpunks@soze.net> wrote:

I don't recall that particular protocol in AC, but it's a mistake to call such a thing "zero-knowledge", since it mandatorily leaks ~1.585 bits of information (the first time) about the other person's integer.

How is there information leakage? Mr.Bruce Schneier in his book titled " Appiled Cryptography" mentions the following MPC protocol to compare the income of two parties, Alice and Bob without revealing their income. The protocol works as follows: Let 'i' be Alice's income. Let 'j' be Bob's income. Let Eb be Bob's public key. Let Db be Bob's privare key. Let n be Bob's public modulus. To start with we assume that the range of i and j is from 1 to 100. 1) Alice chooses a random number x and using Bob's public key computes c=x^Eb (mod n) 2) Alice computes k = c-i and sends the result to Bob. 3) Bob computes the following 100 numbers y1 = (k+1)^Db (mod n) y2 = (k+2)^Db (mod n) [.....] y100 = (k+100)^Db (mod n) Bob now chooses a large prime p, such that p<x. Bob doesnot know the value of x but Alice can tell Bob about the _size_ of x. 4) Bob then computes z1 = y1 (mod p) z2 = y2 (mod p) [.....] z100 = y100 (mod p) He verifies that |zi-zj|>=2 for all i,j in the range 1 to 100. If this is not true Bob chooses another prime and starts again. 5) Bob sends Alice the sequence in the exact order let _ denote subscript, e.g. a_b is a subscript b. Z1, Z2, ...,Zj, Z_(j+1) +1, ..., Z_(j+100) +1, p 6) Alice checks if the (i th) number in the sequence is congruent to x mod p. If yes, she concludes i<=j, otherwise i>j. When we have the case i>j, Bob computes Z_(j+1) +1, ..., Z_(j+100) +1, this makes the (i th) sequence Alice looks at incongruent (mod p) and makes the protocol work. We have |zi-zj|>=2 so that the sequences donot collide with one another. The protocol as such donot detect cheaters in the scheme. thanks, Sarad. Yahoo! Mail Stay connected, organized, and protected. Take the tour: http://tour.mail.yahoo.com/mailtour.html