Welcome back to another screencast about the division algorithm. In this video we're going to pick up on an idea that you might have noticed in the last video about using the remainder in the division algorithm to set up cases in a proof. Now when we divide any integer a by a positive integer b, the division algorithm says that although b may not divide into a evenly, you will definitely divide in and get a quotient and a remainder, q and r, such that a is equal to bq plus r, and r satisfies the inequality 0 less than or equal to r strictly less than b. For example, and this is our first example we saw of this, if a is equal to 345 and b is 8, then we can write 345 equal to 8 times 43 plus 1, and that indicates that 8 goes into 345 43 times with a remainder of 1. Let's do something different with this equation here. Let's subtract 1 from both sides and get 345 minus 1 equals 8 times 43. This is certainly true, but it's saying something interesting. It's saying that 345 minus 1 is divisible by 8, it's a multiple of 8. So we've seen this language before where 8 divides a difference, and what this is really saying here again is that 345 is congruent to 1 modulo 8 because 8 divides their difference. So what the division algorithm is actually telling us is something about integer congruence, not just about divisibility. Let's go back to another example we saw in that first video, with a equal to negative 87 and b equal to 6. In that case, the division algorithm gave us negative 87 is equal to 6 times negative 15 plus 3. If we subtract the remainder from both sides, we get negative 87 minus 3 equals 6 times negative 16, and so negative 87 minus 3 is divisible by 6, and that means that negative 87 is congruent to 3 modulo 6.  So what that means is that a minus r is a multiple of b, which means a minus r is divisible by b, which means that a is congruent to r mod b. So in other words, and I'll state this as a theorem, if a and b are integers with b positive and a equal to bq plus r, then a is congruent to r modulo b. And what that means in English is that a is always congruent to the remainder we get when we divide a by b. So this is a pretty nice way to think about an integer congruence. It's just something that's naturally associated with regular division that we've known since the third grade. But there's more. The division algorithm doesn't just give the existence of q and r. It says that if we require r to satisfy the inequality, 0 less than or equal to r or less than b, then those integers are unique. So the division algorithm, in the division algorithm, the r is not just any old integer, it's the unique number within that range such that a equals bq plus r. For example, we know that 345 is congruent to 1 mod 6, but it's also congruent to a number of other things mod 6. For example, 7 and 13 and negative 5, all these are different by multiples of 6. But 1 is the only integer in that list that's non-negative and less than 6. So what we actually get from the division algorithm is the following. If a and b are integers with b positive and a equal to bq plus r given by the division algorithm, that is that r is bigger than or equal to 0 but less than b, then r is the smallest non-negative integer such that a is congruent to r modulo b. In an earlier video, we gave this value a name. We called it the least non-negative residue mod b. That least non-negative residue is the remainder that we get from the division algorithm. Now the reason we care about the least non-negative residue of an integer modulo something else is that oftentimes you want to reduce an integer down to its quote unquote lowest form and this number is what we are after. Here's a quick example and in the next video we'll give a bigger example that hasn't applied flavor to it. So what's the least non-negative residue of 2012 mod 17? That is of all the numbers that are congruent to 2012 modulo 17, which one is the smallest one that stays out of the negative number territory? So the result that we quoted above says that we can just look to the division algorithm for this. We can implement the division algorithm through just regular long division and I'm going to do that here on the screen. Why we see here that 17 goes into 2012 118 times and the remainder is 6. So that means that 2012 is congruent to 6 mod 17 and moreover that 6 is the least non-negative number to which 2012 is congruent mod 17. It's the least non-negative residue. To check we can just rewrite the division algorithm result as 2012 equals 17 times 118 plus 6. Now subtract the remainder to get 2012 minus 6 equals 17 times 118 and you can see here that 2012 is indeed congruent to 6 mod 17. One quick concept check before we're done. What's the least non-negative residue of negative 16 mod 5? Well you can automatically rule out A because we're looking for the least non-negative residue, so anything that's negative is out automatically. If we use the division algorithm here, although maybe not long division because there are negative numbers involved, we can get negative 16 equals 5 times negative 3 minus 1. Now this is correct but the remainder is negative and so it doesn't fit in the division algorithm. So instead let's bump up the quotient by 1 and make that a negative 4 and change the remainder to a 4 instead. So this equation is also true but this time the remainder is the right size. It's between 0 and 4 as the division algorithm demands that it be. So the remainder is 4 and that means that negative 16 is congruent to 4 mod 5 and that 4 is the least non-negative number to which negative 16 is congruent mod 5. That's the least non-negative residue. So that's a nice connection and an important one between division and congruence. Thank you for watching.


