Strong PRP ⇒ Strong TBC (LRW2)

Fully-black-box reduction · standard model · via Almost XOR-universal hashing · LRW02 · security loss: additive for queries and an -AXU hash family

Statement

Let be a strong PRP on , write , and let be an efficiently samplable and evaluable -almost XOR-universal family of functions with negligible in . With key for , the construction

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

— LRW02.

Sketch

samples and answers each query with one call to its own forward or inverse oracle. With replaced by a uniformly random permutation, the answers are distributed as under an ideal tweak-indexed family unless two queries under distinct tweaks meet at the same input or output of the permutation; stays hidden until then, so each pair of queries causes this with probability .

Notes

  • For , the family with is -AXU, since has exactly one solution for ; the additive term is then the birthday bound — standard.
  • Since for every AXU family into , the bound is never better than birthday, — standard.