Decients, welcome back to the lecture Secure Multi-Party Computation.

So in the previous lecture we continued our past towards building a secure to party computation

protocol. So in the last lecture we studied the notion of private key encryption schemes.

We will need this notion when we are starting to discuss the Ausgabe circuit. And there

in particular we will use the encryption scheme to encrypt gates of the circuit.

Today we introduce another cryptographic building block of the Ausgabe circuit and this is a

cryptographic protocol called Oblivious Transfer. Oblivious Transfer is a pretty cool protocol.

So what Oblivious Transfer allows you to do is the following. We have two parties, Alice

and Bob, as always, and Alice holds two secrets, say X0 and X1. And now Bob wishes to learn

one of them, XB, depending on his own input B, in such a way that Alice doesn't really

know which one of both he actually learned. On the other hand Alice is only willing to

give out one of them. So this is a cryptographic building block that is extremely cool. So

with Oblivious Transfer there exists a beautiful result that shows Oblivious Transfer is complete.

That means if Oblivious Transfer exists, then purely on this assumption you can securely

realize any cryptographic object, any functionality. Amazing, right? Such a beautiful primitive.

How do we construct Oblivious Transfer? Well, we will need something a little bit stronger

than you have seen before. In particular we will need a cryptographic primitive called

a trapdoor permutation. So trapdoor permutation is a permutation that has this additional

property that there exists a trapdoor. And if you know the trapdoor, then inverting a

trapdoor permutation, inverting this function is computationally easy. The only instance

that we know so far is based on RSA. Nevertheless, we introduced this in generality. Maybe you

find a new instance that would definitely be interesting for the broad audience. So

thank you again for watching. I hope you enjoyed the video so far and I look forward to seeing

you in the question and answer session. So we begin with the introduction of a cryptographic

primitive called trapdoor permutations. To introduce this primitive let me recall of

a one-way function respectively a one-way permutation. So this was a cryptographic object

of function f that is easy to compute, let's say given a string. But the security notion

essentially says that if I give this string here to an adversary, then for the adversary

it is computationally hard to output some value x' such that f of x, namely this value

below, equals 2f of x'. So this might be a permutation, right? We can define the same

notion for permutations. And now we are considering something slightly stronger and this is called

a trapdoor permutation. So the difference is here that for one-way functions in general

this going back, this intuition of going back is in general hard. So regardless of whether

there exists some private information going back is hard. In contrast a trapdoor function

or in this case a trapdoor permutation, it can essentially be computed in two ways. The

same way here if we basically insert x then we get f of x but it also has a different

mode of computation and this is called in this case let's say invert. And invert requires

the private trapdoor. And if you have this private trapdoor you can essentially insert

f of x and since it's a permutation in this case you will end up with the same x. So trapdoor

permutations are mainly known to exist from the RSA assumption as we will see later. So

we will start with the following definition that introduces trapdoor permutations following.

So we say a trapdoor permutation f is a tuple of efficient algorithms

and here we introduce the algorithms gen, sample, eval and invert. And these algorithms

have the following property. We start with the generation algorithm. The key generation

algorithm outputs a pair i and td where you can really think of i as being an index that

points to a certain function. So i defines a particular permutation f i over some domain

di and td is essentially a trapdoor.

So, the next algorithm that we introduce is a sample algorithm. And this we have already

seen when we discussed the notion of one-way functions.

So,