Deterministic Public-Key Encryption for Adaptively Chosen Plaintext Distributions.
Ananth Raghunathan, Gil Segev, Salil Vadhan
Bellare, Boldyreva, and O’Neill (CRYPTO ’07) initiated the study of deterministic public-key encryption as an alternative in scenarios where randomized encryption has inherent drawbacks. Theresultinglineofresearchhassofarguaranteedsecurityonlyforadversarially-chosenplaintext distributions that are independent of the public key used by the scheme. In most scenarios, however, it is typically not realistic to assume that adversaries do not take the public key into account when attacking a scheme. We show that it is possible to guarantee meaningful security even for plaintext distributions that depend on the public key. We extend the previously proposed notions of security, allowing adversaries to adaptively choose plaintext distributions after seeing the public key, in an interactive manner. The onlyrestrictionswemakearethat: (1) plaintextdistributionsareunpredictable (as is essential in deterministic public-key encryption), and (2) the number of plaintext distributions from which each adversary is allowed to adaptively choose is upper bounded by 2 p, where p can be any predetermined polynomial in the security parameter. For example, with p = 0 we capture plaintext distributions that are independent of the public key, and with p = O(slogs)
•Jan 1, 2013•0 citations