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 non-negligible 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.Category / Keywords: foundations / Pseudo random permutations, pseudo random functions, advantage Date: received 3 Aug 2015 Contact author: shay at math haifa ac il Available format(s): PDF | BibTeX Citation Version: 20150803:191821 (All versions of this report) Short URL: ia.cr/2015/773 Discussion forum: Show discussion | Start new discussion