____________________________________________________________________ Before a larger group can see the virtue of an idea, a smaller group must first understand it. "Stranger Suns" George Zebrowski The Armadillo Group ,::////;::-. James Choate Austin, Tx /:'///// ``::>/|/ ravage@ssz.com www.ssz.com .', |||| `/( e\ 512-451-7087 -====~~mm-'`-```-mm --'- -------------------------------------------------------------------- ---------- Forwarded message ---------- Date: Wed, 21 Feb 2001 14:22:26 -0800 From: hal@finney.org To: bram@gawth.com, Pete.Chown@skygate.co.uk Cc: coderpunks@toad.com, crypt@bxa.doc.gov Subject: Re: Harvard mathematician creates 'provably unbreakable' code Let me tell you how the Rabin system works in the Crypto 99 paper. I'll do it as pseudo code and copy it to BXA so everything is kosher. Basically they generate a one time pad by xoring a random subset of the message bits, where the subset indices are agreed upon in advance by the communicants: Security Parameter k // Error probability = 1/2^(k/5) Random data length PER MESSAGE BIT n = 5E // E is maximum size of adversary memory Message Length m //bits Message M = {M_1, ..., M_m} // m bits long Secret key s = {sig_1, ... sig_k} // each in range 1-n, k of them Random data alpha[n][m] // n*m bits long One Time Pad X[m] // Will be xored with M for i = 1 to m do for j = 1 to n do if j is an element of s then R and S store alpha[j][i] end for j S and R set X[i] = xor of stored alpha[j][i] values (k of them) S sends M[i] xor X[i]; R recovers M[i] by xoring with X[i] end for i For each message bit M_i we need to use 5*E random bits, where E is the estimate of the maximum amount of memory the adversary can hold. For example if Eve can store 100 Tbits, we need to use up 500 Tbits of data for each message bit. To send say a 1 Mbit message that is, well, it's a lot. 500 exabits. (It goes giga, tera, peta, exa. Then zetta and yotta.) The initial shared secret key is simply k indexes in the range 1-n, where k is the security parameter such that the guaranteed probability of failure is bounded by 1/2^(k/5). k = 300 would give a security level of 2^60. The size of the initial shared secret key is therefore k log n, so with k = 300 and n = 2^49 as above, this is about 15000 shared key bits. So I would say no, this 1999 scheme is not practical. Maurer's original approach used only n random bits in total, not n bits per message bit, but it did not have as strong provability. The authors leave it as an open problem whether they can achieve similar levels of provable security using n bits total, which would make it much more practical. Maybe the new result presented in the Times fixes this problem and reduces the data quantity to something sane. Hal