Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Fast evaluation of polynomials over binary finite fields and application to side-channel countermeasures

  • CHES 2014
  • Published:
Journal of Cryptographic Engineering Aims and scope Submit manuscript

Abstract

We describe a new technique for evaluating polynomials over binary finite fields. This is useful in the context of anti-DPA countermeasures when an S-box is expressed as a polynomial over a binary finite field. For \(n\)-bit S-boxes, our new technique has heuristic complexity \({\fancyscript{O}}(2^{n/2}/\sqrt{n})\) instead of \({\fancyscript{O}}(2^{n/2})\) proven complexity for the Parity-Split method. We also prove a lower bound of \({{\varOmega }}(2^{n/2}/\sqrt{n})\) on the complexity of any method to evaluate \(n\)-bit S-boxes; this shows that our method is asymptotically optimal. Here, complexity refers to the number of non-linear multiplications required to evaluate the polynomial corresponding to an S-box. In practice, we can evaluate any 8-bit S-box in 10 non-linear multiplications instead of 16 in the Roy–Vivek paper from CHES 2013, and the DES S-boxes in 4 non-linear multiplications instead of 7. We also evaluate any 4-bit S-box in 2 non-linear multiplications instead of 3. Hence our method achieves optimal complexity for the PRESENT S-box.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

Notes

  1. Originally, it was claimed in [14] that the scheme is secure against \(d\)-th order attack with \(d+1\) shares. However, an attack of order \(d/2\) was shown in [8] against the scheme. The authors of [8] also showed a \(d\)-th order secure scheme with \(d+1\) shares for some subset of S-boxes.

References

  1. FIPS 46–3: Data Encryption Standard. National Institute of Standards and Technology. csrc.nist.gov (1993)

  2. Bogdanov, A., Knudsen, L.R., Leander, G., Paar, C., Poschmann, A., Robshaw, M.J.B., Seurin, Y., Vikkelsoe, C.: PRESENT: An ultra-lightweight block cipher. In: Paillier, P., Verbauwhede, I. (eds) CHES, Lecture Notes in Computer Science, vol. 4727, pp. 450–466. Springer, Berlin (2007)

  3. Brier, E., Clavier, C., Olivier, F.: Correlation power analysis with a leakage model. In: Joye, M., Quisquater, J.J. (eds.) CHES, Lecture Notes in Computer Science, vol. 3156, pp. 16–29. Springer, Berlin (2004)

  4. Carlet, C., Goubin, L., Prouff, E., Quisquater, M., Rivain, M.: Higher-order masking schemes for S-Boxes. In: Canteaut, A. (ed.) FSE, Lecture Notes in Computer Science, vol. 7549, pp. 366–384. Springer, Berlin (2012)

  5. Chari, S., Rao, J.R., Rohatgi, P.: Template attacks. In: Çetin Kaya Koç, B.S.K. Jr., Paar, C. (eds.) CHES, Lecture Notes in Computer Science, vol. 2523, pp. 13–28. Springer, Berlin (2002)

  6. Coron, J.S.: https://github.com/coron/htable/ (2013)

  7. Coron, J.S.: Higher order masking of look-up tables. In: Nguyen, P.Q., Oswald, E. (eds.) Advances in Cryptology—EUROCRYPT 2014–33rd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Copenhagen, Denmark, May 11–15, 2014. Proceedings, Lecture Notes in Computer Science, vol. 8441, pp. 441–458. Springer, Berlin (2014). doi:10.1007/978-3-642-55220-5_25

  8. Coron, J.S., Prouff, E., Rivain, M., Roche, T.: Higher-order side channel security and mask refreshing. In: FSE (2013) (to appear)

  9. Genkin, D., Shamir, A., Tromer, E.: RSA key extraction via low-bandwidth acoustic cryptanalysis. IACR Cryptol. 2013, 857 (2013). (ePrint Archive)

    Google Scholar 

  10. Ishai, Y., Sahai, A., Wagner, D.: Private circuits: Securing hardware against probing attacks. In: Boneh, D. (ed.) CRYPTO, Lecture Notes in Computer Science, vol. 2729, pp. 463–481. Springer, Berlin (2003)

  11. Kocher, P.C., Jaffe, J., Jun, B.: Differential power analysis. In: Wiener, M.J. (ed.) CRYPTO, Lecture Notes in Computer Science, vol. 1666, pp. 388–397. Springer, Berlin (1999)

  12. Messerges, T.S.: Using second-order power analysis to attack DPA resistant software. In: Çetin Kaya Koç, Paar, C. (eds.) CHES, Lecture Notes in Computer Science, vol. 1965, pp. 238–251. Springer, Berlin (2000)

  13. Paterson, M., Stockmeyer, L.J.: On the number of nonscalar multiplications necessary to evaluate polynomials. SIAM J. Comput. 2(1), 60–66 (1973)

    Article  MATH  MathSciNet  Google Scholar 

  14. Rivain, M., Prouff, E.: Provably secure higher-order masking of AES. In: Mangard, S., Standaert, F.X. (eds.) CHES, Lecture Notes in Computer Science, vol. 6225, pp. 413–427. Springer, Berlin (2010)

  15. Roy, A., Vivek, S.: Analysis and improvement of the generic higher-order masking scheme of FSE 2012. In: Bertoni, G., Coron, J.S. (eds.) CHES, Lecture Notes in Computer Science, vol. 8086, pp. 417–434. Springer, Berlin (2013)

  16. Shirai, T., Shibutani, K., Akishita, T., Moriai, S., Iwata, T.: The 128-bit blockcipher CLEFIA (extended abstract). In: Biryukov, A. (ed.) FSE, Lecture Notes in Computer Science, vol. 4593, pp. 181–195. Springer, Berlin (2007)

