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

achieves m-recoverability. It combines the transmission to members of an ini-
tial set of shares with the transmission of additional, redundant shares at every
update round. With that information, members are able to recover a given key
even if they miss its corresponding update. The price for that is an increase in
bandwidth overhead, up to O ( mt 2 ): m is the maximum number of updates a
member can miss, while t is both the polynomial degree and the minimum num-
ber of ex-members that must collude in order to break the system. The protocol
presented in [34] by Liu et al. goes further by reducing the bandwidth overhead
to O ( tj ). The value j is the current session within the interval m :notethat
the re-key information transmitted is a multiple of j and therefore increases de-
pending on the current session, to a maximum of m times. More recent schemes
involve the use of one way functions. The scheme in [35] by Dutta et al. achieves
a better bandwidth usage, constant member storage requirements, presumably
unconditional security and is not restricted to only m sessions recoverability.
However, Du et al. reveal security weaknesses of [35] and propose an improved,
collusion-free protocol [36]. Finally, the same authors propose another constant
storage scheme [37] but they do not guarantee its resistance to collusion.
Table 3 compares the schemes found in [33], [34], [35] and [37], focusing on
the storage requirements at the member and the communication overhead per
key update ( q is a large prime involved in calculations, greater than n ). Data
areexpressedintermsofbits.Giventhelimited memory space of smart devices,
constant storage requirements are desirable. As we see, Dutta et al. [35] and Du
et al. [37] offer the best results in those terms. Regarding the communication
overhead, Dutta et al. [35] shows the best results again. However, its vulnerability
to collusion attacks makes it a weak option to choose. Du et al. [37] and Liu

Table 3. Self-healing secure multicast schemes comparison

Storage at Communication Collusion Key long

member overhead resistant life-span

Staddon et al. [33] ( m − j +1) 2 log q ( mt 2 +2 mt + m + t ) log q Yes No

Liu et al. [34] ( m − j +1) log q (2 tj + j ) log q Yes No

Dutta et al. [35] 3 log q ( t +1+ j ) log q No Yes

Du et al. [37] 3 log q (3 t +2+ j ) log q Yes Yes

Table 4. Feature comparison for the different schemes reviewed

Cat. Stful/
Stless

Coll.
Res.

Rel. Keys
tree

Cat. Stful/
Stless

Coll.
Res.

Rel. Keys
tree

SL [22], 1989 1 Stless ✓ SKD [12], 2009 1 Stful ✓ ✓

GKMP [5], 1997 1 Stful ✓ EGK [20], 2010 1 Stful ✓ ✓

Cluster [21], 1997 1 Stful ✓ ✓ Naranjo [23], 2010 1 Stless ✓

LKH [6][7], 1999 1 Stful ✓ ✓ Zhang [29], 2006 2 Stless ✓ ✓ ✓

LKH+ [10], 1999 1 Stful ✓ ✓ MG [26][27], 2007 2 Stful ✓ ✓

OFCT [14], 1999 1 Stful ✓ ✓ HAC [28], 2008 2 Stful ✓ ✓

FT [18], 1999 1 Stful ✓ Staddon [33], 2002 3 Stless ✓

✓ ✓ ✓ ✓ ✓

ELK [15], 2001 1 Stful Zhu [32], 2003 3 Stless

LKH++ [11], 2002 1 Stful ✓ ✓ Liu [34], 2003 3 Stless ✓ ✓

SL+HTA[24],2002 1 Stful ✓ ✓ Dutta [35], 2007 3 Stless ✓

OFT [13], 2003 1 Stful ✓ Du [36], 2008 3 Stless ✓ ✓

Ku [17], 2003 1 Stful ✓ ✓ Du [37], 2009 3 Stless ✓