00 Introduction to the course

if you look in cryptography textbooks then you find that that there is an elementary treatment but it is used as I mean the mathematics is used as a blackx and what is this course is trying to do is to fill fill in the Gap by keeping an an elementary account that is also regor so um unlike the the pure math textbooks I will not teach you all all the material in B mathematics because you don't need all of it instead we take various shortcuts we we do almost only the the necessary material for earrings over Fin and but on the other hand we we do full proofs or almost full proofs I don't want to commit on on like precise number but be something like and now why why would anyone be interested in in in the proofs I mean of course you can believe that Community check check all the details many times it's reliable but I mean mathematicians are interested in proofs even if they are convinced the result is is true because the proofs teach you how to reason about the options and and I hope that you will you will see the benefit of of this RoR approach throughout along the way we will we will cover I think all the all the topics needed for caring only maema and well I I think it would also be helpful for other other stuffy um but it would I mean as a result it would take take quite some time now it's not so maybe I disconnected I think um okay so um I will start with the motivation and antic curve uh is an equation um y² = x + a x b and in fact I would I need to specify where the the coefficients a and leave but for now um we say that we we consider curves over um the real numbers this is R so curve over over the real numbers is an equation of this form with um A and B some numbers R and such that well there is some condition this and we wanted the discriminant e which actually don't remember the form now should very easy to find some some combination the coefficients which is called discriminant is is assumed to be and for curve um we can consider the the are points this is um denoted as e r and it's the set of of solutions to this equation so it's the set of all pairs XY and such that X Y is in in the real plane r² and X and Y satisfy this equation so y ALS X this called this set is called the finite points and we we add in addition another point which iot as o Z this point is called the point Infinity now um I will I will touch later on on this this special point at Infinity but for now if you if you just PL in a computer you take some coefficients A and B and you PL the graph of an curve you will get something like this this is like a fish it could be just a fish but it could be a fish with some some [Music] and so this is the the final points and um if I take points let's say p and Q this then the line going through p and Q generically let's say would have to intersect the curve e in a third point and only in one additional ter and the reason I mean we will prove it but the reason is that e is the polom of degree 3 and a line intersect the polom of degree 3 in exactly three points in the generic case and then in the non generic case intersects the Cur point you we will will touch this so there is another point which I can I would denote as a p star q and and note that the equation is symmetric along the xaxis right this is y s so so I can reflect along the x axis by simply taking a minus of the second coordinate which this point P star Q has two coordinates and after I reflect the point I will Den note by p+ Q this this part Fin and this this construction defines a a binary operation on at least on the finite points of so if I if I write it in notation I take a the finite points okay and find and this construction gives me another finite point on and um the the surprising effect is that um this this operation is is associative in the sense so this in the sense that if you take a three points p q and r on on the the set of finite points then you can a prior you can do two things right you can do p+ Q in Brackets and then R and you can do p+ q r with in this and when I say that the operation is asstive I mean that these two expressions This is highly non to Pro in fact proof is is quite long and Technical but but it can be done even in elementary methods and once I once I know that I have an associative operation I can define a group structure together with this additional quanti so this additional Point Infinity I just treat it as like an abstract well actually I I can explain a bit more how how why we need this point at infinity and I mean this construction that I do is in the generic case but what happens if I um I take a let's say it take a point right here p and I want to do and p+ so now now I I draw the line that passes between p and itself and intersect the curve there is only one line this this is the tent line which in this case is also the Y AIS and as you can see the line here does not intersect the curve in any other so I introduce temporarily I call it the point of infinity it's it's it's like a point sitting at the end of um every direction of the two dimensional plane this called o and um I I regard it as as a point on so if I if I do that then I can say that the tangent line this blue line intersects the curve in an additional point right and so according to the recipe I described before it will it will be the speed isal to and this is not just for the the point in the in the edge you can take another point for example q and you look at the the reflection of Q along the xais so this is this we call minus and again according to the recipe I the construction I described before in order to do um q +us q what we need to do is to draw the line and passing through q andus q and look for the intersection of this line with the Curve and here intersection would be o and then we need to reflect the intersection along the xaxis but o is sitting in all directions so reflection of O is still so you see we have this point or and what what I'm saying this is only sketch um but what you get from this ah and of course um the other Edge case let's say is um if I take some generic Point not on the on the tip of the curve and let's see q and I want to add it to itself to add it to itself I need to draw the line so I want to do q+ Q so to do Q + Q I will draw the line passing through q and this would be the tangent line to the curve my drawing is is very bad but would be something like tent here look like a tent line and this tangent line is guaranteed to intersect the curve in a third Point again this point this is the the point we started then this is what I call Q star and and again I I reflect and I get what I Define to be so all in all what you get and again this is on a sketch is that um the the collection of all finite points with the point Infinity forms an which means you can you have a binary operation is associative it has um for every element the inverse to the element has a so zero element which weot as all and yeah so this is this is an a now um we don't have to consider only the theing numbers so in in Elementary number series uh there is this notion of mod Artic but before I move to this are there any questions on this this part if you have then please raise a hand seem to indicate any points higher yeah I mean so if this is why I said generically um so in the in the like in the typical case you take I mean most of let's say istically in a very high probability you take two points then you will get this situation okay um but there are edge cases and one of the edge cases is where I take the point and and it's reflection what what I call the negative so I take Q and I take minus Q the reflection Q then the line passing through Q andus clearly cannot intersect the curve because it's par to the the yis and then I would say that this line still intersect the curve but in the point question yeah that's because my drawing but it is the case yeah you can you can find the precise drawings internet and you can even Dr yourself around see always points well I mean in the generic case course in in this case of q andus but but for a typical line this this is situation any any addition questions from online EAS what's yeah okay so um of course you could have you could have said why not use using a mov this why don't say I mean also I mean in my drwing to be right but then this is a degree 2 and when we take point so this is one the issues when you take two points it will simply intersect you don't have the the third intersection because it's a dee I didn't prove it this is this you can you can actually like just experiment a little bit you see that in the generic case you don't have you don't have so then what you do you you because we are interested I mean this would be let's call it P and then I could do p of R I can even ad join the point Infinity but how do I Define the group right so I have like P and Q and how would I Define I I can reflect I can reflect along the xais this is but I don't have inter look like most of the time you will have intersection but because some uh you know can always be can split time you will not always get a solution to your equation to so so the the situation with the roots and this so we have this equation and y^2 = x + a x + B and you can look this is e and there is this Pol of which is X a x this a pol in only one and you can look at the the zer of of these are all the all the EX such is zero and it turns out that a polom over Pol of 33 over the real numbers can either have one or three it cannot have two and if it has one then the graph of the would be just fish and if it has three three Roots then it will be the Fish Lake okay so so this is the situation but again we will we will the details once we get there but we take us time to to get to this point yes where do you find notes in in my website so uh we will post the the link in the Ian correspondence um okay [Music] so and in elementary Theory there is this notion of modul AR and this is like the best analogy I think is um is the Artic of right you have I mean zero but it's one up to 12 but 12 isal to Z so and if you you add you continue round of the clock then 13 isal one and so so clock arithmetic is um this is denoted as integers mod 12 but you can do it I mean for every every number right give give me every integer a positive integer I can do kind of generaliz for this so for a general integer for integer n a the set of integ mod n is um as a set is um just set of numbers Z one nus one and we have a binary operation um the takes a and b and send them to a you do you do PL of integers and you take mod it means that um you write A+ b as um q n + r for r strictly smaller than n this you can always do this is like um long division or Division and after you write you write this this you can do for any integer in particular for a b and we Define a n r okay so again just like in the clock Ari and in so so this is this is a another example of in the beginning and and if I mean the zero element so zero is the is neutral with respect to addition and if a is is some element in integ mod n then Aus a is Def to be nus which is is again a number between Z andus one it's a number in and a a is but so so I get that every element has anit this is calledit but and and what I didn't say I mean when I say that something is in a bil group it means I have a binary operation this operation needs to be Associated among other things but it's not hard to see that taking mod is associative in the sense that right a um but I don't have to restrict myself on to addition I can do also multiplication so with so then I take a and b in no I I can multiply every element zero and get Zer and so * B right is I can write it as again q n plus r for some R and I I say that a * B is equal R and this is again an associative associative binary operation it also has um a neutral element with respect to to this operation and this is the the element one is a neutral with respect this multiplication mod and and this is in the sense that for a * okay so so now I I I see that on Z end I have a structure that is somewhat similar to the real numbers right I have ADD I have multiplication I have neutral elements with respect to the each of the this binary operations and actually binary operations are also compatible this is called distributivity it means for any A and C in if I do a * b c then I get a so this looks very similar to um to the real numbers in kind of an obstructed way but there is one um one property that that is missing for the the comparison to be let's say complete that is um not every element a m M I mean some element iot a every I should say non element course um in the real numbers you don't have a multiplicative for for the Z element and so multiplicative inverse is some element Aus such that a * Aus is equal to the neutral element of of the multiplication H specifically K and L bigger than one then K and L our element in and z in ZN K * if K - one would be then take this I this equation by K - one k - 1 * K is = * 0 but K - 1 * 0 is 0 K - 1 * K if I had be one stays as it is but 1 * get this Contrition so this is like a nonformal proof but it tells you that if n is not prime you cannot have multiplicative on the other hand this ising if and every nonzero element in CP okay so um this of course it takes a bit time it's not great um and what we get um we weote by FP the set Z to with addition [Music] and and this is an and and the the term for this this structure discuss this okay and so I I want to get back to to but I think maybe now is a good time to take questions and take a break are there any questions on on this part of the modulus yeah yeah yeah this this one thing is is just sketch to kind of show you the landscape of where we going and okay so let's let's take a 10 minutes break and we come back to so we have this we have this field um FP and and we can do I mean the fact that it's a it means we can do multiplication and addition and this means I can consider a a pols over FP so we can consider and poomi and let's say in two variables over andp a typical polinomial over FP in two variables would be fxy equals um let's say degree 3 maybe degree two degree to polinomial um would be some um a m x² plus b y² plus C XY plus um d x + e y + f with um the coefficients are now and I mean elements a b c d e f are now elements in FP and we can consider also the the set of of roots of a polinomial right and this this is the notion denoted as the the solution set solution set of a is um the set of of pairs XY is such that X and Y are in FP and F of XY is equal to zero of course zero I mean the zero element in F and um we don't have to just restrict to degree 2 we can look at degree 3 polinomial um and in particular if um let's call it Fe or Fe is the polom um X Cub plus a x + b - Y 2 um for some coefficients A and B in FP H we can consider the the the set of of all um solutions to this polom the solution set or P this would B I mean what we denote is the finite points um of an elliptic curve over FP and the whole set elliptic curve over FP would be simply the finite points and the point of infinity some some additional additional symbol that we uh we will Define how it behaves algebraically um and given any point given say p and Q we can start with finite points actual solutions to the the polom P we want to Define um p+ Q so how do we do it well we um we use the the analogy that we had in the real numbers I mean the the geometric construction that we had for the the binary operation this means that we need to draw the line between p and Q what what does it mean to draw a line between P Q in over well in FP well it's actually in FP squ is the solution set of um a polom a x + b y + C in other words a line L is the set of all X Y in FP s such that a x + b y plus C is equal to Z okay so we have kind of an abstract notion of a line a line is just a solution set for a linear degree one and H it turns out so so if I have two points p and Q which are finite it means each of of them has coordinates so let's write p is equal to PX p y and Q equals QX qy and uh just like you know in in high school mathematics um you can construct the line between h p and Q um the line between p and Q well it has to pass through p and Q right so I write the equations and a p x + b p y + C is = z and also a QX + b qy+ c is equal to Z I subtract I get that a px - QX + b P Yus u y is equal to Zer um actually okay and I have these I have these two equations right um let's say even let's say even C is equal to zero if C is equal to zero um then I have two equations in two variables A and B and I can I don't even have to substract now um I can solve for um A and B and I get um I get some Expressions I mean um I don't want to to spend time on writing them now but I get some expressions for a and b h with the the initial data of PX py QX and q y so I get I get a line and this so you can one can show that this this uh a set of two equations two linear equations um have a unique a unique solution um A and B over over any field actually and in particular over FP so I get the line L PQ let's say and this is this is um an equation right a x + b y in fact once I I assume C is equal to zero then I can I can write the line as a in more familiar form this would be y = mx plus plus a um [Music] so I get an equation of of a line maybe this this would have been better because this this line ax plus b y + C H this uh takes into account the the case in which the line is is parallel to the Y AIS but if if I remove this case then I can say that uh a non well uh an ordinary line is the set of solutions to the equation y - MX - A and then I take the solution set of this m y - MX minus a where M and A are elements in FB um and then uh the equation here simplify it's just maybe it's it's a bit better to do it like this so I have y is is now pyus m x a and I have the same for CU okay and um so so I solve for instead of a B I solve for M and A I get some formula for for m um I mean this actually if you want we can we can we can write it down this and and this is pyus py is equal to and m p xus u so I get that m is equal to pyus qy ided PX minus QX and of course there is an edge case in which PX is equal [Music] to to QX and um but let's say in the generic case I get a I get well defined M this this is called by the way slope and I substitute it in the the equation I get that um for example py minus this m q1 ided by PX - QX * PX um is equal to a right so I get also an expression to a uh so I I can I mean with this Abra definition of of a line I get a a line between two points in in FP s and after I get a line I I need like in the the construction in the the real numbers I need to check the intersection point of the line with the Curve but that's that's something I can also do over FP because intersection point between two pols is just the the intersection of the solution set right I mean um so we get we get a line lpq This is a solution set of this this is the solution or okay this m x and a - Y and and the the solution set of this polinomial mx + Aus y it contains p and it contains q p and Q are indeed points in the the solution set and um the intersection of e and um lpq is simply the intersection of the solution set so you take uh the solution set of a Fe p is this defining polom of what we want to be an atic curve and I take the solution set of this line MX plus Aus Y and um we can show I mean of course p and Q are in the intersection because we chose them to be initially in the solution set of the and and we constructed the line so that there will be points in the line but there is an additional point which we can denote P star P star Q it has two coordinates right so I write P star Q X and P star q y and I Define p + Q to be the same thing but when I reflect along the X reflect along the x axis is to Simply do minus on the Y and minus of course I mean in FP is just taking the addtive inverse of this element that is I take pus P minus and miraculously or maybe not so miraculously um this gives me a a billion group structure on efp is in billion group um the proof is I mean once once you know the proof for um the fact that in the curve over the real numers is in a billion grou you can pretty much imitate all the steps you did over any field I mean the construction we had this geometry right but the geometry the geometry construction involve a things that we can imitate algebraically that is we need to draw a line to draw a line is simply take the solution set of [Music] linear we need to take the intersection of the line with the Curve this is just taking the intersection of solution set of and we need to reflect along the xaxis this is just taking a the additive inverse of the the Y okay and so once you know that this is an abent group over the real numbers you get almost automatically that it's an a billion group over anything and I should say a warning I mean let's say um p is large and this is typically the case in cryptography we take a big Prim number so one naive approach would could say okay let's let's put all the numbers one up to P minus one on the the typical exis and uh and just PL the discrete the discret solution set of um and since we uh we know what the graph looks like in in the over the real numbers we may expect that we get something like this but this would be a radically wrong and the reason is that the arithmetic of FP is is radically different than the arithmetic of so when we when we do I mean we look at the solution set right this y² = x Cub + a X plus b you can look I mean if I give you some A and B between zero and and and P minus one you can consider them as just numbers right and then and take the plot of the the resulting elliptic curve um but when you consider them as elements in FP I mean for example when you do a a y s if if Y is is bigger than square root of P then Y squ is bigger than p and so y s would need to be something else than the actual real number y s it would be some modules so the result is that you get if you plot it over FP I guess you could say that maybe up to some around the square root of P you would get something similar to the square root or maybe a a cube root because we also need to consider that X cube is is not mod so up to um around a cube root of P you would get I mean the arithmetic of FP is just a just the arithmetic of real numbers and so you would get a portion of the graph that you are used to see in over the real numbers but after after that you get gibbish I mean there is no way to make sense of this of the thing that you get you actually get various captured points all over the place so the the geometry on in the sense is is r and you cannot expect that the the typical construction of a line between two point if you even if you take two points here the line between them may contain h i mean the line is simply the solution set so it may contain some uh some points here right the line between even if you take some some points here p and Q the line between them would not look like a a scatter plot of of a line over up right it would so we lose what what happens when we we walk with FP is that we lose the a the na geometric and I guess here it's like a there's a there's a nice Insight of pro pro that analyz the The Ten Commandments and he said I mean he was he was not religious in any sense but but he said the most important commandment to human thought is do not make statue or a mask so think of God ab and this we have a bit of an analogous situation I mean if you want to understand li curves for cryptography you cannot think only on the the graph of the Cur over the real because the geometry is completely ruined over F so you need we need to think abstractly ontic curve Al it would be mostly algebraic but nevertheless we take analogies from the geometry of the real numbers and we try imitate and we we will see when the geometry works when it does turns out that quite a bit of it transfers to the general algebraic case I mean you can talk about smoothness for example you can talk about tangent line and this this kind of approach in mathematics is called the algebraic geometry um before I mo one uh any questions on on this part uh yeah does it mean that for any value under cubic root of P we don't really have a lot of security because we don't have any scrambling [Music] um you could say it's not exactly it's not it's not exactly insecure because the security is a bit more involved I mean so depending on what what you want to do but eventually if you you only consider elur as an abent group and you do standard na like Helman exchange exchange then this security relies on the discret log and a discret log even on below Square Cube rout of p is still hard so you will still get the security then there is the question of I didn't talk about parings at all soon soon reach to it but there is the question of security of parings but this this is another [Music] another issue I think it's it's too early to consider um okay so maybe this is this is a good point to H to reach to this this issue pairings or or maybe are are there any questions from uh online okay so um there I I said that there is this surprising property that e efp e ER also and over in fact over any field if you take the equation of an elliptic curve get an A Billion group but in fact there is an additional structure on the set of solutions of an elliptic curve that um makes it even more more special and and more useful for cryptography um and this is the the So-Cal pairing and and aaring I I'm going to lie a little bit and but roughly speaking aaring is a function from the set of solutions I mean this set of points of the elliptic curve time times itself into H let's say FP we can say that it's actually FP without without element zero [Music] and what is this sping this is usually denoted as e this sping has this property that um if you take two elements of this form G to the a or here I should say what is g to the a you take some some element in in efp and G to the a is simply um G Plus G Plus g a time so a a is an integer and this Pro this pairing has this property that if you take e of G G to the A and G to the B you get e of g g to the ab and some well some additional property but this this specific property this is bilinearity um gives you a a a very important structure on elliptic curves that does not I mean it's usually if you take just a a arbitrary billion groups instead of elip curve groups you cannot or it's a it's very hard most most most of the time it's impossible to construct a a a pairing between I mean the the ab bilon groups that you you choose so the thetic curve gives you this additional I mean the altic curve group so if you know that you're given a billion groups that are a groups coming up from elip curves then you are guaranteed to have this additional structure this pairing and it gives you a a an important a property to construct a crypto system in particular zero knowledge proofs protocols I mean use extensively this and Okay so what this I mean constructing the paing I guess um This was um the main the main result was that way and I don't remember the year but this is somewhere in the the first half of the 20th [Music] centy and as we will see you have different sorts of pairings but they all follow from the W so um this brings me to what what is the path roughly that we're going to take so um in order to get to this uh this wh pairing is I guess you could look at the at the notes see the um the table of contents um the first thing we will do but I think this will have to wait mostly for for the next session ER we need to talk about set theory set theory is is going to be like the ER like the machine the machine code of of all the mathematical constructions we will do so it is worth to to spend a few sessions [Music] on set theory what is called na set theory not not axiomatic logic set theory um and uh we will we will get to it you you will see that there are some even even in this somewhat dry setup there are some interesting phenomenal then we move to a groups ER what is used in in in cryptography is mostly a bil but not only in in a a bachor in mathematics you have a special course in set theory you have a special course in groups most of the course in in a university on Bo Theory we don't cover because we don't need we need a mul bilan groups and a little bit of non at the end of groups we will do a classification of a finite grps um after we finish uh we finish groups we we move to Fields again in in university courses H field theory is an entire semester but we will cover it much more quickly but still it will take time [Music] and the the the key result that we want to take from from field is a classification of fin FS then and we we actually start touching elliptic curves and here there are quite a few topics that we need to cover before we we can construct the we pairing so one of the topics would be the group law the other would be projected coordinates then we will have H quite a long a section on um zeros uh and PS and H what is called divisors and from divisors we will move [Music] to I think well I'm not sure what what would be the order but there is an important construction by Miller that is used in implementation of pairings but we will also use it theoretically to prove some properties um of of divisors divisors over tic Cs and um eventually we will get to um there are some some topics in the middle we will get to well pairing and from the we pairing it's very hard it's very easy to H to do other stuff like the tap Fairing and and there is also eing aging yeah so so and finally I guess this would also be a nice uh um a nice chapter to to do is a what is called pairing pairing friendly curves so these are these are specific specific curves that are designed to [Music] be efficient and nicely handed in uh parent Bas cryptography and in particular there is the current curve that is as far as I know is on um it's supposed to become the main curve for pring on ethereum this is the the BLS M 12 381 so uh so at the end of the at the end of the road you should be able first to to understand the the specific details of pairings in general and and also um how to handle some parent friendly cures any questions um yeah a bit before you defined um a like you say g g of a mhm you took it in the natural numbers uh is it does it always have to be there's something I think called the scalar field I think mhm um and I was wondering from what I understand it's not okay typically for example if you look at BS it has a infinite color field it's finite field uh is that like okay I'm trying sorry I'm trying to come up to the question that makes sense I think I understand what you're asking like is the security secur so we always in cryptography we always work over five otherwise because you need it to be computationally [Music] prison so but in this in this part where we do g g to the A and I said that a is in in the integers but I might as well just put a in zp so if a is not if a is bigger than p i take mod P right but what I mean is is it still secure bigger than if it's not even even I don't exactly know how to answer the question I mean the what you need I mean you need for security you need the discri hardness thep if you do think over the real numbers then discret log is actually log and log can be computed efficiently so it's not so good um if you work over the rational numbers you can Define right you could Define e over Q the rational numbers and [Music] there it's not Al clear to me what would be the hardness of discret La you could imagine that you could do discret log you take a rational number you do discret log over the real numbers and you look at the result is a rational number or not so in a way you theet L would not be that hard um and okay there are other other examp I think these These are the main two examples of infinite infinite fields in which I expect that the L would not would not be a secure not be a hard problems or would not be secure and yeah I mean there there are other reasons that in cryptography we we actually work I mean eventually we need to encode our and integer arithmetic is the most [Music] efficient other other questions well I don't have a I have a request we look at the organization yeah at the end of the course can we look into this stuff called the remember there's a Goldie L field like there Nova there are some systems that are built on top of of some very like curves with very small field sizes okay so curves with a a of fields of characteristic two or three you mean like two to the FS of two to the power of something so this is called a characteristic tool we will cover but we could I mean at the end of the course or whatever we could do many things and this would be one of them um but what I suggest what what I plan for the the main course this would take a while as I said H is to to do things away from a characteristic 2 and three so the prime number P in FP in our case we we will consider elliptic curves over FP and a p would be different than two or three and the reason is that the theory is much simpler it simplifies significantly over these primes and and the the vast as far as I know the vast majority of the cryptography literature is with a a big price so so it would I think it would be best for most of the people to to assume that P is different than than 2 A3 and then the theory simplified B even more a bit and you still get most of the the body of literature ER it's not so hard afterwards to to extend to extend the case to primes two or three and this you I mean eventually the course gives you tools the would allow you to read more or less to read yourself even the kind of the other cases this is maybe the point to say that I think questions are very important so first of all thank you for many questions but you will see certainly when we move to to more technical stuff ER it's it's a it's not so easy to [Music] ask precise questions and this this would be really the the thing that will promote you the most to to insist on trying to ask questions I mean if it's not so prid it's not you know it's not a big deal but eventually we try to make the precise questions and er even if you have silly questions it could be about notation it could be about er er what is out there outside of what I talked about ER ER it could be about a specific reasoning that I I explained that you didn't understand um ask questions this is this is a very important both for for you and for me because then I know what is what is missing and I would also say that again there are different ways to to take this course um but kind of the IDE did set up and since we do and in the mean let's say in the first around three month we will uh we will consider stuff that are not even a curs just this H uh topics one two and three and this will be completely fullprof the ideal way to to see if you're if you your understanding is to to have some kind of like a air type understanding that is you understand all the all the steps in all the proofs if it's a little bit less than air typ it's also okay but if if you lose too much air you canly so so pay attention to this eventually ER the things will depend on each other quite significantly so if you don't understand one part ask about you may get CL any questions from online before we end the session all right then uh next week uh we start with the the