Segmentation of Tree-Like Data Structures and Their Parallel Processing in Authentication Methods Based on Block Coupling Encoding

Purpose of reseach. In the tasks of authenticating groups of messages encoded in the mode of chaining blocks, there is a need for the formation and processing of specific tree-like structures. The contents of such structures, in addition to information about the placement of data in the internal memory of the calculators, describes the relative location of messages in the data stream between subscribers of a peer-to-peer network. This information is necessary to isolate a structured set from the entire message stream to the receiver, for which its source is uniquely determined. Using approaches to segmentation of tree structures allows you to parallelize the processes of adding elements to it and searching for areas corresponding to an authentication error.

Methods. The division of the tree structure into areas subject to modification and areas for analysis is based on a metric dynamically formed from message authentication codes – the position of a specific message in a structured set of messages transmitted from the source to the receiver. The value of this metric determines the distance from the root of the tree, which defines the boundary between the two named areas

Results. By isolating the modified and analyzed sections of the tree structure, races of processes implementing independent algorithms for working with it are excluded. The possibility of detecting authentication errors before receiving the last message in a structured set of messages is shown. As a result, there is no need to transmit those group messages that were supposed to be sent after the error was detected. Formulas for estimating the average transmission time of multiple messages with sequential and parallel implementation of procedures for the formation and processing of a tree structure containing descriptors of incoming messages to the receiver are given.

Conclusion. The paper shows that the parallel implementation of algorithms for adding elements to the tree structure and the algorithm for searching for areas corresponding to an error reduces the average transmission time of a group of messages by 5-12% compared with the sequential implementation of these algorithms. This reduces the load on the communication channel for the target class of systems using block coupling encoding for authentication.

1. Bellare M., Kilian J., Rogaway P. The security of the cipher block chaining message authentication code. Journal of Computer and System Sciences, 2000. 61(3):pp. 362-399 DOI: 10.1006/jcss.1999.1694

2. Iwata T., Kurosawa K. OMAC: one-key CBC MAC. Fast Software Encryption, 2003, pp. 129 – 53.

3. Dworkin M. SP 800-38D: Recommendation for Block Cipher Modes of Operation: Galois/Counter Mode (GCM) and GMAC, 2007.

4. Dworkin M. Recommendatin for Block Cipher Modes of Operation: The CCM Mode for Authentication and Confidentiality. Nist Spec. Publ., 2004, vol. 800, 38 р.

5. Stallings W. The advanced encryption standard. Cryptologia, 2002, vol. 26, no. 3, pp. 165–188.

6. Black J. Authenticated Encryption. Encycl. Cryptogr. Secur., 2005, pp. 11–21.

7. Black J., Rogaway P. CBC MACs for arbitrary-length messages: The three-key constructions. J. Cryptol, 2005, vol. 18, no. 2, pp. 111–131.

8. IEEE Standard for Low-Rate Wireless Networks. IEEE Std 802.15.4-2020, pp.1-800, 23 July 2020, doi: 10.1109/IEEESTD.2020.9144691.

9. Tanygin M. O., Ahmad A.A., Kazakova O. V., Golubov D. A. Recursive Algorithm for Forming Structured Sets of Information Blocks that Increase the Speed of Performing Procedures for Determining Their Source. Izvestiya Yugo-Zapadnogo gosudarstvennogo universiteta = Proceedings of the Southwest State University. 2023; 27(1): 73-91 (In Russ.). https://doi.org/10.21869/2223-1560-2023-27-1-73-91.

10. Pasechnikov K.A., Ivanova G.S. Sintez optimal'nykh struktur dannykh dlya resheniya zadach na grafakh [Synthesis of optimal data structures for solving problems on graphs]. Vestnik Moskovskogo gosudarstvennogo tekhnicheskogo universiteta im. N.E. Baumana. Seriya Priborostroenie = Bulletin of the Bauman Moscow State Technical University, 2008, no. 4(73), pp. 29-37.

11. Kolganov A.S. Parallel'naya realizatsiya algoritma poiska minimal'nykh ostovnykh derev'ev s ispol'zovaniem tsentral'nogo i graficheskogo protsessorov [Parallel implementation of minimum spanning tree algorithm on CPU and GPU]. Vestnik Yuzhno-Ural'skogo gosudarstvennogo universiteta. Seriya: Vychislitel'-naya matematika i informatika = Bulletin of the South Ural State University, 2016, vol. 5, no. 3, pp. 5-19. DOI 10.14529/cmse160301

12. Tasci S., Demirbas M. Employing in-memory data grids for distributed graph processing. IEEE 2015 IEEE International Conference on Big Data (Big Data), 2015, pp. 1856– 1864. doi:10.1109/bigdata.2015.7363959

