International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Hard Isogeny Problems over RSA Moduli and Groups with Infeasible Inversion

Authors:
Salim Ali Altuğ
Yilei Chen
Download:
DOI: 10.1007/978-3-030-34621-8_11
Search ePrint
Search Google
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.
BibTeX
@article{asiacrypt-2019-30042,
  title={Hard Isogeny Problems over RSA Moduli and Groups with Infeasible Inversion},
  booktitle={Advances in Cryptology – ASIACRYPT 2019},
  series={Advances in Cryptology – ASIACRYPT 2019},
  publisher={Springer},
  volume={11922},
  pages={293-322},
  doi={10.1007/978-3-030-34621-8_11},
  author={Salim Ali Altuğ and Yilei Chen},
  year=2019
}