Collision free one way function

Question

I was playing with a function that I think is collision free and uninvertible assuming the hardness of integer factorization. I am unfortunately not as skilled at math as I would like to be, and do not know how to prove or disprove the function as being collision free. My only proof so far has been from unit testing all possible inputs, which for all 2 byte combinations has proven successful, but is obviously not concrete.

The algorithm iterates over a sequence of bits. It counts upwards through prime numbers, beginning at 2. For each contiguous '1' bit in the input bits, an exponent counter is incremented. When a '0' bit is encountered, the current prime is exponentiated and composed into the running output, the exponent counter reset to 0, and the current prime is set to the next prime.

For example:

"11001101"

Is interpreted as:

(2 ** 2) * (3 ** 0) * (5 ** 2) * (7 ** 1)

Is this function provably collision free, assuming the output is not truncated?

Is the function uninvertible for sufficiently large inputs/outputs?

Lastly, does the function become harder to invert if the output is modified (i.e. truncated or rotated)?

Edit in response to an answer: Let me rephrase the question to be more accurate with what I was actually doing. Suppose we iterate through integers, starting at 0 and incrementing by one. Convert each integer to it's binary form and process it in the manner described above. Do any output values produced this way ever collide?

Answer 1

No, it is not collision-free. All possible sequences of 0's produce the same output:

0    --> (2 ** 0) = 1
00   --> (2 ** 0) * (3 ** 0) = 1
000  --> (2 ** 0) * (3 ** 0) * (5 ** 0) = 1
0000 --> (2 ** 0) * (3 ** 0) * (5 ** 0) * (7 ** 0) = 1

In fact, it can be seen that $f(s) = f(s||0)$, for every bit-string $s$.

This could be easily solved by initializing the exponents to 1, and not to 0.

Anyway, I'm afraid you have not discovered anything new. The Fundamental theorem of arithmetic states that any positive integer can be represented uniquely by a product of prime numbers:

$$n = p_1^{\alpha_1}p_2^{\alpha_2} \cdots p_k^{\alpha_k} = \prod_{i=1}^{k}p_i^{\alpha_i}$$

Your idea is basically a method for interpreting the bit string as the sequence of exponents $\alpha_1, \alpha_2, ..., \alpha_{k}$.

It is also very easy to invert (leaving aside the issue of the number of trailing 0's). Let us assume that $f(s) = n$. If $n$ is divisible by 2, then the first bit of $s$ is 1. Now you divide by 2 and if the result is divisible by 2, then the next bit of $s$ is also 1. Repeat until it is not divisible by 2, and you know the next bit is 0. Repeat this process with the divisibility of 3, 5, 7, etc.

---

With respect to the new question you added: yes, there are collisions.

For example: $f(1) = f(2) = f(4) = ... = f(2^k) = 2$

In fact, for any integer $n$, it can be seen that $f(n) = f(n\cdot 2^k)$, for every integer $k>0$, which means that for each integer there are infinite collisions.

Answer 2

I'm answering the questions I posed. While cygnusv answer was correct for the idea I presented, it was not helpful to me as I had already identified and solved that issue, but failed to present the correct algorithm in my question. I'm not saying cygnusv is wrong; the answers presented are very much correct and I gave a +1. However, there were more questions that were not addressed.

The problem of zeros on the right can be fixed simply by appending a '1' bit or the string length to the input string. Now I was doing this already in the toy hash function that was using this idea, but it was applied before the unpack_factors function call so I neglected to mention it (this was completely my fault).

With this fix in place, the function gains what I will only refer to as collision resistance, with that statement being based solely on empirical testing by supplying inputs and recording outputs and not theoretical conjecture.

The hardness of factoring

In regards to the "hardness of factoring", this is something that really only applies to RSA style composition, where at least one of the factors is very far away from 0 on the number line.

Factoring numbers composed of large primes is slow because of the large number of primes to test. If a number is only composed of small primes, it can be factored efficiently even by a naive factoring algorithm.

For instance, unpacking basically any bitstring of all 1's would be equivalent to 2 ** N, where N is the length of the string. Even a basic factoring algorithm should solve this almost immediately, more or less regardless of how long the input string is.

However, unpacking a bitstring of lots 0's with a single 1 bit at the end would take significantly longer, and if the quantity of 0's was long enough to push the prime in question far enough to the right of the number line, then it would be "safe" in that it would never finish. However, in order to compose such a number, we would need to generate that prime, which is equally time consuming, and thus not a situation we can rely on.

Ouput truncation and rotation

Now, as for truncating the output, this has an interesting effect. It not only removes the collision resistance, it makes it trivial to calculate an infinite number of preimages for a given output. If you are only taking the last N bytes of output, then anything which unpacks and truncates to having those last N bytes as being the same is a preimage.

In other words, given an output, you can append any byte(s) you want to the left of it, factor it, and recover a valid preimage. While it does make it to where you won't know exactly what input produced the output, you can find an infinite set of inputs that it will reside in.

I would think rotating the output bits would increase the complexity of recovery by the max quantity of bits rotated this way when rotated by a data dependent amount, but am not totally sure. I couldn't think of any effects like what truncation has for rotation though, besides probably creating collisions.