Multi-message encryption without PRFs

Multi-message encryption without PRFs

Keren Ganon 30 Jan 2020 09:01

In the end of lecture 4 before introducing PRFs, we talked about using our current set of tools to support multi-message encryption.
In both of the examples (stream ciphers and public synchronization) the main issue was that we have to maintain a state.

Is this the only way to support multi-message encryption? If the encryption is random, isn't this sufficient for multi-message encryption?

My main wonder here is what do PRFs introduce to us that wasn't possible before.
If this is stateless multi-message encryption, then why wasn't this possible before?

Re: Multi-message encryption without PRFs

nbitansky 30 Jan 2020 17:22

Not sure I understand the question. Formally, it's all possible, as PRFs follow from OWFs. Do you have a specific construction in mind of multi-message encryption that doesn't use PRFs?

Re: Multi-message encryption without PRFs

Keren Ganon 31 Jan 2020 08:02

I'm not sure I understand why any regular encryption scheme (G,E,D) where E is randomized wouldn't work.

From what I understand, the danger in encrypting multiple messages of the adversary gaining more information from the multiple encryptions.
But if E is randomized and we encrypt a polynomial number of messages, where is the risk here?

Re: Multi-message encryption without PRFs

nbitansky 31 Jan 2020 16:44

There are two separate issues here:
1) the fact that a stateless multi-message encryption must be randomized in order to be secure (regardless of how it's constructed).
2) the second is how to construct (randomized) multi-message encryption. Not every randomized encryption is multi-message secure. We constructed a secure one based on PRFs.