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

Экстрактор случайности , часто называемый просто «экстрактор», представляет собой функцию, которая применяется к выводу из источника слабой энтропии вместе с коротким, равномерно случайным начальным числом, генерирует высокослучайный результат , который выглядит независимым от источника и равномерно распределенным. . Примеры слабослучайных источников включают радиоактивный распад или тепловой шум ; Единственное ограничение на возможные источники заключается в том, что их невозможно полностью контролировать, рассчитывать или предсказывать, и что можно установить нижнюю границу уровня их энтропии. Для данного источника экстрактор случайных чисел можно даже считать настоящим генератором случайных чисел ( TRNG ); но не существует ни одного экстрактора, который, как было бы доказано, производит действительно случайный результат из любого типа слабослучайного источника.

Иногда термин «смещение» используется для обозначения отклонения слабослучайного источника от однородности, а в более старой литературе некоторые экстракторы называются несмещенными алгоритмами . поскольку они берут случайность из так называемого «предвзятого» источника и выдают распределение, которое выглядит несмещенным. Слабо случайный источник всегда будет длиннее, чем выход экстрактора, но эффективный экстрактор — это тот, который максимально снижает это соотношение длин, одновременно сохраняя низкую длину начального числа. Интуитивно это означает, что из источника «извлечено» как можно больше случайности.

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

Формальное определение экстракторов

Минимальная энтропия распределения $X$ (обозначается $H_{\infty }(X)$), является наибольшим действительным числом $k$ такой, что $\Pr[X=x]\leq 2^{-k}$ для каждого $x$ в диапазоне $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$, выходное распределение ${\text{Ext}}$ -близок ε к $U_{m}$.

В приведенном выше определении ε -близость относится к статистическому расстоянию .

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

Мощные экстракторы

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

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

${\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}$ обозначаем одну и ту же случайную величину) $\epsilon$-близкое к равномерному распределению по $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 представляет собой a ( 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). Криптография, устойчивая к воздействию, учитывает тот факт, что трудно сохранить в тайне первоначальный обмен данными, который часто происходит во время инициализации приложения шифрования , например, отправитель зашифрованной информации должен предоставить получателям необходимую информацию. для расшифровки.

В следующих параграфах определяются и устанавливаются важные отношения между двумя видами ERF — k -ERF и k -APRF , которые полезны в криптографии, устойчивой к воздействию.

Определение ( k -ERF): Адаптивная k-ERF — это функция $f$ где для случайного ввода $r$ , когда вычислительно неограниченный противник $A$ может адаптивно читать все $r$ за исключением $k$ биты, $|\Pr\{A^{r}(f(r))=1\}-\Pr\{A^{r}(R)=1\}|\leq \epsilon (n)$ для какой-то незначительной функции $\epsilon (n)$ (определено ниже).

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

Определение (k-APRF): A $k=k(n)$ APRF — это функция $f$ где при любой настройке $n-k$ биты ввода $r$ к любым фиксированным значениям, вектор вероятности $p$ продукции $f(r)$ над случайным выбором для $k$ оставшиеся биты удовлетворяют $|p_{i}-2^{-m}|<2^{-m}\epsilon (n)$ для всех $i$ и для какой-то незначительной функции $\epsilon (n)$.

Камп и Цукерман доказали теорему, утверждающую, что если функция $f$ является k -APRF, то $f$ также является k -ERF. Более конкретно, любой экстрактор, имеющий достаточно малую ошибку и принимающий в качестве входных данных не обращающий внимания источник с фиксацией битов, также является APRF и, следовательно, также k -ERF. Более конкретный экстрактор выражен в этой лемме:

Лемма: Любая $2^{-m}\epsilon (n)$-экстрактор $f:\{0,1\}^{n}\rightarrow \{0,1\}^{m}$ для набора $(n,k)$ забывчивые источники бит-фиксации, где $\epsilon (n)$ пренебрежимо мал, также является k-APRF.

Эту лемму доказали Камп и Цукерман. Лемма доказывается путем исследования расстояния от равномерности выпуска, которое в $2^{-m}\epsilon (n)$-экстрактор, очевидно, самое большее $2^{-m}\epsilon (n)$, что удовлетворяет условию APRF.

Лемма приводит к следующей теореме, утверждающей, что на самом деле существует k описанная функция -APRF:

Теорема (существования): Для любой положительной константы $\gamma \leq {\frac {1}{2}}$, существует явный k-APRF $f:\{0,1\}^{n}\rightarrow \{0,1\}^{m}$, вычислимое за линейное число арифметических операций над $m$-битовые строки, с $m=\Omega (n^{2\gamma })$ и $k=n^{{\frac {1}{2}}+\gamma }$.

