|
|
|
|
We investigate the great secret of maths:
Research Project - "VMPC Function - is P=NP?"
www.vmpcfunction.com/pnp
Bartosz Zoltak
1. Purpose of the project
2. News
3. How the VMPC function works
4. Why is the VMPC function likely one-way
5. Publications
6. Detailed description of the VMPC function
7. Contact
1. Purpose of the project
The question whether P=NP is one of the great secrets of maths.
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.
The question whether P=NP has a complex mathematical definition, but its
main idea is whether 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 1998 I discovered a mathematical transformation.
It turned out so interesting that for over 10 years now I have conducted research on it.
In 2004 I was invited to present it at a prestigious international scientific conference, FSE.
I named the transformation as the "VMPC function".
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.
If it was true, it would be the first one-way function in the world. To make it happen, 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", says the majority of the mathematicians.
- "If something cannot be done, it takes somebody who does not know that - and he will do it", said Albert Einstein.
My name is Bartosz Zoltak and I believe with all my heart and mind that it is possible to
prove that VMPC is a one-way function. I don't know if the length of my life will be enough to do it.
If not - I am convinced that in 100 years somebody else will do it.
2. News
22.07.2008 - The project's website starts
3. 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.
(2,0,3,4,1) is an example permutation. Let's refer to this one as "F".
VMPC will transform the "F" permutation into a new permutation "FF"
according to the formula FF(x) = F(F(F(x))+1):
The value of the VMPC function is produced in four steps:
step 1) 0 goes to 2. We read this from the table - position 0 goes to 2.
step 2) 2 goes to 3. We read what the number from the previous step (2) goes to.
step 3) 3+1=4. The simplest but the most important and most mysterious step.
This one gives the function its unusual properties...
step 4) 4 goes to 1 - we read what the number from the previous step (4) goes to.
We have just computed the first element of the VMPC function! We already know that the FF permutation
will be FF=(1, ?,?,?,?). The above four steps need to be repeated for the remaining four positions
(we start "jumping" through the table starting from positions 1,2,3 and 4) and its done!
We obtain that the value of the VMPC function for the permutation
F=(2,0,3,4,1) is FF=(1,4,2,3,0).
4. Why is the VMPC function likely one-way
Caution. The text below is not mathematically strict. Its purpose is to present
the idea of the function in a way understandable for the possibly broadest range of readers.
Physicist Richard Feynman said that a scientist who cannot explain the subject of his research to an 8 year old is a charlatan...
For a more detailed analysis of the function see
section 6. Detailed description of the VMPC function
and section 5. Publications, where you can find
the paper on VMPC published on the FSE'04 conference, and other scientific publications.
At the start let's look at the function FF(x)=F(F(F(x))), which differs from VMPC only with the lack of the +1 operation
in step 3.
Let two example elements of permutation FF be:
FF(7) = (7→9, 9→5, 5→2) and FF(9) = (9→5, 5→2, 2→4).
We can see that two elements of the F permutation - 9→5 and 5→2 - occur together in both - FF(7) and FF(9).
We can use this fact to invert the function.
Let's assume that the element FF(7) = (7→9, 9→5, 5→2) is revealed.
Then, like following a string, we can get to a new element FF(9) = (9→5, 5→2, 2→4),
because we know two (9→5 i 5→2) of the three elements of F which produce FF(9).
Having FF(9) traced this way we can read from it the third - new - element of permutation F (2→4).
We continue the procedure further - we keep tracing new elements of FF and read new elements of F from them
until the whole permutation F is revealed.
In case of the VMPC function the situation is different.
Because of the +1 operation it is hard to find two elements of F, which occur together in two different elements of FF,
like it happened above. In the VMPC function the elements of F spread through the FF permutation like in a cobweb.
Let's assume that one element of FF is FF(7) = (7→9, 9→5, 6→1).
It is hard to find a new element of FF, which uses two out of these three elements of F.
Instead it is usually possible to find only such element of FF, which uses only one of them.
For example FF(9) = (9→5, 5→2, 3→0).
The value of one of the two remaining elements of F (e.g. 5→2) needs to be guessed.
Only then can we read the value of the second one (3→0)...
The guessing usually needs to be repeated for each consecutive element of FF.
If the guess shows to be wrong it is necessary to change it or change one of the previous guesses.
The number of possible combinations grows very fast. And usually there is only one correct combination which needs to be found...
This is where the compelxity of inverting the VMPC function comes from.
If we managed to mathematically prove that these guesses are necessary, the VMPC function
would turn out to be truly one-way and the great problem - whether P=NP - would be solved.
Although building such a proof is a difficult task, I believe it is possible.
All research results up-to-date and intuition tells that it is so.
I will be pursuing it with great determination.
Yes, nobody has ever proved the one-wayness of any function...
But only from not long ago a likely-one-way function of such simplicity is known - the VMPC function.
5. 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) Some Words on Cryptanalysis of Stream Ciphers, Alexander Maximov. PhD Thesis, Department of Information Technology, Lund University, Sweden, pages 127-144, 16 June 2006.
6) Presentation of a paper "VMPC one-way function and VMPC-Tail-MAC authenticated encryption scheme",
Cryptography Applications Conference
Enigma 2004,
10-13 May 2004, Warsaw, Poland.
7) Presentation of a paper "A year in VMPC cryptanalysis, VMPC-MAC authenticated encryption scheme and VMPC-HASH algorithm",
Cryptography Applications Conference
Enigma 2005,
30 May - 02 June 2005, Warsaw, Poland.
8) "VMPC - cipher based on permutations", Dobromir Matusiewicz, 2. Cryptography Workshop, Lublin Catholic University, Poland, 14-15 May 2004.
9) Article "VMPC One-Way Function and Stream Cipher" published by a computer magazine
SOFTWARE 2.0 (currently Software Developer's Journal)
issue 9 (117), September 2004, pages 26-29. See magazine cover.
Contact us about the project!
Tel. (Bartosz Zoltak): +48 888 422 122
Form:
|
