Re: Zero knowledge( ab )

[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 ab,ab 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.

Re: Zero knowledge( ab )

[cypherpunk]

On 5/9/05, Sarad AV [EMAIL PROTECTED] 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 ab,ab 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

Zero knowledge( ab )

[Sarad AV]

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 ab,ab or a=b.

Thankyou,
Sarad.




Yahoo! Mail
Stay connected, organized, and protected. Take the tour:
http://tour.mail.yahoo.com/mailtour.html

Re: Zero knowledge( ab )

[Adam Back]

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 ab,ab or a=b.