Varaiable Member Group Authentication Protocol using Trivariate Polynomials

Varaiable Member Group Authentication Protocol using Trivariate Polynomials

Suresh Grandhi

Research Scholar, Dept of CSSE

A U College of Engineering, Andhra University Vishakapatnam, India

P S Avadhani

Professor, Dept of CSSE

A U College of Engineering, Andhra University Vishakapatnam, India

AbstractGroup authentication is required for secure communication, which ensures that users in the group are valid. When a group user count is not fixed, group authentication has to handle the entry of new users and exit of current users from the group, if necessary. Currently, available group authentication schemes are complex in nature that require heavy computation and communication overheads. Thus, in this paper, we propose a variable number group authentication mechanism based on the Lagrange interpolation using Tri- variate polynomials. The proposed model shares secret keys to the group user and authenticates all users participating in the group using a single computation and individual users when required. The proposed scheme has a group manager (GM) authenticating all group users and also generates a group key for validating member authenticity. GM is responsible for authenticating and validating each user in the group. GM takes care of members entry and exit from the group. The proposed scheme also handles backward and forward confidentiality during the group conversation. The security analysis of our scheme guarantees Forward Secrecy, Backward Secrecy, Integrity, Confidentiality and Availability.

Keywords Group Authentication; Variable Group Members; Lagrange Interpolation; Tri-variate Polynomials; Group communication.

1. INTRODUCTION

   In group communication, all the users must be authenticated and verified. Secure communication applications must provide user authentication and group key creation as essential services. User authentication process helps in identifying the participating members. Group key is used by the group for securing the group conversations. There are two standard authentication approaches, 1) Knowledge based [1,2] and 2) key based authentication schemes. [3,4] Knowledge based approach has security concerns [5]. User tendency is to use easy and familiar passwords. Simple and familiar passwords are easily decoded by hackers. Public key and Private Key based authentication require a valid certificate authority to provide authenticated public keys. Also, the key exchange process is complex and process-intensive approach. Performance is the most critical factor of key based authentication. A better and easy scheme is to be developed for securing Group Communication.

   User validation and securing group communication are the two essential aspects of any group conversation. Group communication is secure only if it validates all the users and protect the entire group conversation. All the members of the group must be authenticated in secure group communication. George Thomas et al. [6] proposed a method that uses a one- time session key for each group along with individual security. USB based key is used by individual users to

   increase security further. This process uses Shamirs [12] famous secret sharing method to create individual shares for all the group users, and Lagrange Interpolation method to construct individual member key share.

   Distribution of shared secret keys for all the group users is called as Key establishment process [14]. Secret keys are used to secure the messages transmitted during the communication and keeping the integrity of them. Key Agreement and Key Transfer protocols are the two prominent key establishment protocols.

   Key Generation Center (KGC) plays a vital role in Key transfer protocols. KGC chooses a group key for communication among the group members during the group initialization process. Key agreement protocol uses public keys to create a group key. Group key works as a session key for the communication among the group members. Our proposed scheme addresses the establishment of a session key for group communication.

   During registration process, KGC uses another secret key to encrypt session keys. [7] Vijaya Lakshmi et al. proposed a key transfer protocol that uses secret sharing scheme for authentication. Group key is transmitted by KGC to authorized group members. Group key cannot be accessed by unauthorized users. They claim that their scheme is information-theoretically secure. Transportation of group key is done based on authentication.

   KGC acts as a trusted party in Group key transfer protocol. Also, it creates and transfers the group key to all the members in a secure manner. KGC registers all the users and subscribes them for key distribution. KGC is responsible for keeping track of all the registered users and delete inactive users. KGC sends a secret key to all the users during registration process. KGC uses encrypting methods to send the secret keys to all the users. Message checksum is also calculated and shared during the group authentication. A computationally secure encryption algorithm is used for group key transmission. Harn

   [8] proposed a secret sharing protocol in place of encryption algorithm.

   Designing a Group key scheme to deliver messages to the group users securely is required for group communication. Any group communication protocol should handle registering users, keeping track of them, adding new users, exiting current users and securing the communication among the group users. The proposed mechanism is an extension to the Group Authentication Scheme defined by Shi et al. [9]. In their scheme, they defined Group authentication method that works for fixed group size. Our scheme is extended to a variable number of users. Also, our method is extended to handle issues with Lagrange Interpolation errors. As part of the

   proposed scheme, Lagrange Interpolation and trivariate polynomials are used to generate key shares to be distributed among the users, and these shares along with Lagrange Interpolation basis values are used to verify the group users.

