Paper 2013/303

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

Shivam Bhasin, 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$.

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.

Metadata
Available format(s)
PDF
Category
Implementation
Publication info
Published elsewhere. Minor revision. Radon Series on Computational and Applied Mathematics 16
DOI
10.1515/9783110317916.41
Keywords
Side-channel analysismaskinghardware
Contact author(s)
sylvain guilley @ telecom-paristech fr
History
2015-07-03: last of 5 revisions
2013-05-25: received
See all versions
Short URL
https://ia.cr/2013/303
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/303,
      author = {Shivam Bhasin and Claude Carlet and Sylvain Guilley},
      title = {Theory of masking with codewords in hardware: low-weight $d$th-order correlation-immune Boolean functions},
      howpublished = {Cryptology ePrint Archive, Paper 2013/303},
      year = {2013},
      doi = {10.1515/9783110317916.41},
      note = {\url{https://eprint.iacr.org/2013/303}},
      url = {https://eprint.iacr.org/2013/303}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.