 VMPC One-Way Function P vs NP Project VMPC Encryption Technology VMPC-R CSPRNG VMPCrypt Application Permutu Game Publications About Author Contact

 VMPC One-Way Function 1. Introduction 2. Definition of the VMPC function 3. The 3-instruction implementation of the VMPC function     3.1. General implementation of the VMPC function 4. Example values of the VMPC function 5. Complexities of computing / inverting the VMPC function 6. Inverting the VMPC function VMPC function inverting challenge Download FSE'04 paper "VMPC One-Way Function and Stream Cipher": vmpc.pdf (171 KB) vmpc.ps (289 KB) vmpc.dvi (55 KB) Earlier paper "VMPC One-Way Function" available also at IACR ePrint archive

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

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=Pa.
- 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 computationaloperations 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 