Последствия OWF для сложности

Хорошо известно, что наличие односторонних функций необходимо и достаточно для большей части криптографии (цифровые подписи, псевдослучайные генераторы, шифрование с закрытым ключом и т. Д.). Мой вопрос: каковы теоретико-сложные последствия существования односторонних функций? Например, OWF подразумевают, что $\mathsf{NP}\ne\mathsf{P}$ , $\mathsf{BPP}=\mathsf{P}$ , а также $\mathsf{CZK}=\mathsf{IP}$ , Есть ли другие известные последствия? В частности, подразумевают ли OWF, что полиномиальная иерархия бесконечна?

Я надеюсь лучше понять связь между наихудшим и средним уровнем твердости. Меня также интересуют результаты, идущие другим путем (то есть теоретико-сложные результаты, которые подразумевают OWF).

cc.complexity-theory reference-request complexity-classes cr.crypto-security one-way-function Томас
источник

Вы проверили литературу о мирах Импальяццо?

Каве

@ Мухаммед Ал-Тюркистан так

P \neq N P

$\mathsf{P} \neq \mathsf{NP}$ подразумевает

P \neq P H

$\mathsf{P} \neq \mathsf{PH}$ , Однако это не исключает коллапса: оно по-прежнему соответствует

N P = P H

$\mathsf{NP} = \mathsf{PH}$ ,

Сашо Николов

Томас, есть довольно много криптографических нижних границ для эффективного обучения PAC. Я полагаю, что они намекают в газете «Пять миров» Импальяццо

Сашо Николов

Я не думаю, что существование OWF (согласно их стандартному определению) подразумевает

P = B P P

$P=BPP$ , Для таких дерандомизаций нам нужны псевдослучайные генераторы с экспоненциальным растяжением, и OWF не подходят для таких целей.

Махди Черагчи

@MarzioDeBiasi:

P \neq U P

$P \neq UP$ если только OWF существуют для OWF типа "структурная сложность" (инъективные вычисляемые по времени функции без обратной по времени). Вид OWF, необходимый для криптографии, как и в этом вопросе, кажется немного более сильным (требующим необратимости случайными или неоднородными противниками на входах среднего случая).

Джошуа Грохов

Ответы:

Это поздний ответ.

Во-первых, чтобы исправить то, что вы написали: Криптографическая псевдослучайность (та, которая получена из OWF) не имеет достаточного растяжения, чтобы дерандомизировать «естественно определенные» классы вычислительной сложности. В старой статье (начало 80-х годов) Эндрю Яо показывает некоторую субэкспоненциальную временную дерандомизацию для RP и т. Д. С использованием этих объектов (кстати, это немедленно), но более сильная дерандомизация не известна. Обратите внимание, что с точки зрения дурацкой мощности криптографические PRG сильнее, чем то, что вам нужно для дерандомизации, но в то же время с точки зрения их растяжения слабее, чем их типичные теоретико-сложные аналоги (это следует по порядку количественного определения в определении PRGS).

Как отметил Сашо Николов, в PAC есть множество примеров. Взгляните на очень раннюю статью Кернса и Валианта о невозможности изучения формул и автоматов (см. Ссылки в Google ученом оттуда). Кроме того, есть последствия в сложности доказательства через интерполяцию - взгляните также на ранние работы Яна Крайчека и Павла Пудлака. Тем не менее, я не уверен, считаете ли вы это теориями сложности (но я так понимаю).

- Периклис

user17164
источник

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

Мухаммед Аль-Туркистани
источник