**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

**Original Publication**** (with minor differences): **Radon Series on Computational and Applied Mathematics 16
**DOI: **10.1515/9783110317916.41

**Date: **received 20 May 2013, last revised 3 Jul 2015

**Contact author: **sylvain guilley at telecom-paristech fr

**Available format(s): **PDF | BibTeX Citation

**Note: **The minimal weight of 6-th order correlation immune Boolean functions with 10 variables was already known.
The authors thank Yuriy Tarannikov for this information.

**Version: **20150703:121506 (All versions of this report)

**Short URL: **ia.cr/2013/303

[ Cryptology ePrint archive ]