Reading assignment for 5/5 + answer to a question

[עודד גולדרייך‎]

For next meeting (on 5/5), please read
* Sec 6.3.1 (constricting MACs based on PRF),
**but you may skip Sec 6.3.1.3 (I forgot to say this)**.
* Sec 6.4.1 (one-time signature schemes).
So you have approximately 3+5 pages to read.

In the meeting, a sequence of Q&As led to the following question:
Is it true that for any CPA+CCA2-secure *private-key* encryption
scheme
it is ineasible to generate a valif plaintext-ciphertex pair that did
not appear in prior queries. The answer is *no*.

Let $(G,E,D)$ be an CPA+CCA2-secure *private-key* encryption scheme,
and consider the scheme $(G,E',D')$ (i.e., $G'=G$):
* $E'_K(msg) = (0,msg)$ with probability $2^{-|K|}$
and $E'_K(msg) = $(1,E_K(msg))$ otherwise.
* $D'_K(b,y) = y$ and $D'_K(1,y) = D_K(y)$.
A small bonus/non-obligatory exercise: prove that $(G,E,D)$
is an CPA+CCA2-secure *private-key* encryption scheme.

[עודד גולדרייך‎]

I had a typo in my def of $D'$; I'll let those interested fix it...
(It is minor..) Oded