Tweakable block cipher
A tweakable block cipher (TBC) is a keyed family of permutations of a domain , indexed by a public tweak as well as the key, that no efficient adversary can distinguish from a family of independent uniformly random permutations, one per tweak, given oracle access to it — LRW02.
Syntax
A TBC is a triple of efficient algorithms with respect to keyspace , tweak space , and domain :
- is a randomized algorithm that samples a key
- is a deterministic algorithm that takes a key , a tweak and an input , outputting
- is a deterministic algorithm that takes a key , a tweak and an input , outputting
For every key and tweak , is a bijection on . The map , , is the usual notation. A PRP is the case .
Properties
Correctness
A TBC is correct if for all , and ,
Security
The ideal world samples an independent uniformly random permutation of for every tweak; chooses the tweak of each query.
\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{tprp}}_{\mathsf{TBC},\calA}(\secpar)$}
\begin{algorithmic}
\State $k \gets \KeyGen(1^\secpar)$; $b \getsr \bits$
\State $\pi_t \getsr \Perms(\calD)$ independently for each $t \in \calT$
\Comment{Can be sampled lazily}
\State $\calO_0(t, x) := \Eval(k, t, x)$
\State $\calO_1(t, x) := \pi_t(x)$
\State $b' \gets \calA^{\calO_b}(1^\secpar)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}
A TBC is a tweakable PRP if for all efficient ,
is negligible — LRW02.
Strong security
In the strong tweakable PRP game, additionally receives an inverse oracle, again with a tweak of its choice.
\begin{algorithm}
\algname{Game}
\caption{$\Game^{\mathrm{tsprp}}_{\mathsf{TBC},\calA}(\secpar)$}
\begin{algorithmic}
\State $k \gets \KeyGen(1^\secpar)$; $b \getsr \bits$
\State $\pi_t \getsr \Perms(\calD)$ independently for each $t \in \calT$
\Comment{Can be sampled lazily}
\State $\calO_0(t, x) := \Eval(k, t, x)$ ; $\calO_0^{-1}(t, y) := \Invert(k, t, y)$
\State $\calO_1(t, x) := \pi_t(x)$ ; $\calO_1^{-1}(t, y) := \pi_t^{-1}(y)$
\State $b' \gets \calA^{\calO_b,\calO_b^{-1}}(1^\secpar)$
\Return $[b' = b]$
\end{algorithmic}
\end{algorithm}
A TBC is a strong tweakable PRP if for all efficient ,
is negligible — LRW02. A strong tweakable PRP is a tweakable PRP (Strong TBC ⇒ TBC); the LRW1 construction is a tweakable PRP whenever its block cipher is a PRP on with , and four queries distinguish it from an ideal family once inverse queries are allowed — standard.
Variations
Tweakable enciphering schemes
A tweakable enciphering scheme has a domain of bit strings of several lengths, and each is a length-preserving permutation of . Its security is the strong game above with each a uniformly random length-preserving permutation of — HR03.
Other results
Participates in
Builds on Tweakable block cipher
Produces Tweakable block cipher