[2116] in cryptography@c2.net mail archive
Re: Something really new??
daemon@ATHENA.MIT.EDU (Frank (Giff) Gifford)
Fri Feb 6 15:03:37 1998
Date: Fri, 6 Feb 1998 14:13:23 -0500 (EST)
From: "Frank (Giff) Gifford" <giff@va.pubnix.com>
To: griffin <lpchiew@pc.jaring.my>
cc: cryptography@c2.net
In-Reply-To: <34DB448D.1321@pc.jaring.my>
On Sat, 7 Feb 1998, griffin wrote:
Flaw shown down below...
> http://www.economist.com/editorial/freeforall/current/index_st4443.html
>=20
> SCIENCE AND TECHNOLOGY=20
>=20
> Cryptography=20
>=20
> Swap you=20
>=20
>=20
> HOW do you find out if you share a secret with someone without=20
> giving that secret away? Moni Naor, of the Weizmann Institute,=20
> in Israel, thinks he knows.
>=20
> Working in collaboration with Ronald Fagin of IBM=92s Almaden=20
> Research Centre, in San Jose, California, and Peter Winkler,=20
> of Bell Laboratories in Murray Hill, New Jersey, he has devised=20
> a surprisingly simple way for two people to find out if both=20
> possess the same piece of information without telling each other=20
> what it is.=20
>=20
> Unlike more conventional cryptographic methods, which involve the=20
> use of computers and mind-numbingly long prime numbers (that is,=20
> numbers which have no factors except themselves and 1), this one=20
> requires=97in its simplest manifestation=97no more than some paper, a=20
> couple of pencils and a good supply of envelopes. And it has another=20
> advantage over conventional cryptography: it cannot be broken, even=20
> in theory.=20
>=20
> The example Dr Naor gives to explain his method is of two managers=20
> who have both received a confidential complaint. The managers=97call=20
> them Bill and Ben=97seek to find out if the same individual is involved=
=20
> in both cases without giving away the name of their own complainant=20
> in case it turns out to be different from the other=92s.=20
>=20
> To make the comparison, each manager first translates the letters of=20
> the name of the person who has complained to him into ones and zeros=20
> according to any pre-arranged code and then orders these ones and=20
> zeros in a column (see table). For each place in the column, he then=20
> picks two random numbers, puts each in an envelope, and arranges the=20
> envelopes in two columns, labeled =930=94 and =931=94, so that a pair of =
random=20
> numbers corresponds with each place in the original column.=20
>=20
> [diagram]
>=20
> Having done this, both managers add up the random numbers in the=20
> envelopes corresponding to the values (ie, either =930=94 or =931=94) of =
the=20
> places in the column to which those envelopes refer. They then seal=20
> the envelopes and exchange them, still in order. Each then picks from=20
> the envelopes that he has received those that correspond to his own=20
> series of ones and zeros. He returns the others to his colleague to=20
> show that he has taken only the correct number, and the surplus=20
> envelopes are destroyed without being opened.=20
Here's the flaw - the original envelopes when returned can be opened. If
a different random number is used for each envelope, it's trivial to find
out which series of envelopes were kept and thus reveal the secret which
the second person knows.
A devious person can learn of the secret and give back any random answer
and claim, "Nope, I guess we are talking about a different secret" while
having learned your secret.
>=20
> Lastly, each manager adds up the numbers in the envelopes he has picked,=
=20
> thus arriving at a second sub total, and then adds that to the sub total=
=20
> he got before the exchange. The two managers then compare their grand=20
> totals.=20
>=20
> If the names are the same, Dr Naor=92s method means that each manager wil=
l=20
> have added the same set of numbers together, and will thus have arrived=
=20
> at the same grand total. If the names are different, the two grand
> totals=20
> will have been assembled from different sets of numbers. Different
> totals,=20
> therefore, mean that the complainants must be different people. The only=
=20
> flaw in the method is that there is a small chance of a =93false positive=
=94
> =97that is, of the two totals being the same by coincidence, even though=
=20
> the numbers added together to arrive at them were different. However,=20
> this risk can be minimised by increasing the size of the biggest
> possible=20
> random number that can be chosen.=20
>=20
> Obviously this clumsy manual method would not often be used in practice,=
=20
> and the services of a computer programmer would generally be required to=
=20
> automate it. But the program involved is not a complex one, and is thus=
=20
> available for easy verification that no shenanigans (such as storing the=
=20
> contents of the electronic =93envelopes=94, rather than deleting them) ar=
e=20
> going on.=20
>=20
> Dr Naor thinks that computerised versions of his method could have=20
> widespread applications in areas such as banking, where the secure=20
> exchange of information requires the comparison of passwords. The=20
> researchers therefore hope that their discovery will now be=20
> commercialised. How? For the moment, it=92s a secret . . .
>=20
-Giff
