Создание CPA-устойчивых систем шифрования

89
3.5.1 Псевдослучайные функции и блочные шифры 
Псевдослучайные функции обобщают понятие псевдослучайных генерато-
ров. Теперь вместо того, чтобы рассматривать похожие на случайные строки, 
мы рассматриваем похожие на случайные функции. Как уже говорилось в об-
суждении псевдослучайности, нет смысла говорить о том, что какая-то фикси-
рованная функция f : {0, 1}* → {0, 1}* является псевдослучайной (так же, 
как и нет смысла говорить, что какая-то фиксированная функция является слу-
чайной). Таким образом, мы вместо этого должны ссылаться на псевдослучай-
ность распределения по функциям. Такое распределение естественно осущест-
вляется при рассмотрении функции с ключом, определенной далее.
Функция с ключом F: {0, 1}*×{0, 1}*→{0, 1}* является функцией двух пе-
ременных, где первая переменная называется ключ и обозначается k. Мы го-
ворим, F является эффективной, если существует полиномиально-временной 
алгоритм, который вычисляет F (k, x) заданных k и x. (Нас будут интересовать 
только эффективные функции с ключом.) При типичном использовании ключ 
k выбирается и фиксируется, и тогда нас интересует только функция с одной 
переменной Fk:{0, 1}*→{0, 1}*, определенная Fk (x) = F (k, x). Ключ параметр 
безопасности n определяет длину ключа, входную и выходную длину.
Иначе говоря, мы ставим в соответствие с F три функции Akey, Ain, и Aout; для 
любого ключа k∈{0, 1}Akey(n), функция Fk определяется только для входных дан-
ных x∈{0, 1}Ain(n), в случае которых Fk(x)∈{0, 1}Aout(n). Если не указано иное, 
для простоты мы допустим, что F является сохраняющей длину, что означает, что 
Akey (n) = Ain(n) = Aout(n) = n. Иными словами, фиксируя ключ k∈{0, 1}n, мы полу-
чаем функция Fk, преобразующую n-битные входные строка в n-битные выходные.
Функция с ключом F обуславливает естественное распределение по функциям, за-
данных выбором унифицированного ключа k∈{0, 1}n, и рассмотрение получившей-
ся функции с одной переменной Fk . Мы называем F псевдослучайной, если функция 
Fk (для унифицированного ключа k) неотличима от функции, случайно и равномерно 
выбранной из множества всех функций, обладающих одинаковыми областями опре-
деления и значения. Говоря иначе, если ни один эффективный противник не может 
различить (в смысле, который мы более точно обозначим ниже), взаимодействует он 
с Fk (для унифицированного k) или f (где f равномерна выбрана из множества всех 
функций, преобразующих n-битные входные данные в n-битные выходные данные).
Поскольку случайный выбор функции интуитивно представить гораздо слож-
нее, чем случайный выбор строки, на этом стоит остановиться подробнее. Рас-
смотрим множество всех функций, преобразующих n-битные входные данные 
в n-битные выходные, Funcn. Это множество конечно, и выбор функции, пре-
образующей n-битные входные данные в n-битные выходные данные, означает 

90
равномерный выбор элемента из этого множества. Насколько велико Funcn? Функция 
f определяется заданием значения в каждой точке своей области определения. Мы мо-
жем рассматривать любую функцию (в конечной области определения), как большую 
таблицу соответствия, в которой хранятся f (x) в строке таблицы, помеченной x. Для 
f ∈Funcn таблица соответствия для f имеет 2n строк (по одной для каждой точки об-
ласти определения {0, 1}n), где в каждой строке таблицы находится n-битная строка 
(поскольку область значений f составляет {0, 1}n). Объединив все данные таблицы, 
мы видим, что любая функция из множества Funcn может быть представлена строкой 
длиной 2n • n. Кроме того, это соответствие является одним-к-одному, поскольку каж-
дая строка длиной 2n • n (т. е. каждая таблица, содержащая в себе 2n записей длиной n) 
определяет уникальную функцию множества Funcn. Таким образом, размер Funcn 
точно равен n числу строк длиной n • 2n, или |Funcn| = 2n•2.
Рассмотрение функции в качестве таблицы соответствий позволяет по-
другому представлять выбор равномерной функции f∈ Funcn: Он с точностью 
соответствует равномерному выбору каждой строки таблицы соответствия f. В 
частности, это означает, что значения f (x) и f (y) (для любых двух переменных x 
ƒ= y) являются равномерными и независимыми. Мы можем рассматривать эту 
таблицу соответствий как заранее наполненную случайными данными , перед 
оценкой f по любой переменной, или можем рассматривать данные таблицы, 
как равномерно и оперативно выбранные по мере необходимости, всякий раз, 
когда f оценивается по новой переменной, по которой f ранее не оценивалась.
Возвращаясь к нашему обсуждению псевдослучайных функций, напомним, 
что псевдослучайная функция - это функция с ключом F, такая что Fk (для 
k∈{0, 1}n, случайно и равномерно выбранного) не отличима от функции f (для 
f∈Funcn, случайно и равномерно выбранной). Первая выбирается из распреде-
ления в пределах (максимум) 1n различных функций, тогда как вторая выбира-
ется из всех 2n•2 функций в Funcn. Несмотря на это, «поведение» этих функций 
должно выглядеть одинаково для любого полиномиального дистинктора.
Первой попыткой формализации понятия псевдослучайной функции было 
бы действовать аналогично Определению 3.14. То есть, мы могли бы потре-
бовать, чтобы каждый полиномиальный дистинктор D, который получает опи-
сание псевдослучайной функции Fk, выдает 1 с «почти» той же вероятностью, 
как когда он получает описание произвольной функции f. Тем не менее, это 
определение неправильно, так как описание произвольной функции имеет экс-
поненциальную длину (данную ее таблицей длиной n • 2n), в то время как D 
ограничен работой в полиномиальном времени. Таким образом, D даже не 
будет располагать достаточным временем, чтобы изучить все входные данные.
Таким образом, определение дает D доступ к оракулу О, который либо равен 
Fk (для постоянной k), либо f (для постоянной функции f ). Дистинктор D может 

91
посылать запросы своему оракулу в любой точке x, в ответ на что оракул возвра-
щает О(х). Мы рассматриваем оракул как черный ящик в той же манере, как когда 
мы давали противнику оракульный доступ к алгоритму шифрования в определе-
нии атаки с выбором незашифрованного текста. Однако, здесь оракул вычисляет 
детерминированную функцию и, таким образом, выдает тот же результат, если 
запрос делается дважды с одинаковыми входными данными. (По этой причине, 
мы можем предположить без ущерба общности утверждения, что D никогда не 
посылает запрос оракулу дважды с одинаковыми исходными данными.) D может 
свободно взаимодействовать со своим оракулом, выбирая свои запросы адаптив-
но на основе всех предыдущих результатов. Однако, так как D работает в поли-
номиальном времени, он может сделать только полиномиальное количество за-
просов . Представим теперь формальное определение. (Исключительно с целью 
упрощения это определение предполагает, что F не меняет длину.)

жүктеу/скачать 6.4 Mb.

Достарыңызбен бөлісу: