New Source of Hardness from Isogeny Graphs (Yilei Chen)


Computational problems from elliptic curve isogeny graphs were recent recognized as the new source of hardness in building post-quantum cryptography. In this work we explore more hard problems from isogeny graphs by looking at the isogeny graphs defined over RSA moduli. Although the problems are no longer hard against quantum computers, they provide more interesting cryptographic capabilities secure against classical computers. In particular, based on the conjectured hardness of these new problems, we provide candidate constructions of groups with infeasible inversion.

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 strong assumption of indistinguishability obfuscation (iO). Our construction gives a candidate without using the heavy machinery of iO.

In the talk I will give an introduction of the basic application of isogeny graphs in cryptography. No background of elliptic curve is required.

Based on the joint work with Salim Ali Altug from Boston University. The paper is available at


2019-11-19   14:00 ~ 15:00   


Yilei Chen, Visa Research


Room 602, School of Information Management & Engineering, Shanghai University of Finance & Economics