CryptoDB
Hard Isogeny Problems over RSA Moduli and Groups with Infeasible Inversion
Authors: | |
---|---|
Download: | |
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 }