Black-box construction of a more than non-malleable CCA1 encryption scheme from plaintext awareness 1

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.