Paper 2015/773
Distinguishing a truncated random permutation from a random function
Shoni Gilboa and Shay Gueron
Abstract
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 nbit string w, the oracle computes f(w), truncates the m last bits, and returns only the first nm bits of f(w). How many queries does a querying adversary need to submit in order to distinguish the truncated permutation from a random function? In 1998, Hall et al. showed an algorithm for determining (with high probability) whether or not f is a permutation, using O ( 2^((m+n)/2) ) queries. They also showed that if m < n/7, a smaller number of queries will not suffice. For m > n/7, their method gives a weaker bound. In this manuscript, we show how a modification of the method used by Hall et al. can solve the porblem completely. It extends the result to essentially every m, showing that Omega ( 2^((m+n)/2) ) queries are needed to get a nonnegligible distinguishing advantage. We recently became aware that a better bound for the distinguishing advantage, for every m<n, follows from a result of Stam published, in a different context, already in 1978.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Preprint. MINOR revision.
 Keywords
 Pseudo random permutationspseudo random functionsadvantage
 Contact author(s)
 shay @ math haifa ac il
 History
 20150803: received
 Short URL
 https://ia.cr/2015/773
 License

CC BY
BibTeX
@misc{cryptoeprint:2015/773, author = {Shoni Gilboa and Shay Gueron}, title = {Distinguishing a truncated random permutation from a random function}, howpublished = {Cryptology ePrint Archive, Paper 2015/773}, year = {2015}, note = {\url{https://eprint.iacr.org/2015/773}}, url = {https://eprint.iacr.org/2015/773} }