# When will a function $f$ be a truly random function?

I'm familiar with a definition of a truly random function:

$f$ is a truly random function if it was selected uniformly from the set of all the functions $f(x):\{0,1\}^{n} \to \{0,1\}^{n}$

But I'm having a struggle to figure out if a new function $g$ that was constructed with some manipulation over $f$ will be also truly random.

For example: $g(x)=f(x) \oplus f(1^{n})$ isn't truly random because $g(1^{n})=0^{n}$ and that will happens only with a neglected probability if we were choosing $g$ uniformly. I would be happy to get some intuition for when a function $g$ will likely be truly random and when not. (maybe we can start with reasoning if $g(x)=f(x)\oplus f(\lnot x$) is random or not.)

• So how I learned was that we instead reason about random permutations, which are keyed. ie. $$p :: \{0,1\}^n \times \{0,1\}^n \rightarrow \{0,1\}^n$$And so we can say it is a random permutation, if over all keys, each element in the domain mapping to each element of the co-domain is equally likely. Jun 30 '18 at 9:45

The question's definition is restricted to truly random functions from $\{0,1\}^{n}$ to itself, but has an easy and common extension to any to two finite sets.
get some intuition for when a function $g$ will likely be truly random and when not
I like this intuitive definition: a function $g:\mathcal A\to\mathcal B$ is truly random if and only if, for any $x_0\in\mathcal A$, even with knowledge of $g(x_i)$ for all elements $x_i\in\mathcal A-\{x_0\}$, one can't predict $g(x_0)$ better than by a random pick in $\mathcal B$.
Thus to prove that a function is not truly random, one wants to exhibit a particular $x_0$, a particular subset $\{x_1,x_2\dots\}=\mathcal A'\subset\mathcal A$ with $x_0\not\in\mathcal A'$, and a method allowing to predict $g(x_0)$ with probability better than $1/|\mathcal B|$ given the $g(x_i)$ going with each $x_i$.
Hint to prove that $g(x)=f(x)\oplus f(\lnot x)$ is not truly random: one can pick any $x$ for $x_0$ (when we only need a particular one), $\mathcal A'$ can contain a single well-chosen element $x_1$ (when we could pick $|\mathcal A|-1=2^n-1$), and $g(x_1)$ then allows to predict $g(x_0)$ with certainty (when any probability better than $1/|\mathcal B|=2^{-n}$ is good enough), merely by using commutativity of $\oplus$.