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? Thanks much, -David Molnar
