Криптография без допущений - ищет обзор

25

Предположим, что и быстрый линейный алгоритм времени для SAT появится завтра. Внезапно RSA становится небезопасным, большая часть нашей современной системы связи сломана, и мы должны пересмотреть, как хранить секреты друг от друга.пзнак равноNп

Вопрос: Существует ли хороший единый справочник (или краткий список), чтобы получить общее представление о том, что возможно в крипто (и в смежной области «безопасности») без предположений о неразрешимости? Это могло бы спасти цивилизацию в один прекрасный день, а также было бы неплохо изучить в то же время.

Обсуждение: Большинство криптографических задач, которые мы сейчас изучаем (OWF, PRG, PKE), невозможно доказать в мире (мир, названный «Algorithmica» во влиятельном эссе Impagliazzo), но некоторые вещи остаются возможными: общение с одноразовый блокнот ; распределенный секретный обмен ; поиск личной информации ; и некоторые другие приятные вещи. (Некоторые виды физических механизмов, таких как запертые блоки , устройства, реализующие забытую передачу , и квантовые состояния также могут пригодиться. Конечно, всегда есть какое-то физическое предположение о том, кто может видеть какую информацию.)пзнак равноNп

Можно провести различие между теоретико-информационной безопасностью (которая работает против неограниченного в вычислительном отношении противника) и «безусловной» безопасностью (которая может потребовать ограниченного противника, но все же демонстрирует безопасность без каких-либо недоказанных предположений). Меня больше всего интересует теоретико-информационный случай.

Для начала приведу одну библиографию теоретико-информационной безопасности (которая для моих целей неуправляемо длинна и несопоставима).

Энди Друкер
источник
Хороший вопрос, на самом деле это не ответ, но он может представлять интерес. У Альфреда Менезеса и Нила Коблица есть замечательная серия статей «Другой взгляд», где они задают некоторые вопросы, аналогичные вашим, но также и целое направление «модели безопасности». Я кратко обсудил это в этом ответе , но я не уверен, слишком ли это применимо к подходу.
Артем Казнатчеев
3
Я подозреваю, что такой алгоритм SAT можно использовать сам, чтобы найти альтернативы существующим PKC и безусловно безопасным системам.
T ....
Обратите внимание, что RSA не является NP-Complete, поэтому требование P = NP для коэффициента может быть чрезмерным.
user834
большая часть современной криптографии основывается на предположениях о неразрешимости не для упрощения / удобства, а потому, что в теории сложности нет лучших результатов / доказуемых пределов (особенно сложность среднего случая) ... см. также crypto.se
vzn
3
Вот обзор по Ули Маурер , который, хотя и немного устарели, является весьма информативным: ftp.inf.ethz.ch/pub/crypto/publications/Maurer99.pdf

Ответы:

16

Ключевыми фразами, которые вы, вероятно, ищете, являются «теоретико-информационная криптография» и «квантовая криптография». Поиски литературы по этим темам приведут к большой работе, которую вы ищете. Некоторые примеры выделяются ниже:

  • Для конфиденциальности: одноразовый блокнот, канал прослушивания Wyner, обмен секретными данными, обмен квантовыми ключами и т. Д.

  • Для целостности и аутентификации: универсальные хеш-функции.

  • Для анонимности: анонимное общение (например, сети постоянного тока, схемы на основе лука, p2p-сети, основанные на быстром смешивании случайных блужданий), протоколы ограничения расстояния.

  • Для безопасности, основанной на физических предположениях: PUF (физически не клонируемые функции), коды целостности (Capkun и др.), Квантовая криптография, безопасность с использованием TPM или защищенного от несанкционированного доступа оборудования.

Есть много статей на эти темы; слишком много, чтобы обобщить все результаты в литературе.

DW
источник
Благодаря DW, я знаю, что слишком много оснований, чтобы подвести итог в ответе; Я надеюсь найти полезные книги или обзоры.
Энди Друкер
@AndyDrucker, я бы порекомендовал вам ознакомиться с оригинальными или современными статьями на интересующие вас темы. Я не уверен, что вы найдете книгу, которая охватывает всю работу в этой области (некоторые из которых произошли за последние 5-10 лет). Даже если вам повезет и вы обнаружите какую-то книгу, к тому времени, когда она появится на книжных полках, она начнет отставать от последней исследовательской литературы.
DW
2
Я даже не стремлюсь к современному состоянию. Нет действительно современного учебника для любой области TCS; Тем не менее, все еще можно взять книги Голдрайха и ориентироваться на фундаментальные результаты и концепции криптографии на основе сложности. Я задавался вопросом, появилось ли что-нибудь подобное для теоретико-информационной стороны.
Энди Друкер
4

