Hey, our next talk is going to take a look at what you can do wrong if you're using

secure 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 Luca, so warm round of applause

please. So, good morning and thank you for waking up. It's a great honor for us to give this talk, especially in the slot directly after DJB and Tanya Lange.

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 Audit Goldreich is a great cryptographer and this talk should not be a rant. The organization is as follows, we'll give a short motivation, what you want to have,

proofs of security and then we'll show how to do them and the next, 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't break. It's not even hard. This quote by Bruce Schneier shows a little bit why you want to have provable 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'm sure you know this example. The electronic codebook mode is an encryption scheme where you take blocks of a plain text and you encrypt each block on its own and it's secure in the meaning that each block

looks random compared to the plain text but in the end that's maybe not what you mean by a secure encryption scheme.

More complex example is the CBC or cipher block chaining mode. Here you see that you have blocks of cipher text and of plain text and in the decryption step, and I use my, you use the cipher text from one block and XOR it to the decryption

of another cipher text block to get a plain text. And for a deeper insight into this protocol, you can watch the talk on TLS 1.3 by Hanno.

But we'll show a small problem of this. But before I need to introduce so-called oracles. Oracles are a way to formulate that you have some protocol 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 by themselves can't handle. And if you introduce a special so-called padding oracle to the CBC mode which takes

a cipher text and answers you if the padding of the plain text is correct which means that, sorry, it ends with either a one byte or two bytes or three bytes. Just entering an oracle which tells you this information is enough to break the complete

cipher text because you now can just guess one byte after another which is much more efficient than breaking the complete cipher in one shot. 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 versus NP problem and that you can get quite rich by solving

it if you have a cipher text, an 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. Then you would have shown an example of a problem which is in NP because given the secret key it's easy to do this.

You 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 NP is different which make you quite rich and famous. But it's not that plausible that you find it just on the way of proving the security

of your scheme. So we have to do some assumptions and Florian will now tell you about some of these. Okay, good morning everyone. Now, many of you may have seen RSA and I've just written down a 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 just set to 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 plain text and taking it to the power of E, so in our case three.

And doing that modulo N. Modulo in case you don't remember. If you do division with remainder, you throw away the quotient and keep the remainder and that's what we call 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 plain text. And there is this common misconception that RSA is secure if 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 I give you a public key and some ciphertext that was created with the public key with a random plain text for you to fully extract that plain text.

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 plain text from a ciphertext doesn't mean

that there are no practical attacks on it. If you're only able to extract half the plain text and you know that it contains ASCII text that says either yes or no and I give you the first byte of it, you can pretty much guess what the other bytes might be.

And there are many other problems with RSA in that shape. For example, if you want to encrypt small numbers, 23, you take 23 to the power of three, modulo some really huge number. 23 to a three is 12,167.

That's way, way smaller than n. So you can simply throw the cube root at it and you get the plain text back. That's an efficient operation and one of the reasons why you should naively use RSA. Now you might say I'm not going to encrypt my plain text with 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 the symmetric scheme because that'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 key bits for some secure version of AES and you are quite daring and use only 1024 bits of RSA key. 256 times three is still a lot smaller than 1024.

So this attack 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 the plain text might be, you can simply encrypt it. 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. There 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, for none of them the often claimed case of

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 scheme 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 is 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 pre-image for that hash. But if the original set from which your pre-image comes is small

you can simply brute force it. And I've heard this several times where people made this claim maybe they even knew it but they didn't say so. The result is of course that you get vulnerabilities everywhere. Now we need, so one of the issues that we saw in RSA with this RSA 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 complicated formulas but it gives you the gist of what the idea is. If I give you a public key and a ciphertext you should not be able to learn anything about the contained plaintext except for its length. If this is true for an encryption scheme

then we consider that scheme secure in the sense that it provides semantic 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 indistinguishability under chosen plaintext attacks.

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 two plaintexts can be anything as long as they have the same length.

You give both of them to me I pick a random one I will encrypt it 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's always the chance that you just by pure chance

guessed the secret key correctly. We don't worry about that but anything that is substantially better than guessing is a real issue. And the nice thing is at some point some people went through the trouble of proving that those two notions are equivalent and thus if you prove in CPA security

you have proven semantic security. But again semantic 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 were able to fully decrypt some plaintext using a padding oracle.

