Sie befinden sich hier: Termine » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 13 » Fragen

Prüfer: Prof. Dr. Schröder, Beisitzer: Russell W. F. Lai, 1. April 2019

Prüfungssprache im Vorfeld auf Englisch festgelegt. Bei Verstaendnisproblemen kann man zu Deutsch wechseln.

Zettel und Stift liegen bereit und wurden im Verlauf der Prüfung oft von Prüfer und Prüfling verwendet.

Bei fast allen Fragen habe ich Schemen/Algorithmen Beschreibungen aufgemalt.

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