Если R (x) - случайная функция, то R (x) ||R (x ') тоже случайная функция?

Question

Если R (x) - случайная функция, то R (x) ||R (x ') тоже случайная функция?

R (x) является случайным в истинном смысле.

x - битовая строка от 0 до 1 с.

x 'является дополнением к x.

||это простая конкатенация

Редактировать:

Этот R (x) выбирается случайным образом из семейства функций {0,1} ^ k -> {0,1) ^ k.Как только R (x) был выбран, это исправлено.Таким образом, один и тот же вход будет генерировать тот же результат.Длина R (x) фиксирована (k, скажем, 32)

G (x) = R (x) ||Р (х ')

Answer 1

Предполагая, что R() - это стандартная сеяная функция PRNG, если R(x) является случайным, то R(x') также является случайным, поскольку это просто альтернативное начальное число для вашего PRNG. Кроме того, R(x) + R(x') также является случайным, поскольку это будет просто конкатенация двух случайных строк.

Однако можно атаковать x, зная, что y = R(x) + R(x'), который, хотя и не снизит случайность строки, может открыть слабые места, если эта случайная функция будет использоваться для каких-либо целей, связанных с безопасностью. .

Answer 2

Похоже, да:

Считайте вероятность p из R(x) || R(x') равной любой данной y, пусть y = y_1 || y_2.Тогда p равно вероятности R(x) = y_1 кратной вероятности R(x') = y_2, поскольку оба случая независимы.Мы видим, что он не зависит от y, поэтому он одинаков для всех y.

---

Редактировать:
Если, однако, значение R(x) однозначно определяет значениеR(x'), результирующая функция не случайна!Поскольку значение R(x) || R(x') не может быть произвольным: первая половина значения определяет вторую половину, поэтому значение не может быть произвольным.Это означает, что определенные значения имеют вероятность 0.

Спасибо @adamax за указание на это.

Answer 3

В определении, которое я дал для случайной функции, есть фундаментальный недостаток.

Это должно быть определено как: Случайная функция {0,1} ^ k1 -> {0,1} ^ k2 - это случайно выбранная функция из семейства всех возможных функций над {0,1} ^k1 -> {0,1} ^ k2

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

В нашем случае, предполагая, что R (x): {0,1} ^ k -> {0,1} ^ k - случайная функция, R (x) случайным образом выбирается из семейства функций.

Доказать, что G (x) = R (x) ||R (x '): {0,1} ^ k -> {0,1} ^ 2k - случайная функция, нам нужно установить, что G (x) действительно выбирает случайным образом из семейства функций над {0,1} ^k -> {0,1} ^ 2k, учитывая, что R (x) - случайная функция.Однако это не так, поскольку пример с небольшим счетчиком покажет, что G (x) выбирает из меньшего подмножества семейства функций.

Следовательно, G (x) не является случайным, даже если R (x)это

Answer 4

Да, если R (x) определен как СЛУЧАЙНЫЙ в истинном смысле, результат будет сильно отличаться с небольшими изменениями x Это означает, что R (x) полностью отличается и не имеет отношения к выходу R (x '). Кроме того, концентрация на двух случайных выходах будет также производить случайный выход.