ZKPodcast: Isogenies with Luca De Feo

Transcript

[Music] welcome to zero knowledge a podcast where we talk about the latest in zero knowledge research and the decentralized web the show is hosted by me Anna and me Fredrik this week we chat with Luca DeFeo all about the topic of ice Sajha knees but before we start in we want to say thank you to this week sponsored trail of bits trail of bits recently released Manticore 0.33 which includes support for symbolically executing webassembly

binaries if you're a regular listener of this podcast you will have heard Fredrik mentioned wasum quite often wasum or webassembly is a newly standardised programming language that allows web developers to run code with near native performance directly within the browser Manticore 0.33 can explore all reachable States in a Wasson program and derive the concrete inputs that produce a given state the goal is to provide a solid foundation for security analysis of wasman programs more information is covered in their latest blog post entitled symbolically executing web assembly in Manticore in general keep an eye on the trail of bits blog for security news and explanation pieces

just like this one I've added the link in the show notes so thank you again trail of bits now here is our interview with Luca in this week's episode we take the podcast in a slightly different direction than we usually do and try to dig into a topic that is pretty deep into cryptography and mathematics and while there's not snark stuff and zero knowledge proof certainly is deep in there as well this is perhaps a bit of a different flavor of that so we want to explore the concept of isogen ease and to some degree how they relate to VDS and cryptography and maybe other

blockchain related things we'll see what we get into but we are we actually arrived at this episode because we talked about PDFs in a previous episode wherein I I said that like there were three Foundation has been playing with this idea of ice our journey based videos and Luca your Co authorial interview in a second your co-author of the ice ogyny vdf paper reached out to to talk more about I saw Jenny's and it's probably the first time that any of the authors of the paper or the some of the work that we've been talking about the podcast as reach out to us so this is a first and a very exciting thing for me but yeah we're very excited to

welcome an experts on this topic look at FAO who's a researcher at IBM research to the podcast to help us better understand what this thing is hi Fredrik hi Anna hello if we just start our basic what are I so genies and how do you think we should approach them for this episode well that's a question which can be answered in one word or one hour at your choice probably before saying the word as a genie I should say the word the little curve I assume most of your audience knows about a little curves a little bit they know it's used in public key encryption and public key

signatures haja knees are a concept related to a little curves and so the one-word definition of a czaja knees is just that they are morphisms of elliptic curves so I guess that morphism is not a word that is used very much in this podcast so I will try to give a slightly longer definition so a morphism is just a function which means that in a naja knee is the function from analytic curve to another related curve which maps points to points but on top of that you also require this function to be something that is called the group morphism which means that it is compatible with the group law of an elliptic curve which basically means that isogen is of a plus size dodging e of b is equal to a so G of a plus B and

that's it something I found really interesting looking at that Wikipedia page is it has this phrase quote the term isomorphism was sometimes confusingly used for what is now called a nice ogyny and it kind of as you said like morphism is probably not a super common term but actually like isomorphism is something that programmers talk increasingly about I come from the haskell world where a lots of people talk about isomorphisms all the time and like category theory but it's even like started to be a thing that you talk about isomorphic web applications jibs main basically meaning that a web app who that's whose code can

run both on the server and in the client and like you can use the same code base everywhere it just thought it was funny to like link these things together because I think people have some basic understanding of isomorphism so how does what what is a morphism when you remove I so isomorphism well all these words come from wit of course morphisms more morphe Morphet means four and morphism is something that preserves some form so it's a function that is keeping preserving some structure and when you add the prefix eyes oh you mean that the structure is being preserved in a

one-to-one way like in a bijection maybe this were this more common and actually it's funny that you mentioned that I've wrote we wrote that in the paper because I completely forgot that but yet through this that i za Jenice i certainly is a very recent word it was invented in the forties by andre by they I guess his French and before the 40s though there was a confusion or between isogen e's isomorphisms nowaday in modern terminology and isomorphism is a special kind of a soul journey so to be precise isomorphisms ability curves are just

eyes dodging is of degree one that's the definition nowadays but at the end of the twentieth century at the beginning of sorry at the end of the 19th century beginning of 20th century people were more looking into the geometry ability curves over the complex numbers where it felt natural to call isomorphism this concept and then only in the beginning of the 20th century and come into the 30s people started to look it more algebraically and then they really wanted to make this distinction between isogen ease and isomorphisms which was in the end written down by they so I thought is a very strange word which is very uncommon I don't think there's any other object in

mathematics that has such a strange name it would definitely be make sense to just call them morphisms ability curves but actually I like that there is this very special word because I would say morphism based cryptography doesn't sound good but I don't need a script offerees is a nice word I've I've been talking to a few people about ice Lajja knees in the lead-up to this episode to try to get some sense of it and I actually heard morphism defined as a map that preserves a property and not necessarily as a function is that also correct yeah definitely I use the words mapping function in more or less ting meaning the same in some textbooks you could have a different meaning for

