Candidate One Way Function

The construction of the function goes like this: The main idea is the construction of a "random" permutation on words of fixed size and then applying this permutation to the given word. 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/Factorial_number_system, 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$. One might first ask, why the construction with $k$ is needed, and why one might not just compute the Lehmer-Permutation of $m$ instead. This is done so that the permutation is better distributed among the numbers $1 ,\ldots, n!$. Otherwise since $2^n << n!$ the permutation $\pi_m$ will have to many fixed points $\pi_m(i) = i$ for $1 \le i \le L$ for some $L$ . One possible attack would be given a word $x = f(w)$ with $l$ zeros and $n-l$ ones, to consider all words $y$ with $l$ zeros and $n-l$ ones and then compute $f(y)$ of such words. There are exactly $\binom{n}{l}$ such words. This attack would function if $l$ is either too small or too large. Since as is known the $\binom{n}{l}$ takes the maximum value at the central binomial coefficient (the middle term), we might conjecture, that words with $l=\frac{n}{2}$ zeros and $n-l=\frac{n}{2}$ ones are hard to attack. But for some random word $w$, the expeted number of zeros and ones is equal to $l = n-l = \frac{n}{2}$. Hence since the central binomial coefficient fullfills the inequality: $$\binom{n}{n/2} \ge \frac{2^n }{ \sqrt{2 \cdot n} }$$ we might conjecture, that the work to be done to invert such words is exponential in $n$. Here are some small examples, all words of length $n = 4$:

m=0, n=4, k=1
Lehmer-Code = (Factorial-Digits of m) = [0, 0, 0, 0]
pi_k = [0, 1, 2, 3]
w= [0, 0, 0, 0]
pi_k*w= [0, 0, 0, 0]
m=1, n=4, k=2
Lehmer-Code = (Factorial-Digits of m) = [0, 0, 1, 0]
pi_k = [0, 1, 3, 2]
w= [0, 0, 0, 1]
pi_k*w= [0, 0, 1, 0]
m=2, n=4, k=3
Lehmer-Code = (Factorial-Digits of m) = [0, 1, 0, 0]
pi_k = [0, 2, 1, 3]
w= [0, 0, 1, 0]
pi_k*w= [0, 1, 0, 0]
m=3, n=4, k=4
Lehmer-Code = (Factorial-Digits of m) = [0, 1, 1, 0]
pi_k = [0, 2, 3, 1]
w= [0, 0, 1, 1]
pi_k*w= [0, 1, 1, 0]
m=4, n=4, k=5
Lehmer-Code = (Factorial-Digits of m) = [0, 2, 0, 0]
pi_k = [0, 3, 1, 2]
w= [0, 1, 0, 0]
pi_k*w= [0, 0, 1, 0]
m=5, n=4, k=6
Lehmer-Code = (Factorial-Digits of m) = [0, 2, 1, 0]
pi_k = [0, 3, 2, 1]
w= [0, 1, 0, 1]
pi_k*w= [0, 1, 0, 1]
m=6, n=4, k=7
Lehmer-Code = (Factorial-Digits of m) = [1, 0, 0, 0]
pi_k = [1, 0, 2, 3]
w= [0, 1, 1, 0]
pi_k*w= [1, 0, 1, 0]
m=7, n=4, k=8
Lehmer-Code = (Factorial-Digits of m) = [1, 0, 1, 0]
pi_k = [1, 0, 3, 2]
w= [0, 1, 1, 1]
pi_k*w= [1, 0, 1, 1]
m=8, n=4, k=9
Lehmer-Code = (Factorial-Digits of m) = [1, 1, 0, 0]
pi_k = [1, 2, 0, 3]
w= [1, 0, 0, 0]
pi_k*w= [0, 0, 1, 0]
m=9, n=4, k=10
Lehmer-Code = (Factorial-Digits of m) = [1, 1, 1, 0]
pi_k = [1, 2, 3, 0]
w= [1, 0, 0, 1]
pi_k*w= [0, 0, 1, 1]
m=10, n=4, k=11
Lehmer-Code = (Factorial-Digits of m) = [1, 2, 0, 0]
pi_k = [1, 3, 0, 2]
w= [1, 0, 1, 0]
pi_k*w= [0, 0, 1, 1]
m=11, n=4, k=12
Lehmer-Code = (Factorial-Digits of m) = [1, 2, 1, 0]
pi_k = [1, 3, 2, 0]
w= [1, 0, 1, 1]
pi_k*w= [0, 1, 1, 1]
m=12, n=4, k=13
Lehmer-Code = (Factorial-Digits of m) = [2, 0, 0, 0]
pi_k = [2, 0, 1, 3]
w= [1, 1, 0, 0]
pi_k*w= [0, 1, 1, 0]
m=13, n=4, k=14
Lehmer-Code = (Factorial-Digits of m) = [2, 0, 1, 0]
pi_k = [2, 0, 3, 1]
w= [1, 1, 0, 1]
pi_k*w= [0, 1, 1, 1]
m=14, n=4, k=15
Lehmer-Code = (Factorial-Digits of m) = [2, 1, 0, 0]
pi_k = [2, 1, 0, 3]
w= [1, 1, 1, 0]
pi_k*w= [1, 1, 1, 0]
m=15, n=4, k=16
Lehmer-Code = (Factorial-Digits of m) = [2, 1, 1, 0]
pi_k = [2, 1, 3, 0]
w= [1, 1, 1, 1]
pi_k*w= [1, 1, 1, 1]

