
NOTE: You are reading a legacy documentation from 2004.
The newer description of the VMPC function can be found here.
1. Introduction
VMPC is an abbreviation of Variably Modified Permutation Composition.
The VMPC oneway function is a combination of triple permutation composition and integer addition.
It differs from a simple triple permutation composition with one integer addition operation performed
on some of the elements of the permutation. The consequence of this addition operation is corruption of
cycle structure of the transformed permutation  the fundamental source of the function's
resistance to inverting.
The VMPC function has a simple formal definition and the value of the function can
be computed with 3 oneclockcycle, instructions of an Intel 80486 and
newer or compatible processor per byte.
Inverting the function by_{ }the^{ }fastest known inverting algorithm is estimated to require an average computational
effort of about 2^{260} operations. This_{ }effort can be significantly extended at only linear cost.
Adding one more onecycle instruction to the implementation of the_{ }function^{ }increases its resistance
to inverting to an average level of about 2^{420} operations. Adding_{ }another onecycle instruction raises it
to about 2^{550} operations_{ }and adding yet another^{ }onecycle instruction produces a function requiring
an average computational_{ }effort of about 2^{660} operations to be inverted.
The simplicity of the VMPC oneway function could raise a question whether it might be possible to prove the
lower bound on the complexity of inverting it. This currently is an open problem and a
possible subject of future research.
The more detailed explanation of why the VMPC function it hard to invert is to be found in
6. Inverting the VMPC function

2. Definition of the VMPC function
Notation:

n,
P, Q : P and Q: nelement permutations. For simplicity of further
implementations
P
and Q are onetoone mappings A → A, where A = {0,1,...,n1}
k
: Level of the function; k<n
+
: addition modulo n 
Definition:
A
klevel VMPC function, referred to as VMPC_{k}, is such
transformation of P into Q, where
Q[ x ] = P [ P_{k}
[ P_{k1} [...[ P_{1} [ P [ x ] ] ] ...] ] ],

x
{0,1,...,n1}, 
P_{i}_{
}is an nelement permutation such that P_{i}[x]
= f_{i} (P[x]), where f_{i} is any function
such that 
P_{i}[x]
P[x]
P_{j}[x]
for i
{1...k}, j
{1...k} / { i }. 
For
simplicity of further implementations f_{i} is assumed
to be f_{i}(x) = x + i
For
simplicity of future references notation Q=VMPC(P) is assumed to be equivalent to Q=VMPC_{1}(P)
Example:
Q=VMPC_{1}(P)
is such transformation of P into Q, where:
Q[
x ] = P[P_{1}[P[x]]],
P_{1}[x]=P[x]+1.
Table 1. Definitions of 1,2,3 and 4level VMPC function

Function 
Definition 
VMPC_{1}
VMPC_{2}
VMPC_{3}
VMPC_{4} 
Q[x]=P[P[P[x]]+1]
Q[x]=P[P[P[P[x]]+1]+2]
Q[x]=P[P[P[P[P[x]]+1]+2]+3]
Q[x]=P[P[P[P[P[P[x]]+1]+2]+3]+4] 


3. The 3instruction implementation of the VMPC function
Implementation of a 1level VMPC function, where Q[x] = P[P[P[x]]+1],
for 256element permutations P and Q in assembly language is described.
Assume that :

 Pa is a 257byte array indexed by numbers from 0 to 256, the P permutation is stored in the array
at indexes from 0 to 255 (Pa[0...255]=P) and that Pa[256]=Pa[0].
 the EAX 32bit register stores value zero. ("AL" denotes 8 least significant bits of EAX)
 the EDX 32bit register stores an address, where the Pa array is stored in memory
 the ECX 32bit register specifies which element of the Q permutation to compute
Execute:
Table 2. Implementation of 1level VMPC function 
Instruction 
Description 
MOV AL, [EDX] + ECX
MOV AL, [EDX] + EAX
MOV AL, [EDX] + EAX + 1 
Store ECXth element of P in AL
Store ALth element of P in AL
Store (AL+1)th element of P in AL 


The 3 MOV instructions in Table 2 store the ECXth element of permutation Q,
where Q=VMPC_{1}(P), in the AL (and EAX) register.

3.1. General implementation of the VMPC function
Implementation of a klevel VMPC function for nelement permutations P and Q
in assembly language is described.
Assume that :

 Pa is an (n+k)byte array indexed by numbers from 0 to n+k1, Pa[0...n1]=P
and Pa[n+x]=Pa[x] for x from 0 to k1
 the EAX 32bit register stores value zero. ("AL" denotes 8 least significant bits of EAX)
 the EDX 32bit register stores an address, where the Pa array is stored in memory
 the ECX 32bit register specifies which element of the Q permutation to compute
Execute:
Table 3. Implementation of klevel VMPC function 
Instruction 
Description 
MOV AL, [EDX] + ECX
MOV AL, [EDX] + EAX
MOV AL, [EDX] + EAX + 1
MOV AL, [EDX] + EAX + 2
...
MOV AL, [EDX] + EAX + k 
Store ECXth element of P in AL
Store ALth element of P in AL
Store (AL+1)th element of P in AL
Store (AL+2)th element of P in AL
...
Store (AL+k)th element of P in AL 


The MOV instructions in Table 3 store the ECXth element of permutation Q,
where Q=VMPC_{k}(P), in the AL (and EAX) register.
The number of MOV instructions required to implement a klevel VMPC function is k + 2.
4. Example values of the VMPC function
Values of the 1,2,3 and 4level VMPC function of an example 10element
permutation P are shown in Table 4:
Table 4. Example values of the VMPC function for 10element permutations
index 
0 
1 
2 
3 
4 
5 
6 
7 
8 
9 
P 
2 
0 
4 
3 
6 
9 
7 
8 
5 
1 
Q_{1}=VMPC_{1}(P) 
9 
3 
8 
6 
5 
4 
1 
7 
2 
0 
Q_{2}=VMPC_{2}(P) 
0 
9 
2 
5 
8 
7 
3 
1 
6 
4 
Q_{3}=VMPC_{3}(P) 
3 
4 
9 
5 
0 
2 
7 
6 
1 
8 
Q_{4}=VMPC_{4}(P) 
8 
5 
3 
1 
6 
7 
0 
2 
9 
4 

5. Complexities of computing / inverting the VMPC function
Efforts required to compute and to invert the 1,2,3 and 4level VMPC function for
256element permutations by the fastest known inverting algorithm are shown in Table 5:
Table 5. Complexities of computing / inverting the VMPC function for 256element permutations
Function 
VMPC_{1} 
VMPC_{2} 
VMPC_{3} 
VMPC_{4} 
Number of MOV instructions required to compute
one byte of the value of the function 
3 
4 
5 
6 
Estimated average number of computational operations
required to invert the function 
2^{260} 
2^{420} 
2^{550} 
2^{660} 

For a detailed description of the algorithm of inverting the VMPC function and example
complexities of inverting the function for permutation sizes smaller than 256,
see 6. Inverting the VMPC function
For a proposed practical application of the VMPC Function in an
encryption algorithm, see VMPC Stream Cipher

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
