okay so I think the audio seems fine okay so this is lecture 21 okay and the last thing we saw was construction of a regular ldpc matrix right Gallagher's construction for a regular ldpc matrix let me quickly remind you how this is done if you have an omega c omega r regular if you would like to construct an omega c omega r regular regular ldpc matrix okay and if you have wr dividing the block length n then it's very easy to divide your parity check matrix into wc sub matrices right so that's what you do you divide it into h1 h2 so on till hwc okay each matrix is 1 comma wr regular okay that's how each matrix was right am i right each matrix each of these sub matrices has column weight 1 and row weight wr so if you put one below the other the overall matrix will have this k will be wc wr and for this you need wr to divide n otherwise it won't work so smoothly okay what is the number of columns here n over wr okay so how do you construct h1 h1 has a very simple structure like this okay right just put once in a stepwise fashion you get that okay you put wr once put n over wr of them you'll cover the entire block length n okay this is the this is Gallagher's construction okay so let's move on and see an example I'll take a really really simple example an example where the matrix will clearly not be low density okay we're very high density matrix but I want to take a small block length n because once block length becomes very large it just becomes very difficult for me to keep writing down these huge matrices okay so as an example suppose I take n equals 8 and I want a 3 comma 4 regular matrix okay can we do Gallagher's construction is Gallagher's construction feasible for this parameters yeah 4 divides 8 right go ahead and try just write down h1 I'll write a specific h2 and h3 okay write down h1 alone what will be the dimension of the matrix overall dimension 6 by 8 right 6 by 8 okay okay so the first row will be 11 11 11 11 okay I'll leave out the zeros they're a little bit distracting if I if I leave a position blank it means it is zero okay so I'll leave out the zeros this will be my first row okay maybe I'll need maybe I'll need to keep this a little bit open okay my second row I'll just pick to be this way okay so this is some people might argue this is not random enough I'll agree with them but it's easy for me to write down okay it's just an example this is a valid h2 there's nothing wrong with that it's a permutation of the columns of h1 there's nothing wrong with that okay the next one I'll pick as 11 okay that's a construction for you okay clearly this is not the only matrix right you have so many others maybe some of them will be repetitions okay so you can't just blindly do total number of permutations times total number of permutations again right that's not possible because some things will repeat okay there are some permutations which will not give you distinct numbers but maybe one can compute it maybe it's not very relevant to even compute it but this is one matrix in the ensemble okay this is how you go about doing it so you see this is already a 6 by 8 matrix okay if I were to even do for an equals say 12 it automatically already becomes what a 9 by 12 matrix okay so it becomes very difficult for me to write down and you kind of missed the picture okay this is very simple thing to write down for this 6 by 8 case 3 4 regular okay if you want a 3 6 regular code then you'll have to go to a really larger n okay so you have to go to at least n equals 12 and maybe for that it's it's if you work out in a reasonable fashion okay so those are those are examples you can cook up examples like this and in practice real examples will come only for large n okay and for large n I can't really write down you have to write a matlab program it's easy to write a matlab program to do this construction for large n right just pick that n first matrix is easy to write down in matlab you can write it down in few comments then matlab has a ran perm command which is just random permutations of 1 to n just reorder the collabs of h1 that also is very easy to do in matlab so you can write a very quick click 3 or 4 line matlab program to generate a random instance of a matrix from this ensemble okay this is easy enough okay any questions on how I did it well think about it think about so you see he's asking questions about counting the total number of matrices with in this construction is that what you're asking yeah I mean it's I don't know if it's a very trivial calculation to do but you might be able to do okay I don't know maybe that's the way of counting it I'm not sure I'm not I'm not thought seriously about the counting could be possible okay so there's another structure associated with associated with parity check matrices which is very crucial for ldpc codes to study decoding over ldpc codes in fact to study even other constructions there is a structure associated with this parity check matrix that that is what's known as the tanner graph and this is what we'll see next in fact to study the next construction that we need the we need to understand what tanner graphs are okay the the there's one more construction which I've been talking about what's called the socket construction so you should know a little bit about tanner graphs before we go into the socket construction so tanner graph is basically a graphical representation of a parity check matrix okay so graph don't think of sin x versus x or something that's not the graph I'm talking about this is the graph theoretic notion of graph okay so you have a bunch of nodes which are connected by edges okay so that that if you're you can it turns out you have a very nice representation for a parity check matrix as a graph as in fact what's called a bipartite graph it's not so crucial to us but anyway there's a bunch of nodes which are connected by edges that's graph okay so what is the graph nodes connected by edges okay for us the nodes okay in the tanner graph the nodes will correspond to columns and okay so maybe the parity check matrix is h columns and rows of h okay and the edges will correspond to the ones in h okay so that will be the correspondence okay so you'll see how it's done it's a very simple representation I will make a copy of this guy here just to show you okay so that's my parity check matrix so how does my graph look like I said I need nodes for the columns and rows of h the rows of h are also called checks right there's a parity checks that the each row of h is a parity check that the code word has to satisfy right we saw that before okay so so I'll put nodes corresponding to the columns on the left hand side okay I'll show the tanner graph construction for this example the general case is also very similar there's really no need for defining it in general okay so how many columns do I have I have eight columns so I need eight nodes corresponding to the columns four six seven and eight okay those are my eight nodes maybe I number them one two eight okay so the columns I guess I number number them like this okay so those are my eight column nodes okay nodes corresponding to columns okay so and then I need nodes corresponding to the rows which are the checks okay how many of them do I have six I have six rows one two three four five and six and for those nodes I'll I'll put squares okay just to just to distinguish them you can put circles if you know in your mind what are columns and rows but put squares just for convenience okay so one two three four five and six okay and to make it a little bit symmetric I'll move these guys around that's better right okay so that's better okay so those are my check nodes and maybe I'll number them and number one two three four five six okay so you see just to illustrate how intuitive the tannograph is what do you think we can do how do you think we should connect up the edges connect up the nodes with edges yeah so you put the edge there so you see that it's quite intuitive if there is a one corresponding to a particular at the intersection of a column and a row if there is a one connect those two nodes with an edge that's all okay so do that and I'm going to do it here on the screen so you can do it in your wherever you are as well and check that we've made the right connections it's not too difficult okay for the first check node go check node by check node it's slightly easier okay so the second one I have five six seven eight I'm sure there is a smarter way to do these lines in this pc so that it's all straight lines but I guess I'm not maybe I should learn that sometime okay all right so this goes to three this goes to three then I have five and six going to three okay eventually it's going to look a little bit messy but there's no way to easily avoid that okay then the last one three five seven eight six four okay so I've connected it up and it looks looks quite dense okay so it's it's as I told you it's not really a sparse graph so sparse matrix right there's too many ones pick such a small block length once you make the block length very large you'll have very few edges okay so it won't look so messy if you actually manage to draw it okay but if you have thousands of nodes takes a long take too many pages probably there's no point in drawing it you have to just visualize that such a graph will exist okay so this is this is the way tannograph is designed so how do I do it in general just repeat the same thing is put one node each on the left side for each column put one node each on the right side for each row and whenever there's a one that column and that row connect it up with an edge okay so this is the tannograph there are few few few notations few definitions uh so the tannograph represents the parity check matrix it's the same one and the same thing you either give the parity check matrix or the tannograph both are the same right you can go from one to the other it's no problem so likewise there are corresponding relationships okay so each column of the parity check matrix I can imagine represents is kind of related to the a particular bit of the code word right does that correspondence make sense can I say each column of the parity check matrix is related to the corresponding bit in the code word why h times c transpose is zero when I do that h times c transpose what happens each each column gets multiplied by the corresponding bit so each of these columns kind of represent a bit okay I can think of it that way this one to eight is actually the location of the eight bits okay so likewise these nodes on the left hand side which represent columns are called bit nodes okay so these nodes are called bit nodes and okay I already made this comment each row of the parity check matrix actually represents a parity check okay a particular check for instance the first row tells you what what does the first row tell you in terms of c1 plus c2 plus c3 plus c4 is zero modulo 2 right that's what the first likewise other rows also give you parity check so these nodes on the right which represent rows of the parity check matrix are also called check nodes okay there is some terminology here these bit nodes are sometimes also called variable nodes okay some people refer to them as variable nodes but we'll refer to them as bit nodes okay well the edges are edges there's really no nothing to nothing more to say that okay and then such a graph okay so if you're a little bit familiar with graph theory when you have when you can divide the set of nodes into two sets and every edge connects a node from one set to another set such a graph is supposed to be bipartite okay so this is a bipartite graph and we really don't use some properties maybe but really we don't care too much about why it's bipartite but that is the graph okay a few few computations and few more notations and definitions graph theoretic are the following okay so in my matrix each column had weight wc right that's how I define my regular matrix okay so the columns the weight of the column in the matrix corresponds to something in the graph and that is the number of edges connected to the particular node okay that number is called the degree of the node okay if a node has three edges connected to it that number is that number three is called the degree of the node okay so so so one can talk about a bit node degree okay for regular graphs the bit all bit nodes will have degree equal to wc likewise what will be the check node degree equals wr okay so another computation if somebody were to ask you what is the total number of edges okay you can count it two ways right like we counted the number of ones in the parity check matrix you can count it two ways you can either go column wise or row wise it's either n times wc or n time or n wc by wr times wr is again n times wc so it's enough if you say n times wc okay so that's the number of edges okay that's also another correspondence something like that we'll come to it slowly you have to make sure a degree you know there's some some non-triviality there we'll come to it okay so that's the tannograph and well at this point it doesn't seem that fantastic or even necessary okay so I've not done anything really new the one non-trivial thing that we need in the tannograph is what are called neighborhoods okay and that is a little bit difficult to define with the matrix alone okay one could define it with the matrix it's not that neighborhoods are difficult to define but but it's more natural and intuitive to define neighborhoods starting from the tannograph okay so so that's that's where tannographs are very useful okay so once I define the neighborhoods and all that you'll see and the neighborhoods play a big role in the decoding okay so we'll define what those are soon enough okay that's why the tannograph is very useful okay that's one thing and the other thing is most decoders for ldpc codes are described on the tannograph okay you kind of do operations on the tannograph okay so you think of the bits as being on the left hand side and the checks being on the right hand side and you use the checks and the bits together to do decoding on the tannograph that's where the tannograph is very very useful okay we'll come back to those things soon enough but for now I'll describe the socket construction which is described on the tannograph I'll define that first I'll describe that first and then we'll move on to these other properties of the tannograph okay so what is the socket construction okay so it's due to Prudiger or Banke and Thomas Richardson okay so they played a very important role in the in the during the making ldpc codes really really popular okay so they analyzed it very rigorously they came up with a lot of theories so they were very famous in the ldpc area okay all right so socket construction how does it work suppose I want to construct n wc wr regular ldpc codes okay I'll define an ensemble for going about doing it okay so think of it in terms of a tannograph so what do I want I want to generate a tannograph with n nodes on the left side n wc by wr nodes on the right side and n times wc edges each node having degree wc on the left side and wr on the right side right so that's what that's what I want in terms of construction the way to think about it is keep imagine you have n nodes okay and imagine each node has wc sockets okay so on the right side again you have nodes and each node has how many sockets wr sockets okay remember there are n nodes here and there are wc sockets there are n wc by wr nodes here and there are wr sockets so what is the total number of what is what is the total number of sockets on the left side n wc what's the total number of sockets on the right side okay n wc this is the total number of edges right so now I'll imagine each node each edge connected to socket a particular socket okay each edge I will imagine is connected to a particular socket on the left hand side and a particular socket on the right hand side okay is that clear each edge I will imagine is connected to a particular socket on the left hand side and a particular socket on the right hand side how many sockets do I have n wc on both sides okay once I assign edges to all sockets what will I have the edges will actually give you a will give you what in terms of the sockets they'll give you a mapping from the left sockets to the right sockets okay and what kind of a mapping will that be it'll be a bijection right it'll be a one to one invertible mapping right that's how I that's how they just work right once they put down all the edges I will get a one to one invertible mapping or a bijection from the left sockets to the right sockets okay so that is how I define my ensemble of codes I say every bijection from the set one to n n wc to itself will define a bipartite graph for me which will be a tanner graph of a LDPC matrix okay so that's how I start okay I start with pi being a mapping from what to what n wc to one to n wc being a bijection bijection or a permutation right in terms of numbers you can think of it as a pi as a permutation it's the same thing okay now I'm going to number my sockets on the left hand side from one to n wc similarly I can number the sockets on the right hand side from one to n wc again and then how will I connect the edges according to this bijection pi okay so and then what do you do I connect socket i okay in the LHS left hand side to socket what pi of i in RHS that's it that's my construction okay yeah so there's no question about comparison between this and Gallagher's construction yeah I mean your he's right I mean so Gallagher's construction will be a subset of this construction okay in any code you get there will be a subset here and in fact this construction is possible whenever wr divides n times wc you don't need that other special constraint that wr should divide and you don't need that okay this will work in a general case okay so you put down the circuits there is one problem here though and let me see who's going to be the first to observe that there is a problem here which will not show up in Gallagher's construction there's a problem here what is the problem think about it for a while I'm sorry wr will well no I mean I will I will fix wc and wr first I will say I have n wc and wr n is such that such a construction is possible and then I can go down and do this that is not the problem there is a more subtle problem let me see I'm sorry linearly dependent you'll get in fact in Gallagher's construction you'll definitely get linearly dependent rows think about it for a while you look at Gallagher's construction there will be at least one set of linear dependence okay you can guarantee that I don't care about linear dependence too much because my rate can only increase and it will not be too too much that's not the problem there's a more subtle problem here okay remember I'm allowing all kinds of bijections so what will happen I can have two edges connecting the same set of nodes same two nodes right I've just imagined sockets in each node right I can have a bijection which connects the first socket to the first socket and the second socket to the second socket but those two will be in the across the same node okay so how will I how will I relate that to the parity check matrix is a problem and when I relate that to the parity check matrix my column weight row weights will go for a toss okay so that is the problem there that is a it's a bit of a problem but it's not a real problem the reason is all the regular ldpc codes are definitely included in this construction there is no regular ldpc code that will be left out in this construction but there will be these extra multi-edge tanner graphs which don't really correspond to regular ldpc matrices but you will get something else right right you'll get something else which is different so you can do one of two things you can either expurgate your set and throw away all these multiple edges or just have them there and say my list my set of ldpc codes okay corresponds to n w c w r tanner graphs obtained in this way okay and I maybe my matrices will not be regular I don't care okay maybe my matrices are not regular anymore but I don't care my set of ldpc matrices are defined by these tanner graphs okay when I go back to the matrix it may not be regular but that's okay I will live with that you can do both and you tend not to lose too much okay the reason is you can show out of all the permutations that are out there the permutations that give you multiple edges are very very smaller number as n becomes very large those permutations become negligible okay so if you do a random construction enough number of times you will quickly get a permutation with no multiple edges so it's okay so in practice it's not a big deal okay so that's a slightly technical point and we can from now on we'll ignore that okay so we'll not worry about it I will say when I say n w c w r I'll mean the socket constructed the set of tanner graphs okay so you can either think of it as having no multiple edges removing all those graphs with multiple edges or include them and include the corresponding parity check matrices also I'm okay with both okay so my regularity will be defined only with respect to the graph I don't care about the parity check matrix and how it works okay and there are other ways of doing it it's all kinds of all kinds of modifications are there on this construction but this is how it works any questions okay okay so but this construction is easy enough and it's difficult for me to give you an example of this construction I can go back and reinterpret the Gallagher example I gave you in terms of this construction it's easy it's not too difficult I can tell you what is this permutation for that construction okay right maybe maybe you can spend some time and write down that permutation it's not too difficult okay one can do that so it'll work out in this way okay so that's the socket construction okay so now let's go back to this tanner graph that we had and define these neighborhoods which are so crucial in the decoding process okay so that's what I'm going to do next okay let me copy this tanner graph okay so this is my example tanner graph so this is an 8 comma 3 comma 4 regular let me say regular LDPC code I mean it's not a big deal to make that jump okay so it'll not be a 8 comma 6 code at best it'll be a it'll not be a 8 comma 2 code it'll be a 8 comma 3 code or something okay so I'm not really calculated the dimension exactly so right it's parity check matrix this is 6 by 8 matrix so you would expect it to be at least a 8 comma 2 code in fact there will be a linear dependence and go back and check that okay so it'll be less than that okay so so this is my this is my tanner graph and I'm worried about neighborhoods okay so this neighborhood is actually it's also a graph theoretic concept okay so how do you think of neighborhood in practice a neighborhood is what is your neighborhood people who are close by okay so first thing you need before you go to neighborhood is some notion of distance okay so now I want to think of the same distance in a graph okay suppose I look at the bit node one okay what will you say are in its immediate neighborhood just a natural intuitive definition all the nodes that are immediately connected to it okay so that will be my notion of distance okay if I can go in one step what nodes can I go to along the edges that will be my immediate neighborhood okay neighborhood of depth one okay and then I'll have neighborhood of depth two which is the nodes that I can go to when I make two jumps okay what will be the neighborhood of depth three three jumps okay four jumps so on okay same thing is defined for each nodes okay but now since this graph is bipartite what will happen in the first jump neighbors of all bit nodes will only be check nodes because it's bipartite right from here if I jump from the left side if I jump I'll go to the right side only what about neighborhoods neighbors of depth two they'll all be bit nodes again okay so one can do that it's a simple thing I can write it down formally in a long way but you understand what I mean by neighborhood right so basically you start from a bit node jump to all the neighbors and then from there jump to their neighbors then jump to their neighbors so on so on so forth you get neighborhoods at different depth okay it's a very simple intuitive concept okay and this is this one could define this even with respect to the matrix right but on a graph it's much easier all these jumps are very easy to describe on the graph on the matrix it's a little bit more difficult okay so I'm not going to formally define the neighborhood I'm going to do it by example okay so I'll draw the neighbors of say bit 1 bit node 1 at depth 1 depth 2 and so on okay so let's start okay so suppose I start with bit node 1 okay what are its immediate neighbors how many neighbors will it have how many immediate neighbors will it have wc right in which case it is 3 okay so you have what are the neighbors 1 3 and 5 okay so the sum I okay this is my bit node 1 and I connected to if you want to distinguish between bit nodes and check nodes you can either do the circle square thing or if you want to further distinguish you can say b1 c1 c3 just so that you know I mean just use any notation you want but I think circle and square is good enough you can see the distinction okay what this is these are the neighbors at depth 1 what about depth 2 what are the neighbors of check node 1 2 3 4 why am I not including 1 again it's already there okay so don't jump back to the same thing it's only only go we'll look for other neighbors you're not your own neighbor okay so that's the philosophy here okay eventually you'll see you might become your own neighbor okay that's a bad thing you'll see we'll come to it okay so 2 3 and 4 here and for 3 what is it 2 5 6 am I right okay so I'm going to write it down differently okay so so remember this is 2 3 4 this is once again 2 okay so in fact these two nodes are the same okay maybe I can connect it this way I'll simply write it in one more fashion okay so 2 5 6 and for 5 what is it 3 5 7 okay so so once again you see you have repetitions okay so these are at depth 2 okay so depth 2 okay so you have repetitions don't worry about them just keep just keep doing it now I can keep proceeding okay so if we keep proceeding you'll see all kinds of things will happen and the number of neighbors will keep on increasing okay so now including repetitions including possible repetitions I want you to give me the number of neighbors at depth 1 in the general case okay suppose I take instead of the specific case in general if I take n w c w r a code okay number of neighbors at depth 1 for all nodes right all bit nodes it's going to be equal to w w c check nodes okay what about depth 2 w c times w r minus 1 what about this will all be check nodes right this will be bits right what about depth 3 including repetitions okay so forget about repetitions I don't care about repetitions for now okay what will it be w c times w r minus 1 times w c minus 1 do you agree or is it only w c again see remember each of these nodes are already connected to one check node you'll have to only do r minus 1 always is that clear no no no repetition is one thing but you can't repeat your neighbors see why did I get w r minus 1 here because one has already been included right so likewise here when I put down neighbors here how many will I have yeah how many will I have I'll have only two right do you see that I'll have only two why because one is already there okay so don't don't repeat that okay don't keep repeating that okay so that that repetition is not allowed okay so if at all here down below if you get a repetition it's okay okay so do that you will get w c times w r minus 1 times w c minus 1 checks right so you can keep on doing this computation maybe you can write down a general formula for depth l as well okay so you can keep on doing it for a for every for a regular code one can do it okay so and this picture looks exactly the same for every bit node okay this structure this number will be exactly the same but the actual bits and checks will differ okay but the structure will remain exactly the same this neighborhood of each bit will look very similar this tree like structure no I mean not really tree like but know what I mean okay it'll look exactly the same okay right but the actual number of the bit nodes will change but the picture will look very very similar okay that happens for the regular code there's no problem that happens because of regularity right see that's that's the reason why this happens okay that's one observation there are a few other observations that I want to make okay little bit tricky it will need your imagination a little bit okay suppose I have a repetition at depth two okay suppose I have the same node appearing at a particular depth here in this depth two you saw you had repetitions right same node bit node two same bit node two appeared here as well as here okay let me let me go slowly I mean you can't say that's not the statement I want to make it's not true that everything following them will be the same okay because two is connected to three there two is connected to one here then this will be different that will be different okay it will change a little bit but so when will that happen that's the question when will you get a repetition at the particular depth okay so it seems like well you get it what do you think will happen and what is the way of describing that is there any anything that you can notice that why did we get that repetition what can we say that repetition will mean for the bipartite graph okay so it's a little bit difficult to imagine so moment you got a repetition like this it means right so actually what what has happened in the bipartite graph I have a I have an edge like this okay which means starting at two okay starting at two I can go to notice here maybe I'll do it with a different pen okay no color is here okay so it means starting at two no no this is different I need okay maybe I'll pick this okay starting at two I can go to one and then from the first check node I can go to the first bit node and then from the first bit node I can come back to the third check node and from the third check node what can I do I can in fact come back to the same bit node two okay I wrote the same two here differently so what does that mean in the original graph what does it mean there is a loop or a cycle okay if moment you get a repetition somewhere it means in the original graph there was a closed loop or a cycle okay these things are called cycles in a graph okay so every time you have a cycle in the graph original graph you will get some repetition in the neighborhood at a certain depth okay okay so that's that's the notion here okay so remember when I wrote down this neighborhood I I repeated the bit nodes right this two I repeated once again here okay if I go back to the graph and then trace this in fact I can trace this in the graph also I'll show you how to trace this in the graph okay you got a repetition here no so you start at bit node two go to check node one and then go to bit node one then go to check node three and from check node three you can go back to bit node two and you see there is a loop there okay in the graph it seems to be crossing but there is a loop okay maybe we'll take one more example what are the repetition is there five and five is repeating right so from five to three to one to five to five back again I should be able to get a loop let's let's start that five to three maybe I'll look at a different color I'm sorry okay so from five to three well it became a really light color okay can you see it maybe yeah five to three and then from three to one okay then one to five then five back to five notice that's another loop okay so every time you get a repetition at a particular depth you will get a closed loop or a cycle in the original graph okay is that clear so it's a very simple correspondence the way I made it okay okay so that's the that's the first thing slightly non-trivial observation that I want to make let me write that down repetition of nodes in neighborhood implies and is implied by cycles in tannograph okay so both ways you can go okay so the next thing is the next observation I want to make is something about the depth at which the repetition occurs okay so here yeah so so you'll see the depth at which the the repetition occurs you would imagine this a little bit carefully is related to the length of the cycle what is the length of a cycle length of a cycle is number of edges in it okay so here the repetition occurred at depth two which means you will have four edges in your site if the first repetition occurred at depth well see the repetition bit node repetition can happen only at even depths right it can happen only at depth two or depth four and so on but you can also have check node repetition before that okay so you can have some repetitions like that okay so if you will get repetitions at depth two if there is a length four cycle in the tannograph you will get repetitions at depth three if there is a length six cycle in the tannograph there cannot be a length five cycle in this bipartite graph right if you start at some point you can come back to it only after the even number of jumps that's because of the bipartite nature in general graphs it's possible but in bipartite graphs it will happen only after the even number of jumps and if there is in general if there is a length two l cycle in the tannograph there will be a repetition at depth l for every node involved in that cycle right it's very easy to see that okay so that's the next statement I'm writing it down well it may not be very easy to see but if you imagine that a little bit you can see that okay so length two l cycle in tannograph implies and is implied by repetition at depth l for nodes in that cycle okay it will happen for both check nodes or bit nodes if there is a if there is a cycle the cycle will involve both check nodes and bit nodes right for each of those bit nodes and check nodes if you write down the neighborhood at depth l you will get a repetition okay so that has to happen imagine the cycle right so in your neighborhood you'll be going through the cycles also and you'll eventually come back okay it requires a little bit of imagination but you can see the give you some examples and you can see the correspondence from there okay okay so the reason why I'm talking about repetition is it will turn out later that repetition is bad for us we would like to have tannographs for which for which repetition happens only at very large depths okay you don't want repetitions to happen at depth one and depth two well depth one is very bad depth two and depth three and so on you don't want repetition in fact if there's multiple edges from a node to a other you will get repetition at check at depth one you will have repetition at depth one right so all those things you don't want to happen okay so so again I'm not I'll when I describe the decoder it'll be clear to you okay so it is desirable not to have avoid short cycles it's desirable to avoid short cycles because if you don't have short cycles you will not get repetition for very low depths okay only for long depths will you get repetition okay so that's one thing is it possible in the regular construction it turns out for sparse matrices as n tends to infinity okay the number of repetitions is very very minimal okay it doesn't really happen there's a proper way of writing it down let me think about it and write it down carefully okay so let me repeat the statement first and then write it down formally okay it turns out when you make n very very large for a particular w c and w r when you make keep on making n very very large it's very very unlikely that you will get repetitions in your neighborhoods okay right now it was just six and eight so you saw repetitions happened very quickly okay if you make your n very very large block length is very very large you will see you will hardly see repetitions in your neighborhood up to depth two three four so on there will be not much repetition if at all there is a repetition there will be only repetition for very few nodes not for too many nodes okay so that's that's a that's a good thing that you can prove okay for large n things get better your neighborhood avoids repetition okay if there is no repetition then that's good for you I'm not telling you exactly why but that's that's desirable and it turns out when n becomes very very large you don't have repetition okay so a formal way of writing it down is given l okay six l there exists n large enough such that so that uh yeah probability of uh repetition okay let me just write it in terms of cycles length two l cycle tends to I don't know it tends to zero I'll just you know what I mean okay so well you can show that the yeah so yeah let's not equal to yeah let's not all right so the way you show it is this probability will decrease exponentially in n e power minus some n little decrease okay so if you increase n very very make it very very large this probability will quickly go to zero okay and you can remember I fixed l so you can keep on increasing l even if I make l 100 okay there is an n large enough so that you will not really see any repetition up to that depth in your in each bit node of a tannograph okay so that's the the that's a statement I mean again if you have to prove it it's a lot of combinatorics go back to some of the papers I'll I'll give you references some good references where if you're interested you can see these proofs okay so it's possible to prove it and we'll we'll just accept it as truth in this class okay so remember these results about the tannograph this is very crucial and in the next class I'll describe a very simple decoder for ldpc codes for the binary symmetric channel and in analyzing that decoder we'll use many of these properties okay so that's what we'll do in the next class


