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

#дневниклекций
Краткое содержание прошлой и сегодняшней лекций:
- Односторонние перестановки с секретом (точнее, их семейства). Определение через 4 вероятностных алгоритма: генератор ключей, сэмплер, вычислитель и обратитель. Генератор возвращает пару (индекс, секрет), сэмплер возвращает случайный элемент области определения, вычислитель вычисляет перестановку, обратитель обращает при известном секрете. Определение труднообратимости без знания секрета.
- Примеры предположительно односторонних перестановок с секретом на базе функций Рабина и RSA.
- Общая идея, как используются односторонние перестановки с секретом в асимметричной криптографии.
- Понятие о генераторах случайных чисел. Генераторы истинной случайности и псевдослучайности. Борьба генераторов и тестов случайности. Улучшение качества случайности при помощи экстракторов.
- Виды близости случайных величин (точнее, их последовательностей - ансамблей). Статистическое расстояние между величинами и 2 его определения. Статистическая близость и её эквивалентность неотличимости никакими тестами. Вычислительная неотличимость (неотличимость простыми тестами). Всё это - отношение эквивалентности.
- Формальное определение ГПСЧ. Теорема: если существуют ГПСЧ, то существуют односторонние функции (например, сам ГПСЧ).
- Обратная теорема: если существуют односторонние функции, то существуют ГПСЧ (б/д). Более простая версия: если существуют односторонние перестановки, то существуют ГПСЧ.
- Общая конструкция доказательства: построение односторонней перестановки с трудным битом, построение из неё генератора n->n+1, построение генератора n->p(n)
- Формальное определение трудного бита.
- Вторая часть теоремы (XOR-лемма Яо): если g - односторонняя перестановка, а h - трудный бит, то G(x)=g(x)h(x) - генератор. Доказательство через преобразование отличителя строк в предсказатель последнего бита.
- Третья часть теоремы: итерация предыдущей конструкции. Построение генератора n->n+2: G(x)=g(g(x))h(g(x))h(x). Построение гибридного генератора, доказательство неотличимости нашего от гибридного, а гибридного от случайной строки. Обобщение на полиномиальную длину, некорректность рассуждения по транзитивности и его исправление.

В следующий раз докажем первую часть теоремы и поговорим про псевдослучайные функции.

Система оценивания

Мы обсудили и решили, что система оценивания будет такой:

- Для курса по выбору (экзамен):
25% - домашние задания. Будет две домашки по задачам, также по желанию можно часть из них заменить на практический проект
25% - промежуточная контрольная aka мидтерм (ориентировочно конец октября)
50% - устный экзамен (нужно сдать хотя бы на 3 из 10 для закрытия курса)

- для ДМ и ПМИ.Инф (дифзачёт):
30% - домашние задания (аналогично курсу по выбору можно сделать практический проект вместо части задач)
30% - промежуточная контрольная (мидтерм)
40% - итоговая контрольная (файнал). Не блокирующая, но нужно сдать хотя бы на 20 баллов для оценки отл (задачи будут оцениваться от 5 до 15 баллов).

Веса условные, всюду можно будет набрать немного больше максимума. Точные пороги на оценки объявим ближе к концу семестра.

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

#дневниклекций
Сегодня на лекции прошли вот что:
- Напоминание: сильно и слабо односторонние функции
- Умножение как предположительно односторонняя функция. Обсуждение, почему её слабая односторонность следует только из предположения о сложности разложения на простые, а сильной может не быть. (Я сомневался, и действительно: на самом деле числа с маленькими делителями занимают экспоненциально малую часть всех чисел, так что алгоритма, раскладывающего даже обратно полиномиальную долю всех чисел, неизвестно. То есть умножение предположительно именно сильно односторонняя. Но это куда более сложные оценки).
- Теорема об усилении: если существует слабо односторонняя функция, то существует и сильно односторонняя.
- Конструкция усиления через параллельное повторение, её устойчивость против наивных обратителей.
- Принцип настоящего доказательства: если новую функцию можно обратить с существенной вероятностью, то исходную с почти единичной.
- Обсуждение идей, как можно построить обратитель старой функции из обратителя новой. Описание конструкции: подставляем аргумент на разные позиции, остальное заполняем случайными, пытаемся обратить, проверяем успешность и так много раз (амплификация).
- Доказательство корректности конструкции: разделение аргументов на простые и сложные, две леммы о вероятности успеха нового обратителя и ошибки старого, подбор параметров, чтобы получилось противоречие.
- Односторонние перестановки. Неизвестность их существования в строгом смысле
- Функция Рабина (возведение в квадрат по модулю): определение, обратимость при известном разложении модуля на множители, определение подмножества, на котором она биективна и (предположительно) необратима (модуль - произведение двух простых вида 2k+3, вычет - квадратичный).
- Общее определение односторонней перестановки. Эффективная генерация равномерного распределения на D_n. Как её сделать для функции Рабина.

Вот последняя версия книги Н. К. Верещагина "Односторонние функции и их применения". Это основной учебник для нашего курса.

