Mittwoch, 30. September 2015

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.

Keine Kommentare:

Kommentar veröffentlichen