Конечная односторонняя перестановка с бесконечной областью

10

Пусть - перестановка. Обратите внимание, что хотя действует на бесконечной области, его описание может быть конечным. Под описанием я имею в виду программу, которая описывает функциональность . (Как и в колмогоровской сложности.) См. Пояснения ниже. π ππ:{0,1}{0,1}ππ

Например, функция NOT является одной такой перестановкой:

функция НЕ (х)
    Пусть у = х
    Для i = 1 до | x |
        Переверните немного й
    вернуть у

πk() , определенный ниже, является другим случаем:

функция pi_k (x)
    вернуть x + k (мод 2 ^ | x |)

Мой вопрос касается особого класса перестановок, называемых односторонними перестановками . Неформально говоря, это перестановки, которые легко вычислить, но трудно инвертировать (для машины ). Простое существование односторонних перестановок является давней открытой проблемой в криптографии и теории сложности, но в остальном мы будем предполагать, что они существуют.BPP

n=pqe=65537πn(x)=xemodn

Обратите внимание, что RSA определяется над конечной областью . Фактически, чтобы получить бесконечную перестановку областей, нужно рассмотреть семейство перестановок RSA , где - бесконечный набор целых чисел Блума. Обратите внимание, что - это описание семейства, и по определению оно бесконечно. { π n } n D DDZn{πn}nDDD

Мой вопрос (при условии существования односторонних перестановок):

Существуют ли односторонние перестановки конечного описания над бесконечной областью ?

Ответ может быть различным: он может быть положительным, отрицательным или открытым ( может быть положительным или отрицательным ).

Фон

Вопрос возник, когда я читал газету ASIACRYPT 2009 . Там автор неявно (и в контексте некоторых доказательств) предположил, что такие односторонние перестановки существуют.

Я буду счастлив, если это действительно так, хотя я не смог найти доказательств.

М.С. Дусти
источник
Разве мы не можем окончательно описать ? Существует конечный алгоритм, ищущий наименьшее число Блюма, большее некоторого входного числа, поэтому вычисление можно описать, например, как «найти наименьшее число Блюма большее , а затем вычислить ». Тем не менее, для меня не очевидно, что функция, которую вы получите путем склеивания некоторого бесконечного числа , обязательно будет перестановкой. Могли бы вы объяснить? π ( x ) b x π b ( x ) π bDπ(x)bxπb(x)πb
Каролина Солтыс
@Karolina: Спасибо за ответ. Я думаю, что алгоритм «найти наименьшее число Блюма больше, чем , затем вычислить » обязательно будет дополнительную информацию о , такую ​​как его факторизация. Следовательно, такой алгоритм не может быть использован для описания односторонних перестановок. Ты согласен? x π b ( x ) bbxπb(x)b
MS Dousti
Хорошо, я думаю, я понял - вы хотите, чтобы конечное описание описывало функцию простым способом вычисления. Я думаю, что мы могли бы закодировать часть "найти наименьшее число Блюма ...", не раскрывая никакой информации о (просто реализовать поиск brute-force для ), но тогда это не было бы эффективно вычислимо. бbb
Каролина Солтыс
Может быть, этот вопрос поможет с идеями: cstheory.stackexchange.com/questions/1378
Мэтт Грофф
@Matt: Спасибо. В этом вопросе условие «легко вычислить, но трудно инвертировать» не относится к машинам с ограниченным временем.
MS Dousti

Ответы:

14

В статье « О построении односторонних функций 1-1 » Гольдрайха, Левина и Нисана показано, как построить сохраняющие длину функции 1-1 с бесконечными областями и конечным описанием. Трудность инвертирования функций основана на распространенных предположениях, таких как сложность инвертирования RSA или нахождения дискретных логарифмов.

Их построение является поворотом простой идеи преобразования семейства односторонних функций в одну одностороннюю функцию путем установки где - это Случайность, используемая для выбора индексов и - это случайность, используемая для выбора входных данных (с учетом индекса ). f ( r , s ) = f i ( x ) r i s x i{fi}if(r,s)=fi(x)risxi

Проблема с вышеупомянутой идеей состоит в том, что не обязательно 1-1. Они исправляют эту проблему, слегка изменяя и утверждая, что при определенных условиях в семействе новая конструкция действительно 1-1. Затем они продолжают показывать, что эти условия удовлетворяются функциями, основанными на RSA / Discrete-log.f ( r , s ) { f i } if(r,s)f(r,s){fi}i

Алон Розен
источник
1
Спасибо Алон за твой отличный ответ. Не по теме: я очень рад видеть вас здесь. Мне нравятся ваши книги и статьи о параллельном нулевом знании !
MS Dousti
Thans, Sadeq. Рад слышать, что вам это нравится :-)
Алон Розен