# Not understanding deterministic authenticated encryption (DAE) security definition

I have a question regarding the security definition of deterministic authenticated encryption (DAE) as defined by Bellare and Shrimpton. Their definition is reproduced below, and my question pertains to the emphasized part.

Definition 1 Let $$\Pi = (\mathcal K, \mathcal E, \mathcal D)$$ be a DAE scheme with header space $$\mathcal H$$, message space $$\mathcal X$$, and expansion function $$e$$. The DAE-advantage of adversary $$A$$ breaking $$\Pi$$ is defined as

$$\mathbf{Adv}_{\Pi}^{\mathrm{dae}}(A) = \Pr[K \gets \mathcal{K} : A^{\mathcal{E}_K(\cdot, \cdot), \mathcal{D}_K(\cdot, \cdot)} \Rightarrow 1] - \Pr[A^{\\\(\cdot, \cdot), \bot(\cdot, \cdot)} \Rightarrow 1]$$

On query $$H \in \mathcal H,X \in \mathcal X$$, the adversary’s random-bits oracle $$\\\(\cdot,\cdot)$$ returns a random string of length $$|X|+e(H, X)$$. As always, oracle queries outside the specified domain return $$\bot$$. The $$⊥(\cdot,\cdot)$$ oracle returns $$\bot$$ on every input. We assume that the adversary does not ask $$(H, Y)$$ of its right (ie, second) oracle if some previous left (ie, first) oracle query $$(H, X)$$ returned $$Y$$; does not ask $$(H, X)$$ of its left oracle if some previous right-oracle query $$(H, Y)$$ returned $$X$$; does not ask left queries outside of $$\mathcal H \times \mathcal X$$; and does not repeat a query. The last two assumptions are without loss of generality, as an adversary that violated any of these constraints could be replaced by a more efficient and equally effective adversary (in the $$\mathbf{Adv}_{\Pi}^{\mathrm{dae}}$$-sense) that did not. The first two assumptions are to prevent trivial wins

Basically, I don't see how the last assumption (i.e., no repeated query) is without loss of generalization? More specifically, isn't this assumption needed for any deterministic scheme to be considered secure according to this definition?

Here is how you could break any deterministic scheme according to Def. 1, if queries could be repeated. First, repeat the same query $$(H,X)$$ to the left oracle (either $$\mathcal{E}_K(\cdot, \cdot)$$ or $$\\\(\cdot, \cdot)$$) and get back $$Y_1$$ and $$Y_2$$. If $$Y_1 = Y_2$$ return 1. It's trivial to see that this attack has DAE-advantage $$1-2^{-|X|-e(H,X)}$$.

As justification for their WLOG claim, I imagine they had the following reduction in mind. Let $$A$$ be a DAE-adversary that repeats queries, and let $$B$$ the following DAE-adversary that doesn't. It runs $$A$$ and forwards all of $$A$$'s queries to its own oracles, except whenever $$A$$ repeats a query, where $$B$$ instead returns the same response back for that query (which $$B$$ cached). $$B$$ outputs the same as $$A$$. However, this reduction doesn't work! (In particular, it doesn't properly simulate the DAE game).

• I think the key thing to note here is that we're talking about deterministic authenticated encryption and therefore the encryption function is deterministic, meaning equal inputs lead to equal outputs? Dec 28, 2020 at 19:05
• Yes, exactly. That's the heart of the issue. Dec 28, 2020 at 20:19
• Short answer: the random-oracle also returns the same result if queried with the same input, so your attack does not work. Dec 28, 2020 at 22:28
• Hmm, interesting. I've never thought of a random-bits oracle as caching its results (like a normal random oracle does). Do you have any references for this interpretation elsewhere in the literature? Of course, in the context of DAE this interpretation makes sense, but isn't odd that they don't call out this behavior explicitly? Dec 28, 2020 at 23:33
• @hakoja In this case the ideal functionality should clearly still be a (random) function, but I agree that the definition in your reference is not as clear as it could be. It would be more precise to say "uniform random function" rather than "random-bits oracle". (For example, see Definition 1 in tosc.iacr.org/index.php/ToSC/article/view/7296/6470.) Dec 28, 2020 at 23:55