Variably Modified Permutation Composition
Encyclopedia
VMPC is encryption
technology designed by Bartosz Zoltak, publicly presented in 2004 at an international cryptography
conference Fast Software Encryption in Delhi, India.
The core of the technology is the VMPC one-way function, applied in an encryption algorithm
- the VMPC stream cipher.
The VMPC function is a transformation of n-element permutation
s defined as:
for x from 0 do n-1: g(x) = VMPC(f(x)) = f(f(f(x))+1)
Interestingly inverting the function, i.e. obtaining f from g appears to be a complex problem. According to computer simulations the average number of operations required to recover f from g for a 16-element permutation is about 211, for 64-element permutation - about 253 and for a 256-element permutation - about 2260.
Theoretically speaking - if these results were possible to be proved - it would imply that VMPC is a true one way function
, which would solve the famous P vs NP problem.
In 2006 at Cambridge University Kamil Kulesza published a paper "On inverting the VMPC one-way function", which investigated the issue but it left the problem open - the one-wayness of the function was neither proved nor denied.
The VMPC one-way function is used in an encryption
algorithm - the VMPC stream cipher
. The algorithm is very efficient in software implementations (encrypt L bytes of plaintext do):
1. n = 0
2. Repeat steps 3-6 L times:
3. s = P[ (s + P[n]) mod 256 ]
4. Output = P[ (P[P[s]]+1) mod 256 ]
5. Temp = P[n]
P[n] = P[s]
P[s] = Temp
6. n = (n + 1) mod 256
Where 256-element permutation P and integer value s are obtained from the encryption password using the VMPC-KSA (Key Scheduling Algorithm), which can be found at the VMPC Homepage along with the VMPC-MAC (Message Authentication Code) allowing to authenticate messages encrypted with the VMPC Stream Cipher.
Encryption
In cryptography, encryption is the process of transforming information using an algorithm to make it unreadable to anyone except those possessing special knowledge, usually referred to as a key. The result of the process is encrypted information...
technology designed by Bartosz Zoltak, publicly presented in 2004 at an international cryptography
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
conference Fast Software Encryption in Delhi, India.
The core of the technology is the VMPC one-way function, applied in an encryption algorithm
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
- the VMPC stream cipher.
The VMPC function is a transformation of n-element permutation
Permutation
In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...
s defined as:
for x from 0 do n-1: g(x) = VMPC(f(x)) = f(f(f(x))+1)
Interestingly inverting the function, i.e. obtaining f from g appears to be a complex problem. According to computer simulations the average number of operations required to recover f from g for a 16-element permutation is about 211, for 64-element permutation - about 253 and for a 256-element permutation - about 2260.
Theoretically speaking - if these results were possible to be proved - it would imply that VMPC is a true one way function
One-way function
In computer science, a one-way function is a function that is easy to compute on every input, but hard to invert given the image of a random input. Here "easy" and "hard" are to be understood in the sense of computational complexity theory, specifically the theory of polynomial time problems...
, which would solve the famous P vs NP problem.
In 2006 at Cambridge University Kamil Kulesza published a paper "On inverting the VMPC one-way function", which investigated the issue but it left the problem open - the one-wayness of the function was neither proved nor denied.
The VMPC one-way function is used in an encryption
Encryption
In cryptography, encryption is the process of transforming information using an algorithm to make it unreadable to anyone except those possessing special knowledge, usually referred to as a key. The result of the process is encrypted information...
algorithm - the VMPC stream cipher
Stream cipher
In cryptography, a stream cipher is a symmetric key cipher where plaintext digits are combined with a pseudorandom cipher digit stream . In a stream cipher the plaintext digits are encrypted one at a time, and the transformation of successive digits varies during the encryption...
. The algorithm is very efficient in software implementations (encrypt L bytes of plaintext do):
1. n = 0
2. Repeat steps 3-6 L times:
3. s = P[ (s + P[n]) mod 256 ]
4. Output = P[ (P[P[s]]+1) mod 256 ]
5. Temp = P[n]
P[n] = P[s]
P[s] = Temp
6. n = (n + 1) mod 256
Where 256-element permutation P and integer value s are obtained from the encryption password using the VMPC-KSA (Key Scheduling Algorithm), which can be found at the VMPC Homepage along with the VMPC-MAC (Message Authentication Code) allowing to authenticate messages encrypted with the VMPC Stream Cipher.