#дневниклекций
Попробую в этом семестре кратко описывать пройденное на лекциях. Если пропускаю что-то важное, дополняйте. Вчера было вот что (возможно, в другом порядке):
- Общее понятие криптографической задачи. Примеры: шифрование, цифровая подпись, авторизация, распределённые вычисления
- Парадигма доказательной криптографии. Её важность в связи с бурным развитием ИИ-моделей.
- Варианты угроз: равномерный и неравномерный противник
- Связь возможности построить криптопротоколы и проблемы P/NP
- Перечень основных математических конструкций и криптографических протоколов, которые мы будем изучать в курсе
- Одноразовый блокнот (гаммирование) как один из немногих гарантированно защищённых протоколов. Его ненадёжность относительно двукратной атаки
- Немного о шифровальной машине Enigma и её взломе Тьюрингом
- Немного о квантовой и постквантовой криптографии
- Определение односторонней функции в сильном и слабом смыслах, относительно равномерного и неравномерного противника
- Теорема: если f(x) односторонняя, то и g(xy)=f(x)y тоже односторонняя (с идеей доказательства)
- Теорема: если существует слабо односторонняя функция, то существует и сильно односторонняя. Конструкция сильно односторонней из слабо односторонней и её защищённость против наивных обратителей.

В следующий раз начнём с полного доказательства теоремы об усилении: почему полученную функцию не смогут обратить не только наивные, но и произвольные обратители.

Предварительная версия программы курса. По поводу правила выставления оценок решим до 14 сентября.

С расписанием разобрались: семинар в 423+424 будет по средам, в том числе сегодня.

Информация для тех, кто уже проходил курс

Есть возможность записаться на спецкурс "Дополнительные главы криптографии". Примерное содержание: безопасные дву- и многосторонние вычисления, протоколы электронных выборов, неинтерактивные доказательства с нулевым разглашением, безопасное делегирование вычислений (снарки), можно также поговорить про блокчейн и криптовалюты. Занятия проходят по вторникам в 13:55. Первое занятие сегодня, но можно начать со второго занятия через неделю. Чат по курсу: https://t.me/+f2l8WjwADRYxZjk6

В группах 423 и 424 по ошибке семинары поставлены в 2 слота: вторник и среда. На этой неделе семинар будет завтра, а потом уточним.

Криптография ФПМИ pinned «Служебный пост с информацией на осень 2026 (будет дополняться). Расписание: Лекции - Даниил Мусатов, вт, 10:35, 117 ГК Семинары: 413 (ПМИ.Инф) - Фёдор Киселёв, вт, 12:10, 535 ГК 415+417 (ПМИ.Инф) - Никита Андрусов, вт, 13:55, 907 КПМ 416+417 (по выбору)…»

Служебный пост с информацией на осень 2026 (будет дополняться).

Расписание:
Лекции - Даниил Мусатов, вт, 10:35, 117 ГК

Семинары:
413 (ПМИ.Инф) - Фёдор Киселёв, вт, 12:10, 535 ГК
415+417 (ПМИ.Инф) - Никита Андрусов, вт, 13:55, 907 КПМ
416+417 (по выбору) - Давид Дарчиев, вт, 13:55, 525 ГК
423+424 (по выбору) - Артур Бикеев, ср, 13:55, 509 ГК
425+426+427 (по выбору) - Максим Коротков, вт, 12:10, 5.18 Цифра
Бакалавриат ДМ - Илья Степанов, вт, 15:30, 415 ГК

Этот канал (новости и материалы по курсу): https://t.me/fpmi_crypto
Чат для вопросов и обсуждений: https://t.me/+lg12rtBNAJthNzgy

Папка с материалами (литература, списки задач и прочее): https://www.dropbox.com/scl/fo/uqmf4kjlcwjajefnwwp2d/AIVKOxd_I8UB1owxdzFdO_s?rlkey=cv0hobct34du3uezi6x25jb1m&dl=0
Табличка для оценок: (будет дополнено)

Давайте начнём к/р в 15:15, аудитория 302 КПМ.

Напоминаю, что завтра будет к/р для тех, кто не писал в декабре. Планируемое время начала - 15 часов, возможна задержка, если экзамен по теории игр затянется. Аудиторию уточним утром, пока что есть только поточка Цифры, но там неудобные столики. По возможности, актуализируйте свой статус в таблице https://docs.google.com/spreadsheets/d/1naQAkNvNKWYOzLy8Ge4PBsMiKHNHYy24nhEenWFWNhQ/edit?usp=sharing

С наступившим новым годом! С учётом голосования предлагаю сделать контрольную в пятницу, 9-го, во второй половине дня, точное время скажу позже. Если совсем не можете, но хотите написать, пишите в личку @musatych, обсудим.

У нас произошла накладка, к/р начнётся ориентировочно в 11:30. Аудитория та же, 117 ГК.

Правила проведения контрольных:
Контрольная работа состоит из 9 задач разной сложности. Число баллов за задачу указано в скобках. Во время решения можно пользоваться любой литературой, в том числе в электронном формате, но нельзя общаться, в том числе искать в интернете. Также нельзя использовать программы обработки текста сложнее обычного поиска. Решения нужно писать полностью, даже если похожие конструкции разбирались на лекциях или семинарах. Ни на какие вопросы по условию ответы не даются. Если вы предполагаете, что в условии ошибка, можете исправить или дополнить его по своему усмотрению. Время на выполнение работы — 2 часа 45 минут.
Завтра меня не будет, будет проктор на раздачу/проведение/сбор работ, так что пункт про вопросы важный.

Завтрашняя контрольная работа пройдёт в 117 ГК, начало в 11:00, продолжительность - 2 часа 45 минут. Вроде бы должны все записавшиеся поместиться в аудитории. Если хотите поменять день, это пока можно сделать.

Завтра надо будет забронировать аудиторию на контрольную во вторник. Чтобы понимать, какого размера нужна аудитория, я сделал запись на даты. Точную дату в январе выберем немного позже. Выберите подходящий вам вариант в табличке: https://docs.google.com/spreadsheets/d/1naQAkNvNKWYOzLy8Ge4PBsMiKHNHYy24nhEenWFWNhQ/edit?usp=sharing

Третья домашка. Сроки сдачи уточняйте у своих семинаристов.