A New Tool to Find Lightweight (And, Xor) Implementations of Quadratic Vectorial Boolean Functions up to Dimension 9
- 4 September 2025
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Circuits and Systems I: Regular Papers
- Vol. 73 (1) , 478-491
Abstract
The problem of finding a minimal circuit to implement a given function is one of the oldest in electronics. It is known to be NP-hard. Still, many tools exist to find sub-optimal circuits to implement a function. In electronics, such tools are known as synthesisers. However, these synthesisers aim to implement very large functions (a whole electronic chip). In cryptography, the focus is on small functions, hence the necessity for new dedicated tools for small functions. Several tools exist to implement small functions. They differ by their algorithmic approach (some are based on Depth-First-Search as introduced by Ullrich in 2011, some are based on SAT-solvers like the tool desgined by Stoffelen in 2016, some non-generic tools use subfield decomposition) and by their optimisation criteria (some optimise for circuit size, others for circuit depth, and some for side-channel-protected implementations). However, these tools are limited to functions operating on less than 5 bits, sometimes 6 bits for quadratic functions, or to very simple functions. The limitation lies in a high computing time. We propose a new tool (The tool is provided alongside the IEEE article with CodeOcean and at https://github.com/seduval/implem-quad-sbox) to implement quadratic functions up to 9 bits within AND-depth 1, minimising the number of AND gates. This tool is more time-efficient than previous ones, allowing to explore larger implementations than others on 6 bits or less and allows to reach larger sizes, up to 9 bits.Keywords
All Related Versions
Funding Information
- French National Agency of Research (ANR-22-CE39-0015)
This publication has 28 references indexed in Scilit:
- Computing the Distribution of Differentials over the Non-linear Mapping $\chi $2022
- Very High Order Masking: Efficient Implementation and Security Evaluation2017
- How Fast Can Higher-Order Masking Be in Software?2017
- PRESENT: An Ultra-Lightweight Block Cipher2007
- Physically Observable Cryptography2004
- A Toolbox for Cryptanalysis: Linear and Affine Equivalence Algorithms2003
- Private Circuits: Securing Hardware against Probing Attacks2003
- The Wide Trail Design Strategy2001
- Towards Sound Approaches to Counteract Power-Analysis Attacks1999
- DES and Differential Power Analysis The “Duplication” Method1999