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