Hello everyone and welcome after a quick break. We have a talk about static typing in Python by Sanjit. So I would like to invite Sanjit to the stage now. Can you hear me? Yes, as long as I can hear you. Hello everyone. Great. I can hear you as well. And yeah, feel free to start and let me know when you want me to share the video. Yeah, you can go ahead. Sure. So, okay, I'm just trying to set up the video and because of network issues, we are trying to do this pre-coded talk. So Sanjit will be present with us for all the questions. Feel free to ask Sanjit any questions that you have any time. We'll make sure that Sanjit gets your question after the end of this talk. Okay, so you have the hop in chat. Feel free to put the questions there and stay there. I'm just just a few more seconds. And yes, we have the talk right here on the stream. Nice. I guess you can see the talk and here we go. Hello everyone. This is Sanjit and I hope you all are having very good time. I'm also very excited to be here. Before we get started, I would like to thank Ficon India 2020 team for giving me the opportunity to present this talk. So as you can see my title that I'm going to talk to you about a started typing in Python. So without further ado, let's get started and see what's the agenda. So primarily I'm going to actually try and set some context about typing. And we will understand the world of different type of typings available in Python. And why do we actually need static typing at all? And because Python is a dynamically typed language and people love Python for this feature. And once we understand that how static typing works, we'll also understand that how to be static type Python code. And then we will jump on to see that what are some of the complex types available in Python's typing module, which we can use to actually static type our legacy or large code basis. Then we'll also see one important tool called type checkers. So I'm going to primarily talk to you about MyPy, which is one of the most popular type checkers available at this moment. And then we'll end the talk with some pros and cons of static typing. But one disclaimer I want to give that I'm going to talk to you about some of the basics stuff as well. So in case you're aware about some of the basics, please bear with me. I will be covering because there are some people who may not know some of the initial concepts as well. Okay. Okay, without before moving forward, let's also let me just quickly talk about myself. So as I said, my name is Sanchit and I'm primarily working as a lead software engineer at E-PAM India. And I'm very passionate about open source communities and Python and especially about Docker. And I'm a very community-centric person. I have been working with communities from last almost three to four years. I helped run a couple of communities that are called Hyderabad Python user group and also DevOps and SRE user group Hyderabad. And I'm happy to talk to you about anything with regards to open source communities, Python, Docker, or about, especially about Hyderabad. And you can find me on my social handle, which is in a list. I'm available on Twitter, LinkedIn and GitHub. So feel free to reach out to me and I'm happy to get connected. So let's get started with the talk. So let's revise some concepts like static typing, dynamic typing, and etc. So here what we see that this is a basic example of static typing. So I chose to use C code because that is a very familiar language for all of us. So essentially there is a function called main and there's a variable called age here, which is typed as int. So age can only accept integer values. So I'm trying to print that particular variable here. So essentially that's how you started typing code that your compiler would know that before runtime itself that there is something called age, which is supposed to be an int value. So in case you try and assign some string value or take a value, you will end up having an error here. So that's how basically I started typing scenario would work. Let's also understand what is dynamic typing. Let's try and revise that. So this piece of code is primarily written in Python 2.7. You can ignore that because typing is primarily available in 3.5 plus. But let's understand this piece of code. There's a function called foo here, which has two conditions. If a is greater than zero, then do something and if in the elsewhere do something. So essentially when I'm trying to call, let me also actually include the pointer so that I can actually navigate and help you understand. So now when I call the function called foo here, right, by passing the argument called to this guy goes here and the function and the condition gets fulfilled and it prints high. Okay. Give me high as an output. So this line doesn't get executed, which means that this type checking of this line is not happening when I'm running this function. Okay. So that's how the dynamic typing things work here. But when I call foo of zero, that is where the condition gets fail and then tries to actually evaluate the type of it. Which means if it is not being called, I mean, if it is not being evaluated, the type is also not going to be checked. Okay. So that that's the beauty of dynamic typing that you don't have to define the types. You may have some bugs in your code with regards to type of the objects or the variables, but you don't have to write that specific code by defining the specific type of variable, etc. So just a quick reminder about how does the dynamic typing thing works. There is one more concept called duck typing. Okay. There's a saying called if it cracks like a duck and if it walks like a duck, it is probably a duck. Right. So I'm trying to actually replicate the same scenario here. There is something called class as duck, which has a method called fly. Then we have something called bird, which is again a class and it also has a method called fly. Right. And in the end, I'm trying to actually iterate through both of these classes and trying to call the fly method. Right. But what you see here is that Python is not worried about that what is my class type. Right. It is also it is only looking about whether the fly method, which is available here or not. If it is not available, then it may give me an error, but it is never going to be worried about that. What is the type of that particular animal item here? Okay. So that's how duck typing also works. So till that, till this time, I want to actually just do a quick revision of how static typing, dynamic typing and duck typing works. Let's quickly understand the why should we actually care about types? Right. Why types are important? I mean, as we see, you saw in the initial example, right, that you define your tribes and then you will end up having not those confusion later on. So you can see what I'm trying to say that Python is a dynamically type language that you don't have to spend too much of time writing those types and define things. Right. But what will happen that let's say if you go towards a very large code base or your code is getting multilayered sort of thing, then you will end up having tough time figuring out those box or issues where in there is some data flow happening and you are having tough time to figure out that what this particular argument is about and from where this particular person is argument is being called a function is being called. So those type of scenarios which can occur, definitely Python is a beautiful language and it also has this feature called dynamic typing, but it also has some cons. So we'll also talk about those cons as well, but I'll talk about the cons of static typing essentially, but dynamic typing also has some cons. If you probably are from the world of Java or from other languages, you will understand if you have your code statically typed, it helps you actually find out the bugs much, much before if it goes to production. So that's I think that's why we should care about ties. Let's move forward and understand that with an example. So there is an example I've written a very basic example is a function called do something, which normally has four arguments here, something called user class client, retry count and data. And I'm trying to import my user class from the my module. So what you see here is that there are a bunch of arguments, but let's say if this whole stuff is available probably in a legacy code base and you are supposed to fix a bug here. You'll end up having a very tough time finding out that where these arguments are defined and what are the type of and what do I expect from these. Okay, maybe there is some code, but you'll end up having maybe have a tough time to figure out those issues. So that is why static typing becomes very important. And so what you will do maybe even before you don't think about typing, you will actually find and find out that if there are any doc strings available, maybe you will try and search for doc string and try and see that if you can make out something with that. Or in the other case you may also try and find out if there are test cases available. Okay, with the help of test cases, you can figure out that how the code is working or you may also have some bunch of other statements. So these all scenarios are there and possible wherein you can use those things to understand the code. But still, there is a possibility that you will end up having debugging the code and reading the whole piece of code base just for a single line of fix. So these are all possible scenarios and it can give a tough time to a developer who is new to the code or probably working on a very large code base. So that's why I think static typing becomes very important. And so once you actually write the same code with type annotations, which was introduced in PEP 484, 483, I think, if you static type your code using this way, right? So what will happen that you have your same function do something? It has an argument called user object. We have client, we have retry count and data, but it clearly specifies using the typing modules types available. So I'm trying to import list, double dictionary and set from what you'll call typing, which is natively available in Python 3.5 plus. If you use that, you can actually specify that what a specific argument type is about. So now if you want to static type your code, you can just apply a colon on top of your, beside your argument and you can define your type here. The same thing I'm doing here. I'm saying that user object is primarily user class and client is primarily a dictionary of string as a key and list as a value. The retry count is basically integer and the data is basically a tuple. And ultimately using an arrows and I can specify also that it is going to return a set of integers. So essentially it is helping me to understand the code right away and help understand that what do I need to do about these arguments? If there is something which is happening in my code and some bug is there, that can primarily help me understand those things. And in my personal opinion also, it's subjective, but it's my personal opinion. So rather than writing doc strings, if you write static type, your code right, it becomes much more cleaner and easy to understand. With those long, long, bright doc string, where you define your specific argument and whatever example, etc. But if you write these doc strings, it becomes very much easier to understand. And in any way it's going to help you figure out those bugs much before. I'll talk about how this thing can help. But before we move forward, I also need to set one example here that static typing in Python is not actually natively implemented. Python is still a dynamically typed language. And static typing is available as an optional thing. So we can use static typing, but it's often available. I'll talk more about this probably later in this session. Let's also try and understand more on the static typing front, and then we'll come back to that part. So let's see that there is another example called, there's a function called get employee first name. Primarily it is taking an argument wherein I'm passing a name and then returning the name after doing the slit of it. Then there's a dictionary called dummy name wherein I have first name and the last name. Then we have a user input, which basically takes input from the user and then try to return the first name by calling that specific function here. And in case the first name is not passed here, it basically called the same function again passing the dummy name. And then if I try and in there, I'm trying to print hiSunchit. So basically if I pass my name here as Sunchit Balsandani, so it is going to print the first name of my name. That's going to be Sunchit. So it can say hiSunchit. So the code looks fine, but there's a bug. And what is the bug here? So essentially if you see, if I don't pass anything here, and please provide your name, if I don't pass anything here in this input, what will happen that this condition would be true and now the function would be called as get employee first name with the dummy name. And dummy name is essentially a dictionary. And the dictionary doesn't have the split method. So if it failed, that's what is happening here. So it is possible that if I don't do that test case of passing an empty value, I won't cache this bug at all. And this code may go to production. And maybe after that sometime it may break because of this input. So how do we cache these bugs? So you can see that there is an error status coming and it's saying that attribute error dict object has no attribute called split. That's why it is failing at line number two. So how do we fix this bug? I mean we can fix that bug just by using typing as I said. So you can use the typing module. You can say from typing import dict, you can specify your dictionary here. You can also specify arguments in your function. You can say the name is always going to be a string value and return type is also going to be a string value. But the important thing is that I'm going to also say that my user input is also string and first can be a string way. But eventually this would make our life easier. So when I'm saying the name has to be an str value, that means a string value. So whenever this condition fails, if not first name, and I try and pass the dummy name which is a dictionary, I'll end up having that error in my type checker.  And I would know about that particular bug beforehand itself. So how can I do that? You just have to actually use that static type checker. Let's say if you use mypy, and you run that file called mypy 1.py, you'll end up having that error saying that getEmployFirstName function has an incompatible type called a dictionary of str and str, but expected type is str. So that's how you can easily find out and validate whether there is a bug or not. So these are some of the basic examples. Let's also talk about how do you annotate the variables. I think we also had an example in the previous one, but let's also understand how does the variable and function annotation works. So again, a very basic example. Again, we have something called the function called odd numbers, and odd numbers primarily have numbers as an argument, which is basically a list, and it also returns a list as an argument. But essentially, if you see that, I am trying to actually say that my odd variable is basically a list of integer, and then I'm trying to append something in odd. So if I try to append something which is not an integer, and if I run through this whole code using mypy type checker, I will definitely have an error saying that you are trying to append, which is not an integer value. So these are the things, I think, your variable annotation, also the function annotation that can help you figure out those bugs much ahead of your time. So I just wanted to help you understand that how these things work. Let's also understand that what are the different complex types. And why I'm talking about these complex types, because once you try and start implementing static typing, right, you'll also have opportunities to work on large code bases or scenarios within the type return types of functions or uses of those things are kind of little complex. So typing module provides a very comprehensive of different types. I'm going to cover only a few of them today, but you can feel free to reach out to probably look at a typing module and understand that how many different types are available. So let's talk about a few of them today. So there is one thing called union type. And it's very important and also very common if you work on large code bases. What will happen? Let's say there are two functions here. One is do something one and one is do something two. Both are accepting one argument called argument one and argument two. argument one is basically an integer value and argument two is basically an string value. But why I'm trying to actually specify that you may have a use case but you're not sure that what type of argument or what type of type you're going to return. It can be class A, it can be class B and this class and class B is just an example here. It can be any other thing. You are not sure about a return type of your function. It can either return a dictionary of some values or it can either return a set or a couple. So no matter everything is going to be an object. So it's up to you and according to use case but if there is a use case then you are not sure about what's going to be return type. So you can keep that thing in the union type mentioning that it can either be class A or class B. This is probably a bad example. I'm using classes as a return type. It should either be objects but let's assume that these are all objects. So either class A or class B would be returned from this function. So type checker would understand if your function is probably well written it has a return type as class A or class B so it will understand that it is a correct implementation. It's also possible that my class or my function would return none in some cases. So you can use none as one of the arguments here in the union. Let's also look at optional type. What's optional type? Since we talked about union and also we had none in one of the argument in the union type. So typing module actually supports that natively and in cases wherein you have one of the argument as none so you can use optional here. So what you see in this example that there is something called handle employee and the argument is primarily E here which is saying that it is optional of employee. So it can be optional or it can be none as well. So you don't need to define those default values. It can come as none. So depending upon that you can write your code and you can actually write the code and try and follow the logic. But optional would help you have that thing natively available. So you don't need to actually have a union of employee and none. So Python natively provides I mean the typing module natively provides an optional type which you can use and that will automatically understand that there can be a none coming up here. They can be a none. They can also be an employee but they can also have a none as well. So that's an optional type also very handy and useful. There is one more thing called any type which is very, very important because a lot of time you will not be sure about the type of any particular object. So in that case you can use any type. It can be of any type and it can have any type of function but it's not going to be a built-in. It's not going to be a completely built-in but any type of object you create you can actually have that as any type of type from typing module. So again similar example that we have something called do something and arg is basically a dictionary key is a dictionary and value can be anything. It can be any type of object be it a list or a tuple or a set or any custom object. So it doesn't matter. You can just mention any here. So for a lot of cases if you have to fix right once you actually start implementing your satir typing legacy code basis I ended up using any type at a lot of places because if you're not sure about something you can use that but it is always good to specify that what that specific type would be but any can be your I mean it can be your go-to thing if you're not sure about any specific type. Let's also understand how do we implement that type instead of typing so there's something called sequence available in typing module. So similarly I mean like I spoke about that typing that if there is a method available which means that if there isn't either method available you can also available in list type and also available in sequence type so that's why I'm able to actually iterate through the sequence of load and it works well. So that's basically example of duck typing. So basically if as I said that if fly method was available in both duck and word classes it was working fine. Similarly in the case of sequence also if it has a data method you should be able to iterate through it. So you can use sequence if it is required in any of the cases. Let's also talk about generics. So if you are probably from Java background you may also be familiar with the generics. So you can write the generic types. So I'm trying to create a generic type here and passing it as a another thing in the calculator class. So what will happen that I have something called item one which is an one type and then have wide input on the type. So ultimately the written type is also the generic. But it depends on me that if I have when passing one and two here in the calculator class object so I can do an add function and add method by passing one and two but it will work for me because I'm trying to create a generic here. That's how the generic concept works. I'm not going to explain how the generic works generics work but essentially you can try and create generics using static typing. I mean natively it is not available in Python but in the help of typing module you can create those generics and it will give you the same scenario which basically is available in other languages. So I'm creating a generic and passing the argument as one and two and it will end up having the three as an output because the type is is kept as a generic and similarly I can also use str here and pass as a generic type and it will end up having my string concatenation. So a very good example to understand that using this way you can implement generics and especially when you work on those multilayered architecture you have your interfaces etc it is very handy to have these things available. So this is about generics now since we understood about how static typing works and how do you implement static typing along with some of the complex types these are some of the static type checkers available primarily mypy, pyree and pytype mypy is primarily in your pythonslap and also pyree is from I think from facebook and pytype is primarily from google but pymypy is the most popular one which was developed I think at Instagram so let's understand that how do you use mypy I think I already gave an example of how does mypy work but let's also understand quickly again you can just quickly install mypy using pip install mypy and any script you want to actually run through which is already statically typed you can just say mypy script.py once you say that so you will end up having those those errors so I am just trying to show you another example let's say this is a function called myfun and it has a statically typed thing and you can try and pass 10 value which is likely accepting an integer value sorry string value but I am passing an integer value I will end up having those errors here so it says that argument 1 to my function has an incompatible type call in so that's how the mypy type checker is going to give you the errors beforehand that's how you can use my type checking in mypy and there is also something called monkey typing so once you actually work on a legacy code which is not statically typed and you would not want to actually spend a lot of time to type check those code or add annotations you can use this project called monkey typing which can generate stubs for you so I would recommend you to use to read more about monkey typing on this link which I am going to share in my slides so essentially it is going to generate stubs and using those stubs you can apply annotations on your legacy code base that will help you start to type your code and essentially your legacy code which is already written but not statically typed and I would recommend if you are writing a new code you should start writing type code from this scratch so how do you approach started typing so essentially if your project is very new you can 100% you can use started type code because it is going to help you a lot with regards to finding out bugs later on and you should definitely include that in cf so any type checker you can also talking about mypy or pyree or others you can use those in your CI so that before things are going up I mean before your test cases are being run your type checkers can actually run and understand and help you figure out those bugs beforehand else if your project is not new it is a legacy code base or a very large code base on which you are supposed to apply started typing you can either use monkey typing as I spoke about because that is going to help you to generate those annotations automatically and also you can actually start working in the large code base when you are working in the new code right you should actually try and start to type your code because gradually if you can build up your starting typing it will help you in the longer train and again you should definitely implement a CI also for the large projects or the older projects and I would recommend that you should start using started typing only for those piece of your code which are kind of most commonly used so that the bugs are kind of can be can be little less so I would recommend these approach if you are planning to use started typing in any of your project yeah so let's also talk about pros and cons before ending the talk so as I said in the start that started typing is definitely going to help you to document your code it makes your code much much cleaner and it also helps you write list is because basic data flows wherein you are trying to test whether a function exception in pj value or a string value those type of tests can automatically be eliminated because you are going to implement started typing and type checkers are going to take care of that and as we have been talking that you can cache those bugs beforehand for sure and refactoring also when you are probably coming back to the same code after let's say 2 years the refactoring of your code would also be much much easier because you are going to use started typing and it is going to make your life easier and certainly there are some cons as well so let's also talk about those cons definitely once you import typing module it is going to come up with some import time it is going to add some slight delay there but yeah that is understandable because typing is also heavy module and there are a bunch of things being imported so every time when you do from typing import this a lot of things get imported so that is a downside and also definitely since Python is dynamically typed that you don't have to actually add a lot of types at this moment but once you start working on your started typing you have to spend time you have to understand that what is the type of going to be for a specific function or return type or an argument so those things kind of take a lot of time and if you are working in your legacy code and trying to generate desktops those things I think kind of add a lot of duplicate files you may not want to be there because it makes your code base a little mess but yeah I mean if you definitely want to implement typing I think Stubs are also on monkey typing is also one of the good way to do that so they are taking two sides of the coin always that there are some pros and cons available as well so I think with that I would like to conclude that if you definitely try started typing it is definitely very helpful and especially for new projects I would recommend using typing and you can explore these things I have referred some of the blogs and also some of the videos you can actually go here and understand some of the good videos and blogs I found I'm open for any Q&A thank you hello everyone thanks Sanjith for the great talk and I can understand that it was recorded because of all these network issues and for those who are asking about the link to the video just to make sure that we will get the entire video that you are seeing right now not that video but this entire stream with the Q&A and everything and we will post it on YouTube so you follow PiconIndia on twitter and all the other social platforms that we have and when it comes to the presentation that Sanjith was using Sanjith will share it on Zulip later on and over to you Sanjith we have some questions let's quickly take some questions do we have to use typing for example can we use list instead of dict capital D and capital L yeah so those classes are available in typing module which starts from capital L and capital D these are specific to typing module you should not compare it with available default native classes like list and dictionary you cannot use them in compared to native ones the second question is does static typing checking slow down program execution yes it does up to some extent so I would recommend that you can use some performance tool or you can also use the off time tool available to check that how much time it takes but definitely it comes with some downtime I mean it comes with some time so whenever you do import typing it's certainly going to take some time but yeah there are some cons available as I talked about in my cons like but yeah there are some benefits as well so in case you can actually manage those times so you should use static typing we'll take one last question because of this time constraint and the last question is would not using any that is capital L they really defeat the purpose of type checking sorry capital A yeah so I think you are partially right that any if you're using any so as I said that you should be cognizant about using any type you should first of all try and find out that what's the type is about and then you should use that specific type but yeah in case you're not able to find out any specific type of an object which you are not sure about then in that case typing modules provide you this way of using any as well so yeah it's up to also very dependent on the use case you are trying to implement such it and rest assured for rest of the questions such it will be present on hopping chat as well as on julep chat that is 2020 power slash stage power slash deli so make sure you subscribe to that stream such it will be present there for all your questions and he will reply to the questions on hopping chat which are still present there so thanks a lot Sanjith thank you