function and map but definitely not in this podcast got it and is the I also understood that it is this algebraic I think you just said this the algebraic property is what defines the I so the ice the ice ogyny version right okay just checking it yeah yeah and when we say algebraic would really mean these polynomials okay you can think of polynomials like X cube plus 3 that's a polynomial algebraic just means that somewhere in your structure there's something that's defined by polynomials cool so the and I just mentioned that this morphisms you preserve some property and and I think it's about to ask the question of like what properties do they

preserve there's two things that are preserved by this notion of morphism but one I already said it before it's that it's a group and so it preserves the group structure and the second aspect the second important thing that is preserved by his attorneys is been algebraic varieties but does not going to take us anywhere because that's pretty much implicit in the fact that I'm sending a little authority curves I think we need to map out somewhat where this concept of us I I saw Jenice lives sort of water compared to what it does when you describe it as a function between a group in a group mathematically that I mean at least for me that of did math from here it's a pretty simple concept mathematically it's just like

okay I get that how the hell does that lead to anything cryptography well to really understand how I saw Denise are using crypto you should forget at least for a while that these are functions and kind of zoom out and look from really a miles above perspective in Nagy Anubis crypto we do not just look at 2l it occurs with one as alternate between them we really look at lots of a little curves with all the Asajj needs that link them so we call these object size autographs because we really do graphs like in graph theory for those who have some background in that where vertices are analytic curves

and edges are isogen ease that linked them usually you put some constraint on which kind of elite occurs and which kind of a sahjhan is you want to put in your graph and then from these structures we study their algebraic properties how they are behaved what's the size of the graphs what's the connectivity structure of the graph like how many steps it takes from for getting from one point to the other and then it's based on the structures that we construct a critter graphing so when when we do crypto we were talking about huge graphs for example in psyche which is one of the most popular post quantum candidates as origin graphs are huge they have something like 2 to the

power 400 vertices 2 to a power 400 led curves that's 1 trillion more times than the number of atoms in the universe and there's about as many so Johnny's eyes Organists in total in the graph we consider so these are really huge graphs and the property we use from these graphs is something that's called expansion which is something that says that these graphs may be huge but getting from one point to any other point is very quick actually in practice for saga can take as few as hundreds of steps to get from any point to any point so you can picture this as a very strange warp the universe where you can go from

anywhere to anywhere at Lightspeed but finding your way out there it's immensely complicated I have sort of a like I'm taking a step a little bit back I sahjhan ease living between kind of the function that bridges between elliptic curves do these in the example you just gave is it like the Asajj knees create multiple elliptic curves or like I'm kind of curious like which comes first in that scenario the elliptic curve or the isogen II that's probably a very deep mathematical question what comes before in mathematics usually you start from axioms and you can struck all mathematics and in this sense neither a little earth nor as aaja knees have a

priority but someone is going to tell me I'm - yes I guess there's a question there of can you construct a elliptic curve from a nice ogyny like if you have one curve and the nice ogyny can you you know make a new one or do you need both curves to construct the ice ogyny that's those are very concrete questions which also have an algorithmic content like meaning that you really have data described in an azure journey and you have data describing allottee curve can you construct the other a little curve the answer is yes but also you have through a little curves and you

know that the reason I saw journey that's going to connect them then the answer is also yes you can construct others alternate so from a an algorithmic by computational point of view the answer is either way from a mathematical perspective historical reality curves come first but then modern algebra geometry came and the point of your modern algebraic geometry is always to look at the maps first and then at the object so I so Jenice would come first so it's really a matter of perspective and I I would say it's whatever you prefer in practice when we do crypto and so we implement these in computers you start from analytic curve and then you construct the azure journey and then

you construct the image a little curve I also read somewhere that like I saw genies only go in one direction so would you need to create maybe I don't know if it's correct but would you have to create two I sahjhan ease to connect and like to elliptic curves both ways so this is interesting because sure and I thought Genizah map so it goes one direction but there is a theorem very one of the first theorems you learn when you study as aa Jenice I was a kid when I learned about it is the duality theorem that tells that whenever you have an ISO Janee going from A to B you also have something that's called the

dual that goes from B to a and the composition of these two razajin is so going from A to B then back to a is something very simple it's a multiplication map okay your explanation of this this graph is interesting to me because it's it sounds familiar to a lot of other things that I've heard before I mean I directly related to like the way that file coin for instance construct there proves because they generate these massive graphs find one particular path delete all the other data and then it's like impossible to reverse this proof or like Forge the proof in retrospect sort of and and I like from just studying this but before hand I know there's some

