Blackbox Construction of a More Than Non-Malleable CCA1 Encryption Scheme from Plaintext Awareness

摘要

We construct an NM-CCA1 encryption scheme from any CCA1 encryption scheme that is also plaintext aware and weakly simu-latable. 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 PAl 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 Damgard Elgamal Scheme (DEG) [Dam91] and the Cramer-Shoup Lite Scheme (CS-Lite) [CS03] are weakly simulatable under the DDH assumption. Since both are known to be statistical PAl under the Diffie-Hellman Knowledge (DHK) assumption, they instantiate our scheme securely. Next, in a partial response to a question posed by Matsuda and Mat-suura [MM11], we define an extended version of the NM-CCA1, cNM-CCAl, in which the security definition is modified so that the adversary is permuted to ask a c > 1 number of parallel queries after receiving the challenge ciphertext. We extend our construction to yield a cNM-CCAl scheme for any constant c. All of our constructions are black-box.