O.Goldreich, S.Goldwasser, S.Micali. How to construct random
functions//Journal of the ACM, vol.33, Э4, Oct 1986, pp.792-807.
Аннотация. Разрабатывается конструктивная теория случайности для
функций, основанная на вычислительной сложности. Представлен
генератор псевдослучайной функции. Генератор является
детерминированным алгоритмом полиномиального времени, который
преобразует пару (g,r), где g - некоторая односторонняя функция,
а r - случайная k-битная последовательность, в вычислимые за
полиномиальное время (ПВ) функции f :{1,..,2 } - {1,..,2 }. Эти f
неотличимы от случайных функций любым вероятностным алгоритмом
ПВ, который запрашивает и получает значение функции от выбранного
им аргумента. Результаты применимы в криптографии, случайных
построениях и теории сложности. "Я выполнил на манчестерской ЭВМ
небольшую программу, использующую всего 1000 единиц памяти; с ег
помощью ЭВМ для входного 16-разрядного числа выдавала за 2
секунды в качестве ответа другое число. Я предлагаю на основе
этих ответов разгадать программу с целью предсказания ответов для
любых ранее не испытанных входных значений." А.Тьюринг 1.
ВВЕДЕНИЕ Что имеется ввиду, когда говорят, что определгнные
функции "ведут себя случайно"? В статье мы дадим точный ответ на
этот вопрос. Затем мы покажем эффективный путь построения
функций, которые ведут себя случайно. В завершение покажем
применение нашим построениям. Во второй половине века случайность
привлекала большое внимание. Однако большинство работ посвящено
измерению случайности последовательностей. Согласно понятию
сложности у Колмогорова [10,13,22,24-26,30, 34,37,42] мерой
случайности последовательности является длина ег наименьшего
описания (shortest description). Случайность по Колмогорову это
присущее свойство отдельных последовательностей. Такой подход
неконструктивен и неприменим к генерации псевдослучайных
последовательностей. Отметим, что множество случайцных по
Колмогорову последовательностей нерекурсивно. Интересные
обобщения понятия сложности Колмогорова рассмотрены в
[1,19,36,38]. Здесь последовательность S "случайна", если ег
нельзя выработать программой, которая эффективна (полиномиального
времени) и короче s. Этот подход далгк от генерации
псевдослучайных чисел. Действительно, не существует эффективного
алгоритма, использующего менее k истинно случайных бит и
способного выработать k-битную последовательность, случайную в
упомянутом смысле. Недавно был предложен конструктивный подход к
случайности последовательностей, основанный на вычислительной
сложности [8,41]. При таком подходе множество S
последовательностей является полиномиально случайным
(полислучайным), если программы, выполняемые за полиномиальное
время, приводят к тождественным результатам как в случае
использования элементов, случайно выбранных из S, так и при
случайном выборе из множества всех последовательностей. Такой
подход конструктивен в следующем смысле: существует
детерминированный алгоритм ПВ такой, что для входной k-битной
последовательности выходом является поли(k)-битная
последовательность; причгм, если существуют односторонние
функции, то множество всех выходных последовательностей
полислучайно. В этой статье мы разрабатываем данный подход,
предлагая конструктивную теорию случайности для функций. В
частности: (1) мы вводим меру случайности функций на основе
вычислительной сложности: грубо говоря, назовгм функцию
полислучайной, если не существует такого алгоритма ПВ, который,
запрашивая значения функции для выбранных им аргументов, может
отличить вычисления, во время которых он получает истинные
значения функции, от вычислений, во время которых он получает
выходные значения независимых бросков монеты. Отметим аналогию с
тестом Тьюринга для определения умственных способностей; (2)
предполагая существование односторонних функций, мы предлагаем
алгоритм для построения полислучайных функций. Наша работа
вызвана нерешгнной проблемой в [9] и [7]. Далее мы обсудим
определение полислучайной совокупности - множества функций,
которые легко выбрать и рассчитать и которые достигают
случайности по отношению к вычислению полиномиального времени. Мы
сравним это определение с ранее рассмотренными определениями
односторонних функций и криптографически сильных генераторов
псевдослучайных бит (КСБ-генераторы). 1.1. ПОЛИСЛУЧАЙНЫЕ
СОВОКУПНОСТИ. Пусть Ik означает множество всех k-битных
последовательностей. Рассмотрим множество Hk всех функций из Ik в
Ik. Отметим, что мощность Hk равна 2 . Таким образом, для
определения функции в Hk требуется k*2 бит - это неосуществимая
задача даже при не очень больших k. Теперь предположим, что для
каждого целого k случайно выбирается подмножество Hk Hk мощности
2 . Пусть H обозначает совокупность {Hk}. Таким образом, каждая
функция в Hk имеет уникальный k-битный индекс. Однако с
вероятностью 1 не существует алгоритма ПВ такого, что при
заданном k-битном индексе функции f Hk и x Ik может вычислить
f(x). Наша цель - сделать "случайные функции" доступными для
применений, т.е. построить функции, которые легко определить и
рассчитать и тем не менее нельзя отличить от функций, выбранных
случайно в Hk. Таким образом, мы ограничиваем себя выбором
функций из мультимножества (multiset) Fk (чьи элементы находятся
в Hk), причгм совокупность F={Fk} имеет следующие свойства: (1)
Индексирование: каждая функция Fk имеет ассоциируемый с ней
уникальный k-битный индекс: Fk={f |i Ik}. Таким образом, функцию
f Fk легко случайно выбрать, если можно получить k случайных бит.
(2) Вычисление полиномиального времени: существует полиномиальный
алгоритм, который (для всех k>=1) при вводе индекса i Ik и
аргумента x Ik, рассчитывает f (x). (3) Псевдослучайность: не
существует вероятностного алгоритма, который выполняется за
время, полиномиальное относительно k, и способного отличить
функции в Fk от функций в Hk (точное определение см. в 3.1).
Такая совокупность функций F называется полислучайной
совокупностью. Грубо говоря, несмотря на то, что функции в Fk
легко выбрать и рассчитать, с точки зрения исследователя с
полиномиально ограниченными ресурсами они обладают всеми
свойствами случайно выбираемых в Hk функций. Приведгнное
определение весьма конструктивно. Мы преобразуем любой
КСБ-генератор (высококачественный генератор псевдослучайных бит,
обсуждаемый в гл.2) в полислучайную совокупность. Было показано
(см. 2.2), что КСБ-генераторы можно построить при наличии
односторонних функций. 1.2. СРАВНЕНИЕ С ОДНОСТОРОННИМИ ФУНКЦИЯМИ.
Нестрого говоря, односторонние функции (ОФ) - это функции,
которые легко рассчитать, но трудно обратить для непренебрежимой
части примеров. Мы строим случайные функции из любой
односторонней функции, что подтверждает громадный потенциал,
заложенный в определение ОФ. Однако этой мощью необходимо
пользоваться осторожно. Хотя обращение ОФ весьма непредсказуемо,
это не означает, что оно случайно. Действительно, все функции,
которые сейчас считаются односторонними удовлетворяют различным
алгебраическим тождествам (например, RSA-функция [33] - это
мультипликативная перестановка; следовательно, при заданном
обращении для x и y можно легко найти обращение для x*y). Этого
не происходит для истинно случайных функций, и, фактически, не
происходит для функции, случайно выбранной из полислучайной
совокупности {Fk}. В частности, наше построение скрывает все
алгебраические тождества, которым удовлетворяет лежащая в основе
ОФ, от наблюдателя с полиномиально ограниченными ресурсами. По
существу, полислучайные совокупности обладают следующим
свойством. Случайно выбирается и фиксируется f Fk. Пусть
вероятностный поли(k)-временной алгоритм А запрашивает значение f
от полиномиально большого (относительно k) числа аргументов по
своему выбору: y , y ,.., y . Пусть затем А выбирает аргумент x
(x=y для всех i) для проверки. Если теперь предоставить А в
случайном порядке два числа, одно из которых f(x), а другое -
случайное k-битное число, он не сможет решить, какое из них
является f(x) с вероятностью, существенно превышающей 1/2. Таким
образом, если f выбирается в полислучайной совокупности, то не
только нельзя найти значение f(x) при помощи значений f от других
аргументов, но его даже нельзя распознать! Приведгнный тест
является полным определением полислучайных совокупностей (см.
гл.4). 1.3. СРАВНЕНИЕ С КСБ-ГЕНЕРАТОРАМИ. В этом подразделе мы
обращаемся к проблеме моделирования вероятностных вычислений ПВ с
целью сбережения таких основных ресурсов, как бросания монеты и
память. Как мы увидим, при вероятностных вычислениях ПВ
КСБ-генераторы позволяют сберечь бросания монеты, а полислучайные
совокупности - и бросания монеты, и память (вычисления
производятся со случайным предсказателем). КСБ-генераторы - это
эффективные детермининрованные программы, развгртывающие
(случайное) k-битное входное начальное значение в k -битную
выходную (псевдослучайную) последовательность для некоторой
константы t>0. Эти последовательности неотличимы в ПВ от k -
битных истинно случайных последовательностей (см. подробно в
2.1). Следовательно, мы можем заменить бросания монеты в
вероятностном поли(k)-временном вычислении битовой
последовательностью, сгенерированной КСБ-генератором на случайной
k-битной последовательности, и получить те же результаты. Теперь
обратимся к проблеме эффективного моделирования более сложных
вероятностных вычислений - вычислений со случайным
предсказателем. Случайный предсказатель (СПр) [4] - это
специальный случай случайной функции: он связывает результат
одного бросания монеты с каждой последовательностью. При
вычислении со СПр алгоритм запрашивает его последовательностью q
и получает связанный с q бит (обозначаемый b(q)). Поскольку b(q)
не изменяется со временем, алгоритм может не хранить пару
(q,b(q)), а просто запрашивать СПр при помощи q при необходимости
получения b(q). Преимущества таких вычислений поясняются
применениями в гл.5. Вычисление ПВ, запрашивающее СПр при помощи
k последовательностей длины k, может быть тривиально моделировано
с использованием КСБ-генератора и всего лишь k монет (см. ниже).
Однако такое тривиальное моделирование СПр требует k бит памяти.
Сохраним случайно выбранную k-битную последовательность s и
обозначим как b i-ый бит, выработанный КСБ-генератором для
входного значения s. Пусть q будет i-ым новым запросом (т.е.
запросом, который не производился ранее). Тогда положим, что b(q
)=b , добавим (закодированный) q к списку старых запросов и
выдадим ответ b . Упорядоченный список старых запросов позволяет
нам определять, производился ли запрос ранее, и если это так, то
дать такой же ответ. Отметим, что список старых запросов
действительно необходим. Такой список может быть тяжело
подвергнуть значительному сжатию (например, при случайно
выбранных запросах). Таким образом, в наихудшем случае
моделирование требует k бит памяти. Интересное свойство
полислучайных последовательностей состоит в том, что они
обеспечивают такой же результат для любых вычислений ПВ со
случайным предсказателем для k-битных последовательностей,
используя только k бросаний монеты и храня только k бит! Это
осуществляется путгм случайного выбора и запоминания k-битного
индекса, определяющего функцию f в полислучайной совокупности.
Бит, ассоциируемый с каждой последовательностью x, является
первым битом f(x). Разделение случайности в распределгнной среде.
Дополнительное преимущество полислучайных совокупностей состоит в
том, что они позволяют нескольким сторонам эффективно разделять
случайную функцию f в распределгнной среде. Под разделением f мы
понимаем, что если f рассчитывается в разное время разными
сторонами от одного и того же аргумента x, то будет получено
одинаковое значение f(x). Такое разделение может быть получено
бросанием k монет для определения функции f в полислучайной
совокупности. Эти k бит передаются и хранятся каждым процессором.
Для разделения процессорами f больше не требуется никакого обмена
сообщениями. 1.4. СИСТЕМА ОБОЗНАЧЕНИЙ И СОГЛАШЕНИЯ. В статье не
рассматривается колмогоровское понятие сложности. Упоминая
случайный элемент, мы имеем ввиду элемент, случайно выбранный из
соответствующего множества. Пусть А будет мультимножеством с
отдельными элементами а ,.., а , встречающимися с частотой m ,..,
m соответственно. Тогда |А|= m . Под записью а А мы имеем ввиду,
что элемент а был случайно выбран из мультимножества А. Таким
образом, элемент, встречающийся в А с частотой m, выбирается с
вероятностью m/|А|. Для единства обозначений параметр k,
задаваемый в качестве входа для любого алгоритма, обсуждаемого в
этой статье, представляется в унарном виде. (Мы анализируем время
работы алгоритмов по отношению к длине их входного значения, а
ряд алгоритмов в этой статье имеют на входе только k). В качестве
основной вычислительной модели мы выбрали машину Тьюринга. Можно
легко привести утверждения и доказательства наших результатов к
виду, определяемому моделью цепей (circuit model). 1.5.
ПОСТРОЕНИЕ СТАТЬИ. В главе 2 мы коротко напоминаем основные
определения и результаты относительно КСБ-генераторов и
нерешгнной проблемы "лггкого доступа" (easy-access). В главе 3 мы
формально определим полислучайные совокупности и покажем, как их
построить при заданной односторонней функции. В главе 4 мы опишем
полислучайные совокупности в качестве чрезвычайно сложных задач
предсказания. В главе 5 коротко обсудим различные применения
полислучайных совокупностей. 2. КСБ-ГЕНЕРАТОРЫ Генератор
псевдослучайных чисел - это детермининрованный и эффективный
алгоритм, развгртывающий случайное входное число (начальное
значение) в длинную последовательность псевдослучайных чисел.
Псевдослучайная последовательность должна обладать "некоторыми"
статистическими свойствами, присущими истинно случайным
последовательностям (например, приблизительно равное число 0 и
1). Многие статистические свойства линейной конгруэнтной
последовательности псевдослучайных чисел x =a*x +b (mod n) были
изучены Кнутом [21]. Однако в отличие от истинно случайных
последовательностей в линейной конгруэнтной последовательности
можно легко рассчитать следующее число из предыдущих чисел, даже
если x , a, b и n не заданы [31]. См. также [12,20,23]. Шамир
[35] предложил ГПСЧ, для которого вычисление следующего числа
последовательности из предыдущих так же сложно, как обращение
RSA-функции. Однако несмотря на непредсказуемость, числа в такой
последовательности могут и не оказаться "случайными" (например,
их старшие биты легко предсказать). Все эти проблемы доказательно
не возникают для КСБ-генераторов. 2.1. ОПРЕДЕЛЕНИЕ
КСБ-ГЕНЕРАТОРА. Блюм и Микали [8] предложили определение
криптографически сильного псевдослучайного генератора
(КСБ-генератора). Пусть Р будет полиномом. КСБ-генератор G - это
детермининрованный поли(k)-временная программа, развгртывающая
kбитное случайно выбранное начальное значение в P(k)-битную
последовательность (называемую КСБ-последовательностью), которая
проходит все тесты следующего бита. Пусть P будет полиномом, Sk -
мультимножеством P(k)-битных последовательностей и S= Sk. Тест
следующего бита для S - это вероятностный алгоритм ПВ Т, который
для входного значения k и первых i бит последовательности s Sk
производит на выходе бит b. Пусть p обозначает вероятность того,
что b равно i+1му биту s. Говорим, что s проходит тест следующего
бита Т, если для всех полиномов Q, достаточно больших k и для
всех целых i [0,P(k)] | p - 1/2 | < 1/Q(k) . Более общее
определение случайности последовательности предложено Яо [41].
2.2. СТАТИСТИЧЕСКИЕ ТЕСТЫ ПОЛИНОМИАЛЬНОГО ВРЕМЕНИ ДЛЯ
ПОСЛЕДОВАТЕЛЬНОСТЕЙ. Определение (Яо). Пусть P и P будут
полиномами, а S= Sk - мультимножеством последовательностей, где
Sk состоит из P(k)-битных последовательностей. Статистический
тест полиномиального времени (СТПВ) для последовательностей - это
вероятностный алгоритм ПВ Т, который на входе получает P (k)
последовательностей, каждая длиной P(k) бит, и производит на
выходе 0 или 1. Говорим, что S проходит тест Т, если для любого
полинома Q и достаточно больших k | p - p | < 1/Q(k), где p
означает вероятность того, что Т вырабатывает на выходе 1 для P
(k) случайно выбранных из Sk последовательностей, а p означает
вероятность того, что Т вырабатывает на выходе 1 для P (k)
случайно выбранных битовых последовательностей, каждая длиной
P(k). Особый интерес представляет случай, когда полином P (k)
является константой 1, и статистический тест получает на входе
единственную последовательность. Следующее определение играет
важную роль для связи приведгнных определений случайности.
Говорим, что мультимножество S= Sk выборочно, если существует
вероятностный алгоритм ПВ такой, что при заданном входе k
вырабатывает на выходе s Sk. Теорема 1. (Яо [41]). Пусть S= Sk -
выборочное множество битовых последовательностей. Тогда три
следующих утверждения эквивалентны: (i) S проходит тест
следующего бита. (ii) S проходит все СТПВ для
последовательностей. (iii) S проходит все СТПВ, чьи входы состоят
из единственной последовательности в S. Отметим, что
КСБ-последовательности образуют выборочное мультипликативное
множество. Следовательно, (*) КСБ-последовательности проходят все
СТПВ. Фактически, в [41] в точном виде содержится только
утверждение (*). Однако его доказательство включает все идеи,
требуемые для доказательства эквивалентности трех условий теоремы
1. Читатель может получить доказательство теоремы 1 из
доказательства теоремы 4 (которую можно рассматривать как
обобщение теоремы 1). 2.3. РЕАЛИЗАЦИЯ КСБ-ГЕНЕРАТОРОВ. Блюм и
Микали [8] представили алгоритмический метод построения
КСБ-генераторов, основанный на теоретическом предположении общей
сложности (см. краткое изложение в разделе А1 приложения). Они
также представили первый пример схемы, основанный на
специфическом сложностном предположении: предположение
трудноразрешимости задачи о дискретных логарифмах (ЗДЛ). А
именно, если следующий бит в последовательностях, вырабатываемых
их генератором, можно предсказать с вероятностью, большей 1/2+ ,
то существует поли(k, )-алгоритм для решения ЗДЛ для части всех
простых чисел длины k. Более эффективный КСБ-генератор,
основанный на ЗДЛ, можно найти в [28]. Найдены и другие примеры
КСБ-генераторов, основанные на различных предположениях из теории
чисел. КСБ-генераторы, основанные на задаче квадратичных остатков
появились в [41] и [7]. Первый гератор, основанный на разложении
на множители, появился в [41]. Более эффективные генераторы,
основанные на этом же принципе см. в [2,5,18,39]. Как указано в
[40], результаты в [2] позволяют сделать вывод, что генераторы на
базе квадратичных остатков [4,17] фактически основаны на
разложении на множители. В более общем плане Яо [41] показал, как
получить КСБ-генераторы, если задана любая односторонняя
перестановка. Левин [27] показал, как получить КСБ-генератор при
более слабом условии: существовании односторонней функции (см.
ниже). Определение (Левин). Пусть Dk Ik. Пусть f :Dk - Dk будет
последовательностью функций, и пусть функция f будет определена
следующим образом: f(x)=f (x), если x Dk. Пусть f обозначает f,
применгнную i раз. Пусть D Dk так, что y D , если н=f (x) для
некоторого x Dk. f является односторонней функцией, если: (1) f
вычислима за полиномиальное время; (2) f трудно обратить, т.е.
для каждого вероятностного алгоритма ПВ А, для всех достаточно
больших k и для каждого i, 1<=i<=k , А(x) = f (x) по крайней мере
для постоянной доли x D ; (3) Dk является выборочным. Теорема 2
(Левин [27]). Односторонняя функция существует тогда и только
тогда, если существует КСБ-генератор. Эта теорема конструктивна.
Левин показывает частный генератор, который является
КСБ-генератором, если только КСБ-генератор вообще существует.
Левин использует построение согласно Яо [41], показанное коротко
в главе А2 приложения. 2.4. КСБ-ГЕНЕРАТОРЫ С ЛГКИМ ДОСТУПОМ.
Отметим, что хотя КСБпоследовательнсоть, сгенерированная при
помощи k-битного начального значения, состоит из полиномиально
большого (относительно k) количества бит, КСБ-генератор и
начальное значение s определяют бесконечную (в конечном итоге
периодическую) битовую последовательность b , b ,.. Интересная
особенность, впервые показанная в генераторе Блюма [7],
заключается в том, что знание начального значения позволяет
лггкий доступ к каждому из первых 2 бит; т.е. если log i < k, то
i-ый бит последовательности b можно рассчитать за поли(k)-время.
Это происходит из-за специальной односторонней перестановки, на
которой построена безопасность генератора. Однако эта легко
доступная, экспоненциально длинная битовая последовательность
может не оказаться "случайной". Блюм и др. доказали только, что
любой единственный полиномиально длинный интервал
последовательных бит в последовательности проходит все СТПВ для
последовательностей при условии, что извлечение квадратного корня
по модулю целого числа Блюма n является односторонней
перестановкой (над квадратными корнями по модулю n). (Целое число
Блюма - это целое в виде P1*P2, где P1 и P2 - два различных
простых числа, сравнимых с 3 mod 4.) Действительно, возможно, что
при заданных b ,..,b и b ,..,b легко рассчитать любой другой бит
последовательности. Открытая проблема лггкого доступа состоит в
том, является ли лггкий доступ к экспоненциально удалгнным битам
в их псевдослучайном пути операцией, "сохраняющей случайность".
Эта проблема была выдвинута Брассардом [9], `люмом и др. [7], а
также рассматривалась Англюэ и Лихтенстайном [3]. Отметим, что
имеется естественное однозначное соответствие между "сохраняющими
случайность" легко доступными k*2 -битными последовательностями и
случайными функциями из Ik в Ik. Строя полислучайную совокупность
F={Fk}, мы фактически строим k*2 -битные последовательности {s
=f(1)f(2)...f(2 )| f Fk}, к которым можно легко получить доступ
"сохраняющим случайность" образом. Это практически решает
проблему лггкого доступа. Фактически наше построение
демонстрирует другой путь получения выгоды, которую обеспечивал
бы положительный ответ на проблему лггкого доступа. И что ещг
лучше, мы строим полислучайные совокупности не только в том
случае, если извлечение квадратного корня по модулю целого числа
Блюма является ОФ, но при любой заданной ОФ.
