Canetti et al. [5] showed that there exist signature and encryption schemes that are secure in the random oracle (RO) model, but for which any implementation of the RO (by a single function or a function ensemble) results in insecure schemes. Their result greatly motivates the design of cryptographic schemes that are secure in the standard computational model. This paper gives some new results on the RO methodology. First, we give the necessary and sufficient condition for the existence of a signature scheme that is secure in the RO model but where, for any implementation of the RO, the resulting scheme is insecure. Next, we show that this condition induces a signature scheme that is insecure in the RO model, but that there is an implementation of the RO that makes the scheme secure.

A digital signature does not allow any alteration of the document to which it is attached. Appropriate alteration of some signed documents, however, should be allowed because there are security requirements other than the integrity of the document. In the disclosure of official information, for example, sensitive information such as personal information or national secrets is masked when an official document is sanitized so that its nonsensitive information can be disclosed when it is requested by a citizen. If this disclosure is done digitally by using the current digital signature schemes, the citizen cannot verify the disclosed information because it has been altered to prevent the leakage of sensitive information. The confidentiality of official information is thus incompatible with the integrity of that information, and this is called the digital document sanitizing problem. Conventional solutions such as content extraction signatures and digitally signed document sanitizing schemes with disclosure condition control can either let the sanitizer assign disclosure conditions or hide the number of sanitized portions. The digitally signed document sanitizing scheme we propose here is based on the aggregate signature derived from bilinear maps and can do both. Moreover, the proposed scheme can sanitize a signed document invisibly, that is, no one can distinguish whether the signed document has been sanitized or not.

A fair exchange scheme is a protocol by which two parties Alice and Bob exchange items or services without allowing either party to gain advantages by quitting prematurely or otherwise misbehaving. To this end, modern cryptographic solutions use a semi-trusted arbitrator who involves only in cases where one party attempts to cheat or simply crashes. We call such a fair exchange scheme optimistic. When no registration is required between the signer and the arbitrator, we say that the fair exchange scheme is setup-free. To date, the setup-free optimist fair exchange scheme under the standard RSA assumption was only possible from the generic construction of [12], which uses ring signatures. In this paper, we introduce a new setup-free optimistic fair exchange scheme under the standard RSA assumption. Our scheme uses the GQ identity-based signature and is more efficient than [12]. The construction can also be generalized by using various identity-based signature schemes. Our main technique is to allow each user to choose his (or her) own "random" public key in the identity-based signature scheme.

We say that a signature scheme is strongly existentially unforgeable (SEU) if no adversary, given message/signature pairs adaptively, can generate a signature on a new message or a new signature on a previously signed message. We propose a general and efficient conversion in the standard model that transforms a secure signature scheme to SEU signature scheme. In order to construct that conversion, we use a chameleon commitment scheme. Here a chameleon commitment scheme is a variant of commitment scheme such that one can change the committed value after publishing the commitment if one knows the secret key. We define the chosen message security notion for the chameleon commitment scheme, and show that the signature scheme transformed by our proposed conversion satisfies the SEU property if the chameleon commitment scheme is chosen message secure. By modifying the proposed conversion, we also give a general and efficient conversion in the random oracle model, that transforms a secure signature scheme into a SEU signature scheme. This second conversion also uses a chameleon commitment scheme but only requires the key only attack security for it.

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.

This paper studies the relations among several definitions of anonymity for ring signature schemes in the same attack environment. It is shown that one intuitive and two technical definitions we consider are asymptotically equivalent, and the indistinguishability-based technical definition is the strongest, i.e., the most secure when achieved, when the exact reduction cost is taken into account. We then extend our result to the threshold case where a subset of members cooperate to create a signature. The threshold setting makes the notion of anonymity more complex and yields a greater variety of definitions. We explore several notions and observe certain relation does not seem hold unlike the simple single-signer case. Nevertheless, we see that an indistinguishability-based definition is the most favorable in the threshold case. We also study the notion of linkability and present a simple scheme that achieves both anonymity and linkability.

