On 2005-05-09T12:28:25-0400, Adam Back wrote:
There is a simple protocol for this described in Schneier's Applied Crypto if you have one handy...
(If I recall the application he illustrates with is: it allows two people to securely compare salary (which is larger) without either party divulging their specific salary to each other or to a trusted intermediary).
Adam
On Mon, May 09, 2005 at 06:00:58AM -0700, Sarad AV wrote:
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.
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. Perform it enough with enough different integers on your side, and you'll be able to discover the other person's integer. There's the round-table of people who want to know what their average salary is, but that only works if there are more than two people and no two are in collusion. (one person generates a random number, adds that to salary, gives only the sum to the next person. Everyone else simply adds their salary and passes it on. It gets back to the originator who subtracts out the random number and divides by the number of people. Hence it doesn't work with 2 people. Technically, the two-person salary comparison isn't zero-knowledge either, which explains why I didn't find it in the zero-knowledge chapter (or maybe I've lost my ability to skim technical books). Once you know the average, you know something about your salary compared with both the overall average and the average of everyone else. You know that nobody can make any more than the sum. The trouble is that you don't know how many bits of information the other person _doesn't_ have about your salary. If they know you make either A, B, or C, running the protocol Adam mentions and choosing the middle salary will reveal the other person's exact salary.