Key authentication. Key Con rmation and Key Integrity All of these are necessary to achieve resistance to active at- tacks mounted by an increasingly powerful adversary. And, xi ri Sn Sn (Mi) Kij exponentiation base; generator in group G long-term secret key of Mi random (secret) exponent 2 ZZq generated by Mi group key shared among n members Mi 's view on a group key long-term secret shared by Xx and Mj , with i 6= j as always, ironclad security must be achievable with the low- est possible cost. We now present some de nitions for the above and other terminology used in this paper. (Some of these are adapted from Xxxxxxx et al. [18]) Throughout the paper, all arithmetic is performed in the cyclic group G of prime order q which is a subgroup of ZZp for a prime p such that p = kq + 1 for some small k 2 N. p 3 can be computed by repeatedly selecting a random element b 2 ZZ and computing = b(p 1)=q mod p until 6= 1. No practical methods are known to compute partial in- formation with respect to discrete logarithms (DL) in sub- group with this setting. Most DL-based schemes have been designed using a prime order subgroup. One of the advan- tages of working in such a group is that all the elements (except the unity element) are generators of the subgroup itself. Moreover, using subgroup of prime order seems to be a prudent habit [1]; it also results in increased e ciency. When operating in subgroups it is important to take into account the attacks outlined in [1, 15]. To prevent mas- querading or leaking of (even partial) information of the secret values, each party has to verify that the (purport- edly random) values it receives are in fact elements of the subgroup.4 Note that p, q and are public and common to all users. Since they need to be generated only once (or very seldom), it is desirable to make the generation process unpredictable but veri able to prevent the selection of weak or special primes. One approach is to use the NIST method for se- lecting DSA primes as described in the FIPS 186 document [13]. In this context, the ability of an active adversary C to modify or inject messages is quite \limited". In fact, any message m can be written as m = c mod p, where is a generator of the unique cyclic subgroup of ZZp having order q and c some exponent (perhaps unknown). Later on, we will suppose that the adversary C operates on this type of elements.
Key authentication. To determine Kvo for a non-leaf node vo whose children are both leaf nodes corresponding to members Mi1 and Mi2 , the adversary E has to know rMi1 rMi2 . However, E only observes rMi1 and rMi2 . Thus, it is infeasible for E to solve the Xxxxxx-Xxxxxxx problem for rMi1 rMi2 . On the other hand, to determine Kv for a non- leaf node v which contains at least one non-leaf child node, say node 2v + 1, E has to know K2v+1 K2v+2 . However, E cannot identify K2v+1 from the blinded key messages due to the intractability of the discrete logarithm problem (i.e., given only K2v+1 xMi and xMi , it is infeasible to compute K2v+1). Therefore, A-TGDH provides key authentication.
Key authentication. Upon and after network initialization, in order to increase the communication and computation overhead of networks, a malicious node can broadcast a random key chain falsified by itself to neighboring nodes. If any keys in the falsified key chain are in common with the other side, the attacker can establish a secure link with the le- gitimate node. However, since our scheme makes use of negotiatory key to provide the authentication of key information, it guarantees the key authentication. Even if an attacker luckily generates a key shared with a legitimate node, it can not generate a session key for further communication between two nodes. This is because it has no corresponding one-way hash function. Pr(sharing at least one key) 0.6 0.5 0.4 0.3 0.1 0 r=2(MRS) r=2(SKS) r=6(MRS) r=6(SKS) r=10(MRS) r=10(SKS) 3 20 40 80 150 The size of key pool (a) Number of cases = 0% 1 Pr(sharing at least one key) 0.6 0.5 0.4 0.3 0.1 0 r=2(MRS) r=2(SKS) r=6(MRS) r=6(SKS) r=10(MRS) r=10(SKS) 3 20 40 80 150 The size of key pool
