TY - JOUR
AU - Rasoolzadeh, Shahram
PY - 2022/09/09
Y2 - 2022/10/01
TI - Low-Latency Boolean Functions and Bijective S-boxes
JF - IACR Transactions on Symmetric Cryptology
JA - ToSC
VL - 2022
IS - 3
SE - Articles
DO - 10.46586/tosc.v2022.i3.403-447
UR - https://tosc.iacr.org/index.php/ToSC/article/view/9862
SP - 403-447
AB - <p>In this paper, we study the gate depth complexity of (vectorial) Boolean functions in the basis of {NAND, NOR, INV} as a new metric, called <em>latency complexity</em>, to mathematically measure the latency of Boolean functions. We present efficient algorithms to find all Boolean functions with low-latency complexity, or to determine the latency complexity of the (vectorial) Boolean functions, and to find all the circuits with the minimum latency complexity for a given Boolean function. Then, we present another algorithm to build bijective S-boxes with low-latency complexity which with respect to the computation cost, this algorithm overcomes the previous methods of building S-boxes.<br>As a result, for latency complexity 3, we present n-bit S-boxes of 3 ≤<em> n</em> ≤ 8 with linearity 2<sup><em>n</em>−1</sup> and uniformity 2<sup><em>n</em>−2</sup> (except for 5-bit S-boxes for whose the minimum achievable uniformity is 6). Besides, for latency complexity 4, we present several <em>n</em>-bit S-boxes of 5 ≤ <em>n</em> < 8 with linearity 2<sup><em>n</em>−2</sup> and uniformity 2<sup><em>n</em>−4</sup>.</p>
ER -