Randomness in Public Key Encryption

Question

For a scheme to be at least CPA secure, one has to randomize the scheme. In case of a secret key encryption scheme, the used randomness will typically become part of the cipher text as in the case of an IV and is "public" (This is not a necessary requirement but how most algorithms work).

Now, if I switch to public key encryption schemes, the randomness will typically not be "public". The decryption algorithm simply removes it without necessarily really knowing it, like for example in the case of LWE or McEliece.

Now my question is: Is this a necessary requirement for public key encryption schemes that at least some of the randomness is not explicitly given as part of the cipher text?

Moreover, might it even be the case that all randomness that effects security has to be non-public? To be more precise, does all randomness that I cannot replace with a public constant value, without harming the security of the scheme have to be private.

(As a motivating example of randomness that can not effect security: I can always add randomness by first XORing the plaintext with a random bit string and adding this bit string to the cipher text but the scheme would be as secure as if I XORed the all zero string instead. Hence, this randomness could be omitted without harming the security.)

Answer 1

A public-key encryption algorithm cannot rely exclusively on "public" randomness. The reason comes down to the fact that encryption is a public algorithm that can be run by anyone. If the algorithm's output included all the random coins that it used, then an adversary could determine the message from the ciphertext, by running the encryption algorithm with the (given) coins and each of the two candidate messages from the IND-CPA experiment. The true message (and only that message) would yield the target ciphertext.

In some cryptosystems, the decryption algorithm recovers all of the encryption randomness. Examples include encryption schemes based on injective trapdoor functions like RSA. There's no contradiction with security here because one needs the secret key to recover the randomness.

For your second question, we can't go so far as to say that all publicly recoverable randomness is non-security influencing, i.e., replaceable by a fixed public constant (which is the contrapositive of your question). For example, consider a PRG that uses some random public parameter along with a secret random seed (e.g., an LWE-based PRG). Now consider an encryption algorithm that chooses both a public parameter and a seed for the generator, to produce a pseudorandom string for the "real" encryption, and outputs the parameter as part of the ciphertext. This would be secure, but might not be if we fixed the public parameter to be, say, all zeros.

Answer 2

Even non-public randomness may be fatal.

For example, RSA public keys are calculated as p*q, where p and q are two random primes. If you have lots of two keys, you can work out if they have any common factors (which would be either p or q) and what it is. Once you have this, you can work out the other, and you can then recalculate the private key.

This was used as an actual attack. It was made easier by the fact that, if you multiplied two public keys together, you could test a third key against both of the first two keys. If you don't get a match, multiply by the third key to test the next candidate against all three keys.

This means that, if p or q are used more than once in different keys, attacker knowing only the public key can calculate BOTH private keys trivially.

As a "sanity check", Arjen Lenstra et al. tried a gcd-calculating trick out on several million real keys [..] and cracked about 13000 of them. This led to a New York Times report emphasizing that this could be a serious flaw in the way RSA is used: about 0.2% of all keys seen on the Internet seem to be vulnerable.

• from http://www.loyalty.org/~schoen/rsa/, referring to http://eprint.iacr.org/2012/064.pdf

Note that this applies to RSA specifically; other encryption schemes will not have this specific issue, this does not mean that they don't have other (comperable?) issues.

Answer 3

It's always useful to add randomness lavishly (both for symmetrical and a-symmetrical cases). For one, a cryptanalyst will not know whether this random-looking string is in fact an encrypted subliminal message. Also, by adding misleading words to a phrase and then transposing it with a complete transposition cipher (one that encrypts any arbitrary permutation to any other arbitrary permutation), one renders his ciphertext mathematically unbreakable. For example, let the plaintext be: P = "let's meet Friday, at 7pm". One could add to it to form P* = "let's meet Friday at 7pm # Sunday, Monday,... 1pm, 2pm,... " then transpose P* to a cipher C. The intended reader would un-mix C to P* and ignore everything right of the "#", but the cryptanalyst will find many keys that will decrypt C to different plaintext candidates, like P' = let's meet Monday, at 2pm".

See more at: https://eprint.iacr.org/2015/510