Dear students, welcome to the second lecture of Secure Multi-Party Computation.

In the first lecture what we have learned so far were the basics or the basic preliminaries

that we required in this lecture, in particular we discussed of the notion of algorithms,

randomized algorithms, negligible functions, circuits and one-way functions.

The next basic that we require for our construction of a Secure Multi-Party Computation protocol

are private key encryption schemes.

So the purpose of this lecture here is to introduce this primitive formulae and also

to show how we can actually construct such a primitive.

Instead of going all the way from a one-way function towards this goal, we make our life

a little bit easier and refer to the previous lecture and we will just assume the existence

of pseudorandom functions.

Recall that a pseudorandom function, this is this magic object that you can query but

you cannot tell whether the function is a pseudorandom function or a truly random function.

So we have defined that formally in the sense that there is initially a bit flippy and this

decides about the object that is contained in the box.

So there is a box the adversary can interact with, can send query, queries receive the

responses, and at the end of the game the adversary has to tell whether there was a

pseudorandom function in this box or a truly random function in this box.

We will use pseudorandom functions as a building block to construct a CPA secure encryption

scheme.

While we did this already in the introductory class, we will repeat this exercise here for

two reasons.

First of all, we need to make sure that we all understand what is the basis for the construction

of a secure multi-party computation protocol.

And the second purpose is to make sure that we recall the notion of reduction proofs,

which is one of the main fundamental techniques in crypto that helps us to relate where is

the security coming from and what is the underlying assumption.

And these assumptions are in general significantly easier than the scheme itself and they can

be analyzed completely independent of the cryptographic primitive that you want to achieve.

So thank you for your attention so far and I'm looking forward to the coming semester.

Thank you.

In this lecture, we're introducing the notion of private key encryption.

Private key encryption is the most fundamental cryptographic primitive and probably the one

that motivated most of the area.

You probably remember the definition of private key encryption from the introductory class

called Introduction to Modern Crypto.

So here in this lecture, we are going to recall this primitive for two reasons.

First of all, we would like to make sure that we all share the common ground, we all know

what primitives we are using and we all have the same understanding of the properties that

we are using.

It should also serve as a practice to recall how our proofs by reduction work.

And the second reason is since we are going to introduce the Ausgabelt circuit as a secure

two-party computation protocol, we will actually describe all of the components that the Ausgabelt

circuit require fully in depth such that we are aware of what properties are needed.

To motivate the need or the purpose of private key encryption, let's take a look at the picture

that you can see here.

So here you see two parties and this is Alice and this is Bob and magically they somehow

share a private key before.

At this point we don't really care how they agreed on that key, we make our life simple

and assume they just did it somehow before.