Welcome to the fifth lecture in the class Privacy Preserving Crypto-Currencies.

My name is Dominik Schröder and we will start this lecture as always by reviewing what we

did in the past lectures, giving an outline of what we're going to do in this lecture

and also taking a look at the global structure of this class.

So we essentially started with creating the foundations and in particular we looked at

the cryptographic building blocks.

So in particular we started by looking at concrete constructions for public key encryption.

So here we looked at the textbook RSA scheme and remember that the textbook RSA scheme was

the one that was initially suggested at the time but we still didn't understand what security

actually means.

So to make this or to basically lift it to a secure scheme, right, I mean that was a

deterministic scheme and we know that a deterministic scheme cannot be secure, we took a look at

the version that is called padded RSA and the idea of the padded RSA encryption is essentially

to include some randomness within the group element and therefore padded RSA is CPA secure

but only for messages that are quite short.

Afterwards we took a look at the Elgammal encryption scheme.

Once we finished the part on public key encryption we continued with our introduction of signature

schemes.

Remember that a digital signature scheme mimics the properties of the handwritten signature

which means that only the person knowing the secret information which corresponds to the

information in some sense in your head how you actually do the signature, only this person

can create a signature but the verification should be publicly possible.

In practice people compare your signature to a given signature and then they believe

that well somehow they check that this is your signature.

In the digital case there is a verification algorithm.

So here we in particular looked at the definition which is essentially the description of the

interface and the security model.

In the security model we introduced it as the unforgeability notion which roughly says

that even if the adversary is allowed to see signatures of its choice he cannot create

a new fresh signature.

Again we looked at the textbook RSA signature scheme for historical reasons and then we

also thought about how we can actually obtain a secure one and here we looked at FDH RSA.

And in the exercise you have already seen how to prove the scheme secure.

And finally we took a look at ECDSA which is also the signature scheme that is used

in many cryptocurrencies such as Bitcoin.

So what are we going to do in this class?

So basically in this class we are going to introduce proof systems.

In crypto we are often faced with the situation that one party has to convince the other party

about a certain statement.

So this is used in many, many protocols where for example one party wishes to prove the

other party that it is indeed behaving honestly.

So in this lecture we will introduce proof systems in general.

We start essentially by introducing the underlying computational model.

And this model will essentially cover one thing and this is something that is probably

new and these are non-uniform algorithms.

We will see that we can express non-uniform algorithms in two different ways.

First of all as a Turing machine that gets an advice.

And this advice is you can really think about it as some secret information that the adversary

gets an addition.

And the second formalization how we will see is actually a family of poliomyotide circuits.