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

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

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

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

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

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

В мин-энтропия распределения ${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}$ .

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

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

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

В приведенном выше определении ε-close относится к статистическое расстояние.

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

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

Экстрактор силен, если сцепление посевной материал с мощностью экстрактора дает распределение, близкое к равномерному.

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

{displaystyle {ext {Ext}}: {0,1} ^ {n} imes {0,1} ^ {d} ightarrow {0,1} ^ {m},}

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

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

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

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

{displaystyle {ext {Ext}} _ {n}: {0,1} ^ {n} imes {0,1} ^ {d (n)} ightarrow {0,1} ^ {m (n)}}

является явным (k, ε) -экстрактор, если Ext (Икс, у) можно вычислить в полиномиальное время (по входной длине) и для каждого п, Ext_п это (k(п), ε(п)) - экстрактор.

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

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

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

{displaystyle m = k + d-2log left ({frac {1} {varepsilon}} ight) -O (1)}

.^[5]

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

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

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

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

Следующие параграфы определяют и устанавливают важную взаимосвязь между двумя видами 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): А ${displaystyle k = k (n)}$ APRF - это функция ${displaystyle f}$ где для любой настройки ${displaystyle n-k}$ биты ввода ${displaystyle r}$ для любых фиксированных значений вектор вероятности ${displaystyle p}$ выхода ${displaystyle f (r)}$ над случайным выбором для ${displaystyle k}$ оставшиеся биты удовлетворяют ${displaystyle | p_ {i} -2 ^ {- m} | <2 ^ {- m} эпсилон (п)}$ для всех ${displaystyle i}$ и для какой-то незначительной функции ${displaystyle epsilon (n)}$ .

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

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

Эта лемма доказана Кампом и Цукерманом.^[7] Лемма доказывается путем исследования расстояния от формы выхода, которое в ${displaystyle 2 ^ {- m} эпсилон (п)}$ -экстрактор явно не более ${displaystyle 2 ^ {- m} эпсилон (п)}$ , что удовлетворяет условию АПРФ.

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

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

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

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

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

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

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

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

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

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

{displaystyle (n, k) = (n, delta n) Стрелка вправо k = delta n}

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

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

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

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

{displaystyle Дельта правой стрелки ^ {2} = n ^ {2gamma -1}}

{displaystyle Дельта правой стрелки = 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}$

Примеры

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

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

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

Машина хаоса

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

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

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

Приложения

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

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

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

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