Это довольно сложный вопрос, так как у нас действительно нет хорошего обзора области. Частично это связано с тем, что информационная теория и крипто-сообщество работали над похожими темами, не взаимодействуя друг с другом. Много хороших моментов было дано выше. Я просто хотел бы добавить несколько дополнительных замечаний:

  • У нас был большой объем работ, посвященных проблеме согласования секретного ключа (и безопасной связи) с заданной настройкой. Здесь настройка означает, например, что стороны в системе (скажем, Алиса, Боб и противник Ева) обмениваются некоторой коррелированной информацией, поступающей из трехстороннего распределения вероятностей. Альтернативная установка может состоять из шумных каналов (например, Алиса может отправлять информацию Бобу и Еве по шумным каналам). Кроме того, Алиса и Боб связаны через канал связи (который может или не может быть аутентифицирован). Это направление работы началось с Аарона Уайнера в 70-х годах, который представил модель канала Wiretap, и был дополнительно очищен Маурером и другими в 90-х годах. Кроме того, множество методов в этой области (усиление конфиденциальности, согласование информации) в конечном итоге использовалось в настройке Quantum Key-Distribution (QKD). На сегодняшний день здесь проделана значительная работа, например, в смежных областях, таких как не подверженные кованию экстракторы и т. Д. Модель ограниченного хранения также является параметром, который отличается от вышеупомянутого, но использует аналогичные методы и имеет аналогичные цели.

  • Помимо просто секретного обмена, вы найдете большое количество работ по теоретически защищенным многопартийным вычислениям (MPC). В частности, направление работ, инициированное протоколом BGW, является полностью теоретическим.

  • Кроме того, я не уверен, насколько далеко заходит вопрос: если, например, P = NP действительно имеет место, но мы можем как-то оправдать присутствие случайного оракула в небе, то симметричная криптография все еще возможна. Иногда такие модели действительно используются для доказательства безопасности определенных криптографических конструкций (таких как хэш-функции или блочные шифры), и эти методы являются полностью теоретико-информационными.

  • Теоретико-информационные методы в криптографии также часто выступают в качестве промежуточного инструмента в теоретических результатах сложности, но я думаю, что это выходит за рамки вопроса. (См. Работу Маурера по случайным системам и усилению неразличимости в качестве примера такого типа работы.)

Стефано Тессаро
источник
«мы можем как-то оправдать присутствие случайного оракула в небе», что вы именно здесь говорите? Как здесь возможна симметричная крипта с открытым ключом?
T ....
1
@JA Я полагаю, он имеет в виду модель случайного оракула Беллара и Рогэвея , см., Например, cseweb.ucsd.edu/~mihir/papers/ro.html . Эта модель эвристическая, часто полезная, но есть веские причины для скептицизма: arxiv.org/abs/cs/0010019
Сашо Николов
ic .. что именно здесь происходит? у вас есть идея на конкретном уровне? Все теоретико-информационные симметричные схемы ключей, которые я видел, основаны на извлечении общей информации из коррелированных и, следовательно, возможно, не могут быть превращены в версию с открытым ключом. Есть ли здесь фундаментальная идея, которая делает возможным криптографическое решение с открытым ключом, теоретически безопасное для информации?
T ....
2
Позвольте мне уточнить: в модели случайного оракула, где все стороны имеют доступ к случайному RO оракула, честные стороны, обладающие секретным ключом SK, могут надежно зашифровать сообщение M как (R, M + RO (SK || R)), где R - случайность шифрования (и заново генерируется при каждом шифровании), + обозначает побитовый xor (здесь предполагается, что выходная длина RO равна длине сообщения). Безопасность этой схемы зависит только от случайного оракула. Напротив, из работы Impagliazzo и Rudich известно, что шифрование с открытым ключом недостижимо в модели случайного оракула.
Стефано Тессаро
3

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

В связи с вышеупомянутым направлением работы, некоторые места, на которые вы, возможно, захотите взглянуть, это кандидатская диссертация Кристиана Качина и также Ренато Реннер (более квантовый).

Конечно, есть совершенно другой подход с ключевыми словами, включая BB84, Preskill-Shor, Артур Экерт и т. Д.

Выше, конечно, только отражает мой ограниченный опыт, и, конечно, есть еще много подходов и интересных направлений работы.

Мухаммед Баварский
источник