
1. Introduction
nelement permutation P has to be recovered given information from nelement permutation Q,
where Q=VMPC_{k}(P) (e.g. n=256, k=1: Q[x]=P[P[P[x]]+1]).
By definition each element of Q is formed by k+2 (e.g. 3), usually different, elements of P.
One element of Q (e.g. Q[33]=25) can be formed by many possible configurations
of P elements (e.g. P[33]=10, P[10]=20, P[21]=25 or P[33]=1, P[1]=4, P[5]=25, etc.).
It cannot be said which of the configurations is more
probable. One of the configurations has to be picked (usually k+1 (e.g. 2)
elements of P have to be guessed) and the choice must
be verified using all those other Q elements, which use at least one of the P elements from the
picked configuration.
Each element of P is usually used to form k+2 (e.g. 3) different elements of Q. As a result,
usually (k+2)*(k+1) (e.g. 6) new elements of Q need to be inverted (all k+2 elements of
P used to form each of those Q elements need to be revealed) to verify the P elements
from the picked configuration.
This would not be difficult for a simple (e.g. triple) permutation composition, where the cycle
structure of P is retained by Q (some cycles are only shortened).
In Variably Modified Permutation Composition however the cycle structure of P is
corrupted by the addition operation(s) and cannot be easily recovered from Q.
Due to that it is usually impossible to find two different elements of Q, which use at least
k+1 (e.g. 2) exactly the same elements of P.
(This can be done easily for a simple permutation composition)
In fact only such element of Q can usually be found, name it Q[r], which uses only one of
the k+2 (e.g. 3) elements of P, used to form another Q element.
This forces the k remaining (e.g. 1) elements of P, used to form Q[r], to be guessed to make the
verification of the initial pick possible.
However at each new guessed element of P, there usually occur k+1 (e.g. 2) new elements of
Q which use this element of P and which need to be inverted to verify the guess.
The algorithm falls into a loop, where at every step usually k (e.g. 1) new elements of P
need to be guessed to verify the previously guessed elements. It quickly occurs that the
k+2 (e.g. 3) elements of P picked at the beginning of the process indirectly depend on
all n (e.g. 256) elements of Q.
The described scenario is the case usually and it is sometimes possible to benefit
from coincidences (where for example it is possible to find two elements of Q, which use
more than one (e.g. 2) exactly the same P elements (e.g. Q[2]=3: P[2]=4, P[4]=8, P[9]=3
and Q[5]=8: P[5]=9, P[9]=3, P[4]=8)).
The actual algorithm of inverting VMPC was optimized to benefit from the possible coincidences.
The average number of P elements which need to be guessed  for n=256  has been reduced to
only about 34 for 1level VMPC function, to about 57 for 2level VMPC, to about 77
for 3level VMPC and to about 92 for 4level VMPC function.
Searching through half of the possible states of these P elements takes on average about
2^{260}_{ }steps for 1level VMPC function (not 2^{268,7}), about 2^{420} for 2level VMPC, about 2^{550}_{ }for 3level
VMPC and about 2^{660} steps for_{ }4level^{ }VMPC function.

2. Algorithm of inverting the VMPC function
The fastest method of inverting the VMPC function found
derives nelement permutation P which produces a given
Q=VMPC_{k}(P) permutation, according to the following algorithm:
Notation:

P_{t} : nelement table, the searched permutation will be stored in
Argument,
Value; Base, Parameter of an element of P_{t} :
For
an element P_{t}[x]=y : x is termed the argument and
y the value.
The
base is either the argument or the value; the parameter is the
corresponding 
the
value or the argument.
Example:
for an element P_{t} [3]=5: If value 5 is the base,
argument 3 is the parameter.
1.1) Reveal one element of P_{t} by assuming P_{t}
[x]=y; where x and y are any values within range
x
{0,1,...,n1}, y
{0,1,...,n1}_{ }
1.2) Choose at random whether x is the base and y the parameter
or y the base and x the parameter_{ }
of the element P_{t}
[x]=y. Denote P_{t} [x]=y as the current element of
P_{t}.
2) Reveal all possible elements of P_{t} by running
the deducing process (see section
2.1)
3) If n elements of P_{t} have been revealed with no
contradiction in step 2: Terminate the algorithm and output P_{t}
4) If fewer than n elements of P_{t} have been revealed
with no contradiction in step 2:
4.1) Reveal a new element of P_{t}
by running the selecting process (see section 2.2).
Denote the revealed element as the current element of P_{t}.
4.2)
Save the parameter of the revealed element of P_{t}
4.3) Go to step 2
5) If a contradiction occurred in step 2:_{ }
5.1) Remove all elements of P_{t}
revealed in step 2 when the current element of P_{t}
had been revealed
5.2) Increment modulo n the parameter
of the current element of P_{t}
5.3) If
the parameter of the current element of P_{t} has returned to the
value saved in step 4.2:
5.3.1)
Remove the current element of P_{t}
5.3.2)
Denote the element, which had been the current element of P_{t}
directly before the element
removed in step 5.3.1 became the current one, as the current
element of P_{t}
5.3.3)
Go to step 5.1
6) Go to step 2
2.1. The deducing process
The deducing process reveals all possible elements of P_{t},
given Q and given the already
revealed elements of P_{t}, according to the following
algorithm:
Notation: as in section 2, with:
C,A
: temporary variables
Word
x of Statement y:
Statement
y: A set of all elements of P_{t} used to calculate
Q[y]
Word
x: xth consecutive element of P_{t} used to calculate
Q[y]:
Example
for VMPC_{2} : Q[ x ] = P[P[P[P[x]]+1]+2] :
Assume
P_{t}[2]=3, P_{t}[3]=5, P_{t}[6]=2,
P_{t}[4]=7, which produces Q[2]=7.
The elements P_{t}[2]=3, P_{t}[3]=5, P_{t}[6]=2,
P_{t}[4]=7 form statement 2.
The element P_{t}[2]=3 is word 1 of statement 2; P_{t}[3]=5
is word 2 of statement 2, etc.
1.1) Set C to 0
1.2) Set A to 0
2) If the element P_{t} [A] is revealed:
2.1) If the element P_{t} [A]
and k other revealed elements of P_{t} fit a general
pattern of k+1 words
of
any statement : Deduce the remaining word of that statement
(see example 2.1.1)_{ }
2.2)
If the deduced word is not a revealed element of P_{t} :
2.2.1)
Reveal the deduced word as an element of P_{t}
2.2.2)
Set C to 1_{ }
2.3)
If the deduced word contradicts any of the already revealed
elements of P_{t} (see
example 2.1.2) :
Output a contradiction and terminate the deducing algorithm_{ }
3.1) Increment A
3.2) If A is lower than n: Go to step 2
3.3) If C is equal 1: Go to step 1.1
Example 2.1.1)
For
VMPC_{2} : Q[ x ] = P[P[P[P[x]]+1]+2]:
Assume
that Q[0]=9 and that the following elements of P_{t}
are revealed:
P_{t}
[0]=1, P_{t} [1]=3, P_{t} [8]=9
Word
3 of statement 0 can be deduced as P_{t}'[4]=6 (P_{t}'[3+1]=82)
Example 2.1.2)
For
VMPC_{2} : Q[ x ] = P[P[P[P[x]]+1]+2]:
Assume
that Q[7]=2 and that the following elements of P_{t}
are revealed:
P_{t}
[1]=8, P_{t} [9]=3, P_{t} [5]=2 and P_{t}
[6]=1
Word
1 of statement 7, deduced as P_{t}'[7]=1, contradicts
the already revealed element P_{t} [6]=1.
2.2. The selecting process
The selecting process selects such new element of P_{t}
to be revealed which maximizes the number
of elements of P_{t} possible to deduce in further steps
of the inverting algorithm.
The selecting process outputs a selected base and a randomly
chosen parameter of a new element of P_{t}.
Notation: as in section 2.1, with:
G,R,X,Y
: temporary variables
Ta,Tv
: temporary tables
Weight
: table of numbers:
Weight[1;
2; 3; 4] = (2; 5; 9; 14); Example: Weight[3]=9
1.1) Set Ta and Tv to 0
1.2) Set G to 0
1.3) Set R to 1
2) Count the number of revealed elements of P_{t} which
fit the general pattern of words of a statement
in which an unrevealed element
of P_{t} with argument G would be word R.
Increment Ta[G] by Weight of this
number (see example 2.2.1)_{ }
3) Count the number of revealed elements of P_{t} which
fit the general pattern of words of a statement
in which an unrevealed element
of P_{t} with value G would be word R.
Increment Tv[G] by Weight of this
number_{ }
4.1) Increment R
4.2) If R is lower than k+3: Go to step 2
4.3) Increment G
4.4) If G is lower than n: Go to step 1.3
5.1) Pick any index of Ta or Tv for which the number stored
in any of the tables Ta or Tv is maximal
(see
example 2.2.2)
5.2) If the index picked in step 5.1 is an index of Ta:_{ }
5.2.1) Store this
index in variable X_{ }
5.2.2) Generate a
random number Y within range Y
{0,1,...,n1} ,_{ }
such that an element of P_{t} with value Y is not revealed
5.2.3) Output P_{t}'[X]=Y,
where X is the base and Y is the parameter
5.3) If the index picked in step 5.1 is an index of Tv:_{ }
5.3.1) Store this
index in variable Y_{ }
5.3.2) Generate a
random number X within range X
{0,1,...,n1} ,_{ }
such that an element of P_{t} with argument X is not
revealed
5.3.3) Outputs P_{t}'[X]=Y,
where Y is the base and X is the parameter
Example 2.2.1)
For
VMPC_{2} : Q[ x ] = P[P[P[P[x]]+1]+2]:
Assume
that G=8; R=2; Q[6]=1 and that the following elements of P_{t}
are revealed:
P_{t
}[6]=8, P_{t} [5]=1
There
are two revealed elements of P_{t} which fit the general
pattern of words of a statement in which
P_{t}
[8] would be word 2 : P_{t} [6]=8, P_{t} [5]=1:
word 1 word 2 word 3 word
4
P_{t}
[6]=8, P_{t} [8]=?, P_{t} [?]=?, P_{t}
[5]=1
Ta[8]
= Ta[8] + Weight[2] = Ta[8] + 5
Example 2.2.2)
Assume
Ta = (0, 5, 2, 7, 5, 7) and Tv = (2, 7, 0, 0, 5, 2)
The
maximal number stored in any of the tables is 7: Ta[3]=Ta[5]=Tv[1]=7
Pick
any of: index 3 of Ta, index 5 of Ta or index 1 of Tv
3. Example complexities of inverting the
VMPC function
Complexity of inverting the VMPC function has been approximated
as an average number of times _{ }
the deducing process in step 2 of the inverting algorithm described
in section 2 has to be run until_{ }
permutation P_{t} satisfies Q=VMPC_{k}(P_{t})
Average numbers of elements of P_{t} which need to be assumed are given in brackets in Table 1.
Complexities of inverting the VMPC function of the following
levels have been approximated:
VMPC_{1}
: Q[ x ] = P[P[ P[x]]+1]
VMPC_{2}
: Q[ x ] = P[P[P[P[x]]+1]+2]
VMPC_{3}
: Q[ x ] = P[P[P[P[P[x]]+1]+2]+3]
VMPC_{4}
: Q[ x ] = P[P[P[P[P[P[x]]+1]+2]+3]+4]
Table 1. Example complexities of inverting
the VMPC function 
Function n 
VMPC_{1} 
VMPC_{2}