relation here to lattices and post quantum cryptography you know and like I kind of see the this graph pattern appearing in general post quantum discussions as well is there a relation there if so like what is the relation you already mentioned that psyche this this thing that you were talking about is and like a good post quantum candidate so how do you achieve the the post quantum properties of ice our journey based crypto so the foundation of all isotonic base crypto is always a routing problem in a graph meaning that you have two vertices in the graph you know that there's going to be a path probably more than one path between them

and your goal is to find this path and as I was saying is very easy to you move fast in the graph but actually the hard problem is once you forget how you got somewhere it's very hard to find your way back so this is the main problem on which all post quantum is actually based protocols are founded because for VDS it's it's a different story but in the post quantum space this is really the main tool we have this hardness of finding a path between two a little curves in a misogyny graph this is a very different problem when you compare with lattices and code base crypto all these other paths quantum candidates each of these family has a

very different problem of a different nature you need to solve to break using your quantum computer in order to beat the cryptography so the analogies between a dodging ease and these other post cuantos candidates come more on the encryption side where the way you do encryption or the way you do signatures razajin ease is very similar to the way you do with lattices for example but on the quantum security level it's a really unique and I would say beautiful problem which is given to a little earth fine and Azure journey between them you mentioned that the crypto is based on this hardness of finding that path in the graph so is that thing comparable to like in more traditional crypto we rely

on the hardness of finding like two long primes or the discrete log problem is is that like the kind of core of a sergeant and based crypto I would say it's very similar to the discrete logarithm problem actually you can even construct a graph from so discrete logarithm problem is in a group you have some general G you put G to the power a you get some new element call it H and then now C in G and H your goal is to find this power a you used and actually you can construct a graph from the group and then you can express the discrete logarithm problem as a path finding problem in this graph so this is really analogous

you can make like this analogy really meaningful for the as ogyny based schemes so now that we've talked about this graph a bit and I get the fundamental concept a little bit better I'm actually understanding another thing that I read which was this key exchange you know story about people traveling the universe and aliens and things and it makes sense now that I know this is graph theory bit but that's all like a story to talk about how key exchange can be done in I saw Janine's based crypto but I mean we can probably read that

whole story here it's bit too long maybe but what is key exchange and what relevance does it have how do you do key exchange in this scenario okay the story you are referring to is something I've wrote for fun a couple of years ago and my goal was to be as close as possible to the way psyche works which wasn't a noble goal of making things easy to understand it was more just for the fun but I think we can just stay on earth without going to with aliens in space and explain how all this ice abyss Keys change work without having that complexity naturally we can just get

down to Manhattan I think so you know marathon you have all these streets and avenues it's very nice it's a lattice actually and so let's say that you want to go from Times Square to the Empire State Building makes sense so what you would do is take the 7th Avenue you would take it solved for 8 blocks and then you would go two blocks east on the 34th Street and there you are at the Empire State that's one way to do it but actually you have a second way to do the same it is you start from Times Square you go east for two blocks on the 42nd Street and then when you reach the fifth avenue you go south for eight blocks and again you are the Empire State Building

so this is drawing square in Manhattan as you can see it's either you go first East and after you go south and an East and this is the basic building block we like to use in mathematics well mathematician calls these commutative diagrams because you have essentially two ways to get the same result now think of these paths in Manhattan has been I so Jenny works so sequences of isogen is in Anna's autograph from Times Square which is an elliptic curve you go east then maybe you do it more complicated you go one block east one block south three block east four block south and then you end up somewhere and you can do this in many possible ways and the idea now is that

you will distribute this to the two players so in critter it's usually Alice and Bob so Alice will do maybe three blocks east and four blocks south Bob will do four blocks east and nine blocks south and then they will maybe text each other where their coordinates and then they will exchange positions and restart the same walk they made before so Alice will do again what did I say four blocks east and nine south and Bob will do the same he did in the first place and they will end up being in the same intersection of course now this is essentially what we do in as our geneva script oh except that the asaji graphs

are immensely more complicated than mannithen of course in manhattan if you are in Times Square and you want to know how to get to the Empire State Building you just ask Google and Google will give you the street but in a so Jenny graphs you don't have any Google to give you the these ways if the only things you know are the two places the one where you started and where not the one where you end it there is no easy way at least that's the hardest assumption there is no easy way to find a path between these two places but Alice she knew how to she got to this place so she is able to replay a similar walk which will be again three steps out four steps north five steps south etc and this way they both Alice and Bob can end

