Authenticated key exchange and signatures with tight security in the standard model. (English) Zbl 1489.94123
Malkin, Tal (ed.) et al., Advances in cryptology – CRYPTO 2021. 41st annual international cryptology conference, CRYPTO 2021, virtual event, August 16–20, 2021. Proceedings. Part IV. Cham: Springer. Lect. Notes Comput. Sci. 12828, 670-700 (2021).
Summary: We construct the first authenticated key exchange protocols that achieve tight security in the standard model. Previous works either relied on techniques that seem to inherently require a random oracle, or achieved only “Multi-Bit-Guess” security, which is not known to compose tightly, for instance, to build a secure channel.
Our constructions are generic, based on digital signatures and key encapsulation mechanisms (KEMs). The main technical challenges we resolve is to determine suitable KEM security notions which on the one hand are strong enough to yield tight security, but at the same time weak enough to be efficiently instantiable in the standard model, based on standard techniques such as universal hash proof systems.
Digital signature schemes with tight multi-user security in presence of adaptive corruptions are a central building block, which is used in all known constructions of tightly-secure AKE with full forward security. We identify a subtle gap in the security proof of the only previously known efficient standard model scheme by C. Bader et al. [Lect. Notes Comput. Sci. 9014, 629–658 (2015; Zbl 1359.94571)]. We develop a new variant, which yields the currently most efficient signature scheme that achieves this strong security notion without random oracles and based on standard hardness assumptions.
For the entire collection see [Zbl 1486.94003].
Our constructions are generic, based on digital signatures and key encapsulation mechanisms (KEMs). The main technical challenges we resolve is to determine suitable KEM security notions which on the one hand are strong enough to yield tight security, but at the same time weak enough to be efficiently instantiable in the standard model, based on standard techniques such as universal hash proof systems.
Digital signature schemes with tight multi-user security in presence of adaptive corruptions are a central building block, which is used in all known constructions of tightly-secure AKE with full forward security. We identify a subtle gap in the security proof of the only previously known efficient standard model scheme by C. Bader et al. [Lect. Notes Comput. Sci. 9014, 629–658 (2015; Zbl 1359.94571)]. We develop a new variant, which yields the currently most efficient signature scheme that achieves this strong security notion without random oracles and based on standard hardness assumptions.
For the entire collection see [Zbl 1486.94003].
Citations:
Zbl 1359.94571Software:
HMQVReferences:
| [1] | Bader, C.; Gritzalis, D.; Kiayias, A.; Askoxylakis, I., Efficient signatures with tight real world security in the random-oracle model, Cryptology and Network Security, 370-383 (2014), Cham: Springer, Cham · doi:10.1007/978-3-319-12280-9_24 |
| [2] | Bader, C.; Hofheinz, D.; Jager, T.; Kiltz, E.; Li, Y.; Dodis, Y.; Nielsen, JB, Tightly-secure authenticated key exchange, Theory of Cryptography, 629-658 (2015), Heidelberg: Springer, Heidelberg · Zbl 1359.94571 · doi:10.1007/978-3-662-46494-6_26 |
| [3] | Bader, C.; Jager, T.; Li, Y.; Schäge, S.; Fischlin, M.; Coron, J-S, On the impossibility of tight cryptographic reductions, Advances in Cryptology - EUROCRYPT 2016, 273-304 (2016), Heidelberg: Springer, Heidelberg · Zbl 1369.94519 · doi:10.1007/978-3-662-49896-5_10 |
| [4] | Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: Denning, D.E., Pyle, R., Ganesan, R., Sandhu, R.S., Ashby, V. (eds.) ACM CCS 1993, pp. 62-73. ACM Press, November 1993 |
| [5] | Bellare, M.; Rogaway, P.; Stinson, DR, Entity authentication and key distribution, Advances in Cryptology — CRYPTO’ 93, 232-249 (1994), Heidelberg: Springer, Heidelberg · Zbl 0870.94019 · doi:10.1007/3-540-48329-2_21 |
| [6] | Blazy, O.; Kiltz, E.; Pan, J.; Garay, JA; Gennaro, R., (Hierarchical) identity-based encryption from affine message authentication, Advances in Cryptology - CRYPTO 2014, 408-425 (2014), Heidelberg: Springer, Heidelberg · Zbl 1345.94044 · doi:10.1007/978-3-662-44371-2_23 |
| [7] | Canetti, R.; Krawczyk, H.; Pfitzmann, B., Analysis of key-exchange protocols and their use for building secure channels, Advances in Cryptology — EUROCRYPT 2001, 453-474 (2001), Heidelberg: Springer, Heidelberg · Zbl 0981.94032 · doi:10.1007/3-540-44987-6_28 |
| [8] | Cramer, R.; Kurosawa, K., Bounded CCA2-secure encryption, Advances in Cryptology - ASIACRYPT 2007, 502-518 (2007), Heidelberg: Springer, Heidelberg · Zbl 1153.94363 · doi:10.1007/978-3-540-76900-2_31 |
| [9] | Cramer, R.; Shoup, V.; Knudsen, LR, Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption, Advances in Cryptology — EUROCRYPT 2002, 45-64 (2002), Heidelberg: Springer, Heidelberg · Zbl 1055.94011 · doi:10.1007/3-540-46035-7_4 |
| [10] | Cremers, CJF; Feltz, M.; Foresti, S.; Yung, M.; Martinelli, F., Beyond eCK: perfect forward secrecy under actor compromise and ephemeral-key reveal, Computer Security - ESORICS 2012, 734-751 (2012), Heidelberg: Springer, Heidelberg · doi:10.1007/978-3-642-33167-1_42 |
| [11] | Davis, H., Günther, F.: Tighter proofs for the SIGMA and TLS 1.3 key exchange protocols. ACNS 2021 (2021). https://eprint.iacr.org/2020/1029 · Zbl 1491.94044 |
| [12] | Diemert, D., Gellert, K., Jager, T., Lyu, L.: More efficient digital signatures with tight multi-user security. In: 24th International Conference on Practice and Theory of Public-Key Cryptography, PKC 2021 (2021) · Zbl 1479.94309 |
| [13] | Diemert, D., Jager, T.: On the tight security of TLS 1.3: theoretically-sound cryptographic parameters for real-world deployments. Cryptology ePrint Archive, Report 2020/726 (2020). https://eprint.iacr.org/2020/726 · Zbl 1470.94082 |
| [14] | Escala, A.; Herold, G.; Kiltz, E.; Ràfols, C.; Villar, J.; Canetti, R.; Garay, JA, An algebraic framework for Diffie-Hellman assumptions, Advances in Cryptology - CRYPTO 2013, 129-147 (2013), Heidelberg: Springer, Heidelberg · Zbl 1316.94070 · doi:10.1007/978-3-642-40084-1_8 |
| [15] | Escala, A.; Herold, G.; Kiltz, E.; Ràfols, C.; Villar, JL, An algebraic framework for Diffie-Hellman assumptions, J. Cryptol., 30, 1, 242-288 (2017) · Zbl 1370.94510 · doi:10.1007/s00145-015-9220-6 |
| [16] | Fujioka, A.; Suzuki, K.; Xagawa, K.; Yoneyama, K.; Fischlin, M.; Buchmann, J.; Manulis, M., Strongly secure authenticated key exchange from factoring, codes, and lattices, Public Key Cryptography - PKC 2012, 467-484 (2012), Heidelberg: Springer, Heidelberg · Zbl 1300.94106 · doi:10.1007/978-3-642-30057-8_28 |
| [17] | Gay, R.; Hofheinz, D.; Kiltz, E.; Wee, H.; Fischlin, M.; Coron, J-S, Tightly CCA-secure encryption without pairings, Advances in Cryptology - EUROCRYPT 2016, 1-27 (2016), Heidelberg: Springer, Heidelberg · Zbl 1347.94032 · doi:10.1007/978-3-662-49890-3_1 |
| [18] | Gay, R.; Hofheinz, D.; Kohl, L.; Katz, J.; Shacham, H., Kurosawa-Desmedt meets tight security, Advances in Cryptology - CRYPTO 2017, 133-160 (2017), Cham: Springer, Cham · Zbl 1390.94835 · doi:10.1007/978-3-319-63697-9_5 |
| [19] | Gjøsteen, K.; Jager, T.; Shacham, H.; Boldyreva, A., Practical and tightly-secure digital signatures and authenticated key exchange, Advances in Cryptology - CRYPTO 2018, 95-125 (2018), Cham: Springer, Cham · Zbl 1436.94104 · doi:10.1007/978-3-319-96881-0_4 |
| [20] | Günther, CG; Quisquater, J-J; Vandewalle, J., An identity-based key-exchange protocol, Advances in Cryptology — EUROCRYPT ’89, 29-37 (1990), Heidelberg: Springer, Heidelberg · doi:10.1007/3-540-46885-4_5 |
| [21] | Han, S., et al.: Authenticated key exchange and signatures with tight security in the standard model. Cryptology ePrint Archive, Report 2021/863 (2021). https://eprint.iacr.org/2021/863 |
| [22] | Han, S.; Liu, S.; Lyu, L.; Gu, D.; Boldyreva, A.; Micciancio, D., Tight leakage-resilient CCA-security from quasi-adaptive hash proof system, Advances in Cryptology - CRYPTO 2019, 417-447 (2019), Cham: Springer, Cham · Zbl 1507.68061 · doi:10.1007/978-3-030-26951-7_15 |
| [23] | Jager, T.; Kiltz, E.; Riepel, D.; Schäge, S.; Canteaut, A.; Standaert, F-X, Tightly-secure authenticated key exchange, revisited, Advances in Cryptology - EUROCRYPT 2021, 117-146 (2021), Cham: Springer, Cham · Zbl 1479.94325 · doi:10.1007/978-3-030-77870-5_5 |
| [24] | Jager, T.; Kohlar, F.; Schäge, S.; Schwenk, J.; Safavi-Naini, R.; Canetti, R., On the security of TLS-DHE in the standard model, Advances in Cryptology - CRYPTO 2012, 273-293 (2012), Heidelberg: Springer, Heidelberg · Zbl 1296.94121 · doi:10.1007/978-3-642-32009-5_17 |
| [25] | Krawczyk, H.; Shoup, V., HMQV: a high-performance secure Diffie-Hellman protocol, Advances in Cryptology - CRYPTO 2005, 546-566 (2005), Heidelberg: Springer, Heidelberg · Zbl 1145.94445 · doi:10.1007/11535218_33 |
| [26] | Langrehr, R.; Pan, J.; Lin, D.; Sako, K., Tightly secure hierarchical identity-based encryption, Public-Key Cryptography - PKC 2019, 436-465 (2019), Cham: Springer, Cham · Zbl 1465.94076 · doi:10.1007/978-3-030-17253-4_15 |
| [27] | Langrehr, R.; Pan, J.; Moriai, S.; Wang, H., Unbounded HIBE with tight security, Advances in Cryptology - ASIACRYPT 2020, 129-159 (2020), Cham: Springer, Cham · Zbl 1511.94124 · doi:10.1007/978-3-030-64834-3_5 |
| [28] | Li, Y., Schäge, S.: No-match attacks and robust partnering definitions: defining trivial attacks for security protocols is not trivial. In: Thuraisingham, B.M., Evans, D., Malkin, T., Xu, D. (eds.) ACM CCS 2017, pp. 1343-1360. ACM Press, October/November 2017 |
| [29] | Liu, X.; Liu, S.; Gu, D.; Weng, J.; Moriai, S.; Wang, H., Two-pass authenticated key exchange with explicit authentication and tight security, Advances in Cryptology - ASIACRYPT 2020, 785-814 (2020), Cham: Springer, Cham · Zbl 1511.94184 · doi:10.1007/978-3-030-64834-3_27 |
| [30] | Morgan, A.; Pass, R.; Shi, E.; Moriai, S.; Wang, H., On the adaptive security of MACs and PRFs, Advances in Cryptology - ASIACRYPT 2020, 724-753 (2020), Cham: Springer, Cham · Zbl 1511.94140 · doi:10.1007/978-3-030-64837-4_24 |
| [31] | Morillo, P.; Ràfols, C.; Villar, JL; Cheon, JH; Takagi, T., The kernel matrix Diffie-Hellman assumption, Advances in Cryptology - ASIACRYPT 2016, 729-758 (2016), Heidelberg: Springer, Heidelberg · Zbl 1404.94100 · doi:10.1007/978-3-662-53887-6_27 |
| [32] | Nielsen, JB; Yung, M., Separating random oracle proofs from complexity theoretic proofs: the non-committing encryption case, Advances in Cryptology — CRYPTO 2002, 111-126 (2002), Heidelberg: Springer, Heidelberg · Zbl 1027.68601 · doi:10.1007/3-540-45708-9_8 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
