1
$\begingroup$

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.)

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Jackoson Jun 30 '18 at 9:45
3
$\begingroup$

definition of a truly random function

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$.

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.