M.Santha, U.V.Vazirani. Generating Quasi-random Sequences from
Semi-random Sources// Journal of Computer and System Sciences,
vol.33, Э1, 1986, pp.75-87.
Аннотация. В статье
рассматривается математическая проблема генерации случайных
битовых последовательностей при помощи физических источников шума
(типа диодов Зенера). Предложена общая математическая модель
таких источников - полуслучайный источник, и показано, как
преобразовать выход таких источников в квазислучайные
последовательности. Эти последовательности в сильном смысле не
отличаются от действительно случайных. Это позволяет доказать,
что квазислучайные последовательности могут использоваться вместо
действительно случайных в качестве начальных заполнений ДСЧ, в
алгоритмах рандомизации и стохастическом моделировании. 1.
Введение В ряде случаев требуется источник "случайных битовых
последовательностей": например, в алгоритмах рандомизации (широко
известны тесты проверки на простое число [10,13]), в
стохастическом моделировании [1,6], оптимизационных задачах [7],
криптографии [3] и др. [8]. В идеальном случае желательно иметь
последовательности несмещгнных и независимых битов. К сожалению,
имеющиеся физические источники случайности, включая диоды Зенера
и счгтчики Гейгера, несовершенны [9]. Их выходные биты не только
смещены, но и коррелированы. В статье предложен математический
подход к генерации случайных битовых последовательностей при
помощи несовершенных физических источников шума. Предлагается
очень общая математическая модель физического источника и
алгоритм преобразования выхода таких источников в битовые
последовательности, которые вполне могут использоваться в
указанных случаях. В нашей модели выходные значения получаем,
бросая монету, смещение которой (вероятность появления "1")
переменно. Смещение следующего выходного значения выбирается
противником, имеющим неограниченную вычислительную мощь и
полностью знающим ранее сгенерированную последовательность. Для
того, чтобы источник всг же обладал некоторой случайностью,
противник может выбирать смещение больше и меньше 1- для
некоторого положительной величины 0< <1. Эта модель справедлива
для таких источников случайности, как диоды Зенера, у которых
частота появления нулей и единиц "плавает" на временном
интервале. Назовгм такой источник, рассматриваемый с точки зрения
противника, полуслучайным. (Примечание. В первом варианте статьи
[17] использовался термин "слабослучайный"). Простейшим примером
несовершенного источника случайности является монета с
неизвестным, но фиксированным смещением. Фон Нейман (von Neumann,
[9]) предложил очень простой алгоритм в реальном масштабе времени
для получения несмещгнных бросков при помощи "смещгнной" монеты.
Блюм (Blum, [1]) обобщил эту модель для детерминированного
марковского процесса с конечным числом состояний, для которого
задана таблица переходов, но переходные вероятности неизвестны.
Такой марковский процесс можно рассматривать как бросание монеты,
смещение которой зависит от состояния процесса; следовательно,
выходные биты будут коррелированы. Блюм показал, что явное
обобщение процедуры фон Неймана недопустимо, но при изменении
порядка следования выходных битов можно добиться их независимости
и несмещгнности. Модель, представленная в статье, не предполагает
рассмотрения природы источника (в этом качестве рассматривается
злонамеренный противник); единственное требование - это наличие
небольшой неопределгнности относительно каждого выходного бита.
Характер нашей модели ("взгляд со стороны противника") лежит в
основе отличия нашего подхода от теории информации. Теорема
кодирования Шеннона в общих чертах гласит: от любого источника
можно получить столь много независмых и несмещгнных бит, сколь
велика его энтропия (наилучший случай). Напротив, мы докажем, что
не существует алгоритма, при помощи которого можно получить хотя
бы один несмещгнный бит от полуслучайного источника (фактически,
не лучше, чем (1- )-смещгнный бит). Это вытекает из следующего
отличия: слабослучайный источник с параметром определяет
некоторый большой класс распределений; выходное распределение
источника выбирается противником из этого класса. Тогда как
теорема Шеннона гласит, что для любого распределения существует
хороший алгоритм для получения несмещгнных, нгезависимых битов,
мы покажем, что не существует такого алгоритма, одинаково
приемлемого для каждого полуслучайного распределения с параметром
. Мы покажем, как получить квазислучайные последовательности
(КСП) из выходных данных независимых полуслучайных источников.
Эти КСП могут и не быть истинно независимыми и несмещгнными, но
они не отличимы от действительно случайных последовательностей в
очень строгом смысле (даже сильнее, чем у Яо (Yao, [16])).
Следствием этой неотличимости является возможность замены
действительно случайных последовательностей КСП в ряде
практических задач. Например, мы докажем, что КСП можно
использовать вместо истинно случайных бросков монеты для
генерации СЧ в стохастическом моделировании. Мы покажем, как
получить n-битные КСП от w(log n) независимых полуслучайных
источников (ПСИ): алгоритм эффективен, не требует памяти, удобен
для аппаратной реализации. Модель ПСИ была вызвана ег идейной
простотой. Необходимо ли рассматривать модель наихудшего случая
для физического источника шума? Наше основное допущение состоит в
том, что точный характер корреляций на выходе источника зависит
от деталей физической природы источника; эти детали не только
тяжело определить, но они непостоянны во времени, зависят от
условий работы (температура, влажность). Таким образом, создание
шумового диода с малой корреляцией на выходе затруднено, а
наиболее эффективный метод - это делать выборку выходных значений
диода на малой скорости. Из этой статьи последует вывод о
возможности совершенно другого подхода: выборка выходных значений
диода производится с большой частотой, получаем коррелированные,
но полуслучайные биты. Затем получаем КСП из выходов нескольких
независимых шумовых диодов: реализация дгшева, и для получения
n-битной КСП требуются w((1/ )n) полуслучайных битов. Возникает
инженерная задача по обеспечению независимости w((1/ )log n)
шумовых диодов. Таким образом, получаем двойной выигрыш:
во-первых, относительный выигрыш в скорости благодаря увеличению
скорости выборки; во-вторых, электромагнитная изоляция шумовых
диодов (для обеспечения независимости) - вполне исследованная
проблема. И наконец, давайте сравним подходы к генерации
случайных битовых последовательностей: выборку из физического
шума и псевдослучайную генерацию на основе детерминированных
методов [8]. Псевдослучайный подход имеет то преимущество, что не
требуется разработки специальных схем и допускается многократное
использование для отладки программ. Однако проблема в том, что не
доказаны статистические свойства последовательностей (особенно в
сложных задачах). Наконец, случайные последовательности можно
получить на (относительно) больших скоростях при выборке из
физических источников (см., например, [9]). Новаторские работы
Шамира, Блюма-Микали, Яо [12,2,16] привели к теории совершенных
датчиков псевдослучайных чисел с доказательно хорошими
статистическими свойствами на основе факта существования
односторонних функций. Блюм [1] показал, что необходимо тщательно
выбирать случайный вектор инициализации (начальное заполнение)
для таких датчиков, так как ДСЧ может усиливать зависимость или
смещение в битах начального заполнения. Мы докажем, что КСП могут
быть использованы в качестве начального заполнения совершенных
датчиков псевдослучайных чисел без ослабления криптографической
стойкости датчика. 2. Квазислучайность Мы имеем источник, который
для любой длины n генерирует n-последовательности x {0,1} с
некоторой вероятностью p (x). Определение 1. Источник является
квазислучайным датчиком, если для любого t>0 и для достаточно
больших n: Определение квазислучайного датчика первоначально было
основано на идее вероятностного полиномиального статистического
теста и совершенного датчика псевдослучайных чисел (ДПСЧ),
предложенного Яо [16]. Ниже приводится равнозначное определение
квазислучайного датчика, которое более соответствует определениям
Яо и позволяет сравнить два понятия - квазислучайность и
псевдослучайность. Определение. Функциональный статистический
тест (ФСТ) - это любая функция f: {0,1}* Ж [0,1], где [0,1] -
единичный интервал. Пусть (n)= 1/2 f(x) - среднее значение f на
случайных n-последовательностях. Пусть (n)= 1/2 p (x)f(x) -
среднее значение f на nпоследовательностях, генерируемых
источником. Определение 2. Источник является квазислучайным
датчиком, если для любого t>0 и для достаточно больших n для
любого ФСТ f: Теорема 1. Оба определения квазислучайного датчика
эквивалентны. Доказательство. Рассмотрим источник,
удовлетворяющий определению 1, и пусть f будет функциональным
статистическим тестом. Тогда для всех t и всех достаточно больших
n | (n) - (n)|= (1/2 - p (x))f(x) <= <= |1/2 - p (x)| <= 1/n.
Следовательно, источник также является квазислучайным датчиком в
соответствии с определением 2. Для доказательства обратного пусть
1 если 1/2 > Pn(х) g(x()= 0 в противном случае Пусть h(x)=1-g(x).
Тогда p (x) - 1/2 = | (n) - (n)| + (n) - (n) = O(1/n ) + O(1/n )
= O(1/n ) для всех t>0. **** Давайте вспомним, что ДПСЧ - это
вычислимая за полиномиальное время функция G: {0,1}* Ж {0,1}*
такая, что для некоторого полинома poly(n) при начальных
заполненях длины n функция G генерирует последовательности длины
poly(n). Определение [Яо]. Вероятностный статистический тест
полиномиального времени (СТПВ) является функцией Т: {0,1}* Ж
{0,1}, которая вычисляется при помощи вероятностной машины
Тюринга полиномиального времени. ДПСЧ проходит этот тест Т, если
для любого t>0 и достаточно больших n | (poly(n) - (n)| <= 1/n .
ДПСЧ является совершенным, если он проходит все СТПВ. Очевидное
различие между статистическими тестами Яо и нашими ФСТ в том, что
функция f не обязательно должна быть вычислимой; от нее вовсе не
требуется вычислимость. Более фундаментальное различие вытекает
из того факта, что СТПВ - понятие теории сложности, а ФСТ -
понятие теории информации. По этой причине определение Яо для
совершенного ДПСЧ не является общим в следующем смысле: ДПСЧ
совершенен, если для любого t>0 и любого СТПВ имеется начальное
заполнение длины n, удовлетворяющее определению. В общем плане,
значение n зависит от статистического теста, и не существует
конечного значения n, удовлетворяющего определению по отношению
ко всем статистическим тестам. С другой стороны, квазислучайность
- это общая концепция: для любого t>0 длина n может быть выбрана
так, что КСП длины n будут удовлетворять определению для каждого
ФСТ. Очевидным следствием второго определения квазислучайного
датчика является то, что совершенный ДПСЧ остагтся совершенным,
если начальные заполнения генерируются при помощи квазислучайных
источников. Последующая теорема также покажет, как сильные
свойства квазислучайных датчиков позволяют заменить истинно
случайные последовательности. Мы покажем, что КСП могут
использоваться вместо последовательностей бросков монеты любой
процедурой, которая генерирует случайные величины желаемого
распределения из последовательностей этих бросков. Пусть f:
{0,1}* Ж Z, множество целых чисел. При заданном распределении
вероятности Pr на {0,1} f приводит к распределению вероятности на
Z: p (y)= Pr(x). Пусть - желаемое распределение. В качестве меры
близости, с которой апроксимируется распределением, обусловленным
f, выберем Предполагаем, что служит мерой области между графиками
плотности двух распределений. Теорема 2. Пусть f будет любой
функцией, описанной выше; пусть p - плотность вероятности,
обусловленная f, когда все последовательности длины n выбираются
с одинаковой вероятностью, и пусть q - плотность вероятности,
обусловленная f, когда последовательности длины n генерируются
квазислучайным датчиком. Пусть Тогда для любого t и достаточно
больших n. Комментарий. Эта теорема может использована для
определения эффективных границ: задавая границу, можно вычислить
n такое, что ошибка (область между графиками плотности), вводимая
при замене истинно случайных последовательностей квазислучайными,
будет меньше этой границы. Это значение n приемлемо независимо от
алгоритма генерации случайных переменных по свойству однообразия.
Тот факт, что ФСТ в определении квазислучайности могут не быть
СТПВ, очень важен в этой теореме, так как не проводилось анализа
времени выполнения алгоритмов выработки распределений, которое
может быть суперполиномиальным. Доказательство. Пусть 1, если p
(f(x)) > q (f(x)) h(x)= 0 в противном случае. Пусть g(x)=1-h(x).
Тогда |p (y) - q (y)|= = (p (y) - q (y)) + (q (y) - p (y)) = |
(n) - (n)| + | (n) - (n)| = O(1/n ) + O(1/n ) = O(1/n ) для
каждого t>0. Окончательно имеем | - |= | (y) - p (y)| - |
(y) - q (y)| <= || (y) - p (y)| - | (y) - q (y)|| <= |p (y) - q
(y)| = O(1/n ) для каждого t>0. **** 3. Получение квазислучайных
последовательностей при помощи полуслучайных источников Дадим
точное определение слабослучайного источника. Определение.
Распределение вероятности на {0, 1} является слабослучайным, если
существует констата , 0< <= 1/2, такая, что для любого i и любой
последовательности s длины i-1 <= Pr[ x =1 | x ...x =s] <= 1- .
Полуслучайным называется источник, чьг распределение вероятности
выходных значений полуслучайное. Удобно рассматривать ПСИ как
процесс, управляемый противником, который генерирует
последовательность нулей и единиц, бросая монету с переменным
смещением. Смещение следующего броска монеты зависит от исхода
предыдущих бросков. Функцию, описывающую эту зависимость, назовгм
стратегией противника. Более строго: Определение. Стратегия
противника - это отображение S: {0,1}* - [ , 1- ], где S(x)=
Pr[следующий бит равен 1| предыдущие выходные значения - это
последовательность x]. Следующая лемма показывает, как получить
единственный "хороший" бит из выхода w(log n) независимых
слабослучайных источников. Лемма 3. Пусть x , x ,.., x будут
битами на выходах соответственно m независимых ПСИ. Тогда
|Pr[проверка на чгтность(x , x ,.., x )=1] - Pr[проверка на
чгтность(x , x ,.., x )=0]| <= (1-2 ) . Доказательство. По
индукции относительно m. Пусть r = Pr[проверка на четность(х , x
,..., x )=1], и s = Pr[проверка на четность(х , x ,..., x )=0]=
1-r . Пусть p = Pr[ x =1], q = 1-p. Тогда <=p, q <= 1- .
Поскольку источники независимы r = r q + s p. s = s q + r p.
Следовательно, |r - s | = |(r - s )(p-q)| <=(1-2 ) (1-2 )) = (1-2
) . **** Лемма 3 показывает, как использовать независимость двух
источников для получения "хорошего" бита: специально возьмгм
m=О((1/ )log n); тогда контрольный бит проверки на чгтность имеет
смещение [1/2 - 1/n , 1/2 + 1/n ]. Пока мы использовали по одному
биту от независимых источников. Далее мы покажем, что генерация
этих хороших битов - ключ к созданию помех противникам.
Рассмотрим следующий "хороший" источник: последовательности длины
n генерируются монетой Cn, чьг смещение можно немного изменять
после каждого броска; на смещение накладывается ограничение: оно
должно быть больше, чем 1/2 - (n), и меньше, чем 1/2 + (n). Перед
каждым броском монеты противник, которому известна история
бросков монеты, устанавливает смещение монеты. Цель противника -
создать наибольшую зависимость в распределении
последовательностей бросков. Мы хотели бы показать, что если (n)
является достаточно малой функцией от n, то источник является
квазислучайным. Теорема 4. Если для каждого t и для всех
достаточно больших n (n) < 1/n , то источник определгнный выше,
является квазислучайным. Доказательство. Пусть для любой
последовательности х=s ...s длины n и для каждого i, 1<=i<=n,
Pr(s |s ...s ) означает условную вероятность того, что i-ый исход
броска монеты равен s , причем результатом первых i-1 бросков
является s ...s . Тогда вероятность того, что источник выработает
х равна p (x) = Pr( s |s ...s ) x...x Pr(s |s ) x Pr(s ).
Поскольку каждый последующий бит вырабатывается при помощи броска
монеты, чье смещение лежит в пределах 1/2- (n) и 1/2+ (n): (1/2 -
(n)) <= p (x) <= (1/2+ (n)) . Таким образом, 1/2 - p (x) <= 2
((1/2 + (n)) - 1/2 ) = (1 + 2 (n)) - 1. И в результате простого
вычисления: (1+ 2 (n)) - 1 = 2n (n) + o(n (n)) = O(1/n ) для
каждого t>0. **** Простая реализация хорошего источника такова:
для входного значения длины n пусть x x ...x ;x x ...x ;x x ...x
будут n-битными выходами k=w((1/ ) log n) независимых ПСИ.
Выходом является y , y ...y , где y =проверка на чгтность(x ,x
... x ). Теорема 5. Определгнный выше источник является
квазислучайным. Доказательство: по лемме 3 этот источник является
хорошим и, следовательно, по теореме 4 является
квазислучайным.************* Описанный выше метод извлекает 1 бит
из каждых w((1/ ) log n) полуслучайных битов. Далее мы покажем,
как увеличить эту скорость, используя метод Вайнера [15]. Вайнер
изучил проблему передачи в совершенной секретности в присутствии
подслушивателя, имеющего канал перехвата с помехами; каждый
передаваемый бит подслушиватель "видит" правильно с вероятностью
1- и ошибочно с вероятностью , 0< <1/2. Вайнер показал, как
достичь секретности, если даже противнику известен способ
кодирования. Следующий простой метод использует функцию чгтности
для достижения секретности, но не обеспечивает хорошей скорости
передачи: закодируем каждый бит сообщения m как k-битное слово с
с ...с , выбранное равновероятно среди последовательностей длины
k таких, что проверка на чгтность (с с ..с )=m. Ясно, что легко
восстановить m из с с ..с . Однако подслушиватель видит
последовательность е е ..е , где е =с с вероятностью 1- и е = с с
вероятностью . Нетрудно увидеть, что Н(m|е е ..е )= h(1/2 -
1/2(1-2 ) ), которая стремится к 1 при к, стремящемся к
бесконечности. Проведгм аналогию между проблемой канала перехвата
и квазислучайной генерацией при помощи независимых ПСИ:
подслушиватель соответствует противнику, а канал с помехами
соответствует -случайности выхода каждого из k независимых
источников. Наконец, использование функции чгтности для
достижения большой энтропии по отношению к последовательности
противника е е ..е соответствует извлечению "хорошего" бита
независимо от стратегии противников. Вайнер покзывает, как
достичь оптимальной скорости передачи, используя коды с проверкой
на чгтность. Мы покажем, как использовать тот же метод для
получения КСП на более высоких скоростях. Главная идея состоит в
повторном использовании полуслучайных битов, Пусть х , x ,..., x
будут k слабослучайными битами, полученными от независимых
источников. Давайте получим биты r , r ,.., r следующим образом:
каждый r - это проверка на чгтность некоторого подмножества x , x
... x . Для обеспечения несмещгнности r подмножества должны быть
большими, а для уменьшния корреляций - "хорошо разнесгнными". Это
в точности достигается в строках l х k порождающей матрицы кода
проверки на чгтность (строки - это 0/1вектора размерности k, по
сути - подмножества), которая обнаруживает k ошибок при некоторой
константе >0 [4, гл.6]. Точная структура таких асимптотически
эффективных кодов приводится в [5]; для реальных значений k более
полезен код БЧХ, хотя он не всегда асимптотически эффективен.
Следующий алгоритм объединяет эти идеи: proc qgen(n): Пусть G
будет log n х k - порождающая матрица кода проверки на чгтность,
обнаруживающая k ошибок, где k=о((1/ )log n). Пусть x x ..x , x x
..x , x x ..x - это m-битные выходы от k=о((1/ )log n)
независимых слабослучайных источников, где m=n/log n. Пусть u = x
...x , u = x ...x , u = x ...x . Выход G u , G u , G u . end;
Теорема 6. Определгнный выше источник является квазислучайным. Он
преобразует о((1/ )n) слабослучайных битов в n-битную
квазислучайную последовательность. Доказательство. Мы покажем,
что определенный выше источник является "высококачественным" 9.
J. von Neumann. Various techniques used in connection with random
digits (notes by G.E.Forsythe). Applied Math. Series, vol.12,
p.36-38, 1951, NBS, Washington, D.C., reprinted in "Collected
Works", vol.5, p.768-770, Pergamon, N-Y, 1963. 10. M.O.Rabin.
Probabilistic algorithms in primality testing// J. Number Theory,
12, 1980, 128-138. 11. Schmeiser B. Random variate generation: A
Survey. 1980 IEEE "Simulation with Discrete Models:
A-state-of-the-art view", (T.Oren, C.Shub, P.Roth, Eds). 12.
Shamir A. On the generation of cryptographically strong
pseudo-random sequences//ACM Tr. on Computer Systems, v.1, 1983,
p.38-44. 13. Solovay R., Strassen V. A Fast Monte-Carlo test for
primality //SIAM J. Comp., v.6, 1977, 64-85. 14. Vazirani U.V,
Vazirani V.V. Trapdoor pseudo-random number generators with
applications to protocol design//In "15th Annu. ACM Sympos.
Theory of Comput.", 1983. 15. Wyner A. The Wire-Tap Channel. 16.
Yao A. Theory and applications of trapdoor functions//In 23rd
IEEE Sympos. Found. of Comput. Sci., 1982. 17. M.Santha,
U.V.Vazirani. Generating Quasi-random Sequences from
Slightly-random Sources//In "25th Annu. ACM Sympos. Theory of
Comput.", 1984.
