Abstract
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 a NM − CCA1 scheme that follows strictly from encryption schemes with seemingly weaker or incomparable security definitions to NM − CCA1.
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ård 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 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 [MM11], we define an extended version of the NM − CCA1, cNM − CCA1, 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 − CCA1 scheme for any constant c. All of our constructions are black-box.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Bellare, M., Palacio, A.: Towards Plaintext-Aware Public-Key Encryption Without Random Oracles. In: Lee, P.J. (ed.) ASIACRYPT 2004. LNCS, vol. 3329, pp. 48–62. Springer, Heidelberg (2004)
Choi, S.G., Dachman-Soled, D., Malkin, T., Wee, H.: Black-Box Construction of a Non-malleable Encryption Scheme from Any Semantically Secure One. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 427–444. Springer, Heidelberg (2008)
Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology, revisited. J. ACM 51(4), 557–594 (2004)
Cramer, R., et al.: Bounded CCA2-Secure Encryption. In: Kurosawa, K. (ed.) ASIACRYPT 2007. LNCS, vol. 4833, pp. 502–518. Springer, Heidelberg (2007)
Cramer, R., Shoup, V.: Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack. SIAM J. Comput. 33(1), 167–226 (2003)
Damgård, I.: Towards Practical Public Key Systems Secure against Chosen Ciphertext Attacks. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 445–456. Springer, Heidelberg (1992)
Dolev, D., Dwork, C., Naor, M.: Nonmalleable cryptography. SIREV: SIAM Review 45 (2003)
Dent, A.W.: The Cramer-Shoup Encryption Scheme Is Plaintext Aware in the Standard Model. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 289–307. Springer, Heidelberg (2006)
Dent, A.W.: The hardness of the DHK problem in the generic group model. IACR Cryptology ePrint Archive 2006, 156 (2006)
Damgård, I., Nielsen, J.B.: Improved Non-committing Encryption Schemes Based on a General Complexity Assumption. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 432–450. Springer, Heidelberg (2000)
Matsuda, T., Matsuura, K.: Parallel Decryption Queries in Bounded Chosen Ciphertext Attacks. In: Catalano, D., Fazio, N., Gennaro, R., Nicolosi, A. (eds.) PKC 2011. LNCS, vol. 6571, pp. 246–264. Springer, Heidelberg (2011)
Myers, S., Shelat, A.: Bit encryption is complete. In: FOCS, pp. 607–616 (2009)
Pass, R., Shelat, A., Vaikuntanathan, V.: Construction of a Non-malleable Encryption Scheme from Any Semantically Secure One. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 271–289. Springer, Heidelberg (2006)
Pass, R., Wee, H.: Black-box constructions of two-party protocols from one-way functions. In: Reingold, O. (ed.) TCC 2009. LNCS, vol. 5444, pp. 403–418. Springer, Heidelberg (2009)
Wee, H.: Black-box, round-efficient secure computation via non-malleability amplification. In: FOCS, pp. 531–540. IEEE Computer Society (2010)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2012 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Myers, S., Sergi, M., shelat, a. (2012). Blackbox Construction of a More Than Non-Malleable CCA1 Encryption Scheme from Plaintext Awareness. In: Visconti, I., De Prisco, R. (eds) Security and Cryptography for Networks. SCN 2012. Lecture Notes in Computer Science, vol 7485. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-32928-9_9
Download citation
DOI: https://doi.org/10.1007/978-3-642-32928-9_9
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-32927-2
Online ISBN: 978-3-642-32928-9
eBook Packages: Computer ScienceComputer Science (R0)