VMPC_{3}

VMPC_{4} 
6 
2^{4.1} (2.3) 
2^{5.5} (3.1) 
2^{6.1} (3.3) 
2^{6.9} (3.8) 
8 
2^{5.5} (2.7) 
2^{7.5} (3.4) 
2^{8.8} (4.0) 
2^{9.8} (4.4) 
10 
2^{7.1} (3.0) 
2^{9.7} (4.0) 
2^{11.5} (4.7) 
2^{13.0} (5.2) 
16 
2^{11.5} (3.8) 
2^{16.6} (5.4) 
2^{20.4} (6.6) 
2^{23.3} (7.5) 
32 
2^{24} (6.0) 
2^{37} (9.1) 
2^{47} (11.5) 
2^{54} (13.4) 
64 
2^{53} (10.2) 
2^{84} (16.2) 
2^{108} (21.0) 
2^{127} (24.9) 
128 
2^{117} (18.5) 
2^{190} (30.0) 
2^{245} (40.0) 
2^{292} (47.0) 
256 
2^{260} (34.0) 
2^{420} (57.0) 
2^{550} (77.0) 
2^{660} (92.0) 

Example: For 1level VMPC function_{ }applied^{ }on 256element permutations about 34 elements of P_{t} need to be assumed to recover all elements of P_{t}.
Searching through_{ }half^{ }of the possible states of the 34 assumed elements takes_{ }about 2^{260} steps.

Home 
VMPC Function 
VMPCR CSPRNG 
VMPC Stream Cipher 
VMPCMAC scheme 
VMPC KSA3 algorithm 
Research 
Inverting Challenge
P vs NP Project 
VMPCrypt Application 
Permutu Game 
Publications 
About Author 
Contact



Copyright © 19992018 by Bartosz Zoltak

