2.6 Complexity analysis

2.6.1 Optimizations analysis

The problem with TGDH is that a lot of BK messages for virtual nodes are sent. To be preicse, the number of messages sent when a node updates its BK depends on its depth in the tree. The figure 2.11 sums up how a node can manage BK messages in the TGDH protocol, which are the most important messages exchanged when the group is created.

Figure 2.11: TGDH management messages

One can clearly see that the protocol is simple, but the problem with TGDH is that a lot of BK messages for virtual nodes are sent. The number of messages sent when a node updates its BK depends on its depth in the tree. Let us consider n mathend000# nodes in the group. In TGDH, the depth of the tree is given by the formula h = E(log2(n)) + 1 mathend000# and h mathend000# BK keys have to be rebuilt (in order to get the tree root). Another problem is that as all intermediate nodes are virtual, so one of the leaves has to propagate these messages. The average number of BK keys a node should manage is $\sum_{{i=1}}^{{h_s-1}}$(i ^. (1/2)ⁱ⁺¹) + h_s ^. (1/2)^h mathend000#.

The optimization we propose with S-TGDH (illustrated by the figure 2.12)helps to reduce the number of messages sent during a BK key update process, and also the number of messages sent by each node. As for TGDH, the number of messages sent during a key removal depends on the depth of the considered node. But contrary to TGDH, all the intermediate nodes are not obligatory virtual. Ideally, we have no virtual node. Thus, the average number of sent messages is h_s = E(log2(${\frac{{n}}{{2}}}$ + 1)) mathend000# and the other interesting part is that a node may have to take into account only one mathend000# BK message, if the parent is not a virtual node.

Figure 2.12: S-TGDH management messages

We also notice that the number of messages associated to a BK removal process depends on an implementation choice: either we can use a multicast process if the routing protocol allows it, or we can use unicast messages. Depending on this choice, the number of messages sent by the source and the intermediate nodes is quite variable. As it does not change the comparison between TGDH and S-TGDH, we choose to compare the number of BK keys that have to be changed and the average per node.

2.6.2 Algorithms complexity

In order to estimate the algorithm cost of each sub-protocol, we make the assumption that an optimal messages propagation algorithm can be chosen (see previous section). The results are summed up in the tables 2.3 and 2.4.

Group creation

The number of messages sent during the creation process (ie the authentication phase) is 4 ^. (n - 1) mathend000#, where n mathend000# is the number of nodes if we consider unreliable network communications ( 3 ^. (n - 1) mathend000# otherwise). Comparing to the 3 ^. (n - 1) mathend000# messages suggested by TGDH, the process produces an increase of 33% in the worst case though our approach provides a fully authenticated protocol. Moreover, as explained below, this overhead occurs only during the group creation process and is compensated by the optimisations made in the other processes. All the algorithm complexity is supported by the initiator (as other nodes only have to check the challenge from the initiator node and to decrypt messages).
For the initiator node, the complexity is linked to the problem where to insert a node in the graph. With the implementation we propose, the complexity is minimal: the maximal cost is obtained if no virtual node is caught during the sub-tree analysis. We then have h ^. single$\_cost$ mathend000#. The global cost is $\sum_{{i=0}}^{{n}}$E(log2(i + 1)) mathend000# which give a complexity of n ^. log2(n) mathend000#.

Group initiation

In this case, the number of nodes that get a BK message is maximal, since all the leaves send their BK keys. So we have n_leaf = 2^H_s-1 = ${\frac{{n+1}}{{2}}}$ mathend000# leaves at a depth H_s = E(log2(n + 1)) mathend000#. The global cost is then n_leaf ^. $\sum_{{i = 2}}^{{H_s}}$((2ⁱ -2) ^. BKcost) mathend000# for the BK messages cost, and (2^h_s-1 -1) ^. Kcost mathend000# for the K messages cost where h_s = E(log2(${\frac{{n}}{{2}}}$ + 1)) mathend000# is the mean depth for the node to take into account. (for TGDH, only the leaf receives BK messages , so cost = n ^. $\sum_{{i = 1}}^{{H_t-1}}$((2i - 1) ^. BKcost mathend000#))

The different algorithm costs are evaluated according to our implementation of S-TGDH. Moreover, the algorithm complexity in S-TGDH is quite the same as in TGDH as the additional checks on S-TGDH only happened on the copath, which makes them fast.

• Kcost: SC ^. O(log2(n/2)) mathend000#, mainly in order to build its public key
• BKcost: SC ^. O(n) + SC ^. O(log2(n/2)) mathend000#, mainly to create the parent private key, and perform checks

SC (Security_Cost) represents the cost to create the key.

Updating a key

The number of nodes that get a BK message is $\sum_{{i = H_s-h_s+2}}^{{H_s}}$(2ⁱ - 2) mathend000# where H_s = E(log2(n + 1)) mathend000#, as mentioned before (the sum on i mathend000# is due to the removal of the intermediate BK keys, until we reach the tree root). The cost for the K messages is h_s ^. Kcost mathend000#.

2.6.3 Authentication overhead

With S-TGDH, all the messages are authenticated. The overhead is produced by the signature attached to each message, which is in fact given by the formula signature = hash((message)_key) mathend000#. The hash function, as for other cryptographic protocols, generates an output of constant length. For instance, the commonly used md5 hash function produces an output of 128 bits.

By default, the packets maximum size is the same as for all the Ethernet protocols: 1500 bytes. If we consider a transfer that tries to use as many payloads as possible, we got a decrease of 3% of the performance (using a 256 bits length signature). But very often, the packets do not have the maximum size. Thus, the performance decreases come only from the time spent to send the packets. For the WiFi, it takes 250 $\mu$ mathend000#s with 1 mbps (slowest speed) to send the signature.

Another impact of the packet's encryption is the time needed to decrypt it. Fortunately, only the recipient has to decrypt the packet, as the addresses are not encrypted. As we use a symmetric cryptographic process, the deciphering process is quite fast.

2.6.4 Graphical comparisons

The following graphics illustrate the different results we described in the previous sections and compare them with the one we got for TGDH. We can see that both protocols produce the same cost, but S-TGDH generates less messages and distributes equitably the cost on each node.

Table 2.3: Authentication cost

	messages	Initiator	other nodes
TGDH	3 . (n - 1) mathend000#	O(n . log2(n)) mathend000#	-
S-TGDH	4 . (n - 1) mathend000#	O(n . log2(n)) mathend000#	1 challenge check
		& n challenges checks

Table 2.4: Group management cost

	BKmessages cost	Kmessages cost
TGDH creation	BKcost . O(n . log2(n)2) mathend000#	Kcost . O(n) mathend000#
TGDH update	BKcost . O(log2(n)2) mathend000#	Kcost . O(log2(n)) mathend000#
S-TGDH creation	BKcost . O(n2) mathend000#	Kcost . O(n) mathend000#
S-TGDH update	BKcost . O(n) mathend000#	Kcost.O(log2(n)) mathend000#