13. Volchikhin V. I., Vashkevich N. P., Biktashev R. A. Modeli sobytijnyh nedeterminirovannyh avtomatov predstavleniya algoritmov upravleniya vzaimodejstvuyushchimi processami v mnogoprocessornyh vychislitel'nyh sistemah na osnove ispol'zovaniya mekhanizma monitora [Models of event-driven nondeterministic automata representing algorithms for controlling interacting processes in multiprocessor computing systems based on the use of a monitor mechanism]. Izvestiya vysshikh uchebnykh zavedenii. Povolzhskii region. Tekhnicheskie nauki = Izvestia of higher educational institutions. Volga region. Technical sciences, 2013, no. 2(26), pp. 5-14.

14. Courtois P. J.; Heymans F.; Parnas D. L. Concurrent Control with "Readers" and "Writers". Communications of the ACM. 14 (10), 1971, pp. 667–668. doi:10.1145/362759.362813.S2CID 7540747.

15. Babionitakis K., Doumenis G.A., Georgakarakos G. et al. A real-time motion estimation FPGA architecture. J Real-Time Image Proc, 2008, no. 3, pp. 3–20. https://doi.org/10.1007/s11554-007-0070-9

16. Dorogikh N. O., Yurin A. Y. Podhod k avtomatizirovannomu napolneniyu grafov znanij sushchnostyami na osnove analiza tablic [An approach to automated filling of knowledge graphs with entities based on table analysis]. Ontologiya proektirovaniy = Design Ontology, 2022, vol. 12, no. 3(45), pp. 336-352. DOI 10.18287/2223-9537-2022-12-3-336-352.

17. Putnin V. I. Avtomatizaciya processa postroeniya raspisaniya s primeneniem topologicheskoj sortirovki na grafe [Automating the process of building a schedule using topological sorting on a graph]. E-Scio = Aposematic, 2021, no. 3(54), pp. 584-588.

18. Tanygin M. O., Dobroserdov O. G., Vlasova A. O., Ahmad A. A. Metod ogranicheniya mnozhestva obrabatyvaemyh priyomnikom blokov dannyh dlya povysheniya dostovernosti operacij opredeleniya ih istochnika [Method of limiting the set of data blocks processed by the receiver to increase the reliability of operations for determining their source]. Trudy MAI = Proceedings of MAI, 2021, vol. 118, no. 3, 15 doi 10.34759/trd-2021-118-14.

19. Modinger D., Frohlich N., Hauck F.J. Pixy: A Privacy-Increasing Group Creation Scheme. Conference: ICNCC 2020: 2020 The 9th International Conference on Networks, Communication and Computing. December 2020 DOI: 10.1145/3447654.3447671.

20. Khabibullin N. F., Shkerdin A. N., Shcherbenko A. N. Povyshenie propusknoj sposobnosti sistem peredachi s peresprosom za schet vvedeniya dopolnitel'noj svyazi mezhdu processami dekodirovaniya s ispravleniem i obnaruzheniem oshibok [Increasing the throughput of transmission systems with a replay by introducing additional communication between decoding processes with correction and error detection]. Internet-zhurnal Naukovedenie = Online journal of Science Studies, 2016, vol. 8, no. 3(34), pp. 143 (In Russ.)

21. Tuchkin A.V. Principy funkcionirovaniya protokola kanal'nogo urovnya dlya paketnoj peredachi raznorodnogo trafika po nizkoskorostnym kanalam [Principles of functioning of the channel layer protocol for packet transmission of heterogeneous traffic over lowspeed channels]. T-Comm: Telekommunikatsii i transport = T-Comm: Telecommunications and Transport, 2008, vol. 2, no. 3, pp. 31-33.

22. Maltsev G. N. Pomekhoustojchivost' i skrytnost' peredachi informacii po radiokanalam na osnove kombinirovannogo sluchajnogo kodirovaniya [Noise immunity and secrecy of information transmission over radio channels based on combined random coding]. Informatsionno-upravlyayushchie sistemy = Information and Control Systems, 2015, no. 2(75), pp. 82-89. DOI 10.15217/issn1684-8853.2015.2.82.

23. Tanygin M. O., Chesnokova A. A., Akhmad A. A. A. Snizhenie resursnyh zatrat na obrabotku kodov autentifikacii soobshchenij za schet ogranicheniya chisla obrabatyvaemyh soobshchenij [Reduction of resource costs for processing message authentication codes by limiting the number of processed messages]. Prikaspiiskii zhurnal: upravlenie i vysokie tekhnologii = Caspian Journal: Management and High Technologies, 2022, no. 4(60), pp. 22-29.

24. Tanygin M. O., Chesnokova A. A., Ahmad A. A. A. Povyshenie skorosti opredeleniya istochnika soobshchenij za schet ogranicheniya mnozhestva obrabatyvaemyh blokov dannyh [Increasing the speed of determining the source of messages by limiting the set of processed data blocks]. Trudy MAI = Proceedings of MAI, 2022, no. 125. DOI 10.34759/trd-2022-125-20.

25. IEEE Standard for Low-Rate Wireless Networks. IEEE Std 802.15.4-2020, pp.1-800, 23 July 2020, doi: 10.1109/IEEESTD.2020.9144691