up find in the same intersection so this is essentially how all isogen abased key exchange work then there's variants on exactly how you construct Graff how these walks are performed how do you encode these works into into bits in the end but yeah the essential object is a commutative square something where there you have two different ways to reach the same oolitic curve using a larger knees and maybe I can add that from this basic building block of course you can get encryption that is similar to the way you do el-gamal from different monkey exchange and you can also get signatures that's slightly more complicated than in the discrete log

case but it's also kind of see that's the part where I get a little bit lost is that next step where this is then used for encryption wait like where is that part is it because it's like are you trying is it one single path that's impossible to find in all of these other paths or like what's yeah that part isn't clear to me so the way you get encryption from a key exchange it's essentially a generic way you can do it with any case change doesn't have to be this great lock doesn't have to be a little curves doesn't have to be as honest you can always do it and the idea is that in a key has changed Alice and Bob have symmetric roles where they both publish something and then they end up

having a shared secret in encryption you will make these rules as symmetric so maybe Alice has this table public data which is her public key and her secret is the way she got the public data so in the Asajj any case the public data would be analytic curve and the secret would be the iso Janee walk that took to the solid curve okay and then Bob would perform a key exchange with this public data of Alice and get some shared secret and this ref secret will be the encryption key for a symmetric encryption scheme you plug in and then you use symmetric encryption to do the encryption understand that's worthless so actually this is what really happens for classical encryption formality

curves for example in TLS when you do TLS encryption what's really happening under the hood is that you have an elliptic curve key exchange and then from that you derive a key which is the news for symmetric encryption another practical question for me is I mean I sort of see the the path that you would take from this fundamental mathematical property to the graph to key exchange to encryption I think that path is pretty clear now but what's still not clear to me especially like from an engineer's perspective is how do i construct these graphs I mean as you said there's like two to four hundred or something

different curves and and and I sahjhan ease I can't store two to four hundred different things on my computer so how do I pick which elliptic curves to go between and how do i know which i za Janine's exists to be able to go from one point to the other so you're perfectly right I'm not going to store the whole 2 to the power 400 elliptic curves in my memory that's does not the goal you you would have a starting a little curve which is something that's decided once and for all it's the same as in the film and key exchange where you have the public parameters the generator the group etc which are decided once and for all and in the Asajj nini case the starting

little curve will be some a little curve which has been chosen by us by those who make the standards usually we like to start from a very symbolic curve which has a question y squared equals x cubed plus X because we find it nice but you could choose other oolitic curves as starting points so that's the only vertex of the graph which that you know in the beginning and then from every little curve there's only a small number of colonists that you consider starting from that little curve usually you would consider 3 or 4 isogen ease and then what you do is that you choose one among these two three four I thought instead random and you do one step and then you keep doing this so you

I to rate these I choose one out of three one out of three one out of three and by doing this you will do a random walk in this graph and by doing this random walk so as we were saying before you start from the data including the elliptic curve then you figure the data encode India's our journey and that gives you the data encoding the new LED curve you repeat this process you will discover more and more elliptic curve but you will never discover the hole to do the power 400 that's not the goal you will do a walk which is going to be a couple of hundred steps in practice for as a genie encryption and then along this path you will have discovered a little curves you absolutely trash the dial the data about the elliptic curves you found along the way you just record how you did this

walk and then your public data is just going to be the end point of this walk I see that makes a lot of sense so my next question then is how expensive is it to construct these and mark that path of a couple of hundred steps and essentially like the general question of like how well does a sergeant leave a script or perform compared to other kinds of crypto there's two answer to that the first the commercial answer is reasonable entirely reasonable in practice when you compare with other post quantum candidates it's unbearably slow so to give you an idea to do to perform a walk which is 200 something

steps with the current C code running on modern CPUs and vectorized instructions all the possibility musicians you can put at the software level of course it would take a couple of milliseconds like two three four to three milliseconds which is reasonable for the applications you have in mind like TLS would be reasonable but it's two orders of magnitude slower even three possibly three orders of magnitude slower then lattices for example yeah it sounds entirely reasonable to me when you said unbearably slow it's like oh is this gonna take a couple seconds to do but a couple milliseconds is still yeah for

something like TLS that's completely acceptable I guess it starts you know becoming a questionable thing once you start getting into doing things like snarks and need to do many many many of these in in one round entirely but on the other hand and that's one of the main commercial points dajin is the data us change the public data that Alice Bob all the participants and is very small it's actually the smallest public data we have among all post quantum candidates so although that will may make for very slow protocols advanced protocols like snarks it would

also make them very compact which is probably interesting in in the blockchain space because if you need these data to leave on the blockchain then it's going to take lots of space if you use lattices or even worse code base crypto whereas with with a czaja nice you can be essentially at the same size as RSA encryption not as good as a little curse but like decently sized which is interesting of course the main blocking point for isogen is that we do not have efficient isogen e-bay signatures and usually in block chains you are more interested in signature as a primitive than in encryption so next up we really want to start talking about like how these relate to like some specific blockchain topics that we've

