Пусть - перестановка. Обратите внимание, что хотя действует на бесконечной области, его описание может быть конечным. Под описанием я имею в виду программу, которая описывает функциональность . (Как и в колмогоровской сложности.) См. Пояснения ниже. π π
Например, функция NOT является одной такой перестановкой:
функция НЕ (х) Пусть у = х Для i = 1 до | x | Переверните немного й вернуть у
, определенный ниже, является другим случаем:
функция pi_k (x) вернуть x + k (мод 2 ^ | x |)
Мой вопрос касается особого класса перестановок, называемых односторонними перестановками . Неформально говоря, это перестановки, которые легко вычислить, но трудно инвертировать (для машины ). Простое существование односторонних перестановок является давней открытой проблемой в криптографии и теории сложности, но в остальном мы будем предполагать, что они существуют.
Обратите внимание, что RSA определяется над конечной областью . Фактически, чтобы получить бесконечную перестановку областей, нужно рассмотреть семейство перестановок RSA , где - бесконечный набор целых чисел Блума. Обратите внимание, что - это описание семейства, и по определению оно бесконечно. { π n } n ∈ D DD
Мой вопрос (при условии существования односторонних перестановок):
Существуют ли односторонние перестановки конечного описания над бесконечной областью ?
Ответ может быть различным: он может быть положительным, отрицательным или открытым ( может быть положительным или отрицательным ).
Фон
Вопрос возник, когда я читал газету ASIACRYPT 2009 . Там автор неявно (и в контексте некоторых доказательств) предположил, что такие односторонние перестановки существуют.
Я буду счастлив, если это действительно так, хотя я не смог найти доказательств.
Ответы:
В статье « О построении односторонних функций 1-1 » Гольдрайха, Левина и Нисана показано, как построить сохраняющие длину функции 1-1 с бесконечными областями и конечным описанием. Трудность инвертирования функций основана на распространенных предположениях, таких как сложность инвертирования RSA или нахождения дискретных логарифмов.
Их построение является поворотом простой идеи преобразования семейства односторонних функций в одну одностороннюю функцию путем установки где - это Случайность, используемая для выбора индексов и - это случайность, используемая для выбора входных данных (с учетом индекса ). f ( r , s ) = f i ( x ) r i s x i{fi}i f(r,s)=fi(x) r i s x i
Проблема с вышеупомянутой идеей состоит в том, что не обязательно 1-1. Они исправляют эту проблему, слегка изменяя и утверждая, что при определенных условиях в семействе новая конструкция действительно 1-1. Затем они продолжают показывать, что эти условия удовлетворяются функциями, основанными на RSA / Discrete-log.f ( r , s ) { f i } if(r,s) f(r,s) {fi}i
источник