Better Security for Deterministic Public-Key Encryption: The Auxiliary-Input Setting
Deterministic public-key encryption, introduced by Bellare, Boldyreva, and ONeill (CRYPTO 07), provides an alternative to randomized public-key encryption in various scenarios where the latter exhibits inherent drawbacks. A deterministic encryption algorithm, however, cannot satisfy any meaningful notion of security when the plaintext is distributed over a small set. Bellare et al. addressed this difficulty by requiring semantic security to hold only when the plaintext has high min-entropy from the adversarys point of view.
public-key encryption deterministic encryption auxiliary inputs composable security