Towards tightly secure deterministic public key encryption

• Main Authors: ZHANG, Daode, LI, Bao, LIU, Yamin, XUE, Haiyang, LU, Xianhui, JIA, Dingding
• Format: text
• Language: English
• Published: Institutional Knowledge at Singapore Management University 2017
• Subjects: Deterministic public key encryption; Tight security reduction; Lossy trapdoor functions; Standard model; Information Security
• Online Access: https://ink.library.smu.edu.sg/sis_research/9205; https://ink.library.smu.edu.sg/context/sis_research/article/10210/viewcontent/towards_tightly.pdf
• Institution: Singapore Management University

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-n2-CCA secure (i.e., the number of challenge ciphertexts nc∗ is bounded by n2) 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-n2-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-n2-CCA secure D-PKE scheme for block-sources, based on the s-DCR assumption.