О схемах предварительного распределения ключей и ключевых пространств в беспроводных сенсорных сетях со структурой комбинаторного блок-дизайна

Александр [Aleksandr] Борисович [B.] Фролов [Frolov]; Наталья [Natalya] Петровна [P.] Кочетова [Kochetova]

doi:10.24160/1993-6982-2023-4-162-176

Александр [Aleksandr] Борисович [B.] Фролов [Frolov]
Наталья [Natalya] Петровна [P.] Кочетова [Kochetova]

DOI: https://doi.org/10.24160/1993-6982-2023-4-162-176

Keywords: key pre-distribution scheme, multiple space key pre-distribution scheme, combinatorial block design, combined combinatorial block design, security parameter, unital, combined projective plane, local connectivity, global connectivity, node key memory

Abstract

The aim of this work is to present, along with performing their comparative analysis, the structural characteristics and security parameters of the Key Pre-Distribution Schemes (KPDS) and Multiple Space Key Pre-Distribution Schemes (MSKPDS) in wireless sensor networks (WSN) with combinatorial block design (CBD) and combined combinatorial block design (CCBD) structure.

A KPDS is determined by a totality of the sets of WSN nodes, in the key memory of which the same keys are pre-recorded for confidential exchange between the nodes of these sets. An MSKPDS differs in that instead of keys, identical pre-keys are written to the specified nodes, which make it possible to calculate, using node identifiers, different keys for confidential communication between the nodes of these sets. As a rule, the specified sets of nodes correspond to blocks or dual blocks of a certain CBD or blocks and dual blocks of a certain CCBD. If direct links between the nodes of these sets are provided in the WSN, and there are no direct links between other nodes, then, by definition, the KPDS, MSKPDS and WSN are built with the structure of this CBD or CCBD. The CBD structure is determined by a graph on the set of its blocks or dual blocks. Vertices that have common elements are regarded as adjacent ones. The nodes and links of the WSN with the CBD structure correspond to the vertices and edges of this graph. In such WSN, the sets of the KPDS or MSKPDS nodes, to which common keys or common pre-keys are assigned, are composed of nodes corresponding to the vertices of the CBD graph containing the element corresponding to this common key or pre-key. The CCBD structure is determined by a graph on a set of pairs (a CBD block, an element of this block). Vertices that have the same first or the same second elements are adjacent ones. The WSN with the CCBD structure is determined by this graph according to the same rule. The KPDS and MSKPDS in it are defined on the sets of all vertices of this graph that have the same first or the same second components (constituting the CCBD blocks and dual blocks). As a result, two keys are assigned to each node. Once key identifiers are assigned to the vertices, the above-mentioned CBD and CCBD graphs become key sharing graphs (KSG). The objective of this work is to perform a comparative analysis of the structural characteristics (the longest length of the shortest path in the KSG, the size of the node key memory), deterministic and probabilistic security characteristics of the MSKPDS with the CBD structure and the MSPDS with the CCBD structure. Two CBDs were chosen for considering specific cases: symmetric (a projective plane) and asymmetric (a unital combinatorial block design). It is shown that the advantages of MSKPDS with the CCBD structure are a smaller share of compromised direct links when one node is compromised and a small amount of key memory (equal to 2 or linearly dependent on the security parameter), and the shortcoming is that there are three-step routes in the key agreement graph. By limiting the security parameter of deterministic MSKPDS, it is possible to improve the security parameter of probabilistic schemes with a significant reduction of key memory. The results of the work can be used in searching for compromise solutions in choosing the structure and security parameters of the KPDS and MSKPDS in the WSN.

Information about authors

Александр [Aleksandr] Борисович [B.] Фролов [Frolov]

Dr.Sci. (Techn.), Professor of Mathematical and Computer Modeling Dept., NRU MPEI, e-mail: Frolovab@mpei.ru

Наталья [Natalya] Петровна [P.] Кочетова [Kochetova]

Master's Student of Mathematical and Computer Modeling Dept., NRU MPEI, e-mail: Kochetovanp@mpei.ru

References

