In 1999, Gennaro, Halevi and Rabin proposed a signature which achieves provable security without assuming the random oracles, and it is the first RSA-type signature whose security is proved in the standard model. Since that time, several signatures have been proposed to achieve better efficiency or useful property along with the provable security in the standard model. In this paper, we construct a trapdoor hash function, and design an efficient online/offline signature by using the trapdoor hash function. Our signature scheme requires only one non-modular multiplication of two small integers for online signing, and it provides the fastest online signing among all online/offline signatures that achieve provable security in the standard model.

Group signature schemes with membership revocation have been intensively researched. However, signing and/or verification of some existing schemes have computational costs of O(R), where R is the number of revoked members. Existing schemes using a dynamic accumulator or a similar technique have efficient signing and verifications with O(1) complexity. However, before signing, the signer has to modify his secret key with O(N) or O(R) complexity, where N is the group size. Therefore, for larger groups, signers suffer from enormous costs. On the other hand, an efficient scheme for middle-scale groups with about 1,000 members is previously proposed, where the signer need not modify his secret key. However this scheme also suffers from heavy signing/verification costs for larger groups with more than 10,000 members. In this paper, we adapt the middle-scale scheme to larger groups ranging from 1,000 to 1,000,000 members. At the sacrifice of the group manager's slight cost, our signing/verification is sufficiently efficient.

This paper proposes a group signature scheme with efficient membership revocation. Though group signature schemes with efficient membership revocation based on a dynamic accumulator were proposed, the previous schemes force a member to change his secret key whenever he makes a signature. Furthermore, for the modification, the member has to obtain a public membership information of O(nN) bits, where n is the length of the RSA modulus and N is the total number of joining members and removed members. In our scheme, the signer needs no modification of his secret, and the public membership information has only K bits, where K is the maximal number of members. Then, for middle-scale groups with the size that is comparable to the RSA modulus size (e.g., up to about 1000 members for 1024 bit RSA modulus), the public membership information is a single small value only, while the signing/verification also remains efficient.

In this paper, we construct a new signature scheme which is provably secure against adaptive chosen message attack in the standard model under the strong RSA assumption. The proposed scheme is different from Cramer-Shoup scheme and Camenisch-Lysyanskaya scheme and is more efficient than them. The tradeoff of the proposed scheme is a slight increase of the secret key.

A distributor of digital contents desires to collect users' attributes. On the other hand, the users do not desire to offer the attributes owing to the privacy protection. Previously, an anonymous survey system for attributes statistics is proposed. In this system, asking trusted third parties' helps, a distributor can obtain the correct statistics of users' attributes, such as gender and age, while no information beyond the statistics is revealed. However, the system suffers from the inefficiency of a protocol to generate the statistics, since the cost depends on the number of all the users registering this survey system. This paper proposes an anonymous survey system, where this cost is independent from the number of all the registering users. In this accomplishment, a group signature scheme with attribute tracing is also proposed. A conventional group signature scheme allows a group member to anonymously sign a message on behalf of the group, while only a designated party can identify the signer. The proposed scheme further enables the party to trace signer's attribute.

The strong RSA assumption is an assumption that the following problem is hard to solve: Given an RSA modulus and a ciphertext, find a pair of plaintext and exponent corresponding to them. It differs from the standard RSA assumption in a sense that in the strong version, no exponent is given as an input. The strong RSA assumption is considered to be stronger than the RSA assumption, but their exact relationship is not known. We investigate the strength of the strong RSA assumption and show that the strong RSA assumption restricted to low exponents is equivalent to the assumption that RSA problem is intractable for any low exponent. We also show that in terms of algebraic computation, the strong RSA assumption is properly stronger than the RSA assumption if there exists an RSA modulus n such that gcd((n),3)=1 and RSA problem is intractable.