2. METHODOLOGY
   1. Lagrange Interpolation

      Lagrange Interpolation polynomials are used for polynomial interpolation. It is a method for finding the equation corresponding to a curve having some data points.

      Given points, with distinct x coordinates

      , find a of degree n, which passes through all points. The following is the Lagrange Interpolation function .

      Where is given by:

      It is often represented in binary form as

      . (2)

      Equation (1) can be also be expressed as follows.

      (3)

      When x = 1 and z = 1, equation (3) becomes a polynomial of as given below.

      (4)

      And when y = 1 and z = 1, equation (3) becomes a polynomial of x as given below.

      (5)

      When , = 1.

      When , = 0.

      Fig. 1. Polynomial Passing through all points.[10]

      Consider indicate four points respectively. The

      four lines p1, p2, p3 and p4 denote the scaled basis

      polynomials respectively. A black dotted line passes through all four points, that combines all the four basis polynomials.

   2. Polynomial of three variables (Trivariate)

      A Trivariate Polynomial of degree n is a polynomial in three variables x, y, z and has the following form.[13]

      (1)

      And when x = 1 and y = 1, equation (3) becomes a polynomial of z as given below.

      (6)

      Thus, in equations (4), (5) and (6) the degree of polynomials , and are between 1 and n.

      When x = y = z, the polynomial in equation (3) is transformed as.

      (7)

      When x = y = z = 1, the polynomial is the sum of all coefficients.</>

      (8)

   3. Generation of key triplet and sharing

      A key triplet is generated by GM for each and every participating member in the group. All the n users in the system share a public value W with the remaining group users and the GM. During the group initialization process, each user j is registered by GM to include into the group. GM generates a key triplet for

      the user j using its public value and equations (4) and (5).

      Key triplet for user j is designated as:

      (9)

      During the initial process, GM registers all m users as group members. After generating the key triplets for group members, GM distributes each key triplet

      to the corresponding

      group member securely. And is a secure private value which is only known to the group member j itself. The key triplet distribution process is shown in Fig. 2.

   4. Variable number group user authentication scheme

      A group started with an initial number of users. Each user authenticates with GM using their identities. Using equation (2), GM choses a polynomial. Here, the newly generated formula must satisfy the condition that the degree should be

      equal to the number of users.

      During the registration phase, GM generates m key triplets with all the user selected public values . Each key triplet generated is delivered to the corresponding member i. The public value of GM is shared to all the users similar to any other users public value. GM calculates its own private key triplet .

      Each participating group member i calculates Lagrange basis polynomial with its key triplet and the public value . The Lagrange basis polynomial for group member j is calculated as:

      (11)

      All n group members calculate the interpolating value when .

      Each calculated user values of Lagrange basis polynomial

      along with the key triplet received from GM are transmitted back to GM

      GM validates each user by checking user-submitted key triplet and Lagrange basis polynomial against the generated key triplets by GM. Checking of key triplets satisfies minimum security requirements for user verification.

      GM uses the following formula to calculate its two values of interpolation polynomial .

      (12)

      (13)

      (14)

      After receiving all the values

      from n users of the group, GM calculates the sum of all the interpolating values at x = 1, y = 1 and z = 1 as:

      (15)

      (10)

      GM calculate using as given below.

      (16)

      (17)

      When all users are authenticated members of the group, GM can check the values of equations (15), (16), (17) and (2). The sum of all the interpolating values

      should be equal to the value of and should be equal to the value of . All these values must be equal to the total value of all the parameters as in equation

      (2).

      If the three sum results calculated by GM satisfy the following condition, then all the participated n users are valid group members [9].

      (18)

      With the selection of the trivariate polynomial along with degrees of x, y and z, it is observed that the calculated key triplets and Lagrange basis polynomial values are not satisfying the condition in equation (18). Also, the selection of higher values for W by each individual user is causing errors in the Lagrange Interpolation values thus, invalidating the condition in equation (18). A work around for this issue is to compare the user-submitted values

      by GM for checking the authenticity of group users.

      This extended verification process involves checking the sum of all the key triplets generated by GM and sent by the users. In addition to this, GM verifies each user submitted Lagrange basis polynomial value.

      The only caveat in this method is that the group authentication is done by each user instead of doing the validation for the entire group at once.

   5. Inclusion of a new user

      A new user x must be registered with GM to get included in the group. The intended user x requests inclusion into the Group. User x must send value to GM. GM generates a

      key triplet and shares it with the new user x. GM

      makes value available to all the existing users and informs the remaining users in the group about the inclusion of user x. In addition to this, GM calculates revised key triplets of all the users by including user x and distribute respective shares of the users to the corresponding member in a secured manner. All the users must recalculate their two values of Lagrange basis polynomial by including the value of the new user x as mentioned in equation (10). Also, GM must recalculate its Lagrange basis polynomial values using equation (11).

      Recalculation of key triplets ensures backward secrecy as the newly added user would not be able to access the previous key triplets.

   6. Excluding an existing user

   There are two cases of excluding a user from the group. 1) When a user x exits from the group by informing to GM and

   2) When a user x is inactive for a specific interval of time. In these two cases, GM initiates the following exit process

   GM broadcasts user x as inactive, informing all the group users about user exit. GM calculates new key triplets for all the users, excluding the exited user and shares corresponding values with them in a secured manner. All the users must recalculate their Lagrange basis polynomial values, as mentioned in equation (10) to send them back to GM. Also, GM has to recalculate its Lagrange basis polynomial as per equation (11).

   In order to maintain forward secrecy when a group user is exited, all the remaining active users along with GM should recalculate their Lagrange basis polynomial values. As the new key triplets are delivered by the GM, the exited user would not be able to access group communication any more as the exited user keys do not work anymore.