Download references

Acknowledgments

We would like to thank Matthieu Rivain for suggesting us the technique of tabulating linear polynomials described in Remark 3.

Author information

Author notes

  1. Arnab Roy

    Present address: Technical University of Denmark, Copenhagen, Denmark

Authors and Affiliations

  1. University of Luxembourg, FSTC, 6 rue Richard Coudenhove-Kalergi, 1359, Luxembourg, Luxembourg

    Jean-Sébastien Coron, Arnab Roy & Srinivas Vivek

Authors
  1. Jean-Sébastien Coron
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Arnab Roy
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Srinivas Vivek
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Srinivas Vivek.

Additional information

A preliminary version of this paper has appeared at CHES 2014.

Appendices

Appendix A: \({\mathbb {F}}_{2^{n}}\)-polynomial chain

Definition 1

([15], Definition 4) An \({\mathbb {F}}_{2^{n}}\)-polynomial chain \(S\) for a polynomial \(P(x)\in {\mathbb {F}}_{2^{n}}[x]\) is defined as:

$$\begin{aligned} \lambda _{-1}=1,\,\lambda _{0}=x,\ldots ,\,\lambda _{r}=P(x) \end{aligned}$$
(24)

where

$$\begin{aligned} \lambda _{i}=\left\{ \begin{array}{ll} \lambda _{j}+\lambda _{k} &{} \quad -1\le j,k<i,\\ \lambda _{j}\cdot \lambda _{k} &{} \quad -1\le j,k<i,\\ \alpha _{i}\odot \lambda _{j} &{} \quad -1\le j<i,\,\alpha _{i}\text { is a scalar},\\ \lambda _{j}^{2} &{} \quad -1\le j<i. \end{array}\right. \end{aligned}$$

Though \(\cdot \) and \(\odot \) both perform multiplication in \({\mathbb {F}}_{2^{n}}\), the operator “\(\odot \)” is reserved for the multiplication by a scalar. A step such as \(\lambda _{j}\cdot \lambda _{k}\) denotes a non-linear multiplication. Let the number of non-linear multiplications involved in a chain \(S\) be denoted as \(\mathcal {N}(S)\). Then, the non-linear complexity of \(P(x)\), denoted by \(\mathcal {M}(P(x))\), is defined as \(\mathcal {M}(P(x))=\underset{S}{min}\;\mathcal {N}(S)\).

Appendix B: Heuristics for choosing parameters \(t\) and \(L\)

Refer to the Table 6.

Table 6 Choosing parameters \(t\) and \(L\)
Full size table

Appendix C: Evaluation polynomials for DES S-boxes

In Table 7, we give an example of basis polynomials \(q_1(x)\), \(q_2(x)\) for DES and Table 8 shows the solution polynomials \(p_i(x)\) corresponding to the system of linear equations for the first DES S-box \(S_1\).

Table 7 Basis polynomials \(q_1, q_2\) obtained from \(\fancyscript{P}(x^{L})\), for DES
Full size table
Table 8 Solution to the system of linear equations for DES S-box (\(S_1\)). The irreducible polynomial is \(a^6 + a + 1\) over \({\mathbb F}_2\)
Full size table

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Coron, JS., Roy, A. & Vivek, S. Fast evaluation of polynomials over binary finite fields and application to side-channel countermeasures. J Cryptogr Eng 5, 73–83 (2015). https://doi.org/10.1007/s13389-015-0099-9

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s13389-015-0099-9

Keywords

Search

Navigation