PRP ⇒ TBC (LRW1)

Fully-black-box reduction · standard model · LRW02 · security loss: the PRP distinguisher makes queries, plus additive for queries

Statement

Let be a PRP on with , and write . With tweak space , the construction

is a tweakable PRP: for all efficient making queries there is an efficient making queries with

— LRW02.

Sketch

answers each query with two calls to its own oracle. With replaced by a uniformly random permutation , the outer call evaluates at fresh points, so the answers are uniform distinct values, until two distinct queries share an inner value or an inner value equals a queried input; each pair of queries causes either event with probability , and an ideal tweak-indexed family differs from uniform distinct values only by collisions across tweaks.

Notes

  • The construction is not a strong tweakable PRP: for , the inverse queries and give , hence , which an ideal family satisfies with probability — standard.
  • Each evaluation costs two block-cipher calls; LRW2 replaces one by a hash evaluation and is a strong tweakable PRP when its block cipher is a strong PRP — LRW02.