maybe covered in the past but before we do that there's another word that I would love to define because I see it pop up throughout the literature on this and that is the word super singular this a super singular curve what is that word and what does it mean okay that's that's a funny question I'm I don't think any definition I can give you is going to be very enlightening but I can tell you what it is not first of all super singer that doesn't mean that it is very senior super singer means that these curves are rare so there's if you fix a finite field that's usually where we do ISO

Geneva's crypto if you choose any finite field and you take the algebraic closure this planet field okay probably not everyone is familiar with this concept but the algebraic closure of a field is the same thing as the complex numbers are to the rational numbers say like I hope no mathematician is listening it at this point but think of it like that so there's a infinitely many elliptic curves when you go to the algebraic ruler but there's only finally many super seniority curves in total so that's why we call them super singer because they are very rare and they are so rare that's actually something that's conjectured Beha a hard problem algorithmically to pick super senior

curves at random we know a few special super seniority curves like the one I mentioned before y squared equals x cubed plus X and we know lots of other very special super senior curves but then if we want to discover more super cing aircrafts the only way we know is to do this isoh Janee walks and this is of course enough to discover them all because these graphs are very compact very well connected so you can get anywhere as I said but of course there's too many of them and you're never gonna map all the space but on the other hand of all the possible elliptic curves that you may find just by taking curves at random the chance that you end up on a super singer course are very low okay so

this is to explain the name now why is this important for of quantum crypto not that much actually you can actually do post quantum super Geneva's crypto from ordinary reality curves actually that was the first proposal for isogen e base crypto the only thing we use the only reason we use super singer curves for is that we do not know how to do efficient eyes watching base cryptography from ordinary curves for so far we've only managed to do it with super singer curves because these curves are very special they have lots of very special properties which make them very nice to work with we've sort of as you described Fredrik we kind of have done the walk from like what I'm gonna use that term

now - I know it's few strong but anyway we've we've done we've followed the path from defining what they are to this key exchange story and you know how that relates to encryption but how does that all of this then relate back to that earlier topic of VDS this is sort of where the whole at least for us this is where this topic kind of came out of now that we're here I'm actually I forget from that interview they relate and I'm super curious like how did those and two things then come together PDFs maybe we just redefine it here verifiable delay functions it's like a function with a delay built into it so that there's it like something will not happen immediately but what rather will be delayed by a certain

amount of time you can think of it as a single threaded proof of work something that will take some amount of time but you can only do it you know in a single thread doesn't matter if you throw more hardware and it's still gonna take that same amount of time and you can efficiently verify that it was done at the end I can perform so how the hell does sergeant leave a script I'll play into this Oh actually if you want to move to V DFS now there are some connections of course because we still work with this super singers autographs but the way I surgeons provide this delay property is very different and actually requires us to be more specific

give more detail on what an eye surgeon is for a computer and how we compute them got it maybe we can start there which properties of isogen ease or which characteristics or what what part of AI sadja needs do we need to focus in on in the vdf context so if you recall when I define an ISO Jenice I said that it's a map from a little herb stole it a curve so the very important thing is that it Maps points two points and when it does this mapping it also does it by preserving the group structure so that hydrogen's a + isogen your V is equal to a certain of a plus B now if you want to understand why haja knees are useful in delay cryptography we we need to

understand what it really means to represent an azure journey in in a computer and what it means to compute the as a genie compute the image curve of the as ogyny and evaluate the azure genie on a point of the elliptic curve so an illusion is not so complex an object it's just a couple of polynomials usually a pair of polynomials or four polynomials depends exactly what you want represent off the erogenous so you can just think DSR genius being a polynomial they x squared plus 3 that's a polynomial that can be an azure journey and so that's that really links back to the way you do VD F's because if you think of it the FS there is one important polynomial

I'm thinking now of group-based VD f like the velocity of the pizza construction what you use is a group of a known order and the function you either it is this X square function of course X square is a polynomial and here when we do I so Janee based vdf we're really using these isogen ease in place of this X square function except that now there is no group of a known order we are using different properties but the idea is pretty much the same Hajin is come with an invariant which is called the degree which is very similar to the degree of a polynomial so the Polli the degree of the polynomial x square is 2 and we will use as ordinates typically of degree 2 as a delay

function because like for the polynomial X square we conjecture that there is no easy way to do repeated squaring then just doing one squaring after the other and in the same way for Asajj this we conjectured that there is no easy way to do repeated evaluation of Izod needs of degree 2 then going through one as ogyny at a time painstakingly until we get the final result so when we do delay functions from misogynous we're really using a chain of I thought leaves a nice origin you walk in some graph and we need to encode this sog walk so we will need to know where we started from which curve we ended up to but also how we get

