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:

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 I am so passionate and have so much belief in the VMPC function that I 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. Its popular definition is F(F(F(x))+1) The function itself is so easy that is not even necessary to be interested in mathematics to understand it. The diagram below illustrates how F(F(F(1))+1) is evaluated.

Here you can find the more detailed explanation how the VMPC function works and why it is hard to onvert.

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.

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.

Copyright © 1999-2018 by Bartosz Zoltak