Just to recall, we used density points, Lebesgue density points, to prove that transitive isometries are agotic with respect to Lebesgue. Not sure. And there were two key takeaways.   And secondly, isometries preserve density. So meaning that if I have a set and it has a certain density in another set, and I apply f to the n, the density of the image in the image set is the same for an isometry. All right. So that was example one, if you like. Here's example two.  In fact, it's agotic with respect to any invariant measure. Well, it's agotic with respect to Lebesgue measure. OK. So proof. So either using the Lebesgue density theorem or using the exercise from yesterday, you can show the following. So LDT, Lebesgue density theorem, or exercise 2 from yesterday. We can show the following. If x is the subset of r mod z, well, the Borel measurable set in r mod z with positive measure, then there exists a dyadic interval in the circle. Let me draw a picture. Here, x would be any set of positive measure. But somewhere, let's say this is the origin, which is equivalent to 1 under the identification of the circle with r mod z. And somewhere, I can find an interval i whose endpoints are of the form 2 to the m comma k plus 1 over 2 to the m for some k between 0, 2 to the minus 1. I can take the circle, and I can partition it such that. So you can partition a circle into intervals of this form. And you can let m go to infinity. And we get smaller and smaller such intervals. And the exercise yesterday shows that there's some interval somewhere where this set x, this positive measure set x, has very high density. So I'm going to add a quantifier here. So given epsilon greater than 0, there exists such an interval such that the density of the set x in that interval i is greater than 1 minus epsilon. Now suppose that x is f invariant. So suppose that f of x equals x. Or f inverse of x equals x, but that will imply that f of x equals x. OK. So what we're going to do is we're going to look inside this interval, and we're going to apply the dynamics. Now, the dynamics is not going to move this interval around. But it's going to do something else very nice, which is if we apply enough iterates, as we apply iterates, it expands each time by a factor of 2 until when we've applied m iterates to this interval, we get the whole circle. So note that f to the m of i, so I made that interval half open, we note that f to the m of i equals r mod c. Because if I take f to the m of i, I'm going to, if I don't do this mod 2, I get the interval k comma k plus 1. I'm sorry, if I don't do this mod 1, I just keep multiplying out. Multiplication commutes with taking things mod 1.  And then when you take that mod 1, you get 0, 1, which is the whole circle. All right. And so what happens to the density of f to the m of x? On the one hand, the density of f to the m of x over f to the m of i, this density, by definition, is the measure of the intersection divided by the measure of f to the m of i. Now notice here is not an invertible map. So the measure, if I apply, well, this is correct. And this is equal to the measure, now I'll make my note, of f to the m of x intersect i, because it is, divided by the measure of f to the m of i. That's because i is a very small interval. So why can I go from here to here?  So going backwards, there's no issues. This is, in fact, the image of the intersection is, in fact, the intersection of the images. So it's this ratio. Now, what I want to say is, well, the measure of f to the m of this intersection is not the same as the measure of this intersection. Because even though f preserves measure, that f inverse, which doesn't even exist, does not preserve measure. This is not f inverse. This is f. And so in fact, the measure of this, because we're looking at Lebesgue measure, the measure of this set is going to get scaled at each step by a factor of 2. So this is 2 to the m times the measure of x intersect i. And again, in the denominator, it's 2 to the m times the measure of i. And now, beautifully and quite remarkably and unusually, these two numbers cancel. And so this is equal to the measure of x intersect i divided by the measure of i, which is this conditional measure, which we've chosen i, so that this is greater than 1 minus epsilon. So on the one hand, we have this. On the other hand, f to the m of x equals x. f to the m of i equals the whole circle. That conditional measure, well, the measure of x is equal to the conditional measure, the measure of x conditioned on the whole circle. That's always the case. And that equals, because of this, the conditional measure of f to the m of x in f to the m of i. And so what have we shown? We've shown that the measure of x, I think you maybe can't read this little bit, plus the measure of x equals, what I wrote over there, f to the m of x in f to the m of i equals, by what we've said over here, the density of x in i is greater than 1 minus epsilon. So mu of x positive and invariant implies that mu of x is greater than 1 minus epsilon for all epsilon. And so therefore, mu of x is 1. And that shows that there are no f invariant sets, measurable sets of positive measure other than those with full measure. So therefore, f is ergodic. So what are the key things we used here? Questions about the proof? Again, we're not using any smooth. You're not seeing a derivatives pop up here. Well, secretly you are. These are derivatives, these 2 to the m's here. Someone's messing with my lights. Does that make it easier to see? Just choose something, though, because it's having some kind of epileptic seizure here. So what are the key properties of f of x equals 2x that we used here? Well, one is that f maps dyadic intervals onto the circle, 1 to 1, and onto r mod z. So the fact that under any interval, if I wait long enough, we'll map onto the whole circle. The other key property is that f preserves the shape. Well, I guess that's kind of implicit in what I've said here. The other key property is that f preserves density. And I said this before for transitive isometries. Could I have either both set all of them on or all of them off? I don't know who's controlling the lights. This way is better. Bad. Could someone please turn these lights off? Thank you. If you want, you could turn overhead lights. No, no. This is worse. This is OK. It's really strange. I feel like I'm lecturing in the middle of the night somehow. Where is that? OK. And so the second is that f preserves density, i.e., the measure or the conditional measure. Who's doing this? Can you please? No. Is this just happening? OK. The conditional measure for any m. And this is key if I take any m. If I look at the density of f to the m of some set x inside of f to the m of y, that's the same as the conditional measure of x and y. And now let's just for a minute review why that is the case. So this equals the measure of the intersection. So because f is injective, I should say, f preserves density on injective domains. So as long as y, f restricted to y, is injective, this is a true statement. Because we have the change of variables formula, which I'm going to write now. So the conditional measure, mu of f to the m of x. Sorry, I already wrote that. This is equal to the intersection right at this way, since it's injective. And now the change of variables, these are Lebesgue measurable sets. We're in dimension one. So if I want the measure of the image, and my thing is injective, what do I do? I integrate f, the derivative of f to the m prime of dx over the set x intersect y. And I divide by the integral over y of f to the m prime. Or so I should say d mu of x, the beg measure of x, d mu of x. Now in the case that we're considering, the linear case, this is constant and equal to 2 to the m. And this is constant and equal to 2 to the m times the measure of x1. And those cancel, and we get this density. Now, what's m? Oh, it's m dyadic. It's 2 to the m. It's OK. No, it's OK. It's always good to clear it, because I bet other people have thought that. OK. And this is the conditional measure. Everything cancels. OK, but now suppose that we just changed f of x equals 2x just a little bit, right? And we wanted to see what happens to density. Well, let's suppose, on the other hand, if f prime is not constant, and the measure of x and y is very small. So in general, in our proofs, we're actually interested in controlling small densities, which is the same as kind of getting large densities. If you can show that a density of x and y is very small, then you know that the complement has high density. And it's typically easier to show low densities are preserved than high densities are preserved. So on the other hand, if this happens to be small, that does not say less than epsilon than the best naive on the ratio or the density of f to the m of x and f to the m of y, given what I've got here, is just this is less than or equal to, well, the soup, the absolute largest value that I can get, overall x in, well, overall x in x intersect y of the absolute value. This should be this. It doesn't matter. I'm assuming the derivative is positive, but I'm assuming orientation preserving. But in general, if I had just a map from the real line to the real line, an upper bound on the numerator is the soup, and a lower bound on the denominator is an inf. And if I have a bound like this is less than epsilon, then this will be less than epsilon times this ratio. And what I want to impress on you is that if we think about our proof, we were not allowed to choose m in advance. We chose epsilon. Epsilon determined an m in which we had density bigger than 1 minus epsilon.  And we wanted to show that density, high density, was preserved, or equivalently low density was preserved. And here, the largest value of f to the m prime, it might be, suppose I'm very close to the doubling map, but I'm not the doubling map. This could be something like on the order of 2 plus some small number eta to the m, whereas this down here could be on the order of 2 minus eta to the m times epsilon first c1 map. And you'll notice that as m goes to infinity, this goes to infinity. So this proof that I just gave you uses very heavily the fact that the derivatives were precisely on the nose constant everywhere. And a main theme in smooth dynamics is that one needs to be able to bound quantities like this for nonlinear maps. And if you can do this for all m on some interval, what you've achieved is what's called a distortion estimate. So a distortion estimate says that if I choose an interval, well, if I choose some image, I can go back as far as I want. And the ratio of the max and the min of the derivatives up to the m is bounded, independent of them. All right. So that's getting a little bit ahead to the nonlinear setting. But I will come back to this, but I wanted to emphasize that this proof still needs some work if we want it to do anything more than just f of x equals 2x mob 1. OK. So now let's go to example 3. That's the cap map. So if we let a be 2, 1, 1, 1, then the map, f sub a on t2 is ergodic, which we know. We already know this because of Fourier series, so from Kadeem's lecture. But let's see if we can try to do a proof with density points. Well, what happens? Yes, I'm using, where am I using f of x equals x? Both are true. Yeah, it works out fine. Yeah, I know. That's something that's like, wait, what? No. It's because you're looking at the intersection of x with a little interval on which f is injective. So you do get that f to the n. Yeah, but it looks like, I know, it's a good point. I think about that. Yeah. In fact, I should have said f inverse of x equals x, because that's actually assumption that you need to prove it is not f of x equals x. But that's OK because f inverse of x equals x implies f of x equals x. So I should have made this my assumption. So thanks. I really used that. Anyway, so how would we try to prove this with density points? Well, we could do something very similar. So suppose here f is invertible, so we can do it either way. Suppose f of x or f inverse of x equals x, and this is f sub a. Well, if we remember our picture of what the cap map does, if this is the torus, suppose mu of x has positive measure, so x is some invariant set with positive measure, then somewhere, yes, indeed. I can find a very small ball in which I have very high concentration of x. OK. So, well, what happens if I iterate under f? What happens to this ball? Well, if you remember the picture from my first lecture, what happens is we have these two special eigen directions for a, and these two eigen directions, the derivative of f sub a is a, call this x naught, is everywhere a, right? It's constant derivative. Just like f of x equals 2x, I constant derivative 2. This is constant derivative of a. So everywhere, if I look close to a point and I look in its tangent space, I have these two eigen directions. And this eigen direction, so this point is mapped somewhere else. Maybe it's mapped here. I'm more likely to be mapped, say, over here. And this direction here is contracted. So if this is some arbitrary point x, then here's f sub a of x. And the linear map takes this eigen direction to this one and contracts it by some factor that I'll call 1 over lambda. And this direction is expanded by factor lambda. What is lambda? Well, you can solve the characteristic equation. And it's the larger of the two. I have to always write down the characteristic equation. x squared minus 3x plus 1 equals 0. And so the larger solution is 3 plus root 5 over 2, which, by the way, is the square of the golden mean. That's the square of 1 plus root 5 over 2. And actually, the slope here, just for fun, the slope is 1 over the golden mean, which is an irrational number. And here the slope is minus the golden mean. OK, so now I've really cluttered my picture. My point was simply the following, that if I take a nice ball in which I have high density and I iterate it forward, I no longer have a nice ball. I have an ellipse. Well, if I iterate it a lot, I'm going to get, well, you saw what happened to the cat, right? I'm going to get something that's elliptical, but alarmingly thin and not small at all. So even though f is a diffeomorphism, and indeed, what would be the formula for the density, the change in density for f sub a? We could do the same calculation, maybe I'm going to remind you what it is. So here the density of a set of f to the m of some set x and f to the m of another set y. F is a diffeomorphism, so it's injective, so I don't have to worry about a lot of things. Well, in this case, this is going to be equal to the integral over x intersect y, not of f prime, because after all, this is a f prime as a matrix, but it's the absolute value of the determinant of the derivative. It's this. It's this. And by fortunate accident, because, again, we have a linear map, it is the case. Well, this is just the determinant of a to the m over the determinant of a to the m times the density of x and y. So the density of x and y is preserved, because these are the same. This is one, right? In fact, even if this wasn't one, as long as f were injective on that little ball, these would cancel. So we do indeed have that density is preserved. But the problem is, balls are not preserved. And so while we know that the density of this invariant set does not change in its image, its image is useless, the image of the ball is useless from the perspective of the Lebesgue density theorem. We can't get this density point to a density point for the complement while keeping it a density point. So density points are a priori if, for example, if we tried to employ the strategy for transitive maps or transitive isometries, which recall, that means I want to take a density point for my invariant set x to a density point for the complement of x, which we called x prime. Well, we can do that. So I mean, I haven't proved that this is transitive. But the transitivity part works. So we can do that. We can take x close to x prime if we wanted. F sub a is transitive, and that's much easier to prove than ergodicity, which I hope to impress on you. I hope we're, well, it's impossible to impress on you how much easier for an area preserving map, it's much easier to establish transitivity than ergodicity. So we could get x close to x prime, but the point is the picture looks like this. Huge amounts, huge amounts of x, huge amounts of x prime. But if we apply f to the m, this will still be huge in the image. But maybe the image looks like an incredibly flat ellipse. And so here's f to the m of x. And indeed, the green has huge density in this highly elongated ellipse. But that's completely useless. It could just occupy it. So skinny, it could occupy that 1% of this ball that is not x prime. So this argument fails. And the reason is it fails because, well, f does not preserve the shape of balls. It doesn't even roughly preserve the shape of balls. All right, so we need a new idea. And the new idea is very closely related to Corina's lectures. There's another dynamical system that's lurking here, a type of dynamical system that's lurking in the map 2111. And we need to use that other dynamical system to help us prove that invariance, that must be trivial. So he new idea. f sub a has what are called stable and unstable filiations. So recall my little, well, you don't have to recall. Just look over here, that little infinitesimal picture where the derivative of f everywhere just acts like a. That's a microscopic or an infinitesimal, not even microscopic, but an infinitesimal picture. But in fact, since that picture holds everywhere, we have a global picture. So suppose for starters, I take this line. Is that a square? Remotely a square. So suppose we take this line of slope. I believe it's 1 over the golden mean. So we take the line in our do. And we do as Karina did. And we project that line onto the torus. And we want to stay parallel, which is hard to do when you're close to the board. And so what you've seen is that, not so parallel, is that in fact, because this slope, if we call this theta, then I think using Karina's notation, tangent theta, which is less than 1 in this case, is irrational. Consequently, this line, you can go backwards with it, too, this line winds densely through the torus. OK? Now any point, I can do the same for any other point. So here I've associated this line that's immersed in the torus. It never intersects itself, but it's dense. So I'm going to call wu of the origin. That's because this is 0. But through any other point, I can do the same. I can just translate the origin wherever I want to any other point. So maybe I start here. I wish I had two different shades of green. For the colorblind in this room, I guess that wouldn't be so useful. Actually, I guess that would be better than using red. OK, so here's the lighter shade of green. But I could do the same. I can take this line. So if this is the point just x, I can project this line to the torus. And I get a line that's distinct from the other line. And it, too, winds densely through the torus. And I'm going to call this wu of x. And as a set, it's just wu of 0 plus x, like literally the set sum inside of, well, you could either do it upstairs in projector. You can project and do it downstairs because addition commutes with projection. Torus is a group. And so this collection of lines partitions the torus. I'm going to give it a name. I'll call it wu. It partitions. It's a partition of the torus, a hideous one in some sense. But locally, it doesn't look so bad. And so it's a partition. So the union wu of x, just trivially, is t2. In fact, it generates a nice equivalence relation. Two points are as any partition does. It partitions the torus. It's invariant. So you can check these properties in the sense that if I take any x in t2. So by the way, I mean, if I took an x prime, I should say this. If I take an x prime in wu of x, then wu of x prime is equal to wu of x. So it's not like, oh, I take an x prime. And this is part of being a partition. If I take an x prime, it's not like I get some different line. OK, it's invariant. So for any x in t2, we have the following properties. If I take f of wu of x, I get wu of f of x. The leaves of wu, by which I mean, so the leaf through x, I denote by wu of x. So that's called a leaf. It's an element of the partition. Our uniformly, well, they're uniformly expanded by f. But more importantly, in fact, they're uniformly contracted by f inverse. So here's a weak, something stronger is true. There's actually an exponential rate of contraction. But we'll talk about this later. If I have two points, let's just call it y, OK, and they lie in the same leaf, it's called an unstable leaf, that implies that the distance between fA to the minus n of x and fA to the minus m of y goes to 0 uniformly. I'm sorry, x prime, it's also true for y, but goes to 0 uniformly as m goes to infinity. Locally, if I forget what the leaves belong to, this might belong to the same leaf as this. But if I just draw like a little local box here, I can't really tell whether two of these leaves belong to each other. So locally, these are intersections. These are connected components over two. These are the connected components of wu intersects some kind of box of the leaves of wu. These are called plaques and denoted wu, if I have a point. This plaque is denoted by wu, loc of x. Locally, there's a smooth change of coordinates. There's a change of coordinates. In this case, it's affine, so that the plaques actually just look like little line segments. They look like coordinate disks, in this case. This property, plus this, funny I put this first and last, those two properties together are basically the definition of affoliation. Affoliation is a partition of a manifold into smooth submanifolds, like a torus, into lines. So that locally, the elements of the partition look like literally by some change of coordinates look like just horizontal, like a stack of pancakes. OK, so great. So we have affoliation. Its leaves are invariant, or the affoliation is preserved, and the leaves are contracted under f inverse. Similarly, and it also happens to have irrational slope, but actually, that's not super needed, for what I'm going to say. So also, there exists affoliation. So there exists something called WS, called the stable affoliation. It's orthogonal in this case to the unstable affoliation, it's orthogonal to WU. So this is called the unstable affoliation. And it has the same properties, except that the leaves of WS are uniformly contracted, but not under f inverse, but under f. These are parallel to the stable eigen direction. And now Hanan, the next lecture, is going to explain, or maybe not next, but the follow up to this lecture, is going to explain how we can use these two foliations to prove ergodicity. I just want to make a quick little observation that we can prove something even. It's almost an exercise, and maybe it should be an exercise. Ergodicity says that you have no invariant integrable functions, no invariant L1 functions. My observation is that once we have these two foliations, it's now easy to prove. So when I said f invariant, yeah, fA, good, this is fA, to show that there does not exist an fA invariant continuous function. And mostly, I'll just leave you to think about this. But briefly, the reason is, suppose I had a function that was invariant and continuous. Well, let's take a point and look at it I didn't draw the stable foliation, but here's the leaves of the stable foliation look like they're lines that wind densely. Take another point on the stable foliation and look at the two values of f, or phi, sorry, my continuous function. Well, if phi is invariant, then when I apply f, the values don't change. But I can get the values as close as I want by applying f. So for every epsilon, the value of phi at a point here, I keep saying phi, I mean phi, the value of phi here and the value of phi here actually are the same if I have a continuous function that's invariant. So phi is constant on this. Now if I want, I could just use the fact that this is dense. And I could say, well, I have a function, it's constant, and the dense set, it's constant. Maybe I don't know it's dense, but I could do the same argument going backwards now to show that c has to be constant along this leaf. And so now if I look at one of these little boxes, what I call these foliation boxes, I have a function that's constant along stable plaques and is constant along unstable plaques, which if I just look at the picture in R2, I have a continuous function that's constant along these lines and constant along these lines. It's constant. So that's a warm-up kind of idea how you can use these two invariant foliations to prove ergodicity of this map. And this modulo, a lot of technical details, is how you can prove, remember the example I gave with epsilon, sine, blah, blah, blah, that you can prove ergodicity for that map as well. OK. I'm gone over, so I think we should end.


Any patch of land for which Japan has sacrificed a fleet of warships and thousands of fighting men still bristles with United States bombers. For the forces that control Guadalcanal command the approaches to Australia, hold mastery of the skies over the vitally important Solomon Islands. Today these land-based bombers are leading the way as the combined United States land, sea and air offensive begins the task of sweeping the Japs from the South Pacific. All limits comes all the way from Hawaii to decorate Major General van de Gryff whose fighting marines captured the airfield from the Japs and held it against all odds. Donners are awarded officers and men alike. Majors, captains, privates, they've proven themselves in the test by fire. One youngster has 10 Jap bombers and 19 fighter planes to his credit. One of the outstanding records of the war. Men who bore the brunt of the battle. Now with reinforcements newly arrived they're ready to push on. Marching single file, long columns of fighting men stream across the island in pursuit of the enemy. Once the little men of Nipon were in complete control here. Now they're on the run. Lunging into malaria infested jungles, the marines steadily, doggedly enlarge their hold on the island. In advance base they enjoy their first rest in weeks. They have the advantage of an uninterrupted supply line and they get nothing but the best. Make no chances on being surprised by roving Jap patrols. Any line may be the front line on Guadalcanal and they dig in as they advance. Machine guns always on the ready. Artillerymen back up the infantry blasting the Japs from the island. The United States cruiser Boise given up for lost makes port with the most amazing record of the war. The score, painted on the bridge, six Jap warships sunk in 27 minutes. Admiral King, commander of the fleet, comes aboard to salute and decorate her gallant crew. Against overwhelming odds the Boise skipper Captain Mike Moran brought his ship through.  Boise President Carlos Oroio de Río is welcome to Washington. Secretary of State Hall is first to greet the good neighbor from South America who comes to strengthen the ties of friendship. President Roosevelt personally introduces members of the United States Cabinet to the Ecuadorian Chief Executive. President Oroio backs up his sympathy for the United Nations with the important coastal and island bases in the Pacific. Bases that guard the western approaches to the Panama Canal. United States troops occupying Casablanca, salute General Nogus, Governor of French Morocco as he comes to meet the American commander General Patton. At the Miramar Hotel, headquarters of the Western Task Force, General Patton and French military leaders agree upon terms of United States occupation. Leave the hotel in complete accord.  Now, beneath the bayonets of United States infantrymen, they take their exercise. Barrage balloons protect the French colonial harbor of Algiers against low-level air attack. But 16 hours after the Americans landed, authorities agreed to the city's surrender. In the Hotel Saint-Georges, negotiations were completed. French Morocco and Algiers are in allied hands. General Nogus now allied with the United Nations. British Admiral Cunningham, United States General Clark, general Eisenhower in supreme command. Million members of the Axis Armistice Commission, who met the same fate as the Germans at Casablanca, leave the Hotel Angleterre, carefully guarded by American soldiers. From the good people of Algiers pours a steady stream of troops ready for the big push east. Fighting men of Britain's First Army, veterans of Dunkirk, eager for a return engagement with the Nazis. On to join forces with Montgomery, their goal, to rout every Nazi from the soil of Africa. The French harbor of Toulon became the center of worldwide speculation. For here was the home port of the main French fleet. What would they do? 75 mighty vessels, their guns silenced for two and a half years. In them might rest the balance of allied naval tower in the Mediterranean.  And from the flagship of French Admiral Jean de la Borde flashed the order, scuttle the fleet. Nearly the entire fleet was put out of commission.  Four submarines braved the mine-filled harbor and escaped. In one dramatic stroke, Patriot crews struck out to avenge the honor of France.


