Strong PRP ⇒ Strong TBC (LRW2)
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.