Paper 2018/926

Hard Isogeny Problems over RSA Moduli and Groups with Infeasible Inversion

Salim Ali Altug and Yilei Chen


We initiate the study of computational problems on elliptic curve isogeny graphs defined over RSA moduli. We conjecture that several variants of the neighbor-search problem over these graphs are hard, and provide a comprehensive list of cryptanalytic attempts on these problems. Moreover, based on the hardness of these problems, we provide a construction of groups with infeasible inversion, where the underlying groups are the ideal class groups of imaginary quadratic orders. Recall that in a group with infeasible inversion, computing the inverse of a group element is required to be hard, while performing the group operation is easy. Motivated by the potential cryptographic application of building a directed transitive signature scheme, the search for a group with infeasible inversion was initiated in the theses of Hohenberger and Molnar (2003). Later it was also shown to provide a broadcast encryption scheme by Irrer et al. (2004). However, to date the only case of a group with infeasible inversion is implied by the much stronger primitive of self-bilinear map constructed by Yamakawa et al. (2014) based on the hardness of factoring and indistinguishability obfuscation (iO). Our construction gives a candidate without using iO.

Note: Updates: 1. In the introduction, we add a toy example for the trapdoor group with infeasible inversion (TGII). 2. In the main construction of TGII, we separate the construction into the basic version and the general version. 3. Add a small example in Figure 5 to explain the composition and the extraction algorithms. 4. In Section 5.3 we add an attack model called ''gcd-evaluation model'', which describes a simple attack interface. Under the gcd-evaluation model, we find a new attack called ''parallelogram attack'', and discuss the countermeasure. 5. The applications are updated accordingly due to the new presentation of the algorithms and the new attack.

Available format(s)
Publication info
Preprint. MINOR revision.
Elliptic curve isogenyideal class group
Contact author(s)
chenyilei ra @ gmail com
2019-05-14: revised
2018-10-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {Salim Ali Altug and Yilei Chen},
      title = {Hard Isogeny Problems over RSA Moduli and Groups with Infeasible Inversion},
      howpublished = {Cryptology ePrint Archive, Paper 2018/926},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.