Hallo Du!
Bevor du loslegst den Talk zu transkribieren, sieh dir bitte noch einmal unseren Style Guide an: https://wiki.c3subtitles.de/de:styleguide. Solltest du Fragen haben, dann kannst du uns gerne direkt fragen oder unter https://webirc.hackint.org/#irc://hackint.org/#subtitles erreichen.
Bitte vergiss nicht deinen Fortschritt im Fortschrittsbalken auf der Seite des Talks einzutragen.
Vielen Dank für dein Engagement!

Hey you!
Prior to transcribing, please look at your style guide: https://wiki.c3subtitles.de/en:styleguide. If you have some questions you can either ask us personally or write us at https://webirc.hackint.org/#irc://hackint.org/#subtitles.
Please don't forget to mark your progress in the progress bar at the talk's website.
Thank you very much for your commitment!

========================================================================



 Hey our next talk is going to take a look at what you can do wrong. If you're using secret crypto primitives but don't use them the right way. And what you can possibly do about that by writing formal proofs. So to tell you more about that we have Florian and Lucas a warm round of applause please. APPLAUSE So good morning and thank you for waking up. It's a great honor for us to give this talk especially in the slots directly afterD.B. and Daniel enough. Before we start I want to mention two points which might not be clear in the talk. The first one is we like provable security and ordered gold. Is a great cryptographer. And this talk should not be around the organization as as follows will give a sharp motivation while you want to have proofs of security and then will show how to do them and the next and the latest two points will be on strange stuff happens if you use provable security anyone from the most clueless amateur to the best cryptographer can create an algorithm that he himself can break. It's not even hot. This code by Bruce Schneier shows a little bit why you want to have proof of security. Just because you look on your own scheme and you don't find the flaw It does not mean that it's not there and a strict mathematical proof can handle this problem. But it's not that easy. And you should be aware of the boundaries of proof systems. I am sure you know this example. The electronic code mode is an encryption scheme where you take blocks of a plaintext and you encrypt each block on its own and it's secure in the meaning that each block looks random compared to the plaintext but in the end that's maybe not what you mean by a secure encryption scheme a more complex example is the CBC or a safer blog changing mode here. You see that you have blocks of ciphertext and of plaintext and in the decryption step. And I use mine yeah. You use the ciphertext from one block and XOR it to the description of another ciphertext block to get the plaintext. And for a deep
