ID-SP-M4M scheme means ID-based series-parallel multisignature schemes for multi-messages. In this paper, we investigate series-parallel multisignature schemes for multi-messages and propose an ID-SP-M4M scheme based on pairings in which signers in the same subgroup sign the same message, and those in different subgroups sign different messages. Our new scheme is an improvement over the series-parallel multisignature schemes introduced by Doi et al.[6]-[8] and subsequent results such as the schemes proposed by Burmester et al.[4] and the original protocols proposed by Tada [20],[21], in which only one message is to be signed. Furthermore, our ID-SP-M4M scheme is secure against forgery signature attack from parallel insiders under the BDH assumption.

Cryptosystems using pairing computation on elliptic curves have various applications including ID-based encryption ([19],[29],[30] etc.). Scott [33] proposed a scaling method of security by a change of the embedding degree k. On the other hand, he also presented an efficient pairing computation method on an ordinary (non-supersingular) elliptic curve over a large prime field Fp ([34]). In this paper, we present an implementation method of the pairing computation with both of the security scaling in [33] and the efficiency in [34]. First, we will investigate the mathematical nature of the set of the paremeter r (the order of cyclic group used) so as to support many k's. Then, based on it, we will suggest some modification to the algorithm of Scott in [34] to achieve flexible scalability of security level.

Maurer and Yacobi proposed an ID-Based key distribution scheme in 1991. In this scheme, the private key for each user is generated by solving discrete logarithm problem. We examine the realizability of this scheme. We show that this scheme can be practical by appropriate parameter setting.

In 1998, Tseng and Jan proposed a lightweight interactive user identification protocol based on ID-based cryptography. Recently, Hwang et al. modified their protocol to reduce the responding and waiting time for wireless network applications. In this letter, we show that their scheme is vulnerable to impersonation attacks.

Following the developments in the use of ID-based schemes and smart cards, Yang and Shieh proposed two password authentication schemes to achieve two purposes: (1) to allow users to choose and change their passwords freely, and (2) to make it unnecessary for the remote server to maintain a directory of passwords or a verification table to authenticate users. Recently, Chan and Cheng showed that Yang and Shieh's timestamp-based password authentication scheme is insecure against forgery. In this paper, we point out that Chan and Cheng's forgery attack can not work. Thus, we further examine the security of Yang and Shieh's password authentication schemes and find that they are insecure against forgery because one adversary can easily pretend to be a valid user and pass the server's verification which allows the adversary to login to the the remote server.

In this paper we discuss how one can delegate his power to authenticate or sign documents to others who, again, can delegate the power to someone else. A practical cryptographic solution would be to issue a certificate that consists of one's signature. The final verifier checks verifies the chain of these certificates. This paper provides an efficient and provably secure scheme that is suitable for such a delegation chain. We prove the security of our scheme against an adaptive chosen message attack in the random oracle model. Though our primary application would be agent systems where some agents work on behalf of a user, some other applications and variants will be discussed as well. One of the variants enjoys a threshold feature whereby one can delegate his power to a group so that they have less chance to abuse their power. Another application is an identity-based signature scheme that provides faster verification capability and less communication complexity compared to those provided by existing certificate-based public key infrastructure.

ID-based key sharing scheme is one of the important topics in Key management, and the Key Predistiribution System (KPS) is one of the major divisions of such key sharing schemes. In KPS, in order to share a common key between the participants, one of the participants need to simply feed-in his partner's identifier value into their secret-algorithm. In contrast to its such remarkable property and its high contribution to the field of key management for digital signature, it has downsides as well. In this paper, we propose an efficient signature scheme on the KPS infrastructure that can overcome such difficulties that are faced. It is shown that if an ID-based key sharing system belonging to KPS is provided, the new digital signature scheme can be used straightforwardly. Moreover, this signature scheme is proven to be secure if the discrete logarithm is reasonably complex. There already exists other digital signature scheme which are also based on KPS, but they contain inevitable flaws: its verifier is restricted and a tamper resistant module(TRM) is required. Our method resolved these problems. In our signature scheme, it is an ensured fact that, all signatures are authenticated by any entity, which is based on the inherence behavior of key generator and not of some common key. Moreover, TRM is not required in our scheme. In order to describe our new scheme, a new concept of "one-way homomorphism" is introduced.

