1
$\begingroup$

I posted this question on mathoverflow two years ago 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 all words of length 7 when f is applied on those words: graph-7

Improve this question
$\endgroup$
4
  • $\begingroup$ If I understand correctly, given a binary string w, compute: 1. k as shown above 2. The factoradic representation of k (en.wikipedia.org/wiki/Factorial_number_system#Definition) 3. Apply this factoradic to w $\endgroup$
    – hLk
    Commented Jun 17, 2019 at 19:56
  • $\begingroup$ @KhanPower: Yes this is the definition of the function. $\endgroup$
    – user41014
    Commented Jun 17, 2019 at 19:58
  • $\begingroup$ this question has an answer at mathoverflow $\endgroup$
    – user41014
    Commented Jun 24, 2019 at 5:19
  • $\begingroup$ I'm voting to close this question because it was cross-posted on Math Overflow. $\endgroup$
    – D.W. ♦
    Commented Nov 13, 2019 at 2:45

0

Reset to default