Marie Bolzer, Sébastien Duval, Marine Minier

A Tool for Lightweight (AND, XOR) Implementations of Large-Degree S-boxes

Introduction

A tool for lightweight (and, xor) implementations of large-degree s-boxes. Discover a new tool and algorithm for lightweight (AND, XOR) implementations of large-degree cryptographic S-boxes. Minimize multiplicative depth and complexity for secure systems.

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.

Review

This paper proposes a novel "ad hoc automatic tool" aimed at discovering lightweight implementations of non-linear functions, particularly cryptographic S-boxes, with up to 7 variables. The explicit goal is to enable more efficient protected implementations, such as masking, by focusing on the minimization of two critical metrics: multiplicative depth and multiplicative complexity, utilizing solely AND and XOR binary operations. This addresses a significant need in the hardware implementation of cryptography, where optimizing these metrics directly impacts resistance to side-channel attacks and overall hardware resource consumption. A key strength highlighted in the abstract is the introduction of an algorithm based on successive divisions, which is presented as a dual approach to prior work that was limited to degree-2 functions using multiplications. This new methodology effectively removes that limitation, allowing the tool to handle higher-degree S-boxes. The authors claim efficiency, with successful implementations found for S-boxes up to degree 5 on 6 bits and degree 3 on 7 bits. This capability for higher-degree functions is a considerable advancement and could prove highly beneficial for generating optimized hardware for a wider range of modern cryptographic primitives. While the abstract promises a valuable contribution, a reviewer would look for deeper insights in the full paper. The term "ad hoc" suggests a highly specialized tool, and a comparison with more generic logic synthesis or S-box decomposition tools would be important to contextualize its unique advantages and limitations. Furthermore, while "large-degree" is used in the title, the specific limits of degree 5 on 6 bits and degree 3 on 7 bits, while improved, still define a particular scope. A detailed discussion on the implications of these bounds for *arbitrary* cryptographic S-boxes, along with comprehensive benchmark results and analysis of the trade-offs between the optimized metrics and other implementation costs (e.g., area, delay), would solidify the paper's impact.

Full Text

Comments

You need to be logged in to post a comment.