Вкратце: если предположить, что существуют односторонние перестановки , можем ли мы создать такую, которая не имеет люка?
Больше информации:
Односторонняя перестановка - это перестановка который легко вычислить, но трудно инвертировать (см. вики-тег с односторонним действием для более формального определения). Обычно мы рассматриваем семейства односторонней перестановки,где каждый односторонняя перестановка, действующая в конечной области, Люк односторонний перестановка , как определена выше, за исключением того, что существует множество секрета и алгоритм инверсии времени так, что для всех , , а также может инвертировать при условии, что это дано ,
Я знаю односторонние перестановки, которые генерируются так, что невозможно найти люк (но люк существует). Пример, основанный на предположении RSA, приведен здесь . Вопрос в том,
Существуют ли (семейства) односторонних перестановок, у которых нет люка (набора)?
Редактировать: (больше формализации)
Предположим, что существует некоторая односторонняя перестановка с (бесконечной) областью , То есть существует вероятностный алгоритм за полиномиальное время (который на входе , вызывает некоторое распределение по ), что для любого полиномиального времени противника , Любые и все достаточно большое целое число :
(Вероятность принимается за внутренние броски монет и \ mathcal {A} .)
Вопрос в том, можем ли мы построить однонаправленную перестановку , для которой существует вероятностный алгоритм за полиномиальное время такой, что для любого многоразмерного семейства цепей , любое и достаточно большое целое число :
(Вероятность принимается за внутренние броски монет , поскольку является детерминированным.)
источник
Ответы:
Рассмотрим следующие случаи:
1) Односторонние перестановки (OWP) существуют, но перестановок ловушек (TDP) нет (то есть мы находимся в варианте «мини- криптованного » мира Импальяццо ). В этом случае вы просто берете OWP, который гарантированно существует, и вы знаете, что у него нет люка.
2) Существуют как OWP, так и TDP. Здесь у вас есть два варианта:
(a) Каждый OWP имеет алгоритм генерации ключей G, который выводит «публичное» описание функции f вместе с выбранной ловушкой t. В этом случае рассмотрим модифицированную генерацию ключей, которая выводит только f. Это дает вам OWP, и, кроме того, невозможно найти t при заданном f (так как в противном случае у вас есть эффективный способ инвертировать f). Это также должно выполняться для неоднородного варианта.
(b) Существует OWP f, такой, что никакой алгоритм G не может вывести как f, так и t, так что t допускает инверсию f (x) для случайного x. В этом случае f - OWP, у которого нет люка.
Один из комментариев в приведенной выше ветке, кажется, наводит на мысль, что вы на самом деле задаетесь вопросом: известно ли, что существование OWP подразумевает существование TDP. Было показано, что он не содержит конструкций / сокращений черного ящика и открыт в целом (см. Мой комментарий в ветке выше).
источник
Я не знаю о конструкциях из общих предположений, но вы можете получить правдоподобного кандидата для «односторонней перестановки без люка», используя дискретный лог по модулю простого числа . То есть, пусть примитивный корень по модулю и определим . Тогда - это перестановка целых чисел от до , и обычно предполагается, что она односторонняя. Для части «без люка», я полагаю, вам нужно точно определить, что это значит, но, насколько я знаю, у нас нет никакого способа настроить вещи для включения инверсии. (Если бы мы это сделали, то в криптографии было бы много всяких классных (позитивных) приложений!)p g p π(x)=gxmodp π 1 p−1
источник