Updatable hash proof system and its applications. (English) Zbl 1502.94041

Pernul, Günther (ed.) et al., Computer security – ESORICS 2015. 20th European symposium on research in computer security, Vienna, Austria, September 21–25, 2015. Proceedings. Part I. Cham: Springer. Lect. Notes Comput. Sci. 9326, 266-285 (2015).
Summary: To tackle with physical attacks to real world cryptosystems, leakage resilient cryptography was developed. In this setting, the adversary is allowed to have access to the internal state of a cryptographic system, thus violates the black-box reduction used in cryptography. Especially when considering continual memory leakage (CML), i.e., there is no predetermined bound on the leakage of the internal information, the task is extremely tough.
In this paper, we solve this problem by introducing a new primitive called updatable hash proof system (UHPS). A UHPS can be viewed as a special Hash proof system (HPS), which served as a fundamental tool in constructing public key encryption (PKE) schemes in both leakage-free and leaky settings. A remarkable property of UHPS is that by simply substituting the HPS component with a UHPS component in a PKE scheme, one obtains a new PKE scheme secure in the CML setting. Moreover, the resulting PKE scheme enjoys the same advantage of the original HPS-based PKE, for instance, still “compatible” with known transforms. We then give instantiations of UHPS from widely-accepted assumptions, including the symmetric external Diffie-Hellman assumption and the d-linear assumption. Interestingly, we notice that when instantiated with concrete assumptions, the resulting chosen-ciphertext secure PKE scheme is by far the most efficient.
For the entire collection see [Zbl 1492.68028].


94A60 Cryptography
Full Text: DOI


