A Probabilistic Algorithm for Secret Matrix Share Size Reduction

Conference: European Wireless 2013 - 19th European Wireless Conference
04/16/2013 - 04/18/2013 at Guildford, UK

Proceedings: European Wireless 2013

Pages: 6Language: englishTyp: PDF

Personal VDE Members are entitled to a 10% discount on this title

Pfluegel, Eckhard; Politis, Christos (Wireless, Multimedia & Networking (WMN) Research Group, Kingston University London, UK)
Panaousis, Emmanouil (Queen Mary, University of London, UK)

Secret sharing is an important tool in cryptography and has many applications for wireless networks. This paper is motivated by the need for space-efficient secret sharing schemes. We first propose a simple probabilistic algorithm which can be used, prior to secret sharing, in order to split a given secret into public and private data. The public data can be made openly available, and any specific secret sharing method can be used in order to share the private data. We then show that, combined with a previously published space-efficient single secret sharing method, this yields a novel probabilistic matrix-based online multi-secret sharing method with small expected share size. In particular, compared with other matrix-based approaches, our scheme is of similar expected computational cost but smaller share size. Finally, we report on an implementation of our method and evaluate its performance. Our algorithm could be useful to design efficient secret sharing applications for wireless networks, in particular mobile ad-hoc networks, in areas such as secure routing, data transmission or key management. Index Terms — Space-Efficient Multi-Secret Sharing, Probabilistic Algorithms