Paper 2012/109

Chosen-Ciphertext Secure Efficiently Searchable Encryption in the Standard Model

Yang Cui and Kirill Morozov

Abstract

In the standard model, deterministic public-key encryption (PKE) secure against chosen-ciphertext attacks by privacy adversary (PRIV-CCA) is known to be built only from lossy trapdoor functions as demonstrated by Boldyreva et al at Crypto 2008. We show that the method of achieving IND-CCA security via correlated products, recently introduced by Rosen and Segev at TCC 2009, can be used to achieve PRIV-CCA secure PKE of uniform messages from any trapdoor permutation (TDP) in the standard model. Our schemes are {\em not} deterministic as a whole, however randomness is only applied to a particular part of the ciphertext - an one-time signature used for validity check. This allows efficient (logarithmic in the database size) search on encrypted data. In a nutshell, our first construction (which is generic) departs from any IND-CPA secure PKE (implied by TDP), builds its k-correlated version, transforms it into the k-correlated PRIV-CPA encryption, and finally lifts it up to PRIV-CCA security. In contrast to Rosen and Segev's correlated products method, we do not assume one-wayness under correlated inputs, thus any IND-CPA secure PKE can be used in our construction. In addition, we present the second construction -- which is more efficient, than the first one -- based on assumptions from coding theory and any TDP. Note that for the price of allowing some limited use of randomness, we achieve PRIV security for multiple messages, which is strictly stronger than the single-message notion PRIV1 achieved by the scheme of Boldyreva et al at Crypto 2008.