@journal{MSS12a
	title={Blackbox Construction of A More Than Non-Malleable CCA1 Encryption Scheme from Plaintext Awareness},
	author="Steve Myers and Mona Sergi and Abhi Shelat",
	booktitle="J. of Computer Security",
	volume="21",
	number="5",
	pages="721--748"
}
@inproceedings{MSS11a
	title={Blackbox Construction of A More Than Non-Malleable CCA1 Encryption Scheme from Plaintext Awareness},
	author="Steve Myers and Mona Sergi and Abhi Shelat",
	booktitle="Secure Computer Networks",
	year="2011"
}

The journal version of this paper subsumes the SCN conference version.

PDF

We construct an NM-CCA1 encryption scheme from any CCA1 encryption scheme that is also plaintext aware and weakly simulatable. We believe this is the first construction of an NM-CCA scheme that follows strictly from encryption schemes with seemingly weaker or incomparable security definitions to NM-CCA.

Previously, the statistical PA1 notion of plaintext awareness was only known to imply CCA1. Our result is therefore novel because unlike the case of CPA and CCA2, it is unknown whether a CCA1 scheme can be transformed into an NM-CCA1 scheme. Additionally, we show both the Damg{\aa}rd Elgamal Scheme (DEG)~\cite{D91} and the Cramer-Shoup Lite Scheme (CS-Lite)~\cite{CS03} are weakly simulatable under the DDH assumption. Since both are known to be statistical PA1 under the Diffie-Hellman Knowledge (DHK) assumption, they instantiate our scheme securely.

Next, in a partial response to a question posed by Matsuda and Matsuura~\cite{MM11}, we define an extended version of the NM-CCA1, c-NMCCA1, in which the security definition is modified so that the adversary is permuted to ask a $$c\geq 1$$ number of parallel queries after receiving the challenge ciphertext. We extend our construction to yield a c-NMCCA1 scheme for any constant $$c$$. All of our constructions are black-box.