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

Research Project - "VMPC One-Way Function - is P=NP?"

We investigate the great secret of mathematics:

Research Project - "VMPC One-Way Function - is P=NP?"

Bartosz Zoltak

1. Purpose of the project
2. How the VMPC function works
3. Why can the VMPC function solve the P vs NP problem
4. Publications

1. Purpose of the project

The question whether P=NP is one of the great secrets of mathematics.
Clay Mathematics Institute, USA, included it in the group of seven Millennium Problems. For solving any of them it founded a prize of one million dollars. You can read more about the project e.g. on Wikipedia.

The P vs NP problem is a question if there exist problems which solutions are difficult to find but are easy to verify.

For decades no such problem has been discovered but also it hasn't been proved that such problems don't exist...

Theoretically inverting a one-way function would be such a problem. A one-way function is a transformation, which is easy to perform (it is ease to compute its value for an argument) but difficult to invert (find the argument which produced a given value).

However it is not clear whether one-way functions exist... If one was found, the great secret would be solved and we would determine that P is not equal NP.

In 1999 I discovered a function which I called "VMPC".

In 2004 I was invited to present it on the international cryptography conference, FSE. In 2006 a paper analysing this function was published at the Cambridge university.

The function has two distinctive features: it is exceptionally simple and, according to all the knowledge I am aware of, it is a one-way function.

For the function to be officially called "one way" a mathematical proof of its one-wayness is necessary.

The attempt to build such a proof is the purpose of this project.

"Nobody has ever proved one-wayness of any function so it will not happen here either" - this is the rational view of the project's chances.

However we are so passionate about the VMPC function that we devote a lot of energy to keep trying.

2. How the VMPC function works

The name of the function is an abbreviation of Variably Modified Permutation Composition. The VMPC function is a transformation of permutations. A permutation is a set of shuffled consecutive numbers.

(3,1,4,5,2) is an example permutation. Let's refer to this one as "F".

VMPC will transform the "F" permutation into a new permutation "V" according to the formula V(x) = F(F(F(x))+1):

x  1   2   3   4   5 
F(x)  3   1   4   5   2 

step 1)   1 gives 3:  F(1) = 3

step 2)   3 gives 4:  F(F(1)) = 4

step 3)   4+1=5:  This simple step is the most important. F(F(1))+1 = 5

step 4)   5 gives 2:  V(1) = F(F(F(1))+1) = 2

We have just computed the first element of the VMPC function: F(F(F(1))+1)=2. The above four steps need to be repeated for the remaining four values of x: F(F(F(2))+1)=5,  F(F(F(3))+1)=3,  F(F(F(4))+1)=4,  F(F(F(5))+1)=1.  (5+1=1 instead of 6 because there are only numbers from 1 to 5 in this permutation). We obtain that the value of the VMPC function for permutation F is (2,5,3,4,1).

Detailed documentation of the VMPC function

3. Why can the VMPC function solve the P vs NP problem

Inverting the above function is the following task: knowing that VMPC(F)=(2,5,3,4,1) we have to find F. This task appears to be so difficult that some of the elements of the searched F permutation need to be guessed. Guessing means that in practice we need to search through all the possible values of the guessed elements to hit the correct ones.

If we managed to prove that these guesses are necessary then VMPC would become the first one-way function in the world and the P vs NP problem - solved.

According to the current state of my knowledge inverting the VMPC function for a 10-element permutation requires guessing 3 elements of the permutation. Searching through all their possible values takes about 120 operations. For a 30-element permutation 6 elements need to be guessed which takes about 16 million operations. For a 250-element permutation as many as about 33 elements need to be guessed and this takes about 7000...000 operations (75 zeros in this number). This is over a billion billion billion... billions - the word "billion" is repeated 8 times.

An interesting fact is that an almost identical function G(x)=F(F(F(x))) is very easy to invert.

Nobody has ever proved the one-wayness of any function... So why do we believe that it can be possible with the VMPC function?

Because VMPC is so simple. A few lines of non-expert text was enough to explain to you how the function works...

4. Publications

1) VMPC One-Way Function and Stream Cipher, Bartosz Zoltak.
Fast Software Encryption (FSE), international cryptography conference Delhi, India, 5-7 Feb. 2004. Publication in Springer LNCS no. 3017, 2004. Download paper.

2) On inverting the VMPC one-way function, Kamil Kulesza, University of Cambridge. Information, whole paper.

3) On inverting the VMPC one-way function, Kamil Kulesza, presentation on a seminar, Mathematical Institute, Wroclaw University, Poland, 21 May 2008. Information.

4) VMPC One-Way Function and Stream Cipher - presentation on a seminar, Mathematical Institute of Polish Academy of Sciences (IM PAN) on 18 March 2004, Warsaw, Poland.

5) VMPC one-way function and VMPC-Tail-MAC authenticated encryption scheme - Presentation of a paper on the Cryptography Applications Conference Enigma 2004, 10-13 May 2004, Warsaw, Poland.

6) VMPC One-Way Function and Stream Cipher - article published by a computer magazine SOFTWARE 2.0 (currently Software Developer's Journal) issue 9 (117), September 2004, pages 26-29. See magazine cover.

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