The ring signature allows a signer to leak secrets anonymously, without the risk of identity escrow. At the same time, the ring signature provides great flexibility: No group manager, no special setup, and the dynamics of group choice. The ring signature is, however, vulnerable to malicious or irresponsible signers in some applications, because of its anonymity. In this paper, we propose a traceable ring signature scheme. A traceable ring scheme is a ring signature except that it can restrict "excessive" anonymity. The traceable ring signature has a tag that consists of a list of ring members and an issue that refers to, for instance, a social affair or an election. A ring member can make any signed but anonymous opinion regarding the issue, but only once (per tag). If the member submits another signed opinion, possibly pretending to be another person who supports the first opinion, the identity of the member is immediately revealed. If the member submits the same opinion, for instance, voting "yes" regarding the same issue twice, everyone can see that these two are linked. The traceable ring signature can suit to many applications, such as an anonymous voting on a BBS. We formalize the security definitions for this primitive and show an efficient and simple construction in the random oracle model.

A fair exchange scheme is a protocol by which two parties Alice and Bob swap items or services without allowing either party to gain an advantage by quitting prematurely or otherwise misbehaving. Verifiably committed signature is a generalized and unified model for non-interactive optimistic fair exchange scheme. The state-of-the-art verifiably committed signature that enjoys the off-line, setup-free and stand-alone properties is due to Zhu and Bao [1]. In this article, we show that the Zhu-Bao's verifiably committed signature is insecure in the multi-user setting and then consider possible countermeasures.

In the current broadcasting system or Internet content distribution system, content providers distribute decoders (STB) that contain secret keys for content decryption, prior to content distribution. A content provider sends encrypted content to each user, who then decodes it with his or her STB. While users can get the services at their houses if they have an STB, it is hard for them to get the services outside their houses. A system that allowed users to carry around their secret keys would improve usability, but it would require countermeasures against secret key exposure. In this paper, we propose such an extended broadcasting system using tokens and group signature. The content providers can control the number of keys that users can use outside their houses. The system enables the broadcasters to minimize the damage caused by group signature key exposures and the user to get services outside his or her home.

Previously Verifier-Local Revocation (VLR) group signature schemes from bilinear maps were proposed. In VLR schemes, only verifiers are involved in the revocation of a member, while signers are not. Thus, the VLR schemes are suitable for mobile environments. Furthermore, the previously proposed schemes satisfy the important backward unlinkability. This means that even after a member is revoked, signatures produced by the member before the revocation remain anonymous. This property is needed in case of a voluntary leave of a member or in case of a key loss. However, in the previous schemes, signatures become long, due to the adopted assumption, which should be improved in order to apply the schemes to the mobile environments. In this paper an improved VLR scheme is proposed with the shorter group signatures. This is achieved by using a different assumption, DLDH assumption, and improving zero-knowledge proofs in the group signatures. The length of the proposed group signatures is reduced to about 53% of that of the previous ones.

A simple, yet effective geometric method is presented to construct the signature sequences for multicarrier code-division multiple access (MC-CDMA) systems. By minimizing the correlation of the effective signature vectors, the signature sequences are recursively determined via projection onto a properly constructed subspace. Conducted simulations verify the effectiveness of the method.

When we consider user's convenience for electronic transactions, it might be desirable to generate a digital signature using biometrics. However, it is not easy nor practicable in today's communications environment because of inaccurate measuring and potential hill-climbing attacks with regard to biometrics, unless specific hardware storage is provided for manipulating signature keys or biometric templates securely. In this paper, we study a simple practical method for biometrics based digital signature generation without such restriction. It is based on the existing tools in software in our proposed model where a general digital signature such as RSA can be applied without losing its security. This is not a cryptography paper but rather written from the practical perspectives.

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.