CBC mode provides semantic security. It's simply that the attack, the padding oracle is not part of the definition of semantic 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 a very notable one that we won't talk about anymore in this talk are side channel attacks. 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 a key. And that's why 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 it is 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 proper definition of what secure means.

Now, that being said, let's look at how we do the proofs. We are doing so-called reductions. As Lukas already explained, we cannot do absolute proofs that don't need assumptions because there is this millennium problem in the way. So we need some assumption for a hard 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 RSA public key and a cipher text, give me the plain text.

And we then have some kind of translator, and we have an attacker on our scheme that we want to prove as secure. So for example, this might be an attacker on the in-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 the task to translate the challenge that it received from the assumption challenger into something that the attacker on the scheme that we want to prove as secure can use to attack that scheme

if it is capable of attacking the scheme, and then translate the result of that attack back into something that the original assumption challenger would accept as a break of the assumption. And since we believe that there is no way to break the assumption, and we demonstrated that breaking our scheme also implies

an attack against the assumption, we believe that it is impractical to break our scheme. We will now look at a full example where this will maybe get a little bit more clear. And for that, we will look at an encryption scheme called ElGamal, which, unlike RSA, is secure out of the box,

at least in a sense of semantic 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 one, so they are closely related primes, and we also call P a safe prime and Q a sufficient mod prime.

And the reason of this, we won't go into here. You also need to take something called a generator, and we just pick four because that always works. If you pick a bad 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 base elements. Those are all modulo P, so the lower case here. And we have exponents in the game, and those are modulo Q. And for reasons that you can learn about in a group theory university lecture,

this makes actually sense. And for notational purposes, the set of all integers between zero and Q minus one we will call set Q. Now, in order to use ElGamal, we assume we have those integers 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 key generator will now sample a random exponent X from set Q, and this is the secret key. Then he or she will take the generator G and compute G to the power of X.

So again, this is modulo P, so this number won't grow completely out of proportion, but the result is the public key. You already see here this operation, this G to the X, is probably hard to reverse, so you can't undo this to get a signature scheme out of this.

And that's everything you need to do for key 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 R. This is your encryption randomness. This avoids the attack of trying to encrypt some assumed plaintext

and checking whether they match, because every time you encrypt, you use a different value R. And then you compute G to the R first. This is your first part of your ciphertext. Then you take the public key, G to the X, and compute it to the power of R.

And by the rules of how powers work, G to the X to the R is equal to G to the X times R. And that you multiply simply with the plaintext M. 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 G to the X, R times M. And the idea is now that you remove this G to the X, R. And for that, you take the G to the R and compute it to the power of X. And again, rules of power. G to the R to the X is G to the RX.

And if you now do this to the minus one, you get G to the minus RX. G to the minus RX times G to the RX is G to the RX minus RX. This is G to the zero, which is one. So you just have the 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 Elgamal is secure. And for that, we will use the decisional Diffie-Hellman assumption. It says that if you take three random exponents, you're not going to be able to tell

whether I give you a triple that consists out of G to the X, G to the Y, G to the Z, or a triple that consists of G to the X, G to the Y, and G to the XY. 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 I showed you before that. And this is the full game. So at the start, you see, the DDH structure passes some triple to the translator.

And at the end, the translator outputs a bit B that tells the translator's assumption whether Z in this case is equal to X times Y. So you have this game on the left side. On the right side, you have the in-CPA game. So you have in the start, you give a public key.

So for this, you use G to the X to the Elgamal attacker. Then the attacker will hand out two possible plaintexts, M0 and M1. And the translator now selects one at random. For that, he picks a random bit B, and MB will from now on be the selected plaintext.

It then takes the second part of the provided triple, G to the Y, and uses that in place of G to the R. So that's the first part of the ciphertext. And it takes G to the Z in place of G to the RX. So the second part of the ciphertext, except for the plaintext, which we let afterwards.

So you see here, this has basically the structure of an Elgamal 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 B dash about which plaintext was encrypted.

The translator then just checks whether the assumption is correct and outputs the bit whether it is correct to the challenger. It might not be completely obvious at this point why this is a proof. But let's consider the different cases. Let's say the attacker has a success rate of one half plus epsilon.

One 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 so-called adversarial advantage epsilon. And we just assume that it is positive.

Now, if X times Y is equal to Z, which is the case 50 percent of the time, then this is a perfect simulation of the real NCPA game. Because the public key, G to the X, is a completely random element. So perfectly indistinguishable. G to the Y, perfect indistinguishability, also random.

