Assume $F$ is a pseudo-random permutation (PRP) then the tweakable block-cipher based on the Merkle-Damgård construction (take this as the way I understand, here is the equation):

$F_k[t](m) := F_{F_k(t)}(m)$

is a secure tweakable block cipher. This is marked with two stars in my notes.

First question: is it right or wrong?

Second question (if it is right): will a standard argument - that distinguishes the real world from the ideal world - work?

  • 1
    $\begingroup$ Minematsu (Section 5) showed this is secure up to $2^{n/2}$ queries for an $n$-bit tweak. $\endgroup$ Commented Dec 27, 2018 at 17:12
  • $\begingroup$ @SamuelNeves care to turn that into an answer? $\endgroup$
    – Maarten Bodewes
    Commented Dec 28, 2018 at 2:03

1 Answer 1


Minematsu studied this construction, and some generalizations thereof, in Section 5 of Beyond-Birthday-Bound Security Based on Tweakable Block Cipher. Minematsu, however, uses a PRF to derive keys instead of the block cipher.

The idea is simple: the tweakable SPRP security of this construction, for $q$ queries distributed arbitrarily over $t \le q$ different tweaks, is the security of $t$ instances of $F$, plus the distance from the key derivation to uniformly distributed keys.

The security of $t$ instances of $F$ is otherwise known as multi-key or multi-user security, and we can bound it as $t \cdot \mathbf{Adv}_{F}^{\text{sprp}}(\mathcal{D})$, i.e., at most $t$ times the security of any single instance.

So we have $$ \mathbf{Adv}^{\widetilde{\text{sprp}}}_{F}(\mathcal{D}) \le \mathbf{Adv}^{\text{prf}}_F(\mathcal{D'}) + t \cdot \mathbf{Adv}^{\text{sprp}}_{F}(\mathcal{D''}) \,, $$ for a distinguisher $\mathcal{D'}$ making $t$ queries and a distinguisher $\mathcal{D''}$ making at most $q$ queries. The first distance can be refined by the PRP-PRF switch, so we end up with $$ \mathbf{Adv}^{\widetilde{\text{sprp}}}_{F}(\mathcal{D}) \le \frac{\binom{q}{2}}{2^n} + (t + 1) \cdot \mathbf{Adv}^{\text{sprp}}_{F}(\mathcal{D''}) \,. $$

So this construction is secure until approximately $2^{n/2}$ blocks are queried and, assuming a perfect block cipher with $\mathbf{Adv}(\mathcal{D}) \le t/2^k$, around $2^k/t$ evaluations.

Imagine for example a concrete instance of AES-128 where an attacker queries $2^{64}$ different tweaks $x_i = \text{AES}_{\text{AES}_k(t_i)}(0)$ then tries $2^{64}$ keys $k_i$ until $\text{AES}_{k_j}(0) = x_i$. Each attempt has success probability $2^{64-128}$, since there are $2^{64}$ distinct keys. Then, $\text{AES}_{\text{AES}_k(t_i)}(1)$ must also be equal to $\text{AES}_{k_j}(1)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.