Before we start with the actual lecture, let us remind what we did in the past lecture,

and then I want to give you a short overview about the content of this lecture.

In the last lecture we introduced the notion of enhanced trapdoor permutations.

Trapdoor permutations are very similar to one-way functions, in the sense of course

that inversion should be difficult, but moreover they have a trapdoor. And given this trapdoor,

this allows us to invert this function efficiently. So we have seen different definitions of trapdoor

permutations, one that was a little bit formal and the other one that was a little bit easier

to work with. We have essentially then also understood the notion of one-wayness for trapdoor

permutations, and we also discussed the notion of hardcore predicates. And essentially we

have seen these things, right, that was essentially one primitive that we discussed in order to

construct oblivious transfer. So oblivious transfer is this amazing primitive, it's an

interactive protocol to be precise, that allows two parties to interact in such a way that

one party has two secrets, let's say a zero and a one, and the other party has one bit

as input, say B, and at the end of the protocol this party with the bit learns one of the

secrets, namely SB. And we had the security notions with respect to a sender and the receiver

that essentially said, at least on an intuitive level, the receiver only receives one of the

two secrets and learns no information about the second secret, while the sender does not

learn which of the two secrets the receiver actually has chosen, and therefore it's an

oblivious transfer. So in this lecture week we are continuing our path towards constructing

a secure two-party computation protocol. And this protocol essentially, as we will see,

that this will be based on Yaw's garbled circuit, that will consist of two components, namely

private key encryption and oblivious transfer. So both components we have already seen, which

means we have enough stuff together to construct such a protocol. So now the problem is, right,

I mean why don't we start ahead? Well, because we have no clue what security means in this

context. So today we are in particular taking a look at the definition of semi-honest security.

And semi-honest security essentially means that the adversary follows the protocol honestly,

and at the end of the game tries to learn some additional information out of that. This

is a relatively weak notion of security, but it's a good starting point to understand how

to define security in this context at all. So, let's start with the first one. So, the

first one is a very simple one. It's a very simple one. It's a very simple one. It's a

very simple one. It's a very simple one. It's a very simple one. It's a very simple one.

So, let's start with the preliminaries for the definition. So, first of all, we will

define the notion of computation and distinguishability. This is something, of course, that we will

need within this definition. So, this follows the standard computational complexity approach.

And it essentially works as follows. We are considering objects as infinite sequences of

strings. And we are considering objects as infinite sequences of strings. So, we will

define the notion of computation and distinguishability.

Right, so the essential idea is the following. We essentially have one object Xn, and this

is not only a single object, but there is, as we just said, an infinite sequence, which

means we have here an index n coming from the set n. So, this is one possible infinite

sequence of strings. And then we are considering a second infinite sequence of strings. And

let's call this Y. And now we are essentially giving D access to one of those. And D, for

example, might accept Xn if and only if it accepts Yn. Let me be a little bit more precise

here. Essentially, what it means to be computation and distinguishable is that D cannot tell these

apart. And therefore, we essentially said that D accepts Xn if and only if it also accepts

Yn. And this, in fact, means that the distinguisher cannot tell the other two apart.

So, these two distributions are apart. And now what we usually do is we measure the probability

that D outputs one. Right? This is essentially the case when D says, okay, I recognize distribution,

one of the distributions. Right? So, essentially, you can feed D these samples and D will output

one. And now what you want to make sure is that both probabilities are close. So, if