of collision resistance and hash functions and specifically the parallel complexity of such a domain extensions. Namely, how many rounds does the scheme, the final scheme have to invoke the underlying function f and as my students taught me, the best way to explain something is by way of examples. So let's review the well-known domain extension paradigms that you are all probably familiar with, like the Merkel-Dumgard scheme that takes as input a message divided into blocks and initial vector IV and applies f iteratively where each application of f needs to have the result of the previous application and therefore all in all, the output of the construction is the output of the last invocation of f and all in all we have a linear number of iterations where linear in the number of blocks of the original message. So this is a very, very good domain extension scheme but not when you consider the complexity, the parallel complexity. So maybe the Merkel tree is an improvement where in this scheme, f is applied in a form of a binary tree where at each level we apply f to the results of the previous level and finally the output of the scheme is the output at the root of the tree and this is a great improvement. We have an exponential improvement from being linear. We have a logarithmic number of rounds of course to the underlying function but we would like to be even better than that. We'd like to go constant. Can we have a constant number of rounds and Maurer and Tesaro showed how to obtain a two round domain extension scheme and their scheme is almost as good as you can expect. It's two rounds but it falls a bit short from going fully parallel, namely a single round of calls. It does obtain a stronger property which is called indistinguishability which is a notion of indistinguishability from random proposed by Maurer, Rene and Hollenstein. And one drawback of this construction for me is that I couldn't draw it on a single slide at least. And let's go back to our question. So the question is how parallel can you go? Can you go fully parallel? And this is a very interesting question especially when you are concerned with hardware applications of hash functions. And can we do it? So I won't keep you intense too long. I will tell you that the main result is affirmative. Yes, we can. We construct a fully parallel domain extension scheme that has a single round of polynomially many invocations of F and in the random oracle model it guarantees collision resistance and some notion of being random like which we call weak indistinguishability. It's very simple and it has a nice property that it preserved the algebraic degree of the underlying function F. So take any of your favorite function F to replace the random oracle. Our construction will have the same algebraic degree as your function. To compare with previous constructions all constructions have at least two rounds so they are going to be at least quadratic in the original function. They have a quadratic degree in the degree of F. So let's move on to describing the construction. I will describe a general paradigm for obtaining parallel domain extension fully parallel. You take the original message now don't divide it into blocks. You apply a deterministic function to it and we will call this function a code and you obtain C of M. You divide C of M into blocks and you apply F independently to each of the blocks. And finally you XOR the results of these applications and that's the whole construction. The output is the XOR of all the applications and it's very easy to see that there is only one single round of calls to the underlying function F. It's very easy to see that the construction is simple and the only question, so you take the message, you apply a code and then you apply XOR. So the only question is what should the code be? What do we need to require from the code? So in order to understand that let's define security in the random oracle model so here we consider an unbounded adversary that is bounded by the number of calls it can make to the function to the oracle F. And having this security definition in mind now we can think about what should be required from the code C. Maybe the code C is not required at all and how do we understand that? Again by way of examples, by way of attacking the scheme. So let me remind you that to attack the scheme the adversary is required to come up with two distinct code words that collide on the scheme namely if you XOR all the F applied to all the blocks of X and you XOR all F applied to all the blocks of Y you get the same result and the reason I can consider code words is because giving two colliding code words an unbounded adversary can recover the original messages without querying the oracle at all. Okay so let's try with a very simple code. Let's assume that we don't need the code at all maybe the code can be the identity every word is a code word and it's very easy to attack this scheme with this code just take any code word that has two blocks that disagree and take it again only interchange these two blocks and by symmetry of the XOR function no matter what F is these two code words are going to collide. So we actually found a collision so the XOR of all the results of F on all the blocks are going to be the same for the two code words because they are the same blocks and we actually found a collision without ever asking any query to the oracle so this is not good so let's require that the code is well ordered namely no block can appear in two different indices so this block if it appears in the first as a first block it cannot appear as a second block for any two code words. Okay so obtaining this is the well ordered obtaining it it's not too difficult but one way to do it is just by augmenting each of the blocks with its index so we cannot use the identity let's use the well ordered identity namely if each block is going to have a prefix that is any string and suffix that is the index of the code at the block and let's try to attack the protocol we take for as a pair for X we'll take a code word Y that disagrees with X on each and every block on the prefix and now we can ask ourselves what is the probability that these two code words collide? Well this is going to be very small it's two to the minus K where K is the size of the block and this is not going to be a very successful attack however the adversary can create using these two code words or these two N blocks it can create two to the N code words by simply taking all the choices of taking subsets of blocks from X and the remaining blocks from Y there are two to the N such possibilities and since two to the N is much larger than two to the K by the pigeonhole principle we're going to have a collision and the adversary only needed to query the oracle on two N blocks and this brings us to the next requirement you cannot construct too many words from a few blocks and another requirement is going to be that the code needs to have a large hamming distance between any two code words and this is a bit more subtle to see why it happens not getting into it so having these requirements in mind one may think where can we find such a code? Well luckily they exist they are called least recoverable codes and let me introduce you to them there are generalizations of unique error correction code with unique decoding these are codes that take the message M and return a code word C of M such that if for example Alice wants to send Bob C of M the blocks of C of M over a noisy channel such that most of the blocks are going to arrive safely but some alpha fraction of the blocks may be corrupted on the way still we are guaranteed that the decoding algorithm will uniquely find the original message M another extension of that is what's called list decoding where the decoding algorithm no longer recovers a unique message but rather a list of L messages and we are guaranteed that the original message M lies within these L messages finally the next generalization is least recoverable codes in this scenario when Alice sends the blocks of C of M to Bob Bob does not only get one block for each index but rather a list of possible blocks for each of the indices and we call the list of blocks for the index i, T i and now the guarantee is that the original message is alpha consistent with the union of these blocks namely that for at least alpha fraction of the indices i the actual block of the code word at index i appears in the list T i so this happens for at least alpha fraction of the blocks furthermore there are not too many such words such messages that are alpha consistent with the T i's as long as T is not too big and finally we have a recovery algorithm that given these T i's recovers all the big L lists messages that are alpha consistent with the T i's so let me formally define list recoverable codes a code C is alpha small L big L list recoverable if for all sets of blocks of size at most small L there are at most big L strings that are alpha list recoverable sorry that are alpha consistent with the T and this is a reminder what alpha consistent means and let me distinguish between two cases the case that alpha equals one is closely related to unbalanced expanders and was already used by Mauer and Tesaro when they constructed their two round scheme and in this work we require that alpha is strictly smaller than one and we show that it's actually necessary to go from two rounds to a single round of calls and this is strongly related to random randomness condensers and actually when one of the codes that we use is the code of Guru Swami Umans and Vadan that was presented in the context of condenser and it's based on the code of Pavarash and Vardi which is also a list recoverable and their code is alpha small L big L list recoverable where big L can be anything up to two to the K over C where K is the length of each of the blocks and C is some constant and you can see that small L the number of queries that the adversary can ask is practically as good as you can expect since on average every end blocks allow you to construct on average one constant number of strings code words and their code has a nice property that it is linear over the binary field so now that we know that the list recoverable codes exists we can say the converse of saying that we require them they are also sufficient for us so our main theorem is that if you give us a code see that it is alpha small L big L list recoverable and you plug it in our construction as this code then our construction is big L squared over two to the K collision resistant against any adversary that makes at most L a query to the Oracle and this is as good as you get since it's right with the bound of the birthday attack that is applicable to any hash function so plugging in the GUV code we can get many choices of parameters but one choice is to allow the adversary two to the K over four queries and in this case big L will be still two to the K over four and more importantly the probability that the attacker finds a collision is going to be smaller than two to the minus K over four and our construction is going to be degree preserving in the algebraic degree of F but so someone can say okay you got the collision resistance but you use the random Oracle maybe you should give us something else maybe like in differentiability I don't know maybe you can act like your random and if we were optimistic maybe it would be nice to hope that our construction as is is random like in some sense and this would allow us to use applications that are central in cryptography like the Fiat-Chamir paradigm which I'm not I'm going to just scheme through you take a public on three message proof system and you obtain a single message proof system and then you can apply Killian's and Fiat-Chamir and get a sublinear non-interactive argument for any NP language so this is really good and it turns out that we can prove some notion of indistinguishability from random we define it as weak in differentiability and it's a relaxed notion of the indistinguishability I mentioned before and it turns out that it suffices we can prove we prove in the paper that it suffices for the above applications so this is a nice addition and to sum it all we have all the applications that require collision resistance and all the applications that I just mentioned that require some form of indistinguishability from random and all these applications are going to have a low round complexity specifically just as an example the sublinear commitment is going to be one parallel so is the Fiat-Chamir paradigm and the last one since it uses both is going to be two parallel so I just need to know that if you compare other parameters for example with the Merkel tree then we have some loss in parameters which depend on the number of queries you ask you allow the adversary to make so to conclude we have the first fully parallel domain extension scheme and in the random oracle model it guarantees collision resistance and weak indistinguishability it is simple and it is degree preserving and it has all the applications that I just mentioned and a few open questions well it would be nice to have a cleaner implementation of F replacing the random oracle and maybe even a low degree implementation which will make use of the degree preserving property of our construction however we don't really know what are the sufficient and necessary requirements from such an underlying function F we do know that collision resistance of F is not sufficient nor necessary for the collision resistance of our construction and finally least recoverable code seem like a very nice primitive to have it seems like they should have other applications in cryptography and that's it thank you very much


