What's up guys, Mike the coder here today. This is the first time I've started doing a face cam video I don't know I made a poll and says you guys want to do a face cam So this is the first time I'm gonna do a face cam today. We're gonna do a digit queries So essentially is that you're given an infinite string that consists of all positive integers in increasing order 1 2 3 4 5 6 7 8 9 and then 10 11 12 13 14 15 16 17 18 19 20 and 22 20 24 25 Okay, well, it's like I get my mouse in the in this you see one then there's two and there's three and there's four And there's five and there's six seven eight nine ten and it repeats. So it goes 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25, so it continues repeating. So our task is that basically we need to query digits at this form So what is the digit at the kth position in the string? So if I give you I don't know the first Physician it will return one, right? And if I give you the ninth position, it'll return nine, right? And if I give you the the tenth it should give one 11 it should give zero 12 should give one and so on and so forth Essentially is that's what we have to do and the input of the statement is that we basically read in the q which is the The number of queries and then we read in each integer k Which is starting index one of each of the string So that's basically the gist of the problem and now we have to figure out how to solve this problem So let's go right in so the most naive way you could do this is actually just to Repeatedly build your string. So we start one two three four five six seven eight nine ten And we just do 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 And we just keep going on and so forth 26 27 28 29 30 and we just keep going until we could get up to I don't know 10 to the 18th Which if you could do this But I don't think it will you'll probably overflow because There's only a certain amount of digits you could store in a string or an integer So if you just keep I mean you technically you could just keep doing this and so on and so forth and then Hopefully until you get 10 to the 18th and then just pick pick position k and then just read Read in whichever position at the k position But this takes a lot of time and it's not a good way to do this So how do you do this? What you do is you have to build a mathematical equation representing each of the corresponding digits With it's the pattern that you see so the first thing that you can notice is that if the current value of your Digit of your k is less than 10 Right if it's less than 10 You could just return the digit right because if you have like one two three four five six seven eight nine Right, any of the values here Are just going to be itself Right because like if the first position is the first position second position It'll just be the second position So on and so forth it only happens when we reach the 10th position Which case we have to start doing stuff afterwards So if your k is less than uh 10, we could just just return k That's all you have to do just print out k and return it and it only gets harder when we Go past this the first thing you need to know is that let's say that we're forgiven the our value of k We need to know what is our length of the number that we're on that we're repeating right if if I give you the k So let's say that I give you the thousandth position What is the length of the number that is actually repeating if it's if it's a thousand and then it's actually I don't know 300 that's repeating over and over three or one three or two three or three or four That actually matters the reason why is because if we look at this We look at one two three four five six seven eight nine right and then we look at 10 11 12 13 14 15 16 7 18 9 20 once we've reached 100 100 the positions that we are at if we just write a single math equation Dictating hey, what is the thousandth position right what happens is that once we reach longer length of our Current number that we're repeating on repeating two digit numbers of 10 So and so forth 11 12 13 15 16 and then three digit numbers 100 101 102 103 104 is that these because the length is changing of the number that we're incrementing and repeating That is going to affect what our current positions are that's going to affect the current positions and the math equation that That we need what we need to know is that hey if i'm giving you the current position k What is the number what is the length of the number that we're repeating on because if we know that then it's much easier to You know dictate these are the numbers that are going to repeat So on and so forth and then we could figure out our equation from there Because it's changing every time the length of the number that is repeating every time the length of the number is repeating Gages from 10 to 100 and now it's because it's three digits now You know length of three digits that we're repeating 101 102 101 102 103 104 and then once it gets like four digits like a thousand that changes again What we need to know is given our position k What is the length of the number that's repeating and then that will help us find our answer? So we actually can calculate this it's actually not that difficult So we know that if our position or our kth position is less than 10, we just return k, right? It's one two three five six again at night now now we reach two digit numbers So it's repeating 10 11 12 13 14 15 16 17 18 19 20 So what is the last value that are two digit numbers? It's simple 99, right? So The next two digit numbers go from 10 to 99 So now we just need to know what is the last position if we're repeating this many number of times Well, this is not actually difficult to do okay. We can actually calculate this So what is the last position of the number of 99? What do you do is you take 99 minus 10? We minus 10 And we plus one So that's going to give us 90 and this is going to be 90 numbers There are 90 numbers between 10 to 99 to 10 to 99 So there's 90 numbers and these are 90 numbers that are two two digits Okay, these are 90 numbers that are two digits. So these 90 numbers have two digits So we're going to actually take 90 and we're going to multiply it by two And it's going to give us 180. What is 180? This is going to represent similar to the last position that we are going to repeat for two digit numbers Okay, so if we're giving the k position Um, there, there's going to be The position 10 is going to start from one and then 99 is going to end at um position 180 Really would be 180 Now the problem is that this is assuming that this 10 That we started from actually started from index zero, but since we are starting from Nine, we actually have to take 180 and we plus the first nine values that we're starting from So it's going to be 180 plus nine So our range or for two digit numbers For the position would start from 10, right? So it would be this this position would be the 10th position, right? All right, this is going to be the 10th position. So there's a 10 Then 11 12 so so on and so forth and then it's going to go up to 180 Nine this is going to represent the the range of the positions that's going to be yet So we know it's like two digit numbers and so on and so forth. So if our k is like on a 170 So if there are k's at position 170, we know that there's two digit numbers here So let's say our k is equal to 170 now So I want you to find me the number at the position 170 So because we already calculate the ranges the two digit numbers We know that for the ranges of the two digit numbers of their positions We know because 170 lies between 10 and 189 We know this number whichever number this is this number Is going to be a two digit number because we calculated this range that for all the two digit numbers This is like the range of their positions. So we know the number is going to be between 10 So this is our number our number value of n Let's say let's call our number n. We know n is going to be between 10 and 99 Just from knowing this value of our current position k and knowing it's in this range Between 10 and 189. All right, so now let's actually look at the positions of our current number and see how they got their positions So let's say look at our number 13 this number 13 So what is the position of the starting value of 13? So where does this one start? Well, let's count. So we know that nine it ends at nine, right? So this first value is 10, right? So it's 10 11 12 13 14 15 16 Okay, so the starting value of 13 is at position 16. So this starting value 13 is at position The position of 13 is 16 So how do they get 16 at position 16? Well, if you think about it 13 minus the starting value of 10 13 minus 10 Is equal to three right Equal to three and because there's every two digits They're skipping every two digits, right? So because there's every two digits here Every two digits here, right? So 10 11 12. These are every two digits three times two Is equal to six Right, so three times two is equal to six and If we take this value six We add it to the starting value of 10 So we have this starting value of 10 10 plus six Is equal to 16. So that's how they got that's basically how they got This value of this 13 to be at 16 at position 16, right? They took the number Here that they're at subtracted from the starting position Multiply it by the number of digits in this case It's two and then add it to the starting digits starting position So they got the number 16 At the position of one at 16 So What we could do is that because we have this uh lower bound of 10 and we have this upper bound of 99 In our number and we have this value of k This position we could what we could do is we could use binary search Okay, so 10 and we know our numbers between 10 99 So what we could do is we could just guess like the middle. So we take 99 minus 10 Right, and then we get the middle right so we get our our midpoint And then what we do is what we're going to do is we're going to take this midpoint and subtract it From 10 Okay, so we take this midpoint and we subtract it by 10. So we're going to take this mid And subtract it by 10 Right, and then what we're going to do is we're going to multiply it by the number of digits So because we know this We because because we know that our number has two digits, right? Because of this range between 10 and 189 we take mid minus 10 multiply it by two And then we're going to get a another number. This is going to be our position, right? We just have to check this position with k And if it's greater, um, we move our Our left bound to the top and if it's less then we're just going to move the right the right range of 99 down Because of this we will we will be able to get Our solution of our answer by using binary search on the digits So, yeah, all right guys. So before I go over the code, let's just go back to what we had before So remember 10 to 999. These are the two digits Right the numbers of two digit numbers. Remember, we said 99 minus 10 plus one would give us 90 And remember we said for three digit numbers, we have 100 to 9 and 199 And then we said 999 minus 100 plus one would give us 900, right? As you can see here, you don't actually have to calculate 99 minus 10 plus one Um to get 90 you could just subtract powers of 10. So we do 100 minus 10 would give us 90 So this is just like a faster way to do it when we want to code this up to do that in a faster way That's what I did. I just actually put powers of 10. So I actually calculated powers of 10 So here we have an array of vector of powers of 10 and I have not 19 of them Yeah, I set all them to have one right set them all to have one And what I'm doing is I'm just going to loop through and I'm just going to create powers of 10 So I'm going to take the previous number and multiply by 10 So that's going to create like one 10 and 100, 1000 and 10,000 and 100,000 so on so And this will help us calculate these numbers for the number of the range between the two digits and the position All right, so I read in t which represents the number of test cases And then I do while t minus minus keep decrementing the test cases each time And here's what I do is I read in the number n and this is going to represent our k, right? Um, I should have named it k, but it should be like the index What we're trying to search for I have this variable called num digits, which is what we need to find So remember we have to calculate number of digits find out the number of digits for the number given the index Right. Remember that's what we said. So I'm to have this variable for that I have this variable called digits, which just represents the current digits that we're Adding so far and then I have a previous digit that represents the previous digits that were added And I use that later. So here I'm going to loop through from 1 to 19 Which is representing the reason why it's 19 is because there's 10 to the 18th This is the maximum number you could have for your k and that's also another reason why the power is 19 Starting from index zero we have one and then we go up to Up to 18, which is going to be 10 to the 18, right in our powers Just like what we said before here digits the number of digits is going to equal to what we said before here 100 minus 10, which will give us 90 because every time it's going to give be 90 909,000 so on and so forth. This is an easier way to do it So the powers we're going to subtract the previous powers for our digits And I'm going to multiply by i the reason why is because i represents the number of digits Okay, so Remember we had a one two three five six seventy nine, right? So remember this is that what we had before remember we start first digits is one and it goes to two Right, we're repeating two digits here 10 11 12 13 14 15 16 17 then it goes to three digits. It's four digits five digits Right, so this that's what this i represents right We're multiplying by the number of digits every time that we're looping through and then here Is this number digits is actually the length? I'll rename this like yeah digit length, okay? So this that's what this represents. It's just like the digit length that we're incrementing Then if the digit length is greater than or equal to our index And the number of digits that we have will equal to i Right because that's a number of digits that we're repeating because we're doing one Then two then three then four then five Remember we're trying to find the length that it's repeating and that represents i So our number digit variable is going to equal to i because that's what it represents and this Digit like yeah, if our digit length is greater than or equal to the index I'm going to rename it because it's kind of hard to understand this but yeah, if it's equal to Greater than equal to k then we our number digit is going to equal to i and then we break means that we found the digit length that's repeating then I have this previous digits Which is going to equal to I keep track of the previous Length now we now since we have our number number digits that are repeating We could just create use binary search now. So we have low is going to equal to num digits minus one Power of that. So like let's say it was let's say we're repeating 100. So right right here, okay? So this would represent what it represents is if our number digits is like three Powers of two powers of three minus one would be two power of 10 10 to the two would be equal to 100 high would equal to powers of three three powers through would be thousand minus one which would be 999 So what low and high represents here? It will be representing if it was three digits This is what we're low would be and this is what our high would be if we're repeating every three digits That would be our low and then this would be our high then while low is less than or equal to high Here I have the answer position and I also have starting answer position Because I need the starting position also where low is less than or equal to high We're going to get the midpoint. We're going to calculate the starting position So to do that what we're doing is we're going to take our midpoint Which is the one that we're trying to search for trying to check midpoint is going to subtract by Number digits minus one which is going to represent 100 in this case our range And we're going to multiply by number of digits, which would be three Right, there's three of these and then plus previous digits. So previous digits Were to represent all the previous digits beforehand So all these beforehand, this would be like a previous digit Previous number digits, right previous number digits I'm going to I'm going to name this previous number digits previous number digits Is going to equal to the current digit line previous number digits We equal to all the values beforehand because we need that later on midpoint minus the powers Minus one which will be our range of our upper range. So I take midpoint minus upper range Then you to check if it's right I multiply the number of digits because we needed that's number of times we're repeating three like three And then I plus previous number digits would which will represent Represent the position that we're repeating at and since we're repeating it we're stopping at this last position So I assume assume these guys are like in the same line But when we stop at the last position, yeah, we need to get our position So that's what previous number digit does is that we're adding by all the position of the previous Digits, I'll rename it again previous number position And then we need to add one because it goes to the next position Right that we're searching through. So yeah, this is all be our starting position If it's less than or equal to k the index that we want the position that we want Okay, if it's less than or equal to that, we need to check if mid is greater than our answer Which is going to be and then we set our answer to equal to mid And then our starting position we're going to be able to start position If it's less than or equal to k I said low we're going to increase the range. So this range of 100 is going to change to The midpoint which we buy 100 ish. So this this low of 100 We know it can't be in this range of 100 So we're going to go to 501 to 900 otherwise I take high is going to equal to mid So while this is done while our binary search is done Searching through all the values for from 100 to 999 What we're going to do now is we're just going to convert the answer to two string So we have our final answer of our number that we keep kept checking over and over again Converted to a two string and this will be our number and then if you want the current position. So let's say I want this digit this 13 at the 17th position Right this three. So I want the so let's say k is equal to 17 So since I already know the starting position is 16 All I have to do is choose would be one here This starting position, which would be 16 And I take 17 minus 16, which are going to get me to one And then I just print out the position of one of my number that I found So yeah, I just print that out and I'll be the uh, I'll be the digit number that will be at that position Okay, I hope you guys know this video rate com subscribe. I'm pretty tired. Yeah peace


