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).