The latest weapons coupled with the fighting skill of the American soldier stands ready on the alert all over the world to defend this country, view the American people against aggression. This is the Big Picture, an official television report to the nation from the United States Army. Now to show you part of the Big Picture, here is Sergeant Stuart Queen. It comes as a surprise to many people to learn that within the Army there is an elite group of specialists who wear two uniforms. One is the uniform of the United States soldier. The other is the more complicated gear of a professional diver. During a military operation, the safeguarding of ports is the Army's responsibility. To obstruct harbors and destroy port facilities is always a prime objective of the enemy. Helping to maintain those facilities or restore them after the battle is the job of an Army diver. From Korea to the Arctic, Army divers perform underwater salvage, rescue work, construction, underwater repair of Army vessels ranging from troop ships to scouts. Today we are visiting one of the Army's most unique installations, the military divers course of the Transportation School at Fort Eustis, Virginia, where apprentice divers learn one of the toughest, most difficult, and most adventurous jobs in the world. Any Army officer or enlisted man may apply for diver's school. But to enter, he must pass one of the world's most stringent physical examinations and demonstrate that his intelligence is also well above average. During their 17-week course, these men will spend hundreds of hours on the bottom of the James River, often waist-deep in mud. It is work requiring strength, endurance, and ingenuity. At the recompression chamber, the aspiring diver gets his first introduction to the natural phenomena, which make diving the taxing complicated craft that it is. The recompression chamber is both a training device and an instrument which enables the staff of the school to determine a man's suitability for diving. To watch his reaction to pressure under controlled conditions, the recompression chamber can duplicate the intense pressures a diver encounters on the bottom, where his body may be subjected to pressures three or five times that to which he is accustomed on the surface. These young men are going to receive a graphic demonstration of what such pressures can mean to the unwary. An ordinary tin can, which has been sealed at surface pressure, is hung in the chamber to demonstrate the consequences of taking a closed air space into the ocean depths. There are potential closed air spaces within the human body, the ear canals and the sinuses. Here, the instructor demonstrates the technique for equalizing the pressure within those areas of the body with that of the surrounding environment. Pressure is increased gradually, simulating descent beneath the water. Because the men are breathing, the air in their bodies equalizes the pressure. It's different with that sealed tin can. This happened at the equivalent of 30 feet, something to think about for a man who will someday be descending to depths of 150 feet and more. Here is one group of students, which will set about its studies with a real incentive to learn. The students are next taken on a tour of the school. As here they learn that while there is adventure and glamor to diving, there is also a lot of hard work. To qualify as a diver, the student must learn to perform many jobs underwater that take skill on dry land. For instance, tying knots in pitch blackness, wearing heavy diving mitts. The diver must be, among other things, an accomplished welder. He begins by learning the techniques of normal surface welding, a skill which other men may spend months or years to acquire and which they make their soul life's work. The diving student will find the techniques of underwater cutting and welding similar to those of the surface, with the difference that down there every job is going to take him five times as long. The diver is a jack of all trades. Welder, carpenter, mechanic, all rolled into one. He must become familiar with a variety of commercial power tools which have been adapted for underwater work, such as these pneumatic drills and saws. He must also be an explosives expert at home with such items as blasting machines, plastic explosives, gelatin dynamite, and TNT. More than 40 hours of the Army Divers course is devoted to demonstrations and practical exercises in the safe handling of underwater explosives and the techniques of underwater demolition. This is a problem which, to the uninitiated, may seem like being asked to build fires in a bathtub. All divers perform a certain amount of demolition work. But for the military diver, this skill is particularly essential. Rivers, harbors, and other navigation channels are almost invariably blocked by a wartime enemy. The outcome of a vast military operation may depend on the speed with which a handful of military divers can demolish or remove such obstruction. Stand by, fire in the hole. With its numerous port facilities on the James River, the Army Transportation School at Fort Eustis is an ideal place for the training of divers. Divers operate from many different types of vessels. They must become familiar with the ships from which they will work, as well as with the problems they may encounter on the bottom. To salvage ships, a diver must know them thoroughly. The problem of finding your way around on a strange vessel is greatly complicated if the vessel happens to be lying on its side at the bottom of a harbor. Divers' training is in progress at various levels. Novices have opportunities to study the work of both their own instructors and students who have already embarked on more advanced aspects of the training. The students' first dive will be made not in the river, but the school's specially constructed 30-foot tank. There are portholes around the bottom of this tank through which the diver can be watched, the convenience for the instructors, and a safety factor for the students. For the diver, conditions inside the tank are a little different from the real thing. Before the student himself is ready to take the plunge, there is classroom work to be mastered. He must become absolutely at home in the various types of diving gear he will use. This suit is not watertight, but it does keep the body warm in moderately cold water. The diver carries his own breathing equipment in the form of two compressed air tanks and a face mask. There are diving suits for various depths and operations. Part of the diver's skill is knowing how to select his equipment. As the student now begins to learn, the type of suit he wears for a given operation will depend on more than the depth of the water. You make your selection according to the type of work to be done, how long you expect to be underwater, and according to the climate. The suit which works fine in the Panama Canal Zone may leave something to be desired in the icy waters of Alaska. This is a lightweight dress used for searching underwater or performing minor tasks at relatively shallow depths. Deep sea diving is usually considered to be anything deeper than 36 feet and may exceed 250 to 300 feet. These men are hoping to graduate with the rating of salvage diver, allowing them to perform work to a depth of 90 feet. Even there, however, they will encounter pressures nearly three times normal and their lives may depend on their ability to handle their deep sea equipment. Before he can become a diver, the student must know his diver's dress inside and out. He must be able to wear it himself and he must also be a qualified diver's tender. Diving suits are waterproof and airtight. From the moment the diver is dressed and his faceplate sealed, he is entirely dependent on the skill of his two tenders. The instructors at the school keep a watchful eye on every detail of the student's work, for they know that during his career as a diver, each man's life may depend on his having learned the procedures so well they become second nature. At long last, the student is deemed ready to enter the 30 foot tank. Make his first dive. Getting underwater and staying there is itself a test of diving skill. Despite his 40 pound shoes, 84 pound belt, 54 pound breastplate and hat, as the diver calls his helmet, he may float like a cork if he fails to control the flow of air into his suit. After making sure everything is in order, the diver with his suit inflated swims to the descending line. He keeps his legs locked around the line, regulating his descent by how long it takes him to equalize pressure in his body with that in the water around him. Too fast a descent might result in ruptured eardrums or other serious consequences. The maximum rate of descent is usually about 75 feet a minute. Pressure against his eardrums tells him that he has gone down too fast. He pauses, rises a few feet and waits. Putting to good advantage the lessons he learned in the recompression chamber. From the bottom, he regulates the air-exhaust valve of his suit to adjust himself to the surrounding pressure, making his body more buoyant or less buoyant, depending on the job he's about to perform. Much of a diver's underwater work consists of searching for sunken objects and lost articles. He must learn the technique of doing this, using his so-called distant line to keep track of his progress as he sweeps around in a circle on the bottom. The diver's life is now literally in the hands of the tenders on the surface who control his air supply and lifeline, stand by for emergencies. They also send down the tools he needs for his underwater work. This is an exercise in oxy arc cutting. The student must operate a cutting torch with sufficient skill to slice through a half-inch sheet of steel. The instructor arrives for a first-hand inspection and approves the job with a wrap on the head. In this weighted bag are several boards with which the student next teaches himself an important lesson about working underwater. He is going to build a wooden box down here, he hopes. The trouble with wood is it floats. Hold on, some help coming down. Lesson number one. Even a simple task like nailing together a wooden box becomes a job for an expert on the bottom. The instructor comes down to offer a few pointers on how to handle buoyant objects when doing a job underwater. The purpose of this exercise is not to show the student how to build boxes underwater, but to impress upon him that down here, you don't just lay things down and expect to find them waiting for you later. When the student demonstrates to his instructor's satisfaction that he is at home under the water, he is ready for the final stage of his instruction. He will now move on from the tank to actual operations under the waters of the nearby James River. Up to now, the student has dived and performed his underwater work under ideal conditions, conditions made possible by the school's 30-foot tank. He has learned to work with his tenders on the surface and acquired confidence both in them and in himself. Like a fish out of water, the diver is virtually helpless on the surface, weighted down by his heavy belt and shoes and by his helmet, which by now, of course, our student would never call anything but a hat. As he goes down into the James River, the new diver discovers that normal diving conditions are frequently anything but ID. Lowered to the water by his diving stage, the diver swims to the descending line. He goes down into inky darkness, mud stirred up from the river bottom, making visibility impossible. Down below is a sunken vehicle, which the diver must prepare for salvage. Topside, his friends and instructors watch and wait. The tender keeps careful check on the air compressor. And a fellow diver stands by for emergencies. Take a strain on the line. Okay, Charlie, blow up to the surface and move to your stage. Stand by to come up. Coming up. The rigging job is successful. This young man, who 17 weeks ago had never been under the water, is now a qualified salvage diver, a fledgling member of one of the highest paid trades in the world. Here she comes and with her, the student's rating. He will go on now to perform actual work in ports and harbors to progress in his craft until someday he receives the designation master diver qualified to probe any ocean depth human ingenuity can reach. To become a diver, a man must have some remarkable mental and physical qualifications. A diver is alone underwater. Against the dangers he meets, he has only his diver's gear, his technical knowledge, and his common sense to helping. Army divers are relatively few in number, but they're a proud service and they've a right to be proud. This is Sergeant Stuart Queen, your host for The Big Picture. The Big Picture is a weekly television report to the nation on the activities of the Army at home and overseas. Produced by the Army Pictorial Center. Presented by the United States Army in cooperation with this station.