On-line secret sharing scheme, introduced by Cachin, is a computational variation of secret sharing scheme. It supports dynamic changing of access structures and reusable shares, by grace of public bulletin board. In this paper, first we introduce a formal model of on-line secret sharing scheme, and analyze existing on-line secret sharing schemes. As a result, it is shown that they are all vulnerable by giving concrete attacks. Next, we propose a novel on-line secret sharing scheme which is provably secure.

We first model the formal security model of multisignature scheme following that of group signature scheme. Second, we prove that the following three probabilistic multisignature schemes based on a trapdoor permutation have tight security; PFDH (probabilistic full domain hash) based multisignature scheme (PFDH-MSS), PSS (probabilistic signature scheme) based multisignature scheme (PSS-MSS), and short signature PSS based multisignature scheme (S-PSS-MSS). Third, we give an optimal proof (general result) for multisignature schemes, which derives the lower bound for the length of random salt. We also estimate the upper bound for the length in each scheme and derive the optimal length of a random salt. Two of the schemes are promising in terms of security tightness and optimal signature length. In appendix, we describe a multisignature scheme using the claw-free permutation and discuss its security.

Chen et al. introduced a new notion of a concurrent signature scheme for a fair exchange of signatures with two parties. Chen et al. also proposed a concrete scheme and proved its security under the assumption of discrete logarithm problem. Recently, Hiwatari and Tanaka extended the concept of concurrent signature to many-to-one setting. Hiwatari and Tanaka also proposed a concrete scheme; however, it requires some strong assumption to achieve the fair exchange and it is not efficient. This paper gives another construction of concurrent signature for many-to-one setting with multisignature scheme. Hereafter, we call it (n,1) concurrent signature scheme. The proposed scheme is more efficient than the scheme of Hiwatari and Tanaka in computation complexity and signature size, and achieves the fair exchange without the assumption required for the scheme of Hiwatari and Tanaka. This paper also gives a construction for the fair exchange of signatures in many-to-many setting, called (n,m) concurrent signature scheme, in appendix.

We first model the variants of OAEP and SAEP by changing a construction and position of a redundancy, and establish a universal proof technique in the random oracle model, the comprehensive event dividing tree. We then make a taxonomical security consideration of the variants of OAEP and SAEP, based on the assumptions of one-wayness and partial-domain one-wayness of the encryption permutation, by applying the tree. Furthermore, we demonstrate the concrete attack procedures against all insecure schemes; we insist that the security proof failure leads to some attacks. From the security consideration, we find that one of the variants leads to a scheme without the redundancy; the scheme is not PA (plaintext aware) but IND-CCA2 secure. Finally, we conclude that some of them are practical in terms of security tightness and short bandwidth.

The new concept of ES (Encryption-Signature) schemes which realize an encryption scheme and a signature scheme with a unique padding technique and key pair, was proposed by Coron et al. They also gave a proof of PSS-ES. In this paper, first, we discuss the methodology for the construction for ES schemes by using padding techniques of encryption schemes, and propose a new ES scheme, OAEP-ES, adopting this methodology. It is proven that OAEP-ES scheme can be constructed under the assumption of the one-wayness of the encryption permutation, while the security of PSS-ES utilized as an encryption scheme is based on the partial-domain one-wayness; which is a theoretical progress since the one-wayness is more general assumption than the partial-domain one-wayness. It is shown that OAEP-ES attains tighter security than PSS-ES, which is a practical interest.