[6722] in cryptography@c2.net mail archive
Re: A new PKC, and some conjectures
daemon@ATHENA.MIT.EDU (dmolnar)
Sun Mar 5 21:43:55 2000
Date: Sun, 5 Mar 2000 21:07:50 -0500 (EST)
From: dmolnar <dmolnar@hcs.harvard.edu>
To: bram <bram@gawth.com>
Cc: cypherpunks@cyberpass.net, cryptography@c2.net
In-Reply-To: <Pine.LNX.4.10.10003051738240.1250-100000@ultra.gawth.com>
Message-ID: <Pine.OSF.4.05.10003052101580.11546-100000@hcs.harvard.edu>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
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