3. SECURITY ANALYSIS

   Security Analysis focuses on Confidentiality, Integrity, Availability, Backward secrecy and Forward Secrecy to verify the security of the proposed scheme.

   1. Confidentiality

      GM distributes individual key triplets securely to all the group members during the registration process. Key triplet is private information specific to each user, and it must be protected by each user. They should not share it with other users in the group. Even if any user compromises on the key triplet, the proposed model can identify the leak and the culprit user. This is done by the GM while verifying the individual key triplets during the validation process.

      Also, GM has its own key triplets which are essential in determining the group key. It is a significant information in generating group key. Group key cannot be inferred by anyone as the GM key triplet is private and confidential information. GM is responsible for keeping the confidentiality of the communication.

   2. Integrity

      If there are some attackers who modify/forge transmitted key triplets, it cannot pass the GM authentication as it wont satisfy the condition laid in formula (18). If any two members share the same key triplets to GM, then the culprit can be easily identified. GM knows the initial registration value of each user so the culprit can be identified. The proposed scheme ensures the Integrity of the system.

   3. Availability

      The proposed method works for any n users when a trivariate polynomial of degree n is used. This ensures availability.

   4. Forward Secrecy

      Forward Confidentiality ensures that the user who exits the group would not be able to access the future keys. The

      proposed scheme effectively maintains forward secrecy as the user who exits from the group cannot be able to communicate with the group any longer after the exit process is completed by GM and key triplets are re-calculated. The earlier key- triplets are not valid any more. GM excludes the user from the key triplet calculation as well as all the users would do the same by excluding the exited user.

   5. Backward Secrecy</p

      Backward Confidentiality ensures that whenever an additional user is entered to the group, the new user would not have access to the previous communication details. The proposed scheme effectively maintains backward secrecy as the user who enters into the group wont be able to gather previous communications as the user is allowed access only after GM generates new user key pairs and all the rest of the users generate the same. User entry timestamp would be used to provide access to the communication to conceal any previous communication available if any.

