Secure MPC( a>b )
jtrjtrjtr2001 at yahoo.com
Thu May 19 02:16:19 PDT 2005
--- Adam Back <adam at 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 at gmail.com> wrote:
> 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 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
Stay connected, organized, and protected. Take the tour:
More information about the cypherpunks-legacy