Cryptology ePrint Archive: Report 2016/321

Algebraic Decomposition for Probing Security

Claude Carlet and Emmanuel Prouff and Matthieu Rivain and Thomas Roche

Abstract: 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.

Category / Keywords:

Original Publication (with major differences): IACR-CRYPTO-2015

Date: received 22 Mar 2016, last revised 11 Jan 2017

Contact author: matthieu rivain at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20170111:190850 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]