Transcript of the presentation Hard Problems on Isogeny Graphs over RSA Moduli and Groups with Infeasible Inversion, given at the NTT Upgrade 2020 Research Summit, September 30, 2020

Hi, everyone. This is Yilei from Visa Research. Today I would like to tell you about my work with Salim Ali Altug from Boston University about how to construct groups with infeasible inversion from hard problems on isogeny graphs over RSA moduli. So let me start this talk by tell you what is a group with infeasible inversion? A group with infeasible inversion is defined by Hohenberger and Molnar in 2003. It says a representation of a group should satisfy two properties. The first is literally that inversion is hard, namely, that giving an encoding of a group element x, computing the encoding of its inverse is hard. The second is that composition is still easy, namely, given the encoding of x and y, computing the encoding of x plus y is easy. Here we assume plus is the group operation.

So let me explain this definition by going through our favorite example where discrete log is hard. Namely, in the multiplicative group of finite field, we include a group element a, as g to the a, and we put it into the exponent and mod q. So given g and g to the a, finding a is hard, so this group representation at least satisfies one way assuming discrete log is hard. So let’s look at whether this group satisfies a group with infeasible inversion. So it turns out it is not, because given g to the a, finding g to the minus a is still easy.

So if we say this is the representation of the inverse, then computing this representation is simple. So this is not example of group with infeasible inversion. So to work off Hohenberger and Molnar, start by looking how can we find a group with infeasible inversion and what are the applications of such a group representation? It turns out in their thesis, they did not find any group representation that satisfied this property, but instead they find out that if you can find such a group, then they have cryptographic applications, namely building directed transitive signatures. A year later in the work of Irrer et al, they also find that if you can have this kind of group with infeasible inversion, then you can also construct broadcasting encryption with a small overhead. And this is before we know how to construct a broadcast encryption with small overhead over pairings, any particular pairings.

So let’s look at another attempt of constructing groups with infeasible inversion. So instead of defining, still, let’s look at a group where we put the encoding in the exponent, and instead of defining g to the minus a as the inversion, let’s define g to the one over a as the inverse of g to the a. So it turns out you can also define that, and it happens that in many groups, namely if you mod some special value q, then given g and g to the a, then computing g to the one over a is also conjectured to be hard.

But if you define the group element in the exponent in that way, then multiplication in the group exponent is also hard, and so we cannot compose. So this is another example where group inversion is actually difficult to compute, but the composition is also difficult to compute. So for this kind of group, they cannot use this to build directed transitive signatures or broadcast encryption. So now let’s make this attempt feasible by allowing to have ability to compute a composition. Namely, we represent the encoding of a as the follows. So first we have g to the a, and then we also get an obfuscated circuit which contains a and N such that I take a group element x and it can output g to the 2a mod N.

So it turns out to giving this circuit, you have a feasibility of doing composition. And in the work of Yamakawa et al, they show that if the underlying obfuscation is iO and assuming N is an RSA moduli, then this is actually a good construction of group with infeasible inversion. So technically assuming iO, we have already now candidates for groups with infeasible inversion. But that work still leaves the open problem of constructing groups with infeasible inversion without using general purpose obfuscation. And in this talk, I would like to talk, tell you about a group with inversion candidate from some new isogeny problems.

And the brief logic of this talk is the following. So elliptic curve isogenies can be represented by graphs, and the graphs has the shape of volcanoes. For example, this one, if you look, imagine you are looking for a volcano from top to down, and this is the crater, and this is the direction of going down the volcano. And arguably, this is the reason which attracts me to looking to isogeny problems. And also isogeny graphs can be, and isogenies can be used to represent a group called ideal class group, and then eventually we will find some group problems on this graph which we conjecture to be hard and map these hardness to the hardness of the inverting group elements in the ideal class groups. So this will be the high-level overview of this talk.

So what are elliptic curve isogenies? So to talk about elliptic curve isogeny, I could spend a whole day talking about its mathematical definition and the many backgrounds of elliptic curve, but today we only have 15 minutes, so instead let me just give you a high-level overview of what are isogenies. An isogeny is a mapping from one elliptic curve to another, and isogenous is an interesting equivalence relation between elliptic curves. It’s interesting in its mathematical theory. Over a finite field, an elliptic curve can be identified by its j-invariant, and later when we talk about elliptic curve, we’ll think about they’re represented by their j-invariant, which is a number in the finite field.

And given two elliptic curves and then when you’re given their j-invariants, we can efficiently decide whether these two curves are isogenous namely in polynomial time. And given this background, let me now jump to the exciting volcanoes. So it turns out the relation among isogenous curves can be represented the by the isogeny graphs, which look like volcanoes. So let’s first look at the graph on the left and let’s fix a degree for that isogeny. So isogeny has different degrees, to let’s for simplicity think about their primes. So let’s fix a degree L, say L equals to three, and we will let each of the nodes in the graph to represent a different elliptic curve, namely, a different j-invariant, and each edge represent an L degree isogeny.