1. Gholami K.El., Yassine M.Y., Fatani I. F-E. The IEEE 802.15.4 Standard in Industrial Applications: a Survey // J. Theoretical and Appl. Information Technol. 2021. V. 99. No. 15. Pp. 1—17.
2. Kim S.H., Chong P.K., Kim T. Performance Study of Routing Protocols in ZigBee Wireless Mesh Networks // Wireless Pers Commun. 2017. V. 95. Pp. 1829—1853.
3. Kim T., Kim S. H., Yang J., Se Yoo, Kim D. Neighbor Table-based Shortcut Tree Routing in Zigbee Wireless Networks // IEEE Trans. Parallel and Distributed Systems. 2014. V. 25(3). Pp. 706—716.
4. Gomez C., Paradells J. Wireless Home Automation Networks: A Survey of Architectures and Technologies // IEEE Comm. Magazine. 2010. V. 48(6). Pp. 92—101.
5. Кочетова Н.П., Фролов А.Б. Масштабирование сетей и их ключевых систем на основе совмещенных комбинаторных блок-дизайнов // Информационные технологии. 2023. № 4. Т. 29. С. 171—182.
6. Neda Solari Esfehani, Hamid Haj Seyyed Javadi H. A Survey of Key Pre-distribution Schemes Based on Combinatorial Designs for Resource-constrained Devices in the IoT Network // Wireless Networks. 2021. V. 27(11). Pp. 3025—3052.
7. Mitchell C.J., Piper F.C. Key Storage in Secure Networks // Discrete Appl. Math. 1988. V. 21. No. 3. Pp. 215—228.
8. Dyer M., Fenner T., Frieze A., Thomason A. On Key Storage in Secure Networks // J. Cryptology. 1995. V. 8(4). Pp. 189—200.
9. Eschenauer L., Gligor V. A Key Management Scheme for Distributed Sensor Networks // Proc. IX ACM Conf. Computer and Communications Security. 2002. Pp. 41—47.
10. Lee J., Stinson D.R. Deterministic Key Pre-distribution Schemes for Distributed Sensor Networks // Lecture Notes in Computer Sci. 2005. V. 3357. Pp. 294—307.
11. Lee J., Stinson D.R. A Combinatorial Approach to Key Pre-distributionfor Distributed Sensor Networks // Proc. IEEE WCNC. 2005. V. 2. Pp. 1200—1205.
12. Camtepe S.A., Yener B. Key Distribution Mechanisms for Wireless Sensor Networks: a Survey. Tech. Rep. TR-05-07. Rensselaer Polytechnic Institute, 2005.
13. Можаров Г.П. Отказоустойчивые компьютерные сети, построенные на основе комбинаторных блок-дизайнов // Вестник МГТУ им. Н.Э. Баумана. Серия «Приборостроение». 2016. № 6. С. 41—53.
14. Пархоменко П.П. Алгоритмизация синтеза комбинаторных блок-схем одного класса // Автоматика и телемеханика. 2016. № 7. С. 113—122.
15. Blom R. An Optimal Class of Symmetric Key Generation Systems // Proc. Workshop Theory and Appl. Cryptographic Techniques. 1985. V. 209. Pp. 335—338.
16. Du W. e. a. A Pairwise Key Pre-distribution Scheme for Wireless Sensor Networks // ACM Trans. Inform. and Syst. Security. 2005. V. 8. Pp. 228—258.
17. Lee J., Stinson D.R. On the Construction of Practical Key Predistribution Schemes for Distributed Sensor Networks Using Combinatorial Designs // ACM Trans. Inform. and Syst. Security. 2008. V. 11(2). Pp. 1—35.
18. Paterson M.B., Stinson D.R. A Unified Approach to Combinatorial Key Pre-distribution Schemes for Sensor Networks // Designs Codes and Cryptography.·2014. V. 71. Pp. 433—457.
19. Iqbal S., Sujatha B.R. Secure Key Management Scheme for Hierarchical Network Using Combinatorial Design // J. Information Syst. and Telecommunication. 2022. V. 10(37). Pp. 20—27.
20. Kumar A., Bansal N., Pais A.R. New Key Pre-distribution Scheme Based on Combinatorial Design for Wireless Sensor Networks // IET Communications. 2019. V. 13(7). Pp. 892—897.
21. Urivskiy A. On Identity-based-like Non-interactive Key Establishment for Key Pre-distribution Schemes. // Proc. Algebraic and Combinatorial Coding Theory Conf. 2020. Pp. 150—155.
22. Urivskiy A. Key Predistribution Scheme Using Affine Planes and Blom’s Scheme // Proc. Int. Math. Conf. 50 Years of IITP. 2011. Pp. 1—5.
23. Chegeni V., Haj Seyyed Javadi H., Moazami Goudarzi M.R., Rezakhani A. A Scalable Key Pre-distribution Scheme Based on the Unital Design for the Internet of Things Security // IETE J. Research. 2021. Pp. 1—12.
24. Xu Ch., Liu W. Key Updating Methods for Combinatorial Design Based Key Management Schemes // J. Sensors. 2014. V. 8. Pp. 1—8.
25. Boubiche D.E., Athmani S., Boubiche S., Toral-Cruz H. Cybersecurity Issues in Wireless Sensor Networks: Current Challenges and Solutions // Wireless Personal Communications. 2021. V. 117(1). Pp. 177—213.
26. Alghanam O., Qatawneh M., Almobaideen W., Saadeh M. A new Hierarchical Architecture and Protocol for Key Distribution in the Context of IoT-based Smart Cities (2022) // J. Information Security and Appl. 2022. V. 67(2). P. 103173.
27. Solari Esfehani N., Haj Seyyed Javadi H. A High Resilience and High Scalable Key Pre-distribution Scheme Based on Combinatorial Designs for Resource-Constrained Devices in IoT Networks // Wireless Personal Communications. 2022. V. 127(4). Pp. 1—30.
28. Kumar V., Malik N. A Survey of Key Management Schemes for Large Scale Wireless Sensor Networks // Proc. VII Intern. Conf. Advanced Computing and Communication Syst. 2021. Pp. 628—631.
29. Sirohi A., Agarwal A.K. Security in Wireless Sensor Network (WSN): a Detailed Survey // Intern. J. Advanced Sci. and Technol. 2020. V. 29(5). Pp. 376—387.
30. Solari Esfehani N., Haj Seyyed Javadi H. A Survey of Key Pre-distribution Schemes Based on Combinatorial Designs for Resource-constrained Devices in the IoT network // Wireless Networks. 2021. V. 27(4). Pp. 3025—3052.
31. Frolov A., Kochetova N. Networks with the Structure of a Combined Combinatorial Block Design // Proc. Intern. Conf. Electrical, Computer, Communications and Mechatronics Eng. 2021. Pp. 1—6.
32. Клягин А.О., Кочетовa Н.П., Темников Д.Ю., Фролов А.Б. О синтезе систем, имеющих структуру комбинаторной блок-схемы // Известия РАН. Серия «Теория и системы управления». 2021. № 4. С. 84—93.
33. Frolov A., Klyagin A., Kochetova N., Vinnikov A. Educational Desktop for Remote Modeling of Wireless Computer Networks subject to Constraints // Proc. VI Intern. Conf. Information Technol. in Eng. Education. 2022. Pp. 1—5.
---
Для цитирования: Фролов А.Б., Кочетова Н.П. О схемах предварительного распределения ключей и ключевых пространств в беспроводных сенсорных сетях со структурой комбинаторного блок-дизайна // Вестник МЭИ. 2023. № 4. С. 162—176. DOI: 10.24160/ 1993-6982-2023-4-162-176
#
1. Gholami K.El., Yassine M.Y., Fatani I. F-E. The IEEE 802.15.4 Standard in Industrial Applications: a Survey. J. Theoretical and Appl. Information Technol. 2021;99;15:1—17.
2. Kim S.H., Chong P.K., Kim T. Performance Study of Routing Protocols in ZigBee Wireless Mesh Networks. Wireless Pers Commun. 2017;95:1829—1853.
3. Kim T., Kim S. H., Yang J., Se Yoo, Kim D. Neighbor Table-based Shortcut Tree Routing in Zigbee Wireless Networks. IEEE Trans. Parallel and Distributed Systems. 2014;25(3):706—716.
4. Gomez C., Paradells J. Wireless Home Automation Networks: A Survey of Architectures and Technologies. IEEE Comm. Magazine. 2010;48(6):92—101.
5. Kochetova N.P., Frolov A.B. Masshtabirovanie Setey i Ikh Klyuchevykh Sistem na Osnove Sovmeshchennykh Kombinatornykh Blok-dizaynov // Informatsionnye Tekhnologii. 2023;4;29:171—182. (in Russian).
6. Neda Solari Esfehani, Hamid Haj Seyyed Javadi H. A Survey of Key Pre-distribution Schemes Based on Combinatorial Designs for Resource-constrained Devices in the IoT Network. Wireless Networks. 2021;27(11):3025—3052.
7. Mitchell C.J., Piper F.C. Key Storage in Secure Networks. Discrete Appl. Math. 1988;21;3:215—228.
8. Dyer M., Fenner T., Frieze A., Thomason A. On Key Storage in Secure Networks. J. Cryptology. 1995;8(4):189—200.
9. Eschenauer L., Gligor V. A Key Management Scheme for Distributed Sensor Networks. Proc. IX ACM Conf. Computer and Communications Security. 2002:41—47.
10. Lee J., Stinson D.R. Deterministic Key Pre-distribution Schemes for Distributed Sensor Networks. Lecture Notes in Computer Sci. 2005;3357:294—307.
11. Lee J., Stinson D.R. A Combinatorial Approach to Key Pre-distributionfor Distributed Sensor Networks. Proc. IEEE WCNC. 2005;2:1200—1205.
12. Camtepe S.A., Yener B. Key Distribution Mechanisms for Wireless Sensor Networks: a Survey. Tech. Rep. TR-05-07. Rensselaer Polytechnic Institute, 2005.
13. Mozharov G.P. Otkazoustoychivye Komp'yuternye Seti, Postroennye na Osnove Kombinatornykh Blok-dizaynov. Vestnik MGTU im. N.E. Baumana. Seriya «Priborostroenie». 2016;6:41—53. (in Russian).
14. Parkhomenko P.P. Algoritmizatsiya Sinteza Kombinatornykh Blok-skhem Odnogo Klassa. Avtomatika i Telemekhanika. 2016;7:113—122. (in Russian).
15. Blom R. An Optimal Class of Symmetric Key Generation Systems. Proc. Workshop Theory and Appl. Cryptographic Techniques. 1985;209:335—338.
16. Du W. e. a. A Pairwise Key Pre-distribution Scheme for Wireless Sensor Networks. ACM Trans. Inform. and Syst. Security. 2005;8:228—258.
17. Lee J., Stinson D.R. On the Construction of Practical Key Predistribution Schemes for Distributed Sensor Networks Using Combinatorial Designs. ACM Trans. Inform. and Syst. Security. 2008;11(2):1—35.
18. Paterson M.B., Stinson D.R. A Unified Approach to Combinatorial Key Pre-distribution Schemes for Sensor Networks. Designs Codes and Cryptography.·2014;71:433—457.
19. Iqbal S., Sujatha B.R. Secure Key Management Scheme for Hierarchical Network Using Combinatorial Design. J. Information Syst. and Telecommunication. 2022;10(37):20—27.
20. Kumar A., Bansal N., Pais A.R. New Key Pre-distribution Scheme Based on Combinatorial Design for Wireless Sensor Networks. IET Communications. 2019;13(7):892—897.
21. Urivskiy A. On Identity-based-like Non-interactive Key Establishment for Key Pre-distribution Schemes.. Proc. Algebraic and Combinatorial Coding Theory Conf. 2020:150—155.
22. Urivskiy A. Key Predistribution Scheme Using Affine Planes and Blom’s Scheme. Proc. Int. Math. Conf. 50 Years of IITP. 2011:1—5.
23. Chegeni V., Haj Seyyed Javadi H., Moazami Goudarzi M.R., Rezakhani A. A Scalable Key Pre-distribution Scheme Based on the Unital Design for the Internet of Things Security. IETE J. Research. 2021:1—12.
24. Xu Ch., Liu W. Key Updating Methods for Combinatorial Design Based Key Management Schemes. J. Sensors. 2014;8:1—8.
25. Boubiche D.E., Athmani S., Boubiche S., Toral-Cruz H. Cybersecurity Issues in Wireless Sensor Networks: Current Challenges and Solutions . Wireless Personal Communications. 2021;117(1):177—213.
26. Alghanam O., Qatawneh M., Almobaideen W., Saadeh M. A new Hierarchical Architecture and Protocol for Key Distribution in the Context of IoT-based Smart Cities (2022). J. Information Security and Appl. 2022;67(2):103173.
27. Solari Esfehani N., Haj Seyyed Javadi H. A High Resilience and High Scalable Key Pre-distribution Scheme Based on Combinatorial Designs for Resource-Constrained Devices in IoT Networks. Wireless Personal Communications. 2022;127(4):1—30.
28. Kumar V., Malik N. A Survey of Key Management Schemes for Large Scale Wireless Sensor Networks. Proc. VII Intern. Conf. Advanced Computing and Communication Syst. 2021:628—631.
29. Sirohi A., Agarwal A.K. Security in Wireless Sensor Network (WSN): a Detailed Survey. Intern. J. Advanced Sci. and Technol. 2020;29(5):376—387.
30. Solari Esfehani N., Haj Seyyed Javadi H. A Survey of Key Pre-distribution Schemes Based on Combinatorial Designs for Resource-constrained Devices in the IoT network. Wireless Networks. 2021;27(4):3025—3052.
31. Frolov A., Kochetova N. Networks with the Structure of a Combined Combinatorial Block Design. Proc. Intern. Conf. Electrical, Computer, Communications and Mechatronics Eng. 2021:1—6.
32. Klyagin A.O., Kochetova N.P., Temnikov D.Yu., Frolov A.B. O Sinteze Sistem, Imeyushchikh Strukturu Kombinatornoy Blok-skhemy. Izvestiya RAN. Seriya «Teoriya i Sistemy Upravleniya». 2021;4:84—93. (in Russian).
33. Frolov A., Klyagin A., Kochetova N., Vinnikov A. Educational Desktop for Remote Modeling of Wireless Computer Networks subject to Constraints. Proc. VI Intern. Conf. Information Technol. in Eng. Education. 2022:1—5
---
For citation: Frolov A.B., Kochetova N.P. On Key and Multiple Space Key Pre-Distribution Schemes in Wireless Sensor Networks with a Combinatorial Block Design Structure. Bulletin of MPEI. 2023;4:162—176. (in Russian). DOI: 10.24160/1993-6982-2023-4-162-176