Hi, I'm Q. Lee of Seoul National University in Korea. In this video, I will present Megahertz 2K, a new multi-party computation protocol from homomorphic encryption over rings at 2K. This is a joint work with my advisor Jung E Chan and Dr. Dong Woo Kim of Western Digital. Our MPC protocol belongs to so-called speeds family, which follows the approach of speeds protocol presented at crypto 2012. All these protocols aim a general MPC protocol which is secure against actively corrupted majority. By active security, we mean that adversaries may freely deviate from the described protocol opposed to honest but curious model. By dishonest majority, we mean that all parties except one may be corrupted. Among various settings of MPC, it is one of the most important settings. Modeling the security thread as honest but curious adversaries is often unsatisfactory in real-life applications. And in the case of secure two-party computation, corrupted majority is the only meaningful goal. However, it was notoriously difficult to handle actively corrupted majority efficiently. Before speeds, those are first observed that one can push the use of heavy public machinery into a pre-processing phase without knowing input values and functions to compute. Meanwhile, in an online phase, one can securely compute a function using only lightweight primitives. This paradigm, so-called pre-processing model, spotlighted the possibility of designing an efficient MPC protocol even in the actively secure dishonest majority setting. In more details, the goal of pre-processing phase is the generation of so-called Bieber's triple or simply triple generation. That is, parties jointly and securely generate random additive secret shares of A, B, and C, satisfying A times B equals C. Then in online phase, parties can perform secure computation using the famous Bieber's trick, where Bieber's triple is consumed at each multiplication gates. However, this is not sufficient for our malicious setting, since adversaries might deviate from described protocols in online phase. So in speeds like protocols, MAC is used to authenticate the computations. In particular, we use an information theoretically secure MAC simply multiplying a global MAC key alpha to input, which satisfies linearity. Accordingly, the goal of pre-processing phase is changed to authenticated triple generation. Namely, parties additionally generate random additive shares of alpha A, alpha B, and alpha C using obfuscated MAC key. We remark that no one knows the value of alpha since it is generated in a distributed way. The online phase essentially stays the same by the linearity of our MAC. After speeds, there were active and steady developments in this area. Except for the dosage, all these works share the same online phase. The distinctive features are in the designs of pre-processing phase. These works can be classified by main technical tools they are using, namely, somewhat homomorphic encryption, linear homomorphic encryption, and oblivious transfer. There were some back and forth, but overdrive with top-key optimization on it is now considered to be the state-of-the-art, which leveraged hyperalism of lattice-based homomorphic encryption. Meanwhile, all the works I have mentioned are NPC protocols over finite fields. The main reason that they were not extended to more general wings, such as that 2k, is that the security of MAC we are using is somehow related to invertibility. That is, it is hard to translate the online phase of speeds to the ring Z2k where non-invertible elements are, majority. Surprisingly, speeds2k, presented in crypto 2018, extended the MAC to also work over Z2k kays, and initiated the research on speeds like protocol over Z2k. According to the authors, this is not only theoretically interesting, but also have implications in practice. Note that integer arithmetic in modern CPUs are done modulo 2 to the k, say 2 to the 64. If we use npc over zp, we first need to compile our code into zp arithmetic, and zp arithmetic in npc online phase needs to be again emulated by z2k arithmetic for executions. These cause double overheads for emulations. On the other hand, if we use npc over z2k, we can naturally compile without overheads. Meanwhile, there are also limitations that this approach requires a less efficient MAC, namely speeds2k MAC. However, a file of work reported that in serious applications such as decision tree and support vector machine, npc over z2k shows up to 5 times improvement in online phase compared to npc over finite fields. However, a disclaimer here is that this does not mean an absolute advantage, since for the pre-processing phase, there are still a substantial gap between zp and z2k ks. Actually, the goal of our work is to reduce such gap. However, as you can see, speeds2k is an OT-based protocol. The authors left an open problem to construct an HE-based npc protocol over z2k, since the HE-based approach showed the best performance in zp ks. The complication here is that achieving hyperalism in lattice-based HE is very non-trivial in z2k ks, opposed to zp ks. There are two follow-up works aiming to improve the pre-processing phase of speeds2k, namely overdrive2k and manza. Especially, overdrive2k partially solved the open problem of speeds2k by proposing a new packing method for z2k messages. Interestingly, the authors of overdrive2k left another open problem to bring the top gear optimization into z2k framework, as they could not employ top gear, the state-of-the-art technique of zp. And this is where our work belongs. We follow the shg-based approach to construct an npc protocol over z2k, secure against actively corrupted majority. We solved the open problem of speeds2k by designing an efficient packing method for z2k messages, and also the open problem of overdrive2k by proving mathematical limits to allow top gear optimization also in z2k ks. As overdrive2k is the most comparative work, we will continuously compare our work with overdrive2k. In this slide, I will briefly review the shg-based authenticated triple generation. We call that the goal is to securely generate shares of a, b, and c, satisfying a times b equals c. In addition to that, we have to generate shares of alpha a, alpha b, and alpha c, where alpha is a global MAC key. The protocol starts by each party choosing random values a, i, and b, i. Conversely, the shared values a and b are defined by these additive shares. Then, each party encrypts these shares and broadcasts them with so-called zkp of plain text knowledge, which guarantees that they have honestly generated the ciphertext. Then, they add the ciphertext to reconstruct a and b in encrypted form. To generate shares of alpha a, they multiply encryption of a with previously generated encryption of MAC key alpha. Then, they perform so-called distributed decryption to share alpha a. We can do similarly for alpha b. To generate shares of c and alpha c, we first homomorphically multiply the ciphertext. Indeed, to generate shares of alpha c, we can again homomorphically multiply encryption of alpha and perform distributed decryption. However, this method is not favorable since this requires SHE scheme of multiplicative depth 2, as we are homomorphically multiplying 2 times consecutively. This increases parameters of SHE and affects the efficiency. So, the standard method here is so-called reshare protocol. Roughly speaking, the reshare protocol securely re-encrypts a level 0HE ciphertext, which does not allow any more multiplications into a fresh ciphertext. The reshare protocol allows SHE scheme with multiplicative depth 1 to be sufficient for our case.  We remarked that the messages are actually vectors by parallelism offered by packing methods of lattice-based HE schemes. So, to sum up, the main building blocks of authenticated triple generation and their rules are first, a packing method enhances amortized performance. Second, reshare protocol allows us to keep down the SHG parameters. And third, ZKPOPK, which is the heaviest part, guarantees that the parties honestly generated the ciphertext. As the title of our paper suggests, our protocol megahertz 2K is a combination of improvements in all these three building blocks. Finally, we are ready to get into our technical contributions. In this section, we are interested in HE packing methods. By packing, we mean methods for embedding several copies of messages into a single plain text while providing a certain degree of homomorphism. In our work, we consider packing for copies of ring of integers modulo sum t. Packing enhances amortized performance by allowing SIMD-like optimizations. And it is essential for practical use of HE, as this complicated plain text space defined by lattice-based HE schemes is usually not the space we want to compute in. Packing plays an important role in speeds like HE-based NPC protocols, since the efficiency of packing methods, which is measured by how densely the messages are packed into a plain text, directly affects the throughput of triple generations. First, I will review the conventional packing method for prime field messages. The idea is to choose parameters so that the cyclotomy polynomial fully splits modulo p. Then we can apply CRT ring isomorphisms to pack several zp messages into a plain text in zpx quotiented by a cyclotomy polynomial. Note that since this packing method is defined by an isomorphism, it offers fully homomorphic correspondence between messages and plain text, and packing structure is maintained after the homomorphic operations. Also, it offers the perfect packing density. However, we cannot use the conventional packing method for z2k messages, since cyclotomy polynomial never fully splits modulo 2 to the k. Meanwhile, it is known that it vectorizes into polynomials of same degree d. In this case, one way to pack z2k messages is to again leverage CRT isomorphism, but use only constant coefficients and put 0 in the other coefficients. In this way, we can still enjoy fully homomorphic correspondence and level consistency. This method was often used by Helip and Helip-based applications. However, using this method, the packing density goes too low, namely 1 over d. As we can use only d over 10 due to security reasons, using this method in our case causes over 10 times overhead for npc over z2k messages, compared to prime-field ks. Overdrive2k aims to improve the packing density of Helip-packing by an observation that a somatomorphic correspondence up to one multiplication is enough for npc preprocessing. The idea is to use coefficients as much as possible, but avoiding interference. For example, if we pack messages into coefficients of degree 0, 1, 3, 4, and 9 and multiply, as it is carefully designed, coefficients of 0, 2, 6, 8, and 18 encode the product of messages. By this mean, overdrive2k achieve somatomorphic correspondence up to one multiplication. Also note that this packing method is level-dependent, meaning that the packing structure changes after multiplication. The authors claim that the packing density of their method has asymptotically 1 over d to 0.4, and is roughly 1 over 5 for practical parameters. The starting point of our packing method is the idea of what if we use evaluation points rather than coefficients as previous packings. That is, what if we use interpolation to pack messages? If we interpolate the messages into a polynomial of degree roughly half of d, then we can easily avoid degree over flow when multiplied, and prevent information loss by reduction by the quotient polynomials. The best part is that this packing method offers packing density of more than a half. This sounds perfect, reducing the gap of packing density between the field and the z2k case, only to the factor of 2. However, the caveat here is that interpolation over z2k is impossible in general. To see this, consider evaluation at 0 and 2. These two values must have the same parity. Thus, we do not have full freedom to choose target points. However, our story does not end here. We devised a method to perform something very similar to interpolation over z2k. We call this method a tweaked interpolation. The main idea is to lift the target points through a larger ring to cancel out effects of zero divisors. Precisely, when n z2k messages are given, we can find a not-so-large delta so that there exists a polynomial over this lifted ring, whose degree is less than n, and its evaluation at i equals i's message multiplied by 2 to the delta for all i. Coming back to packing methods, we can now realize our packing design with the help of tweaked interpolation. Just one thing to be careful is that since we lifted the target points by a factor of 2 to the delta and multiplied, the lifting factor grows to 2 to the 2 delta. In this regard, we must use plain text modulus with an extra delta to avoid modulus overflow and prevent information loss. Then, our tweaked interpolation packing offers somatomorphic correspondence up to one multiplication. Note that our packing method is also level dependent. In fact, we can choose the delta to be roughly the half of d. Thus, packing density of our tweaked interpolation packing is roughly a half when d is sufficiently smaller than k. And this is the case for typical parameters of actively secure NPC over z2k. Moreover, in a recent paper by me and Professor Chan, we proved that this is somehow near optimal. The graphs show the plots of packing densities along the change of the degree d. The red is for overdrive 2k packing and blue is for our tweaked interpolation packing. Three blue lines each denote densities for three typical size of k used in actively secure NPC over z2k, as our density is affected by the size of the ring z2k. The left graph shows an asymptotic behavior of density, and the right graph shows an exact densities in practical set of d. Notice that the gap is visible even in the closest case. Our tweaked interpolation packing shows up to 2.5 times improvements in packing density versus overdrive 2k packing. That is, using tweaked interpolation packing in NPC preprocessing, we could improve the amortized performance by a factor of 2.5. A limitation of packing for z2k is that they are level dependent. By level dependent, we mean that we get different packing structure after multiplications, so that we have different packing structure for each multiplicative level. A recent paper by me and Professor Chan proves that this situation is inevitable. The circumstance is in contrast with conventional packings for prime fields, which are naturally level consistent by CRT isomorphisms. The issue here is that if a packing method is level dependent, then we cannot perform homomorphic computation between different packing levels. But why does this even matter? To see this, I will briefly review the process of the reshare protocol. Roughly speaking, it is used to re-increase a level 0HE ciphertext, which does not allow any more multiplications into a fresh ciphertext. Oversimplifying a bit, it proceeds like the diagram. First, we add a random ciphertext R to mask the input ciphertext C. Then we perform collaborative decryption, followed by encryption. Finally, we subtract the masking ciphertext R to reconstruct the original plaintext C. Notice that the masking ciphertext R is used twice at different levels. Once to mask the input ciphertext C at level 0, and once to reconstruct the plaintext at level 1. Whereas the ciphertext levels can be easily adjusted by modulus switching technique in HE, but difference of packing levels seems problematic. In this context, overdrive2k provides two masking ciphertext with same message but in different packing levels. This solution, however, almost doubles the cost of reshare protocol. On the other hand, we resolve this issue by a technical trick. The main observation is that we use the reshare protocol only to support an additional multiplication with MAC key alpha, which is indeed a constant in z2k. Thus, in fact, we do not even need to care about packing levels if we use a different packing structure for MAC key, namely if we use constant packing method. Our trick closes gap between the prime field and z2k cases caused by level consistency of the packings and offers 1.4 times reduction in communication cost compared to the solution of overdrive2k. In this section, we are interested in z2kpo plaintext knowledge, which is abbreviated as z2kpopk. It guarantees that a ciphertext is honestly generated from a plaintext without revealing any information on the plaintext. z2kpopk plays an important role in speeds like protocols since it restricts adversaries from submitting maliciously generated ciphertext to learn information of other parties. z2kpopk is a standard genotype protocol. Suppose the prover Alice wants to prove that she has honestly generated a ciphertext, which encrypts a plaintext x with randomness r. First, she commits a random masking ciphertext. Then the verifier Bob chooses a random challenge c, which is either 0 or 1. After receiving the challenge, Alice responds with corresponding linear combination of plaintext and randomness. Finally, Bob checks certain criteria to judge whether really Alice has honestly generated the ciphertext. However, using such a small challenge space consisting of only 0 and 1, we must iterate this process numerous times to achieve satisfactory level of security. The Top Gear protocol aims to enhance the efficiency of z2kpopk by enlarging the challenge space. The main idea is to leverage the structure of HE plaintext base, namely z2x quotiented by a power of 2 cyclotomic polynomial. In this way, they extended the challenge space to 0 and powers of x. This approach is favorable in communication cost and latency. And Top Gear optimization also affects memory consumption in batched version of z2kpopk, which is a standard in speed slide protocols. Behind the scene of Top Gear, there are two mathematical elements which enable such large challenge space. First fact is that multiplying a power of x does not increase the size of questions too much. Second is that a difference of powers of x always has a small pseudo inverse in plaintext space. The second fact was first observed by Benhamu Daedal and is being widely employed. These two facts are the essence of security proofs of z2kpopk, including soundness. However, these lemmas were only known for the power of 2k's. Meanwhile, power of 2 cyclotomic polynomials are irreducible modulo 2 to the k. This means that we cannot leverage CRT parallelism for z2k messages in this case. In this context, overdrive 2k could not employ the Top Gear optimization. In this work, we extended the lemmas to the prime case, and in the follow-up work, we extended even further to the case where M has two or less prime factors. With these new generalizations, we propose Top Gear 2k, which allows us to use larger challenge space for z2k messages as in Top Gear for prime field messages. Indeed, our z2kpopk enjoys same advantages as the original Top Gear protocol. Another limitation of packings for z2k is that they are non-surjective. By non-surjective, we mean that there exist invalid packings in plaintext space. The recent work proves that this situation is also inevitable. The circumstance is in contrast with the conventional packings for prime fields, which are naturally surjective by CRT isomorphisms. The issue here is that malicious adversaries may use these invalid packings to illegitimate the learned information of other parties, so it is necessary to somehow handle these invalid packings. In this work, we conceptualized zero-knowledge proof of message knowledge abbreviated as z2kpomk, which guarantees that a ciphertext encrypts a valid packing without revealing any other information on message. This concept was somehow neglected in overdrive2k, since z2kpomk can be easily integrated into z2kpopk if one only used a small challenge space consisting of zero and one. In this work, we designed an efficient z2kpomk for our tweaked interpolation packing, which goes well with our extended challenge space. Combining all the previous improvements, we can combine them into a better authenticated triple generation. Our new tweaked interpolation packing offers a better amortized performance. Our simpler reshare protocol offers reduction in communication costs and latency, and our better z2kpopk with our new z2kpomk offers reduction in communication costs, latency, and memory consumption. As a whole, megahertz2k, an MPC protocol over z2k, secure against actively corrupted majority, offers from 2.2 to 4.8 times improvements in amortized communication costs versus previous best schemes, and offers 3.7 to 6.4 times improvements in memory consumption versus overdrive2k. But what we really want to share here is our new techniques and concepts which enabled the these improvements, namely tweaked interpolation and tweaked interpolation packing, level dependency and surjective tip for packings, constant packing trick for simpler reshare, generalization of dilemma by behamu.all, and our new notion of z2kpomk. Thank you for watching. Any questions or comments are welcomed by any means.


There will always be a need for world-class scholarship and outstanding research, but in today's business environment, people expect more from universities. Here at the Graduate School of Management, we understand that the boundaries that have traditionally existed in organizations have become arbitrary. We have broken down barriers within the university structure to assemble a team of industry experts and academics who collaborate around the big picture. We select our staff based on a dual skillset. Not only do we want great researchers, we also want great teachers who work alongside industry and across disciplines. We work with people at all levels of the organization, from young professionals to middle managers to top executives at the board table. When our students leave the classroom, they take with them tools, skills and techniques that they can put to use the very next day. One of the things we find so satisfying at the GSM is seeing our graduates develop and succeed within their industries. They return to us as collaborative leaders who understand the value that we can add to their organizations. Our programs bring together a wide range of professionals, from large corporates to not-for-profits to small and medium enterprises and some who work for themselves. This approach fosters peer-to-peer learning and creates completely new networks. We are proud to be a part of the University of Auckland, which has a distinguished history and is New Zealand's top ranked. But we also pride ourselves on working in a unique and nimble way to remain relevant and meet the ever-changing needs of business.