Paper 2016/321

Algebraic Decomposition for Probing Security

Claude Carlet, Emmanuel Prouff, Matthieu Rivain, and Thomas Roche


The probing security model is very popular to prove the side-channel security of cryptographic implementations protected by masking. A common approach to secure nonlinear functions in this model is to represent them as polynomials over a binary field and to secure their nonlinear multiplications thanks to a method introduced by Ishai, Sahai and Wagner at Crypto 2003. Several schemes based on this approach have been published, leading to the recent proposal of Coron, Roy and Vivek which is currently the best known method when no particular assumption is made on the algebraic structure of the function. In the present paper, we revisit this idea by trading nonlinear multiplications for low-degree functions. Specifically, we introduce an algebraic decomposition approach in which a nonlinear function is represented as a sequence of functions with low algebraic degrees. We therefore focus on the probing-secure evaluation of such low-degree functions and we introduce three novel methods to tackle this particular issue. The paper concludes with a comparative analysis of the proposals, which shows that our algebraic decomposition method outperforms the method of Coron, Roy and Vivek in several realistic contexts.

Available format(s)
Publication info
A major revision of an IACR publication in CRYPTO 2015
Contact author(s)
matthieu rivain @ gmail com
2017-01-11: revised
2016-03-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Claude Carlet and Emmanuel Prouff and Matthieu Rivain and Thomas Roche},
      title = {Algebraic Decomposition for Probing Security},
      howpublished = {Cryptology ePrint Archive, Paper 2016/321},
      year = {2016},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.