This paper proposes a new RSA-type scheme over non-singular parts of singular cubic curves En(α,β):(y-αx)(y-βx)x3(mod n). In usual one-to-one communication, we prove that breaking the proposed scheme is not easier than breaking the RSA scheme for the whole ciphertexts. If encryption key e is larger than 19 for 512 bits modulus n, then the proposed scheme is secure against the Hastad attack in broadcast applications. A plaintext of two blocks, i.e., x and y coordinates in En(α,β), is encrypted to a ciphertext of three blocks, where the size of one block is log2n bits. The decryption speed ofthe proposed scheme is as fast as that of the RSA scheme for the even block plaintext.

We propose an RSA-type scheme over the nonsingular part of a singular cubic curve En (0,b) : y2x3+bx2 (mod n), where n is a product of form-free primes p and q. Our new scheme encrypts/decrypts messages of 2 log n bits by operations of the x and y coordinates. The decryption is carried out over Fp or a subgroup of a quadratic extension of Fp, depending on quadratic residuosity of message-dependent parameter b. The decryption speed in our new scheme is about 4.6 and 5.8 times faster than that in the KMOV scheme and the Demytko scheme, respectively. We prove that if b is a quadratic residue in Zn, breaking our new scheme over En(0,b) is not easier than breaking the RSA scheme.