Paper 2021/369

A Note on Algebraic Decomposition Method for Masked Implementation

Shoichi Hirose


Side-channel attacks are a serious problem in the implementation of cryptosystems. Masking is an effective countermeasure to this problem and it has been actively studied for implementations of block ciphers. An obstacle to efficient masked implementation is the complexity of an evaluation of multiplication, which is quadratic in the order of masking. A natural approach to this problem is to explore ways to reduce the number of multiplications required to compute an S-box. Algebraic decomposition is another interesting approach proposed by Carlet et al. in 2015, which gives a way to represent an S-box as composition of polynomials with low algebraic degrees. In this paper, for the algebraic decomposition, we propose to use a special type of low-algebraic-degree polynomials, which we call generalized multiplication (GM) polynomials. The masking scheme for multiplication can be applied to GM polynomials, which is more efficient than the masking scheme for general low-algebraic-degree polynomials. Our performance evaluation based on some experimental results shows the effectiveness of masked implementation using the proposed decomposition compared to masked implementation using the decomposition of Carlet et al.

Note: An error in the decomposition of SKINNY 4-Bit S-box (Sect. 3.3) is fixed.

Available format(s)
Secret-key cryptography
Publication info
Published elsewhere. MAJOR revision.EAI AC3 2021
Algebraic decompositionBoolean functionMaskingS-box
Contact author(s)
hrs_shch @ u-fukui ac jp
2021-12-21: last of 2 revisions
2021-03-22: received
See all versions
Short URL
Creative Commons Attribution


      author = {Shoichi Hirose},
      title = {A Note on Algebraic Decomposition Method for Masked Implementation},
      howpublished = {Cryptology ePrint Archive, Paper 2021/369},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.