Наблюдение, связанное с асимметричной криптографией, заключается в том, что некоторые функции (как полагают) легко выполнять в одном направлении, но трудно инвертировать. Кроме того, если существует некоторая информация о «ловушке», которая позволяет быстро вычислять обратную операцию, тогда проблема становится кандидатом в схему криптографии с открытым ключом.
Классические проблемы люка, ставшие известными RSA, включают в себя проблему факторинга и проблему дискретного журнала. Примерно в то же время, когда был опубликован RSA, Рабин изобрел криптосистему с открытым ключом, основанную на поиске дискретных квадратных корней (позже оказалось, что это по меньшей мере так же сложно, как и факторинг).
Другие кандидаты возникли за эти годы. KNAPSACK (вскоре после RSA), эллиптическая кривая «Логарифмы» с конкретными параметрами и задачи наименьшей основы решетки являются примерами проблем, чьи проблемы с ловушками используются в других опубликованных схемах. Также легко увидеть, что такие проблемы должны находиться где-то в NP.
Это исчерпывает мои знания о функциях люка. Также кажется, что исчерпан список в Википедии .
Я надеюсь, что мы сможем получить вики-список сообщества для языков, которые допускают люки и соответствующую литературу. Список будет полезен. Развивающиеся требования криптографии также изменяют, какие функции люка могут быть основой криптосистем. Взрыв хранилища на компьютерах делает возможными схемы с большими размерами ключей. Призрачный призрак квантовых вычислений лишает законной силы схемы, которые можно сломать оракулом для поиска скрытых абелевых подгрупп. Полностью гомоморфная криптосистема Джентри работает только потому, что мы обнаружили люк-функции, которые уважают гомоморфизмы.
Меня особенно интересуют проблемы, которые не являются NP-Complete.
Ответы:
Важно различать функции люка и шифрование с открытым ключом. В то время как функции ловушек действительно дают схемы шифрования с открытым ключом, известно, что некоторые из упомянутых вами кандидатов подразумевают только шифрование с открытым ключом и не обязательно предоставляют вам функции ловушки. На самом деле, Гертнер, Малкин и Рейнгольд показывают, что не существует «черного ящика» построения функции «люка» из «предиката люка» (которую можно рассматривать как однобитную схему шифрования с открытым ключом).
Классическими примерами люков являются функции RSA и Рабина. Классический пример предиката-люка - это определение квадратичной остаточности по модулю композита из-за Голдвассера и Микали. Упомянутые вами конструкции на основе дискретного журнала и решетки дают возможность шифрования с открытым ключом напрямую, без прохождения функций-ловушек.
Ниже приведен (не исчерпывающий) список конструкций схем шифрования с открытым ключом, большинство из которых, как известно, не выполняют функции-ловушки.
Криптосистема с открытым ключом Эль-Гамаля (включая варианты эллиптической кривой). Безопасность основана на предположении Диффи Хеллмана. Не проходит через функции люка (но см. Пункт Пейкерта-Уотерса ниже для функции люка, безопасность которой основана на семантической безопасности Эль-Гамаля).
[Тахер Эль Гамаль: криптосистема с открытым ключом и схема подписи на основе дискретных логарифмов. КРИПТО 1984: 10-18]
Айтай-Дворк, Регев. Безопасность основана на уникальном SVP в решетках. Не известно, чтобы подразумевать функции люка.
[Миклош Айтай, Синтия Дворк: Криптосистема с открытым ключом с эквивалентностью наихудшего / среднего случая. STOC 1997: 284-293]
[Одед Регев: Новые решетчатые криптографические конструкции. STOC 2003: 407-416]
Регев, Пейкерт. Безопасность основана на сложности обучения с ошибками (это включает сокращение от SVP). Не известно, чтобы подразумевать функции люка.
[Одед Регев: О решетках, обучении с ошибками, случайных линейных кодах и криптографии. STOC 2005: 84-93]
[Крис Пайкерт: Криптосистемы с открытым ключом из задачи наименьшего вектора в наихудшем случае: расширенная аннотация. STOC 2009: 333-342]
Пейкерт, Уотерс. Безопасность основана на решениях Диффи-Хеллмана и проблемах решетки. Известно, что подразумевает функции люка (через функции люка с потерями).
[Крис Пайкерт, Брент Уотерс: функции люков с потерями и их применение. STOC 2008: 187-196]
Любашевский, Паласио, Сегев. Безопасность основана на Subset-Sum. Не известно, чтобы подразумевать функции люка.
[Вадим Любашевский, Адриана Паласио, Гил Сегев: Криптографические примитивы с открытым ключом, обеспечивающие такую же безопасность, как и подмножество сумм. ТСС 2010: 382-400]
Штеле, Штайнфельд, Танака, Хагава и Любашевский, Пейкерт, Регев. Безопасность основана на твердости кольца LWE. Преимущество этих по сравнению с предыдущими предложениями заключается в их меньшем размере ключа. Не известно, чтобы подразумевать функции люка.
[Дэмиен Стеле, Рон Штайнфельд, Кейсуке Танака, Кейта Кагава: Эффективное шифрование с открытым ключом на основе идеальных решеток. ASIACRYPT 2009: 617-635]
[Вадим Любашевский, Крис Пейкерт, Одед Регев: Об идеальных решетках и обучении с ошибками над кольцами. ЕВРОКРИПТ 2010: 1-23]
источник