In Katz & Lindell's textbook (2nd edition)) is said, that only non deterministic encryption can lead to security for multiple encryptions. Now I looked at the experiment for multiple indistinguishable security and there is said, that the challenger gets two sets of messages from the adversary. Say we have the PRG cryptosystem, that XORs messages with the output of the PRG. Why couldn't the challenger simply create a pseudorandom string equal the combined size of all messages in the set using the PRG and therefore create one big key, that is used to encrypt all messages? This should be deterministic and still fullfill the requirements of the experiment?

  • $\begingroup$ The seed of the PRG? What if the adversary send them one by one? $\endgroup$
    – kelalaka
    Nov 2, 2021 at 8:38
  • $\begingroup$ Yes one by one would be a problem, but exploiting the definition of the experiment (not talking about what should make sense) non determinism is not necessary? $\endgroup$
    – Titanlord
    Nov 2, 2021 at 8:45
  • 4
    $\begingroup$ The construction you're suggesting would be stateful. (It needs to remember which parts of the key stream have already been used.) The definition of encryption used in the book (as far as I remember) does not allow for a stateful encryption algorithm. $\endgroup$
    – Maeher
    Nov 2, 2021 at 11:34


Your Answer

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