M.Blum, S.Micali. How to generate cryptographically strong
sequences of pseudo-random bits// SIAM J. Comput., vol.13, no.4,
1984, pp.850-864.
Аннотация. Приводится совокупность условий, позволяющая
вырабатывать непредсказуемые с вероятностью 50 на 50 биты. На
базе этих условий представлен общий алгоритмический метод
построения детерминированных алгоритмов полиномиального времени,
которые развертывают короткое секретное случайное входное
значение в длинную последовательность непредсказуеемых
псевдослучайных битов. Приводится реализация этого метода, и
рассматривается псевдослучайный битовый генератор, для которого
любая эффективная стратегия предсказания следующего выходного
бита с вероятностью, лучшей, чем 50 на 50, легко сводится к
"равноэффективному" алгоритму решения задачи о дискретных
логарифмах. В частности: если задачу о дискретных логарифмах
нельзя решить за вероятностное полиномиальное время, то не
существует вероятностного алгоритма полиномиального времени,
который способен предсказать следующий выходной бит лучше, чем
при бросании монеты: если выпадает "орел", предполагаем "0", если
"решка" - "1". Ключевые слова: случайность, выработка
псевдослучайных чисел, непредсказуемость, случайная
самосводимость. 1. ВВЕДЕНИЕ 1.1. Случайность и теория сложности
Мы предлагаем новый метод выработки последовательностей
псевдослучайных битов. Любой такой метод, прямо или косвенно,
приводит к определению случайности. Во второй половине этого
столетия прилагалось много усилий по формулированию точного
определения случайности. Напомним в нестрогом виде известное
определение Колмогорова [18]: Последовательность битов А=а ,а
,...,а является случайной, если длина наименьшей программы,
вырабатывающей А, равна по меньшей мере k. Отметим, что длина
программы с точки зрения вычислительной сложности является весьма
неестественной мерой. Желательно было бы исследовать более
рабочее определение случайности в свете теории сложности.
Мысленный эксперимент. А и В хотят сыграть в орлянку четырьмя
различными способами. Во всех из них А "честно" бросает "честную"
монету. В первом случае А просит В заключить пари, а затем
бросает монету. Можно ожидать, что В будет выигрывать в 50%
случаев. Во втором способе А подбрасывает монету, и пока она
крутится в воздухе, заключает пари с В. По-прежнему ожидается,
что В будет выигрывать в 50% случаев. Однако во втором случае
исход броска определен, когда В заключает пари: в принципе, он
может рассчитать уравнение движения и победить! Третий способ
похож на второй: В может заключить пари, пока монета крутится в
воздухе, но кроме того у него имеется карманный калькулятор.
Несомненно, он по-прежнему будет выигрывать в 50% случаев, так
как монета упадет еще до начала каких-либо вычислений. Четвертый
способ похож на третий, но у В имеется мощный компьютер,
способный делать снимки вращающейся монеты и быстро расссчитывать
ее скорость, инерцию и т.д. Нельзя сказать, что В будет всегда в
выигрыше, но можно подозревать, что он победит в 51% случаев!
Цель приведенного примера состоит в формулировании следующего
предположения: случайность события относительна для определенной
модели вычислений и определенного количества вычислительных
ресурсов. Связи между случайностью и вычислительной моделью были
показаны Майклом Сипсером в [31], где он определяет случайность
относительно автоматов с конечным состоянием (см. также [24]). В
своей замечательной статье [29] Шамир также рассматривает влияние
вычислительных ресурсов, указывает на значительный прогресс в
этом направлении и на нерешенные задачи. В данной статье
исследуется случайность k-битных последовательностей для
вычислительной модели на основе булевых схем со всего лишь
poly(k) вентилями. 1.2. КСПСБ-генераторы Предлагается определение
криптографически сильного псевдослучайного битового (КСПСБ)
генератора и показывается, при каких условиях он может быть
построен. КСПСБ-генератор - это программа G, которая после
получения в качестве входного значения случайного числа i (будем
называть его начальным заполнением), вырабатывает
последовательность псевдослучайных битов b ,b ,b ,... G обладает
следующими свойствами: 1) биты b легко выработать. Каждый b
вырабатывается за время, полиномиальное относительно длины
начального заполнения; 2) биты b непредсказуемы. Если заданы G и
b ,..,b , первые s выходных битов, но не начальное заполнение i,
то вычислительно невозможно предсказать (s+1)-ый бит
последовательности с вероятностью, лучшей, чем 50 на 50. Здесь s
полиномиально относительно длины начального заполнения. Наши
генераторы являются улучшением генераторов псевдослучайных чисел
Шамира. Шамир предлагает программу, которая из короткого
секретного случайного начального заполнения вырабатывает
последовательность чисел x таких, что способность предсказать
следующее выходное значение эквивалентна обращению RSA-функции
[27]. Главное отличие нашего генератора от генератора Шамира в
следующем: его генератор вырабатывает не биты, а числа. Такие
числа могут быть непредсказуемыми, причем в особом виде. В
частности, каждый бит (информации относительно) следующего числа
в последовательности может быть сильно смещен или предсказуем с
высокой вероятностью. Как следствие, если сгенерированные таким
образом числа имеют длину 100 бит, они могут не быть равномерно
распределенными на интервале [1, 2^100]. 1.3. Псевдослучайные
последовательности и статистические тесты Прохождение заданных
статистических тестов является ключевым моментом в оценке
псевдослучайных последовательностей. Классическая
последовательность x =ax +b mod n позволяет быстро получать
псевдослучайные числа. Известно, что такая последовательность
(при умном выборе параметров a, b и n) вырабатывает "хорошо
перемешанные числа" (см. Кнут [17]). Однако они не являются
криптографически сильными. Плюмстед [25] показывает, что
последовательность можно вывести даже при неизвестных a, b и n. В
противоположность, наши битовые последовательности нельзя
сгенерировать так быстро, но и нельзя вывести, потому что они
имеют "вложенную" трудную задачу. У Блюма, Блюма и Шуба [9]
приводится анализ очень простого генератора псевдослучайных
чисел. Они показывают, что хорошо перемешанные последовательности
со вложенными трудными задачами тем не менее могут быть слабыми
псевдослучайными последовательностями. Требуется нечто большее
для построения хороших генераторов псевдослучайных
последовательностей, о чем рассказано в разделе 2.
Непредсказуемость следующего выходного бита является основным
тестом, исследуемым в данной статье. В более раннем варианте
статьи [10] мы представили детерминированный алгоритм
полиномиального времени, который развертывал случайное k-битное
начальное заполнение в полиномиально (по k) длинную битовую
последовательность. Любой вероятностный алгоритм полиномиального
времени, правильно предсказывающий следующий бит с вероятностью,
большей 1/2+ в выработанной таким образом псевдослучайной
последовательности, можно легко преобразовать в вероятностный
алгоритм, выполняемый за ожидаемое poly(k, )-время, для решения
задачи о дискретных логарифмах для части простых чисел длины k.
Хотя мы осознавали полиномиальную зависимость относительно
(фактически лемма 2 в [10] точно устанавливает это), наша главная
теорема обощала результаты, утверждающие, что следующий бит в
наших псевдослучайных последовательностях нельзя предсказать за
полиномиальное (по k) время с вероятностью, большей 1/2+ для 0<
<1. Яо [33] первым осознал важность полиномиальной функциональной
зависимости от и прекрасно ее использовал (см. 1.3.2). В самом
деле, не меняя наш алгоритм, можно заменить на меньшее значение,
сохраняющее полиномиальным время выполнения. Поскольку в нашем
случае время выполнения полиномиально относительно k и , то
впредь в статье будем использовать вместо 1/poly(k). 1.3..1. Тест
следующего бита Пусть P будет полиномом, а S={Sk} - совокупностью
мультимножеств таких, что Sk содержит P(k)-битные
последовательности (одна и та же последовательность s может
принадлежать Sk более одного раза). Пусть Р1 будет полиномом.
Предсказующая совокупность С={C } - совокупность схем таких, что
каждая схема С имеет меньше, чем P1(k) вентилей, i булевых
входов, i=1/P3(k) для каждого k F, где F бесконечно. Пусть k F.
Обозначим как ту часть начальных заполнений длины k, для которых
первые P1(k)+ +P2(k)+i бит в соответствующей
КСПСБ-последовательности образуют (P1(k),P2(k))-периодическую
последовательность. Тогда мы имеем 1= >= >=...>= >= >= 1/P3(k).
Пусть целое i [0,2*P3(k)) будет таким, что - <= 1/2(1/P3(k)).
(Такое i существует, в противном случае - >1). Рассмотрим
следующий алгоритм А, который предсказывает (i+1)-ый бит в
КСПСБ-последовательности b ,b ,...,b , выработанной при начальном
заполнении длины k: Рассмотрим S=b ,..,b . Если S не является
(P1(k),P2(k))-периодической последовательностью, b
предсказывается бросанием монеты. В противном случае, b
предсказывается так, чтобы сохранить (P1(k),P2(k))-периодичность.
Ввиду того, что >=1/P3(k), и нашего выбора i Ak будет правильно
предсказывать b с вероятностью, большей 1/2 + 1/(2*P3(k)). Мы
получили противоречие в том, что для некоторого полинома P и для
каждого k F Ak можно преобразовать в схему Ck с менее, чем P(k)
вентилями, выполняющую ту же задачу. **** Упомянем, что
рассмотренные алгоритмы Ak можно заменить равномерным
вероятностным алгоритмом полиномиального времени, использующим
выборку. 2.1. Проблемы в построении генераторов Пусть В будет
предикатом, определенным в области D с 2^k элементами такой, что
В(х)=1 для половины х из D. Тогда мы можем выработать случайные
биты b ,b ,..., случайно выбирая х из D и получая b =В(х ).
Недостаток этого метода в том, что требуется использовать k
случайных бит для выбора каждого х , а вырабатываем при этом
единственный бит b . Вместо этого, будем случайно выбирать из D
только первое х , а остальные х будем выбирать детермининрованным
образом, а именно, положив, что х =f(х ), где f -
детерминированная функция. Проблемы данного подхода
иллюстрируются следующим примером. Пусть D сосотоит из целых
чисел в интервале [0,n], В(х)=1, если х Используемая литература:
Garrick St., London WC2, UK.
