Есть ли у «односторонних функций» какие-либо приложения вне криптографии?

16

Функция $f \colon \{0, 1\}^* \to \{0, 1\}^*$ является односторонней, если $f$ может быть вычислена с помощью алгоритма полиномиального времени, но для каждого рандомизированного алгоритма полиномиального времени $A$ ,

$\Pr[f(A(f(x))) = f(x)] < 1/p(n)$

для любого многочлена и достаточно большого , предполагая, что выбран равномерно из . Вероятность берется по выбору и хаотичности . $p(n)$ $n$ $x$ $\{ 0, 1 \}^n$ $x$ $A$

Итак ... есть ли у "One Way Functions" какие-либо приложения вне криптографии? Если да, то каковы они?

cc.complexity-theory cr.crypto-security one-way-function Тарек Радван
источник

1

Я исправил формулы в форму LaTeX, но в MathJax, похоже, есть сбой, так как он правильно просматривает уравнения, но показывает ошибку «Неверно». Я думаю, что это будет исправлено в ближайшее время ...

MS Dousti

1

Для меня это больше похоже на ошибку в SE. По какой-то причине он, похоже, не распознает двойную \ как escape-последовательность, которая должна вывести единственную \, которая затем будет обработана MathJax.

Юкка Суомела

2

В посте это

, но для этого требуется одна дополнительная закрывающая скобка ")".

P r [f (A (f (x), 1^{n}) = x] < 1 / p (n)

$Pr[f(A(f(x),1^n)=x]<1/p(n)$

Александр Бондаренко

2

@ Садек и Юкка: Это может быть связано с недавно исправленной ошибкой в SE: meta.math.stackexchange.com/questions/1115/…

Tsuyoshi Ito

@Tsuyoshi: Спасибо за содержательный комментарий!

MS Dousti

23

Односторонние функции имеют решающее значение в результате естественных доказательств Разборова-Рудича. Я бы не стал рассматривать нижние границы схемы как часть «криптографии», так что, возможно, это соответствует вашим критериям.

mikero
источник

11

Односторонние функции также фигурировали в некоторых дискуссиях вокруг гипотезы Бермана-Хартманиса об изоморфизме . Джозеф и Янг предположили, что если бы существовали односторонние функции, то гипотеза об изоморфизме не сработала (односторонние против детерминированных противников, а не вероятностных, но, надеюсь, это достаточно близко для целей этого вопроса). Джон Роджерс дал релятивизированный мир, в котором гипотеза Джозефа-Юнга провалилась (то есть, где существуют односторонние функции, но гипотеза изоморфизма верна). Но насколько я знаю, гипотеза JY по-прежнему является одним из основных технических доказательств, которые заставляют людей думать, что гипотеза об изоморфизме неверна (если они так думают).

Суть идеи Иосифа и Янга заключается в том, что если является односторонней функцией, то $f$ является -полным, но «не должно» быть изоморфным SAT. $f(SAT)$ $NP$

Джошуа Грохов
источник

8

Да хеш-таблица или хеш-карта требуют односторонней функции. Также обнаружение дубликатов (см. Это и это ) может быть сделано очень эффективно с использованием односторонних функций. В обоих случаях требуются «хорошие» (с низкой вероятностью столкновения) односторонние функции, в то время как криптографическая стойкость обычно не требуется .

Sharptooth
источник

Да, хеш-функции широко используются для хеш-таблиц.

Gamlor

2

ваш ответ не правильный. Для обнаружения дубликатов требуется устойчивость к столкновениям, которая отличается от односторонней. Смотрите определение в оригинальном вопросе для тщательного определения одностороннего. Иногда люди свободно используют фразу «односторонний хэш» как синоним криптографической хэш-функции, но это вводит в заблуждение, поскольку во многих приложениях важно не свойство «одностороннего», а скорее устойчивость к столкновениям ( как при обнаружении дубликатов) или поведение как случайный оракул (как при хешировании).

DW

6

Есть много результатов "криптографической стойкости" (только Google, эта фраза) для проблем обучения. Это результаты твердости, предполагающие существование односторонних функций.

Дана Мошковиц
источник

4

Можете ли вы дать мне точное определение «криптографической стойкости»?

Тарек Радван

1

Результаты стандартной твердости предполагают, что P не равно NP; если это так, то задача занимает суперполиномиальное время. Результаты «криптографической стойкости» предполагают нечто более сильное: существуют односторонние функции. Это предположение подразумевает (и является более сильным, чем) усредненность некоторых проблем.

Дана Мошковиц

5

Односторонние функции имеют применение в колмогоровской сложности:

$x$ $y$ симметрична с точностью до логарифмической аддитивной ошибки. Аналогично, ограниченная полиномиальным временем симметрия информационной гипотезы утверждает, что

$K^q(x, y) = K^q(x) + K^q(y|x) + O(\log n)$ для любого полинома $q$

Если существуют односторонние функции, то ограниченная полиномиальным временем симметрия информационной гипотезы ложна.

Л. Лонгпре и С. Мокас. Симметрия информации и односторонние функции. Письма обработки информации, 46 (2): 95 {100, 1993

Л. Лонгпре и О. Ватанабе. О симметрии информации и полиномиальной обратимости времени. Информация и вычисления, 121 (1): 14 {22, 1995

Mohammad Al-Turkistany
источник

Есть ли у «односторонних функций» какие-либо приложения вне криптографии?

Ответы: