Score:0

Necessity of non determinism for multiple message security

tl flag

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?

kelalaka avatar
in flag
The seed of the PRG? What if the adversary send them one by one?
Titanlord avatar
tl flag
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?
cn flag
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.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.