

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

How would you answer the following question (I have to translate it from German):

The existence of a pseudorandom generator implies the existence of a AE-Secure encryption scheme (AE = authenticated encryption)


I would say "NO" because (as far as I understand) AE-secure schemes should use two keys (one for encryption and one for authentication).

But maybe I'm wrong because of missing background knowledge.

share|improve this question
If you have a PRG, can't you use it to derive multiple keys from a single master key? – Ilmari Karonen Nov 24 '12 at 16:02
Is this homework? – D.W. Nov 24 '12 at 23:35
not really homework. These is from a list of exam question that i need to understand. Its one question on a list of 6 multiple choice question. In the exam it wasnt necessary to give an explanation, but i want to understand it. – twallutis Nov 25 '12 at 11:33

I'm not a hundred percent certain on your definition of "AE-Secure", but I would have to say yes.

Existence of a PRG implies existence of one-way functions, which in turn implies existence of both, symmetric encryption and message authentication codes. From those two primitives you should be able to construct authenticated encryption.

share|improve this answer
I try to translate the definition of AE-secure that is in my lecture notes: An encryption scheme is AE-secure, if it is secure against Chosen-cyphertext attacks and provides authenticity. – twallutis Nov 24 '12 at 12:07
This is the Ruby Goldberg proof, as the proofs of "one-way functions imply symmetric encryption" $\qquad$ and "one-way functions imply message authentication codes" go $\: \text{OWF} \to \text{PRG} \to \text{symmetric encryption} \:$ and $\: \text{OWF} \to \text{PRG} \to \text{MAC} \;\;$. $\hspace{.75 in}$ – Ricky Demer Nov 25 '12 at 8:34

Yes. The existence of a secure pseudorandom generator (PRG) implies the existence of all sorts of other symmetric-key primitives, including a secure PRF, a secure block cipher, a secure MAC, etc. That is enough to build secure authenticated encryption.

share|improve this answer

Your Answer


