Аргументы в пользу существования односторонних функций

25

Я читал в нескольких статьях, что существование односторонних функций широко распространено. Может кто-то пролить свет на то, почему это так? Какие у нас аргументы в пользу существования односторонних функций?

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

Ответы:

22

Вот аргумент, что односторонние функции должно быть трудно инвертировать. Предположим, есть класс проблем 3-SAT с посаженными решениями, которые трудно решить. Рассмотрим следующую карту:

(x,r)s

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

Этот аргумент показывает, что инвертировать одностороннюю функцию так же сложно, как решить проблемы -SAT с посаженными решениями. А поскольку -SAT является NP-полной задачей, если вы можете выяснить, как создавать сложные экземпляры с посаженными решениями для любой NP-задачи, вы можете внедрить решения в формулах -SAT.к кККК

Не было доказано, что можно придумать класс NP-полных задач с посаженными решениями, которые столь же сложны, как и произвольные NP-полные задачи (и даже если это правда, это будет невероятно сложно доказать) , но люди определенно знают, как внедрять решения проблем -SAT способами, которые в настоящее время никто не знает, как их решать.К

ДОБАВЛЕНО: теперь я понимаю, что эта связь уже была дана (более подробно) в Абади, Аллендере, Бродере, Фейгенбауме и Хемачандре ; они указывают на то, что односторонние функции могут дать решаемые сложные экземпляры SAT, и наоборот.

Если говорить более неформально, отсутствие односторонних функций показывает, что по-настоящему сложных головоломок не может быть. Если есть тип головоломки, где кто-то может придумать и головоломку, и ее решение алгоритмически, то есть также алгоритм полиномиального времени для нахождения решения головоломки. Это кажется мне очень нелогичным. Конечно, полиномиальный разрыв может существовать; может случиться так, что если для создания головоломки потребовалось шагов, то для ее решения может потребоваться шагов. Однако моя интуиция говорит, что должен быть суперполиномиальный разрыв. O ( n 3 )NО(N3)

Питер Шор
источник
1
Разве это не тот же аргумент, что и у Садека, в том смысле, что оба полагаются на некоторые проблемы, которые в настоящее время никто не знает, как решить, несмотря на большие усилия?
Цуёси Ито
2
@Sadeq: вы можете дать алгоритму практически все случайные биты, которые вам нужны для этого аргумента; вам действительно не нужен PRG, и уж точно не криптографически сильный.
Питер Шор
6
@ Tsuyoshi: Я думаю, что генерация сложных случаев проблем NP с посаженными решениями является несколько более общей, чем факторинг или дискретный лог; с одной стороны, это не известно, чтобы быть в BQP.
Питер Шор
3
@Tsuyoshi: я хотел бы видеть другой подход; к сожалению, у меня его нет. Но это означает, что действительно сложные головоломки не могут существовать; если есть тип головоломки, где кто-то может придумать головоломку и ее решение алгоритмически, то есть также алгоритм полиномиального времени для решения головоломки. Это кажется мне очень нелогичным.
Питер Шор
4
@ Tsuyoshi: Я думаю, что Питер считает, что не существует только двух или трех кандидатов в OWF; кандидаты чрезвычайно многочисленны и почти тривиальны, чтобы придумать. Например, если вы посмотрите на работу, связанную с конкурсом SHA-3 NIST, кажется, что «OWF» создавать «легко», и люди в основном заинтересованы в разработке сверхбыстрых OWF, которые все еще соответствуют очень строгому понятию безопасности.
Тимоти Чоу
13

Я дам краткий ответ: существование, казалось бы, трудных проблем, таких как FACTORING или DISCRETE LOG, заставило теоретиков поверить в существование OWF. В частности, они десятилетиями (с 1970-х годов) пытались найти эффективные (вероятностные полиномиальные) алгоритмы для таких задач, но ни одна попытка не увенчалась успехом. Это рассуждение очень похоже на то, почему большинство исследователей считают, что P ≠ NP.

