0
$\begingroup$

Let us define a one-to-one function $f$ that maps binary strings of length $n$ to ternary strings of length $n$ such that if $x$ is random then $f(x)$ must be random. My question

Is there an algorithm that computes such function?

  • 0
    No, but there are many. You could feed your $x$ as a seed (maybe broken into pieces) to your favorite random number generator or encryption algorithm.2011-02-28

2 Answers 2

2

If the person reading the ternary string knows your algorithm, then s/he will know that $f(x)$ is not random. There are $2^n$ binary strings of length $n$, so it takes $n$ bits to select one. But there are $3^n$ ternary strings of length $n$, so it takes $n\log_2 (3)$ bits to select one. Your $f(x)$ can only have a range of $2^n$ strings, not $3^n$. However, to somebody who doesn't know your algorithm, the output can look random.

0

Continuing Ross's answer, the correct way is to take $n$ bit binary numbers to $\lfloor (\log_3 2) n \rfloor$ ternary numbers. If you choose such an $n$ so that $(\log_3) 2 n$ is close to an integer, this will be "relatively random" How close to an integer can $(\log_3 2) n$ be? Dirichlet's theorem tells us that the error can be roughly $1/n$ (this is optimal by Roth's theorem), and so letting $m = \lfloor (\log_3 2) n \rfloor$, the range of your function will be $3^{m-\Theta(1/m)} = 3^{-\Theta(1/m)} 3^m.$ As $m$ gets bigger, the range of the function becomes more and more closer to $3^m$, which makes it more and more difficult to break the function. You will need to look for that many numbers: $ \frac{1}{1 - 3^{-\Theta(1/m)}} = \Theta(m). $ In cryptography, when trying to break an $m$-digits generator, you can use polynomially many queries (in $m$). So in this sense, the function is not secure after all.