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


VMPC One-Way Function Inverting Challenge

1. Introduction
2. Current problem
3. Demonstration problem 1
4. Demonstration problem 2
5. Demonstration problem 3
6. Demonstration problem 4

 



1. Introduction

The purpose of the inverting challenge is to stimulate research on the problem of inverting the VMPC function. The final goal is to find an efficient algorithm of inverting the function, which would show the VMPC function is not one-way, or to convincingly show, possibly - prove - the opposite.



2. Current problem

Inverting 1-level VMPC function for 256-element permutations.
Permutation Q=VMPC(P) and 29 correct elements of P are given.

The first person who finds a correct P and notifies us, will be listet at our website as the winner of the current problem. (Any 256-element permutation P, satisfying P[P[P[x]]+1]=Q[x], where "+" denotes addition modulo 256 and Q is given in Table 1, is regarded as a correct P)

Note: in demonstration problem 1 it is possible to recover all 256 elements of P in one step - from a given Q and given 27 correct elements of P


Table 1. n=256, Q[x]=P[P[P[x]]+1]. Q and 29 correct elements of P
Q 61, 71, 49, 62, 52, 185, 214, 89, 156, 120, 240, 139, 172, 184, 43, 168, 74, 8, 132, 151, 83, 186, 159, 229, 23, 175, 112, 142, 75, 232, 204, 123, 12, 59, 73, 64, 225, 14, 161, 198, 68, 69, 92, 226, 63, 32, 87, 150, 178, 118, 245, 196, 45, 116, 255, 18, 46, 102, 179, 13, 136, 252, 154, 35, 70, 53, 169, 242, 72, 194, 10, 42, 19, 209, 121, 140, 86, 124, 80, 201, 137, 109, 114, 88, 106, 205, 11, 234, 157, 247, 129, 153, 28, 31, 238, 122, 202, 22, 103, 171, 37, 119, 166, 212, 182, 17, 91, 30, 216, 93, 101, 104, 0, 78, 141, 95, 107, 195, 1, 66, 41, 217, 237, 199, 165, 56, 143, 127, 100, 76, 117, 131, 193, 253, 167, 223, 38, 227, 113, 97, 206, 228, 130, 181, 221, 84, 236, 6, 211, 55, 33, 110, 177, 29, 27, 145, 96, 219, 249, 230, 40, 174, 105, 138, 85, 36, 243, 218, 9, 25, 4, 244, 250, 158, 149, 208, 188, 94, 146, 207, 111, 224, 203, 213, 125, 191, 7, 215, 200, 47, 148, 170, 26, 24, 34, 54, 57, 233, 192, 173, 44, 126, 98, 197, 3, 144, 128, 99, 134, 2, 58, 65, 133, 248, 241, 160, 152, 67, 164, 220, 183, 51, 239, 222, 189, 135, 155, 82, 210, 246, 187, 79, 190, 176, 81, 162, 39, 60, 50, 77, 254, 15, 180, 147, 251, 231, 16, 163, 90, 108, 48, 20, 115, 5, 21, 235
P P[228]=86; P[86]=12; P[87]=35; P[240]=85; P[229]=137; P[252]=133; P[197]=187; P[129]=108; P[236]=80; P[156]=231; P[141]=152; P[158]=89; P[111]=97; P[29]=190; P[192]=236; P[232]=91; P[152]=62; P[248]=153; P[189]=45; P[182]=165; P[205]=25; P[119]=132; P[62]=130; P[7]=49; P[148]=181; P[42]=44; P[115]=16; P[167]=131; P[214]=158;


Note: First 5 of the revealed correct elements of P (P[228, 86, 87, 240, 229]) were chosen by
the selecting process and the remainig 24 are randomly chosen correct elements of P.

Average numbers of assumptions and numbers of operations required by the fastest known algorithm to invert the VMPC function are quoted at Example complexities of inverting the VMPC function



3. Demonstration problem 1

Inverting 1-level VMPC function for 256-element permutations.
Permutation Q=VMPC(P) and 27 correct elements of P are given.

All the remaining 229 elements of P can be recovered in one step.


