ПОСТРОЕНИЕ ПОЛИСЛУЧАЙНЫХ СОВОКУПНОСТЕЙ В этой главе мы
покажем, как построить совокупность функций, которые проходят все
"полиномиально ограниченные" статистические тесты. Совокупность
функций F - это совокупность {Fk} таких, что для всех k и всех f
Fk f:Ik - Ik. 3.1. СТАТИСТИЧЕСКИЕ ТЕСТЫ ПОЛИНОМИАЛЬНОГО ВРЕМЕНИ
ДЛЯ ФУНКЦИЙ. Определение. СТПВ для функций - это вероятностный
алгоритм ПВ Т, который для заданного 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 ), где + - сложение по модулю 2. Литература: 1. Adelman L.
Time, Space and Randomness. Tech. Memo 131, Lab. for Computer
Science MIT, Cambridge, Mass., 1979. 2. Alexi W., Chor B.,
Goldreich O., Schnorr C.P. RSA and Rabin functions: Certain parts
are as hard as the whole. SIAM J. to appear. (Ранняя версия в
Proc. of the 25th IEEE Symp. on Foundations of Computer Science.
IEEE, New York, 1984, pp. 449457). 3. Angluin D., Lichtenstein D.
Provable security of cryptosystems: A Survey. Tech. Rep. 288,
Dept. of Computer Science, Yale Univ. New Haven, Conn., 1983. 4.
Bennett C.H., Gill J. Relative to a random oracle, A, P =NP =
co-NP with probability 1. SIAM J. Comput. 10 (1981), 96-113. 5.
Ben-Or M., Chor B., Shamir A. On the cryptographic security of
single RSA bits. In Proc. of the 15th ACM Symp. on Theory of
Computing (Boston, Mass., Apr. 25-27). ACM, New York, 1983, pp.
43-52. 6. Ben-Or M., Goldreich O., Micali S., Rivest R.L. A fair
protocol for signing contracts. In Automata, Languages and
Programming, 12th Colloquium, W.Brauer, Ed. Lecture Notes in
Computer Science, vol.194, Springer-Verlag, New York, 1985,
pp.4352. 7. Blum L., Blum M., Shub M. A simple unpredictable
pseudo-random number generator. SIAM J.Comput. 15 (May 1986),
364-383. 8. Blum M., Micali S. How to generate cryptographically
strong sequences of pseudo-random bits. SIAM J.Comput. 13 (Nov
1984), 850-864. 9. Brassard G. On computationally secure
authentication tags requiring short secret shared keys. In
Advances in Cryptology: Proceedings of Crypto-82, D.Chaum,
R.L.Rivest, A.N.Sherman, Eds. Plenum Press, New York, 1983,
pp.79-86. 10. Chaitin G.J. On the length of programs for
computing finite binary sequences. J. ACM 13, 4 (Oct 1966),
547-570. 11. Diffie W., Hellman M.E. New directions in
cryptography. IEEE Trans. Inf. Theory, IT-22 (Nov 1976), 644-654.
12. Freize A.M., Kannan R., Lagarias J.C. Linear congruential
generators do not produce random sequences. In Proccedings of the
25th Symposium on Foundations of Computer Science. IEEE, New
York, 1984, pp.480-484. 13. Gacs P. On the symmetry of
algorithmic information. Sov.Math. Dokl. 15 (1974), 1477. 14.
Goldreich O., Goldwasser S., Micali S. How to construct random
functions. Tech. Memo 244, Laboratory for Computer Science, MIT,
Cambridge, Mass., Nov. 1983. 15. Goldreich O., Goldwasser S.,
Micali S. On he cryptographic applications of random functions.
In Advances in Cryptology: Proceedings of Crypto-84, B.Blakely,
Ed. Lecture Notes in Computer Science, vol.196, Springer-Verlag,
New York, 1985, pp. 276-288. 16. Goldwasser S. Probabalistic
encryption: Theory and applications. Ph.D. dissertation, Dept. of
Computer Science, Univ. of California, Berkeley, Calif., 1984.
17. Goldwasser S., Micali S., Rivest R.L. A "paradoxical"
signature scheme. In Proc. of the 25th IEEE Symp. on Foundations
of Computer Science. IEEE, New York, 1984, pp. 441-448.
17a.Goldwasser S., Micali S., Rivest R.L. A digital signature
scheme secure against adaptive chosen method attack. SIAM J. to
appear. 18. Goldwasser S., Micali S., Tong P. Why and how to
establish a private code on public network. In Proc. of the 23th
IEEE Symp. on Foundations of Computer Science. IEEE, New
York,1982, pp. 134-144. 19. Hartmanis J. Generalized Kolmogorov
complexity and the structure of feasible computations. In Proc.
of the 24th IEEE Symp. on Foundations of Computer Science. IEEE,
New York,1983, pp. 439-445. 20. Hastad J., Shamir A. The
cryptographic security of truncated linearly related variables.
In Proc. of the 17th ACM Symp. on Theory of Computing
(Providence, R.I.,May 6-8). ACM, New York, 1985, pp. 356-362. 21.
Кнут Д. Искусство программирования, т.2. 22. Колмогоров А.Н. Три
подхода к определению понятия количества информации. Пробл.
перед. инф., 1, 1, 1965, с.3-11. 23. Lagarias J., Reeds J.
Extrapolation of nonlinear recurrences. Submitted for
publication. 24. Levin L.A. On a notion of a random sequence.
Sov. Math. Dokl. 14, 5 (1973), 1413. 25. Levin L.A. Various
measures of complexity for finite objects (axiomatic
descriptions). Sov. Math. Dokl. 17, 2 (1976), 522526. 26. Levin
L.A. Randomness conservation inequalities, information and
independence in mathematical theories. Inf. Control 61 (1984),
15-37. 27. Levin L.A. One-way function and pseudo-random
generators. In Proc. of the 17th ACM Symp. on Theory of Computing
(Providence, R.I., May 6-8). ACM, New York, 1985, pp. 363-365.
28. Long D.L., Wigderson A. How discreet is dicscrete log?
Готовится. Предварительная версия в Proc. of the 15th ACM Symp.
on Theory of Computing (Boston, Mass., Apr. 25-27). ACM, New
York, 1983, pp. 413-420. 29. Luby M., Rackoff C. Pseudo random
permutation generators and cryptographic composition. In Proc. of
the 18th ACM Symp. on Theory of Computing (Berkeley, Calif., May
28-30). ACM, New York, 1986, pp. 356-363. 30. Martin-Lof P. The
definition of random sequences. Inf.Control 9 (1966), 602-619.
31. Plumstead J. Inferring a sequence generated by a linear
congruence. In Proc. of the 23rd IEEE Symp. on Foundations of
Computer Science. IEEE, New York, 1982, pp. 153-159. 32. Rabin
M.O. Digitalized signatures and public key functions as
intractable as factoring. Tech. Rep. 212, Laboratory for Computer
Science, Cambridge, Mass., 1979. 33. Rivest R., Shamir A.,
Adleman L. A method for obtaining digital signatures and public
key cryptosystems. CACM, 21, 2 (Feb 1978), 120-126. 34. Schnorr
C.P. Zufaelligkeit und Wahrscheinlichkeit. Lecture Notes in
Mathematics, v.218. Springer-Verlag, New York, 1971. 35. Shamir
A. On the generation of cryptographically strong pseudorandom
sequences. ACM Trans. Comput. Syst. 1, 1 (Feb 1983), 38-44. 36.
Sipser M. A complexity theoretic approach to randomness. In Proc.
of the 15th ACM Symp. on Theory of Computing (Boston, Mass., Apr.
25-27). ACM, New York, 1983, pp. 330-335. 37. Solomonoff R.J. A
formal theory of inductive inference. Inf. Control 7, 1 (1964),
1-22. 38. Wilber R.E. Randomness and the density of hard
problems. In Proc. of the 24th IEEE Symp. on Foundations of
Computer Science. IEEE, New York, 1983, pp. 335-342. 39. Vazirani
U.V., Vazirani V.V. RSA bits are .732+ secure. In Advances in
Cryptology: Proceedings of Crypto-82, D.Chaum, Ed. Plenum Press,
New York, 1983, pp.369-375. 40. Vazirani U.V., Vazirani V.V.
Efficient and secure pseudo-random number generation. In Proc. of
the 25th IEEE Symp. on Foundations of Computer Science. IEEE, New
York, 1984, pp. 458463). 41. Yao A.C. Theory and application of
trapdoor functions. In Proc. of the 23rd IEEE Symp. on
Foundations of Computer Science. IEEE, New York, 1982, pp. 80-91.
42. Zvonkin A.K., Levin L.A. The complexity of finite objects and
the algorithmic concepts of randomness and information. UMN
(Russian Math. Surveys) 25, 6 (1970), 83-124.
