Distinguishing a truncated random permutation from a random function

Shoni Gilboa, Shay Gueron

An oracle chooses a function $f$ from the set of $n$ bits strings to itself, which is either a randomly chosen permutation or a randomly chosen function. When queried by an $n$-bit…