DOI: https://doi.org/10.15588/1607-3274-2019-4-19

THE INVERSION METHOD OF FOUR-BIT BOOLEAN SAC CRYPTOTRANSFORMS

I. M. Fedotova-Piven, V. M. Rudnytskyi, O. B. Piven, T. V. Myroniuk

Abstract


Context. Nonlinear systems of Boolean functions play a prominent role in the protection of cryptosystems. The creation and use
of new four-bit cryptographic transformations with nonlinear Boolean functions that have the property of strict avalanche criterion is
an actual task for increasing the reliability of information protection systems.
Objective. The goal of the work is creating a method for obtaining inverse four-bit cryptographic transformations with the strict
avalanche criterion property, which contain balanced Boolean functions only with the operations of inversion and addition modulo
two.
Method. A method is proposed for obtaining inverse four-bit cryptographic transformations with the strict avalanche criterion
property, each of which contains balanced Boolean functions only with the operations of inversion and addition modulo two. The
method simplifies the process of finding inverse cryptographic transformations by creating a class of thirty balanced basic Boolean
functions with the required predefined limitations and properties and for finding, within this class, the basic Boolean functions that
make up the inverse cryptographic transformation.
Results. The effectiveness of the method is shown for obtaining two inverse four-bit cryptographic transformations with the
property of a strict avalanche criterion from two direct four-bit cryptographic transformations with the property of a strict avalanche
criterion.
Conclusions. For the first time, there was proposed a method for obtaining inverse four-bit cryptographic transformations with
the strict avalanche criterion property for balanced Boolean functions containing two logical operations (inversion and addition
modulo two) to ensure reliable information protection. This method is a method of selecting the already existing basic Boolean functions from a predetermined set of balanced basic Boolean functions for direct and inverse cryptographic transformations, whereas the existing methods of searching for inverse cryptographic transformation are methods for calculating each element of the Boolean functions for the inverse cryptographic transformation. The method can be extended to a larger even number of arguments of the balanced Boolean functions of cryptographic transformations to increase the cryptographic resilience.

Keywords


Boolean functions, inverse cryptographic transformation, balancedness, strict avalanche criterion, inversion, addition modulo 2.

Full Text:

PDF

References


Kemp S. Digital 2019. Essential insights into how people around the world use the Internet, mobile devices, social

media, and e-commerce. [Electronic resource]. Access mode: https: //wearesocial.com/global-digital-report-2019.

Lakhtaria K. I. Protecting Computer Network with Encryption Technique: A Study, Communications in Computer and

Information Science (UCMA 2011), 2011, Vol. 151, No. PART 2, pp. 381–390. DOI: 10.1007/978-3-642-

-7_47.

Debnath S., Linke N. M., Figgatt C. et al. Demonstration of a small programmable quantum computer with atomic

qubits, Nature, 2016, No. 536, pp. 63–66. DOI:10.1038/nature18648

Harrow A. W., Montanaro A. Quantum computational supremacy, Nature, 2017, Vol. 549, pp. 203–209. DOI:

1038/nature23458

Smart S. E., Schuster D. I., Mazziotti D. A. Experimental data from a quantum computer verifies the generalized Pauli

exclusion principle, Communications Physics, 2019, Vol. 2, No. 1, pp. 1–6. DOI: 10.1038/s42005-019-0110-3

Kolokotronis N., Limniotis K., Kalouptsidis N. Best Affine and Quadratic Approximations of Particular Classes of Boolean

Functions, IEEE transactions on information theory, 2009, Vol. 55, No. 11, pp. 5211–5222.

Menezes A. J., Van Oorschot P. C., Vanstone S. A. Handbook of Applied Cryptography. USA, CRC Press, Inc. Boca

Raton, 1996, 810 p.

Alzaidi A. A., Ahmad M., Doja M. N. at al. A New 1D Chaotic Map and β-Hill Climbing for Generating Substitution-

Boxes, IEEE Access, 2018, Vol. 6, pp. 55405–55418. DOI: 10.1109/ACCESS.2018.2871557.

