In recent years, the Internet has become the most important infrastructure in the information society. Until now, a client-server system such as e-mail or WWW that is offered by a fixed service provider has played an important role. However, in such client-server systems, it is impossible to continue to provide services when the servers are halted by some failure. For this reason, a pure Peer-To-Peer (P2P) network, in which a user also acts as a provider, has lately attracted considerable attention as a new commercial infrastructure, because it enables its users to provide a service without a dedicated server. However, it is difficult to provide security on a pure P2P network because each terminal on the network has the same privilege.