Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.