Trapdoor commitment schemes are widely used for adding valuable properties to ordinary signatures or enhancing the security of weakly secure signatures. In this letter, we propose a trapdoor commitment scheme based on RSA function, and prove its security under the hardness of the integer factoring. Our scheme is very efficient in computing a commitment. Especially, it requires only three multiplications for evaluating a commitment when e=3 is used as a public exponent of RSA function. Moreover, our scheme has two useful properties, key exposure freeness and strong trapdoor opening, which are useful for designing secure chameleon signature schemes and converting a weakly secure signature to a strongly secure signature, respectively.

Almost all the existing secret sharing schemes are based on a single dealer. Maybe in some situations, the secret needs to be maintained by multiple dealers. In this paper, we proposed a novel secret sharing scheme based on the multi-dealer by means of Shamir's threshold scheme and T. Okamoto and S. Uchiyama's public-key cryptosystem. Multiple dealers can commonly maintain the secret and the secret can be dynamically renewed by any dealer. Meanwhile, the reusable secret shadows just needs to be distributed only once. In the secret updated phase, the dealer just needs to publish a little public information instead of redistributing the new secret shadows. Its security is based on the security of Shamir's threshold scheme and the intractability of factoring problem and discrete logarithm problem.

A new simply implemented collusion-attack free identity-based non-interactive key sharing scheme (ID-NIKS) has been proposed. A common-key can be shared by executing only once a modular exponentiation which is equivalent to RSA deciphering, and the security depends on the difficulty of factoring and the discrete logarithm problem. Each user's secret information can be generated by solving two simple discrete logarithm problems and synthsizing their solutions by linear combination. The detail comparison with the Maurer-Yacobi's scheme including its modified versions shows that the computational complexity to generate each user's secret information is much smaller and the freedom to select system parameters is much greater than that of the Maurer-Yacobi's scheme. Then our proposed scheme can be implemented very easily and hence it is suitable for practical use.

To examine the computational complexity of cryptographic primitives such as the discrete logarithm problem, the factoring problem and the Diffie-Hellman problem, we define a new problem called square-root exponent, which is a problem to compute a value whose discrete logarithm is a square root of the discrete logarithm of a given value. We analyze reduction between the discrete logarithm problem modulo a prime and the factoring problem through the square-root exponent. We also examine reductions among the computational version and the decisional version of the square-root exponent and the Diffie-Hellman problem and show that the gap between the computational square-root exponent and the decisional square-root exponent partially overlaps with the gap between the computational Diffie-Hellman and the decisional Diffie-Hellman under some condition.

In 1999, Boneh et al. proposed the Lattice Factoring Method (LFM) for the integer factoring problem for a composite of the form N = prq by employing the LLL-algorithm. Time complexity of LFM is measured by the number of calls of the LLL-algorithm. In the worst case, the number is 2log p for a certain constant c. In 2001, Uchiyama and Kanayama introduced a novel criterion and provided an improved algorithm which runs (2k-p)/|p-Nr+1| times faster (for certain constants k, Nr+1). In this letter, we note another practical improvement applicable to the original and the improved LFM, which enables to provide about 2 times speed-up.

Recently, Boneh et al. proposed an interesting algorithm for factoring integers, the so-called LFM (Lattice Factoring Method). It is based on the techniques of Coppersmith and Howgrave-Graham, namely, it cleverly employs the LLL-algorithm. The LFM is for integers of the form N = pr q, and is very effective for large r. That is, it runs in polynomial time in log N when r is on the order of log p. We note that for small r, e.g. N =pq, p2q, it is an exponential time algorithm in log N. In this paper, we propose a method for speeding up the LFM from a practical viewpoint. Also, theoretical considerations and experimental results are provided that show that the proposed algorithm offers shorter runing time than the original LFM.

Secret sharing schemes are good for protecting the important secrets. They are, however, inefficient if the secret shadow held by the shadowholder cannot be reused after recovering the shared secret. Traditionally, the (t, n) secret sharing scheme can be used only once, where t is the threshold value and n is the number of participants. To improve the efficiency, we propose an efficient dynamic secret sharing scheme. In the new scheme, each shadowholder holds a secret key and the corresponding public key. The secret shadow is constructed from the secret key in our scheme, while in previously proposed secret sharing schemes the secret key is the shadow. In addition, the shadow is not constructed by the shadowholder unless it is necessary, and no secure delivery channel is needed. Morever, this paper will further discuss how to change the shared secret, the threshold policy and cheater detection. Therefore, this scheme provides an efficient way to maintain important secrets.

We propose an interactive identification scheme based on the quadratic residue problem. Prover's identity can be proved without revealing his secret information with only one accreditation. The proposed scheme requires few computations in the verification process, and a small amount of memory to store the secret information, A digital signature based on this scheme is proposed, and its validity is then proved. Lastly, analysis about the proposed scheme is presented at the end of the paper.