Low-Latency Boolean Functions and Bijective S-boxes
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 latency complexity, to mathematically measure the latency of Boolean functions. We present efficient algorithms to find all Boolean functions with low-latency...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Ruhr-Universität Bochum
2022-09-01
|
| Series: | IACR Transactions on Symmetric Cryptology |
| Subjects: | |
| Online Access: | https://tosc.iacr.org/index.php/ToSC/article/view/9862 |
| _version_ | 1811208867334324224 |
|---|---|
| author | Shahram Rasoolzadeh |
| author_facet | Shahram Rasoolzadeh |
| author_sort | Shahram Rasoolzadeh |
| collection | DOAJ |
| description |
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 latency complexity, 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.
As a result, for latency complexity 3, we present n-bit S-boxes of 3 ≤ n ≤ 8 with linearity 2n−1 and uniformity 2n−2 (except for 5-bit S-boxes for whose the minimum achievable uniformity is 6). Besides, for latency complexity 4, we present several n-bit S-boxes of 5 ≤ n < 8 with linearity 2n−2 and uniformity 2n−4.
|
| first_indexed | 2024-04-12T04:29:08Z |
| format | Article |
| id | doaj.art-7ae9bfa4f7564f68a0fba9e5418a1162 |
| institution | Directory Open Access Journal |
| issn | 2519-173X |
| language | English |
| last_indexed | 2024-04-12T04:29:08Z |
| publishDate | 2022-09-01 |
| publisher | Ruhr-Universität Bochum |
| record_format | Article |
| series | IACR Transactions on Symmetric Cryptology |
| spelling | doaj.art-7ae9bfa4f7564f68a0fba9e5418a11622022-12-22T03:47:59ZengRuhr-Universität BochumIACR Transactions on Symmetric Cryptology2519-173X2022-09-012022310.46586/tosc.v2022.i3.403-447Low-Latency Boolean Functions and Bijective S-boxesShahram Rasoolzadeh0Radboud University, Nijmegen, The Netherlands 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 latency complexity, 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. As a result, for latency complexity 3, we present n-bit S-boxes of 3 ≤ n ≤ 8 with linearity 2n−1 and uniformity 2n−2 (except for 5-bit S-boxes for whose the minimum achievable uniformity is 6). Besides, for latency complexity 4, we present several n-bit S-boxes of 5 ≤ n < 8 with linearity 2n−2 and uniformity 2n−4. https://tosc.iacr.org/index.php/ToSC/article/view/9862S-boxlow-latencygate depth complexity |
| spellingShingle | Shahram Rasoolzadeh Low-Latency Boolean Functions and Bijective S-boxes IACR Transactions on Symmetric Cryptology S-box low-latency gate depth complexity |
| title | Low-Latency Boolean Functions and Bijective S-boxes |
| title_full | Low-Latency Boolean Functions and Bijective S-boxes |
| title_fullStr | Low-Latency Boolean Functions and Bijective S-boxes |
| title_full_unstemmed | Low-Latency Boolean Functions and Bijective S-boxes |
| title_short | Low-Latency Boolean Functions and Bijective S-boxes |
| title_sort | low latency boolean functions and bijective s boxes |
| topic | S-box low-latency gate depth complexity |
| url | https://tosc.iacr.org/index.php/ToSC/article/view/9862 |
| work_keys_str_mv | AT shahramrasoolzadeh lowlatencybooleanfunctionsandbijectivesboxes |