Zero knowledge( a>b )

[Justin]

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.