Related-key secure key encapsulation from extended computational bilinear Diffie-Hellman. (English) Zbl 1429.94065
Summary: As a special type of fault injection attacks, Related-Key Attacks (RKAs) allow an adversary to manipulate a cryptographic key and subsequently observe the outcomes of the cryptographic scheme under these modified keys. In the real life, related-key attacks are already practical enough to be implemented on cryptographic devices. To avoid cryptographic devices suffering from related-key attacks, it is necessary to design a cryptographic scheme that resists against such attacks. This paper proposes an efficient RKA-secure Key Encapsulation Mechanism (KEM), in which the adversary can modify the secret key sk to any value \(f(sk)\), as long as, \(f\) is a polynomial function of a bounded degree \(d\). Especially, the polynomial-RKA security can be reduced to a hard search problem, namely \(d\)-extended computational Bilinear Diffie-Hellman (BDH) problem, in the standard model. Our construction essentially refines the security of Haralambiev et al.’s BDH-based KEM scheme from chosen-ciphertext security to related-key security. The main technique applied in our scheme is the re-computation of the public key in the decryption algorithm so that any (non-trivial) modification to the secret key can be detected.
MSC:
| 94A60 | Cryptography |
References:
| [1] | Abdalla, M.; Bellare, M.; Neven, G., Robust encryption, (Micciancio, D., TCC 2010. TCC 2010, Lecture Notes in Computer Science, vol. 5978 (2010), Springer), 480-497 · Zbl 1274.94032 |
| [2] | Abdalla, M.; Benhamouda, F.; Passelègue, A.; Paterson, K. G., Related-key security for pseudorandom functions beyond the linear barrier, (Garay, J. A.; Gennaro, R., CRYPTO 2014, Part I. CRYPTO 2014, Part I, LNCS, vol. 8616 (2014), Springer), 77-94 · Zbl 1343.94035 |
| [3] | Applebaum, B.; Harnik, D.; Ishai, Y., Semantic security under related-key attacks and applications, Innovations in Computer Science - ICS 2010, 45-60 (2011), Tsinghua University Press |
| [4] | Bellare, M.; Cash, D., Pseudorandom functions and permutations provably secure against related-key attacks, (Rabin, T., CRYPTO 2010. CRYPTO 2010, LNCS, vol. 6223 (2010), Springer), 666-684 · Zbl 1283.94050 |
| [5] | Bellare, M.; Cash, D.; Miller, R., Cryptography secure against related-key attacks and tampering, (Lee, D. H.; Wang, X., ASIACRYPT 2011. ASIACRYPT 2011, LNCS, vol. 7073 (2011), Springer), 486-503 · Zbl 1227.94028 |
| [6] | Bellare, M.; Kohno, T., A theoretical treatment of related-key attacks: Rka-prps, rka-prfs, and applications, (Biham, E., EUROCRYPT 2003. EUROCRYPT 2003, LNCS, vol. 2656 (2003), Springer), 491-506 · Zbl 1038.94520 |
| [7] | Bellare, M.; Paterson, K. G.; Thomson, S., RKA security beyond the linear barrier: ibe, encryption and signatures, (Wang, X.; Sako, K., ASIACRYPT 2012. ASIACRYPT 2012, LNCS, vol. 7658 (2012), Springer), 331-348 · Zbl 1292.94028 |
| [8] | Biham, E., New types of cryptoanalytic attacks using related keys (extended abstract), (Helleseth, T., EUROCRYPT 1993. EUROCRYPT 1993, LNCS, vol. 765 (1993), Springer), 398-409 · Zbl 0951.94521 |
| [9] | Biham, E.; Shamir, A., Differential fault analysis of secret key cryptosystems, (K., J. B.S., CRYPTO 1997. CRYPTO 1997, LNCS, vol. 1294 (1997), Springer), 513-525 · Zbl 0886.94010 |
| [10] | Boneh, D.; Canetti, R.; Halevi, S.; Katz, J., Chosen-ciphertext security from identity-based encryption, SIAM J. Comput., 36, 5, 1301-1328 (2007) · Zbl 1138.94010 |
| [11] | Boneh, D.; DeMillo, R. A.; Lipton, R. J., On the importance of checking cryptographic protocols for faults (extended abstract), (Fumy, W., EUROCRYPT 1997. EUROCRYPT 1997, LNCS, vol. 1233 (1997), Springer), 37-51 |
| [12] | Boneh, D.; Franklin, M. K., Identity-based encryption from the weil pairing, SIAM J. Comput., 32, 3, 586-615 (2003) · Zbl 1046.94008 |
| [13] | Canetti, R.; Halevi, S.; Katz, J.; Camenisch, J., Chosen-ciphertext security from identity-based encryption, (Cachin, C., EUROCRYPT 2004. EUROCRYPT 2004, LNCS, vol. 3027 (2004), Springer), 207-222 · Zbl 1122.94358 |
| [14] | Cash, D.; Kiltz, E.; Shoup, V., The twin diffie-hellman problem and applications, J. Cryptol., 22, 4, 470-504 (2009) · Zbl 1220.94034 |
| [15] | Chen, Y.; Qin, B.; Zhang, J.; Deng, Y.; Chow, S. S.M., Non-malleable functions and their applications, (Cheng, C.; Chung, K.; Persiano, G.; Yang, B., PKC 2016, Part II. PKC 2016, Part II, LNCS, vol. 9615 (2016), Springer), 386-416 · Zbl 1395.94273 |
| [16] | Cramer, R.; Shoup, V., Universal hash proofs and a paradigm for adaptive chosen ciphertext secure public-key encryption, (Knudsen, L. R., EUROCRYPT 2002. EUROCRYPT 2002, LNCS, vol. 2332 (2002), Springer), 45-64 · Zbl 1055.94011 |
| [17] | 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) · Zbl 1045.94013 |
| [18] | Cui, H.; Mu, Y.; Au, M. H.; Mao, Z. M., Public-key encryption resilient to linear related-key attacks, (Zia, T. A.; Zomaya, A. Y.; Varadharajan, V., SecureComm 2013. SecureComm 2013, Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering, vol. 127 (2013), Springer), 182-196 |
| [19] | Cui, H.; Mu, Y.; Au, M. H., Public-key encryption resilient against linear related-key attacks revisited, TrustCom 2014, 268-275 (2014), IEEE Computer Society |
| [20] | Cui, H.; Mu, Y.; Au, M. H., Relations between robustness and RKA security under public-key encryption, Theor. Comput. Sci., 628, 78-91 (2016) · Zbl 1394.94929 |
| [21] | Fujisaki, E.; Xagawa, K., Efficient rka-secure KEM and IBE schemes against invertible functions, (Lauter, K. E.; Rodríguez-Henríquez, F., LATINCRYPT 2015. LATINCRYPT 2015, Lecture Notes in Computer Science, vol. 9230 (2015), Springer), 3-20 · Zbl 1370.94513 |
| [22] | Goldenberg, D.; Liskov, M., On related-secret pseudorandomness, (Micciancio, D., TCC 2010. TCC 2010, LNCS, vol. 5978 (2010), Springer), 255-272 · Zbl 1274.94070 |
| [23] | Goldreich, O.; Levin, L. A., A hard-core predicate for all one-way functions, (Johnson, D. S., STOC 1989 (1989), ACM), 25-32 |
| [24] | Goyal, V.; O’Neill, A.; Rao, V.; Ishai, Y., Correlated-input secure hash functions, TCC 2011. TCC 2011, LNCS, vol. 6597, 182-200 (2011), Springer · Zbl 1295.94075 |
| [25] | Halderman, J. A.; Schoen, S. D.; Heninger, N.; Clarkson, W.; Paul, W.; Calandrino, J. A.; Feldman, A. J.; Appelbaum, J.; Felten, E. W., Lest we remember: cold boot attacks on encryption keys, (van Oorschot, P. C., Proceedings of the 17th USENIX Security Symposium (2008), San Jose, CA, USA. USENIX Association, 2008), 45-60 |
| [26] | Haralambiev, K.; Jager, T.; Kiltz, E.; Shoup, V., Simple and efficient public-key encryption from computational diffie-hellman in the standard model, (Nguyen, P. Q.; Pointcheval, D., PKC 2010. PKC 2010, LNCS, vol. 6056 (2010), Springer), 1-18 · Zbl 1271.94020 |
| [27] | Hofheinz, D.; Kiltz, E., Secure hybrid encryption from weakened key encapsulation, (Menezes, A., CRYPTO 2007. CRYPTO 2007, LNCS, vol. 4622 (2007), Springer), 553-571 · Zbl 1215.94051 |
| [28] | Hofheinz, D.; Kiltz, E., Practical chosen ciphertext secure encryption from factoring, (Joux, A., EUROCRYPT 2009. EUROCRYPT 2009, LNCS, vol. 5479 (2009), Springer), 313-332 · Zbl 1239.94052 |
| [29] | Hofheinz, D.; Kiltz, E.; Shoup, V., Practical chosen ciphertext secure encryption from factoring, J. Cryptol., 26, 1, 102-118 (2013) · Zbl 1291.94097 |
| [30] | Jafargholi, Z.; Wichs, D., Tamper detection and continuous non-malleable codes, (Dodis, Y.; Nielsen, J. B., TCC 2015, Part I. TCC 2015, Part I, LNCS, vol. 9014 (2015), Springer), 451-480 · Zbl 1359.94607 |
| [31] | Jia, D.; Li, B.; Lu, X.; Mei, Q., Related key secure PKE from hash proof systems, (Yoshida, M.; Mouri, K., IWSEC 2014. IWSEC 2014, Lecture Notes in Computer Science, vol. 8639 (2014), Springer), 250-265 · Zbl 1417.94063 |
| [32] | Jia, D.; Lu, X.; Li, B.; Mei, Q., RKA secure PKE based on the DDH and HR assumptions, (Susilo, W.; Reyhanitabar, R., ProvSec 2013. ProvSec 2013, LNCS, vol. 8209 (2013), Springer), 271-287 · Zbl 1319.94069 |
| [33] | Knudsen, L. R., Cryptanalysis of LOKI91, (Seberry, J.; Zheng, Y., AUSCRYPT 1992. AUSCRYPT 1992, LNCS, vol. 718 (1992), Springer), 196-208 · Zbl 0868.94037 |
| [34] | Kocher, P. C., Timing attacks on implementations of diffie-hellman, RSA, DSS, and other systems, (Koblitz, N., CRYPTO 1996. CRYPTO 1996, LNCS, vol. 1109 (1996), Springer), 104-113 · Zbl 1329.94070 |
| [35] | Lewi, K.; Montgomery, H. W.; Raghunathan, A., Improved constructions of PRFs secure against related-key attacks, (Boureanu, I.; Owesarski, P.; Vaudenay, S., ACNS 2014. ACNS 2014, LNCS, vol. 8479 (2014), Springer), 44-61 · Zbl 1375.94143 |
| [36] | Lucks, S., Ciphers secure against related-key attacks, (Roy, B. K.; Meier, W., FSE 2004. FSE 2004, LNCS, vol. 3017 (2004), Springer), 359-370 · Zbl 1079.68552 |
| [37] | Peikert, C.; Waters, B., Lossy trapdoor functions and their applications, (Dwork, C., STOC 2008 (2008), ACM), 187-196 · Zbl 1228.94027 |
| [38] | Qin, B.; Liu, S.; Yuen, T. H.; Deng, R. H.; Chen, K., Continuous non-malleable key derivation and its application to related-key security, (Katz, J., PKC 2015. PKC 2015, LNCS, volume 9020 (2015), Springer), 557-578 · Zbl 1345.94085 |
| [39] | Shoup, V., Lower bounds for discrete logarithms and related problems, (Fumy, W., EUROCRYPT 1997. EUROCRYPT 1997, LNCS, vol. 1233 (1997), Springer), 256-266 |
| [40] | Sun, S.; Liu, J. K.; Yu, Y.; Qin, B.; Gu, D., Rka-secure public key encryptions against efficiently invertible functions, Comput. J., 59, 11, 1637-1658 (2016) |
| [41] | Wee, H., Public key encryption against related key attacks, (Fischlin, M.; Buchmann, J.; Manulis, M., PKC 2012. PKC 2012, LNCS, vol. 7293 (2012), Springer), 262-279 · Zbl 1290.94138 |
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.
