реклама
ЭКСПЕРТИЗА САЙТОВ НА СЛИВ ИНФОРМАЦИИ

ВОССТАНОВЛЕНИЕ ИНФОРМАЦИИ С РАЗЛИЧНЫХ НАКОПИТЕЛЕЙ В КИЕВЕ
уход за растениями - озеленение - фитодизайн
реклама

proxy  статьи  библиотека  softice  free_юр.консультация  hard  iptv
рекламодателям  фирмы/add  расшифровка штрих-кодов  links/add

http://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.

Содержание

HOME


Если у вас есть сайт или домашняя страничка - поддержите пожайлуста наш ресурс, поставьте себе кнопочку, скопировав этот код:

<a href="http://kiev-security.org.ua" title="Самый большой объем в сети онлайн инф-ции по безопасности на rus" target="_blank"><img src="http://kiev-security.org.ua/88x31.gif" width="88" height="31" border="0" alt="security,безопасность,библиотека"></a>

Идея проекта(C)Anton Morozov, Kiev, Ukraine, 1999-2020, security2001@mail.ru