from one point to the other so all this information is going to be the encoding of our sequence of messages of degree 2 and now we are going to take some point on the starting curve this is going now to be our x point and then we will pass it through this chain of isogi's so it's like taking x 2x squared 2x 4 2x power 8 etc except that now we're doing points X goes through first isogen e gets to summer it occurs then goes through some saikhan misogyny gets to some new led curve etc etc so you repeat this operation enough times and then you get this delay that you conjecture is impossible to compress you cannot skip steps you

cannot find a shortcut in your eyes og graph that will take your point from start to end in any faster way is this then a time delay like by delay we're talking about like time actually because of these transitions because of these jumps is it because of a certain amount of time it takes to compute them or is it because is it the actual steps that is the delay it's pretty much similar to the group-based videos you when you want to decide when you want to determine how long it would take to evaluate this function you must measure how long it takes to do one squaring and for this you will evaluate all possible algorithms you know to do squarings and then you will find the best one

implemented on the best hardware and that will be your unit step and then if your unit step takes one microsecond and let's say you won't have a delay of one hour you will do what's 60 times 60 times a million steps to to get your one hour delay so it's pretty much the same for razajin ease you need to estimate using the best algorithms you have how long it takes to evaluate one isogen you of degree two and then let's say that takes one well most likely 100 microseconds and then you will iterate these millions of times so that you get the delay you were

aiming for got it cool I mean this is really helpful actually to understand how the I saw journey vdf delay like how the D in the vdf is accomplished with these multiple steps and like with them done like to a certain degree or a certain amount to reach a certain time delay but what is what about the V in the VDS the verification does that also change in a nice our journey vdf versus a group of unknown order style vdf extremely different okay Ashley that's one of the nice features of I certainly base PDFs it is that in group based PDFs whether it's the velocity proof or the

pitch sacrif you need to produce a proof that means that you have this delay function that is repeated squaring and this delay function will produce its output but then next to the output you will attach a proof which convinces and interactive prover that this this output really is the output you were expecting from the input in as ogyny based VDS you do not need to attach a proof actually the output is self proving which probably not the most important property on earth you can probably live very happy with group-based PDF and this producing this proof is not too expensive it's reasonable but at least mathematically

it has some beauty in it because just seeing the output proofs itself so this is something that we call perfect soundness in the in technical terms and the way you you can verify that this is really de output you were expecting is maybe a bit expected if you are used to a little curve cryptography and related topics you use a pairing so for example the very pairing or to come back to and Ravel yeah this amends a father of elliptic curves as organist and all this stuff so of course you heard about pairings because they are a fundamental object that's used throughout all these

starts snarks etc actually the way we got to our vdf was by taking a very well known pairing based scheme which is the bony lean chatham signature scheme and replacing so in this bony lean chacham what you do is that you have some point on an elliptic curve you have some message you want to sign you include this message as a point on the elliptic curve to then you have a secret scalar you multiply the message by the secret scalar and that's your signature and then you can use the pairing to verify that the signature on the master checks with the public key that's how the LS

works and we just realized that ISO Jenice can be used as delay functions and actually something that we knew is that ISO Jenice behave a little bit like scalars actually pretty much like skaters so we simply took the BLS signature scheme and replace the scalar with Una's ogyny or more precisely a chain of degree 2 and czaja knees and then used this pair in equation to verify that indeed the output of the delay function is what it should be so this is all related to the by linearity of the valley pairing or any other pairing actually can be the Tate pairing and so this by linearity is this property that it's a little bit

like a generalization of multiplication or of the determinant of a 2 by 2 matrix if you wish where you have these two elements a and B and you want to compute pairing of a and B and then if you multiply a by a constant this constant can be also multiplied in front of P it doesn't change the result so pairing of C times a and B is the same thing as pairing of a and C times B this is how a by linearity works and for isogen is actually you have the same property where you will put d as our journey in the pairing equation so it will be pairing off isogen e applied to a and B is equal to pairing of a and and

here the interesting part comes the dual of the azure journey applied to B so actually this is also one of the possible way to define what this dual I saw trees that we mentioned before is that you allies dajin is d adjoin with respect to the pairing so all these fancy mathematical words but which really say that essentially a nice our journey is behaving like a scalar multiplication for this Viper so this is really what we use when we do the verification in the vdf all you need to do is take the input point take the output point use the pairing and check that the value of this pairing is equal to the value of another pair in you'd competitor beforehand and

