Security of the tweakable single-key Even-Mansour construction

[John Preuß Mattsson]

Hi,

My colleague Alexander Maximov recently published some notes [1] that could be of interest for people designing accordions.

[1] Maximov, Alexander, "Notes on (failed) attempts to instantiate TLR3"
https://eprint.iacr.org/2024/951.pdf

In particular, the (tweakable) single-key "Even-Mansour" construction was mentioned at the 2023 workshop.

The single-key Even-Mansour construction:

c = E(k, m) := π(m ⊕ k) ⊕ k

The tweakable single-key Even-Mansour construction:

c = E(k, t, m) := π(m ⊕ k · t) ⊕ k · t

As mentioned by Maximov in [1], the constructions produces heavily related output.

"One can ignore t, or simply set t = 1. Then consider two related pairs (m, k) and (m′, k′)
such that (m ⊕ k) = (m′ ⊕ k′), then the outputs are heavily related c ⊕ c′ = k ⊕ k′.
In an ideal keyed block cipher we want that for a distinct k we get a pseudo-random
permutation/mapping on all 2^(2n) input values (t, m), which is not the case here in this
construct as k and m are heavily correlated."

Cheers,
John Preuß Mattsson
Expert Cryptographic Algorithms and Security Protocols, Ericsson Research