Abstract
Execution of a protocol in a wireless sensor network may reveal some information about its size. For example, the time required to elect a leader or establish size approximation using the most popular protocols is strongly correlated with the number of participating stations. This property may be very undesirable in many natural scenarios, like e.g., the military area of applications.
This paper considers how much information about the network size a passive adversary eavesdropping on the communication channel can learn from the protocol execution. We formalize this problem in a general form (modeling the system as a multiple access channel with various feedbacks) and then present some practical results for the popular beeping model. In particular, we demonstrate how to construct a universal method that provably conceals the exact number of participating stations. Moreover, we explain the limitations of the presented approach. Finally, we show that in the case of some particular problems, the size-hiding property can be archived without any additional activities.
The paper is supported by Polish National Science Center NCN grants 2018/29/B/ST6/02969.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
Note that \(\mathcal {S}\) can represent different sets of states. We are not limited to a two-state beeping model.
- 2.
That is, it is more difficult to mask the difference between executions when comparing 2 with 22 stations than when comparing 102 with 122 stations.
- 3.
Note that it can be applied in many arrangements distinct from the beeping model as well.
- 4.
Many other natural strategies can be considered. We have considered several of the most natural approaches, and however surprisingly, they give similar results to BS, so we have picked the most elegant one.
- 5.
An adjective ”shifted” is due to a fact that product starts with \(i=1\) instead of \(i=0\) as it is usually defined (in both versions, the product has m factors). Also predominantly, \(h>0\), however we allow \(h\le 0\).
References
Klonowski, M., Syga, P.: Enhancing privacy for ad hoc systems with predeployment key distribution. Ad Hoc Netw. 59, 35–47 (2017)
Kardas, M., Klonowski, M., Syga, P.: How to obfuscate execution of protocols in an ad hoc radio network? Ad Hoc Netw. 84, 90–106 (2019)
Dwork, C., McSherry, F., Nissim, K., Smith, A.D.: Calibrating noise to sensitivity in private data analysis. Theory Crypt. 3876, 265–284 (2006)
Chan, T.-H.H., Shi, E., Song, D.: Privacy-preserving stream aggregation with fault tolerance. In: Keromytis, A.D. (ed.) FC 2012. LNCS, vol. 7397, pp. 200–214. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-32946-3_15
Dwork, C., Roth, A.: The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sci. 9, 211–407 (2014)
Brandes, P., Kardas, M., Klonowski, M., Pajak, D., Wattenhofer, R.: Fast size approximation of a radio network in beeping model. Theoret. Comput. Sci. 810, 15–25 (2020)
Brandes, P., Kardas, M., Klonowski, M., Pająk, D., Wattenhofer, R.: Approximating the size of a radio network in beeping model. In: Suomela, J. (ed.) SIROCCO 2016. LNCS, vol. 9988, pp. 358–373. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-48314-6_23
Chlebus, B.S., De Marco, G., Talo, M.: Naming a channel with beeps. Fund. Inform. 153, 199–219 (2017)
Andriambolamalala, N.A., Ravelomanana, V.: Energy efficient naming in beeping networks. Ad-Hoc, Mobile, Wirel. Netw. 11803, 355–369 (2019)
Altman, T., Aldawsari, L.S.: Naming processes in multichannels with beeps in the weak model. Intell. Comput. 283, 118–132 (2022)
Bojko, D., Grining, K., Klonowski, M.: Probabilistic counters for privacy preserving data aggregation. In: CoRR, vol. 2003.11446 (2020)
Cornejo, A., Kuhn, F.: Deploying wireless networks with beeps. Distrib. Comput. 6343, 148–162 (2010)
Bhaskar, R., Bhowmick, A., Goyal, V., Laxman, S., Thakurta, A.: Noiseless database privacy. In: Lee, D.H., Wang, X. (eds.) ASIACRYPT 2011. LNCS, vol. 7073, pp. 215–232. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25385-0_12
Grining, K., Klonowski, M.: Towards extending noiseless privacy: dependent data and more practical approach. AsiaCCS 2017, 546–560 (2017)
Jacquet, P., Milioris, D., Mühlethaler, P.: A novel energy efficient broadcast leader election. MASCOTS 2013, 495–504 (2013)
Cichon, J., Kapelko, R., Markiewicz, D.: On leader green election. CoRR, vol. 1605.00137 (2016)
Eschenauer, L., Gligor, V.D.: A key-management scheme for distributed sensor networks. In: ACM CCS, pp. 41–47 (2002)
Li, L., et al.: A secure random key distribution scheme against node replication attacks in industrial wireless sensor systems. IEEE Trans. Ind. Inform. 16, 2091–2101 (2020)
Klonowski, M., Kutyłowski, M., Ren, M., Rybarczyk, K.: Forward-secure key evolution in wireless sensor networks. In: Bao, F., Ling, S., Okamoto, T., Wang, H., Xing, C. (eds.) CANS 2007. LNCS, vol. 4856, pp. 102–120. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-76969-9_7
Li, L., et al.: Key pre-distribution scheme with join leave support for SCADA systems. Int. J. Crit. Infrastruct. Prot. 24, 111–125 (2019)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Bojko, D., Klonowski, M., Marciniak, M., Syga, P. (2023). On Size Hiding Protocols in Beeping Model. In: Cano, J., Dikaiakos, M.D., Papadopoulos, G.A., Pericàs, M., Sakellariou, R. (eds) Euro-Par 2023: Parallel Processing. Euro-Par 2023. Lecture Notes in Computer Science, vol 14100. Springer, Cham. https://doi.org/10.1007/978-3-031-39698-4_35
Download citation
DOI: https://doi.org/10.1007/978-3-031-39698-4_35
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-39697-7
Online ISBN: 978-3-031-39698-4
eBook Packages: Computer ScienceComputer Science (R0)