Table 2. n=256, Q[x]=P[P[P[x]]+1]. Q, 27 correct elements of P and solution (P)
Q 57, 141, 79, 135, 206, 51, 33, 96, 149, 88, 58, 176, 38, 123, 230, 221, 234, 82, 200, 252, 183, 222, 60, 64, 50, 116, 111, 129, 112, 68, 6, 92, 118, 240, 198, 61, 250, 126, 37, 114, 70, 54, 170, 226, 45, 25, 95, 190, 76, 29, 244, 159, 152, 181, 162, 246, 211, 161, 146, 153, 10, 67, 167, 47, 22, 186, 179, 99, 202, 49, 74, 66, 21, 7, 151, 178, 106, 193, 155, 85, 158, 255, 136, 236, 184, 169, 220, 143, 105, 121, 215, 113, 245, 11, 138, 23, 235, 72, 142, 164, 19, 128, 103, 243, 120, 231, 139, 100, 130, 201, 35, 20, 94, 48, 80, 156, 133, 44, 233, 185, 251, 132, 214, 254, 14, 239, 91, 225, 52, 216, 41, 62, 30, 83, 63, 75, 207, 154, 163, 168, 17, 55, 195, 46, 16, 218, 203, 150, 148, 15, 242, 104, 42, 28, 93, 180, 90, 43, 9, 145, 115, 137, 73, 144, 165, 204, 27, 127, 26, 102, 205, 2, 12, 210, 237, 89, 3, 109, 4, 177, 77, 238, 8, 86, 98, 188, 34, 223, 125, 69, 194, 196, 191, 84, 175, 249, 40, 228, 39, 140, 248, 24, 107, 71, 192, 209, 117, 197, 224, 171, 32, 217, 219, 13, 53, 160, 172, 65, 147, 122, 208, 5, 31, 78, 36, 166, 247, 182, 18, 157, 87, 173, 174, 97, 56, 134, 101, 199, 187, 241, 1, 81, 229, 119, 131, 232, 212, 227, 213, 0, 59, 108, 124, 253, 189, 110
P P[58]=112; P[98]=57; P[214]=27; P[174]=53; P[53]=44; P[237]=153; P[124]=183; P[248]=181; P[169]=45; P[230]=213; P[231]=20; P[168]=191; P[167]=255; P[183]=235; P[14]=144; P[249]=195; P[213]=238; P[102]=65; P[254]=249; P[105]=122; P[72]=142; P[141]=236; P[73]=58; P[211]=72; P[46]=76; P[56]=147; P[3]=180;
P 182, 73, 151, 180, 171, 164, 107, 132, 31, 179, 211, 196, 89, 154, 144, 55, 185, 129, 198, 10, 26, 239, 156, 146, 68, 204, 123, 173, 98, 158, 50, 163, 223, 159, 38, 117, 110, 134, 17, 197, 200, 175, 104, 137, 247, 237, 76, 64, 169, 245, 125, 208, 77, 44, 47, 138, 147, 71, 112, 141, 128, 232, 70, 174, 81, 162, 187, 60, 29, 12, 226, 131, 142, 58, 148, 241, 194, 203, 140, 205, 109, 111, 190, 78, 11, 54, 43, 74, 222, 33, 49, 139, 133, 170, 85, 253, 0, 186, 57, 201, 82, 118, 65, 13, 92, 122, 188, 88, 91, 28, 254, 166, 22, 7, 105, 234, 108, 199, 59, 218, 192, 126, 124, 80, 183, 231, 6, 115, 18, 99, 37, 155, 161, 48, 120, 41, 79, 69, 220, 221, 130, 236, 233, 217, 165, 101, 46, 9, 1, 143, 51, 135, 119, 116, 25, 243, 66, 94, 23, 202, 121, 219, 96, 103, 149, 172, 230, 255, 191, 45, 83, 209, 24, 16, 53, 84, 75, 136, 40, 106, 150, 229, 97, 235, 214, 114, 210, 8, 90, 177, 176, 19, 227, 63, 178, 95, 189, 184, 39, 52, 61, 4, 216, 240, 152, 93, 207, 34, 32, 242, 206, 72, 252, 238, 27, 228, 5, 145, 15, 42, 30, 246, 113, 100, 224, 36, 86, 167, 251, 212, 213, 20, 244, 248, 21, 225, 14, 153, 102, 87, 56, 193, 3, 2, 62, 67, 215, 168, 181, 195, 35, 127, 160, 157, 249, 250


Note: All 27 of the revealed correct elements of P have been chosen by the selecting process. It is possible to reveal all the remaining 229 elements of P using the deducing process.



4. Demonstration problem 2

Inverting 1-level VMPC function for 8-element permutations.
Permutation Q=VMPC(P) and 1 correct element of P are given.

All the remaining 7 elements of P can be recovered after assuming one more element of P.


Table 3. n=8, Q[x]=P[P[P[x]]+1]. Q, 1 correct elements of P and solution (P)
Q 6, 4, 7, 3, 1, 2, 5, 0
P P[6]=7;
P 4, 6, 3, 5, 0, 1, 7, 2




5. Demonstration problem 3

Inverting 1-level VMPC function for 8-element permutations.
Permutation Q=VMPC(P) and 2 correct elements of P are given.

All the remaining 6 elements of P can be recovered in one step.


Table 4. n=8, Q[x]=P[P[P[x]]+1]. Q, 2 correct elements of P and solution (P)
Q 4, 1, 7, 0, 2, 6, 5, 3
P P[5]=0; P[0]=2;
P 2, 7, 5, 6, 1, 0, 4, 3




6. Demonstration problem 4

Inverting a triple permutation composition for 256-element permutations.
Permutation Q[x]=P[P[P[x]]] and 2 correct elements of P are given.

All the remaining 254 elements of P can be recovered in one step.

P consists of a single cycle and two correct elements of P are given to illustrate the simplicity of deducing new elements of P given Q and given some elements of P for a simple triple permutation composition, as opposed to Variably Modified Permutation Composition.


Table 5. n=256, Q[x]=P[P[P[x]]]. Q, 2 correct elements of P and solution (P)
Q 35, 239, 216, 227, 119, 9, 177, 178, 114, 31, 81, 170, 115, 218, 66, 163, 160, 70, 62, 140, 105, 215, 107, 89, 15, 64, 100, 244, 182, 159, 137, 90, 220, 97, 29, 67, 77, 205, 57, 135, 228, 52, 240, 190, 129, 110, 2, 204, 73, 47, 132, 68, 50, 80, 199, 231, 175, 194, 46, 168, 126, 13, 144, 96, 60, 245, 98, 171, 58, 173, 83, 106, 112, 153, 180, 134, 146, 229, 38, 30, 65, 172, 123, 251, 17, 200, 252, 142, 111, 217, 7, 16, 76, 183, 201, 3, 188, 141, 176, 26, 19, 219, 39, 243, 93, 59, 79, 161, 11, 92, 122, 56, 191, 87, 21, 124, 151, 202, 71, 42, 196, 169, 130, 250, 212, 69, 18, 208, 195, 53, 155, 234, 241, 24, 184, 74, 101, 174, 154, 158, 44, 41, 25, 238, 0, 5, 131, 103, 152, 143, 95, 162, 88, 104, 34, 206, 166, 164, 189, 209, 222, 148, 99, 22, 43, 149, 32, 4, 211, 54, 94, 117, 167, 116, 12, 186, 125, 246, 82, 157, 214, 197, 224, 138, 248, 86, 230, 109, 102, 72, 118, 242, 210, 78, 223, 247, 128, 6, 207, 10, 237, 49, 165, 181, 232, 255, 139, 192, 84, 20, 254, 253, 226, 8, 213, 193, 91, 85, 121, 27, 55, 236, 40, 249, 33, 150, 28, 133, 198, 203, 127, 225, 36, 113, 51, 14, 45, 221, 37, 23, 147, 61, 187, 145, 185, 136, 120, 1, 233, 235, 156, 108, 75, 179, 63, 48
P P[0]=131; P[131]=250;
P 131, 241, 231, 205, 75, 25, 224, 18, 84, 64, 244, 118, 98, 65, 204, 153, 95, 179, 92, 128, 74, 70, 93, 13, 73, 191, 120, 221, 116, 102, 235, 60, 117, 99, 188, 234, 115, 160, 11, 56, 133, 19, 184, 78, 247, 172, 55, 137, 228, 30, 44, 166, 140, 239, 219, 165, 209, 170, 220, 214, 187, 80, 76, 148, 242, 89, 232, 51, 32, 203, 157, 194, 145, 198, 186, 130, 82, 124, 108, 249, 23, 185, 144, 164, 253, 169, 110, 72, 29, 218, 126, 150, 178, 210, 106, 37, 152, 26, 36, 246, 196, 200, 111, 113, 192, 180, 223, 183, 190, 7, 167, 159, 5, 189, 17, 176, 197, 58, 57, 134, 141, 136, 4, 0, 125, 229, 109, 168, 52, 1, 119, 250, 129, 48, 155, 175, 85, 14, 63, 147, 195, 100, 112, 91, 146, 142, 123, 233, 154, 216, 238, 6, 34, 207, 96, 42, 67, 215, 103, 39, 3, 138, 177, 104, 193, 2, 171, 252, 213, 101, 71, 68, 86, 181, 66, 20, 77, 33, 62, 21, 230, 28, 151, 254, 206, 45, 105, 90, 88, 243, 38, 9, 22, 251, 94, 50, 41, 182, 15, 27, 54, 79, 46, 226, 174, 222, 240, 163, 211, 135, 107, 8, 69, 208, 127, 83, 225, 121, 245, 237, 202, 10, 227, 201, 162, 143, 173, 255, 24, 212, 59, 149, 12, 158, 156, 47, 81, 199, 16, 61, 248, 53, 31, 87, 236, 217, 97, 132, 139, 49, 35, 43, 122, 114, 161, 40





Home  |   VMPC Function  |   VMPC-R CSPRNG  |   VMPC Stream Cipher  |   VMPC-MAC scheme  |   VMPC KSA3 algorithm  |   Research  |   Inverting Challenge
P vs NP Project  |   VMPCrypt Application  |   Permutu Game  |   Publications  |   About Author  |   Contact

Copyright © 1999-2018 by Bartosz Zoltak