×

Towards sound fresh re-keying with hard (physical) learning problems. (English) Zbl 1391.94746

Robshaw, Matthew (ed.) et al., Advances in cryptology – CRYPTO 2016. 36th annual international cryptology conference, Santa Barbara, CA, USA, August 14–18, 2016. Proceedings. Part II. Berlin: Springer (ISBN 978-3-662-53007-8/pbk; 978-3-662-53008-5/ebook). Lecture Notes in Computer Science 9815, 272-301 (2016).
Summary: Most leakage-resilient cryptographic constructions aim at limiting the information adversaries can obtain about secret keys. In the case of asymmetric algorithms, this is usually obtained by secret sharing (aka masking) the key, which is made easy by their algebraic properties. In the case of symmetric algorithms, it is rather key evolution that is exploited. While more efficient, the scope of this second solution is limited to stateful primitives that easily allow for key evolution such as stream ciphers. Unfortunately, it seems generally hard to avoid the need of (at least one) execution of a stateless primitive, both for encryption and authentication protocols. As a result, fresh re-keying has emerged as an alternative solution, in which a block cipher that is hard to protect against side-channel attacks is re-keyed with a stateless function that is easy to mask. While previous proposals in this direction were all based on heuristic arguments, we propose two new constructions that, for the first time, allow a more formal treatment of fresh re-keying. More precisely, we reduce the security of our re-keying schemes to two building blocks that can be of independent interest. The first one is an assumption of Learning Parity with Leakage, which leverages the noise that is available in side-channel measurements. The second one is based on the Learning with Rounding assumption, which can be seen as an alternative solution for low-noise implementations. Both constructions are efficient and easy to mask, since they are key homomorphic or almost key homomorphic.
For the entire collection see [Zbl 1344.94002].

MSC:

94A60 Cryptography
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abdalla, M., Belaïd, S., Fouque, P.-A.: Leakage-resilient symmetric encryption via re-keying. In: Bertoni, G., Coron, J.-S. (eds.) CHES 2013. LNCS, vol. 8086, pp. 471–488. Springer, Heidelberg (2013) · Zbl 1353.94029 · doi:10.1007/978-3-642-40349-1_27
[2] Albrecht, M.R., Player, R., Scott, S.: On the concrete hardness of learning with errors. J. Math. Cryptol. 9(3), 169–203 (2015) · Zbl 1352.94023 · doi:10.1515/jmc-2015-0016
[3] Alwen, J., Krenn, S., Pietrzak, K., Wichs, D.: Learning with rounding, revisited - new reduction, properties and applications. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013, Part I. LNCS, vol. 8042, pp. 57–74. Springer, Heidelberg (2013) · Zbl 1310.94123 · doi:10.1007/978-3-642-40041-4_4
[4] Andrychowicz, M., Dziembowski, S., Faust, S.: Circuit compilers with \[ O(1= \text{log}(n)) \] leakage rate. In: EUROCRYPT (2016) · Zbl 1371.94620
[5] Arora, S., Ge, R.: New algorithms for learning in presence of errors. In: ICALP (2011) · Zbl 1332.68099 · doi:10.1007/978-3-642-22006-7_34
[6] Balasch, J., Gierlichs, B., Grosso, V., Reparaz, O., Standaert, F.-X.: On the cost of lazy engineering for masked software implementations. In: Joye, M., Moradi, A. (eds.) CARDIS 2014. LNCS, vol. 8968, pp. 64–81. Springer, Heidelberg (2015) · doi:10.1007/978-3-319-16763-3_5
[7] Banerjee, A., Peikert, C., Rosen, A.: Pseudorandom functions, lattices. In: EUROCRYPT (2012) · Zbl 1297.68071 · doi:10.1007/978-3-642-29011-4_42
[8] Banerjee, A., Brenner, H., Leurent, G., Peikert, C., Rosen, A.: SPRING: fast pseudorandom functions from rounded ring products. In: Cid, C., Rechberger, C. (eds.) FSE 2014. LNCS, vol. 8540, pp. 38–57. Springer, Heidelberg (2015) · Zbl 1382.94056 · doi:10.1007/978-3-662-46706-0_3
[9] Belaïd, S., Fouque, P., Gérard, B.: Side-channel analysis of multiplications in GF(2128) - application to AES-GCM. In: ASIACRYPT (2014) · Zbl 1317.94083
[10] Belaïd, S., Grosso, V., Standaert, F.: Masking and leakage-resilientprimitives: one, the other(s) or both? Crypt. Commun. 7(1), 163–184 (2015) · Zbl 1365.94401 · doi:10.1007/s12095-014-0113-6
[11] Belaïd, S., Coron, J.-S., Fouque, P.-A., Gérard, B., Kammerer, J.-G., Prouff, E.: Improved side-channel analysis of finite-field multiplication. In: Güneysu, T., Handschuh, H. (eds.) CHES 2015. LNCS, vol. 9293, pp. 395–415. Springer, Heidelberg (2015) · Zbl 1380.94073 · doi:10.1007/978-3-662-48324-4_20
[12] Bilgin, B., Gierlichs, B., Nikova, S., Nikov, V., Rijmen, V.: A more efficient AES threshold implementation. In: AFRICACRYPT (2014) · Zbl 1288.94053 · doi:10.1007/978-3-319-06734-6_17
[13] Bilgin, B., Gierlichs, B., Nikova, S., Nikov, V., Rijmen, V.: Higher-order threshold implementations. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014, Part II. LNCS, vol. 8874, pp. 326–343. Springer, Heidelberg (2014) · Zbl 1317.94086 · doi:10.1007/978-3-662-45608-8_18
[14] Blum, A., Kalai, A., Wasserman, H.: Noise-tolerant learning, the parity problem, and the statistical query model. In: ACM STOC (2000) · Zbl 1296.68122 · doi:10.1145/335305.335355
[15] Blum, A., Furst, M.L., Kearns, M., Lipton, R.J.: Cryptographic primitives based on hard learning problems. In: Stinson, D.R. (ed.) CRYPTO 1993. LNCS, vol. 773, pp. 278–291. Springer, Heidelberg (1994) · Zbl 0870.94021 · doi:10.1007/3-540-48329-2_24
[16] Bogdanov, A., Guo, S., Masny, D., Richelson, S., Rosen, A.: On the hardness of learning with rounding over small modulus. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016-A. LNCS, vol. 9562, pp. 209–224. Springer, Heidelberg (2016). doi: 10.1007/978-3-662-49096-9_9 · Zbl 1388.94035 · doi:10.1007/978-3-662-49096-9_9
[17] Bogos, S., Tramér, F., Vaudenay, S.: On solving LPN using BKW and variants. In: IACR Cryptology ePrint Archive (2015) · Zbl 1338.94068
[18] Boneh, D., Lewi, K., Montgomery, H.W., Raghunathan, A.: Key homomorphic PRFs, their applications. In: CRYPTO (2013) · Zbl 1310.94129 · doi:10.1007/978-3-642-40041-4_23
[19] Brenner, H., Gaspar, L., Leurent, G., Rosen, A., Standaert, F.-X.: FPGA implementations of SPRING. In: Batina, L., Robshaw, M. (eds.) CHES 2014. LNCS, vol. 8731, pp. 414–432. Springer, Heidelberg (2014) · Zbl 1396.94063 · doi:10.1007/978-3-662-44709-3_23
[20] Chari, S., Rao, J.R., Rohatgi, P.: Template attacks. In: CHES (2002) · Zbl 1019.68541
[21] Chari, S., Jutla, C.S., Rao, J.R., Rohatgi, P.: Towards sound approaches to counteract power-analysis attacks. In: CRYPTO (1999) · Zbl 0942.68045 · doi:10.1007/3-540-48405-1_26
[22] Coron, J.-S., Giraud, C., Prouff, E., Renner, S., Rivain, M., Vadnala, P.K.: Conversion of security proofs from one leakage model to another: a new issue. In: Schindler, W., Huss, S.A. (eds.) COSADE 2012. LNCS, vol. 7275, pp. 69–81. Springer, Heidelberg (2012) · Zbl 1352.94032 · doi:10.1007/978-3-642-29912-4_6
[23] Dobraunig, C., Koeune, F., Mangard, S., Mendel, F., Standaert, F.: Towards fresh, hybrid re-keying schemes with beyond birthday security. In: CARDIS (2015)
[24] Dodis, Y., Pietrzak, K.: Leakage-resilient pseudorandom functions and side-channel attacks on feistel networks. In: CRYPTO (2010) · Zbl 1280.94047 · doi:10.1007/978-3-642-14623-7_2
[25] Döttling, N., Müller-Quade, J.: Lossy codes, a new variant of the learning-with-errors problem. In: EUROCRYPT (2013) · Zbl 1300.94052 · doi:10.1007/978-3-642-38348-9_2
[26] Duc, A., Dziembowski, S., Faust, S.: Unifying leakage models: from probing attacks to noisy leakage. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 423–440. Springer, Heidelberg (2014) · Zbl 1326.94086 · doi:10.1007/978-3-642-55220-5_24
[27] Duc, A., Faust, S., Standaert, F.-X.: Making masking security proofs concrete. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9056, pp. 401–429. Springer, Heidelberg (2015) · Zbl 1370.94508 · doi:10.1007/978-3-662-46800-5_16
[28] Durvaux, F., Standaert, F.-X., Veyrat-Charvillon, N.: How to certify the leakage of a chip? In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 459–476. Springer, Heidelberg (2014) · Zbl 1326.94088 · doi:10.1007/978-3-642-55220-5_26
[29] Dziembowski, S., Pietrzak, K.: Leakage-resilient cryptography. In: IEEE FOCS (2008) · doi:10.1109/FOCS.2008.56
[30] Gammel, B., Fischer, W., Mangard, S.: Generating a session key for authentication and secure data transfer. US Patent App. 14/074,279, November 2013
[31] Gaspar, L., Leurent, G., Standaert, F.: Hardware implementation and side-channel analysis of Lapin. In: CT-RSA (2014) · Zbl 1337.94096 · doi:10.1007/978-3-319-04852-9_11
[32] Goldreich, O., Krawczyk, H., Luby, M.: On the existence of pseudorandom generators. SIAM J. Comput. 22(6), 1163–1175 (1993) · Zbl 0795.94011 · doi:10.1137/0222069
[33] Grosso, V., Standaert, F., Faust, S.: Masking vs. multiparty computation: how large is the gap for AES? J. Crypt. Eng. 4(1), 47–57 (2014) · doi:10.1007/s13389-014-0073-y
[34] Güneysu, T., Moradi, A.: Generic side-channel countermeasures for reconfigurable devices. In: Preneel, B., Takagi, T. (eds.) CHES 2011. LNCS, vol. 6917, pp. 33–48. Springer, Heidelberg (2011) · Zbl 1401.94158 · doi:10.1007/978-3-642-23951-9_3
[35] Guo, Q., Johansson, T.: A new birthday-type algorithm for attacking the fresh re-keying countermeasure. Cryptology ePrint Archive, Report 2016/225 (2016)
[36] Heyse, S., Kiltz, E., Lyubashevsky, V., Paar, C., Pietrzak, K.: Lapin: an efficient authentication protocol based on Ring-LPN. In: Canteaut, A. (ed.) FSE 2012. LNCS, vol. 7549, pp. 346–365. Springer, Heidelberg (2012) · Zbl 1282.94078 · doi:10.1007/978-3-642-34047-5_20
[37] Ishai, Y., Sahai, A., Wagner, D.: Private circuits: securing hardware against probing attacks. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 463–481. Springer, Heidelberg (2003) · Zbl 1122.94378 · doi:10.1007/978-3-540-45146-4_27
[38] Kiltz, E., Pietrzak, K.: Leakage resilient ElGamal encryption. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 595–612. Springer, Heidelberg (2010) · Zbl 1290.94103 · doi:10.1007/978-3-642-17373-8_34
[39] Kirchner, P., Fouque, P.: An improved BKW algorithm for LWE with applications to cryptography and lattices. In: CRYPTO (2015) · Zbl 1336.94058 · doi:10.1007/978-3-662-47989-6_3
[40] Liskov, M., Rivest, R.L., Wagner, D.: Tweakable block ciphers. J. Crypt. 24(3), 588–613 (2011) · Zbl 1258.94040 · doi:10.1007/s00145-010-9073-y
[41] Mangard, S., Oswald, E., Popp, T.: Power Analysis Attacks - Revealing the Secrets of Smart Cards. Springer, Heidelberg (2007) · Zbl 1131.68449
[42] Mangard, S., Popp, T., Gammel, B.M.: Side-channel leakage of masked CMOS gates. In: Menezes, A. (ed.) CT-RSA 2005. LNCS, vol. 3376, pp. 351–365. Springer, Heidelberg (2005) · Zbl 1079.94561 · doi:10.1007/978-3-540-30574-3_24
[43] Mangard, S., Pramstaller, N., Oswald, E.: Successfully attacking masked AES hardware implementations. In: CHES (2005) · Zbl 05317678 · doi:10.1007/11545262_12
[44] Martin, D.P., Oswald, E., Stam, M., Wójcik, M.: A leakage resilient MAC. In: Groth, J. (ed.) IMACC 2015. LNCS, vol. 9496, pp. 295–310. Springer, Heidelberg (2015). doi: 10.1007/978-3-319-27239-9_18 · Zbl 1376.94039 · doi:10.1007/978-3-319-27239-9_18
[45] Medwed, M., Petit, C., Regazzoni, F., Renauld, M., Standaert, F.-X.: Fresh re-keying II: securing multiple parties against side-channel and fault attacks. In: Prouff, E. (ed.) CARDIS 2011. LNCS, vol. 7079, pp. 115–132. Springer, Heidelberg (2011) · doi:10.1007/978-3-642-27257-8_8
[46] Medwed, M., Standaert, F., Großschädl, J., Regazzoni, F.: Fresh rekeying: security against side-channel and fault attacks for low-cost devices. In: AFRICACRYPT (2010) · Zbl 1284.94095
[47] Medwed, M., Standaert, F.-X., Joux, A.: Towards super-exponential side-channel security with efficient leakage-resilient PRFs. In: Prouff, E., Schaumont, P. (eds.) CHES 2012. LNCS, vol. 7428, pp. 193–212. Springer, Heidelberg (2012) · Zbl 1366.94515 · doi:10.1007/978-3-642-33027-8_12
[48] Micciancio, D., Peikert, C.: Hardness of SIS and LWE with small parameters. In: CRYPTO (2013) · Zbl 1310.94161 · doi:10.1007/978-3-642-40041-4_2
[49] Moradi, A., Poschmann, A., Ling, S., Paar, C., Wang, H.: Pushing the limits: a very compact and a threshold implementation of AES. In: EUROCRYPT (2011) · Zbl 1281.94044
[50] Nikova, S., Rijmen, V., Schläffer, M.: Secure hardware implementation of nonlinear functions in the presence of glitches. J. Crypt. 24(2), 292–321 (2011) · Zbl 1239.94060 · doi:10.1007/s00145-010-9085-7
[51] Pereira, O., Standaert, F., Vivek, S.: Leakage-resilient authentication and encryption from symmetric cryptographic primitives. In: ACM CCS (2015) · doi:10.1145/2810103.2813626
[52] Petit, C., Standaert, F., Pereira, O., Malkin, T., Yung, M.: A block cipher based pseudo random number generator secure against side-channel key recovery. In: ASIACCS (2008) · doi:10.1145/1368310.1368322
[53] Prouand, E., Rivain, M.: Masking against side-channel attacks: a formal security proof. In: EUROCRYPT (2013) · Zbl 1306.94087
[54] Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: ACM STOC (2005) · Zbl 1192.94106 · doi:10.1145/1060590.1060603
[55] Roche, T., Prou, E.: Higher-order glitch free implementation of the AES using secure multi-party computation protocols - extended version. J. Crypt. Eng. 2(2), 111–127 (2012) · doi:10.1007/s13389-012-0033-3
[56] Schindler, W., Lemke, K., Paar, C.: A stochastic model for dierential side channel cryptanalysis. In: CHES (2005)
[57] Standaert, F., Pereira, O., Yu, Y., Quisquater, J., Yung, M., Oswald, E.: Leakage resilient cryptography in practice. In: Towards Hardware-Intrinsic Security - Foundations and Practice (2010) · doi:10.1007/978-3-642-14452-3_5
[58] Yu, Y., Standaert, F.: Practical leakage-resilient pseudorandom objects with minimum public randomness. In: CT-RSA 2013 (2013) · Zbl 1312.94106 · doi:10.1007/978-3-642-36095-4_15
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.