er insight into this protocol you cannot watch the talk on TRL s one point three by no parts. Well so this small problem of this. But before I need to introduce so-called oracles oracles are a way to formulate that you have some practical party which takes a well-defined input and answers with a well-defined output and it's typically used to perform operations that the parties themselves can't handle. And if you introduce a special so-called padding oracle to the to this CPC mode which takes a ciphertext and answers you. If the padding of the plaintext is correct which means that sorry it s it ends with either a one byte or two two bytes or three three bytes just entering an Oracle which tells you this information is enough to break the complete ciphertext because you now can just guess one byte after another which is much more efficient than breaking the complete cipher. And watch out. So to understand the security of the system you need to understand what problem you have and what definition of security you want to have. And then you can go there and prove that your system is secure. But unfortunately you won't be able to prove it without taking assumptions. You might know about the P words and p problem and you get that you can get quite rich by solving it if you have a ciphertext as his neck and neck and encryption scheme and you prove that it's secure in the sense that given an encryption of something you can't tell that this is an encryption of a zero. And you can prove this without taking additional assumptions than you would have shown an example of a problem which is ina. Because given the secret key it's easy to do this you uh decrypt it and then you know if it's a zero or not but it's hard to do without. And then you would have found an example where p and and P is different which make you quite rich and famous but it's not that plausible that you find it just uh on the way of proving the security of your scheme. So we have to do some assumptions and floa
t them and now tell you about some of these. OK. Good morning everyone. Now many of you may have seen RSA and I have just written down the short version of it on the slides. Let me check here. It's quite commonly known that you have two very big primes p and q you multiply them and get a very big integer n and you also take some exponent that we will trust center three in this example. And this is all you need for a public key. And then there is some more complicated way to compute the secret key. And once you have these values encrypting stuff is as simple as taking the plaintext and taking it to the power of E or in our case three and doing that modulo and modulo in case you don't remember. If you do division with the remainder you throw away the quotient and keep the remainder. And that's what we call a modulus. So almost all examples that we will show will have some modulus in them. And in this case encryption as you see it's not really complicated and decryption you take the secret key as the exponent and for some reasons that we won't go into in this talk. This actually works out to give you back the original plaintext and there is this common misconception that RSA is secure of factoring is secure. That's not really the case. The assumption that RSA uses is the so-called RSA assumption and it is roughly equivalent to the following. It's impractical if you. I give you a public key and some ciphertext that was created with the public leave of random plaintext for you to fully extract that plaintext. It sounds a little bit like RSA is secure because RSA is secure and actually that's getting quite close. Except that we have the problem that this version of RSA is not even really secure for sensible security definitions because just being unable to extract the plaintext from a ciphertext doesn't mean that there are no practical attacks on it. If you're only able to extract half the plaintext and you know that's the it's that it contains ASCII text that says either
 yes or no. And I give you the first bite of it. You can pretty much guess what's the other bytes might be. And there are many other problems with RSA in their shape. For example if you want to encrypt a small number of 23 you take 23 to the power of three modulo some really huge number 23 to a three is twelve thousand one hundred sixty seven that's way way smaller than though then. And so you can simply throw the cube you create cube root edit and you get the plant expect that's an efficient operation and one of the reasons why you should nicely use RSA RSA. Now you might say I'm not going to encrypt my plane takes off RSA directly anyways I'm going to use hybrid encryption where I just encrypt a secret key for a symmetric scheme with RSA and then encrypt the message with these symmetric scheme because it's way more efficient and it is indeed what you would usually do in reality. But think about it. Let's be generous and say you're using 256 keep it's for some secure version of a s and you are quite daring and use only 1024 bits of ours a key 256 times three is still a lot smaller than 1024. So this text perfectly works there. And this means that you really have to be careful with RSA and also it's a deterministic scheme. If you have an idea what's the plaintext might be. You can simply encrypted. After all it's a public key encryption scheme. And check if the result matches. So the long story short version here is using RSA is not trivial. They are secure versions of RSA or versions that we believe to be secure but they are a lot more complicated than what you're usually shown. And for example none of that for none of them. The often claimed case of encrypted signing is encrypting with the secret key doesn't work that statement that signing is encrypting with the secret key is not to my knowledge true for any secure scheme in either direction. Now RSA is not the only thing that has its issues and we will later look at El-Gamal which is a very great encryption sche
