Welcome to the sixth lecture of the class Privacy Preserving Cryptocurrencies.

My name is Dominik Schurter.

As always, we start this class by reviewing what we did in the previous lecture to understand

where we are and where we are heading at.

Afterwards, we will discuss the content of this lecture and take a look how it fits in

the overall picture of this class.

In the last lecture, we introduced proof systems.

So proof system is an interactive protocol between two parties, a prover and a verifier,

and the prover wishes to convince the verifier about some assertion.

And the regular way in the setting of NP that we had seen there is that this is in fact

a non-interactive procedure, which means that there exists some assertion and some witness,

and everybody can essentially, or we call this witness certificate, anybody can verify

with a polynomial time computation that this is in fact true.

So we relaxed this notion in two ways.

First of all, we allowed that this proof can fail with a small probability, and the second

thing is that we allowed interaction.

So in the previous lecture, we started with a computational model, and here we in particular

discussed non-uniform algorithms.

And we discussed two different formalizations.

In particular, we have seen that we can express them as probabilistic polynomial time Turing

machines that also get some advice.

And this additional advice that can be something that where the computation is not possible

or not feasible in polynomial time, but this advice is then given to the adversary.

The second way how to express this, how we have formalized it, is as a family of circuits,

of Boolean circuits.

We discussed that both formalizations are in fact equivalent, and they are both stronger

than regular probabilistic polynomial time algorithms.

In particular, the halting problem can be decided by non-uniform algorithms, while we

know that a regular algorithm, a regular polynomial time Turing machine cannot decide this.

We then formalize proof systems.

And in this formalization, we discussed two properties, namely completeness and soundness.

Soundness says that if the protocol is executed honestly, then the prover always convince

the verifier.

And soundness says that a malicious prover cannot convince the verifier about some statement

that is false.

And here we in particular observed that, I mean, if we look at the definition formally,

that the prover in this definition is even allowed to be unbounded.

We then also discussed that was completeness and soundness.

We then also discussed that we have very different notions of soundness, in particular computational

soundness.

And if this holds in a computational sense, then we are usually talking about argument

systems.

So proof system holds with respect to unbounded algorithms, and argument system only holds

with respect to polynomial time algorithms.

And there were also two formalizations.

The common one that is mainly used in complexity theory considers the malicious prover to be

a non-uniform algorithm.

So either this PPT algorithm with an advice or a Boolean circuit.

And in cryptography, most of the time we are using polynomial time algorithms, so they

are not necessarily non-uniform.