Chosen Ciphertext Security via UCE

Bellare, Hoang, and Keelveedhi (CRYPTO’13) introduced a security notion for a family of (hash) functions called

universal computational extractor

(UCE), and showed how it can be used to realize various kinds of cryptographic primitives in the standard model whose (efficient) constructions were only known in the random oracle model. Although the results of Bellare et al. have shown that UCEs are quite powerful and useful, the notion of UCE is new, and its potential power and limitation do not seem to have been clarified well. To further widen and deepen our understanding of UCE, in this paper we study the construction of chosen ciphertext secure (CCA secure) public key encryption (PKE), one of the most important primitives in the area of cryptography to which (in)applicability of UCEs was not covered by the work of Bellare et al.

We concretely consider the setting in which other than a UCE, we only use chosen plaintext secure (CPA secure) PKE as an additional building block, and obtain several negative and positive results. As our negative results, we show difficulties of instantiating the random oracle in the Fujisaki-Okamoto (FO) construction (PKC’99) with a UCE, by exhibiting pairs of CPA secure PKE and a UCE for which the FO construction instantiated with these pairs becomes insecure (assuming that CPA secure PKE and a UCE exist at all). Then, as our main positive result, we show how to construct a CCA secure PKE scheme using only CPA secure PKE and a UCE as building blocks. Furthermore, we also show how to extend this result to a CCA secure deterministic PKE scheme for block sources (with some constraint on the running time of the sources). Our positive results employ the ideas and techniques from the Dolev-Dwork-Naor (DDN) construction (STOC’91), and for convenience we abstract and formalize the ‘‘core” structure of the DDN construction as a stand-alone primitive that we call

puncturable tag-based encryption

, which might be of independent interest.