SoK: Public Key Encryption with Openings | SpringerLink
Skip to main content
Springer Nature Link
Log in

SoK: Public Key Encryption with Openings

  • Conference paper
  • First Online:
Public-Key Cryptography – PKC 2024 (PKC 2024)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 14604))

Included in the following conference series:

  • 388 Accesses

Abstract

When modelling how public key encryption can enable secure communication, we should acknowledge that secret information, such as private keys or the encryption’s randomness, could become compromised. Intuitively, one would expect unrelated communication to remain secure, yet formalizing this intuition has proven challenging. Several security notions have appeared that aim to capture said scenario, ranging from the multi-user setting with corruptions, via selective opening attacks (SOA), to non-committing encryption (NCE). Remarkably, how the different approaches compare has not yet been systematically explored.

We provide a novel framework that maps each approach to an underlying philosophy of confidentiality: indistinguishability versus simulatability based, each with an a priori versus an a posteriori variant, leading to four distinct philosophies. In the absence of corruptions, these notions are largely equivalent; yet, in the presence of corruptions, they fall into a hierarchy of relative strengths, from \(\textrm{IND}\text {-}\textrm{CPA}\) and \(\textrm{IND}\text {-}\textrm{CCA}\) at the bottom, via indistinguishability SOA and simulatability SOA, to NCE at the top. We provide a concrete treatment for the four notions, discuss subtleties in their definitions and asymptotic interpretations and identify limitations of each. Furthermore, we re-cast the main implications of the hierarchy in a concrete security framework, summarize and contextualize other known relations, identify open problems, and close a few gaps.

Work by Hans Heum partially performed as part of his PhD studies at Simula UiB.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 13727
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 18589
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

