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?
Tell me more
×
Mathematics Stack Exchange is a question and answer site for
people studying math at any level and professionals in related fields. It's 100% free, no registration required.
|
|
|||||||||||||||||
|
|
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. |
||||
|
|
|
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. |
|||
|
|
