Top

Cryptography and Communications

Published in:

15-07-2021

Monomial evaluation of polynomial functions protected by threshold implementations—with an illustration on `AES`—

- Extended version -

Authors: Simon Landry, Yanis Linge, Emmanuel Prouff

Published in: Cryptography and Communications | Issue 4/2021

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

In the context of side-channel countermeasures, threshold implementations (TI) have been introduced in 2006 by Nikova et al. to defeat attacks which exploit hardware effects called glitches. On several aspects, TI may be seen as an extension of another classical side-channel countermeasure, called masking, which is essentially based on the sharing of any internal state of the processing into independent parts (also called shares). To achieve side-channel security, a TI scheme operates on shared data and comes with additional properties to get robustness to glitches. When specifying such a scheme to secure a cryptographic implementation, as e.g. the AES block cipher, the challenging part is to minimise both the number of steps (or cycles) and the consumption of randomness. In this paper, we combine the changing of the guards technique published by Daemen at CHES 2017 (which reduces the need for fresh randomness) with the work of Genelle et al. at CHES 2011 (which combines additive masking and multiplicative one) to propose a new TI which does not consume fresh randomness and which is efficient (in terms of cycles) for classical block ciphers. As an illustration, we develop our proposal for the AES, and more specifically its SBox implemented thanks to a finite field exponentiation. In this particular context, we argue that our proposal is a valuable alternative to the state of the art solutions. More generally, it has the advantage of being easily applicable to the evaluation of any polynomial function, which was usually not the case of previous solutions.

previous article Categorizing all linear codes of IPM over

next article How to fool a black box machine learning based side-channel security evaluation

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

To gain in speed execution, the implicit assumption is that the latter power functions applied to a variable x ∈ GF(2ⁿ) are accessible in a lookup table.

The definition of uniformity for threshold implementations was originally given by Bilgin et al. [3] but we use in this paper the version of Carlet [7] which seems to us easier to interpret.

Remark: by taking x = x^q and α = α^q, x_δ is similar than x₃ in Section 3.2

Remark: by taking x = x^q and α = α^q, \(\mathbf {x}_{x^{q}}\) is similar than x₂ in Section 3.2.

As an observation, if the Dirac function δ(x) is computed with TI multiplications (see in Section 4.2), the scheme can also be implemented in eight cycles (4 for x²⁵⁴ and 4 for the TI Dirac function).

see the product specifications here http://www.tul.com.tw/ProductsPYNQ-Z2.html

Akkar, M.-L., Giraud, C.: An implementation of DES and aes, secure against some attacks. In: Koç, Ç.K., Naccache, D., Paar, C. (eds.) Cryptographic Hardware and Embedded Systems—CHES 2001, Third International Workshop, Paris, France, May 14–16, 2001, Proceedings, volume 2162 of Lecture Notes in Computer Science, pp 309–318. Springer (2001)

Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In: Simon, J. (ed.) Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2–4, 1988, Chicago, Illinois, USA, pp 1–10. ACM (1988)

Bilgin, B., Gierlichs, B., Nikova, S., Nikov, V., Rijmen, V.: Higher-order threshold implementations. In: Sarkar, P., Iwata, T. (eds.) Advances in Cryptology—ASIACRYPT 2014—20th International Conference on the Theory and Application of Cryptology and Information Security, Kaoshiung, Taiwan, R.O.C., December 7–11, 2014, Proceedings, Part II, volume 8874 of Lecture Notes in Computer Science, pp 326–343. Springer (2014)

Bilgin, B., Gierlichs, B., Nikova, S., Nikov, V., Rijmen, V.: Trade-offs for threshold implementations illustrated on AES. IEEE Trans. CAD Integr. Circ. Syst. 34(7), 1188–1200 (2015)CrossRef

Blömer, J., Guajardo, J., Krummel, V.: Provably secure masking of AES. In: Handschuh, H., Hasan, M. A. (eds.) Selected Areas in Cryptography, 11th International Workshop, SAC 2004, Waterloo, Canada, August 9-10, 2004, Revised Selected Papers, volume 3357 of Lecture Notes in Computer Science, pp 69–83. Springer (2004)

Brier, E., Clavier, C., Olivier, F.: Correlation power analysis with a leakage model. In: Joye, M., Quisquater, J.-J. (eds.) Cryptographic Hardware and Embedded Systems—CHES 2004: 6th International Workshop Cambridge, MA, USA, August 11–13, 2004. Proceedings, volume 3156 of Lecture Notes in Computer Science, pp 16–29. Springer (2004)

Carlet, C.: Boolean Functions for Cryptography and Coding Theory. Cambridge University Press, Cambridge (2021)MATH

Carlet, C., Prouff, E., Rivain, M., Roche, T.: Algebraic decomposition for probing security. IACR Cryptology ePrint Archive 2016:321 (2016)

