Abstract
We revisit Updatable Public-Key Encryption (UPKE), which was introduced as a practical mechanism for building forward-secure cryptographic protocols. We begin by observing that all UPKE notions to date are neither syntactically flexible nor secure enough for the most important multi-party protocols motivating UPKE. We provide an intuitive taxonomy of UPKE properties – some partially or completely overlooked in the past – along with an overview of known (explicit and implicit) UPKE constructions. We then introduce a formal UPKE definition capturing all intuitive properties needed for multi-party protocols.
Next, we provide a practical pairing-based construction for which we provide concrete bounds under a standard assumption in the random oracle and the algebraic group model. The efficiency profile of the scheme compares very favorably with existing UPKE constructions (despite the added flexibility and stronger security). For example, when used to improve the forward security of the Messaging Layer Security protocol [RFC9420], our new UPKE construction requires less than \(1.5\%\) of the bandwidth of the next-most efficient UPKE construction satisfying the strongest UPKE notion considered so far.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Note that new keys cannot prepared and distributed too far in advance since this only extends the window of time during which forward secrecy is not provided.
- 2.
Indeed, after an update by one group member, new members could only join the group after a different (receiving) group member comes online to validate and sign the updated key. This would mean that at least 2 existing group members are needed to invite a new member to the group.
- 3.
Essentially, the challenger needs some way to identify which \(\textit{pk}\)’s are old versions of \(\textit{pk}^*\) provided by the adversary. This seems to require storing the whole update history in \(\textit{pk}^*\) or \(\textit{jt}^*\).
- 4.
This seems to have happened because initial applications of UPKE are either in the 2-party setting, where forking is inherently not possible [JMM19] or they used very restricted models that artificially avoided forking by definition. Later UPKE constructions relied on UPKE security notions inspired by these early works but were not analyzed in their motivating applications using newer models. We provide a concrete scheme in the full version satisfying the definition [DKW21] but which leads to simple attacks when plugged into rTreeKEM.
- 5.
PCS is the mirror image of forward security where future keys should be secure despite past compromises.
- 6.
The number of signatures can be reduced by half using the same “hashing down the path” optimization as in the parent hash mechanism of MLS.
- 7.
The co-DL assumption in groups \(\mathbb {G}\) and \(\hat{\mathbb {G}}\), both of prime order p and generated by g and h, respectively, states that given \(g^x\in \mathbb {G}\) and \(h^x\in \hat{\mathbb {G}}\) for
, it is hard to compute x. The co-CDH assumption states that given \((g^x,g^r,h^x)\) for
, it is hard to compute \(g^{xr}\).
- 8.
In particular, we use an asymmetric pairing. That is, there are no efficiently computable homomorphisms between \(\mathbb {G}\) and \(\hat{\mathbb {G}}\). In practice, this type of pairing yields the most efficient constructions. Note also that assuming a pairing lets one prove the security of DHIES from co-CDH instead of the interactive assumption gap-CDH [OP01, ABR01] which is also the case for our UKEM (see below).
- 9.
One might wonder why extraction is not trivial in the AGM anyway: an algebraic adversary that has only seen the generator g and returns \(u^*\) must know a representation \(\alpha \) s.t. \(u^*=g^\alpha \). In the context of security proofs, this is not the case: Consider e.g., an algebraic reduction \(\mathcal R\) to the DL problem. This means that \(\mathcal R\) receives a DL instance \(g^*\) and simulates the game to an adversary \(\mathcal A\), providing it with group elements it computes as linear combinations of g and \(g^*\). When \(\mathcal A\) outputs a group element z, it accompanies it by a representation in basis all group elements received from \(\mathcal R\). From this, \(\mathcal R\) can compute a representation \((\alpha _0,\alpha _1)\) in basis \((g,g^*)\), that is, \(z=g^{\alpha _0}\cdot (g^*)^{\alpha _1}\). To argue that \(\mathcal R\) can extract from proofs of knowledge made by \(\mathcal A\), we need to turn \(\mathcal R\) together with \(\mathcal A\) into an adversary against simulation-extractability. This adversary is algebraic, but only in the sense that it can give representations in basis \((g,g^*)\) where \(g^*\) is a group element of which the extractor will not know the discrete logarithm. Therefore, [FO22] (and our proof in the full version) actually show that even in the presence of an “auxiliary-input” \(g^*\), one can extract the witness from a Schnorr proof.
- 10.
This restriction prevents trivial attacks, as in the following example: \(\mathcal A\) queries Enc(0), which creates node 1 with \((\textit{pk}_1,\textit{mt}_1,\textit{jt}_1)\) and ciphertext \(c_1\). It next queries Rev(1), to obtain the corresponding \(\textit{sk}_1\). It then queries Dec\((0,c_1,\textit{pk}_1,\textit{mt}_1,\textit{jt}_1)\), which creates node 2 with \(\textit{sk}_2=\textit{sk}_1\), and finally MChal(2), to receive \((c^*,K^*,\textit{pk}_3,\textit{mt}_3,\textit{jt}_3)\) and checks whether for \((K',\textit{sk}_3)\leftarrow \textsf {Decaps}(\textit{sk}_1,c^*,\textit{pk}_3)\) it holds that \(K'=K^*\).
References
Alwen, J., et al.: CoCoA: concurrent continuous group key agreement. In: Dunkelman, O., Dziembowski, S. (eds.) EUROCRYPT 2022. LNCS, vol. 13276, pp. 815–844. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-07085-3_28
Abdalla, M., Bellare, M., Rogaway, P.: DHIES: an encryption scheme based on the Diffie-Hellman problem. In: Contributions to IEEE P1363a, September 1998
Abdalla, M., Bellare, M., Rogaway, P.: The oracle Diffie-Hellman assumptions and an analysis of DHIES. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 143–158. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-45353-9_12
Alwen, J., Coretti, S., Dodis, Y., Tselekounis, Y.: Security analysis and improvements for the IETF MLS standard for group messaging. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12170, pp. 248–277. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56784-2_9
Alwen, J., Coretti, S., Dodis, Y., Tselekounis, Y.: Modular design of secure group messaging protocols and the security of MLS. In: Vigna, G., Shi, E. (eds.) ACM CCS 2021, pp. 1463–1483. ACM Press, November 2021
Alwen, J., Coretti, S., Jost, D., Mularczyk, M.: Continuous group key agreement with active security. In: Pass, R., Pietrzak, K. (eds.) TCC 2020. LNCS, vol. 12551, pp. 261–290. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64378-2_10
Alwen, J., Hartmann, D., Kiltz, E., Mularczyk, M.: Server-aided continuous group key agreement. In: Yin, H., Stavrou, A., Cremers, C., Shi, E. (eds.) ACM CCS 2022, pp. 69–82. ACM Press (2022)
Alwen, J., Jost, D., Mularczyk, M.: On the insider security of MLS. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022. LNCS, vol. 13508, pp. 34–68. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-15979-4_2
Alwen, J., Mularczyk, M., Tselekounis, Y.: Fork-resilient continuous group key agreement. In: Handschuh, H., Lysyanskaya, A. (eds.) CRYPTO 2023. LNCS, vol. 14084, pp. 396–429. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-38551-3_13
Asano, K., Watanabe, Y.: Updatable public key encryption with strong CCA security: security analysis and efficient generic construction. IACR Cryptology ePrint Archive, p. 976 (2023)
Barnes, R., Bhargavan, K., Lipp, B., Wood, C.A.: Hybrid public key encryption. RFC 9180, February 2022
Barnes, R., Beurdouche, B., Robert, R., Millican, J., Omara, E., Cohn-Gordon, K.: The messaging layer security (MLS) protocol. RFC 9420, July 2023
Boneh, D., Lynn, B., Shacham, H.: Short signatures from the weil pairing. In: Boyd, C. (ed.) ASIACRYPT 2001. LNCS, vol. 2248, pp. 514–532. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-45682-1_30
Barreto, P.S.L.M., Lynn, B., Scott, M.: On the selection of pairing-friendly groups. In: Matsui, M., Zuccherato, R.J. (eds.) SAC 2003. LNCS, vol. 3006, pp. 17–25. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24654-1_2
Bowe, S.: Bls12-381: New zk-snark elliptic curve construction
Cohn-Gordon, K., Cremers, C., Dowling, B., Garratt, L., Stebila, D.: A formal security analysis of the signal messaging protocol. J. Cryptol. 33(4), 1914–1983 (2020)
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). https://doi.org/10.1007/3-540-46766-1_36
Dodis, Y., Karthikeyan, H., Wichs, D.: Updatable public key encryption in the standard model. In: Nissim, K., Waters, B. (eds.) TCC 2021, Part III. LNCS, vol. 13044, pp. 254–285. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-90456-2_9
De Santis, A., Persiano, G.: Zero-knowledge proofs of knowledge without interaction (extended abstract). In: 33rd FOCS, pp. 427–436. IEEE Computer Society Press, October 1992
Durak, F.B., Vaudenay, S.: Bidirectional asynchronous ratcheted key agreement with linear complexity. In: Attrapadung, N., Yagi, T. (eds.) IWSEC 2019. LNCS, vol. 11689, pp. 343–362. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26834-3_20
Eaton, E., Jao, D., Komlo, C., Mokrani, Y.: Towards post-quantum key-updatable public-key encryption via supersingular isogenies. In: AlTawy, R., Hülsing, A. (eds.) SAC 2021. LNCS, vol. 13203, pp. 461–482. Springer, Cham (2022). https://doi.org/10.1007/978-3-030-99277-4_22
Fuchsbauer, G., Kiltz, E., Loss, J.: The algebraic group model and its applications. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10992, pp. 33–62. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96881-0_2
Fuchsbauer, G., Orrù, M.: Non-interactive mimblewimble transactions, revisited. In: Agrawal, S., Lin, D. (eds.) ASIACRYPT 2022, Part I. LNCS, vol. 13791, pp. 713–744. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-22963-3_24
Fuchsbauer, G., Plouviez, A., Seurin, Y.: Blind Schnorr signatures and signed ElGamal encryption in the algebraic group model. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020, Part II. LNCS, vol. 12106, pp. 63–95. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45724-2_3
Günther, F., Hale, B., Jager, T., Lauer, S.: 0-RTT key exchange with full forward secrecy. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017, Part III. LNCS, vol. 10212, pp. 519–548. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56617-7_18
Green, M.D., Miers, I.: Forward secure asynchronous messaging from puncturable encryption. In: 2015 IEEE Symposium on Security and Privacy, pp. 305–320. IEEE Computer Society Press, May 2015
Hashimoto, K., Katsumata, S., Postlethwaite, E., Prest, T., Westerbaan, B.: A concrete treatment of efficient continuous group key agreement via multi-recipient PKEs. In: Vigna, G., Shi, E. (eds.) ACM CCS 2021, pp. 1441–1462. ACM Press, November 2021
Haidar, C.A., Libert, B., Passelègue, A.: Updatable public key encryption from DCR: efficient constructions with stronger security. : Yin, H., Stavrou, A., Cremers, C., Shi, E. (eds.) ACM CCS 2022, pp. 11–22. ACM Press, November 2022
Haidar, C.A., Passelégue, A., Stehlé, D.: Efficient updatable public-key encryption from lattices. Cryptology ePrint Archive, Paper 2023/1400 (2023). https://eprint.iacr.org/2023/1400
Jost, D., Maurer, U., Mularczyk, M.: Efficient ratcheting: almost-optimal guarantees for secure messaging. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11476, pp. 159–188. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-17653-2_6
Jaeger, J., Stepanovs, I.: Optimal channel security against fine-grained state compromise: the safety of messaging. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10991, pp. 33–62. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96884-1_2
Okamoto, T., Pointcheval, D.: The gap-problems: a new class of problems for the security of cryptographic schemes. In: Kim, K. (ed.) PKC 2001. LNCS, vol. 1992, pp. 104–118. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-44586-2_8
Poettering, B., Rösler, P.: Towards bidirectional ratcheted key exchange. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018, Part I. LNCS, vol. 10991, pp. 3–32. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-96884-1_1
Pointcheval, D., Stern, J.: Security arguments for digital signatures and blind signatures. J. Cryptol. 13(3), 361–396 (2000)
Sahai, A.: Non-malleable non-interactive zero knowledge and adaptive chosen-ciphertext security. In: 40th FOCS, pp. 543–553. IEEE Computer Society Press, October 1999
Sakemi, Y., Kobayashi, T., Saito, T., Wahby, R.S.: Pairing-friendly curves. internet-draft draft-IRTF-CFRG-pairing-friendly-curves-11, Internet Engineering Task Force, November 2022. Work in Progress
Acknowledgments
This work was funded by the Vienna Science and Technology Fund (WWTF) [10.47379/VRG18002] and by the Austrian Science Fund (FWF) [10.55776/F8515-N]. The authors would like to thank the anonymous reviewers for their valuable comments and suggestions.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 International Association for Cryptologic Research
About this paper
Cite this paper
Alwen, J., Fuchsbauer, G., Mularczyk, M. (2024). Updatable Public-Key Encryption, Revisited. In: Joye, M., Leander, G. (eds) Advances in Cryptology – EUROCRYPT 2024. EUROCRYPT 2024. Lecture Notes in Computer Science, vol 14657. Springer, Cham. https://doi.org/10.1007/978-3-031-58754-2_13
Download citation
DOI: https://doi.org/10.1007/978-3-031-58754-2_13
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-58753-5
Online ISBN: 978-3-031-58754-2
eBook Packages: Computer ScienceComputer Science (R0)