On Notions of Security for Deterministic Encryption, and Efficient Constructions Without Random Oracles

The study of deterministic public-key encryption was initiated by Bellare et al. (CRYPTO '07), who provided the "Strongest Possible" notion of security for this primitive (called PRIV) and constructions in the random oracle (RO) model. The authors focus on constructing efficient deterministic encryption schemes without random oracles. To do so, they propose a slightly weaker notion of security, saying that no partial information about encrypted messages should be leaked as long as each message is a-priori hard-to-guess given the others (while PRIV did not have the latter restriction). Nevertheless, the authors argue that this version seems adequate for certain practical applications.