References

  1. Bader, C., Hofheinz, D., Jager, T., Kiltz, E., Li, Y.: Tightly-secure authenticated key exchange. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015. LNCS, vol. 9014, pp. 629–658. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46494-6_26

    Chapter  Google Scholar 

  2. Bader, C., Jager, T., Li, Y., Schäge, S.: On the impossibility of tight cryptographic reductions. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 273–304. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49896-5_10

    Chapter  Google Scholar 

  3. Beaver, D., Haber, S.: Cryptographic protocols provably secure against dynamic adversaries. In: Rueppel, R.A. (ed.) EUROCRYPT 1992. LNCS, vol. 658, pp. 307–323. Springer, Heidelberg (1993). https://doi.org/10.1007/3-540-47555-9_26

    Chapter  Google Scholar 

  4. Bellare, M., Boldyreva, A., Micali, S.: Public-key encryption in a multi-user setting: security proofs and improvements. In: Preneel, B. (ed.) EUROCRYPT 2000. LNCS, vol. 1807, pp. 259–274. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-45539-6_18

    Chapter  Google Scholar 

  5. Bellare, M., Desai, A., Pointcheval, D., Rogaway, P.: Relations among notions of security for public-key encryption schemes. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 26–45. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0055718

    Chapter  Google Scholar 

  6. Bellare, M., Dowsley, R., Waters, B., Yilek, S.: Standard security does not imply security against selective-opening. In: Pointcheval, D., Johansson, T. (eds.) EUROCRYPT 2012. LNCS, vol. 7237, pp. 645–662. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-29011-4_38

    Chapter  Google Scholar 

  7. 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). https://doi.org/10.1007/978-3-642-01001-9_1

    Chapter  Google Scholar 

  8. Bellare, M., Yilek, S.: Encryption schemes secure under selective opening attack. Cryptology ePrint Archive, Report 2009/101 (original full version) (2009). https://eprint.iacr.org/2009/101, version 20090302:083605

  9. Bellare, M., Yilek, S.: Encryption schemes secure under selective opening attack. Cryptology ePrint Archive, Report 2009/101 (2009). https://eprint.iacr.org/2009/101

  10. Bellare, M., Yilek, S.: Encryption schemes secure under selective opening attack. Cryptology ePrint Archive, Report 2009/101 (updated full version) (2012). https://eprint.iacr.org/2009/101, version 20120923:212424

  11. Brunetta, C., Heum, H., Stam, M.: SoK: public key encryption with openings. Cryptology ePrint Archive, Report 2023/1337 (2023). https://eprint.iacr.org/2023/1337

  12. Camenisch, J., Lehmann, A., Neven, G., Samelin, K.: UC-secure non-interactive public-key encryption. In: Kópf, B., Chong, S. (eds.) CSF 2017 Computer Security Foundations Symposium (2017)

    Google Scholar 

  13. Canetti, R.: Universally composable security: a new paradigm for cryptographic protocols. Cryptology ePrint Archive, Report 2000/067 (2000). https://eprint.iacr.org/2000/067

  14. Canetti, R., Feige, U., Goldreich, O., Naor, M.: Adaptively secure multi-party computation. In: 28th ACM STOC, pp. 639–648. ACM Press, May 1996. https://doi.org/10.1145/237814.238015

  15. Canetti, R., Krawczyk, H., Nielsen, J.B.: Relaxing chosen-ciphertext security. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 565–582. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-45146-4_33

    Chapter  Google Scholar 

  16. Cramer, R., Shoup, V.: A practical public key cryptosystem provably secure against adaptive chosen ciphertext attack. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 13–25. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0055717

    Chapter  Google Scholar 

  17. Das, A., Dutta, S., Adhikari, A.: Indistinguishability against chosen ciphertext verification attack revisited: the complete picture. In: Susilo, W., Reyhanitabar, R. (eds.) ProvSec 2013. LNCS, vol. 8209, pp. 104–120. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-41227-1_6

    Chapter  Google Scholar 

  18. Dwork, C., Naor, M., Reingold, O., Stockmeyer, L.J.: Magic functions. In: 40th FOCS, pp. 523–534. IEEE Computer Society Press, October 1999. https://doi.org/10.1109/SFFCS.1999.814626

  19. ElGamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. In: Blakley, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 10–18. Springer, Heidelberg (1984)

    Google Scholar 

  20. 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). https://doi.org/10.1007/978-3-642-13190-5_20

    Chapter  Google Scholar 

  21. Fuchsbauer, G., Heuer, F., Kiltz, E., Pietrzak, K.: Standard security does imply security against selective opening for Markov distributions. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016. LNCS, vol. 9562, pp. 282–305. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49096-9_12

    Chapter  Google Scholar 

  22. Gellert, K., Jager, T., Lyu, L., Neuschulten, T.: On fingerprinting attacks and length-hiding encryption. In: Galbraith, S.D. (ed.) CT-RSA 2022. LNCS, vol. 13161, pp. 345–369. Springer, Cham (2022). https://doi.org/10.1007/978-3-030-95312-6_15

    Chapter  Google Scholar 

  23. Goldreich, O.: Foundations of Cryptography: Basic Tools, vol. 1. Cambridge University Press, Cambridge (2001)

    Book  Google Scholar 

  24. Goldwasser, S., Micali, S.: Probabilistic encryption and how to play mental poker keeping secret all partial information. In: 14th ACM STOC, pp. 365–377. ACM Press, May 1982. https://doi.org/10.1145/800070.802212

  25. Han, S., Liu, S., Gu, D.: Almost tight multi-user security under adaptive corruptions and leakages in the standard model. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023, Part III. LNCS, vol. 14006, pp. 132–162. Springer, Heidelberg (2023). https://doi.org/10.1007/978-3-031-30620-4_5

  26. Hara, K., Kitagawa, F., Matsuda, T., Hanaoka, G., Tanaka, K.: Simulation-based receiver selective opening CCA secure PKE from standard computational assumptions. In: Catalano, D., De Prisco, R. (eds.) SCN 2018. LNCS, vol. 11035, pp. 140–159. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-98113-0_8

    Chapter  Google Scholar 

  27. Hazay, C., Patra, A., Warinschi, B.: Selective opening security for receivers. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9452, pp. 443–469. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48797-6_19

    Chapter  Google Scholar 

  28. Heuer, F.: On the selective opening security of public-key encryption. Doctoral thesis, Ruhr-Universität Bochum, Universitätsbibliothek (2017)

    Google Scholar 

  29. Heum, H., Stam, M.: Tightness subtleties for multi-user PKE notions. In: Paterson, M.B. (ed.) IMACC 2021. LNCS, vol. 13129, pp. 75–104. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-92641-0_5

    Chapter  Google Scholar 

  30. Hofheinz, D.: Possibility and impossibility results for selective decommitments. J. Cryptol. 24(3), 470–516 (2011). https://doi.org/10.1007/s00145-010-9066-x

    Article  MathSciNet  Google Scholar 

  31. 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). https://doi.org/10.1007/978-3-540-74143-5_31

    Chapter  Google Scholar 

  32. Hofheinz, D., Müller-Quade, J., Steinwandt, R.: On modeling IND-CCA security in cryptographic protocols. Cryptology ePrint Archive, Report 2003/024 (2003). https://eprint.iacr.org/2003/024

  33. Hofheinz, D., Rao, V., Wichs, D.: Standard security does not imply indistinguishability under selective opening. In: Hirt, M., Smith, A. (eds.) TCC 2016. LNCS, vol. 9986, pp. 121–145. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-53644-5_5

    Chapter  Google Scholar 

  34. 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). https://doi.org/10.1007/978-3-642-54242-8_25

    Chapter  Google Scholar 

  35. Huang, Z., Lai, J., Han, S., Lyu, L., Weng, J.: Anonymous public key encryption under corruptions. In: Agrawal, S., Lin, D. (eds.) ASIACRYPT 2022, Part III. LNCS, vol. 13793, pp. 423–453. Springer, Heidelberg (2022). https://doi.org/10.1007/978-3-031-22969-5_15

  36. Huang, Z., Liu, S., Mao, X., Chen, K.: Non-malleability under selective opening attacks: implication and separation. In: Malkin, T., Kolesnikov, V., Lewko, A.B., Polychronakis, M. (eds.) ACNS 2015. LNCS, vol. 9092, pp. 87–104. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-28166-7_5

    Chapter  Google Scholar 

  37. Jager, T., Kiltz, E., Riepel, D., Schäge, S.: Tightly-secure authenticated key exchange, revisited. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12696, pp. 117–146. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77870-5_5

    Chapter  Google Scholar 

  38. Jager, T., Stam, M., Stanley-Oakes, R., Warinschi, B.: Multi-key authenticated encryption with corruptions: reductions are lossy. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017. LNCS, vol. 10677, pp. 409–441. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-70500-2_14

    Chapter  Google Scholar 

  39. Joye, M., Quisquater, J.-J., Yung, M.: On the power of misbehaving adversaries and security analysis of the original EPOC. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 208–222. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-45353-9_16

    Chapter  Google Scholar 

  40. Küsters, R., Tuengerthal, M.: Joint state theorems for public-key encryption and digital signature functionalities with local computation. In: Sabelfeld, A. (ed.) CSF 2008 Computer Security Foundations Symposium, pp. 270–284. IEEE Computer Society Press (2008). https://doi.org/10.1109/CSF.2008.18

  41. Lai, J., Yang, R., Huang, Z., Weng, J.: Simulation-based bi-selective opening security for public key encryption. In: Tibouchi, M., Wang, H. (eds.) ASIACRYPT 2021. LNCS, vol. 13091, pp. 456–482. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-92075-3_16

    Chapter  Google Scholar 

  42. Lee, Y., Lee, D.H., Park, J.H.: Tightly CCA-secure encryption scheme in a multi-user setting with corruptions. DCC 88(11), 2433–2452 (2020). https://doi.org/10.1007/s10623-020-00794-z

    Article  MathSciNet  Google Scholar 

  43. Nielsen, J.B.: Separating random oracle proofs from complexity theoretic proofs: the non-committing encryption case. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 111–126. Springer, Heidelberg (2002). https://doi.org/10.1007/3-540-45708-9_8

    Chapter  Google Scholar 

  44. Okamoto, T., Pointcheval, D.: REACT: rapid enhanced-security asymmetric cryptosystem transform. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 159–174. Springer, Heidelberg (2000). https://doi.org/10.1007/3-540-45353-9_13

    Chapter  Google Scholar 

  45. Shamir, A.: How to share a secret. Commun. Assoc. Comput. Mach. 22(11), 612–613 (1979). https://doi.org/10.1145/359168.359176

    Article  MathSciNet  Google Scholar 

  46. Shannon, C.E.: Communication theory of secrecy systems. Bell Syst. Techn. J. 28(4), 656–715 (1949)

    Article  MathSciNet  Google Scholar 

  47. Tezcan, C., Vaudenay, S.: On hiding a plaintext length by preencryption. In: Lopez, J., Tsudik, G. (eds.) ACNS 2011. LNCS, vol. 6715, pp. 345–358. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-21554-4_20

    Chapter  Google Scholar 

  48. Watanabe, Y., Shikata, J., Imai, H.: Equivalence between semantic security and indistinguishability against chosen ciphertext attacks. In: Desmedt, Y.G. (ed.) PKC 2003. LNCS, vol. 2567, pp. 71–84. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-36288-6_6

    Chapter  Google Scholar 

  49. Yang, R., Lai, J., Huang, Z., Au, M.H., Xu, Q., Susilo, W.: Possibility and impossibility results for receiver selective opening secure PKE in the multi-challenge setting. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020. LNCS, vol. 12491, pp. 191–220. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64837-4_7

    Chapter  Google Scholar 

Download references

Acknowledgement

The authors would like to thank Joseph Jaeger for many helpful comments and discussions.

Author information

Authors and Affiliations

  1. Simula UiB, Bergen, Norway

    Carlo Brunetta & Martijn Stam

  2. NTNU - Norwegian University of Science and Technology, Trondheim, Norway

    Hans Heum

Authors
  1. Carlo Brunetta
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Hans Heum
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Martijn Stam
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Hans Heum .

Editor information

Editors and Affiliations

  1. The University of Sydney, Sydney, NSW, Australia

    Qiang Tang

  2. The Australian National University, Acton, ACT, Australia

    Vanessa Teague

Rights and permissions

Reprints and permissions

Copyright information

© 2024 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Brunetta, C., Heum, H., Stam, M. (2024). SoK: Public Key Encryption with Openings. In: Tang, Q., Teague, V. (eds) Public-Key Cryptography – PKC 2024. PKC 2024. Lecture Notes in Computer Science, vol 14604. Springer, Cham. https://doi.org/10.1007/978-3-031-57728-4_2

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-57728-4_2

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-57727-7

  • Online ISBN: 978-3-031-57728-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships

Search

Navigation