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
|
|
|