me. But even there if you don't pay close attention you might end up leaking plaintext bits and a single plaintext bit can be disastrous in certain circumstances. Imagine you're doing an election and you encrypt your yes or no vote. If I learn one bit about the plaintext I learn everything. And another example where people often have wrong ideas with hashes. Yes it is true. If you take some random input from a big set and you throw it through a hash it's impractical to learn a premium for that hash. But if the original set from which your play pretty much comes small. You can simply brute force it and I've heard this several times where people made this claim. Maybe they knew it but they didn't say so. The result is of course that you get vulnerabilities everywhere now we need though one of the issues that we saw in RSA with this Rs assumption was that we need some proper definition of what security actually means and a rather old notion that is not without problems but is a good first idea is called semantic security. And what you see on the slides is a simplified version in the sense that it uses regular language instead of very compute complicated formulas but it gives you the chills the gist of all the ideas. If I give you a public key and a cipher text you should not be able to learn anything about the content plaintext except for its length. If this is true for an encryption scheme then reconsider that scheme secure in a sense to provide Symantec security the issue with this is it's not really that simple to prove that for schemes even if you use proper assumptions. So there is another notion and that is called in CPA that is short for undistinguished ability under chosen plaintext of texts. Again this is the colloquial version of it but it boils down to if I give you a public key and you are the attacker and you are now allowed to choose to play in texts can be anything as long as they have the same length you give both of them to me. I pick a random one I wi
ll encrypted with the public key and give you the ciphertext. You should not be able to distinguish which plaintext that you gave me I encrypted. Better than just making random guesses or at least substantially better. There is always the chance that you just by pure chance guess the secret key correctly. We don't worry about that but anything that is substantially better than guessing is a real issue and we end. The nice thing is at some point some people went through the trouble of proving that those two notions are secure are equivalent and thus if you proof in CPA security you have proven Symantec security. But again Symantec security is just one definition of security and it is not necessarily a sufficient one for what you want. We mentioned the CBC mode in the beginning where you could hats were able to fully decrypt some plaintext using a padding oracle CBC mode provide Symantec security. It's simply that they attack this. The padding oracle is not part of the definition of Symantec security and thus the attack happens outside of the security model. So it's really important that you choose a good and appropriate security model. I believe we have a couple of more examples where this will come up and very notable one that we won't talk about anymore and this talk. Our side channel texts if you are capable of learning the secret key by just looking at the network stream and take a stopwatch. The encryption scheme can be as good as you want. It won't help you if that is the way you get the key and that's where why and implementing cryptography is so hard because you have to take care of all these problems. Also just because a scheme is secure on its own that doesn't mean that is a secure. If you combine it with other schemes and finding a proper definition of security can sometimes be the hardest problem of all in cryptography. There are actually cases where it's easier to come up with your solution to a problem than with a property finishing off what secure mean
s now. That being said let's look at how we do the proofs we are doing so-called redactions as Luke has already explained. We can't cannot do absolute proof that don't need assumptions because there is this millennium problem in the way. So we need some assumption for a heart problem and this is usually defined as some kind of game where you have a challenger in this case. We call this the assumption challenger. That gives us some kind of challenge. For example the challenge where he says here is an Ares a public key in a ciphertext. Give me the plaintext and we then have some kind of translator and we have the an attacker on our team that we want to proof as secure. So for example this might be an attacker on the CPA security of an encryption scheme and it will take again some kind of public key and play some kind of security game. And the translator now has to task to translate the challenge that it received from the assumption challenger into something that the attacker on the scheme that we want to proof and secure can use to attack that scheme if it is capable of attacking the scheme and then translates the result of that attack back into something that's the origin assumption challenger would accept as a brake on the assumption. And since we believe that there is no way to break the assumption and be demonstrated that breaking our scheme breaks this also implies an attack against the assumption we believe that is impractical to break our scheme we will now look at for example where this will maybe get a little bit more clear. And for that we will look at a encryption scheme called Gamma which unlike RSA is secure out of the box at least in a sense of Symantec security again we start with two big primes p and q but this time they are required to have a special property p has to be twice Q plus 1. So they are closely related primes and we also call P safe prime and Q US official more prime. And the reason of this is we won't go into here. You also need to take s
omething called a generator and we just pick four because that always works. If you pick a bet generator. This is actually the case that I mentioned in the beginning where you leak plaintext bits and we will now do several operations of those. We have some operations between elements where we multiply based elements. Those are all modulo P. So the lowercase here and we have exponents in the game. And those are modulo Q And for reasons that you can learn about in our group theory. University lecturer this makes actually sense and foreign attentional purposes the set of all interests between zero and q minus one we will call set Q Now in order to use gamma we need. We assume we have those antitrust P and Q They don't need to be secret or anything they can even be standardized and usually or very often they actually are. And the kitchen narrator will now sample a random exponent X from that Q and this is the secret key. Then he or she will take the generator chief and compute she to the power of x. So again this is modulo P so this number one girl completely out of proportion. But what. Yeah. The result is the publicly you already see here. This operation this cheetah the X is probably hard to reverse. So you can't undo this to get signature scheme out of this and that's everything you need to do for ki generation which is much easier than finding two primes for RSA encryption is a little bit more complicated but also doable. You pick another random integer. Ah this is your encryption randomness of what's the attack of looking of trying to encrypt some assume plaintext and checking whether they match because every time you encrypt you use a different value ah and then you compute cheetah they are first. This is your first part of your ciphertext then you take the public key. She took the x and compute it to the path R and by the roots of how powers work. She took the x to the are is equal to she to the x times are and that you multiply simply if the plaintext those two
 elements are now your complete ciphertext and that is everything you have to do for encryption and finally decryption you take the second part of the ciphertext here. So this cheetah the X are times M and the idea is now that you remove this cheetah the X are. And for that you take the cheetah the R and compute it to the power of x and again roots of power Xi to the R to the X is Cheetah the r x. And if you now do this to the minus 1 you get Xi to the minus r x Xi to the minus r x times she truly R X is Xi to the R X minus r x. This is Cheetah the 0 which is 1. So it's you just have to plaintext left here and you're done with the decryption and that's all there is to the scheme. So it's not really that hard. Now we still need an assumption relative to which we will prove that El-Gamal is secure and for that we will use the decisional. If you have an assumption it says that if you take three random exponents it is not you are not able. You're not going to be able to tell but I give you a triple that consists of cheater X she to the Y. She does the set or off it or triple that consists of cheater X cheater Devi and cheat the x y. We won't argue why this is true there is some good rationale why we might believe that but this is an assumption. So we don't have to prove it. We just have to assume it and then prove that our scheme is secure. If this assumption holds and for that we are going to use the game structure that future that I showed you before that and this is the full game. So at a start you see the t the H cha cha passes some triple to the translator and at the end the translator outputs a BP that tells the translators assumption better set. In this case is equal to X times Y. So you have this game on the left side on the right side. You have to in CPA game so you have in the start you give public key. So for this you use cheater the X to the El-Gamal attacker then the attacker will hand out to possible plaintext M0 and then one and a translator. Now select o