G to the Z is in that case, by definition, equal to G to 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, G to the Z is not in any kind of correlation

to G to the X and G to the Y. And as such, this ciphertext won't be in any correlation to either of the plaintexts with overwhelming probability. So it's only possible to get a success rate of one half for the attacker.

And since either of these have a probability of occurring 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

or the NCPA security of El Gamal, we just converted it into an attacker on the DDH assumption with success probability one half 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 DDH assumption

that has non-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 El Gamal is NCPA secure and thus provides semantic security.

End of proof. Now, you might say, yeah, but what did we gain of that? We replaced the assumption that the 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 TLS handshake. As you see, you probably see nothing because it is too complicated to probably 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 reduced to the DDH assumption, and that way, everyone who wants to try to break the schemes can simply try to break the DDH 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 DJB were complaining about all those proposals for the post-quantum schemes, and that it was impossible to review them all. This is what allows 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 the proof 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, 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 the rough definition of in-CPA and semantic security. In-CPA was comparatively weird and technical, whereas semantic security was pretty straight to the point,

and that is often an issue that those 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 then prove 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 definition of security,

and as I said, it's a lot easier to understand what it means, but they are also usually a bit harder to do. Also, especially with them, though that may be because the schemes that you will usually prove with them are more complicated, you can get something called proof artifacts. 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 a ciphertext in some place for a public key, and nobody ever has a secret key for that public key, and that may sound very weird and pointless, and sometimes it may be.

Sometimes, actually, those serve a purpose, so just because something looks weird doesn't mean that it is unnecessary, but maybe sometimes it is, and that's one of the big issues we face there. Now, in the start, I mentioned RSA, and I said there are secure versions of it,

and this is the case. However, they require something a bit more complicated, and one of the things they use to acquire security are hash functions, and hash functions are pretty much functions where you can throw in 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 is, 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, well, some of the issues that we face with them, because the RSA proofs are not really in the standard model. Instead, they use something else.

Yes, well, if we 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 a random oracle, which is, in fact, this dwarf, and this dwarf lives in a box, and he has a dice and a book,

and if someone comes to the box and wants to have a hash for a specific message, he looks into his book and wants to check out if he already answered such a message, and if he did, then he answers in the same way as he did before, and otherwise, he rolls his dice

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.

Yes, 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 H be either a hash function or a random oracle.

Then we simply reuse the generation algorithm, which gives us a key pair for a new encryption scheme, and we partly reuse the encryption algorithm

and modify it 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 our secret key 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 you 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 your hash function

and it will, of course, be evaluated to the same result as the hash function, and then you always get the secret key. So the random oracle allows us to prove schemes which are obviously insecure.

The authors who write the first paper on this came to some harsh statements. It should be clear that the random oracle mythology is not sound, that is, the mere fact that a scheme is secure in the random oracle model cannot take as evidence or indication to the security.

And furthermore, he said, indeed, what happens with the random oracle model reminds us of the biblical story of the bronze serpent. The story illustrates the process by which a good thing may become a fetish and what you should do in such a case. Spoiler alert, this snake had to be destroyed.

But if you need to cite the Bible as a cryptographer, your point maybe is not as good as you might think. Other authors said that if one of the world's leading specialists 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 not clear what to do with it,

because it's widely used in proofs, and there are schemes that can only be proven in the random oracle model. And they seem to be secure, but obviously, as you saw, the random oracle model allows also 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 suddenly strange stuff appeared. This duplicate 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 pair such that the signature is valid under your newly 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 these kind of signatures.

Another example, the Bonne Boyan 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 element, in the context one you have two, 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 one? So you might have noticed that we get a little bit deeper in the beauty of proving brainfuck, and for the next step I'll introduce another cryptographic tool

which is called commitment schemes. A commitment scheme works like this. A party Alice has a message M, and she wants to tell Bob that she's chosen 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 safe 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 learn anything about the message given the commitment.

And later, Alice can open this commitment, which is called the unveil. 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 M and sends the commitment to Bob. Bob commits on another message and sends the commitment to Alice, and then they open the commitments, and they see who wins the game.

But what happens if Alice is not interacting with Bob, who's nice, but with 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 M plus one. That's not what we want to have using our commitment scheme. So, composing protocols together can make them insecure, or 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 composable. They're not even secure. To do this, we use these simulation-based proofs and a special variant of it