Efficient ID-based key sharing schemes are desired worldwide in order to obtain secure communications on the Internet and other related networks, and Key Pre-distribution System (KPS) is one of the majority of such key sharing schemes. The remarkable property of KPS, is that, user need only input the partner's identifier to the secret KPS-algorithm in order to share a key between them. Although this is just a small part of many advantages KPS has in terms of efficiency, an enormous amount of memory is always required to achieve perfect security. While the conventional KPS methods can establish communication links between any pair of entities in a communication system, in most of the practical communication environment, such as in a broadcast system, not all links will be required. In this article, we achieved a desirable method to remove the unnecessary communication links between any pair of entities in a communication system. In our scheme, required memory size per entity was just proportional to the number of entities of the partner's, while that in conventional KPS, it is proportional to the number of entities of the whole communication system. As an example, if an entity communicates with only 1/r others, the memory requirement is reduced to 1/r of the conventional KPS's. Furthermore, it was proven that the obtained memory size was optimum. Overall, our scheme confirmed greater efficiency to achieve secure communication particularly suited in large-scale networks.

As far as the knowledge of authors, the rigorous security of Okamoto-Tanaka identity-based key exchange scheme was shown in [4] for the first time since its invention. However, the analysis deals with only the passive attack. In this paper, we give several models of active attacks against the scheme and show the rigorous security of the scheme in these models. We prove several relationships among attack models, including that (1) breaking the scheme in one attack model is equivalent to breaking the RSA public-key cryptosystem and (2) breaking the scheme in another attack model is equivalent to breaking the Diffie-Hellman key exchange scheme over Zn. The difference of the complexity stems from the difference of the timing of dishonest party's sending out and receiving messages.

Credit-based electronic payment systems are considered to play important roles in future automated payment systems. Like most other types of payment systems, however, credit-based systems proposed so far generally involve computationally expensive cryptographic operations. Such a relatively heavy computational load is preventing credit-based systems from being used in applications which require very fast processing. A typical example is admission-fee payment at the toll gate of an expressway without stopping a vehicle that travels at a high speed. In this article, we propose a very fast credit-based electronic payment protocol for admission-fee payment. More specifically, we propose a payment system between a high-speed vehicle and a toll gate which uses only very simple and fast computations. The proposed system makes use of an optimized Key Pre-distribution System (or KPS) to obtain high resistance against collusion attacks.

We propose a new probabilistic ID-based non-interactive key sharing scheme that has non-separable secret-key functions and a non-separable common-key function. The proposed scheme uses the calculation over modulo-P, modulo-Q and over integer ring for realizing non-separability. This proposed scheme has a large threshold against linear attack by the collusive entities.

A key distribution system is a system in which users securely generate a common key. One kind of identity-based key distribution system was proposed by E. Okamoto. Its security depends on the difficulty of factoring a composite number of two large primes like RSA public-key cryptosystem. Another kind of identity-based key distribution system was proposed by K. Nyberg, R. A. Rueppel. Its security depends on the difficulty of the discrete logarithm problem. On the other hand, Koblitz and Miller described how a group of points on an elliptic curve over a finite field can be used to construct a public key cryptosystem. In 1997, we proposed an ID-based key distribution system over an elliptic curve, as well as those over the ring Z/nZ. Its security depends on the difficulty of factoring a composite number of two large primes. We showed that this system over an elliptic curve is more suitable for the implementation than those over the ring Z/nZ. In this paper, we apply the Nyberg-Rueppel ID-based key distribution system to an elliptic curve. It provides relatively small block size and high security. This public key distribution system can be efficiently implemented. However the Nyberg-Rueppel's scheme requires relatively large data transmission. As a solution to this problem, we improve the scheme. This improved scheme is very efficient since data transferred for the common key generation is reduced to half of those in the Nyberg-Rueppel's scheme.

In this paper it is pointed out that although an elegant differential-like approach is developed, Coppersmith' attacking method on NIKS-TAS cannot succeed to forge a shared key of legitimate entities especially when p-1 contains highly composite divisors, as well as decomposibility-hard divisors. This is mainly due to a severe reduction of modulo size. Computer simulation results confirm this assertion. The ambiguity in the solutions to the collusion equations in the first phase can be analyzed by the elementary divisor theory. Moreover, two basis vectors, qi,ri in the second phase, are found to be inadequate to represent the space spanned by xi-yi and ui-vi(i=1,...,N), because qi,ri exist frequently over the space with small modulo size. Then, the erroneous values of αi,βi,...,εi(i=1,...,N) are derived from the inadequate basis vectors, qi,ri. Also, when the degeneracy in modulo size happens, the solutions to αi,βi,...,εi(i=1,...,N) cannot be solved even by means of the exhaustive search over the small prime divisors of p-1.

We propose two types of key management systems that use complementary exponential calculation, in which users in the system divide into groups, and the different modulus numbers are assigned to each group and edges between groups. Key generation information over the modulus numbers is issued to a user by a trusted center. The user who receives the information can generate shared encryption keys between users in the system without using key exchange protocol. In our proposed system, the number of primes is one of the parameters for generating key generation information. The number decreases in inverse proportion to the square of the number of groups compared to the original method. Our proposed technique enabled us to extend the number of users in the system to more than one million, which is not possible with the original method.