Re: Probabilistic encryption works!

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.

Is this true? I've given this some thought and I had convinced myself that the nature of the algorithm makes it fundamentally impossible. You tend to give away bits of information reguardless of how you use it. I'd like to be wrong though... JWS