Security Analysis and Extensions of the PCB Algorithm for Distributed Key Generation

摘要

Broadcast is the inherent mode of communication in wireless networks that deploy omnidirectional antennas. In broadcast mode, all members who are within the communication range of the transmitting node can receive the message, thus making it resource-efficient for the sender as well as the network. However, in many applications the set of users that have access to the communication must be restricted. The use of cryptography is one way to restrict the set of members who can access the communication. When the amount of data is high, the use of symmetric keys will help reduce the computational overhead due to the encryption and decryption. However, the use of symmetric keys require that all members share the same keys for decryption. Several methods have been proposed to generate and distribute a single common key to all the members of a communicating group. Among these methods is the distributed key generation method proposed by Poovendran, Corson and Baras in PCB, which we call the PCB scheme in this paper. The PCB scheme made use of modulo arithmetic and generalized the property of one-time pad, proposed by Shannon. However, as of now there is no analysis on the security properties of the PCB method. In this work we enhance the original PCB algorithm and present the security analysis based on information theoretic techniques. We also show how to develop a computationally efficient algorithm for computing the PCB keys. The organization of the chapter is as follows: we first review the one- time pad and its properties using probabilistic as well as information theoretic approaches. We then present the PCB algorithm. We provide detailed analysis of the PCB algorithm using probabilistic as well as information theoretic techniques. We also show how to develop computationally efficient techniques that will enable efficient calculation of the group's shared key.