called the Universal Composability Model. Here, we have this ideal function Florian 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... Sorry, that's not an ideal functionality. This one.

So, we have... Here's Keslek. So, that's trustworthy. So, we have this trustworthy authority, and the parties simply put their input to the 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 Z. 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, which 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. So, how does such an ideal functionality look like?

We'll look at the functionality for commitments. Alice can put the message in, then the message, the functionality tells Bob that Alice has committed. Later, Alice says, unveil it, and then Bob gets the message.

So, now we'll try to prove such a system in this universal composability scheme. The environment using the attacker tells the corrupted sender to use this commitment.

The corrupted sender uses this commitment. Later, he's told to unveil. He unveils, and then the receiver who's not corrupted can answer with the message. In the ideal scenario, the simulator is on the good side,

because he wants to confirm the environment that he's in the real scenario, and he works together with the corrupted party. The environment tells the corrupted party to use this commitment.

It tries to send it to the ideal functionality, and the ideal functionality is confused, because there is no definition of to give in a 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 ideal 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 from a given distribution.

It's chosen 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 two generators, such that the public key is chosen randomly, and no one knows the secret key. Now, Alice can use the same commitment scheme as before. For C0, she encrypts the message with the public key,

where no one knows the secret key. She proves with some magic cryptography that the message in C1 and C2 is the same, and then she uses this as a commitment.

The simulator now can just take the common reference string on its own, but he's not taking it from a given distribution randomly, but instead he uses a real key generation algorithm,

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's H, and now he's able to extract the message bit from the commitment,

and put it into the ideal functionality. So, introducing the common reference string allows us to prove this scheme secure.

So, maybe when the NSA gave us ECD-RBG, they didn't want to snoop on us, but maybe they just wanted to give us a tool to provide extractability in UC scenarios. Well, maybe they probably wanted to snoop. As we said, common reference strings are basically backdoors,

so it's quite hard to convince people that they are honestly generated. The probably most sophisticated one, where people actually use complex common reference strings, involves the cryptocurrency CCache, where they went through quite great lengths to produce a common reference string that is plausibly honestly generated.

Of course, it is indistinguishable. It must be indistinguishable, whether that's the case. We did a 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 Monero guys will tell you that they don't use anything that uses a trusted setup. Well, they use Patterson commitments, which are the commitments that we started out with. For them, you still need some kind of plausibility that nobody knows

the discrete logarithm between that G and that H. What they did was basically they took the element G through SHA-3 and used the output as the other group element.

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 own crypto. It's extremely likely that you will get

it wrong. We skipped over several details here, and even if you manage 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 a good heuristic is a lot better than

nothing, so at least use 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 oracle 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.

Thank you very much for this most excellent talk. We have microphones in the cell here, so please line up behind them. And to start it off, we have a question from the internet. Can you elaborate why there is such confidence in DDS assumptions?

The first thing is, people spend a lot of time looking at it, and assumptions usually stem 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's also a different argument. There's something called the generic group model, and it formalises the notion of those mathematical concepts that are used. I only showed you a very technical definition of the Elgamal 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 to this generic group model. And the generic 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 Diffie-Hellman assumption holds, but that doesn't mean that there are no attacks on it that use non-generic properties of the group. For example, the reason we use elliptic

curves is that we believe that they are mostly equivalent to generic groups, and the reason we need so huge groups 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 better off, that's completely broken in that case. Microphone number two, please. 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 try to get rid of it, but this...

You saw the results. Yes, you saw the results. Often you need to change stuff in your protocol to get rid of the random oracle model, and this leads to complicated constructions which are strange properties.

Does that answer your question? Yes. Then microphone two 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 we have some time left. There is four moments. Okay, that's enough. There is this... You occasionally encounter the idea that some security level is enough or insufficient or whatever, and the first thing that is maybe not that trivial is that there 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

this 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 128 bits on itself is pretty much sufficient.

There are also certain schemes that provide statistical security, which is in a way 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 brute force a certain key using two to the 128 operations, you still have to factor in that factor of one in a thousand.

So the 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's 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 that is, of course, the one-time pad, where for every possible plaintext there is a key that will encrypt the ciphertext to the plaintext.

Those are completely impossible to break, and as such there is no security parameter. I think we might be able to take one last question. Do we have another question from the internet? No? No question from here? Well then, a warm round of applause for Luca St. Grobman.