Односторонние функции относительно различных границ ресурса

13

Неформально односторонние функции определены в отношении алгоритмов PTIME. Они вычислимы за полиномиальное время, но не обратимы в полиномиальное время среднего случая. Существование таких функций является важной открытой проблемой в теоретической информатике.

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

Есть ли потенциальная (естественная) проблема, которая является односторонней по отношению к алгоритмам LOGSPACE? Существует ли потенциальная (естественная) проблема, которая является односторонней по отношению к недетерминированным линейным алгоритмам времени ( )?Ntime (п)

Я согласен с наихудшей жесткостью обратимости в отношении указанных выше границ ресурса.

Мухаммед Аль-Туркистани
источник
Вы видели eprint.iacr.org/2013/001.pdf ? Тема этого документа может или не может иметь отношение к вам, но методы в документе (или, возможно, даже цитаты) может привести к чему-то полезному.
Даниэль Апон
Аннотация не помогает, но спасибо за вашу помощь.
Мухаммед Аль-Туркистани
Ну хорошо - я надеюсь, что новый ответ, хотя. :)
Даниэль Апон
Да, это так :)
Мухаммед Аль-Тюркистани

Ответы:

11

Относительно пространства журналов: Несколько возможных односторонних функций вычислимы в пространстве журналов или ниже (и, предположительно, безопасны даже против злоумышленников, противников времени). Вы можете найти несколько указателей, например, в Криптографии в0 статье NC 0 .

Два конкретных примера включают в себя:

Умножение целых чисел (есть некоторые тонкости для стандартного OWF, но если вас волнует только худший случай, этого достаточно)

Кандидат Импальяццо-Наор на основе подмножества-суммы: .е(a1,,,,,aN,S)знак равно(a1,,,,,aN,ΣяSaямодификация2N)

Manu
источник
Спасибо, Эмануэле. Это отвечает случаю Logspace. Просто для полноты, не могли бы вы перечислить некоторые из этих функций в своем ответе.
Мухаммед Аль-Туркистани
Я добавил два примера.
Ману
Большое спасибо, Эмануэле. Есть ли понимание, объясняющее сложность инвертирования этих функций (алгоритмами LOGSPACE)?
Мухаммед Аль-Тюркистани