Steinbach B. Problems and New Solutions in the Boolean Domain, UK, Cambridge Scholars Publishing, Newcastle

upon Tyne, 2016, 480 р. ISBN (10): 1–4438-8947-4 ISBN (13): 978-1-4438-8947-6.

Nielsen M., Chuang I. Quantum Computation and Quantum Information, UK, Cambridge University Press, 2000, 676 p.

ISBN 978-1-107-00217-3.

Golubitsky O., Maslov D. A study of optimal 4–bit reversible toffoli circuits and their synthesis, IEEE Transactions on

Computers, 2012, Vol. 61, No. 9, pp. 1341–1353. DOI:10.1109/TC.2011.144.

Bardis E. G., Bardis N. G., Markovski A. P. at al. Design of Boolean Functions from a great number of variables satisfying

strict avalanche criterion, Proceedings of the IEEE/WSES/IMACS : 3rd World multiconference on circuits,

systems, communications and computers, Athens, July 1999: proceedings. Athens, World Scientific, 1999, pp. 3111–3116.

Tang D., Zhang W., Tang X. Construction of balanced Boolean functions with high nonlinearity and good autocorrelation

properties, Designs, Codes and Cryptography, 2013, Vol. 67, No. 1, pp. 77–99 DOI: 10.1007/s10623-011-9587-9

Alzaidi A. A., Ahmad M., Doja M. N. at al. A New 1D Chaotic Map and β-Hill Climbing for Generating Substitution-

Boxes, IEEE Access, 2018, Vol. 6, pp. 55405–55418.DOI: 10.1109/ACCESS.2018.2871557

Lloyd S. Counting Functions Satisfying a Higher Order Strict Avalanche Criterion, EUROCRYPT ’89 : Workshop

on the Theory and Application of Cryptographic Techniques. Advances in Cryptology, 10–13 April 1989:

proceedings. Berlin, Heidelberg, Springer, 1989, Vol. 434, pp. 63–67. DOI: 10.1007/3-540-46885-4_9

Bardis N. G. Combinatorial method for Boolean SAC functions designing, WSEAS Transactions on Communications,

, Vol. 3, No. 2, pp. 746–752.

Gupta Brij B., Dharma P. Agraval, Haoxiang Wang Computer and Cyber Security: Principles, Algorithm, Applications,

and Perspectives. New York, CRC Press, Taylor & Francis Group, Boca Raton, 2019, 665 p. ISBN 9780815371335.

Dey S., Ghosh R. Cryptanalysis of 4-Bit Crypto S-Boxes in Smart Applications, Security in Smart Cities: Models, Applications,

and Challenges. Lecture Notes in Intelligent Transportation and Infrastructure. Cham, Springer, 2019, P.

–253. ISBN 978-3-030-01560-2. DOI: 10.1007/978-3-030-01560-2_10.

Woods S., Casinovi G. Efficient solution of systems of Boolean equations, 96 Proceedings of the 1996 IEEE/ACM international

conference on Computer-aided design, 10–14 November 1996: proceeding. San Jose, California, ACM

Press, 1996, pp. 542–546.

Rudeanu S. Boolean sets and most general solutions of Boolean equations, Information Sciences, 2010, Vol. 180,

No. 12, pp. 2440–2447. DOI: 10.1016/j.ins.2010.01.029.

Baneres D., Cortadella J., Kishinevsky M. A Recursive Paradigm to Solve Boolean Relations, IEEE Transactions on

Computers, 2009, Vol. 58(4), pp. 512–527. http://doi.ieeecomputersociety.org/10.1109/TC.2008.165

Rushdi Ali M. A., Motaz H. Amashah Using variableentered Karnaugh maps to produce compact parametric general

solutions of Boolean equations, International Journal of Computer Mathematics, 2011, Vol. 88, No. 15, pp. 3136–

DOI: 10.1080/00207160.2011.594505.

Rushdi A. M. A., H. M. Albarakati The Inverse Problem for Boolean Equations, Journal of Computer Science, 2012,

