Inverting a function

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:

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

Answer 1

Yes, you can use the Lehmer-Permutation to make a function that is suitable for cryptography, whose solution is just as hard as the Diffie-Helman problem. The relevant papers are:

(1) Roberto Mantaci, "A permutation representation that knows what "Eulerian" means", Discrete Mathematics and Theoretical Computer Science (4): 101–108, 2001, link.

and

(2) Iharantsoa Vero Rahrinirina, "Use of Signed Permutations in Cryptography", 2017, arXiv link.

In (1), the author shows that the Lehmer code of a permutation is a subexceedant function, and indeed you have a one-to-one correspondence between subexceedant functions and permutations. In (2), the author shows how to use a subexceedant function in cryptography. He discusses the importance of choosing a good base, just like you did by choosing $k$. For such a base, Section 3.1 shows how to do an analogue of the Diffie-Helman public key exchange with a subexceedant function. He points out in 3.4 that it's just as hard as the classic Diffie-Helman problem, i.e. hard enough for cryptography.

Lastly, the problem you raised, of choosing $w$ at random, is a special case of the public key setup of (2). Here Alice is the oracle who "knows" the random number chosen, and an attacker is trying to figure out Alice's private key based on her public key. If your choice of $k$ does what you claim on your blog (making the permutation well-distributed), then (1) and (2) show that your proposed $f$ is good for cryptography.