М.С. Дусти
источник
Что мне не нравится в этом убеждении, так это то, что обе проблемы связаны с BQP, поэтому, если они действительно односторонние, а квантовые компьютеры оказываются практичными, то следует изменить определение односторонней функции (чтобы противостоять квантовым время противников вместо просто рандомизированных). Знаете ли вы кандидатов на сильные односторонние функции в этом смысле? Существуют ли кандидаты типа сильных односторонних функций, которые предполагают Разборова-Рудича в своей теореме?
Диего де Эстрада
1
Ответ на мой первый вопрос: dx.doi.org/10.1016/j.tcs.2007.03.013
Диего де Эстрада
3
Т.е. у нас нет никаких аргументов по этому поводу, кроме того, что никто еще не решил эти проблемы. Это очень недельный аргумент. В том же духе мы верим в твердость всего, что еще не решили. Мы могли бы сказать , что это широко полагают , что факторинг не в , но я не видел , чтобы кто утверждает , что. Должна быть какая-то другая причина для того, чтобы широко верить в существование OWF. Сравнение с P против NP несправедливо. Есть много естественных эквивалентных NP-полных задач. DTяMЕ(ехр(N1/4))
Аноним
10
Должен быть лучший аргумент в пользу того, почему существуют односторонние функции, чем то, что мы знаем множество функций, которые мы еще не знаем, как инвертировать. Я посмотрю, смогу ли я придумать один.
Питер Шор
1
@Anonymous: Re: «широко полагают , [так] , что факторинг не в » вы можете проверить недавние улучшения в дискретном журнале: eprint.iacr.org/ 2013/400 (следующий eprint.iacr.org/2013/095 ). DTяMЕ(еИксп(N1/4))
Джошуа Грохов
-5

Аргумент Сашо опирается на вечную проблему P = NP, для которой в настоящее время нет единого мнения.

Однако, если мы будем следовать криптоанализу Шеннона одноразовых блокнотов, рассекреченных в 1947 г., то есть: не существует математически безопасного алгоритма шифрования, кроме одноразового блокнота. Его аргумент основан на идее, что, если мы имеем действительно случайную последовательность чисел и для некоторой последовательности для шифрования, s 1 , s 2 , s 3 , , s п , мы шифруем следующим образом:р1,р2,р3,...,рNs1,s2,s3,...,sN

е(ря,sя)знак равноряsязнак равнося

е-1(ря,sя)

Мы могли бы имитировать результат Шеннона для односторонних функций.

е:Z/NZ×Z/NZZ/NZе:Z/NZZ/NZ×Z/NZ

Суть в том, что мы не знаем, существуют ли действительно случайные числа, поскольку этот вопрос эквивалентен комментарию Эйнштейна «Бог не играет в кости».

Однако для всех целей генератор случайных чисел, основанный на физическом процессе, считается экспертом достаточно случайным.

(ся,ря)

е(ря,sК)е(рJ,sК)sКе(ря,sя)знак равное(рJ,sJ)

mathersjj1
источник
5
Результат Шеннона - о теоретико-информационной безопасности (когда противник обладает неограниченными вычислительными возможностями). Это не то, о чем вопрос. Вопрос состоит в том, чтобы задать односторонние функции с вычислительной безопасностью (где противник ограничен вычислениями за полиномиальное время). Следовательно, аргументы в стиле Шеннона ничего не говорят о том, существуют ли односторонние функции с вычислительной безопасностью.
DW
Прочитайте определение односторонней функции .
Каве
Ker-I Ko определяет одностороннюю функцию относительно задачи P = NP и полиномиального изоморфизма. Более конкретно, если существуют односторонние функции, то гипотеза Кука о NP-полноте, т.е. изоморфизме между NP-полными множествами, не выполняется. С точки зрения информационной энтропии интерес состоит в том, чтобы показать, что класс изоморфизма математически определяемых функций безопасен (необратим) только в том случае, если можно определить случайное множество. Я не уверен во вкладе Шеннона в неразборчивость и в использовании выражения «математически безопасно».
mathersjj1
2
cstheory - это не дискуссионный форум или личный блог, это сайт вопросов и ответов. Ваш пост не является ответом на вопрос об односторонних функциях (как определено в ссылке). Проверьте тур и справочный центр для объяснения объема истории.
Каве
-6

Будет ли это так же просто, как предложить, например, функцию синуса?

Поскольку для данного входа и выхода вход может быть увеличен или уменьшен на 360 градусов (или на 2 пи, если вы находитесь в радианах), это много к одному, так что вы никогда не можете быть уверены, какой вход у вас был?

Скажите мне, если я неправильно понял вопрос.

Аарон Робсон
источник
4
Проверьте определение .
Каве
3
Вы смешиваете две концепции: односторонние функции и необратимые функции. Хотя функция синуса необратима, это не единственный способ. В частности, вы всегда можете придумать в прообраза (в любую точности вам нравится), даже если это не прообраз.
MS Dousti
Понятно, спасибо за объяснение различия.
Аарон Робсон