Случайность экстрактор , часто просто называют «экстрактором», представляет собой функцию, которая применяется к выходу из слабо случайной энтропии источника, вместе с коротким, равномерно случайными начальным числом , генерирует весьма случайный выход , который появляется независимым от источника и равномерно распределены . [1] Примеры слабослучайных источников включают радиоактивный распад или тепловой шум.; единственное ограничение на возможные источники состоит в том, что их невозможно полностью контролировать, рассчитывать или предсказывать, и что можно установить нижнюю границу их энтропии. Для данного источника экстрактор случайности может даже рассматриваться как истинный генератор случайных чисел ( TRNG ); но не существует единого экстрактора, который, как было доказано, производил действительно случайный результат из любого типа слабо случайного источника.
Иногда термин «смещение» используется для обозначения отхода слабо случайного источника от единообразия, и в старой литературе, некоторые экстракторы называются unbiasing алгоритмов , [2] , поскольку они берут хаотичность из так называемых «предвзятого» источника и вывода распределение, которое кажется беспристрастным. Слабо случайный источник всегда будет длиннее, чем мощность экстрактора, но эффективный экстрактор - это тот, который максимально снижает это соотношение длин, одновременно сохраняя низкую длину затравки. Интуитивно это означает, что из источника «извлечено» как можно больше случайности.
Обратите внимание, что экстрактор имеет некоторое концептуальное сходство с генератором псевдослучайных ситуаций (PRG), но эти две концепции не идентичны. Обе функции принимают на входе небольшое равномерно случайное начальное число и выдают более длинный результат, который «выглядит» равномерно случайным. Некоторые псевдослучайные генераторы, по сути, также являются экстракторами. (Когда PRG основана на существовании жестких предикатов , можно рассматривать слабо случайный источник как набор таблиц истинности таких предикатов и доказывать, что результат статистически близок к однородному. [3] ) общее определение PRG не указывает, что должен использоваться слабо случайный источник, и хотя в случае экстрактора, выход должен быть статистически близким к однородному, в PRG требуется только, чтобы он был вычислительно неотличим от однородного, несколько более слабого концепция.
Специальная публикация NIST 800-90B (черновик) рекомендует несколько экстракторов, включая семейство хэшей SHA, и заявляет, что если количество вводимой энтропии вдвое превышает количество битов, выводимых из них, этот вывод можно считать по существу полностью случайным. [4]
Формальное определение экстракторов
Мин-энтропия из распределения (обозначается ), является наибольшим действительным числом такой, что для каждого в диапазоне . По сути, это измеряет, насколько вероятно должен принимать наиболее вероятное значение, давая оценку наихудшего случая того, насколько случайным появляется. Сдача обозначим равномерное распределение по , четко .
Для n- битного распределенияс мин-энтропией k , мы говорим, что является распределение.
Определение (экстрактор): ( k , ε ) -экстрактор
Позволять быть функцией, которая принимает в качестве входных данных образец из распределение и d- битное семя из, и выводит m- битную строку.является ( k , ε ) -экстрактором , если для всех распределения , выходное распределение есть ε -близкое к.
В приведенном выше определении ε -close относится к статистическому расстоянию .
Интуитивно, экстрактор принимает слабо случайный n- битный ввод и короткое равномерно случайное начальное число и выдает m- битный вывод, который выглядит равномерно случайным. Цель состоит в том, чтобы иметь низкий (т. е. использовать как можно меньше однородной случайности) и как можно более высокое насколько это возможно (то есть, чтобы получить как можно больше битов, близких к случайным).
Сильные экстракторы
Экстрактор является сильным, если объединение семени с выходной мощностью экстрактора дает распределение, которое все еще близко к однородному.
Определение (сильный экстрактор): A-сильный экстрактор - это функция
такой, что для каждого распределение распространение (две копии обозначают одну и ту же случайную величину) -Близко к равномерному распределению на .
Явные экстракторы
Используя вероятностный метод , можно показать , что существует ( K , е ) -extractor, то есть , что строительство возможно. Однако обычно недостаточно просто показать, что экстрактор существует. Требуется явная конструкция, которая дается следующим образом:
Определение (явный экстрактор): для функций k ( n ), ε ( n ), d ( n ), m ( n ) семейство Ext = {Ext n } функций
является явным ( k , ε ) -экстрактором, если Ext ( x , y ) можно вычислить за полиномиальное время (по его входной длине) и для каждого n Ext n является a ( k ( n ), ε ( n )) -экстрактор.
Вероятностным методом можно показать, что существует ( k , ε ) -экстрактор с начальной длиной
и длина вывода
- . [5]
Диспергаторы
Вариант экстрактора случайности с более слабыми свойствами - диспергатор .
Экстракторы случайности в криптографии
Одним из наиболее важных аспектов криптографии является генерация случайных ключей . [6] Часто бывает необходимо сгенерировать секретные и случайные ключи из источников, которые являются полусекретными или которые могут быть в некоторой степени скомпрометированы. Взяв в качестве источника единственный короткий (и секретный) случайный ключ, можно использовать экстрактор для генерации более длинного псевдослучайного ключа, который затем можно использовать для шифрования с открытым ключом. В частности, когда используется сильный экстрактор, его вывод будет казаться равномерно случайным даже для того, кто видит часть (но не весь) источника. Например, если источник известен, но исходное значение неизвестно (или наоборот). Это свойство экстракторов особенно полезно в так называемой криптографии, устойчивой к воздействию, в которой требуемый экстрактор используется как функция устойчивости к воздействию (ERF). Устойчивая к раскрытию криптография учитывает тот факт, что трудно сохранить в секрете первоначальный обмен данными, который часто происходит во время инициализации приложения шифрования, например, отправитель зашифрованной информации должен предоставить получателям необходимую информацию. для расшифровки.
Следующие параграфы определяют и устанавливают важную взаимосвязь между двумя типами ERF - k -ERF и k -APRF, которые полезны в криптографии, устойчивой к уязвимости .
Определение ( k -ERF): адаптивная k-ERF - это функция где для случайного входа , когда вычислительно неограниченный противник может адаптивно читать все кроме биты для какой-то незначительной функции (определено ниже).
Цель состоит в том, чтобы построить адаптивный ERF, выходные данные которого сильно случайны и равномерно распределены. Но часто требуется более сильное условие, при котором каждый выход происходит с почти равномерной вероятностью. Для этого используются почти идеальные упругие функции (APRF). Определение APRF следующее:
Определение (k-APRF): A APRF - это функция где для любой настройки биты ввода для любых фиксированных значений вектор вероятности выхода над случайным выбором для оставшиеся биты удовлетворяют для всех и для какой-то незначительной функции .
Камп и Цукерман [7] доказали теорему о том, что если функцияявляется к -APRF, тотакже является k- ERF. Более конкретно, любой экстрактор, имеющий достаточно маленькую ошибку и принимающий на вход не обращающий внимания , источник с фиксацией битов, также является APRF и, следовательно, также k -ERF. Более конкретный экстрактор выражен в этой лемме:
Лемма: Любая -экстрактор для набора не обращая внимания на источники исправления битов, где пренебрежимо мала, также является k-APRF.
Эта лемма доказана Кампом и Цукерманом. [7] Лемма доказывается путем исследования расстояния от формы выхода, которое в-экстрактор явно не больше , что удовлетворяет условию АПРФ.
Лемма приводит к следующей теореме, утверждающей, что на самом деле существует k -APRF-функция, как описано:
Теорема (существование): для любой положительной константы существует явный k-APRF , вычислимым за линейное число арифметических операций над -битовые строки, с а также .
Определение (незначительная функция): для доказательства этой теоремы нам понадобится определение незначительной функции . Функция определяется как незначительное, если для всех констант .
Доказательство: рассмотрим следующее.-extractor: функция экстрактор для набора не обращая внимания на источник исправления битов: . имеет , а также .
Доказательство существования этого экстрактора с , а также тот факт, что он вычислим за линейное вычислительное время на длине можно найти в статье Джесси Кампа и Дэвида Цукермана (стр. 1240).
То, что этот экстрактор удовлетворяет критериям леммы, очевидно, так как это незначительная функция.
Размер является:
Поскольку мы знаем то нижняя граница преобладают . На последнем этапе мы используем тот факт, что что означает, что сила самое большее . И с тех пор положительное целое число, которое мы знаем, что самое большее .
Значение вычисляется с использованием определения экстрактора, где мы знаем:
и используя значение у нас есть:
Используя это значение мы учитываем худший случай, когда находится на его нижней границе. Теперь с помощью алгебраических вычислений получаем:
Который вставлен в значение дает
- ,
что доказывает, что существует явный экстрактор k-APRF с заданными свойствами.
Примеры
Экстрактор фон Неймана
Возможно, самый ранний пример принадлежит Джону фон Нейману . Из входного потока его экстрактор брал биты, по два за раз (первый и второй, затем третий и четвертый и т. Д.). Если два бита совпадают, выходной сигнал не генерируется. Если биты различались, выводилось значение первого бита. Можно показать, что экстрактор фон Неймана производит однородный выходной сигнал, даже если распределение входных битов неоднородно, при условии, что каждый бит имеет одинаковую вероятность быть одним и нет корреляции между последовательными битами. [8]
Таким образом, он принимает в качестве входных данных последовательность Бернулли с p, не обязательно равным 1/2, и выводит последовательность Бернулли сВ более общем смысле, это применимо к любой заменяемой последовательности - оно основывается только на том факте, что для любой пары 01 и 10 одинаково вероятны: для независимых испытаний они имеют вероятности, в то время как для заменяемой последовательности вероятность может быть более сложной, но обе равновероятны.
Машина хаоса
Другой подход - использовать выходные данные машины хаоса, применяемые к входному потоку. Этот подход обычно основан на свойствах хаотических систем . Входные биты передаются в машину, изменяя орбиты и траектории в нескольких динамических системах. Таким образом, небольшие различия во входных данных приводят к очень разным выходным данным. Такая машина имеет однородный выход, даже если распределение входных битов неоднородно или имеет серьезные недостатки, и поэтому может использовать слабые источники энтропии . Кроме того, эта схема позволяет повысить сложность, качество и безопасность выходного потока, что контролируется указанием трех параметров: временных затрат , требуемой памяти и секретного ключа .
Криптографическая хеш-функция
Также возможно использовать криптографическую хеш-функцию в качестве экстрактора случайности. Однако не каждый алгоритм хеширования подходит для этой цели. [ необходима цитата ]
Приложения
Экстракторы случайности широко используются в криптографических приложениях, при этом криптографическая хеш- функция применяется к высокоэнтропийным, но неоднородным источникам, таким как информация о синхронизации дисковода или задержки клавиатуры, для получения однородно случайного результата.
Экстракторы случайности сыграли свою роль в недавних разработках в области квантовой криптографии , где фотоны используются экстрактором случайности для генерации безопасных случайных битов. [1]
Извлечение случайности также используется в некоторых разделах теории сложности вычислений .
Случайное извлечение также используется для преобразования данных в простую случайную выборку, которая нормально распределена и независима, чего требует статистика.
Смотрите также
Рекомендации
- ^ «Извлечение случайности из выборочных распределений» . Portal.acm.org . Проверено 12 июня 2012 . CS1 maint: обескураженный параметр ( ссылка )
- ^ Дэвид К. Гиффорд, Натуральные случайные числа, MIT / LCS / TM-371, Массачусетский технологический институт, август 1988 г.
- ^ Лука Тревизан. «Экстракторы и псевдослучайные генераторы» (PDF) . Проверено 21 октября 2013 . CS1 maint: обескураженный параметр ( ссылка )
- ^ Рекомендации по источникам энтропии, используемым для генерации случайных битов (черновик) NIST SP800-90B , Баркер и Келси, август 2012 г., раздел 6.4.2
- ↑ Ронен Шалтиэль. Последние разработки в явной конструкции экстракторов. С. 5.
- ^ Джесси Камп и Дэвид Цукерман. Детерминированные экстракторы для источников с фиксацией битов и устойчивой к уязвимости криптографии., SIAM J. Comput., Vol. 36, № 5, с. 1231–1247.
- ^ a b Джесси Камп и Дэвид Цукерман. Детерминированные экстракторы для источников с исправлением битов и устойчивой к уязвимости криптографии. С. 1242.
- ^ Джон фон Нейман. Различные методы, используемые в связи со случайными цифрами. Серия прикладной математики, 12: 36–38, 1951.
- Экстракторы случайности для независимых источников и приложений , Ануп Рао
- Последние разработки явных конструкций экстракторов , Ронен Шалтиэль
- Извлечение случайности и вывод ключей с использованием режимов CBC, Cascade и HMAC , Евгений Додис и др.
- Ключевые выводы и извлечение случайности , Olivier Chevassut et al.
- Детерминированные экстракторы для источников с исправлением битов и устойчивой к уязвимости криптографии , Джесси Камп и Дэвид Цукерман
- Подбрасывание необъективной монеты (и оптимальность продвинутой многоуровневой стратегии) (конспект лекции) , Михаэль Митценмахер