Определение (пренебрежимо малой функции): Для доказательства этой теоремы нам понадобится определение пренебрежимо малой функции . Функция $\epsilon (n)$ определяется как пренебрежимо малый, если $\epsilon (n)=O\left({\frac {1}{n^{c}}}\right)$ для всех констант $c$.

Доказательство: Рассмотрим следующее $\epsilon$-extractor: функция $f$ представляет собой экстрактор множества $(n,\delta n)$ не обращающий внимания источник бит-фиксации: $f:\{0,1\}^{n}\rightarrow \{0,1\}^{m}$. $f$ имеет $m=\Omega (\delta ^{2}n)$, $\epsilon =2^{-cm}$ и $c>1$.

Доказательство существования этого экстрактора с $\delta \leq 1$, а также то, что оно вычислимо за линейное время вычислений на длине $m$ можно найти в статье Джесси Кампа и Дэвида Цукермана (стр. 1240).

То, что этот экстрактор удовлетворяет критериям леммы, тривиально верно, поскольку $\epsilon =2^{-cm}$ является ничтожной функцией.

Размер $m$ является:

$m=\Omega (\delta ^{2}n)=\Omega (n)\geq \Omega (n^{2\gamma })$

Поскольку мы знаем $\delta \leq 1$ тогда нижняя граница $m$ преобладает $n$. На последнем шаге мы используем тот факт, что $\gamma \leq {\frac {1}{2}}$ это означает, что сила $n$ самое большее $1$. И поскольку $n$ является положительным целым числом, мы знаем, что $n^{2\gamma }$ самое большее $n$.

Стоимость $k$ рассчитывается с использованием определения экстрактора, где мы знаем:

$(n,k)=(n,\delta n)\Rightarrow k=\delta n$

и используя значение $m$ у нас есть:

$m=\delta ^{2}n=n^{2\gamma }$

Используя это значение $m$ мы учитываем худший случай, когда $k$ находится на его нижней границе. Теперь путем алгебраических вычислений получаем:

$\delta ^{2}n=n^{2\gamma }$

$\Rightarrow \delta ^{2}=n^{2\gamma -1}$

$\Rightarrow \delta =n^{\gamma -{\frac {1}{2}}}$

Что вставлено в значение $k$ дает

$k=\delta n=n^{\gamma -{\frac {1}{2}}}n=n^{\gamma +{\frac {1}{2}}}$,

что доказывает, что существует явный экстрактор k-APRF с заданными свойствами. $\Box$

Примеры

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

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

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

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

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

Машина хаоса

Другой подход — использовать выходные данные машины хаоса, примененные к входному потоку. Этот подход обычно опирается на свойства хаотических систем . Входные биты передаются в машину, изменяя орбиты и траектории в нескольких динамических системах. Таким образом, небольшие различия во входных данных приводят к очень разным результатам. Такая машина имеет равномерный выходной сигнал, даже если распределение входных битов неравномерно или имеет серьезные недостатки, и поэтому может использовать источники слабой энтропии . Кроме того, эта схема позволяет повысить сложность, качество и безопасность выходного потока, контролируемые путем указания трех параметров: затрат времени , требуемой памяти и секретного ключа .

Обратите внимание: хотя истинные хаотические системы математически обоснованы для «усиления» энтропии, это основано на наличии действительных чисел с бесконечной точностью. при реализации в цифровых компьютерах с представлением чисел с конечной точностью, как в машинах хаоса, использующих IEEE 754 Floating-Point , периодичность далеко не соответствует полному пространству для заданной длины бита. Было показано, что

Криптографическая хэш-функция

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

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

Приложения

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

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

Извлечение случайности также используется в некоторых разделах теории сложности вычислений и при построении кодов, декодируемых списком, исправляющих ошибки .

См. также

• Декорреляция
• Аппаратный генератор случайных чисел
• Случайное слияние
• Нечеткий экстрактор

Ссылки

• Экстракторы случайности для независимых источников и приложений , Ануп Рао
• Последние разработки в области явных конструкций экстракторов , Ронен Шальтиэль.
• Извлечение случайности и получение ключей с использованием режимов CBC, Cascade и HMAC , Евгений Додис и др.
• Вывод ключей и извлечение случайных данных , Оливье Чевассут и др.
• Детерминированные экстракторы для источников с фиксацией битов и устойчивой к внешним воздействиям криптографии , Джесси Камп и Дэвид Цукерман
• Подбрасывание предвзятой монеты (и оптимальность продвинутой многоуровневой стратегии) ​​(конспект лекций) , Михаэль Митценмахер