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

Question

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

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

x - бит строки над 0 и 1 сек.

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

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

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

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

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

Answer 1

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

Его следует определять как: Случайная функция {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 2

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

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

Answer 3

Похоже, да:

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

---

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

Благодаря @adamax для указания этого.

Answer 4

Да, если R (x) определяется как RANDOM в его истинном смысле, выход будет сильно изменяться с небольшими вариациями x. Это означает, что R (x) совершенно различна и не связана с выходом R (x '). Кроме того, концентрация на двух случайных выходах также даст случайный выход.