Talk:Probabilistic encryption

Would it not use a pseudo-random generator? -- KayEss 07:53, 9 Oct 2004 (UTC)

Not sure what the question is. If you mean "does a probabilistic encryption algorithm necessarily have to use a pseudorandom number generator", the answer is: most of the time, yes, unless you somehow get lots of random bits for free. Arvindn 08:09, 9 Oct 2004 (UTC)

It's probably me not understanding how the encryption works. If you randomly encode the message how can it ever be decrypted? KayEss 08:14, 9 Oct 2004 (UTC)

The decryption algorithm maps many different ciphertexts to the same plaintext. Think of probabilistic encryption as padding the plaintext with a random string and then deterministically encrypting it. On decryption you just ignore the junk at the end. That's not a provably secure system, but its easy to understand. Arvindn 08:28, 9 Oct 2004 (UTC)

I see now. Could you put an explanation along those lines into the article? --KayEss 11:51, 9 Oct 2004 (UTC)

Even I had the same doubt. Arvindn, can you add this explanation to the article? -- Sundar 05:24, Oct 28, 2004 (UTC)

Well, the example in the explanation is wrong - its not secure. Random padding of plaintext does not achieve semantic security. While comprehensibility is an important goal, I feel correctness is an overriding criterion. I doubt if there's any probabilistic encryption scheme that's both secure and easy to understand - the one at the end of the article is about the simplest. If there's a way to make the article clearer without using the flawed example, feel free to do so. Arvindn 21:10, 28 Oct 2004 (UTC)

Hey guess what, it turns out that prepending n/2 random bits to the plaintext and then using RSA is conjectured to be secure. In any case I'm going to stop being so anal and the random padding bit to the article. Arvindn 00:45, 15 Nov 2004 (UTC)

A simple probabilistic encryption scheme

The Goldwasser-Micali scheme is simple and secure (under an appropriate hardness assumption). I think it might be a better example than OAEP or the general "pad-then-encrypt" discussion, because there are problems with the security of OAEP.

In the GM cryptosystem, (n,y) is the public key, where n is a product of two large primes p,q, and y is a non-square (mod n) of Jacobi symbol 1. (p,q) is the secret key. Encryption is bit-by-bit. To encrypt a 0, send a random square mod n. That is, pick r from Z_n^* and send r^2 mod n. To encrypt a 1, send a random non-square mod n. That is, pick r from Z_n^* and send y*r^2 mod n.

The recipient knows (p,q) and can determine whether a number is a square or not, mod n. Therefore he can decrypt the message bit-by-bit.