In this paper we study the conditions under which the two ciphertexts in the Naor-Yung construction can share the same random coins. We find that this is possible, provided that the underlying PKE scheme meets an additional simple property. The motivation for re-using the same random coins is that this allows to design much more efficient NIZK proofs. We showcase such an improvement in the random oracle model, under standard complexity assumptions including Decisional Diffie-Hellman, Quadratic Residuosity, and Subset Sum. The length of the resulting ciphertexts is reduced by 50\%, yielding truly efficient PKE schemes achieving CCA security under KDM and key-leakage attacks.
As an additional contribution, we design the first PKE scheme whose CPA security under KDM attacks can be directly reduced to (low-density instances of) the Subset Sum assumption. The scheme supports key-dependent messages computed via any affine function of the secret key.Category / Keywords: public-key cryptography / Naor-Yung paradigm, KDM security, leakage, Subset Sum Original Publication (with major differences): SCN 2016 Date: received 7 Sep 2016, last revised 8 Sep 2016 Contact author: daniele venturi at unitn it Available format(s): PDF | BibTeX Citation Version: 20160914:033732 (All versions of this report) Short URL: ia.cr/2016/880 Discussion forum: Show discussion | Start new discussion