Я читал в нескольких статьях, что существование односторонних функций широко распространено. Может кто-то пролить свет на то, почему это так? Какие у нас аргументы в пользу существования односторонних функций?
25
Я читал в нескольких статьях, что существование односторонних функций широко распространено. Может кто-то пролить свет на то, почему это так? Какие у нас аргументы в пользу существования односторонних функций?
Ответы:
Вот аргумент, что односторонние функции должно быть трудно инвертировать. Предположим, есть класс проблем 3-SAT с посаженными решениями, которые трудно решить. Рассмотрим следующую карту:
где - любая строка битов, - строка битов (вы можете использовать их для заполнения генератора случайных чисел, или вы можете запросить столько случайных битов, сколько вам нужно), а - это проблема -SAT, имеющая как посаженное решение, где генератор случайных чисел точно определяет, какую задачу -SAT вы выберете. Чтобы инвертировать эту одностороннюю функцию, вам нужно решить проблему -SAT с помощью посаженного решения.р с к х к кИкс р s К Икс К К
Этот аргумент показывает, что инвертировать одностороннюю функцию так же сложно, как решить проблемы -SAT с посаженными решениями. А поскольку -SAT является NP-полной задачей, если вы можете выяснить, как создавать сложные экземпляры с посаженными решениями для любой NP-задачи, вы можете внедрить решения в формулах -SAT.к кК К К
Не было доказано, что можно придумать класс NP-полных задач с посаженными решениями, которые столь же сложны, как и произвольные NP-полные задачи (и даже если это правда, это будет невероятно сложно доказать) , но люди определенно знают, как внедрять решения проблем -SAT способами, которые в настоящее время никто не знает, как их решать.К
ДОБАВЛЕНО: теперь я понимаю, что эта связь уже была дана (более подробно) в Абади, Аллендере, Бродере, Фейгенбауме и Хемачандре ; они указывают на то, что односторонние функции могут дать решаемые сложные экземпляры SAT, и наоборот.
Если говорить более неформально, отсутствие односторонних функций показывает, что по-настоящему сложных головоломок не может быть. Если есть тип головоломки, где кто-то может придумать и головоломку, и ее решение алгоритмически, то есть также алгоритм полиномиального времени для нахождения решения головоломки. Это кажется мне очень нелогичным. Конечно, полиномиальный разрыв может существовать; может случиться так, что если для создания головоломки потребовалось шагов, то для ее решения может потребоваться шагов. Однако моя интуиция говорит, что должен быть суперполиномиальный разрыв. O ( n 3 )N O ( n3)
источник
Я дам краткий ответ: существование, казалось бы, трудных проблем, таких как FACTORING или DISCRETE LOG, заставило теоретиков поверить в существование OWF. В частности, они десятилетиями (с 1970-х годов) пытались найти эффективные (вероятностные полиномиальные) алгоритмы для таких задач, но ни одна попытка не увенчалась успехом. Это рассуждение очень похоже на то, почему большинство исследователей считают, что P ≠ NP.
источник
Аргумент Сашо опирается на вечную проблему P = NP, для которой в настоящее время нет единого мнения.
Однако, если мы будем следовать криптоанализу Шеннона одноразовых блокнотов, рассекреченных в 1947 г., то есть: не существует математически безопасного алгоритма шифрования, кроме одноразового блокнота. Его аргумент основан на идее, что, если мы имеем действительно случайную последовательность чисел и для некоторой последовательности для шифрования, s 1 , s 2 , s 3 , … , s п , мы шифруем следующим образом:р1, г2, г3, … , ГN s1, с2, с3, ... , SN
Мы могли бы имитировать результат Шеннона для односторонних функций.
Суть в том, что мы не знаем, существуют ли действительно случайные числа, поскольку этот вопрос эквивалентен комментарию Эйнштейна «Бог не играет в кости».
Однако для всех целей генератор случайных чисел, основанный на физическом процессе, считается экспертом достаточно случайным.
источник
Будет ли это так же просто, как предложить, например, функцию синуса?
Поскольку для данного входа и выхода вход может быть увеличен или уменьшен на 360 градусов (или на 2 пи, если вы находитесь в радианах), это много к одному, так что вы никогда не можете быть уверены, какой вход у вас был?
Скажите мне, если я неправильно понял вопрос.
источник