An efficient method of generating rational points on elliptic curves

Several digital signature schemes based on the discrete logarithm problem or the computational Diffie-Hellman problem which have tight security reductions are proposed in these years. For these schemes, the groups of rational points on elliptic curves are employed for efficiency. These schemes need cryptographic hash functions with the range in the group of rational points on elliptic curves in their procedures for generating/verifying signatures. However, no efficient algorithm for such hash functions is known except for special type of elliptic curves, consequentially, the signature schemes becomes inefficient even if elliptic curves are employed. In this paper, in order to improve the efficiency of the signature schemes, a new method of generating rational points on elliptic curves is proposed. The proposed method is based on the norm map from a quadratic extension field of the definition field. This method consists of one powering for determination of quadratic residuosity and a square root extraction, and at most 16 times multiplications in the definition field. The security when the proposed algorithm is used as a hash function is also investigated.