Towards Sound Fresh Re-keying with Hard (Physical) Learning Problems

详细信息    查看全文

• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：9815
• 期：1
• 页码：272-301
• 全文大小：702 KB
• 参考文献：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)CrossRef
  2.Albrecht, M.R., Player, R., Scott, S.: On the concrete hardness of learning with errors. J. Math. Cryptol. 9(3), 169–203 (2015)MathSciNet CrossRef MATH
  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)CrossRef
  4.Andrychowicz, M., Dziembowski, S., Faust, S.: Circuit compilers with \(O(1= \text{log}(n))\) leakage rate. In: EUROCRYPT (2016)
  5.Arora, S., Ge, R.: New algorithms for learning in presence of errors. In: ICALP (2011)
  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)
  7.Banerjee, A., Peikert, C., Rosen, A.: Pseudorandom functions, lattices. In: EUROCRYPT (2012)
  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)
  9.Belaïd, S., Fouque, P., Gérard, B.: Side-channel analysis of multiplications in GF(2128) - application to AES-GCM. In: ASIACRYPT (2014)
  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)CrossRef MATH
  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)CrossRef
  12.Bilgin, B., Gierlichs, B., Nikova, S., Nikov, V., Rijmen, V.: A more efficient AES threshold implementation. In: AFRICACRYPT (2014)
  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)
  14.Blum, A., Kalai, A., Wasserman, H.: Noise-tolerant learning, the parity problem, and the statistical query model. In: ACM STOC (2000)
  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)
  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 CrossRef
  17.Bogos, S., Tramér, F., Vaudenay, S.: On solving LPN using BKW and variants. In: IACR Cryptology ePrint Archive (2015)
  18.Boneh, D., Lewi, K., Montgomery, H.W., Raghunathan, A.: Key homomorphic PRFs, their applications. In: CRYPTO (2013)
  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)
  20.Chari, S., Rao, J.R., Rohatgi, P.: Template attacks. In: CHES (2002)
  21.Chari, S., Jutla, C.S., Rao, J.R., Rohatgi, P.: Towards sound approaches to counteract power-analysis attacks. In: CRYPTO (1999)
  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)CrossRef
  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)
  25.Döttling, N., Müller-Quade, J.: Lossy codes, a new variant of the learning-with-errors problem. In: EUROCRYPT (2013)
  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)CrossRef
  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)
  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)CrossRef
  29.Dziembowski, S., Pietrzak, K.: Leakage-resilient cryptography. In: IEEE FOCS (2008)
  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)
  32.Goldreich, O., Krawczyk, H., Luby, M.: On the existence of pseudorandom generators. SIAM J. Comput. 22(6), 1163–1175 (1993)MathSciNet CrossRef MATH
  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)CrossRef
  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)CrossRef
  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)CrossRef
  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)CrossRef
  38.Kiltz, E., Pietrzak, K.: Leakage resilient ElGamal encryption. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 595–612. Springer, Heidelberg (2010)CrossRef
  39.Kirchner, P., Fouque, P.: An improved BKW algorithm for LWE with applications to cryptography and lattices. In: CRYPTO (2015)
  40.Liskov, M., Rivest, R.L., Wagner, D.: Tweakable block ciphers. J. Crypt. 24(3), 588–613 (2011)MathSciNet CrossRef MATH
  41.Mangard, S., Oswald, E., Popp, T.: Power Analysis Attacks - Revealing the Secrets of Smart Cards. Springer, Heidelberg (2007)MATH
  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)CrossRef
  43.Mangard, S., Pramstaller, N., Oswald, E.: Successfully attacking masked AES hardware implementations. In: CHES (2005)
  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 CrossRef
  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)CrossRef
  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)
  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)CrossRef
  48.Micciancio, D., Peikert, C.: Hardness of SIS and LWE with small parameters. In: CRYPTO (2013)
  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)
  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)MathSciNet CrossRef MATH
  51.Pereira, O., Standaert, F., Vivek, S.: Leakage-resilient authentication and encryption from symmetric cryptographic primitives. In: ACM CCS (2015)
  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)
  53.Prouand, E., Rivain, M.: Masking against side-channel attacks: a formal security proof. In: EUROCRYPT (2013)
  54.Regev, O.: On lattices, learning with errors, random linear codes, and cryptography. In: ACM STOC (2005)
  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)CrossRef
  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)
  58.Yu, Y., Standaert, F.: Practical leakage-resilient pseudorandom objects with minimum public randomness. In: CT-RSA 2013 (2013)
  
• 作者单位：Stefan Dziembowski (15)
  Sebastian Faust (16)
  Gottfried Herold (16)
  Anthony Journault (17)
  Daniel Masny (16)
  François-Xavier Standaert (17)
  
  15. Institute of Informatics, University of Warsaw, Warsaw, Poland
  16. Fakultät für Mathematik, University of Bochum, Bochum, Germany
  17. ICTEAM – Crypto Group, Université catholique de Louvain, Louvain-la-Neuve, Belgium
  
• 丛书名：Advances in Cryptology ¨C CRYPTO 2016
• ISBN：978-3-662-53008-5
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：9815

文摘

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.