Structural Properties of Cryptographic Sequences - Computational Intelligence in Security for Information Systems - page 155

Table 2. Multi-group secure multicast schemes comparison

Storage overhead Communications overhead

Key Server Member Join Leave

Multicast Unicast Multicast

MG[26][27] O (log n ) O ( Mn ) O ( d log n ) O ( Md log n ) O ( Md log n )

O ( d

HAC[28]

d − 1 Mn 0 ) O (log n 0 )

0 O (1) O ( d log n 0 )

Zhang et al.[29] O ( n ) O (1) 0 O ( M ) O ( M )

(a) A key hierarchy tree (b) A multi-group tree

Fig. 1. Tree hierarchies of keys

the MG scheme, appears in [26] and [27]. Due to the intricate resultant network,
single re-key operations become significantly complex in terms of overhead and
therefore batch re-keyings are used. The HAC scheme [28] reduces both band-
width and communications overhead by improving the multi-tree arrangement
and using one-way functions. Both schemes are statefull. Zhang et al. present
a stateless protocol based on the bilinear Die-Hellman Problem [29]. Table 2
shows a comparison of [27], [28] and [29] in big − O notation terms. M is the

number of groups/trees and n 0 the average number of members in a subgroup.
Other multi-group schemes are [30] and [31]. To the best of our knowledge, it is
the first time this kind of schemes is included in a survey.

4 Self-healing Schemes for Ad-Hoc Networks

Last decade advances on smart devices have led to the development and massive
use of MANETS: mobile ad-hoc networks with unreliable links, limited band-
width, highly dynamic topologies and unpredictable member behavior (there is
no guarantee that members will be online at a given time or for a given period
of time). What's more, most of the devices used in these networks have low
computational capacities given their need to manage energy eciently. Due to
the specific restrictions that MANETS impose, re-keying is usually performed
on a batch manner. An interval between two batch re-keys is called a session .
Zhu et al. present one of the earliests schemes in [32]. They add reliability and
self-healing to a traditional scheme in order to obtain m-recoverability at a low
additional bandwidth overhead. m-recoverability implies that a member may still
recover the current keying material after missing a maximum of m key updates.
An important family within self-healing schemes are those based on polyno-
mials and secret sharing techniques. The scheme in [33] by Staddon et al. also