In this paper we investigate optimal methods for exponentiation in $\mathbb{F}_{2^{n}}$ by studying a variant of addition chain, which we call \textit{cyclotomic-class addition chain}, or \textit{CC-addition chain}. Among several interesting properties, we prove lower bounds on min-length CC-addition chains. We define the notion of \GFn-polynomial chain, and use it to count the number of \textit{non-linear} multiplications required while evaluating polynomials over $\mathbb{F}_{2^{n}}$. We also give a lower bound on the length of such a chain for any polynomial. As a consequence, we show that a lower bound for the masking complexity of DES S-boxes is three, and that of PRESENT S-box is two. We disprove a claim previously made by Carlet et al. regarding min-length CC-addition chains. Finally, we give a polynomial evaluation method, which results into an improved masking scheme (compared to the technique of Carlet et al.) for DES S-boxes. As an illustration we apply this method to several other S-boxes and show significant improvement for them.
Category / Keywords: implementation / block cipher, S-box, masking complexity, addition chain, polynomial evaluation, side-channel attack Original Publication (with major differences): IACR-CHES-2013 Date: received 5 Jun 2013, last revised 23 Mar 2014 Contact author: Arnab Roy at uni lu; srinivasvivek venkatesh@uni lu Available format(s): PDF | BibTeX Citation Note: Full version Version: 20140323:150755 (All versions of this report) Short URL: ia.cr/2013/345 Discussion forum: Show discussion | Start new discussion