> ----- Original Message ----- > From: "Travis H." <[EMAIL PROTECTED]> > To: cryptography@metzdowd.com > Subject: bounded storage model - why is R organized as 2-d array? > Date: Thu, 2 Mar 2006 23:06:41 -0600 > > > Hey, > > In Maurer's paper, which is the last link here on the following page, > he proposes to use a public random "pad" to encrypt the plaintext > based on bits selected by a key. What I'm wondering is why he chose > the strange construction for encryption; namely, that he uses an > additive (mod 2) cipher where each plaintext bit is (apparently) XORed > against K bits from the random pad. He also uses a 2-d array > structure, both of which appear kind of arbitrary to me. > > http://www.crypto.ethz.ch/research/itc/samba/ >
This is a subject that I'm painfully familiar with. Dr. Maurer has slowly but surely over the last decade or so been putting together a solid proof of a cipher very similar in construction to Dr. Atalla's proprietary Tristrata cipher (US patent #6088449). The basic idea is that you do something like random1 XOR random2 = pad, then pad XOR plaintext = ciphertext. If random1 and random2 are arrays of bits (n-bit random numbers) from a much larger amount of random material, then one can tune the probability of the pad repeating to be almost zero. Essentially you get an equation with 2 unknowns (pad and plaintext), which is pretty hard to solve if the pad is hard to determine. The 2-D array simplifies getting the randomX's. Basically you treat the initial random material as a big array of N random bit strings. Each randomX value is a random strip inside each bit string. Each strip is the same size (at TriStrata we typically used four 64-Kbyte strips, each from a 250 Kbyte bit string). You XOR them together and get a "random" pad (ours was 64 Kbytes long). We were able to XOR about 32 Kbytes of plaintext into ciphertext, before an inverse matrix attack became feasible. Then a new pad had to be generated for the next 32 Kbytes. The reason people like Dr. A or Dr. M are interested in doing this is because you can get super-fast ciphers or get some sort of fundamental proof about its strength that is applicable to all types of ciphers. The speed, from a software engineering perspective, results from the classic tradeoff between memory lookup and execution loop complexity. If one can get down to a couple of XORs and memory copies (per 32 or 64 bit data)using ordinary microprocessor instructions then it will outperform AES by around a couple of orders of magnitude. This is very useful for encrypting things like video streams without an expensive hardware cryptographic accelerator card. Dr. M showed in an earlier paper that if one uses enough randomX values that you can get arbitarily close to generating a truly random pad each time you need it to encrypt some ciphertext (but with N XORs!). Anyway, the big negatives are that with this type of Vernam cipher the entropy decays really fast, especially if the initial big source of random bits is publicly known, the pad management is really hairy, and generating lots of random bits of the initial material is very slow. Huge numbers of pads have to be generated and distributed all the time, and a great deal of care has to be taken to mitigate the cipher's decaying strength and to avoid several types of attacks on the pad generation. It is of great personal interest to me to watch Dr. M slowly prove that the underlying mathematics of Dr. A's Tristrata cipher may not have been snake oil after all. - Alex --------------------------------------------------------------------- The Cryptography Mailing List Unsubscribe by sending "unsubscribe cryptography" to [EMAIL PROTECTED]