IACR News item: 09 June 2013
Arnab Roy, Srinivas Vivek
ePrint ReportIn 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.
Additional news items may be found on the IACR news page.