XS-circuits: hiding round oracles.pdf В [1] для описания блочно-итерационных шифров предложено использовать XS-схемы. Элементарная (однотактовая) XS-схема порядка n задаётся тройкой (a,B,c), в которой а и c - двоичные вектор-столбец и вектор-строка размерности n, B - двоичная матрица порядка n. Схема инстанциируется над полем F из 2m элементов выбором подстановки S: F F, которая называется тактовым оракулом. Результатом инстан-циирования является преобразование (а, B, c)[S]: Fn Fn, x y = xB + S(xa)c. Здесь и далее x и y - вектор-строки. Нас будут интересовать регулярные схемы, только они имеют криптографическое значение. В регулярной схеме матрицы cBn-1 A = (a Ba ... Bn 1 a) , C= cB c обратимы. Матрица B может быть обратимой или нет, в зависимости от этого схему относят к типу I или II. Пусть (a,B,c)t - t-тактовый каскад, полученный соединением t экземпляров элементарной схемы (a, B, c). Инстанциируя экземпляры оракулами S1, . . . , St, получаем преобразование (a, B, c)t[S1, . . . , St]. Его действие можно описать следующим образом: по входу x = y(0) G Fn вычисляется последовательность У(т) = У(т - 1)B + St(У(т - 1)a)C т = 1, 2 ..., и её последний элемент y = y(t) объявляется результатом преобразования. Оракулы ST моделируют секретные подстановки, действие которых определяется тактовыми ключами, построенными по исходному ключу блочного шифра. Как правило, тактовый ключ достаточно легко определить всего по одной паре «вход - выход» соответствующего оракула. Поэтому важно, чтобы каскад скрывал своих оракулов в смысле следующего определения. Определение 1. Каскад (a, B, c)t размерности n над полем F из 2m элементов скрывает тактовых оракулов, если в описываемой ниже игре симулятора с противником последний не может добиться успеха с вероятностью отличной от 1 /2m. Правила игры: 1) Симулятор выбирает случайные независимые равновероятные подстановки S1, S2, . . . , St над F. Они будут использоваться в качестве тактовых оракулов. 2) Противник выбирает вектор x G Fn и передает его симулятору. 3) Симулятор вычисляет вектор y = (a, B, c)t[S1, S2, . . . , St](x) и возвращает его противнику. 4) Получив у, противник выбирает номер такта т G {1, 2,...,t}, определяет пару (u,v) G F х F и передает её симулятору. 5) Симулятор подводит итог: противник победил, если V = ST(u), и проиграл, если равенство нарушается. В ходе игры противник демонстрирует умение определять «входы - выходы» тактовых оракулов, а симулятор проверяет это умение. Под противником понимается вероятностный алгоритм. Обратим внимание, что ограничения на его вычислительные ресурсы (время, память) не накладываются. Порог вероятности 1/2m означает, что противник может лишь угадать выход ST (u) на входе u (или вход S-1(v) на выходе V), т. е. каскад действительно скрывает оракулов. Пусть uT G F - вход оракула ST во время обработки x и vT = ST (uT) - соответствующий выход, т = 1, 2, . . . , t. Векторы x и y связаны следующим образом: y = xBt + (v1, v2, . . . , vt)Ct. Здесь Ct - матрица размера t х п, в которой т-я строка - это вектор cBt-T. В силу регулярности матрица Ct обратима при t = n. Поэтому по паре (x, y) можно определить вектор (v1, v2, . . . , vt) выходов тактовых оракулов, а затем и входы: т-1 uT = xBT-1a ■ V vicBт -1-ia, т = 1,2,..., t. i=1 Таким образом, п-тактовый каскад не скрывает оракулов, и число тактов необходимо увеличивать. Следующая теорема показывает, что для скрытия достаточно 2n тактов. Теорема 1. Если (a,B,c) -регулярная схема и t 2п, то каскад (a,B,c)t скрывает тактовых оракулов. Доказательство. Начнём с рассмотрения схем типа I. Предположим, что существует обратимая матрица M размера n х n над полем F, такая, что CtM содержит столбец с единственным ненулевым элементом. Пусть, не нарушая общности, это столбец ет с единицей в позиции т и нулями в остальных позициях. Если ет - это i-й столбец CtM, то vT можно найти как i-ю координату (xBt + y)M, поскольку (v1, v2, . . . , vt)CtM = (xBt + y)M. При запрете на существование M матрица Ct, дополненная столбцом ет, имеет полный ранг n + 1. Данный факт выполняется для любого номера т = 1,2,...,t. Факт означает, что при любом варианте выбора выхода vT имеется одно и то же число вариантов выбора остальных выходов, при которых x переходит в y. Поскольку случайный равновероятный выбор S1, S2, . . . , St индуцирует случайный равновероятный выбор вектора выходов (v1, v2, . . . , vt) при любом векторе входов (u1, u2, . . . , ut), все варианты перехода x y имеют один и тот же вероятностный вес. Поэтому вероятность корректно определить vT равняется 1/2m. С такой же вероятностью окажется корректной любая пара (u,v), выбранная противником. Остаётся показать, что матрицы M не существует. Предположим противное. Пусть r - некоторый (ненулевой) столбец M. Записывая координаты соответствующего столбца CtM снизу вверх, получаем последовательность cB0r, cB1r, . . . , cBt-1r. Мы имеем дело с линейной рекуррентной последовательностью (л.р.п.) порядка n. Л.р.п. ненулевая, поскольку её n-префикс ненулевой. Префикс действительно ненулевой, поскольку матрица C из определения регулярности обратима. Более того, из обратимости C следует, что любой n-отрезок л.р.п. будет ненулевым. Поэтому отрезок длины t 2n не может содержать менее двух ненулевых элементов. Другими словами, столбец CtM не может содержать только один ненулевой элемент. Противоречие. Рассмотрим теперь регулярные схемы типа II. Для них л.р.п. (cBTr) снова начинается с ненулевого n-префикса. Поскольку B вырождена, после префикса могут идти одни нули. Поэтому можно точно определить выход ST для т G {t-n+1, t-n+2, ...,t}. Выходы для остальных т можно определить только с вероятностью 1/2m. Аналогичные рассуждения применимы к обратному преобразованию F-1. Оно имеет тот же тип II, и в нём в обратном порядке задействованы обратные оракулы S-1. Теперь можно определить выход S-1, т. е. вход ST, для т G {1, 2,... , n}. Другие входы определяются с вероятностью 1/2m. Итак, вероятность успешного определения пары (uT, vT) целиком не превосходит 1/2m. Поэтому любая пара (u,v), выбранная противником, окажется корректной с вероятностью 1/2m. ■ Открытым остаётся вопрос о скрытии тактовых оракулов, когда противник может выбрать не один, а несколько входов x и получить соответствующие выходы y = (a, B, c)t[S1, S2, . . . , St](x).

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