© 2002 by British Computer Society
A Hierarchical Non-interactive Key-Sharing Scheme with Low Memory Size and High Resistance against Collusion Attacks
1 Information and Systems, Institute of Industrial Science, the University of Tokyo, Komaba 4-6-1, Meguro-ku, Tokyo 153-8505, Japan Email: hanaoka@imailab.iis.u-tokyo.ac.jp 2 Information Technology R&D Center, Mitsubishi Electric Corporation, Japan 3 Department of Software and Information Systems, University of North Carolina at Charlotte, USA
Efficient ID-based key sharing schemes are desired worldwide for secure communications on Internet and other networks. The Key Predistribution Systems (KPSs) are a large class of such key sharing schemes. The remarkable property of KPSs is that in order to share the key, a participant should only input its partner's identifier to its secret KPS algorithm. Although it has many advantages in terms of efficiency, on the other hand it is vulnerable to certain collusion attacks. While conventional KPSs establish communication links between any pair of entities in a communication system, in many practical communication systems, such as broadcasting, not all links are required. In this paper, we propose a new version of KPS which is called the Hierarchical KPS. In the Hierarchical KPS, simply by removing unnecessary communication links, we can significantly increase the collusion threshold. As an example, for a typical security parameter setting, the collusion threshold of the Hierarchical KPS is 16 times higher than that of the conventional KPS while using the same amount of memory at the KPS center. The memory required by the user is even reduced by a factor $1/16$ in comparison with the conventional linear scheme. Hence, Hierarchical KPS provides a more efficient method for secure communication.