Vol. 8, No. 12, pp. 2098–2105. DOI: 10.3844/jcssp.2012.2098.2105

Bibilo P. N. Decomposition of Boolean functions based on the solution of logic equations. I. II. III., Izvestiya Rossijskoj

akademii nauk. Teoriya i sistemy upravleniya, 2002, No. 4, pp. 53–64; 2002, no.5, pp. 57–63.; 2003, no. 6. – P. 88–97.

Rudeanu S. On the Decomposition of Boolean Functions via Boolean Equations, Journal of Universal Computer Science,

, Vol. 10, No. 9, pp. 1294–1301.

Primenko É. A. Equivalence classes of invertible Boolean functions, Cybernetics, 1984, Vol. 20, No. 6, pp. 771–776.

DOI: 10.1007/BF01072161

Soeken M., Wille R., Keszocze O. at al. Embedding of Large Boolean Functions for Reversible Logic, Journal on

Emerging Technologies in Computing Systems, 2016, Vol. 12, № 4, Article No. 41, pp. 41:1–41:26. DOI: 10.1145/2786982.

Soeken M. Abdessaied N., De Micheli G. Enumeration of Reversible Functions and Its Application to Circuit Complexity,

Proceedings of the 8th Conference on Reversible Computation (RC 2016), 7–8 July 2016: proceedings. Bologna:

Cham, Springer, 2016, Vol 9720, pp. 255–270. ISBN: 978-3-319-40578-0. DOI: 10.1007/978-3-319-40578-0_19.

Kavut S., Maitra S., Tang D. Construction and search of balanced Boolean functions on even number of variables

towards excellent autocorrelation profile, Designs, Codes and Cryptography, 2019, Vol. 87, No. 2–3, pp. 261–276.

DOI: 10.1007/s10623-018-0522-1.

Lorens C. S. Invertible Boolean functions, IEEE Transactions on Electronic Computers, 1964, Vol. EC–13, No. 5,

pp. 529–541. DOI:10.1109/pgec.1964.263724.

Varadharajan V., Wu C.-K. Public key cryptosystems based on boolean permutations and their applications, International

Journal of Computer Mathematics, 2000, Vol. 74, No. 2, pp. 167–184. DOI: 10.1080/00207160008804932.


GOST Style Citations


