Secure MPC( a>b )

Sarad AV jtrjtrjtr2001 at
Thu May 19 02:16:19 PDT 2005


--- Adam Back <adam at> 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 at> 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 at> 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


Yahoo! Mail
Stay connected, organized, and protected. Take the tour:

More information about the cypherpunks-legacy mailing list