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

Концепция физики

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

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

Многие аппаратные генераторы случайных чисел имеют один или несколько «источников шума», генерирующих цветной шум . Процесс объединения их вместе и извлечения несмещенных некоррелированных случайных битов (похожий на белый шум ) часто называют программным отбеливанием . ^{[3] [4] [5] [6]}

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

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

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

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

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

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

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

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

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

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

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

Определение (сильный экстрактор): -сильный экстрактор — это функция. ${\displaystyle (k,\epsilon )}$

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

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

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

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

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

${\displaystyle {\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 ,  ε )-экстрактор с длиной затравки

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

и длина вывода

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

Диспергаторы

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Размер : ${\displaystyle m}$

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

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

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

${\displaystyle (n,k)=(n,\delta n)\Rightarrow k=\delta n}$

и используя значение мы имеем: ${\displaystyle m}$

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

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

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

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

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

Что вставлено в значение дает ${\displaystyle k}$

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

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

Примеры

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

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

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

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

Машина хаоса

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

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

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

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

Приложения

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

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

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

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

Смотрите также

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

Рекомендации

1. Извлечение случайности из выборочных распределений. Портал.acm.org. 12 ноября 2000 г. с. 32. ISBN 9780769508504. Проверено 12 июня 2012 г.
2. Дэвид К. Гиффорд, Натуральные случайные числа, MIT /LCS/TM-371, Массачусетский технологический институт, август 1988 г.
3. «Прикладная статистика: тестирование случайных чисел» . Троэлс К. Петерсен.
4. «OneRNG: О доверии и недоверии» .
5. "Джон фон Нейман".
6. Грейсен Клайн. «Непараметрические статистические методы с использованием R». 2019. с. 24.
7. Лука Тревизан. «Экстракторы и генераторы псевдослучайных чисел» (PDF) . Проверено 21 октября 2013 г.
8. Рекомендации по источникам энтропии, используемым для генерации случайных битов (проект) NIST SP800-90B, Баркер и Келси, август 2012 г., раздел 6.4.2
9. Ронен Шалтиэль. Последние разработки в области явной конструкции экстракторов. П. 5.
10. Джесси Кэмп и Дэвид Цукерман. Детерминированные экстракторы для источников с фиксацией битов и устойчивой к воздействию криптографии., SIAM J. Comput., Vol. 36, № 5, стр. 1231–1247.
11. Джесси Камп и Дэвид Цукерман. Детерминированные экстракторы для источников с фиксацией битов и устойчивой к воздействию криптографии. С. 1242.
12. Джон фон Нейман. Различные методы, используемые в связи со случайными цифрами. Серия прикладной математики, 12:36–38, 1951.
13. Прасицуппарот, Амонрат; Конно, Норио; Шиката, Дзюнджи (октябрь 2018 г.). «Численный и неасимптотический анализ экстракторов Элиаса и Переса с конечными входными последовательностями». Энтропия . 20 (10): 729. Бибкод :2018Entrp..20..729P. дои : 10.3390/e20100729 . ISSN  1099-4300. ПМЦ 7512292 . ПМИД  33265818. 
14. Персон, Кайл; Повинелли, Ричард. «Анализ генераторов псевдослучайных чисел логистической карты на предмет периодичности, вызванной представлением с плавающей запятой конечной точности». Университет Маркетта . Проверено 3 января 2024 г.

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