Можем ли мы объединить два настоящих генератора случайных чисел, чтобы получить новый?

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

Мой вопрос заключается в том, что если у нас есть два настоящих генератора случайных битов, выходные данные которых не проходят набор тестов NIST, можем ли мы объединить эти выходные данные, чтобы получить генератор случайных битов, который проходит наборы тестов статистической случайности?

Это на самом деле делается довольно часто в схемах. Рассмотрим общий полностью цифровой TRNG на основе кольцевых генераторов:

Приведенный выше пример является еще более экстремальным, чем ваш, где используется много (возможно, 32) отдельных кольцевых генераторов. Все они идентичны, все эффектно проваливают любой тест на случайность, но сами по себе производят энтропию. Если для производства 1 бита энтропии на такт требуется 32 кольцевых генератора, вы можете себе представить, что каждый из них должен производить намного меньше. Их смещения также должны быть очень высокими (что характерно для таких осцилляторов). Их объединение значительно улучшает скорость энтропии и, следовательно, уменьшает смещение вывода.

Другим примером является генерация $м \раз п$ матрицы извлечения случайности, используемые в TRNG. Из ID Quantique, Технический документ по экстрактору случайности, версия 1.0, сентябрь 2012 г.:-

В идеале r отдельных источников, используемых в описанной процедуре для генерации матрицы m, должны быть получены из разных источников.

Это анекдотично иллюстрирует концепцию.Математически подходящей парадигмой является лемма о накоплении (Мицуру Мацуи, Метод линейного криптоанализа для шифрования DES) :-

За $n$ независимые случайные бинарные переменные, $X_1, X_2, \ldots X_n$,

$$ Pr(X_1 \oplus \ldots \oplus X_n = 0) = \frac{1}{2} + 2^{n-1} \prod_{i=1}^n \epsilon_i $$

Перестановка, так что если $ \epsilon_{1,2, \ldots, n} $ представляет предвзятость $ X_1 \oplus \ldots \oplus X_n = 0 $, получаем окончательное смещение $n$ объединенные независимые источники как: -

$$ \epsilon_{1,2, \ldots, n} = 2^{n-1} \prod_{i=1}^n \epsilon_i $$

Короче говоря, по мере того, как вы комбинируете все больше и больше независимых ГСЧ, общее смещение вывода асимптотически стремится к нулю. Поэтому создайте новый, лучший.

Да. Мы можем объединить два генератора случайных чисел и сделать лучший. Простейшей формой было бы XOR двух значений. Если хотя бы одно из них случайное, то таким же будет и выход. Это не исправляет все, но имеет хорошие доказуемые свойства. По сути, это, по крайней мере, так же хорошо, как и то и другое (при условии, что они не коррелировали с самого начала).

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

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