An algorithm for generating cryptographically stable S-box optimized for programmable logic integrated circuits

Cryptographic primitives implemented on Field-Programmable Gate Array (FPGA) have a number of advantages over their software counterparts; they are more efficient in terms of performance and energy consumption. At the same time, for implementation on FPGAs, it is important to have a compact representation of cryptographic primitive elements such as substitution tables (S-boxes). This paper presents a cryptographically strong S-box that is compact in its implementation on FPGAs. Based on the algorithm for generating bent functions using wavelet transform, an algorithm for constructing S-boxes has been developed. The nonlinearity, differential uniformity, avalanche effect, and Bit Independence Criterion (BIC) of the S-boxes generated by the developed algorithm are calculated. Diagrams have been constructed showing the distribution of S-boxes by nonlinearity and differential uniformity values for different values of the algorithm input data. A comparison was made of the cryptographic properties of the generated S-boxes and the S-boxes used in the American Advanced Encryption Standard symmetric encryption standard and the Russian Kuznechik cipher. The avalanche effect of the Streebog hash function was analyzed when using its S-box and the S-box generated by the developed algorithm, and a comparison of FPGA resource utilization was performed. The best results in terms of nonlinearity, differential uniformity, avalanche effect, and BIC are achieved by S-boxes consisting of bent functions that have no terms higher than degree two (quadratic bent functions) in algebraic normal form. In terms of cryptographic properties, the S-boxes generated by the developed algorithm are superior to or not inferior to existing ones, but they are not bijective, which narrows their field of application. The avalanche effect of the hash function with its original S-box and the S-box generated by the developed algorithm do not differ. Analysis of the results of the synthesis of hash function implementations showed that the use of the developed S-box allows saving about 1000 Look Up Tables on the FPGA. The S-boxes presented in this work are not inferior to existing ones in terms of cryptographic properties, or surpass them. The developed S-boxes are more compact than existing ones in hardware implementation on FPGAs, but they are not bijective, which makes their use most appropriate and natural in irreversible cryptographic primitives implemented on resource-limited embedded systems.

1. Matsui M. Linear cryptanalysis method for DES cipher. Lecture Notes in Computer Science, 1994, vol. 765, pp. 386–397. doi: 10.1007/3-540-48285-7_33

2. Zyubina D.A., Tokareva N.N. Cryptographic properties of a simple S-box construction based on a Boolean function and a permutation. Applied Discrete Mathematics. Application, 2020, no. 13, pp. 41–43. doi: 10.17223/2226308x/13/13

3. Nitaj A., Susilo W., Tonien J. A New improved AES S-box with enhanced properties. Lecture Notes in Computer Science, 2020, vol. 12248, pp. 125–141. doi: 10.1007/978-3-030-55304-3_7

4. Cui J., Huang L., Zhong H., Chang C., Yang W. An improved AES S-box and its performance analysis. International Journal of Innovative Computing, Information and Control, 2011, vol. 7, no. 5 (a), pp. 2291–2302.

5. Zahid A.H., Arshad M.J. An innovative design of substitution-boxes using cubic polynomial mapping. Symmetry, 2019, vol. 11, no. 3, pp. 437. doi: 10.3390/sym11030437

6. Rothaus O. On “bent” functions. Journal of Combinatorial Theory, Series A, 1976, vol. 20, no. 3, pp. 300–305. doi: 10.1016/0097-3165(76)90024-8

7. Dillon J.F. A survey of bent functions. The NSA Technical Journal, 1972, special issue, pp. 191–215.

8. McFarland R.L. A family of difference sets in non-cyclic groups. Journal of Combinatorial Theory, Series A, 1973, vol. 15, no. 1, pp. 1–10. doi: 10.1016/0097-3165(73)90031-9

9. Carlet C. Boolean functions for cryptography and error-correcting codes. Boolean Models and Methods in Mathematics, Computer Science, and Engineering, 2007, pp. 257–398.

10. Biham E., Shamir A. Differential cryptanalysis of DES-like cryptosystems. Journal of Cryptology, 1991, vol. 4, no. 1, pp. 372. doi: 10.1007/bf00630563

11. Tokareva N.N. Nonlinear Boolean Functions: Bent Functions and their Generalizations. LAP LAMBERT Academic Publishing, 2011, 180 p. (in Russian)

12. Mar P.P., Latt K.M. New analysis methods on strict avalanche criterion of S-Boxes. International Journal of Mathematical, Computational, Physical, Electrical and Computer Engineering, 2008, vol. 2, no. 12, pp. 899–903.

13. Webster A.F., Tavares S.E. On the design of S-Boxes. Lecture Notes in Computer Science, 1985, vol. 218, pp. 523–534. doi: 10.1007/3-540-39799-X_41

14. Detombe J., Tavares S. Constructing large cryptographically strong S-boxes. Lecture Notes in Computer Science, 1993, vol. 718, pp. 165-181. doi: 10.1007/3-540-57220-1_60

15. Shibakin I.V., Levina A.B. Algorithm for generation of bent functions using wavelet transform. It Security (Russia), 2025, vol. 32, no. 4, pp. 106–121. (in Russian). doi: 10.26583/bit.2025.4.08

16. Demyanovich Yu.K., Khodakovsky V.A. Introduction to Wavelet Theory: A Teaching Medium. St. Petersburg, PGUPS Publ., 2007, 50 p. (in Russian)