-1
$\begingroup$

Do the functions of the collatz conjecture and their inverses model a Trapdoor Function?

If given a, b, a^-1, b^-1 and your choice of f(x), is it “hard in the average case” to find some secret x?

I propose that the probability: Pr[f(F(f(x)))=f(x)] < n^-c =Pr[(2^-n)^2] < (n^-(n-1)) Simplifies to: 1 < (log(2)) * ((log(n))^-1) * (e^(n+1))

Looking at the picture from Wikipedia that others are referencing. Let D be the domain of all natural numbers that I can choose x from. Let R be the domain of all natural numbers that you can choose f(x) from. The arrow marked “easy” is the promise that I am choosing a natural number that can be calculated by applying functions A and B to 1.(c(x) exists) It is hard on average for you to calculate how to apply given functions A,B A^-1 and B^-1 to f(x) to return x.(Sometimes this time is less than the verification process) However, I can quickly apply A^-1 and B^-1 to x until 1 is returned, retain and reverse the order the operations applied and pass you this information (t) making finding x trivial by finding the shortest path to collision.

Improve this question
$\endgroup$
17
  • $\begingroup$ Given integer $n\ge2$ and $i\ge0$, let $c_i=1$ if $f^{i+1}(n)=f^{i}(n)/2$ and $c_i=0$ otherwise. Let $k$ be the smallest integer such that $f^k(n)=1$. Define $c(n)=c_k2^{k} + c_{k-1}2^{k-1} + \cdots + c_02^0=(c_{k-1}\cdots c_0)_2$ where the subscript "${}_2$" means binary representation. Is it correct that you are asking whether $c(n)$ could be a trapdoor function? $\endgroup$
    – John L.
    Jul 21, 2019 at 5:23
  • $\begingroup$ What is given? If $n$ is given, then of course we know $n$. If $c(n)$ is given, whose binary representation tells us the operations that have been performed in order, then we can reverse the operations to find $n$. I could not find anything that is hard here. $\endgroup$
    – John L.
    Jul 21, 2019 at 11:21
  • $\begingroup$ Understood. My claim is that it is easy to get from n to one using the collatz conjecture steps but that it is hard to find n given the inverse of the steps and a random input. Easy to verify, hard to solve? $\endgroup$
    – Lance Weingartz
    Jul 21, 2019 at 12:39
  • $\begingroup$ Given the inverse of the steps $(11111101)_2$, we can start with $1$ and perform $g_1, g_1,$$\,g_1, g_1,$$\,g_1, g_1,$$\,g_1, g_0, g_1$ in order to get the "$n$". Here $g_1(x)=2x$ and $g_0(x)=(x-1)/3$. It is very easy to solve. There is no need of a random input. $\endgroup$
    – John L.
    Jul 21, 2019 at 16:14
  • 2
    $\begingroup$ Well, it is better to raise a new question. It is not a good idea to change the question to invalidate the existing answers (and comments). $\endgroup$
    – John L.
    Jul 21, 2019 at 17:16

3 Answers 3

Reset to default
5
$\begingroup$

In order to break a one-way function, it suffices to be able to find a single preimage. Given $x$, $f(2x) = x$, so finding a preimage of an arbitrary input is easy. Hence it's not a one-way function at all.

Improve this answer
$\endgroup$
14
  • 1
    $\begingroup$ A value $x$ is a preimage of a value $y$ with respect to a function $f$ if $f(x) = y$. Nothing more, nothing less. $\endgroup$
    – Yuval Filmus
    Jul 21, 2019 at 2:42
  • 1
    $\begingroup$ The problem seems to be a basic confusion about what one-way functions are. I suggest reading a textbook. $\endgroup$
    – Yuval Filmus
    Jul 21, 2019 at 2:48
  • 2
    $\begingroup$ @LanceWeingartz I think most people here do not want to watch a video to try to understand you. So, asking people not to help you unless they watch the video, means they will likely not help you. It will be much easier to understand you if you can summarize the point of the video here and how it relates to the question. In that way, we can properly respond to what you're asking and more easily ask for clarification. $\endgroup$
    – Discrete lizard ♦
    Jul 21, 2019 at 10:14
  • 2
    $\begingroup$ @LanceWeingartz You don't make any sense. Oneway functions only make sense if there is one pre-image. Possibly if there are multiple pre-images, and they are all hard to find. For the Collatz function, every pre-image is absolutely trivial to find. Of course whether I got the number 16 by calculating f(5) = 16 or f(32) = 16 is impossible to do using mathematics, but that's completely missing the point. $\endgroup$
    – gnasher729
    Jul 21, 2019 at 10:48
  • 3
    $\begingroup$ I suggest looking at the definition of one-way function. It isn’t “easy to verify, hard to solve”. It’s a particular mathematical formulation of this idea. $\endgroup$
    – Yuval Filmus
    Jul 21, 2019 at 15:07
