Cryptology ePrint Archive: Report 2016/831

Reducing the Number of Non-linear Multiplications in Masking Schemes

Jürgen Pulkus and Srinivas Vivek

Abstract: In recent years, methods to securely mask S-boxes against side-channel attacks by representing them as polynomials over finite binary fields have become quite efficient. A good cost model for this is to count how many non-linear multiplications are needed. In this work we improve on the current state-of-the-art generic method published by Coron-Roy-Vivek at CHES 2014 by working over slightly larger fields than strictly needed. This leads us, for example, to evaluate DES S-boxes with only 3 non-linear multiplications and, as a result, obtain \(25\%\) improvement in the running time for secure software implementations of DES when using three or more shares.

On the theoretical side, we prove a logarithmic upper bound on the number of non-linear multiplications required to evaluate any \(d\)-bit S-box, when ignoring the cost of working in unreasonably large fields. This upper bound is lower than the previous lower bounds proved under the assumption of working over the field \(\mathbb{F}_{2^d}\), and we show this bound to be sharp. We also achieve a way to evaluate the AES S-box using only 3 non-linear multiplications over \(\mathbb{F}_{2^{16}}\).

Category / Keywords: implementation / side-channel countermeasure, masking, probing security, block cipher, software implementation, polynomial evaluation

Original Publication (in the same form): IACR-CHES-2016

Date: received 27 Aug 2016

Contact author: Juergen Pulkus at gi-de com; sv venkatesh@bristol ac uk

Available format(s): PDF | BibTeX Citation

Note: This is the author accepted manuscript (AAM). The final published version (version of record) is available online via Springer at Please refer to any applicable terms of use of the publisher.

Version: 20160830:212630 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]