Distinguishing a truncated random permutation from a random function

MaRDI QIDQ6264159zbMATH OpenFDO

Authors Shoni Gilboa, Shay Gueron

Publication date 29 July 2015

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 $n$-bit string $w$, the oracle computes $f(w)$, truncates the $m$ last bits, and returns only the first $n-m$ 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^{fracm+n2})$ 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^{fracm+n2})$ 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.

This page was built for publication: Distinguishing a truncated random permutation from a random function

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6264159)