The Algorithmic Aspects of Creating and Using Wireless Sensor Network Key Spaces Based on Combinatorial Block Diagrams
DOI:
https://doi.org/10.24160/1993-6982-2021-2-108-118Keywords:
wireless sensor network, key space, projective plane, combinatorial block diagram, transversal combinatorial block diagram, algebraic block identifier, duality rule for blocks and dual blocks numbering, key compromising, incompleteness of furnishing a node with keys, incompleteness of the systemAbstract
Algorithmic approach principles relating to development and use of wireless sensor network (WSS) key spaces are formulated based on an analysis of the keys management peculiarities. The formulated principles, which meet certain requirements for the WSS key spaces, have been elaborated proceeding from the assumption that their structure corresponds to one of the varieties of combinatorial block diagrams: cyclic or acyclic projective plane, linear or quadratic transversal block diagrams. Owing to the WSS having a distributed configuration, it becomes possible to avoid the need to construct a combinatorial block diagram in full scope, and the required blocks are computed, whenever necessary, in scaling the network (in adding new nodes) or when determining, in a decentralized manner, the switching parameters of specific nodes. To do so, it is necessary to have algorithms for computing the blocks of the combinatorial block diagram (as the sets of key numbers allocated to a given node) and dual blocks (as the sets of the numbers of nodes to which keys are assigned with the numbers coinciding with the numbers of dual blocks), as well as algorithms for solving derived problems: computing of the key numbers common to two nodes and the number of the node that has a common key with one of two nodes and, possibly, another key with the other one. These problems are solved by using the numbering of elements, blocks and dual blocks in accordance with the proposed duality rule: sets of elements and dual blocks are in one-to-one correspondence by numbering; the dual block with a specified number contains the numbers of blocks containing elements with this number. Distributed (independent) calculation of blocks is carried out on the basis of algebraic identifiers computed by block numbers. In addition to the possible absence of a physical connection between the nodes, the inadmissibility of using separate (compromised) keys is taken into account, and the incomplete furnishing of the network nodes with keys, as well as the incompleteness of the system implementation as a whole. Algorithms for computing the switching parameters of two nodes in designing the WSS and an algorithm for computer modeling of the calculation of such parameters during the WSS operation subject to the specified constraints and in using any of the above types of combinatorial block diagrams are presented.
References
2. Mitchell C.J. Combinatorial Techniques for Key Storage Reduction in Secure Networks // Technical Memo. Bristol: Hewlett-Packard Laboratories, 1988.
3. Dyer M., Fenner T., Frieze A., Thomason A. On Key Storage in Secure Networks // J. Cryptology. 1995. V. 8(4). Pp. 189—200.
4. Erdösh P., Frankl P., Füredi Z. Families of Finite Sets in Which no Set is Covered by the Union of Two Others // J. Combinatorial Theory. 1982. V. A33. Pp. 158—166.
5. Erdösh P., Frankl P., Füredi Z. Families of Finite Sets in Which no Set is Covered by the Union of r Others // Israel J. Math. 1985. V. 51. Pp. 75—89.
6. Lee J., Stinson D.R. On the Construction of Practical Key Predistribution Schemes for Distributed Sensor Networks Using Combinatorial Designs // ACM Trans. Information and Syst. Security. 2008. V. 11. No. 2. Pp. 1—35.
7. Stinson D.R., Van Trung T. Some New Results on Key Distribution Patterns and Broadcast Encryption // Designs, Codes and Cryptography. 1998. V. 14. Pp. 261—279
8. Stinson D.R., Van Trung T., Wei R. Secure Frameproof Codes, Key Distribution Patterns, Group Testing Algorithms and Related Structures // J. Statist. Plan. Infer. 2000. V. 86. No. 2. Pp. 595—617
9. Stinson D.R., Wei R., Zhu L. New Constructions for Perfect Hash Families and Related Structures Using Combinatorial Designs and Codes // J. Combinatorial Designs. 2000. V. 8. No. 3. Pp. 189—200.
10. Camtepe S., Yener B. Combinatorial Design of Key Distribution Mechanisms for Wireless Sensor Networks // Lecture Notes in Computer Sci. 2004. V. 3193. Pp. 293—308.
11. Lee J., Stinson D.R. Deterministic Key Predistribution Schemes for Distributed Sensor Networks // Lecture Notes in Computer Sci. 2005. V. 3357. Pp. 294—307.
12. Paterson M.B., Stinson D.R. A Unified Approach to Combinatorial Key Predistribution Schemes for Sensor Networks // Designs Codes and Cryptography.·2014. V. 71. Pp. 433—457.
13. Chan H., Perrig A., Song D. Random Key Predistribution Schemes for Sensor Networks // Proc. Symp. Security and Privacy. 2003. Pp. 197—213.
14. Eschenauer L., Gligor V. A Key-management Scheme for Distributed Sensor Networks // Proc. IX ACM Conf. Computer and Communications Security. ACM Press, 2002. Pp. 41—47.
15. Холл М. Комбинаторика. М: Мир, 1970.
16. Stinson D. Combinatorial Designs: Constructions and Analysis. Berlin: Springer, 2003.
17. Фролов А.Б., Клягин А О., Кочетова Н.П. Темников Д.Ю. Распределенное вычисление комбинаторных блок-схем // Проблемы теоретической кибернетики: Материалы заочного семинара XIX Междунар. конф. Казань, 2020. С. 126—129.
18. Gashkov S.B. Frolov A.B. The Complexity of Solving Low Degree Equations over Ring of Integers and Residue Rings // Moscow University Mathematics Bull. 2019. V. 74. No. 1. Pp. 5—13.
19. Гашков С.Б., Гашков И.Б. Быстрый алгоритм извлечения квадратных корней в некоторых конечных полях нечетной характеристики // Вестник Московского университета. Серия 1: «Математика. Механика». 2018. Т. 73(5). C. 8—14.
20. Волокитин М.В. Алгебраические возможности пакета Mathematica и их расширение // Вестник МЭИ. 2010. № 2. С. 114—120.
21. Гашков С.Б., Фролов А.Б., Попова Е.П. Об оценках сложности алгоритмов извлечения квадратных корней в конечных полях и в кольцах вычетов // Вестник МЭИ. 2018. № 5. С. 79—88.
22. Sage Web Site [Офиц. сайт] www.sagemath.org (дата обращения 25.09.2020).
23. Frolov A.B., Vinnikov A.M. Modeling Cryptographic Protocols Using Computer Algebra Systems // Proc. V Intern. Conf. Information Technol. Engineering Education. Moscow, 2020. Pp. 1—4.
---
Для цитирования: Фролов А.Б., Кочетова Н.П., Клягин А.О., Темников Д.Ю. Алгоритмические аспекты создания и использования ключевых пространств беспроводных сенсорных сетей на основе комбинаторных блок-схем // Вестник МЭИ. 2021. № 2. С. 108—118. DOI: 10.24160/1993-6982-2021-2-108-118.
---
Работа выполнена при поддержке: РФФИ (проект № 19-01-00294а)
#
1. Mitchell C.J., Piper C. Key Storage in Secure Networks. Discrete and Appl. Math. 1988;21:215—228.
2. Mitchell C.J. Combinatorial Techniques for Key Storage Reduction in Secure Networks. Technical Memo. Bristol: Hewlett-Packard Laboratories, 1988.
3. Dyer M., Fenner T., Frieze A., Thomason A. On Key Storage in Secure Networks. J. Cryptology. 1995;8(4):189—200.
4. Erdösh P., Frankl P., Füredi Z. Families of Finite Sets in Which no Set is Covered by the Union of Two Others. J. Combinatorial Theory. 1982;A33:158—166.
5. Erdösh P., Frankl P., Füredi Z. Families of Finite Sets in Which no Set is Covered by the Union of r Others. Israel J. Math. 1985;51:75—89.
6. Lee J., Stinson D.R. On the Construction of Practical Key Predistribution Schemes for Distributed Sensor Networks Using Combinatorial Designs. ACM Trans. Information and Syst. Security. 2008;11;2:1—35.
7. Stinson D.R., Van Trung T. Some New Results on Key Distribution Patterns and Broadcast Encryption. Designs, Codes and Cryptography. 1998;14:261—279
8. Stinson D.R., Van Trung T., Wei R. Secure Frameproof Codes, Key Distribution Patterns, Group Testing Algorithms and Related Structures. J. Statist. Plan. Infer. 2000;86;2:595—617
9. Stinson D.R., Wei R., Zhu L. New Constructions for Perfect Hash Families and Related Structures Using Combinatorial Designs and Codes. J. Combinatorial Designs. 2000;8;3:189—200.
10. Camtepe S., Yener B. Combinatorial Design of Key Distribution Mechanisms for Wireless Sensor Networks. Lecture Notes in Computer Sci. 2004;3193:293—308.
11. Lee J., Stinson D.R. Deterministic Key Predistribution Schemes for Distributed Sensor Networks. Lecture Notes in Computer Sci. 2005;3357:294—307.
12. Paterson M.B., Stinson D.R. A Unified Approach to Combinatorial Key Predistribution Schemes for Sensor Networks. Designs Codes and Cryptography.·2014;71:433—457.
13. Chan H., Perrig A., Song D. Random Key Predistribution Schemes for Sensor Networks. Proc. Symp. Security and Privacy. 2003:197—213.
14. Eschenauer L., Gligor V. A Key-management Scheme for Distributed Sensor Networks. Proc. IX ACM Conf. Computer and Communications Security. ACM Press, 2002:41—47.
15. Kholl M. Kombinatorika. M: Mir, 1970. (in Russian).
16. Stinson D. Combinatorial Designs: Constructions and Analysis. Berlin: Springer, 2003.
17. Frolov A.B., Klyagin A O., Kochetova N.P. Temnikov D.Yu. Raspredelennoe Vychislenie Kombinatornykh Blok-skhem. Problemy Teoreticheskoy Kibernetiki: Materialy Zaochnogo Seminara XIX Mezhdunar. Konf. Kazan', 2020:126—129. (in Russian).
18. Gashkov S.B. Frolov A.B. The Complexity of Solving Low Degree Equations over Ring of Integers and Residue Rings. Moscow University Mathematics Bull. 2019;74;1:5—13.
19. Gashkov S.B., Gashkov I.B. Bystryy Algoritm Izvlecheniya Kvadratnykh Korney v Nekotorykh Konechnykh Polyakh Nechetnoy Kharakteristiki. Vestnik Moskovskogo Universiteta. Seriya 1: «Matematika. Mekhanika». 2018;73(5):8—14. (in Russian).
20. Volokitin M.V. Algebraicheskie Vozmozhnosti Paketa Mathematica i Ikh Rasshirenie. Vestnik MEI. 2010;2:114—120. (in Russian).
21. Gashkov S.B., Frolov A.B., Popova E.P. Ob Otsenkakh Slozhnosti Algoritmov Izvlecheniya Kvadratnykh Korney v Konechnykh Polyakh i v Kol'tsakh Vychetov. Vestnik MEI. 2018;5:79—88. (in Russian).
22. Sage Web Site [Ofits. Sayt] www.sagemath.org (Data Obrashcheniya 25.09.2020).
23. Frolov A.B., Vinnikov A.M. Modeling Cryptographic Protocols Using Computer Algebra Systems. Proc. V Intern. Conf. Information Technol. Engineering Education. Moscow, 2020:1—4.
---
For citation: Frolov A.B., Kochetova N.P., Klyagin A.O., Temnikov D.Yu. The Algorithmic Aspects of Creating and Using Wireless Sensor Network Key Spaces Based on Combinatorial Block Diagrams. Bulletin of MPEI. 2021;2:108—118. (in Russian). DOI: 10.24160/1993-6982-2021-2-108-118.
---
The work is executed at support: RFBR (Project No. 19-01-00294а)
