Fragen

- What did you like most?

Minicrypt World.

EAV, CPA, CCA, SIGN, PRF, PRP, PRG, OWF.

You can construct everything in here from OWF.

- How do you construct a PRG from OWF? Careful, there's a little trap here.

You don't. You construct PRG from OWP. That was the trap. The construction from OWF is complicated and not part of the lecture.

You can use a hardcore predicate (hc) to expand a OWP (f) to a PRG (G):

G(s) := f(s) || hc(s)

Since i started off with a OWF instead of a OWP, we discussed whether

f'(x) := f(x) || 0

is a OWF, which it is. (This construction just wouldn't work if f' and f should be PRF instead of OWF)

- How do you construct a PRF from a PRG?

Tree construction from the lecture with length doubling PRG.

- How do you get this length doubling PRG? We only had expansion by one bit before.

Rough description of the hybrid argument for constructing polynomial expansion PRG from n+1 bit expansion PRG. If there are only negligible gaps between neighbouring hybrids, the gap between the extreme hybrids is also negligible. The extreme hybrids are a random value of length 2n and the result of applying the n+1 PRG n-times. This matches the input in the PRG distinguishing game.

- What did Diffie and Hellman describe in their beautiful paper?

They most certainly wrote more than one beautiful paper.

- But what did they describe in their first one?

Drawing of Diffie-Hellman-Key-Exchange Protocol

- What security notion does a Key-Exchange Protocol have to satisfy?

Indistinguishability of the exchanged key from a randomly chosen key

- Why is this scheme secure?

DDH is assumed to be hard

- Can you build an Encryption Scheme from this?

Drawing of El Gamel Encryption

- Which security notion does El Gamal satisfy?

CPA

- Why not CCA?

Uuuuuh, because you can somehow alter the Ciphertext.. I don't know.

- Because El Gamal is rerandomisable

Oh, right.

- You said we can also construct Signature Schemes from OWF?

Lamport's OTS Chain/Tree construction for stateful many time Signatures

- What problems does this construction have?

Efficiency, must send chain/tree path of all previously used keys and messages along with the most recent signature.

Leaks all previously signed messages.

The construction uses a Signature Function, which can handle input longer than key size, which we can't with just Lamport's OTS