Research Project  "VMPC OneWay Function  is P=NP?"
We investigate the great secret of mathematics:
Research Project  "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 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 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. A few lines of nonexpert text was enough to explain
to you how the function works...
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.
2) On inverting the VMPC oneway function, Kamil Kulesza, University of Cambridge.
Information,
whole paper.
3) On inverting the VMPC oneway function, Kamil Kulesza, presentation on a seminar,
Mathematical Institute, Wroclaw University, Poland, 21 May 2008.
Information.
4) VMPC OneWay 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 oneway function and VMPCTailMAC authenticated encryption scheme  Presentation of a paper on the
Cryptography Applications Conference
Enigma 2004,
1013 May 2004, Warsaw, Poland.
6) VMPC OneWay Function and Stream Cipher  article published by a computer magazine
SOFTWARE 2.0 (currently Software Developer's Journal)
issue 9 (117), September 2004, pages 2629. See magazine cover.
