Back to Homepage
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





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

Copyright © 1999-2016 Bartosz Zoltak
Supported by OHTON EXPO Okna Wroc³aw