kiev-security.org.ua-Криптография.Как построить случайные функции. Построение полислучайных совокупностей

ПОСТРОЕНИЕ ПОЛИСЛУЧАЙНЫХ СОВОКУПНОСТЕЙ В этой главе мы покажем, как построить совокупность функций, которые проходят все "полиномиально ограниченные" статистические тесты. Совокупность функций 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.