Thank you. Dr. Coulter Really appreciate that introduction. I I second dr. Hernandez's You know Congratulations on really organizing this. This is the second time I've spoken at this conference and It's not an easy thing to do. I'm sure so again. Thank you In the interest of time. I already cleared this pre cleared this with dr. Coulter I'm going to kind of make some adjustments to my talk. My talk was initially going to be two parts One part was going to be kind of focusing on a rhythm is an in in the female population and what's unique and what?  There's an arrhythmia symposium the Ali Missoumi arrhythmia symposium In the Houstonian so if you want to get more detailed information Especially about arrhythmias and pregnancy. I advise that you guys show up to that But what I will do is focus exactly on the topic that she asked us Dr. Coulter asked us to review which is what is new in atrial fibrillation and the answer obviously is typically a lot, but I'm going to just focus on three studies and these are going to be They're going to be I think clinically relevant studies that Have a has have had a large impact on our clinical practice and I think Their outcomes in some cases Are more nebulous and more subtle than what we expected in the beginning Although some in the EP community especially when it comes to the cabana trial, which I'll get to in a second We're predicting that there's going to be some problems in terms of You know using that data to guide our clinical decision-making. So the first study is crystal AF Crystal AF basically it's it's a study that is Asking the question and patients with cryptogenic stroke Who often? You know receive cardiac monitoring There's usually two ways to go about this one is you can have them wear a monitor an ambulatory monitor You can wear two weeks four weeks even six weeks Ambulatory monitors and the other group was an implantable loop recorder, which is I'll show you here in a second but you know 30% of the ischemic strokes are of an unknown mechanism so-called cryptogenic strokes and one of the most common Cardiac causes is atrial fibrillation the question is often a patient will come in and their first symptom of atrial fibrillation Is having a stroke? Of course at the time that they present we don't know this and this obviously again is going to have significant long term sequelae in terms of Oral anti-coagulation and management of these patients so that there's no recurrence So the question was is it better? What's the best modality to be able to detect the causative rhythm or the atrial fibrillation in one group? You have what we would call implantable loop recorders, which are basically exactly what those words say their tiny loop monitors two of the big companies make them they go subcutaneous and They have battery life that lasts typically up to three years and they're just continuously monitoring. They store if there's an arrhythmia The second group, which is the standard group is these ambulatory monitors and the ambulatory monitors these day arts are pretty easy to to use and the the study's purpose was to then compared the outcomes in terms of a diagnosis so These patients were typically 40 years of age or older cryptogenic stroke They had follow-up at one three six months and using a 12 lead EKG or 20 Four-hour EKG monitoring or Holter. They also receive TEs and of course the CTA and MRA So here's a loop recorder Plantable loop recorder it literally takes 30 seconds to put one in It's You know you make a little injection you inject lidocaine subcutaneously usually on the left fourth intercostal space and This you literally again pop it in subcutaneous and you get beautiful single lead EKG It is titanium. So MRIs are not an issue. There's no issues with you know Magnetic interference or things of that nature and most of my patients after three years They like to just keep it in because it's relatively you know inert You can also now nowadays have these ambulatory monitors and actually the most common ambulatory monitor Used in this study was not what we typically think about a five-lead Holter it was a zeal patch made by a company called iRhythm and It consists of a monitor that you stick on your on the surface of the chest It has a rubber covering so you can take a shower and things of that nature without difficulty There's two weeks of recording and in a newer iteration Actually, it will give you a trigger and not notify the physician if an arrhythmia occurs You don't have to wait and you know analyze it after after two weeks of implant The the patient wears it they drop it off in the mailbox after you know after two weeks We analyze the the recordings and and then we See if they've had an arrhythmia so the follow-up again as I said one six and twelve months and Every six months they're after and they recorded all the different types of symptoms associated with potential arrhythmias and I don't think it's you know, I don't think it's it's a surprise to anyone But I think it's important for us to see you know That implantable loot monitors detect these arrhythmias much more easily much more frequently and in fact The ambulatory monitors are somewhat useless for this purpose So I think the the current strategy is that when someone presents with a cryptogenic stroke It's absolutely critical. This should become these implantable loop recorder should become part of the clinical Streamline management And you can see here that again with controls subjects the percentage of AFib that was detected in these patients over time It goes up to about 10% here and here it's about five percent I'm sorry about 10% In conclusion implantable loop recorders were superior to standard monitoring the detection of atrial fibrillation at six months 12 months 36 months and moving forward AF is detected in Almost 10% and ultimately up to 30% of patients at six at 36 months So about a third of these patients do end up having atrial fibrillation is the cause which should not be a big surprise but to document it so effectively I think is impressive and Obviously, and this is a good piece of news that once AF is Detected it does change the way that these patients are managed as it ought to in terms of oral anticoagulants versus anti platelet agents So this is the big study that I think everyone has talked about this past year the cabana trial Doug Packer I'll tell you just how old and how long it took for this study to be To actually happen. I was Doug Packer's fellow still when he was starting this trial. So that was a while ago and The the study basically had very good intentions It was it was designed to look at the efficacy of atrial fibrillation ablation In patients who who had this who have this disease and it was I think perhaps a little over ambitious At the time atrial fibrillation ablation was still kind of feeling its way gaining its You know, it's a toehold in the clinical arena And so the decision was made to take patients and compare and randomize and to really three groups medical therapy and in not without rhythm control rhythm control with pharmacologic therapy and ablative therapy and Perhaps again overambitiously the primary endpoint was determined to be death disabling stroke serious bleeding or cardiac arrest You know for a disease like atrial fibrillation who that if you give oral anticoagulants and you you know treat the heart rate adequately is is really a symptom-driven problem Looking at the efficacy of ablation in these patients and looking at its effect on death or disabling stroke I think it's something that that's pretty ambitious and the data did support this ultimately after a Medium follow-up of about five years. There was a non significant 14% reduction with ablation as Assessed by intention to treat and this was the big thing if you got randomized to one of those groups It turns out that the chances of you dying or having cardiac arrest or having a major stroke or bleed Was really not that low or whether or not you had ablation And this is where all the controversy started this is with this trial because if you were if you didn't look at the patient on an intention to treat basis in other words as The patients came in over time a decision was made. Okay The medications are not working or we for whatever reason decide that we want to switch into the ablation arm then the numbers Really dramatically shift in favor of ablation and I think that we have to keep in mind that over the course of These five years of this study or overall about ten years of follow-up are really that the adolescent teenage prepubescent phase of Atrial fibrillation ablation and the technique and the technology as it starts maturing and as it starts maturing correspondingly more and more Physicians and patients elect to go with the treatment of ablation as they you know as as its safety increases And so what this study has been dogged by is the fact that there was such a high crossover between the groups and Intention to treat versus the therapy that they ultimately did receive So here's a Just kind of a Overview of those in terms of the incidence of atrial fibrillation This is not this is the intention to treat groups and of course ablation I don't think that there's any debate these days that ablation is more effective in rhythm control than medication be at rate control or anti-arrhythmics for rhythm control, so so that's that's fine and dandy and You can see also that the incidence of atrial fibrillation flutter and tachycardia over time Ablation has a higher percentage of patients who are free from atrial fibrillation This number is somewhat disappointing But I think again we have to remember that a lot of this data comes from the periods where Atrial fibrillation still had its acne and still had looked at its awkward stage and still was not really kind of at a more Presentable phase of its of its process and so the other point I think here is if you eliminate the atrial fibrillation patients here drug and ablation with atrial flutter and tachycardia were similar Yet again something that we know in clinical practice It's somewhat unusual that atrial flutter ablation is over 90 95 percent successful and Multiple studies since the beginning of the study of Cabana have shown randomized trials that as a first-line therapy ablation of typical atrial flutter is far vastly superior to To pharmacologic management and yet here you see that they really did not make a difference so and so Here you can see over time as the incidents of patients who with who do have atrial fibrillation With drug versus ablation and again no surprises the big debate with cabana was the fact that that primary endpoint intention to treat did not Did not was not positive and I think cabana is the ultimate Rorsch test You know if you're an EP who does ablations for a living you can look at it in the frame of what I just described to you If you are someone who believes the numbers If and the numbers don't lie and you have to go and be statistically rigorous. Yes, it was a failure So, you know You you you kind of long as you understand why this study Showed what it did and how that can be and the nuances involved in interpreting it then I think it's less And then the amaze trial is a trial that is just actually was completed and I'm putting a plug for dr. Rasek here who was the third leading second leading Contributor to the study nationwide and the amaze trial is a study that is looking at the use of the lariat Which was also invented by a alumni of THI Dr. Billy Cohn Which is a left atrial appendage occluder and the question was not whether or not this left atrial appendage occluder is Going to cause Decreased stroke, but whether or not it actually helps in the management of persistent permanent atrial fibrillation And and the rationale behind that is that more tissue Increases your susceptibility to a rhythm. Yeah, that's it's as simple as that bigger hearts are more susceptible to arithmias because there's more tissue to have these reentrant Rhythms and smaller tissues aren't so what we call atrial debulking electrical debulking using this lariat technology was studied and You know, I I think from what I've seen it looks promising But we won't know that for probably another 18 months or so. It's technically it's somewhat I think one of the more challenging Procedures you require drive pericardial tap things can happen But you know use a micro puncture needle and things of that nature and you decrease the incidence of of some of those Complications there was a very very very steep learning curve with this procedure But at the end of the day, we're going to find out whether or not Isolating because unlike the watchman, which is a plug in the opening or the mouth of the left atrial appendage The lariat actually mechanically cinches around the neck and you basically Strangulate not only the the left atrial appendage, but the tissue itself and over time it just Infarct and it sloughs off and you lose that tissue and follow up CT scans. It disappears so again, we will we will find out but this the study was 600 participants was just completed about three weeks ago, so we will know very soon and Thank you for this opportunity and hopefully help get things on time