Chari, S., Jutla, C.S., Rao, J.R., Rohatgi, P.: Towards sound approaches to counteract power-analysis attacks. In: Wiener [37], pp 398–412 (1999)

10.

Coron, J.-S., Roy, A., Vivek, S.: Fast evaluation of polynomials over binary finite fields and application to side-channel countermeasures. J. Cryptogr. Eng. 5(2), 73–83 (2015)CrossRef

11.

Daemen, J.: Changing of the guards: a simple and efficient method for achieving uniformity in threshold sharing. In: Fischer, W., Homma, N. (eds.) Cryptographic Hardware and Embedded Systems—CHES 2017—19th International Conference, Taipei, Taiwan, September 25–28, 2017, Proceedings, volume 10529 of Lecture Notes in Computer Science, pp 137–153. Springer (2017)

12.

Daemen, J., Rijmen, V.: The Design of Rijndael: AES—The Advanced Encryption Standard. Springer, Berlin (2002)CrossRef

13.

Damgård, I., Keller, M.: Secure multiparty AES. In: Sion, R. (ed.) Financial Cryptography and Data Security, 14th International Conference, FC 2010, Tenerife, Canary Islands, Spain, January 25–28, 2010, Revised Selected Papers, volume 6052 of Lecture Notes in Computer Science, pp 367–374. Springer (2010)

14.

De Cnudde, T., Reparaz, O., Bilgin, B., Nikova, S., Nikov, V., Rijmen, V.: Masking AES with d + 1 shares in hardware. In: Bilgin, B., Nikova, S., Rijmen, V. (eds.) Proceedings of the ACM Workshop on Theory of Implementation Security, TIS@CCS 2016 Vienna, Austria, October, 2016, p 43. ACM (2016)

15.

Fumaroli, G., Mayer, E., Dubois, R.: First-order differential power analysis on the duplication method. In: Srinathan, K., Pandu Rangan, C., Yung, M. (eds.) Progress in Cryptology—INDOCRYPT 2007, 8th International Conference on Cryptology in India, Chennai, India, December 9–13, 2007, Proceedings, volume 4859 of Lecture Notes in Computer Science, pp 210–223. Springer (2007)

16.

Fumaroli, G., Martinelli, A., Prouff, E., Rivain, M.: Affine masking against higher-order side channel analysis. In: Biryukov, A., Gong, G., Stinson, D.R. (eds.) Selected Areas in Cryptography—17th International Workshop, SAC 2010, Waterloo, Ontario, Canada, August 12–13, 2010, Revised Selected Papers, volume 6544 of Lecture Notes in Computer Science, pp 262–280. Springer (2010)

17.

Genelle, L., Prouff, E., Quisquater, M.: Secure multiplicative masking of power functions. In: Nitaj and Pointcheval [30] (2009)

18.

Genelle, L., Prouff, E., Quisquater, M.: Montgomery’s trick and fast implementation of masked AES. In: Nitaj and Pointcheval [30], pp 153–169 (2010)

19.

Genelle, L., Prouff, E., Quisquater, M.: Thwarting higher-order side channel analysis with additive and multiplicative maskings. IACR Cryptology ePrint Archive 2011:425 (2011)

20.

Golic, J.D.J., Tymen, C.: Multiplicative masking and power analysis of AES. In: Kaliski, B.S. Jr., Koç, Ç.K., Paar, C. (eds.) Cryptographic Hardware and Embedded Systems—CHES 2002, 4th International Workshop, Redwood Shores, CA, USA, August 13–15, 2002, Revised Papers, volume 2523 of Lecture Notes in Computer Science, pp 198–212. Springer (2002)

21.

Goubin, L., Patarin, J.: DES and differential power analysis (the “duplication” method). In: Koç, Ç.K., Paar, C. (eds.) Cryptographic Hardware and Embedded Systems, First International Workshop, CHES’99, Worcester, MA, USA, August 12–13, 1999, Proceedings, volume 1717 of Lecture Notes in Computer Science, pp 158–172. Springer (1999)

22.

Groß, H., Mangard, S., Korak, T.: An efficient side-channel protected AES implementation with arbitrary protection order. In: Handschuh, H. (ed.) Topics in Cryptology—CT-RSA 2017—The Cryptographers’ Track at the RSA Conference 2017, San Francisco, CA, USA, February 14–17, 2017, Proceedings, volume 10159 of Lecture Notes in Computer Science, pp 95–112. Springer (2017)

23.

Ishai, Y., Sahai, A., Wagner, D.A.: Private circuits: securing hardware against probing attacks. In: D. Boneh (ed.) Advances in Cryptology—CRYPTO 2003, 23rd Annual International Cryptology Conference, Santa Barbara, California, USA, August 17–21, 2003, Proceedings, volume 2729 of Lecture Notes in Computer Science, pp 463–481. Springer (2003)

24.

Kocher, P.C., Jaffe, J., Jun, B.: Differential power analysis. In: Wiener [39], pp 388–397 (1999)

