Fully Resilient Non-Interactive ID-Based Hierarchical Key Agreement

Abstract

Non-Interactive Key Agreement (NIKA) is a cryptographic primitive which allows two parties to agree on a shared secret key without any interaction. Identity-based Non-Interactive Key Agreement (ID-NIKA) allows each party to compute shared secret key using its own secret key and the peer’s identity. ID-NIKA can be used to establish shared secret keys in ad-hoc networks using minimal battery power and communication.

Mobile Ad-hoc NETwork (MANET) is a network of mobile and moderately resource constrained devices communicating through a wireless medium. Examples of standard MANET devices are laptops, cellphones etc. Due to the inherent characteristics like mobility, dynamic topology and lack of centralized infrastructure, MANETs face some serious security issues. We are particularly interested about ID-NIKA in MANETs. This is of crucial interest for secure communication between two nodes in MANETs.

In 2008, Gennaro et al. introduced a scheme called Hybrid Hierarchical Key Agreement Scheme (HH-KAS). HH-KAS uses subset based key agreement scheme at the non-leaf levels and a key agreement scheme due to Sakai et al. (referred as SOK-KAS) at the leaf level. HH-KAS is (i) non-interactive, (ii) identity-based, (iii) hierarchical and (iv) fully resilient against node compromises at leaf level and resilient against node compromises upto certain threshold values in non-leaf levels. Thus one can say that HH-KAS is partially resilient against node compromises. In their paper the authors claim that there is no key agreement scheme for MANETs in the literature, with all above four properties. This was motivated as an interesting open problem in this area.

Guo et al. proposed a scheme known as Strong Key Agreement Scheme (SKAS) in 2011. The authors claimed it as a potential solution to the open problem posed by Gennaro et al. in their work. However, in 2014, Zhu et al. showed a concrete attack on SKAS. This attack makes SKAS practically useless for real life applications.

Our main contribution is a hybrid scheme using two already existing schemes. Our scheme uses a deterministic key pre-distribution scheme by Lee and Stinson termed as Basic Id One-way function Scheme (BIOS) at level 1 (where root is at level 0). Beyond level 1, we use SOK-KAS for key agreement. We refer our scheme as BIOS-SOK key agreement. BIOS and SOK schemes satisfy properties (i), (ii) and (iv) but none of them is hierarchical in nature. In our work we have made an amalgam of both schemes which is hierarchical in nature. Thus, BIOS-SOK scheme satisfies (i), (ii), (iii) and is also fully resilient against arbitrary number of node compromises at any level.

BIOS-SOK scheme also possesses the benefits of low space requirement, low shared key computation time and better scalability for many real-life applications when compared with the scheme of Gennaro et al. In HH-KAS, the key agreement is carried out only at the leaf level. In BIOS-SOK scheme, any two nodes in the hierarchy (at same or different levels) can compute shared secret key. We also provide a rigorous security analysis for our scheme in a stronger security model compared to the security model used for HH-KAS.