you know he's going to match it's really cool and I guess in a group-based vdf the proof that you produce is probabilistic if I recall correctly and that's I guess the beauty here is like you say probabilistically you know the probability that that proof is incorrect is so low that for all practical matters it doesn't matter like no one should care about whether that's probabilistic or not mathematically it's really nice that you did not have it probabilistic at all it's absolute it's better than that actually there is no probability of the proof being false if the proof checks you know that the output is right if it

doesn't you know that the output is wrong but don't get too excited I mean the a probabilistic proof with a exponentially small failure probability is perfectly fine for any kind of cryptography so this is a neat mathematical property but is not the game changer yeah yeah so one question that I had and I don't know if like it hasn't really come up yet I don't think but it's this idea of AI sahjhan e's having something to do with like randomness generation is there a connection there so there's many different answers to that on some level any vdf can be used to generate distributed randomness I think this was already described in the episode you had

with bono on the vdf where he exactly made that example of using a PDF to to have the distributed generation of randomness so in that sense if you have a vdf you can generate randomness another way as ordinates are related to randomness is this fact that isogen grafts are expanders and that being an expander is really a probabilistic definition which informality see in probabilistic terms means that when you do a random walk in the autograph the end point of the random walk very quickly converges to the uniform distribution expander graphs have

already been used in theoretical works on randomness so you could want to use those particular isogen business plan their graphs for randomness generation but probably that's not a very good idea because it would be very slow compared to other expander graphs we know got it something I've stood we I've actually been trying to do this with a few of the last episodes that's like bring in some questions from outside through conversations that we've been having maybe around some of these topics so I have two questions from Taryn sheet drive who's been on the show a couple times and I've mentioned some of his work a couple times well he had two questions that I wanted to ask you one is will these signatures ever be

practical and the second is do you need custom hardware to speed them up okay I'll start with the first one signatures I hope so there's okay I'm gonna guess break the news but there's a new paper coming out pretty soon that's going to present a new senior scheme based on a certain ease that's going to be the best so far from some points of view still not going to be your favorite signature scheme I am afraid it has lots of nasty properties so it's we're not there yet but hope some day yes we we know why

this so difficult to make good at dodging eBay signature schemes because we've always been thinking of haja needs as being a Jew realization of discrete log but a much more constrained one and so all the nice properties of this gridlock which enabled signature schemes like sure don't work for us or I mispronounce the name so all the nice properties of discrete logarithms that make for good signature schemes like snore don't transfer to as dajin ease so this is really what's blocking us at

this point but there is no fundamental reason why you shouldn't be able to do it it just seems to be very difficult we need to understand better and learn more about those origins to do good signatures but yeah I'm afraid not in the next year sorry what is that that paper you just mentioned when do you think that might come out roughly a couple of weeks if we buckle up okay well it's possible that this air is actually when it's out so if so we'll add a link in the show notes and even if not I'll add it to the show notes once the paper comes out so if people listen to this in the future they can hopefully find it and so what about that second question do you need do we need custom hardware to speed these up or is that

something desirable actually it depends on the application you very definitely want custom hardware for vdf but that's true for any vdf you want to design hardware specifically for the operation and here's where I za Giannini based VDS may be interesting is that for example compared to clasp group-based vdf you can essentially reuse the same trusted hardware a dedicated hardware you are designing for our essay based vdf because essentially the operation is evaluating a polynomial of degree two or maybe two polynomials of degree 2 modulo a prime P so this is very similar to compute in X square modulo n so it's

going to be essentially the same kind of hardware although you can do some specific optimizations because the modulus is going to be a prime which you can control less so you can choose a prime which utilize for in contrast in our essay based vdf your modulus is going to be a product of two primes and the composition the composition is going to be a secret so you can't really optimize that but for other applications of course it's going to be interesting to have good artwork there's people working intensely on having dedicated hardware for implemented psyche for example but you are not going to see that anytime soon in CPUs for example accelerated instructions to do till the

TLS dies dodging the base key exchange I don't see that come in any time soon but the rockers help but for some specific applications where you really want to use ice dodging is because of their short skis short public keys and then speed is critical then you definitely have an interest in this in developing no dedicated hardware so for the signature you mentioned some nasty properties on one hand I'm curious what those are but another thing I'm curious about is speaking of nasty properties is trusted setups it's something that keeps coming up again and it's something we talked about in the video setup as well where RSA based ones might have it or like a class group based ones don't and

that's why people want to go that direction and try to optimize for that so what's the what's the scenario here unfortunately that's one of the nastiest properties of the iso geneva-based vdf you need the trusted setup at the moment for the iso geneva TF and the reason is pretty similar to the reason why you need a group of unknown order for group based vdf essentially when i said that your delay function is a long chain of Asajj knees this means that your delay function is a very long walk india's autograph so this very long walk is going to be much longer than the