1. Kemp S. Digital 2019. Essential insights into how people around the world use the Internet, mobile devices, social
media, and e-commerce. [Electronic resource] / S. Kemp. – Access mode: https: //wearesocial.com/global-digital-report-2019.
2. Lakhtaria K. I. Protecting Computer Network with Encryption Technique: A Study / K. I. Lakhtaria // Communications
in Computer and Information Science (UCMA 2011). – 2011. – Vol. 151, No. PART 2. – P. 381–390. DOI:10.1007/978-3-642-20998-7_47.
3. Demonstration of a small programmable quantum computer with atomic qubits / [S. Debnath, N. M. Linke, C. Figgatt et
al.] // Nature. – 2016. – № 536. – P. 63–66. DOI:10.1038/nature18648
4. Harrow A. W. Quantum computational supremacy / A. W. Harrow, A. Montanaro // Nature. – 2017. – Vol. 549. – P. 203–209. DOI: 10.1038/nature23458
5. Smart S. E. Experimental data from a quantum computer verifies the generalized Pauli exclusion principle /
S. E. Smart, D. I. Schuster, D. A. Mazziotti // Communications Physics. – 2019. – Vol. 2, № 1. – P. 1–6. DOI:10.1038/s42005-019-0110-3
6. Kolokotronis N. Best Affine and Quadratic Approximations of Particular Classes of Boolean Functions / N. Kolokotronis,
K. Limniotis, N. Kalouptsidis // IEEE transactions on information theory. – 2009. – Vol. 55, № 11. – P. 5211–5222.
7. Menezes A. J. Handbook of Applied Cryptography / A. J. Menezes, P. C. Van Oorschot, S. A. Vanstone. – USA :
CRC Press, Inc. Boca Raton, 1996. – 810 p.
8. A New 1D Chaotic Map and β-Hill Climbing for Generating Substitution-Boxes / [A. A. Alzaidi, M. Ahmad, M. N. Doja
at al.] // IEEE Access. – 2018. – Vol. 6. – P. 55405–55418. DOI: 10.1109/ACCESS.2018.2871557.
9. Steinbach B. Problems and New Solutions in the Boolean Domain / B. Steinbach. – UK: Cambridge Scholars Publishing,
Newcastle upon Tyne, 2016. – 480 р. ISBN (10): 1–4438-8947-4 ISBN (13): 978-1-4438-8947-6.
10. Nielsen M. Quantum Computation and Quantum Information / M. Nielsen, I. Chuang. – UK: Cambridge University
Press, 2000. – 676 p. ISBN 978-1-107-00217-3.
11. Golubitsky O. A study of optimal 4-bit reversible toffoli circuits and their synthesis / O. Golubitsky, D. Maslov //
IEEE Transactions on Computers. – 2012. – Vol. 61, № 9. – P. 1341–1353. DOI: 10.1109/TC.2011.144.
12. Design of Boolean Functions from a great number of variables satisfying strict avalanche criterion / [E. G. Bardis,
N. G. Bardis, A. P Markovski at al.] // Proceedings of the IEEE/WSES/IMACS : 3rd World multiconference on circuits,
systems, communications and computers, Athens, July 1999: proceedings. – Athens: World Scientific, 1999. – P. 3111–3116.
13. Tang D. Construction of balanced Boolean functions with high nonlinearity and good autocorrelation properties /
D. Tang, W. Zhang, X. Tang // Designs, Codes and Cryptography. – 2013. – Vol. 67, № 1. – P. 77–99 DOI:
10.1007/s10623-011-9587-9
14. A New 1D Chaotic Map and β-Hill Climbing for Generating Substitution-Boxes / [A. A. Alzaidi, M. Ahmad, M. N. Doja
at al.] // IEEE Access. – 2018. – Vol. 6. – P. 55405 – 55418. DOI: 10.1109/ACCESS.2018.2871557
15. Lloyd S. Counting Functions Satisfying a Higher Order Strict Avalanche Criterion / S. Lloyd // EUROCRYPT ’89 :
Workshop on the Theory and Application of Cryptographic Techniques. Advances in Cryptology, 10–13 April 1989:
proceedings. – Berlin, Heidelberg: Springer, 1989. – Vol. 434. – P. 63–67. DOI: 10.1007/3-540-46885-4_9
16. Bardis N. G. Combinatorial method for Boolean SAC functions designing / N. G. Bardis // WSEAS Transactions on
Communications. – 2004. – Vol. 3, № 2. – P. 746–752.
17. Gupta Brij B. Computer and Cyber Security: Principles, Algorithm, Applications, and Perspectives / Brij B. Gupta,
Dharma P. Agraval, Haoxiang Wang. – London, New York:CRC Press, Taylor & Francis Group, Boca Raton, 2019. –
665 p. ISBN 9780815371335.
18. Dey S. Cryptanalysis of 4-Bit Crypto S-Boxes in Smart Applications / S. Dey, R. Ghosh // Security in Smart Cities:
Models, Applications, and Challenges. Lecture Notes in Intelligent Transportation and Infrastructure. – Cham:
Springer, 2019. – P. 211–253. ISBN 978-3-030-01560-2. DOI: 10.1007/978-3-030-01560-2_10.
19. Woods S. Efficient solution of systems of Boolean equations / S. Woods, G. Casinovi // 96 Proceedings of the 1996
IEEE/ACM international conference on Computer-aided design, 10–14 November 1996: proceeding. – San Jose, California
: ACM Press, 1996. – P. 542–546.
20. Rudeanu S. Boolean sets and most general solutions of Boolean equations / S. Rudeanu // Information Sciences. –
2010. – Vol. 180, № 12. – P. 2440–2447. DOI:10.1016/j.ins.2010.01.029.
21. Baneres D. A Recursive Paradigm to Solve Boolean Relations / D. Baneres, J. Cortadella, M. Kishinevsky // IEEE
Transactions on Computers. – 2009. – Vol. 58(4). – P. 512–527.http://doi.ieeecomputersociety.org/10.1109/TC.2008.165
22. Rushdi Ali M. A. Using variable-entered Karnaugh maps to produce compact parametric general solutions of Boolean
equations / Ali M. A. Rushdi, Motaz H. Amashah // International Journal of Computer Mathematics. – 2011. – Vol. 88,
№ 15. – P. 3136–3149. DOI:10.1080/00207160.2011.594505.
23. Rushdi A. M. A. The Inverse Problem for Boolean Equations / A. M. A. Rushdi, H. M. Albarakati // Journal of Computer
Science. – 2012. – Vol. 8, № 12. – P. 2098–2105. DOI: 10.3844/jcssp.2012.2098.2105
24. Bibilo P.N. Decomposition of Boolean functions based on the solution of logic equations. I. II. III. / P. N. Bibilo //
Izvestiya Rossijskoj akademii nauk. Teoriya i sistemy upravleniya. – 2002. – No. 4. – P. 53–64; 2002. – No.5. –
P. 57–63.; 2003. – No. 6. – P. 88–97.
25. Rudeanu S. On the Decomposition of Boolean Functions via Boolean Equations / S. Rudeanu // Journal of Universal
Computer Science. – 2004. – Vol. 10, № 9. – P. 1294–1301.
26. Primenko É. A. Equivalence classes of invertible Boolean functions / É. A. Primenko // Cybernetics. – 1984. – Vol. 20,
№ 6. – P. 771–776. DOI: 10.1007/BF01072161
27. Soeken M. Embedding of Large Boolean Functions for Reversible Logic / [M. Soeken, R. Wille, O. Keszocze еt al.] //
Journal on Emerging Technologies in Computing Systems. – 2016. – Vol. 12, № 4, Article No. 41. – P. 41:1–41:26. DOI:
10.1145/2786982.
28. Soeken M. Enumeration of Reversible Functions and Its Application to Circuit Complexity / M. Soeken, N. Abdessaied,
G. De Micheli // Proceedings of the 8th Conference on Reversible Computation (RC 2016), 7–8 July 2016: proceedings.
– Bologna: Cham, Springer, 2016. – Vol. 9720. – P. 255–270. ISBN: 978-3-319-40578-0. DOI: 10.1007/978-
3-319-40578-0_19.
29. Kavut S. Construction and search of balanced Boolean functions on even number of variables towards excellent
autocorrelation profile / S. Kavut S. Maitra, D. Tang // Designs, Codes and Cryptography. – 2019. – Vol. 87, № 2–
3. – P. 261–276. DOI: 10.1007/s10623-018-0522-1.
30. Lorens C. S. Invertible Boolean functions / C. S Lorens // IEEE Transactions on Electronic Computers – 1964 –
Vol. EC–13, № 5. – P. 529–541. DOI:10.1109/pgec.1964.263724.
31. Varadharajan V. Public key cryptosystems based on boolean permutations and their applications / V. Varadharajan,
C.-K. Wu // International Journal of Computer Mathematics. – 2000. – Vol. 74, № 2. – P. 167–184. DOI:10.1080/00207160008804932.






Copyright (c) 2020 I. M. Fedotova-Piven, V. M. Rudnytskyi, O. B. Piven, T. V. Myroniuk

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

Address of the journal editorial office:
Editorial office of the journal «Radio Electronics, Computer Science, Control»,
National University "Zaporizhzhia Polytechnic", 
Zhukovskogo street, 64, Zaporizhzhia, 69063, Ukraine. 
Telephone: +38-061-769-82-96 – the Editing and Publishing Department.
E-mail: rvv@zntu.edu.ua

The reference to the journal is obligatory in the cases of complete or partial use of its materials.