Paper 2018/926

Hard Isogeny Problems over RSA Moduli and Groups with Infeasible Inversion

Salim Ali Altug and Yilei Chen

Abstract

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.