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