It's going on everyone. Sam here with late sports cards. We've been 23 at Bowman Chrome Baseball, Hobby HDA, Hobby and HDA choice. Eight box makes number four random team style. Here is a look again at your random results. As always, you can find those on the website, under the results tab, as well as the link in chat. So good luck here everybody, let's do it. Do you wanna see if the Florida game's on? Yeah. Maybe it's probably not gonna be better. The game after this is West Virginia in the other team.  Yeah, West Virginia, that's actually a good one. Because what are they, both Big Ten or ACC? West Virginia's not Big Ten. They might be ACC. Syracuse and Rue. What was that one that you just went by? This is the Hampton Howard. Oh, Hampton Howard. It's up Dan? Dan, the wise man, what up dude? What up Dan? BYU Arkansas. We're feeling like the brass band. Yeah, two QB sneaks, now I saw that for sure. Are we telling them it hurts? No, there's Gabriel Hughes, Bama Thai Simpson, because they benched Milrow. Milrow was their couple weeks starter, but they didn't look that great. Lazaro Montez on the vapor wave to $1.99 for the Mariners, base and base. Time to see 7-6 against Florida. Is that not on? I can't find it there. ESPN, really? I lost to click one of those. That's Lazaro Montez again to $1.99. One for the Lazaro Montez, Rambler. I'm a bot, so I'm a bot. Base auto is Alfredo Duno, nice one there for the Reds, congrats, Reds. Don't know if you know it, Sam, but I mean, middle name's actually a bot. I don't doubt that. There's a blue Corbin Carroll rookie, nice to $150. Yeah, I hear you Peyton, I hear you. I know what you mean. It is, I mean, it's, we have it in the title, you know, high risk, high reward. It's definitely risky, but it's calculated risk to some degree too. That is a green of Alec Thomas to $1.99. World baseball classic, Hans Montero. You're gonna mess with Jaden. What is that? You're gonna mess with Jaden. No, slap said, I got the money. Oh, slap, that's his real name. Wickleman Gonzalez, that's actually Donnie's name. Wickleman, yeah. Wickleman Gonzalez. For the Red Sox, Ethan Salisbase, nice one there, Bauston. That is a Jader Aranamo. On the shimmer first for the Brewers, Raymond Mola. Oh, who wants to watch Giants and San Fran on Thursday night football? It's Matt Mervis for the Cubs to $150. And Victor Cutter-Coffee, base auto, Daniel Guillarte. It's going to the Brewers. Nice one there, Milwaukee. Rashad picking up a iMac Collegiate, I believe, either iMac, baseball, iMac Collegiate, I didn't see which one it was. Personal, thank you buddy, appreciate that. That is a Riley Green, it came to league, Reavos, Christopher Toren, Go Gators. Oh, Josue De Paula, that's not a great, Brandon Maia first, that's not a great first play to look, not gonna watch. I'm shocked they let somebody wear 15 there. There's J-Rod to 150, you know what I mean? Yeah. That's a little odd. Justin Crawford, Josue De Paula. The shimmer of Marcelo Meyer for the Red Sox. Parada, Samuel Munoz. There's a Miguel Blaise to 299, thing right there, Jeremy Pena Iconic. That is a William Regoya, Arthur Jones, Jackson Merrill, Andy Pajes, Roman Anthony, Ben Joyce, Noyce Joyce refractor to 499, Angels. Will Warren, Mini Diamond's Auto II, 299. And that's going to the Yankees, congrats Yankees. Lantigua, Henry Shabilly, Fox Trace of Roman Chrome. It's a Adley Rochman, it came to league, Spada in A, Brooks Lee. Alex Bregman. Ooh, nice, that's awesome, Ramar's. Axial Plaws to 499, that's solid, dude. That's a solid draw in the 10 case, I'm pretty sure. Zach Veen, Edwin Rodriguez. Purple shimmer to Marc Johnson to 250 for the Pirates. Soto and Osardio. Ooh, Orange is Daniel Guillarté. Six to 25, true Orange going to the Brewers. Congrats on that, here you go Brewers. How about Jason A with a plates and patches division? And Tom B with a spot in Flawless. Thank you, Jason and Tom. Appreciate you guys, Braylor Guerrero. I would just be safe. For the first week, pretty much any Orange, then after that I can get a little bit more selective. Any Orange bat, that would, yeah, just not Pitcher essentially. That is Brooks Lee. Lantigua, Henry Chevilli, Chili Chevilli. Chili Chevilli. Jackson Merrill, Javier Rivas. So I think plates is down to five now. I believe plates is down to five. That's Nelson Velazquez for the Cubs I believe to 499. Plates is I think at five, let me double check that. My A of first. Or what? For divisions. Yeah, five to go on plates divisions. Base Auto is Daniel Mateo. That's going to the Rangers. Congrats, Texas. Drew Jones, Justin Crawford. I think Flawless is at six. I think it's at six, yeah, I believe so. Jordan Walker, he came to the league, rookie. Basin, Yosue DePaula. What's up, Brian? Basin, our. And base, base. Tristan Costas, he came to the league to 150 on the mini diamonds. Nice one there, Red Sox. That is a Miguel Amaya to 299. Yeah, me too, I'm pumped for the Flawless cases. They're going to be fun, man. Flawless boxes, I suppose. Yeah, they're a lot of fun. Flawless basketball is good, man. Los Romantes, everything the game used, which is nice. Great checklist as always. Salas, Jackson, Holliday. Yes, Quintuple is after this. Yes, correct. Yellow is Anthony Rizzo, 275. Yes, yes, yes. Starting at 7, or 815 to 930, I believe it is. Brian Rincone, refractor, auto to 499. Going to Phillies, congrats, Phillies. This one there, Philadelphia. So make sure we get that all set up. We get to go. Don and I'll rehearse. Don and I'll throw some shots up. Red Amaya first. When do we eat? Whenever, a lot of times when I like step out in between breaks, I'll grab like a snack or something, cut her coffee. But like full meals, almost never. It's usually, if we ever get like pizza, it's usually just like flott, it's like absolutely just. Piece of air, piece of air. Yeah, exactly. Matt Mervis to 99. Green. Maybe a nimble there. Yeah, so I'll usually eat lunch before I cut. Like I brought lunch in today. Before I, when I came in, I came in at like two. So I ate that and then I'll probably be good for the rest of the night. Rooksley, Shimmer, and base auto, Luke Gold. Nice one there for the Tigers. Congrats, Detroit's, Flaws and Juan Benjamin. Four boxes of choice now. There you go. Like a 14 year grown. All right. Base first auto is Adon Sanchez for the Cubs. Nice one there. Got a Luke Berryhill. First base auto for the Astros, Grats Houston. And Mini diamonds is Ben Metzinger to 299. Hello, Steve. Steve. Steve. Go birds. Go birds. Here's your link again to Flawless, number 32. That is at six spots remaining. Six to go. Got to get plates filled up as well. Both of the plates breaks one random team at 23. 23 to go.   And then NT filled up as well. Down to five divisions on plates. Three divisions on NT, which is freaking awesome. Thank you all. Yeniel LaBoy, I'm gonna give that to Donnie for to 299. Yaboy LaBoy. And I'll show when it gets top loaded and everything as well. Stuck on that annoying stuff there. Henry Chavilly, nice one there for the twins. Chili Chavilly. And first base auto is Peyton Williams. Going to the Blue Jays. All right, let's keep it moving here. On to the next. Hold on, do you have any more? All right, we've got base auto of Jordy Vargas. Going to the Rockies, nice one there. Grats on that. Got base auto is Yolanda Rivera. Going to the Nationals. Grats Washington. And then green is Henry Ramos. That'll be going to the Royals. Grats on that Royals. I'll show once you top load it. I'm just gonna show it again real quick. Thanks, sir. Donnie worked his magic. There's the Yeniel LaBoy. Nice and top loaded, ready to go. Yep, it's magic. It is, it is magic. Got a Emmanuel Terraro. Nice one there for the Pirates. Nice as signature in this entire class, for sure. We've got a another Daniel Guillarte. That is gonna be at first base auto for the Brewers. And then purple. Jesus Bougarin, dude, I love the color match when you get a Rockies purple is unmatched, bro. To 250, congrats on that Colorado. Gorgeous, gorgeous color match. All right, let us, Jason with two in flawless. Thank you, Jason. We're down to just four spots, Donnie. Nice. That's four spots to go in flawless. Jason, thank you, buddy. Appreciate it as always for Tago. Can't spell. Let's do a quick recap. All right, we've got base autos, Guillarte, Emmanuel Terraro, Jordi Vargas, Joinda Rivera, Henry Chevilli, that's Henry Chevilli, Peyton Williams, Luke Berryhill, Aiden Sanchez, Luke Gold, Daniel Mateo, Daniel Guillarte, Wicklman Gonzalez, Alfredo Duno. 499, Brian Rincone. To 299, Benton Metzger, Will Warren, Yennyola Boyd, to 250, Hazard Bougarin, to 99, Henry Ramos. And then true orange to 25, Daniel Guillarte. That'll do it for the break, guys. Thanks again for the pill.