25.

Mangard, S., Popp, T., Gammel, B.M.: Side-channel leakage of masked CMOS gates. In: Menezes, A. (ed.) Topics in Cryptology—CT-RSA 2005, The Cryptographers’ Track at the RSA Conference 2005, San Francisco, CA, USA, February 14–18, 2005, Proceedings, volume 3376 of Lecture Notes in Computer Science, pp 351–365. Springer (2005)

26.

Mangard, S., Pramstaller, N., Oswald, E.: Successfully attacking masked AES hardware implementations. In: Rao and Sunar [31], pp 157–171 (2005)

27.

Micali, S., Reyzin, L.: Physically observable cryptography (extended abstract). In: Naor, M. (ed.) Theory of Cryptography, First Theory of Cryptography Conference, TCC 2004, Cambridge, MA, USA, February 19–21, 2004, Proceedings, volume 2951 of Lecture Notes in Computer Science, pp 278–296. Springer (2004)

28.

Moradi, A., Poschmann, A., Ling, S., Paar, C., Wang, H.: Pushing the limits: a very compact and a threshold implementation of AES. In: Paterson, K.G. (ed.) Advances in Cryptology—EUROCRYPT 2011—30th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Tallinn, Estonia, May 15–19, 2011. Proceedings, volume 6632 of Lecture Notes in Computer Science, pp 69–88. Springer (2011)

29.

Nikova, S., Rijmen, V., Schläffer, M.: Secure hardware implementation of nonlinear functions in the presence of glitches. J. Cryptol. 24(2), 292–321 (2011)MathSciNetCrossRef

30.

Rivain, M., Dottax, E., Prouff, E.: Block ciphers implementations provably secure against second order side channel analysis. In: Nyberg, K. (ed.) Fast Software Encryption, 15th International Workshop, FSE 2008, Lausanne, Switzerland, February 10–13, 2008, Revised Selected Papers, volume 5086 of Lecture Notes in Computer Science, pp 127–143. Springer (2008)

31.

Rivain, M., Prouff, E.: Provably secure higher-order masking of AES. In: Mangard, S., Standaert, F.-X. (eds.) Cryptographic Hardware and Embedded Systems, CHES 2010, 12th International Workshop, Santa Barbara, CA, USA, August 17–20, 2010. Proceedings, volume 6225 of Lecture Notes in Computer Science, pp 413–427. Springer (2010)

32.

Rivest, R.L., Shamir, A., Tauman, Y.: How to leak a secret. In: Boyd, C. (ed.) Advances in Cryptology—ASIACRYPT 2001, 7th International Conference on the Theory and Application of Cryptology and Information Security, Gold Coast, Australia, December 9–13, 2001, Proceedings, volume 2248 of Lecture Notes in Computer Science, pp 552–565. Springer (2001)

33.

Roche, T., Prouff, E.: Higher-order glitch free implementation of the AES using secure multi-party computation protocols—extended version. J. Cryptogr. Eng. 2(2), 111–127 (2012)CrossRef

34.

Sugawara, T.: 3-share threshold implementation of AES s-box without fresh randomness. IACR Trans. Cryptogr. Hardw. Embed. Syst. 2019(1), 123–145 (2019)

35.

Suzuki, D., Saeki, M., Ichikawa, T.: DPA leakage models for CMOS logic circuits. In: Rao and Sunar [31], pp 366–382 (2005)

36.

Vadnala, P.K., Großschädl, J.: Algorithms for switching between boolean and arithmetic masking of second order. In: Gierlichs, B., Guilley, S., Mukhopadhyay, D. (eds.) Security, Privacy, and Applied Cryptography Engineering—Third International Conference, SPACE 2013, Kharagpur, India, October 19–23, 2013. Proceedings, volume 8204 of Lecture Notes in Computer Science, pp 95–110. Springer (2013)

37.

Yao, A.C.-C.: How to generate and exchange secrets (extended abstract). In: 27th Annual Symposium on Foundations of Computer Science, Toronto, Canada, 27–29 October 1986, pp 162–167. IEEE Computer Society (1986)

Title: Monomial evaluation of polynomial functions protected by threshold implementations—with an illustration on AES—
- Extended version -
Authors: Simon Landry
Yanis Linge
Emmanuel Prouff
Publication date: 15-07-2021
Publisher: Springer US
Published in: Cryptography and Communications / Issue 4/2021
Print ISSN: 1936-2447
Electronic ISSN: 1936-2455
DOI: https://doi.org/10.1007/s12095-021-00497-9

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 4/2021

Hashing to elliptic curves of j-invariant 1728

How to fool a black box machine learning based side-channel security evaluation

Special issue from mathematics to embedded devices

A stealthy Hardware Trojan based on a Statistical Fault Attack

Optimization of the scalar complexity of Chudnovsky2 multiplication algorithms in finite fields

On the privacy of a code-based single-server computational PIR scheme

Premium Partner