Can a Full-State Keyed Sponge be used as AEAD by using XEX?

Full-State Keyed Sponge (aka Donkey Sponge) is when a message is absorbed into the full state of the sponge.

Such an approach to MAC construction is considered secure. 1

However for an AEAD or a stream cipher, exposing the state obviously breaks it.

Would utilizing a XEX-like approach be able to secure such a scheme?

Let P be a permutation such as Keccak-p. Using P we construct a duplex object such as:

We modify it to no longer have a hidden state (second lane in the diagram above).

This would result in a broken cipher as the state leaks via Cx.

The proposed fix is to have

Cx = Px ⊕ STATE(x) ⊕ STATE(x-1)


Note that

STATE(x+1) = P(STATE(x) ⊕ Px)


Where

|Cx| = |Px| = |STATE(x)|


Would this work to secure the cipher? I have been unable to find any papers on the subject.

My attempt to analyze it yielded:

Cx = Px ⊕ STATE(x) ⊕ STATE(x-1)
Cx+1 = Px+1 ⊕ STATE(x+1) ⊕ STATE(x)


Meaning that an attacker could obtain:

STATE(x+1) ⊕ STATE(x-1)


Therefore, could obtain:

STATE(J) ⊕ STATE(J+n)


for any n > 0 where J is one step prior to the beginning of ciphertext extraction.

But I don't see how that can help leak the STATE at any point or lead to an attack on the cipher.

• OCH uses Even-Mansour and is like OCB but with a permutation. Commented Oct 14, 2023 at 9:56