shortest path between your two endpoints so if someone was able to find the shortest path then this person could evaluate the delay function much faster and now here's the catch if the elliptic curve you start from has some norm structure and to be precise this no structure is going to be a known endomorphism ring i'm not going to explain what the endomorphism ring is just take it as knowing the endomorphism ring is analogous to know in the order of the group in the group base PDF so if the starting allottee curve has this property it is known structure property then from the description of the very long walk you can delete the description

of a much shorter walk and this way you can break the delay property so the only way to have a secure as Archana vdf is to is to start from analytic curve of unknown endomorphism ring and that's where we are at we have a problem we do not know how to do that the only way we know to generate a little curves is either take some very special ility curves y squared equals x cubed plus X but in that case we do know the endomorphism ring or start from these curves and do a random walk until we find some random a little curve in the graph but the person who does this random walk finds by this random walk exactly the same information finds the

endomorphism ring of the arrival curve so whoever is performing this random walk is going to break this unknown endomorphism assumption so we need a trusted third party to perform this random walk to some random super singer curve in the graph and then forget about this walk and provide this publicly random elliptic curve to anyone now this is not a fundamental necessity on some level we do not see any reason why it should be so this is unlike the RSA based vdf where it's clear that you want an RSA modulus and so someone has to

generate it and if someone has to generate it is someone must be a trusted party here there is no fundamental reason why there shouldn't be a different way to generate oolitic herbs that does not give information on the elliptical on the endomorphism ring however we do not know any algorithm of this sort so we are still looking for it actually that's one of the problems that excites me most at the moment but for the moment every efforts have failed and the other thing that must be said in comparison to the RSA based trusted set up is that in RSA trust it's setup you want to generate this n product of two prime numbers in a distributed way so that you spread the trust over multiple

parties but this is a very complicated protocol whereas in hazzard rebase pdfs you can very easily distribute the trusted set up in an incremental way which is something very simple you have some party start from the speciality curve and do a walk to some random curve and then publish a zero knowledge proof that you really did the random walk to this curve then some new party can come in and repeat the process by publishing a zero knowledge proof and so you can have at anytime any point in time many different participants engage in this distributed protocol of generating a curve of unknown order and if only one of these is harnessed and destroys its information then you're done you're

secure so this is a very easy to implement trust it's setup it's updatable meaning that let's say if you Irma's done this now you can start from Ethier m trusted set up and do your own trusted set up so that you accumulate the trust in the theorem set up and your own set up and actually this is something that I'm working on with some people at the white tree foundation cool very cool yeah I was going to ask if there's an NPC to produce that yeah curve of unknown order but you cut ahead of me and answer that anyway it's great so I think we're pretty much a time I actually have a feeling there's plenty

more we can talk about but I do have I have sort of one last closing question and that's so far we've talked about ice our journeys like you know what it was and in the context of blockchain but I'm sort of curious like does does this kind of research also exist in other fields that you're aware of is this like a broader mathematics ounds like a broader mathematical topic that could be used in all sorts of things you mean ice our journeys outside of cryptography no I mean ISTAR journeys outside of blockchain to answer your question isogen is of course a very fundamental mathematical object and when we so far we have been talking about ice dodging

accessibility curve but of course there's much more out there than a little curves there's hyper-reality curves there's general a billion varieties and even in those contexts you can define as our journeys and there is research on the algorithmic aspects of higher genius curves and there is aa Jenice and how they can apply to cryptography we already have some papers on this it seems much more complicated we know much less on these higher genus scientists so of course it's mostly exploratory the same way that genes to cryptography has been exploratory for ECC in the past twenty years so in the future we may see more things coming out of more general notions of misogynists of course you will always be a very fundamental topic

in mathematics and eyes organists are going to leave against their own life outside of blockchains because post quantum crypto is now a fundamental topic in and out of blockchain and we can hope to see delay properties used for something else than block chains and on that space I thought it seemed to be a very powerful tool because you can combine this isoh genie based delay with this pairing based verification and pairings are so powerful that maybe you can do more than just PDFs actually we know you can do more than just vdf to already have some examples cool if people want to find out more where do they find you or your work I guess people can follow me on Twitter

Luka underscore DeFeo I have a webpage where they can find links to my papers um I would recommend people who are interested in post quantum crypto to visit psyche dot org so si que e dot org which is the official website for the post quantum candidate where they can find more information on isogen e based or otherwise only based protocols some colleagues have been registering domains I think there is a nice organist org domain I must check and that's also a very good source of information we'll add those to the show notes cool well

thank you very much for joining us on the show it's been enlightening and I hope it has been for our listeners sue thank you and to our listeners thanks for listening thanks for listening [Music]