Я читал в нескольких статьях, что существование односторонних функций широко распространено. Может кто-то пролить свет на то, почему это так? Какие у нас аргументы в пользу существования односторонних...
Можно ли преобразовать CNF в другой CNF такой, чтобыCC\mathcal CΨ(C)Ψ(C)\Psi(\mathcal C) Функция может быть вычислена за полиномиальное время из некоторого секретного случайного параметра .ΨΨ\Psirrr Ψ(C)Ψ(C)\Psi(\mathcal C) имеет решение тогда и только тогда, когда имеет решение.CC\mathcal C Любое...
Функция f:{0,1}∗→{0,1}∗f:{0,1}∗→{0,1}∗f \colon \{0, 1\}^* \to \{0, 1\}^* является односторонней, если fff может быть вычислена с помощью алгоритма полиномиального времени, но для каждого рандомизированного алгоритма полиномиального времени AAA,...
Неформально односторонние функции определены в отношении алгоритмов PTIME. Они вычислимы за полиномиальное время, но не обратимы в полиномиальное время среднего случая. Существование таких функций является важной открытой проблемой в теоретической информатике. Я заинтересован в односторонних...
Существует старая хитрость для записи алгоритма, который, если P = NP, решает SAT за полиномиальное время. По сути, каждый перечисляет все полиномиальные машины времени и многозадачность над ними. Есть ли аналогичная уловка для односторонних функций (или даже односторонних люков)? То есть, можем ли...
Пусть - перестановка. Обратите внимание, что хотя действует на бесконечной области, его описание может быть конечным. Под описанием я имею в виду программу, которая описывает функциональность . (Как и в колмогоровской сложности.) См. Пояснения ниже. π ππ:{0,1}∗→{0,1}∗π:{0,1}∗→{0,1}∗\pi \colon...
Мой вопрос касается эквивалентности безопасности различных односторонних функций-кандидатов, которые могут быть построены на основе сложности факторинга. Предполагая проблему ФАКТОРИНГ: [Дано для случайных простых чисел , найти , ]P , Q < 2 n P QN=PQN=PQN = PQP,Q<2nP,Q<2nP, Q < 2^nPPPQQQ...
Если OWF существуют, то возможна статистически обязательная фиксация битов. [1] Известно ли, что если существуют OWF, то возможно обязательное согласование битов? Если нет, существует ли известное разделение черного ящика между ними? [1] http://en.wikipedia.org/wiki/Pseudorandom_generator_theorem и...
Вкратце: если предположить, что существуют односторонние перестановки , можем ли мы создать такую, которая не имеет люка? Больше информации: Односторонняя перестановка - это перестановка ππ\piкоторый легко вычислить, но трудно инвертировать (см. вики-тег с односторонним действием для более...
Хорошо известно, что наличие односторонних функций необходимо и достаточно для большей части криптографии (цифровые подписи, псевдослучайные генераторы, шифрование с закрытым ключом и т. Д.). Мой вопрос: каковы теоретико-сложные последствия существования односторонних функций? Например, OWF...