[1] Abe, M.; Gennaro, R.; Kurosawa, K.; Shoup, V.; Cramer, R., Tag-KEM/DEM: a new framework for hybrid encryption and a new analysis of kurosawa-desmedt KEM, Advances in Cryptology - EUROCRYPT 2005, 128-146, 2005, Heidelberg: Springer, Heidelberg · Zbl 1137.94336 · doi:10.1007/11426639_8
[2] Akavia, A.; Goldwasser, S.; Vaikuntanathan, V.; Reingold, O., Simultaneous hardcore bits and cryptography against memory attacks, Theory of Cryptography, 474-495, 2009, Heidelberg: Springer, Heidelberg · Zbl 1213.94075 · doi:10.1007/978-3-642-00457-5_28
[3] Biham, E.; Shamir, A.; Kaliski, BS Jr, Differential fault analysis of secret key cryptosystems, Advances in Cryptology - CRYPTO ’97, 513-525, 1997, Heidelberg: Springer, Heidelberg · Zbl 0886.94010 · doi:10.1007/BFb0052259
[4] Brakerski, Z., Kalai, Y.T., Katz, J., Vaikuntanathan, V.: Overcoming the hole in the bucket: public-key cryptography resilient to continual memory leakage. In: FOCS, pp. 501-510. IEEE (2010)
[5] Brumley, D., Boneh, D.: Remote timing attacks are practical. In: USENIX Security Symposium, p. 1. USENIX Association (2003)
[6] Canetti, R.; Halevi, S.; Katz, J.; Cachin, C.; Camenisch, JL, Chosen-ciphertext security from identity-based encryption, Advances in Cryptology - EUROCRYPT 2004, 207-222, 2004, Heidelberg: Springer, Heidelberg · Zbl 1122.94358 · doi:10.1007/978-3-540-24676-3_13
[7] Carter, J.L., Wegman, M.N.: Universal classes of hash functions. In: STOC, pp. 106-112. ACM (1977)
[8] 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, 2002, Heidelberg: Springer, Heidelberg · Zbl 1055.94011 · doi:10.1007/3-540-46035-7_4
[9] Dodis, Y., Haralambiev, K., Lopez-Alt, A., Wichs, D.: Cryptography against continuous memory attacks. In: FOCS, pp. 511-520. IEEE (2010)
[10] Dodis, Y., Kalai, Y.T., Lovett, S.: On cryptography with auxiliary input. In: STOC, pp. 621-630. ACM (2009) · Zbl 1304.94046
[11] Dodis, Y., Lewko, A., Waters, B., Wichs, D.: Storing secrets on continually leaky devices. In: FOCS, pp. 688-697. IEEE (2011) · Zbl 1292.94055
[12] Dodis, Y.; Pietrzak, K.; Rabin, T., Leakage-resilient pseudorandom functions and side-channel attacks on feistel networks, Advances in Cryptology - CRYPTO 2010, 21-40, 2010, Heidelberg: Springer, Heidelberg · Zbl 1280.94047 · doi:10.1007/978-3-642-14623-7_2
[13] Dodis, Y.; Reyzin, L.; Smith, A.; Cachin, C.; Camenisch, JL, Fuzzy extractors: how to generate strong keys from biometrics and other noisy data, Advances in Cryptology - EUROCRYPT 2004, 523-540, 2004, Heidelberg: Springer, Heidelberg · Zbl 1122.94368 · doi:10.1007/978-3-540-24676-3_31
[14] Dziembowski, S., Pietrzak, K.: Leakage-resilient cryptography. In: FOCS, pp. 293-302. IEEE (2008)
[15] Gennaro, R.; Lindell, Y.; Biham, E., A framework for password-based authenticated key exchange, Advances in Cryptology - EUROCRPYT 2003, 2003, Heidelberg: Springer, Heidelberg · Zbl 1038.94534
[16] Groth, J.; Sahai, A.; Smart, NP, Efficient non-interactive proof systems for bilinear groups, Advances in Cryptology - EUROCRYPT 2008, 415-432, 2008, Heidelberg: Springer, Heidelberg · Zbl 1149.94320 · doi:10.1007/978-3-540-78967-3_24
[17] 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. In: USENIX Security Symposium, pp. 45-60. USENIX Association (2008)
[18] Hazay, C.; López-Alt, A.; Wee, H.; Wichs, D.; Johansson, T.; Nguyen, PQ, Leakage-resilient cryptography from minimal assumptions, Advances in Cryptology - EUROCRYPT 2013, 160-176, 2013, Heidelberg: Springer, Heidelberg · Zbl 1306.94061 · doi:10.1007/978-3-642-38348-9_10
[19] Hemenway, B.; Ostrovsky, R.; Fischlin, M.; Buchmann, J.; Manulis, M., Extended-DDH and lossy trapdoor functions, Public Key Cryptography - PKC 2012, 627-643, 2012, Heidelberg: Springer, Heidelberg · Zbl 1291.94096 · doi:10.1007/978-3-642-30057-8_37
[20] Hofheinz, D.; Kiltz, E.; Menezes, A., Secure hybrid encryption from weakened key encapsulation, Advances in Cryptology - CRYPTO 2007, 553-571, 2007, Heidelberg: Springer, Heidelberg · Zbl 1215.94051 · doi:10.1007/978-3-540-74143-5_31
[21] Kocher, PC; Jaffe, J.; Jun, B.; Wiener, M., Differential power analysis, Advances in Cryptology - CRYPTO ’99, 388, 1999, Heidelberg: Springer, Heidelberg · Zbl 0942.94501 · doi:10.1007/3-540-48405-1_25
[22] Kocher, PC; Koblitz, N., Timing attacks on implementations of Diffie-Hellman, RSA, DSS, and other systems, Advances in Cryptology - CRYPTO ’96, 104-113, 1996, Heidelberg: Springer, Heidelberg · Zbl 1329.94070 · doi:10.1007/3-540-68697-5_9
[23] Koppula, V., Pandey, O., Rouselakis, Y., Waters, B.: Deterministic public-key encryption under continual leakage. Cryptology ePrint Archive, Report 2014/780 (2014). http://eprint.iacr.org/
[24] Kurosawa, K.; Desmedt, YG; Franklin, M., A new paradigm of hybrid encryption scheme, Advances in Cryptology - CRYPTO 2004, 426-442, 2004, Heidelberg: Springer, Heidelberg · Zbl 1104.94028 · doi:10.1007/978-3-540-28628-8_26
[25] Lewko, A., Lewko, M., Waters, B.: How to leak on key updates. In: STOC, pp. 725-734. ACM (2011) · Zbl 1288.94074
[26] Lewko, A.; Rouselakis, Y.; Waters, B.; Ishai, Y., Achieving leakage resilience through dual system encryption, Theory of Cryptography, 70-88, 2011, Heidelberg: Springer, Heidelberg · Zbl 1291.94118 · doi:10.1007/978-3-642-19571-6_6
[27] Micali, S.; Reyzin, L.; Naor, M., Physically observable cryptography, Theory of Cryptography, 278-296, 2004, Heidelberg: Springer, Heidelberg · Zbl 1197.94197 · doi:10.1007/978-3-540-24638-1_16
[28] Naor, M.; Segev, G.; Halevi, S., Public-key cryptosystems resilient to key leakage, Advances in Cryptology - CRYPTO 2009, 18-35, 2009, Heidelberg: Springer, Heidelberg · Zbl 1252.94091 · doi:10.1007/978-3-642-03356-8_2
[29] Naor, M., Yung, M.: Public-key cryptosystems provably secure against chosen ciphertext attacks. In: STOC, pp. 427-437. ACM (1990)
[30] Ors, S.B., Gurkaynak, F., Oswald, E., Preneel, B.: Power-analysis attack on an asic aes implementation. In: Information Technology: Coding and Computing, pp. 546-552. IEEE (2004)
[31] Pietrzak, K.; Joux, A., A leakage-resilient mode of operation, Advances in Cryptology - EUROCRYPT 2009, 462-482, 2009, Heidelberg: Springer, Heidelberg · Zbl 1239.94062 · doi:10.1007/978-3-642-01001-9_27
[32] Qin, B.; Liu, S.; Sako, K.; Sarkar, P., Leakage-resilient chosen-ciphertext secure public-key encryption from hash proof system and one-time lossy filter, Advances in Cryptology - ASIACRYPT 2013, 381-400, 2013, Heidelberg: Springer, Heidelberg · Zbl 1326.94117 · doi:10.1007/978-3-642-42045-0_20
[33] Qin, B.; Liu, S.; Krawczyk, H., Leakage-flexible CCA-secure public-key encryption: simple construction and free of pairing, Public-Key Cryptography - PKC 2014, 19-36, 2014, Heidelberg: Springer, Heidelberg · Zbl 1335.94074 · doi:10.1007/978-3-642-54631-0_2
[34] Quisquater, J-J; Samyde, D.; Attali, S.; Jensen, T., ElectroMagnetic Analysis (EMA): measures and counter-measures for smart cards, Smart Card Programming and Security, 200, 2001, Heidelberg: Springer, Heidelberg · Zbl 1003.68609 · doi:10.1007/3-540-45418-7_17
[35] Sahai, A.: Non-malleable non-interactive zero knowledge and adaptive chosen-ciphertext security. In: FOCS, pp. 543-553. IEEE (1999)
[36] Wichs, D.: Cryptographic resilience to continual information leakage. Ph.D. thesis, New York University (2011)
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.