[Cryptography] Non-deterministic PRF as a MAC-and-Nonce for AEAD?

[Jon Callas]

> On May 20, 2018, at 4:26 PM, Alfie John <alfie at alfie.wtf> wrote:
> 
> Hi everyone,
> 
> Quick question on if this would work as a safe AEAD scheme:
> 
>  If you use a non-deterministic PRF instead of a MAC when doing
> 	MAC-then-Encrypt, could the NDPRF be safely used as the nonce (or
> 	used to deterministically generate a nonce) to the cipher as it
> 	should never be repeated given the same plaintext?

I confess that I don't understand what you're saying.

If you have a non-deterministic thingie, then it's likely not a function. However, let's say that you have a function F(x) and that for any given x, we can't predict what F(x) is, and that the output of F(x_i) is mathematically pseudo-random, but F(x_i) is always the same value, and it doesn't change every time you call F(). You can't predict what the function value is ahead of time, but once you compute it once, it's not going to change. Does that make sense to you?

If you have such a function, then it is precisely what we mean by a Random Oracle. Ideally, a MAC acts like a random oracle, but remember that a MAC is a function of a key and the data, so it's not exactly the same thing.

I confess that I don't know what you're trying to do. Yes, if you have a MAC, it should function as a random oracle, so sure, it's also an NDPRF as you named things. But there are NDPRFs that are not MACs, as well, even though I don't have one off the top of my head, I am sure I could construct some pathological function that met your requirements but wasn't secure. Again, what problem are you trying to solve? Why not just use a MAC as a MAC? They're hard enough to build. 

	Jon