Although a great deal of research has been done on electronic cash schemes with blind multisignatures to prevent an insider attack, there is no discussion of a formal security model in the literature. Firstly we discussed the security model of e-cash schemes based on the blind multisignature scheme against a (restricted) attack model and proposed a concrete scheme proven to be secure in the model [1]; however, this attack model disallows an attacker from corrupting an issuing bank and shops in the forgery game. In this paper, first, we reconsider the security model to remove the restriction of the attack model. Second, we propose a new untraceable e-cash scheme with a blind multisignature scheme and prove that the proposed scheme is secure against the (non-restricted) attacks under the DDH assumption in the random oracle model.

We study on the security proof of the improved efficient-Rabin (ERabin) scheme and the F-FDHS scheme. First, we show that the security theorem of the improved ERabin scheme is not correct, and then provide a correct theorem for it. Second, we show that the security theorem of the F-FDHS scheme lacks an assumption. Finally, we present a way to modify the improved ERabin scheme and the F-FDHS scheme.

Ring signature scheme enables a signer to sign a message anonymously. In the ring signature scheme, the signer who wants to sign a document anonymously first chooses some public keys of entities (signers) and then generates a signature which ensures that one of the signer or entities signs the document. In some situations, however, the ring signature scheme allows the signer to shift the blame to victims because of the anonymity. The group signature scheme may be a solution for the problem; however, it needs an electronic big brother, called a group manager, who can violate the signer anonymity by himself, and a complicated key setting. This paper introduces a new notion of a signature scheme with signer anonymity, a deniable ring signature scheme (DRS), in which no group manager exists, and the signer should be involved in opening the signer anonymity. We also propose a concrete scheme proven to be secure under the assumption of the DDH (decision Diffie Hellman) problem in the random oracle model.

This paper presents a secure and simple content-based digital signature method for verifying the image authentication under JPEG, JPEG2000 compression and scaling based on a novel concept named lowest authenticable difference (LAD). The whole method, which is extended from the crypto-based digital signature scheme, mainly consists of statistical analysis and signature generation/verification. The invariant features, which are generated from the relationship among image blocks in the spatial domain, are coded and signed by the sender's private key to create a digital signature for each image, regardless of the image size. The main contributions of the proposed scheme are: (1) only the spatial domain is adopted during feature generation and verification, making domain transformation process unnecessary; (2) more non-malicious manipulated images (JPEG, JPEG2000 compressed and scaled images) than related studies can be authenticated by LAD, achieving a good trade-off of image authentication between fragile and robust under practical image processing; (3) non-malicious manipulation is clearly defined to meet closely the requirements of storing images or sending them over the Internet. The related analysis and discussion are presented. The experimental results indicate that the proposed method is feasible and effective.

Multisignature schemes enable us to integrate multiple signatures into a single short signature. In 2001, Mitomi and Miyaji proposed a general model of multisignatures, in which signed messages are flexible and the signing order is verifiable and flexible. Several schemes that satisfy these properties have been proposed, but to the best of our knowledge, their verifiable orders are limited to only sequential structures unlike some order-verifiable (but not message-flexible) multisignatures. We define a signing structure as a labeled tree, which can represent any natural signing order including series-parallel graphs, and formalize a general model of multisignatures that makes good use of our structure. We present a security model for such signatures, give the construction based on the general aggregate signature developed by Boneh et al., and provide a security proof in the random oracle model.

An approach of membership revocation in group signatures is verifier-local revocation (VLR for short). In this approach, only verifiers are involved in the revocation mechanism, while signers have no involvement. Thus, since signers have no load, this approach is suitable for mobile environments. Although Boneh and Shacham recently proposed a VLR group signature scheme from bilinear maps, this scheme does not satisfy the backward unlikability. The backward unlinkability means that even after a member is revoked, signatures produced by the member before the revocation remain anonymous. In this paper, we propose VLR group signature schemes with the backward unlinkability from bilinear maps.

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.