Warning: Parameter 1 to NP_SEO::event_PreItem() expected to be a reference, value given in /home/bh52645/public_html/fucktheplanet.ru/nucleus/libs/MANAGER.php on line 370

Как построить случайные функции. Построение полислучайных совокупностей

ПОСТРОЕНИЕ ПОЛИСЛУЧАЙНЫХ СОВОКУПНОСТЕЙ В этой главе мы
покажем, как построить совокупность функций, которые проходят все
"полиномиально ограниченные" статистические тесты. Совокупность
функций F - это совокупность {Fk} таких, что для всех k и всех f
Fk f:Ik - Ik.
СТАТИСТИЧЕСКИЕ ТЕСТЫ ПОЛИНОМИАЛЬНОГО ВРЕМЕНИ
ДЛЯ ФУНКЦИЙ. Определение. СТПВ для функций - это вероятностный
алгоритм ПВ Т, который для заданного k в качестве входа и при
наличии доступа к предсказателю О относительно функции f: Ik -
Ik, вырабатывает на выходе либо 0, либо 1. Алгоритм Т может
запросить предсказателя О , записав на специальной ленте запроса
некотрое y Ik, а прочитать ответ предсказателя f(y) - на
отдельной ленте ответа. Как обычно, О печатает свой ответ за один
шаг. Пусть F={Fk} будет совокупностью функций. Говорим, что F
проходит тест Т, если для любого полинома Q и для достаточно
больших k: | p - p | < 1/Q(k), где p обозначает вероятность того,
что Т вырабатывает на выходе 1 для входа k и при наличии доступа
к предсказателю О относительно функции f Fk, а p обозначает
вероятность того, что Т вырабатывает на выходе 1 для входа k и
при наличии доступа к предсказателю О относительно функции f Hk
(т.е. случайной функции). Вероятности берутся по всем возможным
выборам f Fk или Hk и броскам монеты внутри Т. Приведгнное
определение можно интерпретировать следующим образом. Функция f
"считается" случайной в зависимости от соотношения вход-выход.
Тест Т состоит из двух этапов. Сперва он собирает информацию об
f, получая значения f от аргументов по своему выбору. Затем он
выносит "вердикт": 0 (если он "думает", что f Fk) или 1 (если он
"думает", что f Hk). Если совокупность F проходит тест, то выход
Т при наличии доступа к предсказателю О не дагт информации о том,
f Fk или f Hk. В противном случае Т выдаст на выходе 1 с той же
вероятностью. Прохождение всех СТПВ для функций - это чрезвычайно
общий критерий случайности. Например, предположим, что некоторый
эффективный алгоритм А может найти завыисимости между
входными-выходными парами f Fk; затем А может быть преобразован в
статистический тест Тa, который вырабатывает на выходе 0 при
обнаружении А таких зависимостей (т.е. решая, что f Fk).
Поскольку таких зависимостей найти нельзя, когда f Hk, то
совокупность F={Fk} не пройдгт тест Та. (Более подробно см.
гл.4.) Теперь покажем совокупность F, которая проходит все СТПВ в
предположении, что существует ОФ. 3.2. ПОСТРОЕНИЕ F. В этой главе
мы покажем, как использовать КСБ-генератор для построения
полислучайной совокупности. Иначе говоря, мы покажем, что
псевдослучайность для последовательностей включает
псевдослучайность для функций. Поскольку КСБ-генератор можно
построить при наличии ОФ, то же можно сказать и о полислучайных
совокупностях. В частности, наше построение использует любой
КСБ-генератор G, который развгртывает начальное значение x Ik в
2k-битную последовательность G(x)=b ...b . Пусть Sk будет
мультимножеством 2k-битных последовательностей, вырабатываемых G
при начальном значении длиной k. Напомним, что S= Sk проходит все
СТПВ для последовательностей. Пусть x Ik. Под Gо(x) мы обозначим
первые k бит, вырабатываемые G для входа x, т.е. Gо(x)=b ...b .
Под G (x) обозначим следующие k бит, вырабатываемые G, т.е. G
(x)=b ...b . Пусть будет двоичной последовательностью. Определим
G (x)=G (...(G (G (x)))...). Для x Ik функция f :Ik - Ik
определена следующим образом: f (y)= G (x). Пусть Fx={f } . Тогда
F={Fk} - требуемая совокупность. (В следующем подразделе мы
покажем, что F - это полислучайная совокупность. Мы не знаем,
справедливо ли это, если определено, что f (y)=Gx(y)). Может
оказаться полезным изобразить функции f :Ik - Ik как корневое
полное двоичное дерево глубины k с k-битными
последовательностями, хранимыми в узлах, и ргбрами, помеченными 0
или 1. k-битная последовательность x будет храниться в корне.
Если k-битная последовательность s хранится во внутреннем узле v,
то Gо(s) хранится в левом дочернем узле v , а G (s) - в правом
дочернем узле v . Ребро (v, v ) помечается 0, а (v,v ) - 1. Тогда
последовательность f (y) хранится в листе, который достижим из
корня через путь, помечаемый y. См. рис.1. Отметим, что
вычисление f (y) для входов x и y требует k*Тk шагов, где Tk
означает число шагов для вычисления G(x) для входа x Ik. Отметим
также, что функции в Fk могут не быть однозначными. 3.3.
ПОЛИСЛУЧАЙНОСТЬ F. Определгнная выше совокупность F удовлетворяет
условиям 1 (индексирование) и 2 (вычисление за полиномиальное
время) для полислучайной совокупности (см. гл.1.1). Основная
теорема показывает, что условие 3 (псевдослучайность) также
выполняется. Теорема 3 (основная). Пусть F будет совокупностью
функций, построенных в соответствии с гл.3.2 при помощи
КСБ-генератора G. Тогда F проходит все СТПВ для функций.
Доказательство. Сперва дадим обзор доказательства. Предположим
для противоречия, что существует некоторый СТПВ для функций Т,
который F не проходит. Тогда мы используем Т для создания СТПВ Ат
для последовательностей. Мы придгм к противоречию, показав, что
множество КСБ-последовательностей, вырабатываемых G, не проходит
Ат. Рассмотрим вычисления статистического теста Т, в котором на
запросы Т отвечает один из вероятностных алгоритмов Аi
(i=0,1,..,k) (т.е. ответы даются не предсказателем О ). Алгоритм
Аi отвечает на запросы Т следующим образом. (Расширим наше
определение, положив G (x)=x, где - пустая последовательность).
Пусть y=y y ..y - запрос Т. Тогда if y - первый запрос с
префиксом y ...y then Аi выбирает последовательность r Ik
случайным образом, запоминает пару (y ...y , r) и дагт ответ G
(r) else Аi извлекает пару (y ...y , v) и дагт ответ G (v).
(Концептуально алгоритм Аi начинается с полного двоичного дерева
глубины k и запоминает случайные k-битные последовательности во
всех узлах уровня i. В узлах следующих уровней хранятся k-битные
последовательности, детерминированно вычисленные G, как описано
ниже. Если k-битная последовательность s хранится во внутреннем
узле v, то Gо(s) хранится в левом дочернем узле v, а G (s) - в
правом дочеренем узле v. Алгоритм отвечает на запрос q
последовательностью, хранящейся в листе, достижимом из корня
через путь q.) Определим p как вероятность того, что Т
вырабатывает 1, когда в качестве входа задано k и на запросы
отвечает алгоритм Аi, 0<=i<=k. Определим p (p соответственно) как
вероятность того, что Т вырабатывает 1, когда в качестве входа
задано k и имеется доступ к предсказателю О относительно функции
f Fk (f Hk соответственно). Отметим, что p =p и p =p . Если
предполагается, что F не проходит Т, то существует полином Q и
бесконечно много k таких, что | p - p | >1/Q(k). Эквивалентно | p
- p | >1/Q(k). Обозначим как К множество таких k. Теперь можем
описать СТПВ Ат для последовательностей. Пусть Р будет полиномом
таким, что тест Т делает самое большее Р (k) запросов для входа
k. Для входа k К и множества Uk Р (k) последовательностей, каждая
длиной 2k бит, тест Ат выполняет двухэтапное вычисление. На
первом этапе Ат равновероятно выбирает i между 0 и k-1. На этапе
2 алгоритм Ат задагт k как вход алгоритма Т и отвечает на запросы
предсказателя Т, постоянно используя множество Uk. Предположим, Т
записывает на ленту предсказателя y=y ...y . if y - первый запрос
с префиксом y ...y then Ат выбирает следующую последовательность
в Uk. Пусть u=u u будет такой последовательностью (u u -
конкатенация u и u , и |u |=|u |=k). Затем Ат запоминает пары (y
...y 0,u ) и (y ...y 1,u ) и дагт ответ G (u ), если y =0 и G (u
), если y =1. else Аi извлекает пару (y ...y , v) и дагт ответ G
(v). Отметим, что Uk состоит из 2k-битных последовательностей,
вырабатываемых КСБ-генератором G для случайно выбранного
k-битного входного начального значения, затем Ат моделирует
вычисление Т с предсказателем Аi. Если же Uk состоит из случайно
выбранных 2kбитных последовательностей, то Ат моделирует
вычисление Т с предсказателем Аi . Вероятность того, что Ат
вырабатывает 1, когда Uk - случайно выбранное подмножество
2k-битных последовательностей, вырабатываемых КСБ-генератором G,
равна (1/k)*p . С другой стороны, вероятность того, что Ат
вырабатывает 1, когда Uk - случайно выбранное подмножество всех
2k-битных последовательностей, равна (1/k)*p . Когда k К, эти
вероятности отличаются, по крайней мере, на (1/k)*|p - p | >
1/(k*Q(k)). Таким образом, последовательнсоти, выработанные G, не
проходят статистический тест Ат, что является противоречием. ****
3.4. ОБОБЩ°ННЫЕ ПОЛИСЛУЧАЙНЫЕ СОВОКУПНОСТИ. Пусть Р и Р будут
полиномами. В ряде применений нам могут потребоваться случайные
функции из I - I (например, при хэшировании из I в I ). Это
требование можно выполнить путгм построения обобщгнной
полислучайной совокупности {F }. Модифицированное построение
легко описать в терминах двух разных КСБ-генераторов: G,
отображающего k битовых последовательностей в 2k битовых
последовательностей, и G', отображающего k случайных входных бит
в Р (k) псевдослучайных бит. Для x Ik функция f F определяется
следующим образом: для входа y I f (y)=G'(G (x)). Аналогично
основной теореме можно доказать, что совокупность {F } обладает
свойствами (1)-(3) полислучайной совокупности. 4. ЗАДАЧИ
ПРЕДСКАЗАНИЯ И ПОЛИСЛУЧАЙНЫЕ СОВОКУПНОСТИ. Физику можно
рассматривать как задачу предсказания. Задача решаема, если: (1)
имеется априорная гарантия, что "законы природы" являются
"простыми"; (2) можно проводить избирательные (selected)
эксперименты; (3) цель состоит всего лишь в приблизительном
выводе "законов природы". Аналогично в теории сложности можно
предположить, что все функции f, которые "просты" (т.е. их легко
рассчитать для некоторого скрытого ключа), можно "приблизительно
вывести" после временного доступа к предсказателю относительно f.
В этой главе мы покажем, что этого не происходит в предположении
существования ОФ. 4.1. ФОРМАЛЬНАЯ ПОСТАНОВКА. Пусть F={Fk} будет
совокупностью функций, а А - вероятностным алгоритмом ПВ,
способного обращаться к предсказателю. Для входа k и при наличии
доступа к предсказателю О относительно функции f Fk алгоритм А
выполняет вычисление, в ходе которого он запрашивает О о x ,...,
x . Затем алгоритм А вырабатывает на выходе x Ik такое, что x=x
,..,x . Это x назовгм выбранной проверкой. В этой точке А теряет
связь с О , и ему предоставляют в случайном порядке два значения
- f(x) и y Ik. Говорим, что А проходит проверку, если он
правильно предполагает, какое из двух значений является f(x).
Пусть Q будет полиномом. Говорим, что А Q-выводит совокупность F,
если для заданного входа k и бесонечно большого количества k он
проходит проверку с вероятностью не меньше 1/2+1/Q(k). Здесь
вероятность бергтся по всем возможным выборам f Fk, броскам
монеты внутри А, всем возможным выборам y и случайному порядку
между f(x) и y. Мы говорим, что совокупность функций F может быть
полиномиально выведена, если существует полином Q и вероятностный
алгоритм ПВ А, который Q-выводит F. Полиномиальный вывод
совокупности F - это очень слабый вид задачи предсказания. Однако
если существует ОФ, это по-прежнему невыполнимая задача, как
следует из теорем 3 и 4. Теорема 4. Пусть F={Fk} будет
совокупностью функций, удовлетворяющих условиям 1
(индексирование) и 2 (вычисление за ПВ) полислучайной
совокупности. Тогда F не может быть полиномиально вычислимой
тогда и только тогда, если она прохдит все СТПВ для функций.
Доказательство. Сперва предположим, что существует вероятностный
алгоритм ПВ А, который Q-выводит совокупность F. Тогда F не
проходит статистический тест для функций Та, описанный ниже. Для
входа k и при наличии доступа к предсказателю О (f Fk или f Hk)
тест Та вызывает вывод алгоритма А со входом k. Для каждого
запроса q, производимого А, тест Та запрашивает О относительно
f(q) и возвращает ответ А. В конце, когда А вырабатывает на
выходе последовательность x в качестве выбранной проверки, Та
запрашивает О об x, случайно выбирает y f(x) и возвращает y и
f(x) в случайном порядке. Если А правильно идентифицирует f(x),
то Та выдагт 1, в противном случае - 0. Для всех k, когда f Hk,
вероятность того, что Та вырабатывает на выходе 1, равна в
точности 1/2. С другой стороны, для бесконечно большого
количества k, когда f Fk, вероятность того, что Та вырабатывает
на выходе 1, больше 1/2+1/Q(k). таким образом, F не проходит Та.
Обратно, предположим, что F не проходит статистический тест Т.
Следовательно, существует полином Q такой, что для бесконечно
большого количества k | p - p |>1/Q(k), где p (p соответственно)
- это вероятность того, что Т вырабабывает на выходе 1 для входа
k и при наличии доступа к предсказателю О относительно f Fk (f Hk
соответственно). Без потери общности можем предположить, что для
бесконечно большого количества k p -p >1/Q(k), и пусть К
обозначает множество всех таких k. Также без потери общности в
ходе такого вычисления Т никогда не делает один запрос дважды и
(для входа k) делает в точности P(k) запросов (для некоторого
полинома P). Мы строим вероятностный алгоритм ПВ Ат, который
использует Т как подпрограмму и 2*P(k)*Q(k)-выводит F. Для входа
k и при наличии доступа к предсказателю О (f Fk) алгоритм Ат
работает следующим образом. Сперва он равновероятно выбирает i
между 0 и P(k)-1. (Ниже мы называем i индексом.) Затем Ат
вызывает Т со входом k и использует предсказателя О для ответа на
первые i запросов Т. Когда Т делает i+1-ый запрос x , Ат выдагт x
в качестве выбранной проверки. При пригме f(x ) и y, где y Ik),
Ат случайно выбирает z {f(x ),y} и дагт z в качестве ответа на
запрос x . Затем алгоритм Ат продолжает отвечать на запросы Т от
x до x , случайно выбирая k-битные последовательности. В конце Т
вырабатывает на выходе бит и останавливается. Если выходом Т был
0, то Ат предполагает, что z Ik, в противном случае,
предполагает, что z=f(x ). При анализе вероятности того, что Ат
делает правильное предположение, может оказаться полезной
концепция (k,i,g)-эксперимента (где g Fk). Выполнить Т со входом
k и ответить на его запросы следующим образом. Пусть x будет j-ым
запросом Т. if j<=i, then ответить g(x ); else ответить случайной
k-битной последовательностью. Пусть p будет вероятностью того,
что Т вырабатывает на выходе 1 в ходе (k,i,g)-эксперимента, когда
g Fk. Отметим, что p = p и p = p . Давайте рассчитаем вероятность
того, что Ат делает верное предположение для входа k К и при
наличии доступа к предсказателю О относительно f Fk. (В этом
вычислении k фиксировано, и вероятности берутся по всем возможным
выборам f Fk и броскам монеты внутри Ат с равномерным
распределением.) Рассмотрим выполнение Ат. Пусть А означает
событие "Алгоритм Ат выбирает индекс=i". Тогда вероятность p(Ат
верен)= = p(А ) * p(Ат верен| А )= = (1/P(k)) * [p(z Ik| А ) *
p(Ат считает, что z Ik| z Ik и А ) + p(z=f(x )| А ) * p(Ат
считает, что z=f(x )| z=f(x ) и А )] = (1/P(k)) * [(1/2) * p(Т
выдагт 0| z Ik и А ) +(1/2) * p(Т выдагт 1| z=f(x ) и А )] (1/(2*
P(k)) * ((1-p ) + p ) >= (1/2) + (1/(2*P(k)*Q(k)). ****
Следствие. Полислучайные совокупности не могут быть полиномиально
выводимыми. Примечание. Наше построение полислучайных
совокупностей обладает "усиливающим эффектом". Предположим, что F
- это полислучайная совокупность, построенная для заданной ОФ g.
Тогда функции в F нельзя полиномиально вывести, даже если g и/или
g полиномиально выводимы. 5. КРИПТОГРАФИЧЕСКИЕ ПРИМЕНЕНИЯ И
ДАЛЬНЕЙШЕЕ СОВЕРШЕНСТВОВАНИЕ Полислучайные совокупности служат
мощным инструментом в криптографии. Функции в таких совокупностях
легко выбрать и рассчитать. Они обладают всеми требуемыми
статистическими свойствами случайных функций по отношению к
противникам, ограниченным вычислением полиномиального времени.
Это предполагает следующую методологию создания протокола. Сперва
строится протокол, который (волшебным образом) использует истинно
случайные функции, и доказывается правильность его работы.
Следующий шаг очнь прост. Заменим истинно случайные функции
функциями, случайно выбранными из полислучайной совокупности. Эта
замена доказательно сохраняет все свойства первоначального
протокола по отношению к полиномиально ограниченным противникам.
Эта методология обеспечивает точные решения таких
криптографических проблем, как аутентификация сообщений при
помощи временных меток, не требующее памяти распределение
секретных идентификаторов, системы опознавания "свой-чужой" и
криптографически сильное хэширование. Подробное обсуждение
применений приводится в [15]. Левин и Голдрих указали в [17а],
что полислучайные совокупности можно использовать для метода
подписи Голдвассера-Микали-Райвеста, не требующей памяти.
Использование полислучайных совокупностей очень важно в честном
протоколе подписания контракта БенОра и др. [6]. Недавно Любый и
Раков [29] использовали полислучайные совокупности для построения
совокупностей полислучайных перестановок. Этот результат ведгт к
построению "идеальных криптосистем с секретным ключом". Левин
[27] предложил модификацию нашего полислучайного построения,
которое можно выполнить за поли(log k) шагов. Отсюда следует, что
если существует КСБ-генератор, работающий в NC, то существует
полислучайная совокупность функций, которую можно рассчитать в
NC. ПРИЛОЖЕНИЕ А1. Достаточные условия для построения
КСБ-генераторов. Пусть Dk Ik и Bk:Dk - {0,1}. Пусть g будет
перестановкой над Dk. Пусть D= Dk, B={Bk} и g={g }. Блюм и Микали
[8] показали, что КСБ-генераторы можно построить при следующих
условиях: (1) область (domain) достижима: существует
вероятностный алгоритм ПВ, который для входа k выбирает x Dk с
равновероятным распределением; (2) перестановку легко рассчитать:
существует алгоритм ПВ, который для входа k выбирает x Dk
рассчитывает g (x); (3) предикат не аппроксимируется (The
predicate is inapproximable). Пусть А будет любым вероятностным
алгоритмом ПВ, а Q - полиномом. Тогда для достаточно больших k:
А(x) = B (x), по меньшей мере, для доли 1/2 - 1/Q(k) для x Dk;
(4) существует алгоритм ПВ, который для входа k и x Dk вычисляет
B (g (x)). Отметим, что их этих условий следует, что g является
односторонней перестановкой, как определено в гл. 2.3. Яо [41]
показал, что существование односторонней перестановки является
достаточным условием для построения КСБ-генераторов. А2. Набросок
построения Яо. Построение Яо[41] можно рассматривать как метод
для построения упомянутых B и g, если задана какаялибо
односторонняя перестановка h={h } над достижимой областью Е= =
Еk. По определению односторонней перестановки [41] не существует
полиномиального алгоритма, который может обратить h, не сделав
при этом ошибку на 1/k доле области для некоторой константы c при
достаточно больших k. Пусть Dk будет декартовым произведением k
копий Ek. Пусть g (x x ...x )=h (x )h (x )...h (x ), где x Ek.
Пусть B (x) будет i-ым битом h (x), где x Ek и B (x x ...x )= + +
B (x ), где + - сложение по модулю

Комментарии

Нет комментариев. Вы можете быть первым!

Оставить комментарий


Warning: Parameter 1 to NP_Captcha::event_FormExtra() expected to be a reference, value given in /home/bh52645/public_html/fucktheplanet.ru/nucleus/libs/MANAGER.php on line 370