2
$\begingroup$

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)

YES or NO

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.

$\endgroup$
3
  • 2
    $\begingroup$ If you have a PRG, can't you use it to derive multiple keys from a single master key? $\endgroup$ Nov 24, 2012 at 16:02
  • $\begingroup$ Is this homework? $\endgroup$
    – D.W.
    Nov 24, 2012 at 23:35
  • $\begingroup$ 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. $\endgroup$
    – twallutis
    Nov 25, 2012 at 11:33

2 Answers 2

3
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – twallutis
    Nov 24, 2012 at 12:07
  • $\begingroup$ 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}$ $\endgroup$
    – user991
    Nov 25, 2012 at 8:34
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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