As one can see for $m=9$ and $m=10$ (we have in both cases $\pi_k \cdot w = 0011$), the function is in general neither surjective nor injective. I have implemented this idea in python, and here is a nontrivial example on $150$ bits which runs in under one second even though implemented in python:

w = [1, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 0]
m=1279607855208070195064338423740863454312235238, n=150, k=51223701589084024400750942404902242134696092112154131410359938801887859702545711950279545972412289530642923770897655341449893740303460239109720926509319367414721427119543767321207725214681463099908033034573794457858117619817707577286035424763678710865742056652800
pi_k = [134, 72, 4, 119, 108, 25, 91, 73, 112, 107, 32, 29, 54, 58, 80, 8, 94, 123, 38, 36, 69, 135, 127, 51, 141, 20, 124, 106, 83, 97, 82, 44, 55, 27, 3, 138, 52, 113, 118, 43, 147, 59, 34, 132, 45, 26, 121, 24, 18, 2, 11, 6, 126, 130, 81, 12, 48, 139, 1, 142, 46, 47, 120, 71, 88, 140, 104, 100, 23, 40, 143, 63, 9, 122, 136, 5, 67, 105, 33, 57, 84, 15, 49, 76, 98, 102, 111, 70, 41, 60, 86, 16, 13, 89, 22, 77, 17, 61, 129, 75, 21, 131, 62, 19, 95, 117, 78, 101, 109, 56, 90, 68, 7, 137, 53, 110, 146, 30, 125, 14, 96, 28, 50, 31, 114, 37, 148, 93, 144, 145, 133, 115, 92, 149, 87, 64, 42, 65, 79, 66, 39, 85, 74, 35, 128, 116, 103, 99, 10, 0]
pi_k * w = [1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1]

Here is the python code, to compute the function:

#!/usr/bin/python
import math
from itertools import permutations
import random

def getPermFromLehmer(fnr,n):
  # gives the permutation from lehmer-code: 
  # for example 4041000 -> (4,0,6,2,1,3,5)
  l = range(n)
  perm = []
  for d in fnr:
    perm.append(l.pop(d))
  return perm

def getPermutations(n):
  perms = permutations(range(0,n))
  return list(perms)

def getFactoradicDigits(num,d):
  digits = []
  i = 1
  while num > 0:
    rem = num % i
    num = num / i
    i += 1
    digits.append(rem)
  digits.reverse()
  diff = d - len(digits)
  newDigits = diff * [0]
  newDigits.extend(digits)
  return newDigits

def getLehmerCode(p):
  if len(set(p)) != len(p):
    return "is not a permutation"
  else:
    l = []
    for i in range(len(p)):
      pi = p[i]
      di = len([1 for pj in p[(i+1):] if pj < pi ])
      l.append(di)
    return l

def getFactoradicNumber(perm):
  lehmerCode = getLehmerCode(perm)
  n = len(perm)
  return sum([lehmerCode[i]*math.factorial(n-1-i) for i in range(n)])+1

def getPermFromNr(n,d):
  return getPermFromLehmer(getFactoradicDigits(n-1,d),d)


def getRandomBits(n):
  return [random.randint(0,1) for i in range(n)]

def computeNFromBits(r):
  l = len(r)
  return sum([2**(l-1-i)*r[i] for i in range(l)])


def applyPerm(perm,l):
  if not len(perm)==len(l):
    return None
  else:
    return [l[perm[i]] for i in range(len(perm))]


def f(bits):
  m = computeNFromBits(bits)
  if m == 0:
    m = 1
  n = len(bits)
  k = int(math.floor(math.factorial(n)/(2**n*1.0)))*(m+1)
  print "m=%s, n=%s, k=%s" % (m,n, k)
  perm = getPermFromNr(k,len(bits))
  print "pi_k = %s" % perm
  bitsPerm = applyPerm(perm,bits)
  return bitsPerm

def digits(n,d):
  k = n
  dig = []
  while k> 0:
    dig.append(k%d)
    k = k/d
  dig.reverse()   
  return dig


def computeAll(m):
  p = getPermutations(m)
  for i in range(0,2**m):
    r = digits(i,2)
    if len(r) < m:
       diff = (m-len(r))*[0]
       r.reverse()
       r.extend(diff)
       r.reverse()
    rPerm = f(r)
    print "w= %s" % r
    print "pi_k*w= %s" % rPerm
  for x in p:
    print x, getLehmerCode(x), getFactoradicNumber(x), getPermFromNr(getFactoradicNumber(x),m)


if __name__=='__main__':
  computeAll(3)
  r = getRandomBits(150)
  rPerm = f(r)
  print "w= %s" % r
  print "pi_k*w= %s" % rPerm

If someone has an idea on how to invert the function, please let me know.