×

New approach to practical leakage-resilient public-key cryptography. (English) Zbl 1462.94032

Summary: We present a new approach to construct several leakage-resilient cryptographic primitives, including leakage-resilient public-key encryption (PKE) schemes, authenticated key exchange (AKE) protocols and low-latency key exchange (LLKE) protocols. To this end, we introduce a new primitive called leakage-resilient non-interactive key exchange (LR-NIKE) protocol. We introduce an appropriate security model for LR-NIKE protocols in the bounded memory leakage (BML) settings. We then show a secure construction of the LR-NIKE protocol in the BML setting that achieves an optimal leakage rate, i.e., \(1 - o(1)\). Our construction of LR-NIKE requires a minimal use of a leak-free hardware component. We argue that the use of such a leak-free hardware component seems to be unavoidable in any construction of an LR-NIKE protocol, even in the BML setting. Finally, we show how to construct the aforementioned leakage-resilient primitives from such an LR-NIKE protocol as summarized below. All these primitives also achieve the same (optimal) leakage rate as the underlying LR-NIKE protocol. We show how to construct a leakage-resilient (LR) IND-CCA-2-secure PKE scheme in the BML model generically from a bounded LR-NIKE (BLR-NIKE) protocol. Our construction of LR-IND-CCA-2 secure PKE differs significantly from the state-of-the-art constructions of these primitives, which mainly use hash proof techniques to achieve leakage resilience. Moreover, our transformation preserves the leakage-rate of the underlying BLR-NIKE protocol. We introduce a new leakage model for AKE protocols, in the BML setting, and present a leakage-resilient AKE protocol construction from the LR-NIKE protocol. We introduce the first-ever leakage model for LLKE protocols in the BML setting and the first construction of such a leakage-resilient LLKE from the LR-NIKE protocol.

MSC:

94A60 Cryptography
94A62 Authentication, digital signatures and secret sharing
14G50 Applications to coding theory and cryptography of arithmetic geometry
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)
68P25 Data encryption (aspects in computer science)
68M12 Network protocols

Software:

NAXOS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] S. Agrawal, Y. Dodis, V. Vaikuntanathan and D. Wichs, On continual leakage of discrete log representations, in: Advances in Cryptology—ASIACRYPT 2013. Part II, Lecture Notes in Comput. Sci. 8270, Springer, Heidelberg (2013), 401-420. · Zbl 1326.94069
[2] A. Akavia, S. Goldwasser and V. Vaikuntanathan, Simultaneous hardcore bits and cryptography against memory attacks, in: Theory of Cryptography, Lecture Notes in Comput. Sci. 5444, Springer, Berlin (2009), 474-495. · Zbl 1213.94075
[3] J. Alawatugoda, C. Boyd and D. Stebila, Continuous after-the-fact leakage-resilient key exchange, in: Information Security and Privacy—ACISP 2014, Lecture Notes in Comput. Sci. 8544, Springer, Cham (2014), 258-273. · Zbl 1337.94017
[4] J. Alawatugoda, D. Stebila and C. Boyd, Modelling after-the-fact leakage for key exchange, in: Proceedings of the 9th ACM Symposium on Information, Computer and Communications Security—ASIACCS 2014, ACM, New York (2014), 207-216.
[5] J. Alawatugoda, D. Stebila and C. Boyd, Continuous after-the-fact leakage resilient eCK-secure key exchange, in: Cryptography and Coding, Lecture Notes in Comput. Sci. 9496, Springer, Cham (2015), 277-294. · Zbl 1376.94024
[6] J. Alwen, Y. Dodis and D. Wichs, Leakage-resilient public-key cryptography in the bounded-retrieval model, in: Advances in Cryptology—CRYPTO 2009, Lecture Notes in Comput. Sci. 5677, Springer, Berlin (2009), 36-54. · Zbl 1252.94041
[7] F. Benhamouda, G. Couteau, D. Pointcheval and H. Wee, Implicit zero-knowledge arguments and applications to the malicious setting, in: Advances in Cryptology—CRYPTO 2015. Part II, Lecture Notes in Comput. Sci. 9216, Springer, Heidelberg (2015), 107-129. · Zbl 1351.94026
[8] F. Bergsma, T. Jager and J. Schwenk, One-round key exchange with strong security: an efficient and generic construction in the standard model, in: Public-Key Cryptography—PKC 2015, Lecture Notes in Comput. Sci. 9020, Springer, Heidelberg (2015), 477-494. · Zbl 1345.94041
[9] Z. Brakerski, Y. T. Kalai, J. Katz and V. Vaikuntanathan, Overcoming the hole in the bucket: public-key cryptography resilient to continual memory leakage, in: 2010 IEEE 51st Annual Symposium on Foundations of Computer Science—FOCS 2010, IEEE Computer Soc., Los Alamitos, CA (2010), 501-510.
[10] S. Chakraborty, J. Alawatugoda and C. P. Rangan, Leakage-resilient non-interactive key exchange in the continuous-memory leakage setting, in: Provable Security, Lecture Notes in Comput. Sci. 10592, Springer, Cham (2017), 167-187. · Zbl 1439.94022
[11] R. Chen, Y. Mu, G. Yang, W. Susilo and F. Guo, Strongly leakage-resilient authenticated key exchange, in: Topics in Cryptology—CT-RSA 2016, Lecture Notes in Comput. Sci. 9610, Springer, Cham (2016), 19-36. · Zbl 1332.94088
[12] R. Chen, Y. Mu, G. Yang, W. Susilo and F. Guo, Strong authenticated key exchange with auxiliary inputs, Des. Codes Cryptogr. 85 (2017), no. 1, 145-173. · Zbl 1381.94065
[13] W. Diffie and M. E. Hellman, New directions in cryptography, IEEE Trans. Inform. TheoryIT-22 (1976), no. 6, 644-654. · Zbl 0435.94018
[14] Y. Dodis, K. Haralambiev, A. López-Alt and D. Wichs, Cryptography against continuous memory attacks, in: 2010 IEEE 51st Annual Symposium on Foundations of Computer Science—FOCS 2010, IEEE Computer Soc., Los Alamitos, CA (2010), 511-520.
[15] Y. Dodis, K. Haralambiev, A. López-Alt and D. Wichs, Efficient public-key cryptography in the presence of key leakage, in: Advances in Cryptology—ASIACRYPT 2010, Lecture Notes in Comput. Sci. 6477, Springer, Berlin (2010), 613-631. · Zbl 1290.94064
[16] Y. Dodis, Y. T. Kalai and S. Lovett, On cryptography with auxiliary input, in: STOC’09—Proceedings of the 2009 ACM International Symposium on Theory of Computing, ACM, New York (2009), 621-630. · Zbl 1304.94046
[17] Y. Dodis, R. Ostrovsky, L. Reyzin and A. Smith, Fuzzy extractors: How to generate strong keys from biometrics and other noisy data, SIAM J. Comput. 38 (2008), no. 1, 97-139. · Zbl 1165.94326
[18] S. Dziembowski and S. Faust, Leakage-resilient circuits without computational assumptions, in: Theory of Cryptography Conference, Springer, Berlin (2012), 230-247. · Zbl 1303.94079
[19] E. S. V. Freire, D. Hofheinz, E. Kiltz and K. G. Paterson, Non-interactive key exchange, in: Public-Key Cryptography—PKC 2013, Lecture Notes in Comput. Sci. 7778, Springer, Heidelberg (2013), 254-271. · Zbl 1314.94069
[20] A. Fujioka, K. Suzuki, K. Xagawa and K. Yoneyama, Strongly secure authenticated key exchange from factoring, codes, and lattices, Des. Codes Cryptogr. 76 (2015), no. 3, 469-504. · Zbl 1344.94083
[21] D. Galindo, Boneh-Franklin identity based encryption revisited, in: Automata, Languages and Programming, Lecture Notes in Comput. Sci. 3580, Springer, Berlin (2005), 791-802. · Zbl 1084.94015
[22] S. Goldwasser and G. N. Rothblum, Securing computation against continuous leakage, in: Advances in Cryptology—CRYPTO 2010, Lecture Notes in Comput. Sci. 6223, Springer, Berlin (2010), 59-79. · Zbl 1280.94062
[23] B. Hale, T. Jager, S. Lauer and J. Schwenk, Speeding: On low-latency key exchange, preprint (2015), https://eprint.iacr.org/2015/1214.
[24] S. Halevi and H. Lin, After-the-fact leakage in public-key encryption, in: Theory of Cryptography, Lecture Notes in Comput. Sci. 6597, Springer, Heidelberg (2011), 107-124. · Zbl 1295.94078
[25] A. Juma and Y. Vahlis, Protecting cryptographic keys against continual leakage, in: Advances in Cryptology—CRYPTO 2010, Lecture Notes in Comput. Sci. 6223, Springer, Berlin (2010), 41-58. · Zbl 1280.94073
[26] J. Katz and V. Vaikuntanathan, Signature schemes with bounded leakage resilience, in: Advances in Cryptology—ASIACRYPT 2009, Lecture Notes in Comput. Sci. 5912, Springer, Berlin (2009), 703-720. · Zbl 1267.94072
[27] E. Kiltz and K. Pietrzak, Leakage resilient ElGamal encryption, in: Advances in Cryptology—ASIACRYPT 2010, Lecture Notes in Comput. Sci. 6477, Springer, Berlin (2010), 595-612. · Zbl 1290.94103
[28] B. LaMacchia, K. Lauter and A. Mityagin, Stronger security of authenticated key exchange, in: International Conference on Provable Security, Springer, Berlin (2007), 1-16. · Zbl 1138.94381
[29] T. Malkin, I. Teranishi, Y. Vahlis and M. Yung, Signatures resilient to continual leakage on memory and computation, in: Theory of Cryptography, Lecture Notes in Comput. Sci. 6597, Springer, Heidelberg (2011), 89-106. · Zbl 1295.94185
[30] S. Micali and L. Reyzin, Physically observable cryptography (extended abstract), in: Theory of Cryptography, Lecture Notes in Comput. Sci. 2951, Springer, Berlin (2004), 278-296. · Zbl 1197.94197
[31] H. Morita, J. C. N. Schuldt, T. Matsuda, G. Hanaoka and T. Iwata, On the security of non-interactive key exchange against related-key attacks, IEICE Trans. Fundam. Electron. Comm. Comput. Sci. 100 (2017), no. 9, 1910-1923.
[32] D. Moriyama and T. Okamoto, Leakage resilient eck-secure key exchange protocol without random oracles, in: Proceedings of the 6th ACM Symposium on Information, Computer and Communications Security—ASIACCS 2011, ACM, New York (2011), 441-447.
[33] M. Naor and G. Segev, Public-key cryptosystems resilient to key leakage, in: Advances in Cryptology—CRYPTO 2009, Lecture Notes in Comput. Sci. 5677, Springer, Berlin (2009), 18-35. · Zbl 1252.94091
[34] N. Nisan and D. Zuckerman, Randomness is linear in space, J. Comput. System Sci. 52 (1996), no. 1, 43-52. · Zbl 0846.68041
[35] B. Qin and S. Liu, Leakage-resilient chosen-ciphertext secure public-key encryption from hash proof system and one-time lossy filter, in: International Conference on the Theory and Application of Cryptology and Information Security, Springer, Heidelberg (2013), 381-400. · Zbl 1326.94117
[36] B. Qin and S. Liu, Leakage-flexible CCA-secure public-key encryption: Simple construction and free of pairing, in: Public-Key Cryptography—PKC 2014, Lecture Notes in Comput. Sci. 8383, Springer, Heidelberg (2014), 19-36. · Zbl 1335.94074
[37] V. Shoup, OAEP reconsidered, J. Cryptology15 (2002), no. 4, 223-249. · Zbl 1023.94006
[38] V. Shoup, Sequences of games: A tool for taming complexity in security proofs, preprint (2004), .
[39] Y. Wang and K. Tanaka, Generic transformation to strongly existentially unforgeable signature schemes with leakage resiliency, in: Provable Security, Lecture Notes in Comput. Sci. 8782, Springer, Cham (2014), 117-129. · Zbl 1368.94151
[40] J.-D. Wu, Y.-M. Tseng, S.-S. Huang and W.-C. Chou, Leakage-resilient certificateless key encapsulation scheme, Informatica (Vilnius)29 (2018), no. 1, 125-155. · Zbl 1398.94179
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.