2
$\begingroup$

It looks like you were intuiting too fast.

Let $f_0(x)=3x+1$ and $f_1(x)=x/2$. Their inverse functions are $g_0(x)=(x-1)/3$ and $g_1(x)=2x$, respectively. The operations in Collatz conjecture is to perform $f$ repeatedly or, in other words, perform $f_1$ as long as we have an even number and $f_0$ otherwise.

Given integer $n\ge2$ and $i\ge0$, suppose $f^{k+1}(n)=1$ where $k$ is the smallest such integer. Suppose $f^{i+1}(n)=g_{c_i}(f^{i}(n))$ for all $i$, i.e., $c_i=1$ if $f^{i+1}(n)=f^{i}(n)/2$ and $c_i=0$ if $f^{i+1}(n)=3f^{i}(n)+1$. Define function $$c:\Bbb N_{\ge2}\to\Bbb N,\ c(n)=(c_kc_{k-1}\cdots c_0)_2$$

For example, since $42\stackrel{f_1}{\to}21\stackrel{f_0}{\to}64\stackrel{f_1}{\to}32\stackrel{f_1}{\to}16\stackrel{f_1}{\to}8\stackrel{f_1}{\to}4\stackrel{f_1}{\to}2\stackrel{f_1}{\to}1$, we have $c_0=1, c_1=0, c_2=1, c_3=1, c_4=1, c_5=1, c_6=1, c_7=1$ and $c(42)=(11111101)_2$.

You are asking whether $c$ might be a good candidate for a trap-door function.

However, it is easy to compute $n$ given $c(n)$. All we need to do is to perform the inverse operations to the operations encoded in the binary representation of $c(n)$.

For example, given $(11111101)_2$, we simply perform $1\stackrel{g_1}{\to}2\stackrel{g_1}{\to}4$$\stackrel{g_1}{\to}8\stackrel{g_1}{\to}16$$\stackrel{g_1}{\to}32\stackrel{g_1}{\to}64$$\stackrel{g_0}{\to}21\stackrel{g_1}{\to}42$ to recover $42$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ @LanceWeingartz Then what is the input? There must be some input. If the value $c(n)$ is given, then we can compute its binary representation easily. $\endgroup$
    – John L.
    Jul 21, 2019 at 17:57
  • $\begingroup$ Please come to collabedit.com/m4khn for a chat. $\endgroup$
    – John L.
    Jul 21, 2019 at 19:57
  • $\begingroup$ No.$\quad\quad$ $\endgroup$
    – John L.
    Jul 29, 2019 at 1:36
  • $\begingroup$ I got it! The map of 42 -> 42 is {0100000011111101} where we switch the operations at the eighth bit. Is the bit number the trapdoor? $\endgroup$
    – Lance Weingartz
    Jul 29, 2019 at 19:40
0
$\begingroup$

Your function isn't a one-to-one function. For many y, there are two different x such that f(x) = y:

If y modulo 6 = 4, then x = (y - 1) / 3 is an odd number, and f((y-1) / 3) = y.

For all y, x = 2y is an even number, and f (2x) = y.

As you see, whatever y is, the set of values x with f(x) = y is very easy to calculate. And by the definition of a one-way function, this means f(x) is not a one-way function. For a one-way function, finding any x with f(x) = y must be hard.

It is also not a "one-way trapdoor function", which would be a function where any x with f(x) = y is hard to calculate unless you know some secret. No secret needs to be known to find any x, given y.

Improve this answer
$\endgroup$
4
  • $\begingroup$ You are not given any values. You have four functions and you can choose your initial value. There exists a way to apply the four given functions to map f(x)->x. How long does it take to find this shortest path? Now consider I already know x, I can find a point where we can collide if we both have the values c(x) and c(y) and we both apply the four given functions. This act of colliding is the Trapdoor. I have been suggesting the collision take place at 1, but it does not need to. $\endgroup$
    – Lance Weingartz
    Jul 25, 2019 at 20:07
  • $\begingroup$ What you say has nothing whatsoever to do with "one-way trapdoor function". Do yourself a favour and read at the very least the wikipedia article. $\endgroup$
    – gnasher729
    Jul 27, 2019 at 19:40
  • $\begingroup$ If {fk : Dk -> Rk} maps 42 -> 253 (for example) I cannot get over the thought that inverting 253 -> 42 is near impossible without some trapdoor. The other four bulleted criteria appear to be met. $\endgroup$
    – Lance Weingartz
    Jul 28, 2019 at 11:46
  • $\begingroup$ If the map of 42 -> 42 is {0100000011111101} where we switch the operations at the eighth bit. Would the bit number and function reversal be the trapdoor? $\endgroup$
    – Lance Weingartz
    Jul 30, 2019 at 16:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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