Криптография ФПМИ

Обновлённые условия задач к 11—12 семинарам

Условия задач к 11-му семинару

Готова первая домашняя работа. Всего 9 задач, в зачёт идут 4 лучших задачи из первых 5 (про односторонние функции) и 3 лучших задачи из следующих 4 (про генераторы и семейства псевдослучайных функций). Срок - 3 недели.

Условия задач к 10-му семинару

Условия задач к 9-му семинару

Решения задач 6—8 семинаров

Решения задач 5-го семинара

Условия задач к 7-му семинару

📢 Лекция Льва Суханова в это воскресенье, 22 октября, в 17:00

Лев Суханов - выпускник матфака ВШЭ и исследователь в PSE, Ethereum Foundation. Он расскажет про очень важную область криптографии, в которой он работает - быстрые проверки доказательств.

🔍 Верифицируемые вычисления при помощи sumcheck-протокола

📝 Давайте рассмотрим следующую ситуацию: Алиса посчитала на известных публичных данных X функцию f(X), и хочет убедить Боба в том, что ответ, который она говорит - правильный. Боб, однако, ограничен в вычислительных ресурсах, и не хочет повторять всё вычисление Алисы.

Выясняется, что (при условии что Боб допускает небольшую вероятность ошибки, скажем $2^{-128}$), такую задачу можно решить намного быстрее. Такую постановку вопроса называют "снарк" (succinct non-interactive arguments of knowledge).

Я расскажу про довольно старый протокол из 90х - sumcheck (проверка суммы), в последние год-два получивший второе дыхание в контексте делегированных вычислений и блокчейна, и построенный на этом аргументе протокол GKR (Голдвассер-Калаи-Ротблюма).

Пререквизиты: знать что такое конечное поле и уметь раскрывать скобки, если дойдём до приложений то ещё понадобится (наверное) знать что такое хэш

⏰ Начало в 17:00 МСК. Обратите внимание на необычное время!!!

📌 Ссылка на зум. Чтобы получать наши анонсы, зарегистрируйтесь в боте (инструкция).

#открытые_лекции #анонс

Завтра в 17:00 будет публичная онлайн-лекция на интересную тему от моего знакомого. Кому интересно, присоединяйтесь, анонс и ссылка ниже в посте.

Условия задач к 6-му семинару

Завтра лекция состоится, несмотря на мою командировку. Её прочтёт Илья Степанов. Семинара в группе ТиПИ не будет.

Условия задач к пятому семинару

Решения задач 3-го и 4-го семинаров

Условия задач к третьему и четвёртому семинарам

Решения задач второго семинара