Односторонние перестановки без люка

9

Вкратце: если предположить, что существуют односторонние перестановки , можем ли мы создать такую, которая не имеет люка?

Больше информации:

Односторонняя перестановка - это перестановка πкоторый легко вычислить, но трудно инвертировать (см. вики-тег с односторонним действием для более формального определения). Обычно мы рассматриваем семейства односторонней перестановки,π={πn}nNгде каждый πnодносторонняя перестановка, действующая в конечной областиDn, Люк односторонний перестановка , как определена выше, за исключением того, что существует множество секрета{tn}nN и алгоритм инверсии времени Iтак, что для всех n, |tn|poly(n), а также I может инвертировать πn при условии, что это дано tn,

Я знаю односторонние перестановки, которые генерируются так, что невозможно найти люк (но люк существует). Пример, основанный на предположении RSA, приведен здесь . Вопрос в том,

Существуют ли (семейства) односторонних перестановок, у которых нет люка (набора)?

Редактировать: (больше формализации)

Предположим, что существует некоторая односторонняя перестановка π с (бесконечной) областью D{0,1}, То есть существует вероятностный алгоритм за полиномиальное времяD (который на входе 1n, вызывает некоторое распределение по Dn=0,1nD), что для любого полиномиального времени противника A, Любые c>0и все достаточно большое целое число n:

Pr[xD(1n):A(π(x))=x]<nc

(Вероятность принимается за внутренние броски монет и \ mathcal {A} .)DA

Вопрос в том, можем ли мы построить однонаправленную перестановку , для которой существует вероятностный алгоритм за полиномиальное время такой, что для любого многоразмерного семейства цепей , любое и достаточно большое целое число :πD A={An}nNc>0n

Pr[xD(1n):An(π(x))=x]<nc

(Вероятность принимается за внутренние броски монет , поскольку является детерминированным.)DA

М.С. Дусти
источник
Похоже, вам нужен OWP, который остается односторонним, даже если вы получите многозначный совет. Между прочим, мы обычно не определяем семейства OWP как этот - см. Goldreich Vol 1, определения 2.4.4 и 2.4.5.
Дэвид Кэш
@ Дэвид: Да, я знаю, что это не обычное определение, но я чувствовал, что формальное определение (то, которое появляется в книге Гольдрайха) слишком длинное для этого обсуждения.
MS Dousti
@ Садек: Достаточно справедливо, но я думаю, что изменение определений здесь будет значительным. Что бы это ни стоило, я пытался думать о подобном типе безопасности (без люков) раньше. Казалось, что хорошее определение - разрешить неограниченную обработку семейного индекса для выработки рекомендаций до эксперимента с инверсией.
Дэвид Кэш
@ Давид: посмотреть, удовлетворяет ли отредактированная часть необходимости дальнейшей формализации.
MS Dousti
1
@Sadeq: Определение того, подразумеваются ли односторонние перестановки в люках односторонними перестановками или нет (хотя даже неясно, что означают последние, поскольку они оба могут существовать), является одной из самых больших открытых проблем в теории криптографии. , Импальяццо и Рудич ( cseweb.ucsd.edu/~russell/secret.ps ) доказали, что этого нельзя достичь с помощью методов «черного ящика», а современные методы, как известно, не обходят их разделение.
Алон Розен

Ответы:

7

Рассмотрим следующие случаи:

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. Было показано, что он не содержит конструкций / сокращений черного ящика и открыт в целом (см. Мой комментарий в ветке выше).

Алон Розен
источник
+1, спасибо. Дэвид приложил много усилий, чтобы ответить, и я ему очень благодарен; но это ответ на то , что я имел в виду.
MS Dousti
2
Я думал, что вопрос был: (а) возможно. Криптографически, если у каждого OWP есть люк, вы не можете доверять тому, кто дает вам OWP, чтобы он тоже не знал люка. Конечно, вы можете взять его OWP и составить его со своим собственным OWP, для которого только вы знаете люк, и получить OWP, для которого ни одна из сторон не знает люка.
Питер Шор
1
@ Питер: Да. Композиция, кажется, делает работу. Другой вариант - использовать забывающую передачу (которая, если (а) имеет место, как известно, существует - по модулю некоторых мелких тонкостей). Используя OT, игроки могут создать безопасный двухсторонний вычислительный протокол, который позволяет одному из них учиться f, не изучая люка, а другому - ничего не изучать. Но ваше решение действительно проще.
Алон Розен
7

Я не знаю о конструкциях из общих предположений, но вы можете получить правдоподобного кандидата для «односторонней перестановки без люка», используя дискретный лог по модулю простого числа . То есть, пусть примитивный корень по модулю и определим . Тогда - это перестановка целых чисел от до , и обычно предполагается, что она односторонняя. Для части «без люка», я полагаю, вам нужно точно определить, что это значит, но, насколько я знаю, у нас нет никакого способа настроить вещи для включения инверсии. (Если бы мы это сделали, то в криптографии было бы много всяких классных (позитивных) приложений!)pgpπ(x)=gxmodpπ1p1

Дэвид Кэш
источник
+1. Спасибо за ответ. Вы предполагаете твердость дискретного журнала против неоднородных противников. Мой вопрос: если предположить простое существование односторонних перестановок, можем ли мы построить такой, у которого нет люка?
MS Dousti
@ Садек: Разве существование односторонних перестановок не подразумевает твердость дискретного журнала, так как P = NP?
Мохаммад Алагган
@Alaggan: я так не думаю. Может случиться так, что существуют односторонние перестановки, но кто-то придумает эффективный алгоритм для инвертирования дискретного журнала.
MS Dousti
@ Садек: Это если P = BQP! = NP.
Мухаммед Алагган
@ Садек: Правильно, или я все понял?
Мухаммед Алагган