Marie Bolzer
Université de Lorraine, CNRS, Loria, Inria, Nancy, France

Sébastien Duval
Université de Lorraine, CNRS, Loria, Inria, Nancy, France

Marine Minier
Université de Lorraine, CNRS, Loria, Inria, Nancy, France

Keywords: S-box, lightweight cryptography, masking, multiplicative complexity, multiplicative depth, bitslicing

Abstract

We propose a new ad hoc automatic tool to look for lightweight implementations of non-linear functions on up to 7 variables. This tool is mainly aimed at finding implementations of arbitrary cryptographic S-boxes, with the goal of enabling lightweight protected implementations (such as masking), hence we focus on two metrics that we try to minimise: multiplicative depth and multiplicative complexity. We introduce an algorithm based on successive divisions, which we instantiate into a tool focused on binary operations AND and XOR. In a sense, this is a dual approach to a recent work which used an ad hoc algorithm based on multiplications, which was limited to degree-2 functions. Our algorithm removes this limitation, and our tool is efficient to find implementations of cryptographic S-boxes up to degree 5 on 6 bits and degree 3 on 7 bits.