Cryptology ePrint Archive: Report 2013/303

Theory of masking with codewords in hardware: low-weight $d$th-order correlation-immune Boolean functions

Shivam Bhasin and Claude Carlet and Sylvain Guilley

Abstract: In hardware, substitution boxes for block ciphers can be saved already masked in the implementation. The masks must be chosen under two constraints: their number is determined by the implementation area and their properties should allow to deny high-order zero-offset attacks of highest degree. First, we show that this problem translates into a known trade-off in Boolean functions, namely finding correlation-immune functions of lowest weight. For instance, this allows to prove that a byte-oriented block cipher such as AES can be protected with only $16$ mask values against zero-offset correlation power attacks of orders $1$, $2$ and $3$. Second, we study $d$th-order correlation-immune Boolean functions $\F_2^n \to \F_2$ of low-weight and exhibit such functions of minimal weight found by a satisfiability modulo theory tool. In particular, we give the minimal weight for $n \leq 10$. Some of these results were not known previously, such as the minimal weight for $(n=9, d=4)$ and $(n=10, d \in \{4,5,6\})$. These results set new bounds for the minimal number of lines of binary orthogonal arrays. In particular, we point out that the minimal weight $w_{n,d}$ of a $d$th-order correlation-immune function might not be increasing with the number of variables $n$.

Category / Keywords: implementation / Side-channel analysis, masking, hardware

Date: received 20 May 2013

Contact author: sylvain guilley at TELECOM-ParisTech fr

Available format(s): PDF | BibTeX Citation

Version: 20130525:134955 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]