ne at random for that he picks a random bit B andM.B. will from now on be selected plaintext you then take a stand takes the second part of the provider's triple cheetah Devi and uses that in place of cheetah the R. So that's the first part of the ciphertext and it takes cheetah to set in place of cheetah the R eggs. So the second part of the ciphertext except for the plaintext which we let it afterwords. So you see here this has basically the structure of an egg Ma ciphertext and then you let the attacker guess it can now do pretty much what it wants. As long as it doesn't run extraordinarily long and at the end it will output an assumption P dash about which plaintext was encrypted. The translator then trust checks whether the assumption is correct and outputs the bit better it is correct to the challenger. It might not be completely obvious at this point VI. This is a proof but let us consider the different cases. Let's say the attacker has a success rate of 1 1/2 plus epsilon 1 half is the probability that you would get by just random guessing. So if the attacker is better than just random guessing there has to be some additional code so-called adversarial advantage. Epsilon and we just assume that it is positive. Now if X times Y is equal to set which is the case 50 percent of the time then this is a perfect simulation of the real NCP game because the public key cheater reacts as a completely random element so perfectly indistinguishable she to divide perfect indistinguishable. Also random she truly set is in that case by definition equal to x to cheat the X times Y. So again perfect simulation and we simply get the success probability of the attacker. In that case and yeah so that's fine. Otherwise however she to the set is not in any kind of correlation to cheat you X and she truly y and as such it is also this plane this ciphertext won't be in any correlation with to either of the plaintext with overwhelming probability. So it's only possible to get a succes
s rate of one half for the attacker and since either of these have a probability of of occurance of one half we simply compute the mean value of those and that happens to be one half plus epsilon half. Therefore if there is an attacker against the semantic security already in CPA security of eg I. We just converted it into an attacker on DDD H assumption with success probability 1 1/2 plus epsilon half if Epsilon is non negligible. Then the definition of negligible implies that Epsilon half is also non negligible. And since we believe that there is no attacker on the Didi H assumption that has not negligible advantage we conclude that there is also no attacker on the security of the El-Gamal scheme that has non negligible advantage. It follows that Gamma is in a secure and thus provides Symantec security and of proof now you might say yeah but what did we gain off that we could replace the assumption that encryption scheme is secure with an assumption that is also quite weird. Well first of all the assumption is a little bit less complex though in that case the difference is not that huge. But this is an image of the old version of the Teal as handshake as you see you probably see nothing because it is too complicated to properly fit on the slide which is the entire point I'm trying to make here. These kinds of proofs allow you to take a complex scheme and reduce it to the security of some small simple well understood assumption and you can also share this assumption. There are many cryptographic schemes that can be can be reduced to NCP to D to the H assumption and that way all everyone who wants to try to break the schemes can simply try to break the H assumption and either all schemes are broken or none of them. But we have something that we can very well concentrate on. If you visited the post quantum crypto talk yesterday Tanya and Steve should were complaining about all those proposals for the post quantum schemes and said it was impossible to refute them all.
 This is what allows us to review all those new cryptographic schemes that are not only encryption schemes because everyone just has to look at very few assumptions and you also avoid problems from weird interactions. If you have multiple assumptions. This was not the case right now. But in reality you use several primitives. And even if those are secure on their own they might not be if you combine them with others and approve. Now gives you the certainty that my scheme is secure as long as all of those are secure. I didn't introduce issues from combining them which is also very valuable now back to the definition of security and the problems there are now in this case. Not really that much of a problem. What you just saw is a so-called game based proof. I mean you saw the game. So it's rather intuitive why it's called that way. And those are generally speaking easier to do than the alternative. Exceptions exist but they often have a less intuitive meaning. For example I told you that rough definition of in CPA and semantic security in CPA was comparatively weird and technical where as semantic security was pretty straight to the point. And that is often an issue that still is game based definitions have they are very technical and it's harder to get an intuitive idea of what they really mean. Also the more complex your protocols get. And for example if you want to design cryptographic voting schemes the less these proofs scale at some point you need to switch to the alternative which are so-called simulation based proofs for those you define some ideal functionality. So imagine it as a trusted party that just falls from the sky and is perfectly trustworthy. You define whatever you want to do is done by the party and then assume that everyone has perfectly secure connections to that party and improve that your real protocol is as secure as this idealized thing. Those proofs tend to get more intuitive meanings semantic security is a simulation based on the definitio
