Return to Question

I posted this question on crypto.SE but got no answer:

Let $w = a_0 \cdot a_1 \cdots a_{n-1} $ be a word from $ \{0,1\}^n $, $|w| = n$

Let $m = \sum_{i=0}^{n-1}{ a_i \cdot 2 ^ {n-1-i} } $ be the corresponding binary number constructed from the word. Let $k= \left \lfloor \frac{n!}{2^n} \right \rfloor \cdot (m+1)$ , then $ 1 \le k \le n! $.

Compute the Lehmer-Permutation $\pi_k$ from $k$ on $n$ numbers. ( https://en.wikipedia.org/wiki/Lehmer_code )

Set $ x := \pi_k \cdot w = a_{\pi_k(0)} \cdot a_{\pi_k(1)} \cdots a_{\pi_k(n-1)} $

Then $f(w) := x$.

So the function permutes the digits in the word $w$ and the permutation is determined by $w$.

Suppose you randomly choose uniformly a word from $\{0,1\}^{1000}$ and then you apply the function. Is it practically possible to invert the constructed word? That is, does somebody have an idea on how to invert the word?

More details may be found on:

http://orgesleka.blogspot.de/2015/09/candidate-one-way-function.html

This picture shows f applied on all words of length 7:

I posted this question on crypto.SE but got no answer:

Let $w = a_0 \cdot a_1 \cdots a_{n-1} $ be a word from $ \{0,1\}^n $, $|w| = n$

Let $m = \sum_{i=0}^{n-1}{ a_i \cdot 2 ^ {n-1-i} } $ be the corresponding binary number constructed from the word. Let $k= \left \lfloor \frac{n!}{2^n} \right \rfloor \cdot (m+1)$ , then $ 1 \le k \le n! $.

Compute the Lehmer-Permutation $\pi_k$ from $k$ on $n$ numbers. ( https://en.wikipedia.org/wiki/Lehmer_code )

Set $ x := \pi_k \cdot w = a_{\pi_k(0)} \cdot a_{\pi_k(1)} \cdots a_{\pi_k(n-1)} $

Then $f(w) := x$.

So the function permutes the digits in the word $w$ and the permutation is determined by $w$.

Suppose you randomly choose uniformly a word from $\{0,1\}^{1000}$ and then you apply the function. Is it practically possible to invert the constructed word? That is, does somebody have an idea on how to invert the word?

More details may be found on:

http://orgesleka.blogspot.de/2015/09/candidate-one-way-function.html

This picture shows f applied on all words of length 7:

After two years, also posted on cs: https://cs.stackexchange.com/questions/110790/inverting-a-function

I posted this question on crypto.SE but got no answer:

Let $w = a_0 \cdot a_1 \cdots a_{n-1} $ be a word from $ \{0,1\}^n $, $|w| = n$

Let $m = \sum_{i=0}^{n-1}{ a_i \cdot 2 ^ {n-1-i} } $ be the corresponding binary number constructed from the word. Let $k= \left \lfloor \frac{n!}{2^n} \right \rfloor \cdot (m+1)$ , then $ 1 \le k \le n! $.

Compute the Lehmer-Permutation $\pi_k$ from $k$ on $n$ numbers. ( https://en.wikipedia.org/wiki/Lehmer_code )

Set $ x := \pi_k \cdot w = a_{\pi_k(0)} \cdot a_{\pi_k(1)} \cdots a_{\pi_k(n-1)} $

Then $f(w) := x$.

So the function permutes the digits in the word $w$ and the permutation is determined by $w$.

Suppose you randomly choose uniformly a word from $\{0,1\}^{1000}$ and then you apply the function. Is it practically possible to invert the constructed word? That is, does somebody have an idea on how to invert the word?

More details may be found on:

http://orgesleka.blogspot.de/2015/09/candidate-one-way-function.html

I posted this question on crypto.SE but got no answer:

Let $w = a_0 \cdot a_1 \cdots a_{n-1} $ be a word from $ \{0,1\}^n $, $|w| = n$

Let $m = \sum_{i=0}^{n-1}{ a_i \cdot 2 ^ {n-1-i} } $ be the corresponding binary number constructed from the word. Let $k= \left \lfloor \frac{n!}{2^n} \right \rfloor \cdot (m+1)$ , then $ 1 \le k \le n! $.

Compute the Lehmer-Permutation $\pi_k$ from $k$ on $n$ numbers. ( https://en.wikipedia.org/wiki/Lehmer_code )

Set $ x := \pi_k \cdot w = a_{\pi_k(0)} \cdot a_{\pi_k(1)} \cdots a_{\pi_k(n-1)} $

Then $f(w) := x$.

So the function permutes the digits in the word $w$ and the permutation is determined by $w$.

Suppose you randomly choose uniformly a word from $\{0,1\}^{1000}$ and then you apply the function. Is it practically possible to invert the constructed word? That is, does somebody have an idea on how to invert the word?

More details may be found on:

http://orgesleka.blogspot.de/2015/09/candidate-one-way-function.html

This picture shows f applied on all words of length 7: