07 Recap

uh okay uh I guess we can start um so uh welcome everyone I'm I'm atan um mathematician that transition to cryptography a few years ago uh before that I was many years in in Academia um this course is um is a second er a second version um there was a course that started in August last year um and is is now pretty Advanced let's say in a month and a half I I expect that we start a proving the the properties of the whale pairing um so all in all it would be like a year and three months to cover the material IA and and that's that's roughly the estimate for this course as well um what happened with this course is that we started a um a hybrid version in which we I mean we meet in the etherum Berlin office ER and there are like um participants from the office but but also online people ER and we realize that we don't have a lot of er a lot of people ER participating ER keeping in mind also that people tend to drop out at some point and that's why we advertised it again and um it's good to see you guys I hope many of you will stay um and so what what is generally planned is there are YouTube videos of the of I think six sessions that we did um each of them is about two hours video um and I have to go to a a conference uh next week for about three weeks um so we we rejoin or we start again in about a month from now I think it's like uh August 9 August August 8 dat um and what I want to ask you is to um view I mean watch the videos ER make some questions if you if you like we have a Discord channel so I I will still be available to answer questions on Discord um then when I'm back I think we can do maybe a another recap session and or or even two and uh we start from where the the videos stopped which is more or less caution groups now in in the first video in YouTube I I say what this course is about but ER let me repeat um there is somewhat of a gap up in the literature um concerning pairing based cryptography mathematics um the reason is that elliptic curves are usually taught at um Master Level in pure math and if you try to read the mathematical literature it's not Elementary it it assumes you have an undergraduate degree in in math which is quite a lot um and on the other hand the cryptography literature um is Elementary but it doesn't give you the proofs H so so this course is designed to ER to fill in this Gap ER which means we do almost all the proofs ER it really means that ER you get at the end of the course you get um let's say up to a an early research level in paring based cryptography and now you can ask why do you need it and it's a valid question I mean ER the weak reason you could say is that ER if you really want to know that something is true you want to know the proofs but it's kind of a weak reason because you you you can believe many decades of mathematical Community deliberation and you know it's it's it's pretty solid as it is now but I think the the strongest the stronger reason for making the effort in learning the proofs is that that's that's really the way to learn how to reason about these um mathematical objects and er eventually once you once you work with the paing based cryptography protocols you might you might need to tweak something you might need to look at something else that is not in the protocol and and for that you really need to to reason about these Notions um now the the course is designed um for people with only High School background but it takes a significant mental effort if you don't have the background um which means you need to I mean apart from the the two hours weekly session to go over the session let's say one or two hours in addition um there are no certificates no exams H so it's it's all about you and what you want to learn um but keep in mind that H it's not it's not so good to me sessions if you again if you don't have a a lot of background because things really ER closely rely on each other and ER you you kind of you lose you lose the the Rope very quickly if you if you let's say don't come to the session and then also don't watch it on YouTube um the basic template of um almost every mathematical ER text is a definitions or constructions examples for these these new Notions that the definitions talk about and propositions theorems definitions you need to you need to remember because whatever we talk about ER would rely on on a certain definition I can remind you and and I will do it often but eventually you need to remember the definition of course it over time if you you you follow the the string of the story it's I mean you kind of you tend to me to remember the definition because it's it's being used a lot time the proofs you need to be able to follow every step of the of the proof so it's it's a bit like a I mean the ideal ER the ideal situation is is um when when it's airtight you you understand every step of the proof and and the conclusion ER if a little bit of erir ER goes away it's okay but if too much you you can't fly now apart from this because eventually we will get um into it um somewhat Advanced material in in math it requires maturity and maturity is is kind of understanding why certain definitions are made I mean usually definitions are in close tie with propositions and theorems I mean you want to define something that will be eventually well behaved and maturity is is a matter of experience so of course if you don't have background it will take take you time but I think that a way to accelerate the maturity is to have some kind of a good philosophy about what is going on so I will often offer my my take of the the a little bit of philosophy you can you can have yours and so on but I think think it's worth to um to make some room for it ER now the best way to learn is to ask questions and you you could say there are a strict strict kind of questions which mean h whether something is well defined erh or why a certain step in appr Pro is true ER and there are soft soft kinds of question which are um what motivates the the discussion the definition the theorem um H how to get a more conceptualized understanding and and of course the more questions you ask the the the better you learn and most importantly H you you should put your ego aside and not be ashamed to ask silly questions it's the best way the quickest way to learn um people among you that don't have background may have just questions about ER notation about terminology and so on all of that is welcome I just ask that we do um you raise a hand when you want to to ask something then I can hear it and and I'll be happy to to have many questions um I think that's that's about it from uh from my side on the on the course do you have any questions okay so ah one thing I forgot to mention H but it's written in the announcement and so on on um there are notes for this course um it's a it's pretty much in a in a form of a book um I will I typically follow closely the the notes and you can always find an updated version on my website and and I strongly recommend that you uh take a look at the notes um you could even do it while the while the the session is going um there is I mean one disadvantage of um what I have in the notes is that there are no there are not not many exercises ER the re one reason is that ER especially in the advanced part because we follow a a non-conventional path it's not so easy to to find exercises I mean the the ones in typical math textbooks um might be out of reach for you because we didn't follow the path that the the other book follows um but also I think o over time I H I will add some exercises um it's good to do the exercises and I I will sometimes ER mention exercises um as part of the the lecture um but because of time limitation and so on I cannot give you much of a feedback on exercises so that's that's one of the the disadvantage of this course ER nevertheless I in my experience it should be possible um although challenging it should be POS possible for um average person that has a high school background to to follow the entirely H yeah so that's uh that's about ER the generalities of the course um to can we do a quick vote of um who H actually ER watch some of the videos uh let's say um maybe you can write something in the chat okay and do you do you think you you can um I mean in the the coming month you can watch this six videos yeah we can do one I mean we can postpone a little bit U um the next session if you want or we can do I think what we can do is a um on August 8th I I do a recap or Q&A and recap [Music] um and then you have another week ER to watch the I don't know the remaining videos you didn't watch and so it's it's almost a one video per week and and then we can we can start again ER okay now as for the M the material is all um it should it should be all um Linked In the Twitter post that we had a while ago um I I will there's also a Discord Channel um I don't have the links with me at the moment but um if you are registered then we have your emails and you will get it from there or or maybe someone here in this call have have the links and we um and can send it in the chat maybe hang on okay I think I found the link to the YouTube videos this is the basically the the ethereum foundation Channel on YouTube and and this is the link to my website okay so um so what is an elliptic curve you you know that um I assume that most of you have have SE have seen it before that um if I take a prime number P and I take all the numbers up to P minus one I I will call this thing FP and on FP um we have a um two binary operations that that are addition modul p and multiplication mod P H modu here means that I do um I mean modulus is like a clock arithmetic so you know that if you if you have a time 11 Plus+ two then it's it's one it's because we do I mean so clock arithmetic is modulus 12 I I do addition or multiplication of the the clock hours and uh ER I reduce I mean I I remove all the the multi I mean the maximum maximum amount of multiple of of 12 from the result and and I I remain with a a some number between um one and and 12 and 12 is let's say not included H but you can do this for any for any positive integer I mean I can do so modul two would be I take um num the the number Z one and I can do addition multiplication module two I get this the usual binary representation um but if I do it for a prime number um then this addition multiplication they um make FP is called a field the main property that a field a field has and and um in if p is not prime we we will not get it is that mainly uh for any nonzero element in FP H there exist some element which I denote as a minus one such that a * aus1 is equal to one mod now an elliptic curve is an equation of the form Y 2 = x Cub + a x a x + B and there is a question of where the the the constants A and B come from so um if a A and B are real numbers then I can look at the the solution set of this equation the solution set is a collection of pairs X comma y that satisfy this equation so let's say the the solution set of e is the set of all pairs X comma y in the two dimensional plane R2 such that y² equals x Cub + a x + b if you want maybe a more Elementary example um I I can take a let's call it P ER p is the equation Y = x² and I can take the solution set of p over the real numbers this is the set of all pairs X comma y such that Y is equal to X x² and and if you draw p on the XY plane then you get a parabola so this is typical um in in a field called the algebraic geometry that we we look at solution set of pols but polom is not necessarily in one variable usually in h two or more variables and the solution set of of such a pol a polom it it has a geometry usually um so elliptic curve is another polom in two variable and if you you look at the solution set over the real numbers ER you get a picture like this um and this kind of object is is special in the sense that um it has a binary operation on the ER the points of the curve ER the binary operation is quite simple I mean h you let's say you take two points Q or let's say p and Q you you draw the line between p and Q this line has to intersect the the curve in a third point which I would call P star Q the reason it has to intersect the curve in in another point is is because of this this three here I mean what we have is a a degree 3 polom and degree 3 polom typically it intersects a line in three points just like here a degree 2 polinomial would typically intersect a line in two points so in the elliptic curve I um I take this h two points p and Q and I draw the line I know that it intersect the curve in another point and since the curve is symmetric along the x-axis I can reflect my result and this is called p+ q and it's a um maybe a surprising effect and it's it's pretty not pretty non-trivial to to prove that what you get here is um an a billion Group which is a notion we we didn't discuss yet but a billion group is um is simply a set together with a binary operation that um satisfy natural axioms um so the the the typical ailan group that you you know are the is the integers um the integers Z is in the B grp and and so what we get is um it's it's interesting object because on one hand it has a geometry and on the other hand it's it has an an algebraic structure this aan group so this is um algebra geometric object and it turns out that not only that it has this a bilan group structure but the the ailan group resulting from an elliptic curve has a a additional properties that most ailan groups do not have and that is this um bilinear pairing and so the reason people are interested in elliptic Curves in in in cryptography is well first um because this is one example of a group and groups are um used widely in cryptography but second the the pairing that the group of an elliptic curve admits is um give you um um possibilities to design cryptographic protocols ER that you could not do with just a regular a bilan group um and so it it became actually even in um in ordinary cryptographic protocols that only involve groups people tend to use elliptic curves quite a lot or at least that's what I hear from Dan B ER and then in in many in many parts of cryptography that um use pairings I mean elliptic curves are are essential I mean there there is no other way there is no known other way um to use pairings without Li cures so okay so this is I mean this is where we're going I mean we will try to um er understand these these objects um and eventually Define the pairings but in order to do this we need um quite some background of course it is a I mean it is designed I mean I I I designed the the the lectures on this part so that only the necessary background almost only the necessary background would would be presented and and of course you can read about it in the literature if you want um but what we need is um first we need to learn about a um the basic syntax of mathematics and the basic syntax in modern mathematics is a a set theory so in set theory um you have a you have sets a set is a collection of objects let's say a set s is a collection of objects and such that for any object x h in universe and we can say whether X is an object of a sorry of s or well and and this is denoted X belongs to s or M X is not an object not a I guess element here is is a better term is not an element of s and this is denoted as X does not belong to s h and then set theory has a certain syntax that you need to to be familiar with ER set theory has generally two ER two versions I mean you have axiomatic set theory this is a logic and this is something we we will Skip and you have naive set theory which is a um essentially the the the syntax of set theory explained to use it on a on a regular math discussion um the second component that we need so so we we um the the videos talk about set theory a little bit then um the important part in set theory that I would recommend you to H to pay special attention is this um equivalence relations equivalence relations is a a procedure that allows you to H kind of glue um certain elements in a set and get a um a modified quotient quotient set with respect to certain relation so I I will not give the definition here but maybe intuitively you can understand it by an example and the example is you take s to be the integers and um you can declare M A and B in s to be equivalent if or if and only if this is by the way usually abbreviated as I FF um and I declare a and b to be equivalent if a is equal to b modul n that is if um if after I do long division of a by n and of B by N I get the same remainder right I can always write a is um some kind of Q QA time n plus some remainder let's say remainder of A and B is some QB * n and a is equal to B module n um by definition if ra a is equal to RB as as integers and and then you can say okay so after I have this equivalent relation or after I declare two elements to be equivalent two integers to be equivalent if if and only if they they are equal modu n what do I get when I quot out when I mod out the this equivalence relation I mean I want to to look at the integers um from the from the the point of view of this relation so I I don't care if n is equal two or let's say yeah if n is equal two I don't care if you talk to me about about two or about four or about six they're all equivalent mod so when I when I contract a this equivalence what I get integers contracted by this modul and relation is what is usually denoted as ZN and here it's one one way to represent it is to look at the numbers zero up to n minus one and this is a an exhaust exhaustive list of Representatives for integers mod n because every other every other integer would be equivalent to one of these elements in this list modu n h so you see equivalence relations allow you to um to make an important construction that we will care about and this is one example but there are many many more examples of equivalence relations um so I I suggest that you pay special attention to this topic [Music] um any questions so far before I I get to the second second component of er okay so so the the second ingredient that we have in a um also in in the YouTube videos um we start to talk about H groups and I think many of you so er so so er things about groups before ER it's very typical for people who who do cryptography but nevertheless it's it's good to um to do a review of um what we talk about when we call I mean when we talk about groups that is one thing to notice is that not every group is a billion so a group is a billion if the binary operation or let me take a step back so a group is a set G with a binary operation um typically denoted as a DOT ER so so thought I did not Define it but when I say binary operation this means that I take two elements in the ER in the set G so the collection of all pairs of elements of G is is denoted as G * G this is a another thing that comes up in in the part on set theory this is what is called the cartisian product and a binary operation is simply a function from the cartisian product of G with itself into G and a group is a set with the binary operation um and a specified element which I denote as one H such that um you have three natural axom one is that for any a b and c in G if you do multiplication in this way it's the same as doing multiplication in the other way this is called associativity and and if you think about it associativity is something that we almost always want when we have a binary operation because once we we start to get equations um or or expressions of complicated things that we did with the the binary operation we want to know that um it doesn't matter where we H put the brackets I mean if we know that this axium of associativity holds then we can write a * B * C and this is a unambiguous I mean whatever place you put the brackets you get the same thing so this associativity is a crucial crucial axom for pretty much any binary operation we have and as a a funny thing I mean if if you look at the homomorphic encryption schemes ER they were unable to to make Cipher text multiplication associative so this is one of the the biggest drawbacks in current schemes is that you don't have associativity of a multiplication of Cy text the second the second axom of a group is a I guess you can call it unitarity so let's say the the the operation is unary if for any a in G A * 1 is equal to 1 * a and is equal to a and the third axom is that um for any a in G there exist some element which we call a minus one H such that a * a - 1 is = to 1 so this this is usually called a multiplicative inverse um what I want you to note is that we do not assume that the group is a billion that is um a group is it billion if for any A and B and G a * B is equal to B * a and er part of the the ER the development of groups that I do in in the YouTube videos do not assume that the group is is a billion now in cryptography and especially in pairing based cryptography we use almost only a billion groups but nevertheless we we sometimes use non ailion groups and it's important to to understand a little bit of more General version that is a a a group that is not necessarily a billion and um after a short while I I just um talk only about a bil groups so pay attention to ER to this this distinction um yeah I guess uh usually what we do is I take a a 10 minutes break after an hour and then we we continue but maybe now is a good time for questions if you have anyo what do you think hey um yeah I have a lot of ketchup to do but uh some of it makes sense yeah can can say again I I couldn't hear you well okay so um all right let's H let's take a let's take a break and and we meet again in 10 e e okay so er maybe before I start again do you have any questions on what what we what I said earlier yeah but speak up Emanuel Emanuel can you uh okay yes um we will of course so um one thing that we still didn't cover ER I mean it's not covered in the YouTube uh videos H but it will certainly be covered is um is this notion of homomorphism of of groups then and and this is like a repeating repeating theme in what we what we will do I mean once we have a notion in this case a a group we want to to be able to move between two instances of this notion so um let's say um if G and age are groups let's say G is given by um I have multiplication in G but I have also one in h so I I disambiguate it by by this notation and I have a unit element in G but I also have one in age so I I call this one one one subg yes typically people write it as a as a as a top like this and age is the same I I have the set the binary operation and the unit element uh homomorphism um from F to G sorry from G to H is a function f from G to H such that for any A and B in g f of a Time B is f of a but here the the multiplication is in G this is f of a multiplied in h by F of B and let's say um f of the unit element in G is the unit element in h and a f of an inverse of an element a multiplicative inverse of an element in G is equal to F of this element and then applying multiplicative inverse in h so a homomorphism is is the natural notion that we want if we um want to a function between these these two groups two instances of this this notion of a group that preserves the structure or is a compatible with the structure so compatible with structure is is expressed by these three conditions and what will happen with almost every notion that we get our hands on we will want to to have a a notion of a like a morphism between two instances of this notion and this will be true for of course for groups it it's it's also true for sets sets they have no additional structure so as a morphism between set is just a a function ER but we will talk about Fields H fields are um it's like a group it's it's a set a with binary operation but it has two binary operations you when when we typically call them multiplication and addition and these operations need to satisfy some axioms and after we Define the notion of a field we will have a a a a notion of a a morphism between fields that is a function between the underlying sets of the the fields that preserve the the structure um and later on we will we will talk about elliptic curves but again if we have two instances of I mean we have two elliptic curves we want to know what is the correct notion of a morph between elliptic curves so this is a repeating theme in in all all this course is that we want to not only have a a a not only study a particular instance of a oce but rather the interaction between various instances and and for that we ER we need a notion of morphisms ER is this answering your question Emmanuel well I'm I'm I'm trying to understand what the what you're what you're after but I don't I don't quite get it I mean um obviously understanding homomorphisms is important in ZK um er when you say to go from the structure of vector spaces to polom ER it's not quite clear what you mean I mean Vector space is a is a I mean one one kind of notion that actually we will mostly avoid um and a polom is on on a different level of resolution I mean okay okay uh I think I think I I understand what is the what is the gap here H but this I should say I mean this course ER will not review ER specific Protocols of VK ZK or otherwise we do the math it is mostly pure math we will do a little bit of algorithms but er er for sure we will not cover a ER specific protocols ER I mean the the the familiar ones snarks and Starks you will I mean you will be able at the end of the course you will be able to to read this these protocols yourself and understand all the mathematics but of course the mathematics is not the only thing and there are many questions on implementations and and so on um so that's that's kind of the the limitations of what this course offers but I can assure you Emanuel that you will you will understand polom and pairings and and so on if you to follow yeah go ahead uh okay yeah homomorphism is important to any almost any anything you want to say about either groups or um fields or elliptic curves you need homomorphisms it's not a big it's not a big deal I mean the the definitions definition of homomorphism I just gave here it's a it's very easy to or rather easy to to understand but you want to ER you want to get familiar familiar with or comfortable with the notion ER so that you can use it in various situations and we will have many examples of homomorphisms and so yeah so this this is coming up other other questions Okay so so this is groups um another thing we will talk about is a Fields this is not this this is not something that is is part of the YouTube videos um at the moment so you really don't need to ER to understand it well but just to um to tell you what where this is going I mean a field is a set F together with um two binary operations um let's say plus F and multiplication f h and specified elements 0 subf 1 subf um with um Axion that you would expect generally for multiplication and addition and a zero and one um satisfying so oxum for example you want it for any a B and C in F if I do a * b + C then it's the same as doing a * B plus C and er you would want want that um 1 * a is a and that 0 time a is zero okay so this is a this is like an abstraction of of what what you know about I mean what we have with a ordinary numbers either integers or or real and once I have two binary operations I can talk about pols so a polom over a field f is um a formal expression uh let's say f of x is equal to um a z this is the the free Co efficient plus A1 X Plus H A2 x² up to a a n x to the N um where and is some natural number arbitrary it and we denote n is called the degree of the polom and you see what I did here I mean if um let's say x0 is an element in F we can substitute [Music] um f or evaluate the polom at x0 and what we get is a a0 + A1 x0 Plus um a n x0 to the end and you see what what I do here I I mean in every such expression I do multiplication and between two such Expressions I do addition so I need some kind of object that has both both addition and multiplication in order to talk about pols and so so a field is is is a natural um Choice it's not the only choice you can talk about Rings uh these are slightly weaker objects that I slight slightly weaker notion than than that of a field in which you can still talk about polinomial and as a side remark in a lot of the mathematical literature in around eliptic curves um there is a lot of discussion about rings and we will one of the the simplifications that we will do is that we will mostly avoid a a discussion about Rings because it's easier to talk about fields and and most of the stuff can be circumvented um from ring Theory so you see once we have a field we can talk about pols and once we can talk about polinomial we can talk about a a solution set of a given polinomial so um of course this polom is this is polinomial in one variable one variable that is X but we can do the same trick with the two variables let's say X and Y so a polinomial in two variables over F uh is a formal expression say F XY is equal to a z or maybe we can do a0 0 plus a 01 um I guess a one Z is better one Z X Plus a01 y plus um a11 X Y plus a to a zero this is times x² y the 0 and so on right up to some level we have some A and K x to the n y to the K where of course this I didn't say earlier but uh I hope maybe you you you CAU it I mean here in a polom the coefficients need to be elements in the field so for any I AI is an element in the field and and the same here for any I and for any J so let's say for any I between is Z and n and for any J between Z and k a i j is an element in the field and now if you give me a pair of elements in the field if x0 y0 are two elements in the field then I can substitute x0 and y0 into F and I get some element in the field so now I can talk about the solution set of um of a polom in this case in two variables um the the solution set of f is the set of all pairs X Y such that f of x y is going to be equal to zero zero in here zero means the zero element in the field so you see the a the discussion about fields and about pols is meant to give us a a at least a syntax to talk about solution sets that will eventually um bring us to elliptic curves so we we will H we will discuss a lot about Fields a lot about polinomial over Fields um one thing that so this is the the the all the prerequisites for elliptic curves and what we want I mean everything in cryptography is typically finite this this is General General truth about computer science mathematics it tends to have a lot of empathies about a finite mathematical objects so when when it comes to our interest um the um the main goal in the um um preliminaries um let's say main goals so one is we want to classify finite ailan groups and two we want to classify finite FS now what does it mean to classify this is a kind of a a soft a mathematical statement to classify a a a collection of objects usually means to give a a a short and convenient description of these a of these objects I mean you can say okay so we gave a definition for an AB bilan group right this is like a definition of a group with an additional axum that multiplication is commutative finite ailan group simply means it's it's an ailan group that has finitely many elements same for field and so okay so we have a definition we know in theory we know what are the the what is the finite Oban group but it's it's it's a very abstract definition and it turns out for example in the the first classification ER issue we will we will be able to um Express a every finite abent group is a combination let's say a product of a integers modu n for various various end so the this this is a very convenient um it's a very convenient uh tool I mean because integers modu n we ER we understand very well um it's a clock arithmetic and so on product of integers modu n okay it's it could be a bit more complicated but but is still manageable and it turns out that every finite a billion group is a product of these integers modu one up to a a up to isomorphism isomorphism is a well another notion that we will discuss that tells you when two groups are essentially the same they're not not the same on nose but they are um let's say from the point of view of a computer they will be they will be the same and in two to classify finite Fields it turns out that um for any P um and any a positive integer there is an essentially unique field um this is denoted as FP to the N or also um GF um and um of a a p to the N elements and that's it I mean every other finite field has to be um isomorphic to to one of these one of these fields and so in to sum up the the first part of the course will focus on these ER I mean these two classification statements once we have it we are ER we are ready to to move to elect cures and and continue continue the development of this latter object [Music] um maybe it's time it's good time to pause for more questions if you have any Okay so I I don't want to um to go too far um I mean I think this this is a good description of the near future and uh the rest you can of course ER read in the notes and and so on um and what I ask again is er that you watch the videos you have a a link to the Discord Channel and you can ask a questions about the the existing material on the Discord I will H I will be available there and we meet again on the 9th of August to do another recap and Q&A and after that I guess it would be H sorry it's the the 8th of August and then on the 15 we uh we just start from uh where the videos stopped ER any famous last wordss yes so Ali you you um you have a this a link in the chat here that I I sent you see it it's the it's the only YouTube link I think so it's all all the videos there I think it's six ER yeah probably I will we will upload this session as well but I need to make sure some some people before we do it all right then uh have a good time e