Welcome to my talk, Partial Key Exposure Attack on Short Secret Exponent, CAT-RSA. This is joint work with Alexander Mai and Santana Saka and my name is Julian Novakovsky. Before we dive into CAT-RSA, I would like to have a few words on just RSA. For that, let me quickly fix some rotation. So as usual in RSA, we denote the public key by a tuple N, E and the private key by a tuple N, D and we call the two prime vectors of N, P and Q. Now what's very interesting about RSA is the fact that if you instantiate it with D significantly smaller than N, then the scheme becomes completely insecure. This was first shown by Wiener in 89 and then improved by Bonnier-Durffy in 99. They showed if D is smaller than N to the power of 0.292, then you can break RSA in polynomial time. Now it's an interesting question to ask, what happens if I choose D, which is just slightly above this bound of N to the power of 0.292? Well, then you can't show that RSA becomes completely insecure, but you can still show something very surprising and that is this line of research here, starting with a result by Ernst-Jochim Smae and Tevecha from 2005 and then improved by Aono and Takayaso and Konihiro. They showed that actually whenever you use small D, meaning D smaller than N, then RSA admits for so-called partial key exposure attacks. What are partial key exposure attacks? Well, this means that whenever you use too small D, then you can break RSA in polynomial time, provided that you know a fraction of the bits of D. I guess this graph here explains these results best. So on the horizontal axis, we see how large D is in comparison to N and on the vertical axis, we see how large of a fraction of bits of D you need to be able to break RSA in polynomial time. And now these results by Wiener and Bonnier-Durffy, they show us if we are below this 0.292 bound, then you don't have to know any bits at all. And then these partial key exposure attacks now nicely extend these results as they show if you are just slightly above this bound, then you have to know a really small fraction of bits and then the larger D gets, the more bits you have to know. Then finally, at this point on the right of this graph, where D is of the same sizes and then these attacks show you that at this point, you really need to know all of the bits of D. This is quite a natural ending point for these attacks because if you choose D properly, meaning choose D at random, then with overwhelming probability, D is of the same sizes. And at least we hope that for these properly chosen keys, RSA has no such weaknesses. Let's move on to CAT RSA. So in CAT RSA, the public key is exactly the same as in RSA, but the private key looks a bit different instead of having just this one secret exponent D. We now have two shorter secret exponents called DP and DQ. Now we can of course ask the exact same question for CAT RSA and that is, does CAT RSA also become insecure if we use it with short secret exponents? Which we'd see if we use it with DP and DQ significantly smaller than the square root of N. We now already asked this in 89 as an open question and it took actually quite some time until this question could be answered. Until then in 2007, Johans and Mike gave an affirmative answer to this question. Quite recently, this has been improved by Takayasu Lu and Peng in 2017 and then again in 2019. And now we know that if DP and DQ are smaller than N to the power of 0.122, then you can break CAT RSA in polynomial time. And now to our result, what we showed is basically the CAT RSA counterpart for the result on the bottom left of this slide. We showed that also CAT RSA with two short secret exponents admits for partial key exposure text. Let's also take a quick look at the graph for our attack. Again, on the horizontal axis, we see how large the secret exponents are. And on the vertical axis, we see how large of the fraction of the secret exponents we need to be able to break now CAT RSA in polynomial time. This is previously known results show us if we are below this 0.122 bound, then we don't have to know any bits at all. And now our partial key exposure attack extends these results and it shows if we are slightly above this bound, then we have to know a really small fraction and then the larger the secret exponent get, the more bits we have to know. And as in RSA, we also reach here a very natural ending point. She now is where DP and DQ are of the same size as the square root of N, which again is the point which properly chosen keys have. Now the proof for our new attack basically consists of two steps. In the first step, we take another look at this TLP-19 result and we give a new proof for it. The advantage of our new proof is that it provides much more intuition than the original proof did. And then we use this intuition to generalize this TLP-19 result and with this generalization, we then obtain our partial key exposure attack. So let's first take a look at this new simplified proof for TLP-19. This attack is based on Coppersmith method, which is a famous algorithmic technique to solve problems of this kind here, problems which I like to call Coppersmith type problems.  What you want to do is you want to find all the common roots of these polynomials, modulo m, with the restriction that the absolute values of the components of these rules should be upper bounded by the bounds xi. Now in general, this can, these problems can be very hard and in fact, you can even for some instances, rule out the existence of polynomial time algorithms to solve these problems. But what Coppersmith discovered is that if the bounds are sufficiently small, then these problems can become easy. What you should keep in mind is that the smaller these bounds are, the better you can solve these problems. Coppersmith suggests the following strategy to solve these problems. You first fix a parameter small m, which is polylogarithmic in this modulus m, then you define so-called shift polynomials. After that, you take your shift polynomials and plug in these bounds x1 up to xk into these polynomials. Then you construct a triangular lattice basis matrix consisting of the coefficient vectors of these shift polynomials. Then we have this nice heuristic, which tells us if this enabling condition holds, then we can compute all these roots are in polynomial time. And this enabling condition basically says that the determinant of this basis matrix has to be sufficiently small, namely its absolute value has to be roughly upper bounded by this capital M to the power of small m times the dimension of the lattice generated by V. So how can we apply Coppersmith's method in the cryptanalysis of CTRSA? Well, just by definition, we know that the product of E and DP has to be one plus a multiple of P minus one. Similarly, we know that the product of E and DQ has to be one plus a multiple of Q minus one. And what you can easily show is that if both DP and DQ are significantly smaller than the square root of N, then both K and L become kind of smallish. So if you use CTRSA with short secret exponents, then you know that there are two polynomial equations which have small unknowns, which means we may hope to compute these unknowns using Coppersmith's method. But if you could really do that, then we would of course break the security of CTRSA. So this sounds quite promising, but you can't immediately apply Coppersmith's method here because so far we have two equations defined over the integers, but what we actually want is polynomials modulo sum integer, but that's not a huge problem. We just take these two equations modulo E and then we obtain these two polynomials here, F and G in three variables. And these both have the same root modulo E and that is the root K, P and L minus one. First polynomial comes directly from the first equation and the second one comes from the second equation if you multiply it by P and then rearrange some terms. Actually, you can even learn a third polynomial for that you have to rearrange terms again and then multiply these equations together in a clever way. Now we have this quite nice situation. Now we have three polynomials with a small common root modulo E. And if we could compute this root, then we would break the security of CTRSA with short secret exponents. Now, before we apply Coppersmith method, I would like to have a few words on why we exactly chose these three polynomials. I mean, you could, of course, derive many different polynomials from these two CTRSA equations, but we think these three are actually the best that you can use because in Coppersmith method, you always want to satisfy these two words of thumb. First one being your polynomials should share as many monomials as possible. And the second is in every monomial, the degree of each variable should be as low as possible. We think that with respect to these two rules, our three polynomials are the best that you can obtain from the CTRSA equations. Let me visualize this a bit. First, let us write the polynomials more explicitly so that we write in every monomial be the exponent of every variable. Now, the key really for all of our attack is to think of these polynomials in some geometric way. What we want to do now is to think of these exponents in the monomials as vectors in three-dimensional space. So this 0, 0, 0 monomial would be the 0, 0, 0 point. In a three-dimensional space, this 1, 0, 0 would be the 1, 0, 0 point and so on. Now, these three points, which we now see here in the three-dimensional space, are the monomials of F. What we say now is that the area enclosed by these monomials is the polynomial. So this area here is our polynomial F. Do the same thing for G, that's G, and again, the same thing for H, and then H looks like this. Now let's take another look at our rules. First one being that our monomials should share as many monomials as possible. And then if you take a look at this graphic, and you see that this polynomial satisfies this quite good. We have six different monomials, but three of them, so the half of them, actually appears in multiple polynomials. So that's nice. And the second rule in every monomial, the degree of each variable should be as low as possible, but that's also satisfied quite good because you can see we have no monomial in which the degree of any variable is larger than one. In fact, in F and G, we even have this 0, 0, 0 monomial. So this looks quite promising, and therefore one may hope if we now apply Coppersmith's method to these three polynomials to obtain a quite good result. But unfortunately, if you now apply Coppersmith's method and then calculate the enabling condition, then you actually get a quite disappointing result, and that is this enabling condition here, which now tells you you can extract this root KpL-1 provided that dp and dq are smaller than n to the power of 0.25 times e to the power of minus 0.286. But here we are dealing with short secret exponents here at ERSA. If the secret exponent are small, then necessarily the public exponent is large, and in fact, in practice, e would really be of the same size as n. But then this product here becomes smaller than one. So this enabling condition now tells us you can extract this root if dp and dq are smaller than a number which itself is smaller than one, okay? And this means you can't extract the root. That's a bit strange because with respect to these rules of thumb, we really did the best thing possible for CRT-RSA, but still we obtained such a bad result. So what did we do wrong? The thing is, so far, we didn't use all the information that we have. First one is that we know a multiple of one of the unknowns. We know n, and we know n is a multiple of the unknown p. And this knowledge is in no way reflected in Coppersmith's method. The second thing is, our polynomials have small coefficients, and it's known from previous Coppersmith-type results that if you have small coefficients in your polynomials, then you usually can exploit this in some way. And we also didn't do this so far. I would like to show you now that we can exploit this additional information to satisfy two more rules of thumb. Rule number three is, the total degree of the shift polynomial should be as low as possible. And the fourth rule being, the shift polynomial should have as few monomials as possible. Now, how can we satisfy these rules using our additional information? I would like to illustrate this with a small example. All that, let us take a look at the shift polynomial f to the power of i. This is a bivariate polynomial in xp and yp, and this polynomial has the root k and p. Now, the key is again to think of this polynomial geometrically. And if you would do the same things that we did on the previous slide, then you would find that this polynomial looks like a triangle of width and height i. Now, we want to use this information that we know a multiple of p. For that, we introduce a new variable, which we call yq. And now we multiply our shift polynomial by this new variable. And after that, we replace every term of the form yp times yq by n. By that, we obtain a polynomial in three variables, xp, yp, yq. And what's not hard to see is that now this polynomial has the root k, p, and n over p, or state differently, k, p, and q. What happens to the shape of the polynomial is very nice, and that is the following. If we now multiply our shift polynomial by yq to the power of i over two, and then replace these terms yp times yq by n, then it is as if we would move this triangle in this coordinate system to the left. And every point which moves through this xp axis disappears and then reappears in a new coordinate system, representing the variables xp and yq. And if we now take another look at our rule number three, then we find that we did a quite good job here because we started with our polynomial f to the power of i, which as this graphic shows has a total degree two times i. But then our new polynomial, we can see has only degree three over two times i. And therefore, we now satisfy rule number three better. Let's also do a similar thing for rule number four. For that, we want to use the fact that our polynomials have small coefficients. And what we want to do now is introduce one more variable, which we call xq. And what we want to do now is we want to replace every term of the form xp times yq by xq plus one times yq. By that we obtain a new polynomial in four variables, xp, xq, yp and yq. Now this has the root k, k minus one, p, pq. And now because our polynomials have this small coefficients, lots of nice cancellation is going on between the monomials of our shift polynomials. And then the shape of our polynomial becomes this here. And this is with respect to rule number four, very good because we got rid of lots of monomials, now have a new shift polynomial which has much less monomials than the polynomial which we started with and therefore we satisfied rule number four better. Now you would simply generalize these ideas and then you would finally get a nice enabling condition that you can extract the root if the p and the q are smaller than n to the power of five over 56, which is roughly n to the power of 0.89. And then it's very easy to improve this and finally obtain this Takayaso looping result for that to do something which is in terms of Coppersmith method, just standard. You just have to include so-called extra shifts in the variables yp and yq, then parameterize them correctly and then you are done and get this Takayaso looping result of n to the power of 0.122. Now that we have discussed our new proof for the TLP-19 attack, we now can finally move on to our partial key exposure attack. For that, let's quickly summarize what we did so far. So in the TLP-19 attack, we started with the CIT-RSA equation and obtained from these equations three polynomials which have the root Kp L minus one module E. Then applying Coppersmith method directly to these polynomials unfortunately didn't give us a successful attack, but then we had this additional information that we know a multiple of one of the unknowns and the fact that our polynomials have small coefficients. And then we incorporated this information using our two metric view on Coppersmith method and with that eventually obtained the TLP-19 result. Now in our partial key exposure attack, we now assume that we know some bits of the CRT exponents. This additional knowledge gives us three additional polynomials which we call F tilde, G tilde, H tilde and these polynomials have the exact same root. The situation is exactly as in the TLP-19 attack. If we now apply Coppersmith method directly to these polynomials, we unfortunately don't get a working attack. But as before, we have additional information which can help us to get a successful attack. But now we only have the additional information that we know a multiple of the unknown. For our partial key exposure attack, we no longer have polynomials with small coefficients. In fact, the coefficients are very large of this F tilde, G tilde, H tilde. But nevertheless, we can still at least use the fact that we know a multiple of P and then incorporate this again using our geometric idea and with that, you already obtain a working partial key exposure attack and its graph looks like this. What's nice about this attack is that we already reach this natural ending point of the square root of N. As you can see here on the right end of this graph, but what's a bit odd is the left end of this graph. Here we now reach a point of 0.083 and for every dp and dq which are above this point, then we have to know some of the bits to be able to break CRS-A. But this of course goes against the TLP-19 result which already showed us if we are below 0.122, then we don't have to know any bits at all. But this makes sense that we don't match the TLP bound so far because remember, in TLP-19, we have this additional information that we have polynomials with small coefficients. Within our partial key exposure attack, we no longer have this information when it only makes sense that we get a worse bound. So the only thing that prevents us from reaching this 0.122 bound is the fact that we don't have polynomials with small coefficients. This means on the other hand, if there was some way to include polynomials with small coefficients into our attack, then we would reach this 0.122 bound. And we came up with a strategy to include polynomials with small coefficients to our attack. And as before, the key here is to think of the whole thing geometrically. What we want to do now is to visualize geometrically the polynomials that are in the Takayasu loop and basis matrix. You can't really draw them because geometrically they would form a six-dimensional object, but still you can simply draw two-dimensional slices of them. If you do this, then you would find exactly the pattern shown here on this slide. Now we do the exact same thing for our basis matrix, and then we would find a much simpler pattern, which are simply these squares here. Yeah, that we have this simpler pattern comes from the fact that we don't have the small coefficients. If we had them, then we could also use the pattern by Takayasu and Peng, but unfortunately we have large coefficients and therefore we have to stick to these squares. But then what we found, what we can do is we can introduce one parameter sigma and then use sigma to control the width of our squares. So to turn them into rectangles. This works even though we don't have the small coefficients. This wouldn't work with all arbitrary polynomials, but due to special properties of our polynomials, this works in our partial key exposure ethic. Then we found, well, if we now compare the Takayasu and Peng, let us base matrix with our modified basis matrix, then we find these orange-colored rectangles in their basis matrix, which correspond to monomials which aren't already included in ours. Then we thought, okay, now we simply take the polynomials from the Takayasu and Peng-based matrix which add these monomials to the basis matrix and also add them to ours. So having a basis matrix consisting of a party of our polynomials and party of the Takayasu and Peng polynomials. So then we would find the combined ledges-based matrix, now prioritized by our sigma and by the tau from Takayasu and Peng. Now it's simply a thing of optimizing sigma and tau and if you choose them properly, then you finally obtain our main result and this is the partial key exposure attack which this graph, now that the red part is the, our first partial key exposure attack and now with incorporating these extra polynomials from Takayasu and Peng, we finally get this blue area in addition which then finally matches this 0.122 part. So let me conclude my talk with a short summary. So the first thing that we did was give a simplified proof for TEP-19 with more intuition than the original proof had. And then we used this intuition to obtain the first partial key exposure attack on short secret exponents, CITRSA. And what we hope that you take away from this talk is that it can be very useful to approach Coppers method with a geometric view as it can provide deeper insights and lead to stronger results. I would like to end with an open question. So what's a bit strange about our attack so far is that it does only work for exposed least significant bits. The partial key exposure attacks on RSA, so not CITRSA, just RSA, they usually work for both exposed most significant bits or exposed least significant bits. We tried quite a few things to also make our attack work for exposed most significant bits, but it seems like the techniques that were used in these partial key exposure attacks on RSA that they don't translate to CITRSA. So it looks like here still some new techniques have to be invented to also obtain a MSB type partial key exposure attack on CITRSA that might be worth looking into. Thank you very much for listening and goodbye.