On Sun, 5 Mar 2000, 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 ? k times number of bits sent, yes. > > 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? The PRNG is public, but the seed for a particular communication isn't. It's a funny construct - the seed is communicated using itself, and the other end decrypts it and double-checks that the seed really was sent using itself instead of something else. Does handle the problem nicely though. I have, by the way, looked at the techniques which break the simplest other knapsack PKC's, and they have some difficulty against this one because the amount of pattern hidden in the public knapsack problem is so much less. Of course, that lack of pattern is also the reason for the tremendous bloat of ciphertext. -Bram Cohen
