DH Key Exchange Protocol and how it induces the El Gamal public-key enc. scheme
I drew Alice and Bob and how they shared some (non-further-specified) messages and at the end agreed on a key K. Then, I also explained its security notion and drew the game the adversary plays (gets a transcript, the actual key OR a faked key etc.)
All private-key enc. schemes implicitly assume a key being shared off-band somehow. You can use a key exchange protocol for doing this.
Yes, but I can give you once instance of such a protocol. I drew the DH protocol.
[editor's note: the protocol assumes an authenticated channel!]
Well, it's funny because it's by DDH-hardness which was created exactly to model that.
I gave definitions for Gen, Enc, Dec from El Gamal and elaborated which part originated from which part in the DH protocol:
Gen: subsumes what Alice initially does in DH; pk is what Alice transmitted to Bob; sk is Alice's internal stateEnc
Enc: amounts to Bob completing DH and blinding a message with the obtained key
Dec: amounts to Alice completing DH and recovering the message
IND-CPA
I drew the IND-CCA game in sloppy form (always decryption oracle).
Well, actually I meant: in phase 1 arbitrary access to dec. oracle, in phase 2 restricted access
You can mall with the ciphertext. [editor's note: no details were asked, but I think the counterexample is simple enough to know!]
By combining MAC and IND-CPA-secure scheme to achieve Authenticated Encryption. [editor's note: I mistakenly switche to the private-key world.]
Uh, possibly we could replace MAC by public-key signatures and IND-CPA in private-key sense by IND-CPA in public-key sense, and then use the Encrypt-then-Auth/Sign idiom. [editor's note: no, that's not that easy, carry on reading why]
No, that's not that easily possible, let's see why. Prof. Schröder then drew the supposed `Enc(pk, m) := Sign(sk_{sig}, Enc_{cpa}(pk_{cpa}, m))`. Do you see why now?
Ah, we cannot access sk_{sig} since Enc(pk, m) must be possible with pk alone.
Right, so let's adapt to `Enc(pk, m) := (sk_{sig}, pk_{sig}) ← GenSig, return Sign(sk_{sig}, Enc_{cpa}(pk_{cpa}, m))`.
But then I can just fake ciphertexts by generating signature key pairs on my own as an adversary.
[editor's note: after some thinking and hints by examiners to KEM and FDH-RSA] Ah as follows. I then drew a CCA-secure KEM. At first I forgot hashing, but then after a hint added it.
I drew minicrypt starting with OWF →* OWP → OWP with hardcore predicate → PRG → length-doubling PRG → PRF → MAC. [editor's note: details of →* was not covered in class; but you should know that such a step is necessary]
Perfect, let's inspect some PRFs. Is F'(K, m) := F(K, m || 0) || F(K, m || 1) a PRF ignoring length preservation conditions?
Yes because the inputs to the individual PRF calls are always different (in last bit), hence their outputs are intuitively independent.
Yes, how about `F'(K, m) := F(K, 0 || m) || F(K, m || 1)`?
My last argument now fails, e.g. with first message `m_0 := 0^{n-1}1` and second message `m_1 := 0^n`. We can then relate structure of both outputs by `F'`.