Неформально односторонние функции определены в отношении алгоритмов PTIME. Они вычислимы за полиномиальное время, но не обратимы в полиномиальное время среднего случая. Существование таких функций является важной открытой проблемой в теоретической информатике.
Я заинтересован в односторонних функциях (не обязательно для криптографических приложений), определенных с учетом различных границ ресурсов. Такими границами ресурса может быть LOGSPACE или ограниченный недетерминизм.
Есть ли потенциальная (естественная) проблема, которая является односторонней по отношению к алгоритмам LOGSPACE? Существует ли потенциальная (естественная) проблема, которая является односторонней по отношению к недетерминированным линейным алгоритмам времени ( )?
Я согласен с наихудшей жесткостью обратимости в отношении указанных выше границ ресурса.
источник
Ответы:
Относительно пространства журналов: Несколько возможных односторонних функций вычислимы в пространстве журналов или ниже (и, предположительно, безопасны даже против злоумышленников, противников времени). Вы можете найти несколько указателей, например, в Криптографии в0 статье NC 0 .
Два конкретных примера включают в себя:
Умножение целых чисел (есть некоторые тонкости для стандартного OWF, но если вас волнует только худший случай, этого достаточно)
Кандидат Импальяццо-Наор на основе подмножества-суммы: .е( а1, . , , ,N, S) : = ( а1, . , , ,N, Σi ∈ Saямодификация2N)
источник