What is the difference between a dual cipher and a tweak?

Question

I have looked at the idea of dual ciphers but I cannot convince myself I really understand them. I think I just need a very simple worked example.

I was given the definition: Two ciphers $E$ and $E′$ are dual ciphers if they are isomorphic, i.e. if there exist invertible transformations $f(⋅)$, $g(⋅)$, $h(⋅)$ such that $\forall \ P$ and $K$ $$f(E_K(P))=E′_{g(K)}(h(P))$$ However, this is not easy for me to follow. I think $E$ is the encryption method (in my case below, $[(P \times K_1)+ K_2] \bmod26$). Yet looking at the definition it seems $f(.)$ is the cipher, is that right? And $P$ and $K$ are the plaintext and cipher key respectively. But I really don't understand what $g(K)$ and $h(P)$ are, or how to derive them.

Let's say my encryption cipher is: $C = [(P \times K_1)+ K_2] \bmod26$

1. How do I make a dual cipher of it? A very simple one is fine. If my cipher is not suitable, would you give an equally simple one that can have a dual cipher?
2. In my dual cipher from $.1$, what are my $g(K)$ and $h(P)$?
3. What could I do to this cipher to makes it a tweak but not a dual cipher?
4. How do I show my tweak is not a dual cipher?

This has been bugging me for a while so a simple example would be very much appreciated. I have posted similar questions but the answers are too difficult for my age and level.

Answer 1

So, an obvious way to build a dual cipher is to make it the same cipher: $h = id$, $g = id$, $f=id$. But that probably doesn't help your understanding.

I will a slightly less trivial example of a very simple dual cipher for your $E_{K_1, K_2}(P) = [(P \cdot K_1) + K_2]\ mod\ 26$.

$E'_{K_1,K_2}(P) = [((P+5)\cdot K_1) + K_2]\ mod\ 26$

which is dual for $h(x) = x-5$, $g = id$, $f = id$.

You could also pick

$E''_{K_1,K_2}(P) = [((P+5)\cdot K_1) + K_2]\ mod\ 13$ which is still dual for $f(x) = x\ mod\ 13$.

So two ciphers are dual if you can ANY $h, g$ and $f$ such that the above equations hold.

Now, what is the difference between this and a tweak? A tweakable block cipher has an extra input which can be public but will still changes the permutation the cipher uses. That means that

$E_{K_1, K_2}(P, t) = [((P + t) \cdot K_1) + K_2]\ mod\ 26$

could be considered a tweakable block cipher but as we saw earlier all these ciphers are dual.

Answer 2

For distinct tweaks $t \ne \tau$, the ciphers $E_{k,t}$ and $E_{k,\tau}$ should appear to be independent uniform random permutations for uniform random $k$. For example, you could think of it like having a single-bit tweakable block cipher where $E_{k,0} = \operatorname{AES256}_{k_0}$ and $E_{k,1} = \operatorname{Serpent256}_{k_1}$, where $k_0$ and $k_1$ are like magic independent uniform random bit strings somehow both deterministically derived from $k$.

For dual ciphers $E \ne E'$, $E_k$ and $E'_k$ are very much not independent—there is a deterministic relation between them for every $k$, namely $f(E_k(p)) = E'_{g(k)}(h(p))$ for some deterministic functions $f$, $g$, and $h$.