Towards tightly secure deterministic public key encryption

Abstract

In this paper, we formally consider the construction of tightly secure deterministic public key encryption (D-PKE). Initially, we compare the security loss amongst the D-PKE schemes under the concrete assumptions and also analyze the tightness of generic D-PKE constructions. Furthermore, we prove that the CPA secure D-PKE scheme of Boldyreva et al. (Crypto’08) is tightly PRIV-IND-CPA secure for block-sources. Our security reduction improves the security loss of their scheme from O(nc*) to O(1). Additionally, by upgrading the all-but-one trapdoor function (TDF) in the construction of Boldyreva et al. to all-but-n TDF defined by Hemenway et al. (Asiacrypt’11), we give general construction of PRIV-IND- n/2 -CCA secure (i.e., the number of challenge ciphertexts nc* is bounded by n/2) D-PKE scheme for block-sources. And we observe that if the security reduction of the all-but-n TDF is tight, the D-PKE scheme can be tightly PRIV-IND- n/2 -CCA secure. Finally, we prove that the all-but-n TDF given by Hemenway et al. is tightly secure, which results in the first tightly PRIV-IND- n/2 -CCA secure D-PKE scheme for block-sources, based on the s-DCR assumption.