Research Project  VMPC OneWay Function  is P=NP?
We investigate the great secret of mathematics:
VMPC OneWay Function  is P=NP?
www.vmpcrypt.com/pnp
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 oneway function would be such a problem.
A oneway 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 oneway 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 oneway function.
For the function to be officially called "one way" a
mathematical proof of its onewayness is necessary.
The attempt to build such a proof is the purpose of this project.
"Nobody has ever proved onewayness 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 oneway 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 10element permutation
requires guessing 3 elements of the permutation. Searching through all their possible values takes about 120 operations.
For a 30element permutation 6 elements need to be guessed which takes about 16 million operations.
For a 250element 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 onewayness 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 OneWay Function and Stream Cipher, Bartosz Zoltak.
Fast Software Encryption (FSE),
international cryptography conference
Delhi, India, 57 Feb. 2004. Publication in Springer LNCS no. 3017, 2004.
Download paper.
