Abstract
We study simulation-based, selective opening security against chosen-ciphertext attacks (SIM-SO-CCA security) for public key encryption (PKE). In a selective opening, chosen-ciphertext attack (SO-CCA), an adversary has access to a decryption oracle, sees a vector of ciphertexts, adaptively chooses to open some of them, and obtains the corresponding plaintexts and random coins used in the creation of the ciphertexts. The SIM-SO-CCA notion captures the security of unopened ciphertexts with respect to probabilistic polynomial-time (ppt) SO-CCA adversaries in a semantic way: what a ppt SO-CCA adversary can compute can also be simulated by a ppt simulator with access only to the opened messages. Building on techniques used to achieve weak deniable encryption and non-committing encryption, Fehr et al. (Eurocrypt 2010) presented an approach to constructing SIM-SO-CCA secure PKE from extended hash proof systems (EHPSs), collision-resistant hash functions and an information-theoretic primitive called Cross Authentication Codes (XACs). We generalize their approach by introducing a special type of Key Encapsulation Mechanism (KEM) and using it to build SIM-SO-CCA secure PKE. We investigate what properties are needed from the KEM to achieve SIM-SO-CCA security. We also give three instantiations of our construction. The first uses hash proof systems, the second relies on the \(n\)-Linear assumption, and the third uses indistinguishability obfuscation (\(i\mathcal {O}\)) in combination with extracting, puncturable Pseudo-Random Functions in a similar way to Sahai and Waters (STOC 2014). Our results establish the existence of SIM-SO-CCA secure PKE assuming only the existence of one-way functions and \(i\mathcal {O}\). This result further highlights the simplicity and power of \(i\mathcal {O}\) in constructing different cryptographic primitives.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahai, A., Vadhan, S.P., Yang, K.: On the (im)possibility of obfuscating programs. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 1–18. Springer, Heidelberg (2001). http://dx.doi.org/10.1007/3-540-44647-8_1
Barak, B., Goldreich, O., Impagliazzo, R., Rudich, S., Sahai, A., Vadhan, S.P., Yang, K.: On the (im)possibility of obfuscating programs. J. ACM 59(2), 6 (2012). http://doi.acm.org/10.1145/2160158.2160159
Bellare, M., Hofheinz, D., Yilek, S.: Possibility and impossibility results for encryption and commitment secure under selective opening. In: Joux, A. (ed.) EUROCRYPT 2009. LNCS, vol. 5479, pp. 1–35. Springer, Heidelberg (2009)
Bellare, M., Waters, B., Yilek, S.: Identity-Based encryption secure against selective opening attack. In: Ishai, Y. (ed.) TCC 2011. LNCS, vol. 6597, pp. 235–252. Springer, Heidelberg (2011). http://dx.doi.org/10.1007/978-3-642-19571-6_15
Böhl, F., Hofheinz, D., Kraschewski, D.: On definitions of selective opening security. In: Fischlin, M., Buchmann, J., Manulis, M. (eds.) PKC 2012. LNCS, vol. 7293, pp. 522–539. Springer, Heidelberg (2012). http://dx.doi.org/10.1007/978-3-642-30057-8_31
Canetti, R., Dwork, C., Naor, M., Ostrovsky, R.: Deniable encryption. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 90–104. Springer, Heidelberg (1997). http://dx.doi.org/10.1007/BFb0052229
Canetti, R., Feige, U., Goldreich, O., Naor, M.: Adaptively secure multi-party computation. In: Miller, G.L. (ed.) Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pp. 639–648. ACM, Philadelphia (1996). http://doi.acm.org/10.1145/237814.238015
Cramer, R., Shoup, V.: Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 45–64. Springer, Heidelberg (2002)
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 (2004). http://dx.doi.org/10.1137/S0097539702403773
Damgård, I.B., 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). http://dx.doi.org/10.1007/3-540-44598-6_27
Dwork, C., Naor, M., Reingold, O., Stockmeyer, L.J.: Magic functions. J. ACM 50(6), 852–921 (2003). http://doi.acm.org/10.1145/950620.950623
Fehr, S., Hofheinz, D., Kiltz, E., Wee, H.: Encryption schemes secure against chosen-ciphertext selective opening attacks. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 381–402. Springer, Heidelberg (2010). http://dx.doi.org/10.1007/978-3-642-13190-5_20
Garg, S., Gentry, C., Halevi, S., Raykova, M., Sahai, A., Waters, B.: Candidate indistinguishability obfuscation and functional encryption for all circuits. In: 54th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2013, pp. 40–49. IEEE Computer Society, Berkeley (2013). http://doi.ieeecomputersociety.org/10.1109/FOCS.2013.13
Hemenway, B., Libert, B., Ostrovsky, R., Vergnaud, D.: Lossy encryption: constructions from general assumptions and efficient selective opening chosen ciphertext security. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 70–88. Springer, Heidelberg (2011)
Hofheinz, D.: All-But-Many lossy trapdoor functions. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 209–227. Springer, Heidelberg (2012)
Hofheinz, D., Kiltz, E.: Secure hybrid encryption from weakened key encapsulation. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 553–571. Springer, Heidelberg (2007)
Hofheinz, D., Rupp, A.: Standard versus selective opening security: separation and equivalence results. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 591–615. Springer, Heidelberg (2014). http://dx.doi.org/10.1007/978-3-642-54242-8_25
Huang, Z., Liu, S., Qin, B.: Sender-Equivocable encryption schemes secure against chosen-ciphertext attacks revisited. In: Kurosawa, K., Hanaoka, G. (eds.) PKC 2013. LNCS, vol. 7778, pp. 369–385. Springer, Heidelberg (2013). http://dx.doi.org/10.1007/978-3-642-36362-7_23
Huang, Z., Liu, S., Qin, B., Chen, K.: Fixing the sender-equivocable encryption scheme in eurocrypt 2010. In: 2013 5th International Conference on Intelligent Networking and Collaborative Systems, pp. 366–372. IEEE, Xi’an city (2013). http://dx.doi.org/10.1109/INCoS.2013.69
Katz, J., Ostrovsky, R.: Round-Optimal secure two-party computation. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 335–354. Springer, Heidelberg (2004). http://dx.doi.org/10.1007/978-3-540-28628-8_21
Lai, J., Deng, R.H., Liu, S., Weng, J., Zhao, Y.: Identity-Based encryption secure against selective opening chosen-ciphertext attack. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 77–92. Springer, Heidelberg (2014). http://dx.doi.org/10.1007/978-3-642-55220-5_5
Liu, S., Paterson, K.G.: Simulation-based selective opening cca security for pke from key encapsulation mechanisms. Cryptology ePrint Archive, Report 2015/010 (2015). http://eprint.iacr.org/
Peikert, C., Waters, B.: Lossy trapdoor functions and their applications. In: Dwork, C. (ed.) STOC 2008, pp. 187–196. ACM (2008)
Sahai, A., Waters, B.: How to use indistinguishability obfuscation: deniable encryption, and more. In: Shmoys, D.B. (ed.) Symposium on Theory of Computing, STOC 2014, pp. 475–484. ACM, New York (2014). http://doi.acm.org/10.1145/2591796.2591825
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 International Association for Cryptologic Research
About this paper
Cite this paper
Liu, S., Paterson, K.G. (2015). Simulation-Based Selective Opening CCA Security for PKE from Key Encapsulation Mechanisms. In: Katz, J. (eds) Public-Key Cryptography -- PKC 2015. PKC 2015. Lecture Notes in Computer Science(), vol 9020. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-46447-2_1
Download citation
DOI: https://doi.org/10.1007/978-3-662-46447-2_1
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-46446-5
Online ISBN: 978-3-662-46447-2
eBook Packages: Computer ScienceComputer Science (R0)