[2122] in cryptography@c2.net mail archive
Re: Something really new???
daemon@ATHENA.MIT.EDU (Hal Finney)
Fri Feb 6 19:14:25 1998
Date: Fri, 6 Feb 1998 14:49:29 -0800
From: Hal Finney <hal@rain.org>
To: cryptography@c2.net, dpj@world.std.com
Regarding ...
> http://www.economist.com/editorial/freeforall/current/index_st4443.html
Sounds like the "receive two envelopes, open one, pass the other
back and have it destroyed" is a layman's description of a two-string
oblivious transfer. This is a standard cryptographic primitive in which
Alice has two strings, and sends them to Bob in such a way that Bob only
receives one of them, of his choice, but where Alice can't tell which one
he chose. This is exactly what is required in the comparison protocol.
The key to the security is that at least some of the values Bob includes
in his sum are never seen by Alice, if their strings differ. Those are
the ones he chooses but which correspond to bits which Alice never
"opens".
For example, if Bob's first bit is a 1, and he chooses 47 and 63 as his
random numbers, and if Alice's first bit is a 0, she sees the 47 but
she never sees the 63 which Bob adds in to his sum. It turns out that
adding even one truly random number to a modular sum makes the result
totally random. (The article neglected to mention it, but undoubtedly the
sum must be modulo the size of the random number range.) So the value of
Bob's sum will be totally random as far as Alice is concerned as long as
his input differs in even one bit. There is no way she can try to guess
it, because she's never seen some of the random numbers which were added.
Hal
