Экстрактор случайности

Экстрактор случайности — функция, которая применяется к выходу из слабо случайного источника энтропии, вместе с коротким равномерно распределённым случайным начальным значением (англ. seed) и генерирует случайный выход, который выглядит независимым от источника и равномерно распределён.

Несмотря на то, что экстрактор имеет некоторые концептуальные сходства с генератором псевдослучайных чисел, это различные понятия. Оба алгоритма принимают в качестве входных данных небольшое равномерно случайное начальное число и выдают более длинное случайное, которое «выглядит» равномерно случайным. Некоторые псевдослучайные генераторы также являются экстракторами. (Когда генератор псевдослучайных чисел основан на существовании трудных битов, можно считать слабо случайный источник набором таблиц истинности таких предикатов и доказать, что выходные данные статистически близки к однородным). Хотя в формальном определении псевдослучайного генератора не указывается, что должен использоваться слабо случайный источник, и в случае экстрактора выходные данные должны быть статистически близки к однородным, в ГПЧ требуется только то, чтоб они были вычислительном отношении неотличимы от равномерных, что является более слабым требованием.

Описание

В более ранней литературе некоторые экстракторы называются алгоритмами обратного смещения (англ. unbiasing algorithms), поскольку они берут случайность из источника со смещённым распределением (иногда термин «смещение» используется для обозначения отклонения слабо случайного источника от однородности) и выводят распределение, которое становится не смещённым. Значения слабо случайного источника всегда будут больше, чем выход экстрактора, но эффективный экстрактор — это тот, который максимально снижает это отношение значений, одновременно сохраняя маленькое начальное значение. Другими словами это означает, что из источника было извлечено как можно больше случайностей.

Примерами слабо случайных источников могут быть радиоактивный распад или тепловой шум. Единственное ограничение на возможные источники состоит в том, что не должно быть никакого способа, которым они могут полностью контролироваться, рассчитываться или предсказываться, таким образом, чтобы могла быть установлена ​​нижняя граница для их уровня энтропии. Для данного источника экстрактор случайности может даже считаться истинным генератором случайных чисел, однако не существует единого экстрактора, который доказано производил бы действительно случайный выход из любого типа слабо случайного источника.

В специальной публикация NIST 800-90B рекомендуется несколько экстракторов, включая семейство хэшей SHA и говорится о том, что, если количество входных бит от источника энтропии в два раза превышает количество битов на выходе, этот выход можно считать практически полностью случайным.

Формальное определение

Мин-энтропия распределения $X$ (обозначается как $H_{\infty }(X)$) является наибольшим вещественным числом $k$ таким, что $\Pr[X=x]\leq 2^{-k}$ для любого $x$ из $X$. По сути, это означает то, какова вероятность, что $X$ примет его наиболее вероятное значение, при наихудшем распределении. Обозначим $U_{\ell }$ как равномерное распределение на $\{0,1\}^{\ell }$, или $H_{\infty }(U_{\ell })=\ell$.

Для n-битного распределения $X$ с мин-энтропией k говорят, что $X$ является $(n,k)$ распределением.

Определение (Экстрактор): (k, ε) — экстрактор

Пусть ${\text{Ext}}:\{0,1\}^{n}\times \{0,1\}^{d}\to \{0,1\}^{m}$ — функция, которая принимает на вход выборку из $(n,k)$ распределения $X$, d-битное начальное значение из $U_{d}$ и возвращает m-битную строку. ${\text{Ext}}$ будет являться (k , ε) -экстрактором , если для всех $(n,k)$ распределений $X$ выходное распределение не дальше от $U_{m}$, чем на ε.

В приведённом выше определении подразумевается статистическое расстояние.

Таким образом, экстрактор берёт слабо случайный n-битный вход, короткий равномерно случайный начальный размер и выдаёт m-битный выход, который выглядит равномерно случайным. Цель состоит в том, чтобы сделать маленький d (то есть использовать как можно меньше равномерной случайности) и как можно больше m насколько это возможно (то есть чтобы получить как можно больше близких к случайным битам выходных данных).

Сильные экстракторы

Экстрактор является сильным, если конкатенация начального значения с выходом экстрактора приводит к распределению, которое все ещё близко к равномерному.

Определение (Сильный экстрактор): (k, ε) — экстрактор: A $(k,\epsilon )$ — сильный экстрактор, это функция

