|
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 one-way 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 one-clock-cycle, 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 2260 operations. This effort can be significantly extended at only linear cost.
Adding one more one-cycle instruction to the implementation of the function increases its resistance
to inverting to an average level of about 2420 operations. Adding another one-cycle instruction raises it
to about 2550 operations and adding yet another one-cycle instruction produces a function requiring
an average computational effort of about 2660 operations to be inverted.
The simplicity of the VMPC one-way 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: n-element permutations. For simplicity of further
implementations
P
and Q are one-to-one mappings A → A, where A = {0,1,...,n-1}
k
: Level of the function; k<n
+
: addition modulo n |
Definition:
A
k-level VMPC function, referred to as VMPCk, is such
transformation of P into Q, where
Q[ x ] = P [ Pk
[ Pk-1 [...[ P1 [ P [ x ] ] ] ...] ] ],
|
x
{0,1,...,n-1}, |
Pi
is an n-element permutation such that Pi[x]
= fi (P[x]), where fi is any function
such that |
Pi[x]
P[x]
Pj[x]
for i
{1...k}, j
{1...k} / { i }. |
For
simplicity of further implementations fi is assumed
to be fi(x) = x + i
For
simplicity of future references notation Q=VMPC(P) is assumed to be equivalent to Q=VMPC1(P)
Example:
Q=VMPC1(P)
is such transformation of P into Q, where:
Q[
x ] = P[P1[P[x]]],
P1[x]=P[x]+1.
Table 1. Definitions of 1,2,3 and 4-level VMPC function
  |
Function |
Definition |
VMPC1 
VMPC2 
VMPC3 
VMPC4  |
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 3-instruction implementation of the VMPC function
Implementation of a 1-level VMPC function, where Q[x] = P[P[P[x]]+1],
for 256-element permutations P and Q in assembly language is described.
Assume that :
|
- Pa is a 257-byte 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 32-bit register stores value zero. ("AL" denotes 8 least significant bits of EAX)
- the EDX 32-bit register stores an address, where the Pa array is stored in memory
- the ECX 32-bit register specifies which element of the Q permutation to compute
Execute:
Table 2. Implementation of 1-level VMPC function |
Instruction |
Description |
MOV AL, [EDX] + ECX
MOV AL, [EDX] + EAX
MOV AL, [EDX] + EAX + 1 |
Store ECX-th element of P in AL
Store AL-th element of P in AL
Store (AL+1)-th element of P in AL |
|
|
The 3 MOV instructions in Table 2 store the ECX-th element of permutation Q,
where Q=VMPC1(P), in the AL (and EAX) register.
|
3.1. General implementation of the VMPC function
Implementation of a k-level VMPC function for n-element 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+k-1, Pa[0...n-1]=P
and Pa[n+x]=Pa[x] for x from 0 to k-1
- the EAX 32-bit register stores value zero. ("AL" denotes 8 least significant bits of EAX)
- the EDX 32-bit register stores an address, where the Pa array is stored in memory
- the ECX 32-bit register specifies which element of the Q permutation to compute
Execute:
Table 3. Implementation of k-level 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 ECX-th element of P in AL
Store AL-th 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 ECX-th element of permutation Q,
where Q=VMPCk(P), in the AL (and EAX) register.
The number of MOV instructions required to implement a k-level VMPC function is k + 2.
4. Example values of the VMPC function
Values of the 1,2,3 and 4-level VMPC function of an example 10-element
permutation P are shown in Table 4:
Table 4. Example values of the VMPC function for 10-element permutations
index |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
P |
2 |
0 |
4 |
3 |
6 |
9 |
7 |
8 |
5 |
1 |
Q1=VMPC1(P) |
9 |
3 |
8 |
6 |
5 |
4 |
1 |
7 |
2 |
0 |
Q2=VMPC2(P) |
0 |
9 |
2 |
5 |
8 |
7 |
3 |
1 |
6 |
4 |
Q3=VMPC3(P)   |
3 |
4 |
9 |
5 |
0 |
2 |
7 |
6 |
1 |
8 |
Q4=VMPC4(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 4-level VMPC function for
256-element permutations by the fastest known inverting algorithm are shown in Table 5:
Table 5. Complexities of computing / inverting the VMPC function for 256-element permutations
Function |
VMPC1 |
VMPC2 |
VMPC3 |
VMPC4 |
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 |
2260 |
2420 |
2550 |
2660 |
|
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 |
VMPC-R CSPRNG |
VMPC Stream Cipher |
VMPC-MAC scheme |
VMPC KSA3 algorithm |
Research |
Inverting Challenge
P vs NP Project |
VMPCrypt Application |
Permutu Game |
Publications |
About Author |
Contact
|