Evolutionary Design of Message Efficient Secrecy Amplification Protocols
Tobias Smolka, Petr Svenda, Lukas Sekanina, and Vashek Matyas
{xsmolka,svenda,matyas}@fi.muni.cz, sekanina@fit.vutbr.cz
Masaryk University, Faculty of Informatics, Czech Republic
Brno University of Technology, FIT, IT4Innovations Centre, Czech Republic

Abstract: Secrecy amplification protocols are mechanisms that can significantly improve security of partially compromised wireless sensor networks (e.g., turning a half-compromised network into the 95% secure one). The main disadvantage of existing protocols is a high communication overhead increasing exponentially with network density. We devise a novel family of these protocols exhibiting only a linear increase of the communication overhead. The protocols are automatically generated by linear genetic programming (LGP) connected to a network simulator. After a deep analysis of various characteristics of this new family of protocols, with a special focus on the tuning of LGP parameters, new and better group-oriented protocols are discovered by LGP. A multi-criteria optimization is then utilized to further reduce the communication overhead down to 1/2 of the original amount while maintaining the original fraction of secure links.

Paper download: Smolka_eurogp_2012.pdf
Slides download: EuroGP_120411_final.pdf
  title={Evolutionary Design of Message Efficient Secrecy Amplification Protocols},
  author={Smolka, T. and \v{S}}venda, P. and Sekanina, L. and Maty{\'a}{\v{s}}, V.},
  booktitle={Proceedings of the 15th European Conference on Genetic Programming, EuroGP 2012, LNCS 7244},

Used simulator information and download: S3 Sensor Security Simulator
Raw data from experiments for download: BOINC workunits (use 'demo' as login name and 'eurogp' as password)

OpenPGP key : 0x89CEB31C