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?


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.

I believe I managed to build a successful proof in the years 2004-2014. Since 2014 I have been working on writing down this proof in a paper.

As of January 2019 the paper is almost finished and takes 72 A4 pages.


2. Formal definitions

Formal definition of the VMPC function:



Formal definition of a one-way function:




3. Reader-friendly explanation of the VMPC one-way function

The name of the function is an abbreviation of Variably Modified Permutation Composition. Its popular definition is F(F(F(x))+1)

The idea of the VMPC function F(F(F(x))+1) is best illustrated when compared to a "standard" function F(F(F(x))).

Formally the diagram contains some permutation F in two-line notation.

Let's see how F(F(F(1))) is evaluated:


Following the blue line we read from the diagram that:
(1 2) (below number 1 lies number 2, formally F(1)=2)
(2 6) (below number 2 lies number 6, formally F(2)=6)
(6 3) (below number 6 lies number 3, formally F(6)=3)
And that's it!
we have just evaluated that F(F(F(1)))=3.


Now, by contrast, let's see how the VMPC function F(F(F(1))+1) is evaluated:


Just like above, following the blue line, we read from the diagram that
(1 2) (below number 1 lies number 2, formally F(1)=2)
(2 6) (below number 2 lies number 6, formally F(2)=6)

And here comes the tricky part, which is the essence of the VMPC function:

We increase 6 by 1. We get 6 + 1 = 7.

Only now do we check in the diagram that
(7 4) (below number 7 lies number 4, formally F(7)=4)

And so we get the value of the VMPC function: F(F(F(1))+1)=4.

And that's about it! Simple, isn't it?
All about the VMPC function is just to add 1 at the right place! Nothing more!

What is astounding or almost magical, are the consequences of this innocent +1 operation.

Normally each function has its inverse. For example, if we add 10 + 5 = 15, then to get back from 15 to 10, we need to just subtract 15 - 5 = 10. Subtraction is the inverse of addition. However the VMPC function appears to be the first function in the world which has no inverse!

It means that if we hide the numbers in the bottom row of the diagram, we cannot recover them from the values of the VMPC function! Even despite the fact that these values are so easy to evaluate!

The cool part is that to actually understand why it happens, you still don't need to be a mathematician! It is so simple! So I hope you will follow up reading!

The hard part was to prove it formally. This took me over 14 years from publishing the function at the FSE 2004 conference in India. And I am almost done.

Let's first evaluate all the remaining values, just like we did above by following the blue line.



Let's evaluate F(F(F(2)))


Following the blue line we read from the diagram that:
(2 6) (below number 2 lies number 6, formally F(2)=6)
(6 3) (below number 6 lies number 3, formally F(6)=3)
(3 7) (below number 3 lies number 7, formally F(3)=7)
We have just evaluated that
F(F(F(2)))=7


And now let's evaluate VMPC: F(F(F(2))+1)


(2 6) (below number 2 lies number 6, formally F(2)=6)
(6 3) (below number 6 lies number 3, formally F(6)=3)
The VMPC trick: 3 + 1 = 4
(4 5) (below number 4 lies number 5, formally F(4)=5)

We get the value of the VMPC function: F(F(F(2))+1)=5



Let's evaluate F(F(F(3)))


(3 7), formally F(3)=7
(7 4), formally F(7)=4
(4 5), formally F(4)=5

So we get F(F(F(3)))=5


And now VMPC: F(F(F(3))+1)


(3 7), formally F(3)=7
(7 4), formally F(7)=4
VMPC trick: 4 + 1 = 5
(5 1), formally F(5)=1

We get another VMPC value: F(F(F(3))+1)=1



Let's evaluate F(F(F(4)))


(4 5), formally F(4)=5
(5 1), formally F(5)=1
(1 2), formally F(1)=2

So we get F(F(F(4)))=2


And now VMPC: F(F(F(4))+1)


(4 5), formally F(4)=5
(5 1), formally F(5)=1
VMPC trick: 1 + 1 = 2
(2 6), formally F(2)=6

We get another VMPC value: F(F(F(4))+1)=6



Let's evaluate F(F(F(5)))


(5 1), formally F(5)=1
(1 2), formally F(1)=2
(2 6), formally F(2)=6

So we get F(F(F(5)))=6


And now VMPC: F(F(F(5))+1)


(5 1), formally F(5)=1
(1 2), formally F(1)=2
VMPC trick: 2 + 1 = 3
(3 7), formally F(3)=7

We get another VMPC value: F(F(F(5))+1)=7



Let's evaluate F(F(F(6)))


(6 3), formally F(6)=3
(3 7), formally F(3)=7
(7 4), formally F(7)=4

So we get F(F(F(6)))=4


And now VMPC: F(F(F(6))+1)