4. PERFORMANCE ANALYSIS

   The time complexity of each user communication is O(n) where n is the number of users in the group. In the proposed method, each user is communicating with the GM and do not involve in any communication with the other group users. The users are required to perform calculation of their Lagrange basis polynomial value whenever users are added or exited from the group. This is required for changes in group membership and ensuring security in keeping backward secrecy and forward secrecy.

5. CONCLUSION

   In this paper, a variable number of group member authentication scheme is proposed ensuring security. Malicious users can be easily identified and tracked using the proposed scheme. As our proposed scheme is designed to be flexible with the number of users, users can be added to the group or exit from the group without compromising the security of the communication involved.

6. FUTURE SCOPE

During the execution tests, it is observed that the proposed scheme works with a higher number of users and with fewer

degree polynomials. Another mechanism can be devised by creating random W values for each user by GM itself. This allows, GM to have a set of pre-defined verified polynomials of lesser degrees than the user count. It increases the performance as lower degree polynomial computations are used.

REFERENCES

1. 1. Yan J., Blackwell A., Anderson R., and Grant A., Password memorability and security: Empirical results, IEEE Security & Privacy Magazine, 2(5), (2004): 25-31
   2. Ku W. C., Weaknesses and drawbacks of a password authentication scheme using neural networks for multi-server architecture, IEEE Transactions on Neural Networks, 16(4), (2005): 1002-1005
   3. Downnard I., Public-key cryptography extensions into Kerberos,

      IEEE Potentials, 21(5, (2002)): 30-34

   4. Ren K., Yu S., Lou W., and Zhang Y., Multi-user broadcast authentication in wireless sensor networks, IEEE Transactions on Vehicular Technology, 58(8) (2009): 4554-4564
   5. Lein Harn and Changlu Lin, AN EFFICIENT GROUP AUTHENTICATION FOR GROUP COMMUNICATIONS, International Journal of Network Security & Its Applications, Vol.5,

      No.3, May 2013

   6. George Thomas, lashim lamaludheen K, Levin Sibi, Maneesh P and Mufeedh, A Novel Mathematical Model for Group Communication with Trusted Key Generation and Distribution Using Shamir’s Secret Key and USB Security, IEEE ICCSP 2015 conference
   7. Vijaya Lakshmi Pandranki, N. Krishna, Secure Group Key Transfer Protocol Based on Secret Sharing, International Journal of Computer Science and Information Technologies, Vol. 3 (4), 2012:4712 – 4717
   8. Lein Harn and Changlu Lin, Authenticated Group Key Transfer Protocol Based on Secret Sharing, IEEE TRANSACTIONS ON COMPUTERS, VOL. 59, NO. 6, JUNE-2010: 842-846
   9. Shi Li, Inshil Doh, Kijoon Chae, A Group Authentication Scheme based on Lagrange Interpolation Polynomial, 10th International Conference on Innovative Mobile and Internet Services in Ubiquitous Computing, 2016: 386:389
   10. https://en.wikipedia.org/wiki/Lagrange_polynomial
   11. L. Harn, Group Authentication, IEEE Trans. Computers, vol. 62, no. 9, Sep-2013:1893-1898
   12. A. Shamir, How to Share a Secret, Communication ACM 22,11, Nov. 1979:612-613.
   13. https://en.wikipedia.org/wiki/Polynomial
   14. Lein Harn, Group Authentication, IEEE Transaction on Computers, Vol. 62, No. 9, Sep-2013:1893-1898
   15. Chin-Chen Chang, Lein Harn, and Ting-Fang Cheng, Polynomial- based Key Management for Secure Intra-Group and Inter-Group Communication, International Journal of Network Security, Vol.16, No.2, Mar-2014:143-148.