Probabilistic encryption works!

[rishab@dxm.ernet.in]

solman@MIT.EDU:
> Here is how it works:
> 
> First, choose two large prime numbers that are one less than a multiple of
> [...]
> plaintext and append the final seed and you get your cyphertext.

Congratulations! You've just described the Blum-GoldWasser Efficient 
Probabilistic Public-Key Encryption Scheme, first outlined in Crypto 84.
Nice description in Schneier, who says it's much faster and more secure
than any other PK scheme, but can obviously only be used one-way as it's
vulnerable to a chosen plaintext attack. It would be possible to cook up 
a protocol to allow for signatures as well, but it'd be tricky.

> algorithms for that anyway. What this provides is a public key system based
> on the hardness of factoring that is faster than RSA and apparently not
> covered by the RSA patent. (although I've asked for opinions on this last
> point in another post)

But we don't know whether it's covered by any Blum-Goldwasser patent... or
the PKP ones.

-----------------------------------------------------------------------------
Rishab Aiyer Ghosh             "Clean the air! clean the sky! wash the wind!
rishab@dxm.ernet.in                   take stone from stone and wash them..."
Voice/Fax/Data +91 11 6853410  
Voicemail +91 11 3760335                 H 34C Saket, New Delhi 110017, INDIA