(6 3), formally F(6)=3
(3 7), formally F(3)=7
VMPC trick: 7 + 1 = 8 = 1
We got an 8, but we only use numbers from 1 to 7, so we reset this 8 into 1 (analogously to addition modulo 8).
(1 2), formally F(1)=2

We get another VMPC value: F(F(F(6))+1)=2



Let's evaluate F(F(F(7)))


(7 4), formally F(7)=4
(4 5), formally F(4)=5
(5 1), formally F(5)=1

So we get F(F(F(7)))=1


And now VMPC: F(F(F(7))+1)


(7 4), formally F(7)=4
(4 5), formally F(4)=5
VMPC trick: 5 + 1 = 6
(6 3), formally F(6)=3

We get another VMPC value: F(F(F(7))+1)=3



Now let's collect all the 7 values of F(F(F(x))) which we have just evaluated above

(1 2)(2 6)(6 3) determined that F(F(F(1)))=3
(2 6)(6 3)(3 7) determined that F(F(F(2)))=7
(3 7)(7 4)(4 5) determined that F(F(F(3)))=5
(4 5)(5 1)(1 2) determined that F(F(F(4)))=2
(5 1)(1 2)(2 6) determined that F(F(F(5)))=6
(6 3)(3 7)(7 4) determined that F(F(F(6)))=4
(7 4)(4 5)(5 1) determined that F(F(F(7)))=1

Look closer at all the pairs of numbers on the left, like (1 2)(2 6)(6 3). You might notice that when we take the 2 leftmost pairs, (1 2)(2 6), then we can find those exactly pairs, as 2 rightmost pairs in some other row! Here in row 5: (5 1)(1 2)(2 6).

You can try to do the same with any other row you like...

In fact, with the F(F(F(x))) function you can do it with any row you want! The 2 leftmost pairs will always fit as 2 rightmost pairs in some other row.

Both the 2 leftmost and the 2 rightmost pairs have the same general form (A B)(B C). That's why it is always possible to find two rows where the 2 leftmost pairs in one row are the same as the 2 rightmost pairs in the other row.

This enables to perform a deducing chain, where such pairs of rows are consecutively found revealing one new element of F at each step until the whole F is revealed (i.e. the F(F(F(x))) function is inverted).


Now let's try VMPC:

First, like above, let's collect all the 7 values of the VMPC function F(F(F(x))+1)

(1 2)(2 6)(7 4) determined that F(F(F(1))+1)=4
(2 6)(6 3)(4 5) determined that F(F(F(2))+1)=5
(3 7)(7 4)(5 1) determined that F(F(F(3))+1)=1
(4 5)(5 1)(2 6) determined that F(F(F(4))+1)=6
(5 1)(1 2)(3 7) determined that F(F(F(5))+1)=7
(6 3)(3 7)(1 2) determined that F(F(F(6))+1)=2
(7 4)(4 5)(6 3) determined that F(F(F(7))+1)=3


We can see that whichever row we take, the 2 leftmost pairs cannot be fitted as 2 rightmost pairs in any other row. This happens because of the "+1" operation. The 2 leftmost pairs take a general form (A B)(B C). The 2 rightmost pairs take a general form (A B)(B+1 C). And B+1 cannot be equal to B. Thus the 2 leftmost pairs can never become 2 rightmost pairs in any other row.

This simple fact has severe consequences for inverting the VMPC function. As a result of this fact it impossible to perform the deducing chain, as described above for the F(F(F(x))) function. In VMPC to achieve a situation where 2 given pairs occur in one row, we must usually take those pairs from 2 other different rows. This complicates the inverting process severely.

This simple to observe feature is the conceptual reason why VMPC has the "magical" power of being impossible to invert. Or in other words - one-way.

To invert VMPC, it is necessary to first guess about 1/8 of all the elements of F, plus 2 more. Only then is it possible to match the guessed pairs into some rows, deduce some new elements from these rows, match the deduced ones into further rows and so on until all the elements of F are recovered.

Guessing means searching through all the possible values of the guessed elements. For an example 16-element permutation this results in a computational effort of about 3000 operations. To really a lot. This number however grows rapidly as the size of the permutation increases. For a 32-element permutation it is about 17,000,000 operations. Inverting the VMPC function for a 256-element permutation is beyond the computational power of all the computers in the world combined. The number of operations to perform is about 1078, which is a "1" followed by 78 zeros. Or in other words over a trillion trillions trillions trillions trillions trillions operations.

Permutation size Number of guessed elements Average number of operations
16 4 103
32 6 107
64 10 1016
128 18 1035
256 34 1078


In more general terms the important thing is that the complexity of inverting the VMPC function grows in a non-polynomial fashion (i.e. very rapidly) as the permutation size grows.

This in turn meets the formal definition of a one way function: the probability of inverting the VMPC function is a reciprocal of a non-polynomial function of the permutation size.




Copyright © 1999-2019 by Bartosz Zoltak