${\text{Ext}}:\{0,1\}^{n}\times \{0,1\}^{d}\rightarrow \{0,1\}^{m}\,$

такая, что для каждого $(n,k)$ распределения $X$ распределение $U_{d}\circ {\text{Ext}}(X,U_{d})$ (две $U_{d}$ означают одну и ту же случайную величину) дальше от равномерного распределения не более чем на ε по $U_{m+d}$.

Явные экстракторы

Используя вероятностный метод, можно показать, что существует (k , ε)-экстрактор, то есть что построение возможно. Однако обычно недостаточно просто показать, что экстрактор существует. Необходима явная конструкция, которая выглядит следующим образом:

Определение (явный экстрактор): для функций k (n), ε (n), d (n), m (n) семейство Ext = {Ext _n } функций

${\text{Ext}}_{n}:\{0,1\}^{n}\times \{0,1\}^{d(n)}\rightarrow \{0,1\}^{m(n)}$

является явным (k, ε)-экстрактором, если Ext(x, y) может быть вычислено за полиномиальное время (по длине его входа) и для каждого n, Ext_n является (k(n), ε(n))-экстрактором .

Вероятностным методом можно показать, что существует (k, ε)-экстрактор с начальным значением

$d=\log {(n-k)}+2\log \left({\frac {1}{\varepsilon }}\right)+O(1)$

и длиной входа

$m=k+d-2\log \left({\frac {1}{\varepsilon }}\right)-O(1)$.

Дисперсер

Вариантом экстрактора случайности с более слабыми свойствами является дисперсер .

Экстракторы случайностей в криптографии

Одним из наиболее важных аспектов криптографии является генерация случайных ключей. Часто необходимо генерировать секретные случайные ключи из полусекретных источников, которые могут быть в некоторой степени скомпрометированы. Принимая единственный короткий (и секретный) случайный ключ в качестве источника, экстрактор можно использовать для генерации более длинного псевдослучайного ключа, который затем можно использовать для шифрования с открытым ключом. В частности, когда используется сильный экстрактор, его вывод будет выглядеть равномерно случайным даже для того, кто видит часть (но не весь) источника. Например, если источник известен, но начальное число неизвестно (или наоборот). Это свойство экстракторов особенно полезно в так называемой криптографии, устойчивой к воздействию, в которой требуемый экстрактор используется в качестве функции, устойчивой к воздействию (ERF). Устойчивая к воздействию криптография учитывает тот факт, что трудно сохранить в тайне первоначальный обмен данными, который часто происходит во время инициализации шифрования, например, отправитель зашифрованной информации должен предоставить получателям необходимую информацию для расшифровки.

Примеры

Экстрактор фон Неймана

Дополнительная информация: последовательность Бернулли

Один из ранних примеров экстракторов случайности был предложен Джоном фон Нейманом. Принцип его работы заключался в следующем: из входного потока он берёт пары последовательных (не перекрывающихся) битов. Если два бита совпадают, выходные данные не генерируются. Если биты различаются, выводится значение первого бита. Может быть показано, что экстрактор фон Неймана производит равномерный выходной сигнал, даже в том случае, когда распределение входных битов не является равномерным, если каждый бит имеет одинаковую вероятность того, что он равен единице, и нет корреляции между последовательными битами.

Таким образом, он принимает в качестве входных данных последовательность Бернулли с p, необязательно равным 1/2, и выводит последовательность Бернулли с $p=1/2.$ В более общем смысле, это применимо к любой заменяемой последовательности — оно основано только на том факте, что для любой пары одинаково вероятны 01 и 10: для независимых испытаний они имеют вероятности $p\cdot (1-p)=(1-p)\cdot p$ в то время как для заменяемой последовательности вероятность может быть более сложной, но обе одинаково вероятны.

Приложения

Экстракторы случайных чисел широко используются в криптографических приложениях, где криптографическая хеш-функция применяется к высокоэнтропийному, но не равномерно распределенному источнику, такому как информация о синхронизации дисковода или задержки клавиатуры, для получения равномерно случайного результата.

Экстракторы случайности сыграли свою роль в последних разработках в области квантовой криптографии, где фотоны используются экстрактором случайности для генерации безопасных случайных битов.

Экстракторы случайности также используется в некоторых разделах теории вычислительной сложности.