Informatica

The invention of public-key cryptography makes many new network applications, such as electronic commerce (CE), possible. However, the widely used Internet is open and unprotected. Therefore, verifying the legitimacy of an individual's public key is very important. Most of the key authentication schemes require one or more trustworthy authorities to authenticate the key of a user. Consequently, the system security is mainly dependent on the honesty of these third parties. Unfortunately, a security solution in wide area networks (for example, the Internet) often cannot be applied to local area networks directly without any modification. Sometimes, a complete rebuild is necessary, especially for performance criteria consideration. In this paper, we propose two simple key authentication schemes that require no certification authorities for computer systems in local area networks, in which a host is responsible for user authentication and it uses a designated password authentication mechanism.

The problem we are dealing with is following. There exist certain number of nodes η, transmitting messages at random time moments. If time interval between messages transmitted by different nodes are less than some given value, a collision occurs. We can fix the collision, but we cannot determine the nodes engaged in the collision. The hierarchical decomposition of the nodes is used to resolve the collision. At every hierarchical level, a subset of nodes “suspected” as participating in the collision is divided in a certain number of groups. There is a time period given to every group, at which messages can be transmitted. This proceeds while no more collisions occurs. This paper covers the problems of selecting a number of groups, to minimize the longest collision resolution time, as well as average collision resolution time.