Note: [1] The views and conclusions contained in this document are those of the authors and should not be
interpreted as representing the official policies, either expressed or implied, of the Defense Advanced
Research Projects Agency or the US government.
Abstract: We construct a Non-Malleable Chosen Ciphertext Attack (NM-CCA1) encryption scheme from any encryption scheme that is also plaintext aware and weakly simulatable. We believe this is the first construction of a NM-CCA1 scheme that follows strictly from encryption schemes with seemingly weaker or incomparable security definitions to NM-CCA1. Previously, the statistical Plaintext Awareness #1 (PA1) notion was only known to imply CCA1. Our result is therefore novel because unlike the case of Chosen Plaintext Attack (CPA) and Chosen Chiphertext Attack (CCA2), it is unknown whether a CCA1 scheme can be transformed into an NM-CCA1 scheme. Additionally, we show both the Damgård Elgamal Scheme (DEG) [in: CRYPTO, J. Feigenbaum, ed., Lecture Notes in Computer Science, Vol. 576, Springer, 1991, pp. 445–456] and the Cramer–Shoup Lite Scheme (CS-Lite) [SIAM J. Comput. 33(1) (2003), 167–226] are weakly simulatable under the DDH assumption. Since both are known to be statistical Plaintext Aware 1 (PA1) under the Diffie–Hellman Knowledge (DHK) assumption, they instantiate our scheme securely. Furthermore, in response to a question posed by Matsuda and Matsuura [in: Public Key Cryptography, D. Catalano, N. Fazio, R. Gennaro and A. Nicolosi, eds, Lecture Notes in Computer Science, Vol. 6571, Springer, 2011, pp. 246–264], we define cNM-CCA1-security in which an NM-CCA1-adversary is permitted to ask a c≥1 number of parallel queries after receiving the challenge ciphertext. We extend our construction to yield a cNM-CCA1 scheme for any constant c. All of our constructions are black-box.
