Mapping enlargements preserving identification property.pdf Пусть A = { 0 , 1 , . . . ,k - 1}, k ^ 2, n - натуральное число, Q - множество всехотображений q: An ^ An и для каждого отображения q в Q определены функцииq^: An ^ A, i = 1, 2 , . . . , n , так, что q(x) = q1(x)q2(x)... qn (x) для всех x в An, т.е.q = q1q2 ...qn. Пусть также B = { i b i2,... , i|B|} С { 1 , . . . , n } , i1 < i2 < ... < i|B| иa[B] = ail ai2 ... для любого вектора a = a1a2 ... an.Говорят, что отображение q в Q идентифицируется на B, если для любого отоб-ражения t G Q из q[B] = t[B] следует q = t.По определению, если отображение q в Q идентифицируется на B, то оно иденти-фицируется и на любом множестве F С { 1 , . . . , n}, таком, что B С F.Построим отображение g: An+1 ^ An+1 как расширение отображения q следу-ющим образом. Возьмём произвольную функцию а: A ^ A и элемент j G { 1 , . . .,n + 1} \ B и положим gj (x1,...,xj-, ...,xn+1) = a(xj), gi(x1,...,xj-, ...,xn+1) == qi(x1,... , xj-1, x j + 1 , . . . , xn+1) для всех i = j. Пусть наконец D = B U { j } .Теорема 1. Отображение q идентифицируется на B, если и только если отобра-жение g идентифицируется на D. Отображение g не идентифицируется на множестве{ 1 , . . . , n + 1 } -{ j } .Доказательство. Пусть отображение q идентифицируется на B. Предположим,что его расширение g не идентифицируется на D. Тогда найдётся такое отображениеt' : An+1 ^ An+1, что t'[D] = g[D] и g = t', и для t G Q, полученного из t' вычёркивани-ем j-й компоненты, будет q[B] = t[B] и q = t, что противоречит идентифицируемости qна B. Следовательно, g идентифицируется на D.Обратно, пусть отображение g идентифицируется на D. Предположим, что q неидентифицируется на B. Тогда найдётся такое отображение t: An ^ An, что t[B] == q[B] и q = t. Построим расширение t' для t, положив tj = gj, и как результат получимg[D] = t'[D] и g = t', что противоречит идентифицируемости g на D. Следовательно,q идентифицируется на B.Пусть g' - такое расширение отображения q, что gj(x) = a'(xj) = a(xj) = gj(x).Т о гда g1g2... gj-1gj+1... gn+1 = gig2... gj-1gj+1... gn+1 и g = g', т .е . о т о б р а ж е н и е g неидентифицируется на множестве {1,... , n + 1} - { j}.Пусть далее V С Q есть множество всех инволюций на An, т. е. подстановокq: An ^ An со свойством инволютивности: Vx,y G An(q(x) = y ^ q(y) = x). Непосред-ственно проверяется, что если расширение g инволюции q G V построено с помощьюподстановки а: A ^ A, то g G V, т.е. расширение инволюции по подстановке явля-ется инволюцией; в этом случае теорема 1 остаётся в силе, если в её формулировкевместо отображений в Q рассматриваются инволюции в V. Таким образом, для любойинволюции q G V можно построить k!(n + 1) различных инволюций, являющихся рас-ширениями инволюции q, сохраняющими свойство идентифицируемости последней.Эти результаты могут быть использованыв инволюционных схемах разделениясекрета [1], когда в множество участников схемы вводится новый участник и требуется,чтобы неавторизованные множества новой схемы включали в себя неавторизованныемножества прежней схемы.В этой связи, а также в связи с криптоанализом инволюционных шифров [2, 3]представляет интерес следующий тест идентифицируемости произвольной инволюции.Теорема 2. Инволюция q е V идентифицируется на B, если и только если длялюбых x и y в An, x = y, выполняется q(x)[B] = q(y)[B].Доказательство. Необходимость. Пусть инволюция q идентифицируется на B.Предположим, что в An найдутся такие x и y, что x = y и q(x)[B] = q(y)[B]. Построиминволюцию t е V, t = q, такую, что q(x) = t(y) и q(y) = t(x), а на остальных элементахв An инволюции t и q совпадают. Тогда t(y)[B] = q(x)[B] = q(y)[B] = t(x)[B]. Имеемt[B] = q[B] и t = q, что противоречит идентифицируемости q на B.Достаточность. Пусть для любых x и y в An, где x = y, выполняется q(x)[B] == q(y)[B]. Предположим, что инволюция q не идентифицируется на B. Тогда в Qнайдется инволюция t, что t = q и q[B] = t[B]. Если же t = q, то в An найдутся такие xи y, что x = y, q(x) = t(y) и q(y) = t(x). Следовательно, q(x)[B] = t(x)[B] = q(y)[B] == t(y)[B], что противоречит условию.

Скачать электронную версию публикации