Institute of Information Science, Academia Sinica

When modeling the security game for public-key encryption, we require an adversary to distinguish between encryptions of different messages, called the challenge ciphertexts.  A scheme is secure if no efficient adversary can distinguish the challenge ciphertexts with non-negligible advantage.  Since in a public-key scheme the adversary may compute encryptions on his own, it is imperative for security that the encryption is randomized.  Traditionally, we assume that the challenge ciphertexts are encrypted using perfect (i.e. completely uniform) randomness.

Since randomness is a scarce resource and since physical sources are imperfect and may even be subject to attacks, more recent models have studied what happens when we relax this assumption.  Namely, what if the challenge ciphertexts are encrypted using imperfect randomness, and perhaps even randomness that is tampered with maliciously by the adversary?

We propose a new security model that roughly captures the following attack model: an attacker plants a virus on the target system, and this virus is able to tamper with the randomness used when generating challenge ciphertexts.

In order to achieve positive results, we restrict the amount of information the virus has about the public key and/or the messages to encrypt.  Nevertheless, we obtain a model that subsumes all previous models studying encryption with weak randomness.  Furthermore, building on results of Raghunathan et al. we propose constructions in both the standard model and the random oracle model that achieve our notion of security.