Мотивирующие разговоры об основах криптографии

10

Этот вопрос в том же духе, что и вдохновляющие разговоры для учеников старших классов . Мой доктор философии консультант попросил меня дать вдохновляющую лекцию для нового M.Sc. студенты. Предмет - основы криптографии , которая лучше всего иллюстрируется книгой Гольдрайха . Беседа займет около часа, и я хочу познакомить студентов с основными конструкциями (такими как односторонние функции / перестановки, псевдослучайные генераторы, доказательства с нулевым разглашением, схемы шифрования / подписи и т. Д.), А также решить и нерешенные проблемы на местах.

Я хочу, чтобы разговор был очень мотивирующим . Основная проблема двоякая:

  1. Основы криптографии требуют очень хорошего понимания теории сложности вычислений . Увы, магистр наук студенты не прошли ни одного курса, связанного с этой теорией.
  2. Мне нужно представить некоторые проблемы в качестве возможных тем для M.Sc. Тезис. Хотя в этой области существует много нерешенных проблем, большинство из них слишком сложны для магистратуры. студент.

Предложения приветствуются. Кроме того, меня очень интересуют указатели на подобные разговоры.


Изменить: я нашел список студентов Голдрайха чрезвычайно вдохновляющим. Я буду искать другие подобные списки, но вы можете помочь мне, если знаете какие-либо подобные списки. См. Также: Демистификация магистерской диссертации и исследование в целом: история некоторых магистерских диссертаций .

М.С. Дусти
источник

Ответы:

12

Поскольку вы не можете полагаться на знание теории сложности, вы должны подчеркнуть изменение парадигмы от безопасности к неясности к безопасности от неразрешимости, высказывая мысль о том, что некоторые проблемы трудно решить эффективно. Это, конечно, устраняет многие проблемы, связанные с мирами непостижимости Impagliazzo, но дает представление о том, как работает современная криптография.

для ZKP, которые действительно потрясающие, есть много способов донести основные идеи интуитивно. Посмотрите, например, мой ответ на МО , а также веселую историю Али-Бабы и 40 воров . Хотя они изначально были предназначены для молодой аудитории, они хорошо работают в любом возрасте, чтобы передать правильную интуицию.

Суреш Венкат
источник
@Suresh: Большое спасибо. Есть идеи по второму вопросу (мотивация нерешенных проблем на уровне магистратуры)?
MS Dousti
1
Две ссылки одинаковы.
Цуёси Ито
это сложно. Есть не так много проблем, которые можно решить на этом уровне, не зная сложности.
Суреш Венкат
@Suresh: Да, это была моя проблема с тех пор, как я начал говорить на эту тему. Во всяком случае, я должен идти на компромиссы; так что вы можете смело предполагать, что люди как-то хорошо понимают сложность! Тогда, как я могу дать им мотивационные проблемы для M.Sc. Тезис?
MS Dousti
Я очень мало знаю о крипто, так что :(. В геометрии есть хороший список открытых проблем. Возможно, вам следует просмотреть список открытых вопросов, который был опубликован здесь некоторое время назад.
Суреш Венкат
4

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

Я бы предложил (немного) более прикладную направленность на линии книги Каца-Линделла.

user686
источник