Thanks, Anjum. So this is joint work with Run, Kennedy, and Whipple-Goyle. So since there have already been two talks on MPC and on concurrent security, so I'm just going to skip all the basics of those things and get right into it. So our setting is that of protocol composition. That is, we ask the question, what if a protocol is executed concurrently with many copies of the same protocol or arbitrary other protocols, and what if all these protocols are controlled by a central adversary, this adversary in the middle? And we ask, in this demanding setting, is the protocol security still preserved? That is, just, can we achieve protocol composition? And for simplicity, or actually for the focus of this talk, we are just going to worry about protocol self-composition. That is, we will consider the scenario where unbounded many copies of the same protocol are being executed. And again, they're all being controlled by a same central adversary. We'll just focus on the two-party setting between parties P1 and P2, and the adversary in the middle can run unbounded number of executions of this protocol, playing the role of P1 and P2 interchangeably. And again, we ask the same question, can we achieve security in this demanding setting? While this is weaker than the standard notion of general composition, this is still quite meaningful in many client-server settings. And indeed, there are many examples of this that arise. For our interest, we will be concerned with concurrent multi-party computation. But the same problem, in fact, arises in many weaker scenarios as well. For example, concurrent zero-knowledge, non-malable encryption, or even commitments, and password authenticated key exchange. So this is a very general problem, and the question is, can we achieve concurrent self-composition securely? And unfortunately, the answer is no, there are broad impossibility results that show that there exists a large class of functionalities that cannot be securely realized under concurrent self-composition. As we saw in the previous talk, there are some special cases in which this impossibility result can be bypassed. But if we are concerned with generality that is achieving security for all functions, then this impossibility results hold. So what can we do to circumvent these impossibility results? So two lines of research have emerged. The first one concerns with the use of trusted setup assumptions, that we assume that there is some trusted party who can generate for us, for example, a common random string or unclonable functions, or tamper proof hardware, and so on and so forth. And then these works use these trust assumptions to realize secure protocols. And in fact, not only do they achieve concurrent self-composition, but in fact, they can also achieve UC security, the gold standard. The second line of research, which is what we are interested in, is essentially that of relaxing the security definition. Instead of demanding the standard real ideal security for MPC, we relax the security requirements by usually allowing some additional leeway to the simulator, or requiring indistinguishability instead of simulation, and so on. One of the most common definitions in this line of work is that of super polynomial time simulation, where instead of requiring the simulator to be polynomial time, as the definition suggests, we require it to be super polynomial time. And this clearly relaxes the security, but it's still quite meaningful, and there has been a long line of work in this study. But really the main question that we ask when it comes to relaxing security definitions is that what security are we really losing, right? When we are relaxing the definition, can we precisely quantify what security we are losing by relaxing this definition due to concurrent attacks? And if you think of definitions like super polynomial time simulation, it's not always clear how to precisely quantify this information, okay? So what we'll be studying is this notion of multiple ideal query model, which was introduced in joint work with Whipple and Rafi a few years ago at Crypto. So the definition kind of looks like the standard real ideal paradigm, where there is a simulator in the ideal world who can make output queries to the trusted party, except that now the simulator has a reset button. So the simulator can now reset the ideal functionality and make more than one output query on different inputs of its choice, and all of the output that it gets from the trusted party are with respect to the same fixed input of the honest party. And when I say fixed input, it's fixed for a particular session, okay? And the same experiment can be repeated for each session. And now we can parameterize this definition by considering a parameter K, and we say that this protocol has a query complexity K if we can construct a simulator that makes K output queries to the ideal functionality in each session. Okay? So now it's easy to see that with this definition, we have a very easy way to quantify the security loss, right? If we have query complexity K, it means that we are leaking at most K outputs, and therefore the security loss is K outputs in each session. And to look at the meaningfulness of this definition, we can consider this function F, which is fixed with input X of the honest party in a session, and the remaining security in that particular session is essentially the level of unlearnability of this function for after K queries, where K is the query complexity, right? So this is quite meaningful, even when K is polynomial, this makes sense for unlearnable functions, but of course our goal will be to minimize this K as much as possible, and we will discuss this later on. And as a special case of this primitive or this notion, when K is constant, we get password-based key exchange as per the definition of Goldback and Lindel. I'll come back to this later on when we mention our results. Okay, so as it should be obvious, the main goal in this line of work or in this notion of multiple ideal query is to minimize the query complexity. The smaller the K, the better the security loss, right? Or the less of the security loss, right? So let's look at the state of the art in this work. Let's first discuss lower bounds, okay? So in this context, it was shown by Goyal and myself in your crypt a couple of years ago that it is impossible to achieve query complexity of constant, okay? That is, there exist functionalities that cannot be securely computed in the MIQ model with query complexity constant. And one point that I want to remark here is that this result rules out query complexity of constant where the constant has to be a universal constant. That is, it must be fixed a priori, the protocol design, and then we require that any simulator for this protocol should only make at most these fixed K queries, okay? So it rules out a universal constant. In terms of positive results, there have been two prior works. The first with Goyal and Rafi and the second one with Wipple and Divya, where we constructed secure protocols, assuming oblivious transfer, where the average query complexity in each session was a constant. Let me clarify what I mean by average. So really the broad guarantee here was that if there are n sessions where n could be any arbitrary polynomial in the security parameter, then the total number of output queries made by the simulator in the other world would be a constant times this number of sessions n, okay? So therefore what this broad guarantee gives you is that on an average in any session, the total number of queries will be a constant, but in the worst case, the total number of queries in any particular session could be arbitrary polynomial in particular proportional to the number of sessions. And this is really bad because it means that in some sessions we may completely compromise, we may completely lose all security, all right? So what we want is essentially to achieve a worst case guarantee, okay? That is, we ask, what is the best possible worst case query complexity that we can achieve in this model? And what we show is that assuming oblivious transfer, we can construct secure protocols where the worst case query complexity in every session is only a constant, okay? So this may sound funny in light of the negative result that I mentioned earlier, and really the way we circumvent the lower bound is by achieving this constant, or by making this constant to be adversary dependent. What I mean is that if the number of sessions is let's say n to the c where n is a security parameter and c is some constant, then the number of idle queries in every session would be roughly two to the c, okay? So which is still a constant. And this matches the lower bound from Yorkev-2013 where adversary independent constants or universal constants were ruled out, okay? So this essentially settles the main problem in this area, and a nice feature is that the protocol is actually the same as in previous works, and what we do is essentially give a new analysis of these protocols. And as a corollary of this main result, we get a concurrent secure password-authenticated key exchange protocol in the plain model, that is a standard model, no set up assumptions, no random oracles, nothing. And this is the first search protocol that is known. And to compare with the definition of Goldweig and Lindel from 2001, what we essentially get is that for end to the c sessions and a password dictionary d, the security of exchange keys as per their definition is essentially two to the c divided by the size of the dictionary. And this can be seen as the amount of guesses that the number of password guesses that the adversary can make. Okay, so let's jump into the technical details. So the first question that we should ask is why is concurrent security even hard, right? Can we just apply the GMW paradigm in the concurrent setting? We saw this kind of slide in the previous talk, but this will be slightly different here. So let's say we start with a semi-onness protocol, and since we are in the concurrent setting, we will, instead of using standard zero knowledge, we are going to use a concurrent zero knowledge protocol. And indeed, there are many concurrent zero knowledge protocols known in the literature. Since we are in the concurrent setting, we also have to worry about non-malability. So let's throw in non-malability as well. And in fact, we also have concurrent non-malability zero knowledge protocols in the literature. So the question is, why doesn't this already give concurrent secure computation? And to understand this, let's go back and figure out how do simulators typically work, right? So simulators work in the following manner. The main job of the simulator is essentially to extract the adversary's input. And usually it achieves this by rewinding. Of course, there is also non-blackbox simulation to consider, but let's ignore it for this talk, right? We will only consider blackbox simulation. And now, essentially, since we are in the concurrent setting, the simulator must extract adversary's input in all of the sessions, right? That's its main job. The rest is usually easy. It can be taken care of by standard techniques. So let's just worry about extracting adversary's input in all sessions. Okay, so now let's kind of revisit the core problem of concurrent simulation. And this observation comes from Linda. So let's consider the scenario where the simulator is trying to extract the adversary's input in a bunch of concurrent sessions. And since the adversary controls the scheduling of messages, let's consider rather complicated scheduling of messages across different protocols. So here, the blue arrows denote an outer session and the orange boxes denote inner sessions. Okay, so the inner sessions are interleaved inside the messages of the outer protocol. And now the simulator's goal is to extract the adversary's inputs in all of these sessions. So let's say he tries to extract adversary's input by rewinding the outer blue sessions somehow. Okay, so let's say it's rewinds in the top part of the protocol and sends a new message. So note that when it does so, a new copy of the inner orange session will be executed by the adversary, right? And in particular, the adversary may in fact even change his input in this around execution of the inner session. So in the original copy of the orange session, he may use an input Y and in this rebound execution, he may use an input Y prime, which is different. And now in order to complete this rewinding, the simulator should obtain the output for this Y prime as well. And if you think about standard MBC, there the simulator only has one output query, so he kind of gets stuck here. But since I already mentioned to you the MIQ definition, clearly MIQ can help us in this setting, right? In this notion, the simulator is in fact allowed to make multiple output queries, so therefore he should be able to simply reset the idle functionality and take care of this problem, right? By getting multiple outputs. And indeed this observation already shows that the GMW paradigm using known concurrent zero knowledge simulators or known concurrent zero knowledge protocols already use a positive result in this setting, but with the caveat that the query complexity is some large polynomial, okay? And this is quite bad. We want to minimize this query complexity, okay? So how do we improve the query complexity? So if we look back, really the main problem with the main problem, why we get a large query complexity is because these concurrent zero knowledge simulators rewind a lot, okay?  And with this view, the goal is to minimize the number of rewinds. If we minimize the number of rewinds, then we'll minimize the query complexity, okay? So it sounds simple, right? I mean, let's just rewind fewer times. What's the big deal, right? So, well, it turns out to be a big deal because it's not like these works on concurrent zero knowledge. They were not rewinding many times for just for fun, right? There was a reason behind it, and so let's try to understand this reason, right? Why did they rewind so many times? So again, I'm going to now consider simulator and adversary, but now the simulator will play the role of the prover and the adversary will play the role of the verifier, okay? And in fact, I'm going to use the same nested interleaving of sessions that I discussed earlier, okay? So here's the interleaving of sessions, right? Now, of course, these sessions correspond to a zero knowledge protocol, but that doesn't matter for us. The details don't matter. And the main challenge in this setting is for the simulator to simulate the adversary's view or the verifier's view in polynomial time, okay? So again, the simulator since it can only simulate by using rewinding in our setting. So therefore, let's say it tries to rewind the outer session somehow by sending some new message. And again, when it does so, the inner orange session will be executed again, okay? Here, we don't care about the outputs. In zero knowledge, the outputs are simple, right? It's just one. So we don't care about the output, but the problem is that when this rewinding happens, the simulator is forced to simulate this inner orange session two times, okay? It may have already done a lot of work in simulating this orange session on the main execution, but when it rewinds the outer session, it is forced to re-simulate the orange session inside, okay? And now, if you consider some adversarial nesting of sessions that can quickly lead to exponential simulation time, okay? So this is really the main challenge in concurrent simulation. And looking at this picture, this looks very similar to the problem of multiple outputs that we discussed earlier, right? And in fact, what I'm going to show you later is that these are essentially the same problem. So the way this problem of exponential time is solved is by using sophisticated rewinding strategies which involve recursion. So the basic idea is as follows. Let's say here we have a concurrent schedule of many sessions, okay? The different colors denote different sessions. The idea is this. The simulator takes this entire transcript of all the protocols, okay? It first divides it into two parts. So when it divides into two parts, we say that it's like using a spreading factor of two, okay? This will be important for us later on. After dividing this transcript into two parts, it rewinds each of these parts independently, okay? And now we just recurse. We take each of these two parts, we divide them into two further parts and rewind each of them independently again. And we keep going until we reach the point where each of the parts is just of length one. That is, it just consists of one pair of messages. Okay, at that point we stop. I'm not going to argue why these rewinding strategies work. That's, you know, for another day. But you can trust me, or in fact, you can trust all of these people that these rewinding strategies really work. So now let's come back to the MIQ model, right? Let's come back to the concurrent secure computation setting. And here really the only difference is that now we will be concerned especially about these output messages. So recall our goal was to minimize the query complexity, which in turn translates to the number of times the output messages appear in the protocol transcript. Okay, or rather in the simulation transcript. So therefore we will be concerned about minimizing these output messages during the simulation. And these output messages are denoted in these bold arrows. So now if we apply these rewinding strategies, you know, you can look at this picture, we are rewinding so many times, clearly we are going to get a large query complexity. And what we really want is essentially to do this. We want to throw away some of the rewindings and only rewind very frugally, that is just sufficient for extracting all the adversaries inputs. And still, and then we essentially will get small query complexity. So this problem can be essentially broadly studied as the problem of precise simulation, which was started by Mikhalian pass in the standalone setting, and then later by Parnari et al in the concurrent setting. So this problem says the following. It says that we want to minimize the overhead of simulation. So what do I mean? Let's think of running time of simulator. So typically when we think of the running time of the simulator, we say that it could be some arbitrary polynomial in the running time of the adversary, okay? But here in the case of precise simulation, we say that a simulator is precise if the running time of the simulator is only a constant overhead, has only a constant overhead in the running time of the adversary, okay? And now we can essentially map this to our problem, to a problem of query complexity. So essentially now we can consider a similar precision problem for number of outputs, where in the real world, the number of outputs seen by the adversary are n, where n is a number of sessions, so one for every session. And now we want that in the idle world, the number of outputs that the simulator should learn is constant times n, okay? So it's really the same precision problem. And in fact, it was shown by Gwell et al in 2010, that you can translate the precision in run time to precision in the query complexity, okay? So these are really the same problems, great. So that is nice. In fact, we do now know reminding strategies which achieve this precision. So what's the problem? So the problem is that these precise, when we take this view of precise simulation, it only gives us global precision, okay? We're only saying that if the number of outputs in the real world are n, then the total number of outputs in the idle world are constant times n, okay? So this global precision will only give an average case guarantee on the query complexity of the simulator, whereas what we want is a worst case guarantee. So we need to do something new. So at a high level, our strategy is going to be this. Essentially, as we already saw, the query complexity of the simulator in any given session, let's say i, is essentially the number of times the output message of the session appears in the simulation transcript. It obviously appears more than once because we are rewinding. And now we want to simply count how many times this output message appears in the simulation transcript. So what we do is essentially a new combinatorial analysis of the rewinding strategy of Gwell et al from 2013. And with this new analysis, we are able to show that essentially their simulator already has a constant worst case query complexity. So our strategy will essentially proceed in three steps. So in the first step, in the first step, we are going to consider a restricted class of adversaries that we call static adversaries. So static adversaries are ones which do not change their behavior upon being rebound. That if I rewind the adversary, it's going to send me the same messages that it sent to me on the main execution. And in this case, we are able to show that if you take existing rewinding strategies like the one of Kilian Petronk or Prabhakar Natal, where the splitting factor for recursion is n, where n is a security parameter, then for these rewinding strategies, you can already achieve a query complexity of a constant. In the second case, we now consider adaptive adversaries. And these are really the adversaries that we care about. These adversaries may change their behavior upon being rebound. And here, we proceed in two steps. In the first step, we again consider the same rewinding strategies of Kilian Petronk and so on, with the splitting factor n. And here, we are able to show a slightly worse bound. We show that the query complexity is logarithmic in the security parameter. And then finally, we apply this sparsification, stop, sorry. Okay, let me just say it. So in the final step, we use the sparsification step of Goyal et al, which essentially squashes this query complexity from logarithmic to a constant. So let me actually just show you these steps pictorially. So the strategy looks like this. We are going to look at the recursion tree of these rewinding strategies. The recursion tree looks like this. We take the main transcript, the main execution. We divide it into n parts here, and it's simply two for pictorial reasons. And then we take each of these parts, and we run it two times. Each of these parts is executed two times. And then we just repeat this process many, many times, essentially, we recurse until we reach the final level, where each of the parts is just size one. So now, let's consider some particular session, and let's count how many times the output message of that session appears in the entire simulation transcript. So let's say, for a given session, the output message appears in the second half of the protocol transcript. So it's in the right-hand side, half still, denoted by this red box. And now, when we rewind, we divide this red part into two parts, and run each of these parts independently. So again, let's say that it appears in the right part of this right part. And since the adversary is static, it will appear in the same halves always. The adversary cannot change its behavior upon being rebound, so therefore it's always going to appear in the same parts, either all the right parts or all the left parts. And now we can just repeat this idea going downwards the recursion tree. So the observation is as follows. At each level in the recursion tree, this outward message can only appear two times. And now the number of levels, if we use a spreading factor of n, then the depth of this recursion or the number of levels is a constant. And therefore the total query complexity will also be a constant. So let me just take two more minutes. Let's consider adaptive adversaries. We are going to do the same thing, but now the main challenges are falling. If we again look at this, the part where the outward message appears, the problem is that not only may it appear in the places where it was appearing previously, here since the adversary can change its behavior upon being rebound, it may also appear in the first half of the tree. And this is because that even if this message did not appear on the main execution when the adversary is rebound, it may suddenly start sending this outward message in the rebound executions. And this is what messes up the calculation. The previous bound of constant does not work anymore. So essentially the bad event is that the outward message may appear on the rebound execution even before it appears on the main execution. And to solve this problem, we use the indistinguishability of execution threads. So this is a property that is common to all known revining techniques that the behavior of the simulator appears the same to the adversary on all execution threads. And by using this property, we can show that the probability that this bad event appears once is a constant. Then we can just essentially repeat this idea and say that the total number of times the bad event can happen is only logarithmic. If it's super logarithmic, then essentially the probability becomes negligible. Right, so this is how we handle adaptive adversaries for the previous revining strategies. And the final step is this magic step where we essentially take the revining strategy of Gauil et al, which can be seen as follows. This revining strategy looks very much like the previous revining strategies except that a lot of the nodes in this recursion tree are simply dropped. Essentially, polylog fraction of nodes at each level are simply deleted. And because of this step, essentially even if we had a logarithmic query complexity in the previous revining strategies, here we are able to essentially squash it down to constant because of this classification step. So essentially the bad event before was happening logarithmic many times and now essentially after specification we can show that it only happens constant number of times.