{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:19:02Z","timestamp":1750306742589,"version":"3.41.0"},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2014,12,18]],"date-time":"2014-12-18T00:00:00Z","timestamp":1418860800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100004281","name":"Narodowe Centrum Nauki","doi-asserted-by":"publisher","award":["DEC-2011\/01\/B\/ST1\/03943"],"award-info":[{"award-number":["DEC-2011\/01\/B\/ST1\/03943"]}],"id":[{"id":"10.13039\/501100004281","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Sen. Netw."],"published-print":{"date-parts":[[2015,3,2]]},"abstract":"<jats:p>A key distribution scheme for wireless sensor networks based on a system of dynamic, pairwise keys is considered. In the scheme, each pair of communicating nodes shares pairwise symmetric keys and changes them at every transmission using a set of hashing functions. This article examines security aspects of the protocol. The most important issue is to ensure that it is infeasible for an adversary to restrict exhaustive key search to a subset of the keyspace. This desirable property holds if, after a small number of random key transitions, the distribution of keys among the nodes is close to uniform. The article provides a rigorous mathematical analysis of the distribution of keys and supplements it with experimental results. The problem is reduced to the question of determining mixing time and the stationary distribution of a random walk on a random digraph. It is shown that with probability close to 1, the mixing time is of small order and the fluctuations of the distribution are limited. This ensures the ongoing security of the protocol by making the communications forward secure and protecting against node compromise.<\/jats:p>","DOI":"10.1145\/2637482","type":"journal-article","created":{"date-parts":[[2014,12,19]],"date-time":"2014-12-19T13:38:51Z","timestamp":1418996331000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Mixing in Random Digraphs with Application to the Forward-Secure Key Evolution in Wireless Sensor Networks"],"prefix":"10.1145","volume":"11","author":[{"given":"Marek","family":"Klonowski","sequence":"first","affiliation":[{"name":"Wroc\u0142aw University of Technology, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Miros\u0142aw","family":"Kuty\u0142owski","sequence":"additional","affiliation":[{"name":"Wroc\u0142aw University of Technology, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Micha\u0142","family":"Ren","sequence":"additional","affiliation":[{"name":"Adam Mickiewicz University, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Katarzyna","family":"Rybarczyk","sequence":"additional","affiliation":[{"name":"Adam Mickiewicz University, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,12,18]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Reversible Markov Chains and Random Walks on Graphs. Retrieved","author":"Aldous David","year":"2014","unstructured":"David Aldous and James A. Fill . 2002&plus; . Reversible Markov Chains and Random Walks on Graphs. Retrieved August 17, 2014 , from http:\/\/www.stat.berkeley.edu\/&sim;aldous\/RWG\/book.html. David Aldous and James A. Fill. 2002&plus;. Reversible Markov Chains and Random Walks on Graphs. Retrieved August 17, 2014, from http:\/\/www.stat.berkeley.edu\/&sim;aldous\/RWG\/book.html."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1002\/0471722154"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/1025124.1025893"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/168588.168596"},{"volume-title":"Random Graphs","author":"Bollob\u00e1s B\u00e9la","key":"e_1_2_1_5_1","unstructured":"B\u00e9la Bollob\u00e1s . 1985. Random Graphs . Academic Press . B\u00e9la Bollob\u00e1s. 1985. Random Graphs. Academic Press."},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Society (INFOCOM\u201905)","author":"Chan Haowen","year":"2005","unstructured":"Haowen Chan and Adrian Perrig . 2005 . PIKE: Peer intermediaries for key establishment in sensor networks . In Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Society (INFOCOM\u201905) . 524--535. Available at http:\/\/www.cs.cmu.edu\/&sim;haowen\/. Haowen Chan and Adrian Perrig. 2005. PIKE: Peer intermediaries for key establishment in sensor networks. In Proceedings of the 24th Annual Joint Conference of the IEEE Computer and Communications Society (INFOCOM\u201905). 524--535. Available at http:\/\/www.cs.cmu.edu\/&sim;haowen\/."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.5555\/829515.830566"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.06.001"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2011.11.001"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF00124891"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/586110.586117"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1002\/9781118032718"},{"key":"e_1_2_1_14_1","first-page":"135","article-title":"Remarks on a general model of a random digraph","volume":"65","author":"Jaworski Jerzy","year":"2002","unstructured":"Jerzy Jaworski and Zbigniew Palka . 2002 . Remarks on a general model of a random digraph . Ars Combinatoria 65 , 135 -- 144 . Jerzy Jaworski and Zbigniew Palka. 2002. Remarks on a general model of a random digraph. Ars Combinatoria 65, 135--144.","journal-title":"Ars Combinatoria"},{"key":"e_1_2_1_15_1","first-page":"111","article-title":"On a random digraph","volume":"33","author":"Jaworski Jerzy","year":"1987","unstructured":"Jerzy Jaworski and Ipe H. Smit . 1987 . On a random digraph . Annals of Discrete Mathathematics 33 , 111 -- 127 . Jerzy Jaworski and Ipe H. Smit. 1987. On a random digraph. Annals of Discrete Mathathematics 33, 111--127.","journal-title":"Annals of Discrete Mathathematics"},{"key":"e_1_2_1_16_1","series-title":"Lecture Notes in Computer Science","volume-title":"Cryptology and Network Security","author":"Klonowski Marek","unstructured":"Marek Klonowski , Miros\u0142aw Kuty\u0142owski , Micha\u0142 Ren , and Katarzyna Rybarczyk . 2007. Forward-secure key evolution in wireless sensor networks . In Cryptology and Network Security . Lecture Notes in Computer Science , Vol. 4856 . Springer , 102--120. Marek Klonowski, Miros\u0142aw Kuty\u0142owski, Micha\u0142 Ren, and Katarzyna Rybarczyk. 2007. Forward-secure key evolution in wireless sensor networks. In Cryptology and Network Security. Lecture Notes in Computer Science, Vol. 4856. Springer, 102--120."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.v34:3"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/11836810_19"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 2005 Symposium on VLSI Circuits. 216--219","author":"Tiri Kris","year":"2005","unstructured":"Kris Tiri , David Hwang , Alireza Hodjat , Bo-Cheng Lai , Shenglin Yang , Patrick Schaumont , and Ingrid Verbauwhede . 2005 . AES-based cryptographic and biometric security coprocessor IC in 0.18-um CMOS resistant to side-channel power analysis attacks . In Proceedings of the 2005 Symposium on VLSI Circuits. 216--219 . Available at http:\/\/www.emsec.ee.ucla.edu\/pubs.html. Kris Tiri, David Hwang, Alireza Hodjat, Bo-Cheng Lai, Shenglin Yang, Patrick Schaumont, and Ingrid Verbauwhede. 2005. AES-based cryptographic and biometric security coprocessor IC in 0.18-um CMOS resistant to side-channel power analysis attacks. In Proceedings of the 2005 Symposium on VLSI Circuits. 216--219. Available at http:\/\/www.emsec.ee.ucla.edu\/pubs.html."}],"container-title":["ACM Transactions on Sensor Networks"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2637482","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2637482","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:28:17Z","timestamp":1750231697000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2637482"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12,18]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2015,3,2]]}},"alternative-id":["10.1145\/2637482"],"URL":"https:\/\/doi.org\/10.1145\/2637482","relation":{},"ISSN":["1550-4859","1550-4867"],"issn-type":[{"type":"print","value":"1550-4859"},{"type":"electronic","value":"1550-4867"}],"subject":[],"published":{"date-parts":[[2014,12,18]]},"assertion":[{"value":"2013-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-12-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}