At 6:07 PM -0800 3/5/00, dmolnar wrote: >On Sun, 5 Mar 2000, bram wrote: > >> During encryption, the encrypter has to pick a bunch of random 0 or 1 bits > >Here "a bunch" = k, right ? > >> to determine whether to include each of the public key integers in each >> sum. Rather than doing that randomly, she picks a seed for a standard >> cryptographically strong PRNG, and uses the PRNG's output to choose >> whether to include each number. She then includes the seed to the PRNG as >> the first bunch of bits sent to the decrypter. It is now possible for the > >Is the PRNG public? If it is, and I as an eavesdropper have the seed, >then it seems I now have access to the same output used to pick whether >to include each number. So if I know how that is done, then now I as >an eavesdropper know which of the public key integers were picked >to form the ciphertext. > >So now I check to see whether the ciphertext is the sum of the integers or >their negation. Now I know whether the ciphertext represents an 0 or a 1. > >If the PRNG isn't public, then it seems to be a shared secret. > >> decrypter to tell if the input is well formed by re-running the PRNG and >> seeing if it gives the same totals, so the attack is thwarted. > >It does thwart that attack -- but does it mean we now need a shared >secret PRNG? This is starting to look like a variant of the old "we share a large set of numbers--"one time pad"--and then the message includes a set of bits specifying an entry point into this set of numbers." In this case, the shared PRNG is not only security through obscurity, which doesn't work, it is also dependent on the entropy of the seed. Which is probably a whole lot less than the entropy implicit in our usual several hundred decimal digit--equivalent work factors. And it vaguely resembles some of the many variants of the "pseudo one time pad." The zero knowledge stuff seems ancillary, an afterthought, to use the PRNG and seeds as the main carriers of information. --Tim May ---------:---------:---------:---------:---------:---------:---------:---- Timothy C. May | Crypto Anarchy: encryption, digital money, ComSec 3DES: 831-728-0152 | anonymous networks, digital pseudonyms, zero W.A.S.T.E.: Corralitos, CA | knowledge, reputations, information markets, "Cyphernomicon" | black markets, collapse of governments.
