Регистрация Войти
Рейтинг:0
Zoey avatar Crypto

Исключающее ИЛИ всех битов $f(x)$ хардкорный бит

флаг cn
Zoey

Зачем рассматривать случайный $г$ в построении хардкорного предиката в теореме Гольдрейха-Левина? Почему бы не рассмотреть только XOR всех битов ввода?

76
0 + 0
флаг cn
Maeher
Пусть $f : \{0,1\}^n \to \{0,1\}^n$ — односторонняя функция. Рассмотрим функцию $g : \{0,1\}^n \to \{0,1\}^{n+1}$, определенную как $g(x) = g(x_1\ldots x_n) := f( x)\Vert \bigoplus_{i=1}^{n} x_i$. Является ли $g$ односторонним? Является ли xor всех входных бит хардкорным предикатом для $g$?
2
Ответить
Zoey avatar
флаг cn
Zoey
это не так, так как это часть вывода. Но тогда почему нельзя сделать то же самое с . Если вы включите это в вывод, это будет не слишком хардкорно, верно? Также не является ли XOR особым случаем, когда r равно 1?
0
Ответить
флаг cn
Maeher
Помните, что GL определяет *конкретный* OWF, для которого внутренний продукт является хардкорным.
0
Ответить
флаг cn
Maeher
$r$ является частью *входа*, вы не можете *установить* его на что-либо, он выбирается случайным образом. Но что особенно важно, это не часть входных данных *базовой* функции, так что эта функция не может делать ничего смешного.
1
Ответить
Zoey avatar
флаг cn
Zoey
Позвольте мне попытаться понять здесь: XOR битов не является хардкорным битом для любого OWF, потому что мы можем создать такую, где XOR является частью вывода. XOR может быть хардкором базовой функции $f$, это происходит, если $r= 11...1$ (все единицы) является случайно выбранным выбором для ввода GL-преобразования $f$, т.е. $g$ .
0
Ответить
флаг Moldova
Admin
Этот вопрос на других языках:

Ответить или комментировать

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