Abstract. Recently . Since the solution is very efficient, i.e., 0 ( l p l 3 ) , the Semaev-Smart-Satoh-Araki (SSSA) algorithm implies the possibility of realizing a trapdoor for the discrete logarithm problem, and we have tried to utilize the SSSA algorithm for constructing a cryptographic scheme. One of our trials was to realize an identity-based cryptosystem (key-distribution) which has been proven to be as secure as a primitive problem, called the Diffie-Hellman problem on an elliptic curve over Z/nZ (n = p q , p and q are primes) where Ep and E, are anomalous curves (anomalous En-Diffie-Hellman problem). Unfortunately we have found that the anomalous En-Diffie-Hellman problem is not secure (namely, our scheme is not secure). First, this paper introduces our trial of realizing an identity-based cryptosystem based on the SSSA algorithm, and then shows why the anomalous En-Diffie-Hellman problem is not secure. In addition, we generalize the observation of our breaking algorithm and present reductions of factoring n to computing the order' of an elliptic curve over Z / n Z . (These reductions roughly imply the equivalence of intractability between factoring and computing elliptic curve's order.) The algorithm of breaking our identity-based cryptosystem is considered to be a special case of these reductions, and the essential reason why our system was broken can be clarified through these reductions: En in our system is a very specific curve such that the order of En (i.e., n) is trivially known.
Okamoto and Uchiyama REF proved that the order of an elliptic curve group over the RSA ring reveals the factorization of the RSA modulus.
Security of an Identity-Based Cryptosystem and the Related Reductions
In Advances in Cryptology, Eurocrypt'98, LNCS 1403
Mathematics Computer Science