Рейтинг:1

Корреляция OWF и iO

флаг br

Какова связь между односторонними функциями (OWF) и неразличимой запутанностью (iO)? Я знаю, что iO существует даже тогда, когда P=NP и OWF не существуют. Но подразумевает ли существование OWF iO?

Geoffroy Couteau avatar
флаг cn
Обратите внимание, что iO по-прежнему «морально» подразумевает OWF: если NP не содержится (бесконечно часто) в BPP, то iO подразумевает OWF — см. [здесь] (https://eprint.iacr.org/2014/347.pdf).
Рейтинг:4
флаг kr

Мы не знаем ни о какой конструкции iO из однонаправленных функций[*], и было бы очень удивительно, если бы такая вещь существовала. Верно, iO + OWF подразумевает шифрование с открытым ключом (и различные другие примитивы «криптомании»), так что если бы только OWF подразумевал iO, он также подразумевал бы PKE.

[*] Насколько я знаю, на данный момент мы не знаем ни о каком построении iO из стандартных предположений. (см. комментарий Жоффруа ниже).

Fractalice avatar
флаг in
Я думаю, мы не знаем, как собрать PKE из OWF?
флаг kr
Да и у меня есть веские основания думать, что такой конструкции быть не должно. Например, известно, что конструкция *черного ящика* невозможна, и даже некоторые классы конструкций, отличных от черного ящика, были исключены. См., например. этот ответ: https://crypto.stackexchange.com/a/83929/1423
Geoffroy Couteau avatar
флаг cn
«На данный момент, насколько мне известно, мы не знаем ни о каком построении iO из стандартных предположений». Я не согласен, теперь у нас есть конструкции iO из совершенно прекрасных предположений: субэкспоненциальная LPN над большими полями + субэкспоненциальная жесткость PRG Гольдрейха + субэкспоненциальная SXDH. Все это старые, хорошо изученные, весьма правдоподобные предположения, которые я бы назвал стандартными.
флаг kr
Достаточно честно, я не следил за всеми последними результатами!

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

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