So if you fix the degree L, the isogenies, their relations, they just look like what I said, like a volcano going from top to bottom. And if, let’s say, fix all the elliptic curve on the crater, or in general all the elliptic curves on the same layer of the volcano, then you allow to have different degrees. So this is degree L and this is degree M, et cetera and et cetera. Then the graph actually looks like it’s almost fully connected. So imagine all of them are connected by different degrees. And the graph structure is actually described not too long ago in the PhD thesis of David Kohel in 1996, and later it gets popularized in a paper in 2002 because they say, hey, this looks like a volcano.

So now the isogeny volcano is used in many reference according to graph. So let me tell you a little bit more about the relation of isogeny and the ideal class group. So the short story is if you fix a layer on the isogeny graph, say, the crater, so actually all the nodes has a one-to-one mapping to the group element in an ideal class group. The foremost series, the ideal class group acts on the set of isogenies which have the same endomorphism ring, which we will not go into there in the talk today.

So let me give you a simple example. So this is a concrete representation of an ideal class group of seven group elements. And if we fix j0, the j-invariant of one of the elliptic curves, let’s say this guy represents the identity in the ideal class group. And then we let j1 to represent one of the class group elements where its inverse is just going one step back from origin in the opposite direction. So this is a very important picture. We will use exactly the j-invariants to represent the ideal class group elements. So this is exactly the representation we are going to take except we are going to work with over the RSA moduli.

So after giving some mathematical background of elliptic curve isogeny and the isogeny graph, now let’s talk about computational problems. And before jumping into RSA moduli, let me start from the more traditionally studied isogeny problems over the finite field. The first problem is if I fix a degree L and I give you a j-invariant of an elliptic curve as one of the nodes, let’s first to take an easy question. Is it easy to find all of its isogeny neighbors of degree L? Say L is a polynomial. The answer is yes, and the technical answer are two different ways. I will not go to the details of what they are, but all what we need to know is they require solving polynomials of degree L or L squared.

Let’s look at another problem that, so imagine I select two random curves from an isogeny graph. So think about this isogeny graph is defined over a large field and they are superpolynomial, the many graphs of them. I’m choosing two random curves. The question is, can you find out an explicit isogeny between them, namely passed from one to the other? It turns out this problem is conjectured to be hard even for quantum computers, and this is exactly what was used in the post-quantum key exchange proposals in those works. So they have differences of structures, could SIDH or CSIDH, they are just a different types of endomorphism ring. The question is of the same nature, finding a path from one curve to the other.

So these are not relevant to our work, but I would like to introduce them for some background of the history of isogeny problems. So in our work, we need to study isogeny problems over an RSA modulus N. So the first question is even how to define an isogeny, or an isogeny graph over a ring, like over an RSA modulus N. So there is a general way of defining it and a special case. So in this talk, I will just talk about the special case because this is easier to understand. So think about, I have the ability of picking two isogeny volcanoes over mod p and mod q that has exactly the same structure, and then I just use a CRT composition to stick them together.

So namely j0, the value is the CRT of the j0 over the small fields p and q and N is equal to p times q. And by the way, these j-invariants are exactly the way to represent an ideal class group of such a size. In this example it’s the ideal class group of with discriminant minus 251. Okay, so now let’s look at what is magical over this representation. So let’s look back to the problem we start from, namely finding other isogenous neighbors, this time over an RSA moduli. So I give you the j-invariant of E0 and ask you to find one of its neighbors. Finding the j-invariant of one of its neighbors.

So it turns out even this problem is hard and that actually we can prove this problem is as hard as factoring. And a naive way of explaining of what’s going on is that the two methods that work over the finite field doesn’t work anymore since they both require to solve high degree polynomial mod N, and that this is hard where N is an RSA modulus. So to be useful for constructing a group of infeasible inversion, we actually need to look at this called a joint neighbor search problem. Namely, if I give you a curve E0, which represents the identity, then another curve which represents the group element, your task is to find its inverse, namely, one of the E2 candidates beneath E0.

So it turns out this problem, we also conjecture to it to be hard, and we don’t know how to base it on hardness of factoring. Again, the naive reason is the way to solve it over the finite field doesn’t work because they both require to solve polynomial of degree higher than one over an RSA modulus. And this is exactly the reason that we believe the group inversion is hard over this representation. Now, finally, we also would like to remind the reader that according to the definition of group with infeasible inversion, we would also like the group elements to be easy to compose. Now let’s make another observation that over, if you’re finding the joint neighbor of an isogeny of different degree, so if I give you the j-invariant of E1 and j-invariant of E2, ask you to find the j-invariant of E3, and they happen to have coprime degree isogeny, then there is a way to find their joint neighbor because they are coprime and there’s only a one solution to solving the modular polynomial that I haven’t defined out. But this is the way we make sure that composition is easy when we output encoding that are coprime so that they can be composed.

To summarize, we propose a candidate group with infeasible inversion from elliptic curve isogeny. It requires a trapdoor because you need to know the prime factors of RSA moduli to set up the whole system and to generate the encoding. And our main assumption is that certain joint neighbors search problem on the isogeny graphs defined over RSA moduli is hard. Again, a group with infeasible inversion has the application of constructing broadcast encryption, directed transitive signatures, and it’s a very interesting problem to explore.