Hello, everyone. Welcome to this talk. I'm going to talk about constructing locally leakage resilient linear secret sharing schemes. This is a joint work with Maji, Hanat, and Tom. So in this talk, we're going to talk about locally leakage resilient secret sharing schemes. So in a classical setting, in your secret sharing schemes, you have a dealer that takes a secret S and sample N secret shares, S1, S2, and SN. The security notion guarantees that for any unauthorized set of secret shares, it is uncorrelated with the secret S. So what if the adversary leaks local information from every secret share? For example, it learns a bit BI from every secret share SI. So is the joint distribution of the leakage correlated with the secret S or not? Locally leakage resilient secret sharing schemes ensure that the joint distribution of the leakage is uncorrelated with the secret S. So why do we study leakage resilient secret sharing? It turns out that this is a very useful primitive and connected to many other fields. For example, in this fascinating problem called repairing error correcting code, where the objectives that you learn minimum information from every secret share, and you want to fully reconstruct the secret using this information. So intuitively, if you are able to reconstruct the secret S, then the secret sharing schemes is not leakage resilient. And on the other hand, the leakage resilience asks for much stronger security guarantee that not only you cannot reconstruct the secret, this information you learn from every secret share is actually revealed no information about the secret. So the leakage resilient secret sharing schemes has also been used as a building block to construct a secure multi-party computation protocols that is resilient to local leakage attacks. And it also has been used to build other primitives such as non-malleable secret sharing schemes. So since the introduction of leakage resilient secret sharing, there has been two main research directions. So the first research direction is to construct new secret sharing schemes that are designed to be leakage resilient. So we have a fascinating body of works that construct secret sharing schemes that is robust against many, many very sophisticated leakage family. However, these constructions usually incurs a significant overhead and loses some algebraic structure, such as linearity. And these crucial algebraic structures could be very important for the application of secret sharing schemes. So therefore, there is another line of works that investigate the leakage resilience of prominent secret sharing schemes, such as Shamir secret sharing and additive secret sharing schemes. Since the application of secret sharing schemes usually use such prominent secret sharing schemes, this line of work have significant impact on the real-world implementations, and our work belongs to this line of research. So let me set up the context for this work first. So in this work, we consider Macy's secret sharing schemes corresponding to a random linear code. So Macy's secret sharing schemes works as follows. So given any code C, which is just a subset of the vector space, you can construct the secret sharing schemes as follows. So let's say you want to sample the secret share of a secret S. To do this, you just sample a random code word from this code C, conditioned on that the first coordinate is identical to the secret S. Then the rest of the coordinates are the corresponding secret shares. So it turns out that if the code C is linear, then the Macy's secret sharing schemes is also linear. And it turns out that every linear secret sharing schemes is a Macy's secret sharing schemes corresponding to some linear code. So for example, the well-known Shamir secret sharing schemes is nothing but Macy's secret sharing schemes corresponding to Reed-Solomon code, and additive secret sharing schemes corresponds to the parity code. So we consider Macy's secret sharing schemes corresponding to a random linear code. So how do you sample a random linear code? You just sample the generator matrix G uniformly at random. And note that since we consider an exponentially large field F, when you sample a random matrix G over exponentially large field F, the random matrix is maximum distance separable with overwhelming probability. And when the code word G happens to be an MDS code, the Macy's secret sharing schemes corresponding to G is nothing but a threshold secret sharing schemes with N parties and K plus one reconstruction threshold where K plus one is the dimension of the code. Okay, so now we're ready to present our results. So let Namda be the security parameter which represents the size of each secret share. So remember that every secret share is an element from the field F. Therefore, the size of the field is roughly two to the Namda. And we assume M bits are leaked from every secret share. Our result is as follows. So you pick any N to be the number of parties. You pick any K such that K plus one is the reconstruction threshold. And let M be any constant. If you have the guarantee that K, roughly the reconstruction threshold is greater than half of N, which is the number of parties, then the Macy's secret sharing schemes corresponding to a random matrix G is M bit locally leakage resident except with exponentially decaying probability. So we do need the number of parties N to be less than the security parameter to ensure that the G is MDS with high probability. So as a representative example, we can set the number of reconstruction hold to be one-third of Namda and to be half of Namda. So our second result complement our first result where we show a bottleneck for the existing analytic approaches. So in their seminal work, Ben-Hermuda at all introduced this innovative Fourier analytic approach, which is adopted by all existing work, including this one, to prove leakage resilience. We show that this approach is bound to fail when the number of, when the reconstruction threshold is less than half of the number of parties. So in detail, this approach used a Fourier analytic expression as an, as a proxy to upper bound the statistical distance. We consider the leakage function to be the indicator function of quadratic resducity. That is the leakage function output one, if the corresponding secret share is a quadratic residue and zero otherwise. We'll prove that given any linear secret sharing scheme, this Fourier analytic proxy is at least the half, at least the one for this leakage function. So remember that this proxies used up to upper bound the statistical distance. If it is greater than one, then it always give an inconsequential bond. So due to this, the first result I just present to you is actually the optimal result. One can hope to prove use the existing technical approach and to prove leakage resilience when K is less than half of N requires it's significantly different ideas, even just for this one function, the indicator for quadratic residue city. So this is actually motivated because the Shamir secret sharing schemes, Shamir secret sharing based MPC protocol is multiplication friendly when K, the degree K is less than half of the number of parties. And in some ongoing works, we show that we use a combinatorical argument to show that you can actually prove leakage resilience when K is less than half of N, if the leakage family L is small. Okay, so before I present the technical highlight, let me summarize some of the relevant prior works. So in the original work by Ben Hamoda at all, they show that if you are given any MDS code G, the Macy secret sharing schemes corresponding to G is leakage resilient when M bit is leakage, when M bit is leaked from every secret share, as long as K is greater than a constant fraction of N, where this constant fraction depends on the bit leaked from every secret share. So roughly when one bit is leaked from every secret share, you need that K is greater than 0.85 times N. And this fraction increases as the number of bit leaked increases. In particular Shamir secret sharing schemes is one bit leakage resilient if K is greater than 0.85 times N. So to compare their work with ours, their construction is deterministic because their proof works for any fixed MDS code G. And they prove that K is, it is leakage resilient as long as K is greater than delta M times N, which is at least 0.85. While our construction is randomized with exponential failure probability, I will prove that K need only be at least half of N. So in another, our recent work, we consider the Shamir secret sharing schemes with randomly chosen evaluation places. And we consider a severely restricted leakage model that we call physical bit leakage. So in this model, every secret share is stored in their natural binary representation and the leakage function can learn the bit stored at specified locations. So for this restricted leakage family, we show that with overwhelming probability, Shamir secret sharing schemes with randomly chosen evaluation places is leakage resilient even if the reconstruction threshold is only two and the number of parties can be any polynomial in the security parameter and the number of bits leaked from every secret share can be an arbitrary constant M. So note that this work also employs the existing Fourier analytic approach and they prove a result, they prove that it is leakage resilient even when K is less than half of N. However, this result does not contradict the bottleneck we presented because they only considered physical bit leakage. In particular, the counter example that we raised that testing whether a field element is a quadratic residue or not cannot be learned through physical bit leakage and to put this work into perspective, they also consider a randomized construction but their code generator matrix is sampled not fully random but from this distribution and they consider a very severely restricted leakage family namely the physical bit leakage but they prove a very strong result that the reconstruction threshold can be a constant as low as two and an unbounded number of parties. Okay, so now let me give you a very brief technical overview. So recall that we want to prove that Macy's secret sharing schemes corresponding to a random matrix is leakage resilient as long as K is greater than half of N. So the major challenging part about this result is that a typical union bound will not have worked. So for example, consider this very straightforward proof strategy let's say you fix a leakage function L and you prove that most the code are secure against this L and then your union bound over all the possible choices of the leakage function L and that gives you the result. However, this won't work. Why? Because the total number of leakage functions is very large. For example, let's assume that you are learning one bit from every secret share. So the leakage function L is the domain is the field F the range is zero one. So the number of leakage functions is two to the power of F. The number of leakage function for every secret share is two to the power F and then the total number of leakage functions from N shares is the N's power of this. So the important point is that the number of leakage functions is doubly exponential because the field size is single exponential. In comparison, if you look at our family of constructions the constructions is solely determined by the generator matrix which is of dimension roughly K by N. So the number of constructions is F to the power of K times N is this much, which is single exponential. So the number of leakage functions is much, much larger than the family of constructions. So you cannot hope to use a union bound over the choices of L to prove leakage resilience. So the technical novelty of our proof is that we identified a new set of tests. So the proof chooses gamma, sigma and A and they are constant. So a test is specified by a product space V which is V1 cross V2 cross VN. So every VI is of a constant size gamma. So we say a code word C is bad or fails this test V if a large fraction of the coordinates fall inside this VI. So that is the number of the set of indices where CI is in VI. If this set is too large we say this code word is bad and we say that a code G passes the test if only few code words less than A which is appropriately chosen constant A A to the power N code words are bad. So to give you some intuition about this test so if you fix any leakage function L1, L2 and LN where LI is the leakage function on the IS share the VI will be the set of field elements that are who has large Fourier coefficient corresponding to LI and if a code passes all the test V we're going to prove that it is leakage resilient against all the leakage functions so the intuition behind that is that for any leakage functions this code will only have few code words that has many coordinates with large Fourier coefficient so this set of tests this definition is inspired by literature in pseudo-randomness so intuitively if an object has a low correlation with all the Fourier characters you can think of it as being pseudo-random so here we are saying that a code G is pseudo-random if it does not have too many code words that are not pseudo-random so the benefit of defining this set of tests is that number of tests is actually much smaller so here's a simple counting argument remember that a test is specified by a product space V where every VI is of a constant size gamma so the number of tests is roughly this much which is single exponential in comparison the total number of leakage functions is double exponential so given this set of tests we are going to prove leakage resilience as follows so you fix any test V and you prove that the most Gs will pass this test V this is based on the combinatorial argument and then you can use a union mount thanks to the fact that the number of tests is small to prove that most Gs passes all the tests and the third step is that finding code G that passes all the tests we are going to prove that G is leakage resilience and this step is based on the existing Fourier-analytic argument introduced by Ben-Helmholtz at all so this step is where we inherently requires K to be greater than half of N so finally let me say a few words about the bottleneck we proved so recall that we show that the existing approach cannot prove leakage resilience when K less than half of N and in particular it cannot even prove leakage resilience for this single function that is testing whether a secret shares a quadratic residue or not so if you are familiar with the Fourier-analytic approach the intuition behind that is that the quadratic residue function is the function that maximizes the L1 norm of the Fourier coefficient this is intuitively why this is the most devastating case for the current proof strategy so as I mentioned earlier in some ongoing works we partially make progress to resolve this by using a purely combinatorial argument to prove that for any small enough leakage family L a random call G is leakage resilient against this L well this L could potentially contain this quadratic residue function and we also have other ongoing works that identifies the optimal leakage attacks in appropriate settings so with that I would like to conclude my talk and I will refer you to the full version of our paper for the additional subtleties in the proof thank you