n of security. And as I said it's a lot easier to understand what it means but they're also usually a bit harder to do. Also especially one of them though that may be because the schemes that you will usually proof of that a complicated you can get something called proof artefacts. That's where you need some very weird thing in your cryptographic scheme that doesn't appear to serve any purpose. For example you suddenly have ciphertext in some place for a public key and nobody ever has a secret key for the public key and that may sound very weird and pointless and sometimes it may be sometimes actually does serve a purpose or just because something looks weird doesn't mean that it is unnecessary but maybe sometimes to this. And that's one of the big issues we face there. Now in the start I mentioned RSA and assets there are secure versions of it and there is the case however they require something a bit more complicated. And one of the things they used to acquire security are hash functions and hash functions are pretty much functions where you can throw in some random at some string of some length and get out a random looking bit strings of fixed length independently of how long the string that you throw in us. And I say random looking because the proper definitions of what a secure hash function is are shockingly complicated. You can ask me after the lecture if you want but it's very very easy to get them wrong especially since they appear to be so easy. Now Lucas will now tell us how these hash functions are used or how some of the issues that we face lift them because the RSA proofs are not really in the Standard Model. Instead they use something else. Yes. Well if you want to model a hash function in our proofs and we want to get rid of all these strange properties of hash functions we use something called random Oracle which is in fact this dwarf and this dwarf lives in the box and he has a dice and a book. And if someone comes to the box and wants to have a ha
sh for a specific message he looks into his book and wants to check out if you already answered such an message. And if he did then he answers in the same way as he did before and otherwise he rolls his eyes and gets a new random value which is now the hash of this message. Unfortunately no one has ever found such a box with a dwarf. And furthermore it would be quite difficult to handle because every time you want to compute a hash you would have to go to the dwarf but the biggest problem is that this is not a valid abstraction and I'll show you what the problem is. Let's assume that we have a secure encryption scheme and let age be either a hash function or a random Oracle then we simply reuse the generation algorithm which gives us a keep out for a new encryption scheme and we partly reuse the encryption. I grew rhythm and modified like this. We check is the message valid code. Note that a code execution attack is not the problem here. We simply look at it. Is it a valid code. We take random input x and evaluate the code. Given this random input and if the result of the code is different than what h tells us then we use our secure encryption scheme. But if it's the same we use are a secret keep as the ciphertext. This might sound very weird. Yes. You should not do this in a real encryption scheme. But here we can see that this scheme is secure. If we use a random Oracle but insecure for any instantiation with a hash function. If we use a random Oracle the probability of the dwarf to get the same output as the given code is negligible because it's randomly chosen but for a real hash function you simply can put in the code of hash function and it will of course be evaluated to the same result as the hash function. And then you'll always get the secret key. So the random Oracle allows us to prove schemes which are obviously insecure the office who fried the first paper on this came to some harsh statements. It should be clear that the random Oracle mythology is not s
ound. That is the mere fact that a scheme is secure and the random Oracle model cannot be taken as evidence or indication to their security. And furthermore he said. Indeed what happens with a random Oracle model reminds us of the Bible story of the bronze serpent. This story illustrates the process by which a good thing may become a fetish and what you should do in such a case. Spoiler alert The snake had to be destroyed. But if you need to cite the Bible as a cryptographer your point maybe is not as good estimate. Might think other awful authors said that if one of the world's leading specialists put forth his best effort to undermine the validity of the random Oracle assumption and if the flawed construction is the best he can do then perhaps there's more reason than ever to have confidence in the random Oracle model so you see that even in the scientific community this model is it's not what what to do with it because it's widely used improves and there are schemes that can only be proven in the random ARPA model. And they seem to be secure but obviously as you saw the random market model allows altered to prove the security of insecure protocols. So people try to get rid of it they invented signature schemes which don't use the random Oracle model but some the strange stuff appeared. This w signature key selection attack is an attack which is also out of model for the typical definition of the security of signature schemes and it allows that given a signature and a message under some public key you could be able to find a new key power such that the signature is valid under your new generated key for the same message. And maybe that's not a problem in your specific use case but you should really be aware that this could happen if you use this kind of signature signatures. Another example the bullet point signatures were derived from another signature scheme. But suddenly the signatures get much more complicated here in the easy one. You have just one group elem
ent in the complex one you have to. And the second one is quite difficult to calculate and the probability that a programmer will do some mistakes by implementing it is much higher than in the easy scheme. And then the question is is this worth the effort. Do we want to have schemes which are secure without using this unsound model or do we want to have the easy ones so you might have noticed that we get a little bit deeper in the beauty of proving brand fuck and for the next step. I'll introduce another cryptographic tool which is called commitment skills commitment scheme works like this. The party Ellis has a message. And she wants to tell Bob that she knows that that she's choosing the message but not telling the message to Bob. You can imagine it like having a safe writing the message on a piece of paper put it into the safe lock it and give the safety to Bob. And if you tell Bob the code for the safe then he can open it and read the message for the scheme. We have two messages. The first one is called the commitment and it should have two properties. It should be binding which means after sending the commitment Alice should not be able to manipulate the message and it should be hiding. Which means that Bob should not should not learn anything about the message given the commitment and later Alice can open this commitments which is called the anvil. In this case she simply sends the message and the random. And now Bob can calculate if this message and this random matches to the commitment given before. Well let's assume we have this secure scheme and we build a more complex protocol. Let's assume that they both want to know if the message that they've chosen is larger than the message the other one has chosen. Alice commits on em and sent the commitment to Bob. Bob it's on an other message and sends the commitment to Alice and then they open their commitments and they see who wins the game. But what happens if Alice is not interacting with Bob who is nice but w
ith an evil party. Mallory who acts like this Mallory takes the commitment C and multiplies it by the generator. Alice has used then when Alice opens the commitment Mallory can simply open this message as a commitment on trust one. That's not what we want to have. Using our commitment scheme so composing protocols together can make them insecure or can can lead to insecure protocols and what we want to have in a security definition is that the security definition should contain all imaginable properties and should be secure regardless of the context in which you use your primitive. You see that using these locks for the bike are not composed well they're not even secure to do this we use this simulation based on proofs and a special variant of it called the universal comparability model. Here we have this ideal a function of look I mentioned before and we have the real protocol and we prove that an environment which is everything outside of the protocol all computers all protocols on the Internet for example is unable to distinguish if it's interacting with the real world or with the ideal world. So we have this uh sorry that's not ideal functionality on this one. So we have here is Catholic so certified trustworthy. So we have this trustworthy authority and the parties simply put their inputs to a trustworthy authority and the authority calculates stuff and gives it back to the parties. In the ideal scenario and in the real scenario we have the parties executing our protocol but we don't have only the parties but also an adversary who can for example listen to the messages manipulate them or even corrupt parties and he interacts with the environment that so you can think about like the environment and the adversary are one party and they want to know if they are in the real scenario or in the ideal one in the ideal one. You have a so-called simulator and he tries to convince the environment that he is a real attacker but he is interacting with the ideal function wh
ich won't tell him too much on the messages the parties gave in. And now we say that a scheme is secure if for every adversary there exists a simulator such that any environment is unable to distinguish in which world it lives. How does such an idea of functionality look like we'll look at the functionality for commitments Ellis can put the message in. Then the message and the functionality tells Bob that Ellis has committed later. Ellis says unveil it. And then Bob gets the message. So now we'll try to prove such a system in this universal comparability scheme the environment using the attacker tells the corrupted sender to use this commitment. The corrupted senator could use this commitment later. He's told told to unveil he unveiled and then the receiver who is not corrupt that can answer with the message. In the ideal scenario the simulator is on the good side because he wants to confirm the diamond that he's in the real scenario and he works together with the corrupt the party. The environment tells the crap that party to use this commitment it tries to send it to the idea functionality and the ideal functionality is confused because there is no definition of to give in commitment but you want to have a message instead and you could try to extract the message from this commitment which should do the simulator but this would break the security definition of our commitment scheme. So there can't be a commitment scheme which realizes this idea of functionality. That's bad because we believe that there are secure commitment schemes. So what's the reasonable and most clear solution for this of course we could introduce a backdoor. Sorry. I mean we could introduce a common reference string a common reference string is a randomly chosen value buy from a given distribution. It's choosing honestly but exists only in the real world. So let's assume that our common reference string in this case is a public key and to generators such that the public key is chosen randomly 
and no one knows the secret key. Now Ellis can use the same commitment scheme as before for a C zero. She encrypts the message with the public key where no one knows the secret key off. She proves with some magic cryptography. That's the message in C1 and C2 is the same. And then she uses this as a commitment the simulator now you can just take the common reference ring on its own but he is not taking it from a given distributed distribution randomly but instead he uses a real key generation algorithms so he knows the secret key and he don't take random generators but he chooses them in a way such that he knows an X with G to the X is H. And now he's able to extract the message bits from the commitment and put it into the idea of functionality. So introducing this back I mean introducing the common reference string allows us to prove this scheme secure. So maybe when the NSA gave us easy the bitchy they didn't want to snoop on us but maybe they just wanted to give us a tool to provide extra stability inU.S. scenarios. Well maybe it probably they wanted a snoop as we said common references strings are basically back doors so it's quite hard to convince people that they are honestly generated. The probably most sophisticated one where people actually use complex com reference strings involves a cryptocurrency C cache where they went through quite great lengths to produce a common reference thing that is plausibly honestly generated. Of course it is indistinguishable. It must be indistinguishable. Whether that's the case with the s subtitle there is a link if you download the slides you can watch the video. It's quite interesting. In other scenarios sometimes you might get away with nothing up my sleeve numbers. For example the money other guys will tell you that they don't involve they don't they don't use anything that uses a trust set up well they use partisan commitments which are the commitments that we started out with. And for them you still need some kind of pl
ausibility that nobody knows these discrete logarithm which means that G instead H and what they did was basically they took the element she threw through it through Sha 3 and use the output f the other group element and that is indeed quite plausible that it's secure but still it is a kind of common reference string. Now all that being said let's come to the conclusions. The first one as always for these kinds of talks please don't roll your on crypto. It's extremely likely that you will get it wrong. We skipped over several details here and even if you implement managed to implement a scheme in a secure way for some security definition it still doesn't mean that your security definition is what you might want. Other than that security is difficult if you do it. Please at least employ proofs and be aware of their limitations. Also the random Oracle model may be a flawed framework but no scheme no real world scheme that has been proven secure in it has ever been broken because of the random Oracle model. So it good Eurosceptic is a lot better than nothing. So at least you that. And if your proofs are too complicated for other people to read they are not all that much worse. That's the big problem if you see proofs they are so complicated that often nobody really reads them and they are arguably therefore less convincing than random aka model proofs because those tend to be simple enough for people to understand. With all that being said we are now here for some questions and thank you very much for your attention. Is most excellent talk. We have microphones in the soil here so please line up behind them and to start it off. We have a question from the internet and can you elaborate why there is such come center much confidence in dash assumptions. The first thing is it's very people spend a lot of time looking at it and assumptions users Shirley stemmed from the idea that if we looked at it for a very long time and nobody found an attack there's a good chance it is 
secure. There is also a different argument. There is something called the generic group model and it formalizes the notion of those mathematical concepts that are used. I only showed you the very technical definition of the El-Gamal scheme. There is actually a way to view it in terms of group theory and if you do that it becomes much simpler. But you require the previous knowledge and you see how you can map it's to this generic group model and institute network group model allows you to prove that there are no generic attacks that only use the structure of the group. And there is a proof that in the generic group model the decisional if you have an assumption holds but that doesn't mean that there are no attacks on its that use non generic properties of the group. For example the reason we won't use the curves is that we believe that they are mostly equivalent to generic groups. And the reason we need so huge groups for if you want to use regular prime numbers is that they have more structure than that. So it's a very good argument but it's of course not perfect and also if you get quantum computers all bets are off. That's completely propaganda. Microphone number two please. And my question is do you think doing a proof in the random Oracle model is helpful in constructing a proof that can later be advanced to remove the random Oracle model. And does this usually happen in your experience. Well yes. Often you start by approving your scheme in the random Oracle model and then tried to get rid of it. But this you saw the results. Yes because all the results often you need to change. Duff in your protocol to get rid of the random Oracle model and this leads to complicated constructions which are difficult to implement and may introduce strange properties does that answer your question. Yes. Ben microphone to again please. What's on the next slide. Okay. That's the bonus slide a little bit on security levels. If you want I can tell. I believe you have some time left. 
There is four moments. Okay. That is enough. There is this uh you occasionally count the encounter the idea that there is that some security level is enough or insufficient or whatever. And the first thing that is maybe not trivial is that they are fundamentally different kinds of security even for the same definition. The one that most people think about is called computational security. And what that means is basically if I give the attacker a certain amount of computational power the attacker shouldn't be able to break my scheme using brute force and that's where you. Where does 128 bit comes from. Which is a level where the energy if you use somewhat realistic assumptions on hardware the pure energy consumption of going through that many steps is I believe enough to boil the oceans. So one had 28 bits on itself is pretty much sufficient. There are also certain schemes that provide statistical security which is innovative much better because in that case the question is not how much computational power does the adversary have but just how much luck does he have. And if you think about it computational power has to factor that in. If you have a one in a thousand chance to put forth certain key you sing to the one hand 28 operations you still have to factor in that factor of once in a thousand years. So these statistical security parameters can be much smaller and if you read 40 bits of statistical security that's not great but it's not as terrible as it may sound at first. And finally there perfect security which is even if you give all computational power of the world and then a lot more to the attacker and if the attacker has perfect luck he still isn't able to break it. The most popular scheme that provides status of course the onetime pet where for every possible plaintext there is the key that will encrypt the ciphertext to the plaintext. The others are completely impossible to break. And as such there is no security parameter. I think we might be able to tak
e one last question. We have another question from the Internet. No. No question from here. Well then a warm round of applause for Lucas.