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.

In [13], we proposed new decision problems related to lattices, and proved their NP-completeness. In this paper, we present a new public-key identification scheme and a digital signature scheme based on one of the problems in [13]. We also prove the security of our schemes under certain assumptions, and analyze the efficiency of ours.

In this paper, we introduce a new decision problem associated with lattices, named the Exact Length Vector Problem (ELVP), and prove the NP-completeness of ELVP in the ∞ norm. Moreover, we define two variants of ELVP. The one is a binary variant of ELVP, named the Binary Exact Length Vector Problem (BELVP), and is shown to be NP-complete in any p norm (1 ≤ p ≤ ∞). The other is a nonnegative variant of ELVP, named the Nonnegative Exact Length Vector Problem (NELVP). NELVP is defined in the 1 norm, and is also shown to be NP-complete.

We proposed a one-way trapdoor permutation f based multi-signature scheme which can keep tighter reduction rate. Assuming the underlying hash functions are ideal, our proposed scheme is not only provably secure, but are so in a tight. An ability to forge multi-signatures with a certain amount of computational resources implies the ability to invert a one-way trapdoor permutation f (on the same size modulus) with about the same computational effort. The proposed scheme provides the exact security against Adaptive-Chosen-Message-Attack and Adaptive-Insider-Attack by . can also attack in key generation phase, and act in collusion with corrupted signers.

Up to present, proposed are many multi-signature schemes in which signers use respective moduli in the signature generation process. The FDH-based schemes are proposed by Mitomi et al. and Lysyanskaya et al.. The PSS-based schemes are proposed by Kawauchi et al. and Komano et al.. The FDH-based schemes have the advantage that the signature size is independent of the number of the signers. However, since the signature generation algorithm is deterministic, it has a bad reduction rate as a defect. Consequently, the signers must unfortunately use the keys large enough to keep the security. On the other hand, in the PSS-based schemes, good reduction rates can be obtained since the signature generation algorithms are probabilistic. However, the size of the random component shall overflow the security parameter, and thereby the signature size shall grow by the total size of the random components used the signers. That means, if the size of the random component is smaller, the growth of the signature size can be kept smaller. In this paper, we propose new probabilistic multi-signature scheme, which can be proven secure despite that smaller random components are used. We compare the proposed scheme and two existing schemes. Finally, we conclude that the proposed scheme is so-called optimal due to.

In an order-specified multisignature scheme, one can verify not only a set of signers who have signed the message but also its signing order. Though we have seen several schemes with such properties proposed, none of them is given the security proof against active adversaries. The scheme can be easily modified to be an order-specified multisignature scheme, but still has the restriction that the possible signing orders are only ones of the type of serial signing. In this paper, we propose the first order-specified multisignature scheme, which is shown to be secure against adaptive chosen-message insider attacks in the random oracle model, and which allows the signing orders to form like any series-parallel graphs. The security is shown by using ID-reduction technique, which reduces the security of multisignature schemes to those of multi-round identification schemes. Furthermore, we discuss the efficiency of the proposed scheme and the upper bound of the possible number of participating signers.