>>Hi, everyone. This is L. A from Visa Research today. I would like to tell you about my work with Salim. Earlier. Took from Boston University about how to construct group with invisible inversion from heart problems on ice Arjuna graphs over I say model E eso Let me start this talk by tell you, uh, what is a group with invisible inversion? A group was invisible Inversion is defined by Hulkenberg and Mona In 2003 It says a representation off a group should satisfy two properties. The first is literally that inversion. It's heart. Namely that giving an including off group element X computing Uh, the including off its inverse his heart. The second is that the composition is still easy, namely given the including off X and Y computing the including off X plus y is easy here we're seeing. Plus, is the group operation. So let me explain this definition by going through our favorite example where discreet log it's hard, namely in the Multiplicity group of finance field. We include a group element A as G today, namely, put it into the exponents and more, uh, cute. So given G energy today finding a it's hard. So this group representation at least satisfy one way, as you mean this great look. It's hard. So let's look at at whether this a group satisfied group was invisible inversion. So it turns out it is not because given due to the A finding G to the minus A, it's still easy. So if we say this is the representation off the universe, then computing this reputation is simple. So this is a no example. Off group was invisible invasion. So the work off Falkenburg and Mona started by looking. How can we find group was invisible inversion? And what are the applications off such a group? Representation, >>It turns out, in their sisters. They did not find any group reputation representation that satisfy this property. But instead they find out that if you can find such a group and then they they have >>a cryptographic applications, namely building direct directed transitive signatures a year later in the work off Iraq at or they also find that if you can have this kind of group with invisible inversion there, you can also construct broadcast encryption with a small overhead, and this is before we know how to construct the broadcast encryption with small overhead over Terry's elliptic curve. Paris. So let's look at another attempt off constructing group with invisible inversion. So instead off defining. Still, let's look at a group where we put >>the including in the exponents and instead of defining due to the minus A as the inversion Let's define due to the one over a as the the inverse off do today. So it turns out you can also define that. And it happens that in many groups, minimally, if you more, uh, some special value a que then given G energy to the A, then competing due to the one over A is also conjectured to be hard. But if you define the group element in the experiment in that way, then multiplication in >>the group exponents is also hard, and so we cannot compose. So this is another no example where group inversion is actually difficult to compute. But composition is difficult to compute, uh, either. So for this kind of group, they cannot use this to build directly transitive signatures or broadcast encryption. So now let's make this attempt, uh, visible by allowing thio. So so thio have ability to compute composition. Namely, we represent the including off A as the follows. So first we help you today >>and then we also give an office Kate the circuit which contains a and n such that I take a group element X, and it can output due to the to a model end. So it turns out giving this circuit you have a feasibility off doing composition and in the work off yamakawa at all to show that if and that the underlying off station is io and assuming and it's an R s a moderately then Thistle >>is actually a good construction off group with invisible university. So technically, assuming I oh, we have already know candidates for group was in physical inversion. Uh, but that work still leaves the open problem off constructing group with invisible inversion without using general purpose sophistication. And in this talk, I would like to talk to tell you about a group was inversion candidate from some new certainly problems And the brief logic off this talk is the following. So elliptical insurgencies can be represented by graph, uh, and the graphs has a ship off volcanoes. For example, this one if you look imagine you're looking for a volcano from top to down and this is the Creator, and this is like the direction off going down the volcano. And arguably this is the reason which attracts me to looking to. I certainly problems, and also I certainly graphs can be an I certainly can be used to represent a group called Idea Class Group >>and then eventually we will find some group >>problems on this graph, which we conjecture to be hard. And they use map thes harness to the harness off inverting group elements in the ideal classroom. So this will be the high level overview off this talk. >>So what are a little bit curve? Assertiveness? So to talk about elliptic curve, I certainly okay spend the whole day talking about its mathematical definition and the many backgrounds off elliptic curve. But today we only have 15 minutes. So instead, let me just to give you a highlight help have overview off what I certain this and I certainly is a mapping from when a little bit of curve to another, and I certainly is an interesting equivalence relation between elliptic curves. It's interesting in its mathematical theory, over a finite field and elliptic curve can be identified by its J environment. And later, >>when we talk about elliptic, curve will think about their represented by their environment, which is a number in the finance field >>and given to elliptic curves and namely, given their environments, we can efficiently decide whether these two groups assertiveness, namely in polynomial time. And given these backgrounds, let me now jump to the exciting volcanoes. So it turns out >>the relation among I certainly occurred. Assertiveness curbs can be represented by the I certainly graphs, which looks like volcanoes. So let's first look at the graph on the left and let's fix a degree for that. I certainly so I certainly has different degrees. So let's for simplicity. Think about their crimes. So let's fix a degree Air say equals 23 >>and we will let each of the note in the graph to represent a different elliptic curve, namely a different Jane environment, and each is represent an air degree by certainly so if you fix the degree ill and I certainly is their religions, uh, they just look like what I said, like what kind of going from top to bottom and if, let's say, fix all the >>elliptic curve on the creator or, in general, all the elliptic curves on the same layer off the volcano, Then you allowed to have different degrees. So this is degree L and this is degree M, etcetera, etcetera. And then the graph actually looks like it's almost fully connected. Eso imagine all of them are connected by different degrees. And the graph structure is actually described not too long ago in the pH. Diseases off Davico Hell in 1996 and later it gets popularized in a paper in 2002 because they say, Hey, this looks like a volcano. So now the I certainly will. Kind of is they used in many reference by according the graph. >>So let me tell you a little bit more about the relation off. I certainly and the idea class group. So the short story is, if you fix a layer on the uncertainty graph, say the creator. So actually, all the notes has a 1 to 1 mapping to the group element in an ideal >>class group. The foremost Siri is the ideal class group acts on the, uh, set off a surgeon is which have the same in the more it is a Marine. But we will not go into their, uh in the talk today. So let me give you a simple example. So this is, ah, concrete representation off an ideal class group off seven group elements. And if we fix a J zero j environment off one off the grade curve, let's say this guy represents the identity in the idea class group. And then we let J one to represent one off the class group elements. Then it's inverse is just going one step back from the origin in the opposite direction S O. This is a very important picture we will use exactly the J environments to represent and the idea class group elements eso This is exactly the reputation we're gonna take, except we're gonna work with over the icy modeling. So after giving some mathematical background off elliptical by certainly in a certain graph now, let's talk about competition of problems >>and before jumping into I say model E, let me start from the, uh, more traditionally studied. I certainly problems over the finite field. The first problem is if I fix a degree, air and I give you a J environment off elliptic curve. Ast one off the note. That's first. Take an easy question. Is it easy to find all off? >>It's certainly neighbors off degree will say there is a polynomial. >>The answer is yes. And the technically there are two different ways. Uh, I will not go to the details off what they are, but what we need to know is they require serving, uh, polynomial off degree or air squares. Let's look at another problem that so imagine I select to random >>curves from an I certainly graph. So think about this. Uncertainty graph is defined over a large field, and they are super polynomial limited graphs off them. I'm choosing to random curves. >>The question is, can you find out an explicit I Certainly between them naming and Emily passed from one to the other. It turns out this >>problem is conjecture to be hard even for quantum computers, and this is exactly what was used in the post to quantum key exchange proposals in those works. So they have different structures could aside the seaside. They're just a different types off in the book is a Marine off the question is off the same nature finding and passed from one curve to the other. So these are not relevant to our work. But I would like to introduce them for for some background, off the history off. I certainly problems, >>So you have a work we need to >>study. I certainly problems over in, I say endogenous. And so the first question is even how to define. And I certainly, uh oh, and I certainly graph over the ring like, uh, over and I say modular. Same. So >>there is a general way off defining it in the 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 have the ability off peaking too. I certainly volcan als over multi and multi cube. That has exactly the same structure. And then I just use a C a c r T composition to stick them together. So namely a J >>zero. The value is the CRT off the J zero over. They're over the small fields P and the Cube and the N S equals to P times Q. And by the way, thes gene variants will be exactly the way to represent an ideal class group off such a size in this example is the ideal class group off, uh, with discriminate minus 250 bucks. Okay, so now let's look at what this magical over this representation. So let's look at back to the problem we start from namely, finding all the insurgents neighbors at this time over. And I see model E eso. I give you the J environment off easier and ask you to find a one off the its neighbors finding the J environment off one off its neighbors. So it turns out, even this problem is hard. And actually, we can prove this problem is as hard as factory and naive. Way off. Explaining off What's going on is that the two methods that work over the finite field that doesn't work anymore, since they both required to solve high degree polynomial model end, and that this is hard where when end is in, I certainly I say modelers. So to be useful for constructing a group off invisible inversion, we actually need to look at this called a joint neighbors. Such problems, namely, if I give you a curve zero, which represents the identity, then another crib, which represents a the group element. Your task is to find its inverse namely one off the E two candidate beneath zero. Yeah, eso it turns out this problem. We also conjectured to it to be hard and we don't know how to base it on how this a factoring, uh, again, the not even reason is the way to solve it over the finite field doesn't work because they both required to solve polynomial off degree higher than one over in i. C model is. And this is exactly the reason that we believe the group inversion is hard over deserve visitation Now. Finally, we also would like to remind the readers that for death according to the definition off group with invisible inversion, we would also like the group elements to be easy to compose. No, that's not. Make another observation that over. If you're finding the joint neighbor off, I certainly off different degree. Say, if I give you a J invent off Iwan and Jane Barrett off you to ask you to find the J environment off the three and they happened to off co prime degree I. Certainly then there is a way to find their joint neighbor because they're cold prime. And there's only 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. Normally we output, including that are a cold prime so that they can be composed to summarize that we propose a group candidate group with invisible inversion from any particular I. Certainly it requires a chapter because you need to know the prime factors off. I seem odd early to set up the whole system and generated the including in our me assumption is that certain joint neighbors such problem on the I certainly graphs defined over S a moderately it's hard again group within physical inversion has the application of constructing broadcasting, corruption directed transitive signatures, and it's a very interesting problem to explore