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

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

Завтра, 2 декабря, лекция состоится, но будет замена лектора: прочтёт Илья Степанов. Тема - забывающая передача данных (oblivious transfer).

#дневниклекций
В прошлый раз (2 недели назад) мы говорили о приложениях протоколов привязки и протоколах аутентификации:
- Постановка задачи о распределённом бросании монетки. Два вида постановки: стороны определяют, кто выиграл, или просто генерируют случайный бит. Надёжный протокол для первого случая: Алиса отправляет привязку к случайному биту, Боб отвечает случайным битом, Алиса раскрывает ключ. Если ключ не подошёл, то выиграл Боб, если подошёл, то победитель определяется xor'ом двух битов.
- Невозможность надёжного протокола во второй постановке (б/д). В частности, в указанном протоколе Алиса может намеренно не раскрыть привязку и победит всегда Боб.
- Постановка задачи об аутентификации. Варианты с закрытым и открытым ключом. Виды атаки: простая, с подслушиванием и фишинговая (с фальшивым сервером), их связи между собой.
- Простейший протокол с закрытым ключом: клиент отправляет пароль, сервер сверяет со своей записью.
- Простейший протокол с открытым ключом: сервер хранит y, клиент отправляет x, такой что f(x)=y.
- Протокол с закрытым ключом на базе семейства ПСФ: сервер присылает x, клиент возвращает f_s(x). Его надёжность относительно многократной атаки с подслушиванием для слабого семейства ПСФ и относительно фишинговой атаки для сильного семейства ПСФ.
- Протоколы с открытым ключом через доказательства с нулевым разглашением. Кажется, мы это подробно не обсудили, сегодня дообсудим.

Следующая большая тема - протоколы цифровой подписи. Сегодня будем обсуждать определения и простейшие конструкции, а также необходимые для более сложных конструкций семейства хеш-функций. Приходите!

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

#дневниклекций
В прошлый раз изучали схемы шифрования и протоколы привязки к биту. Вот что успели пройти:
- Общая схема шифровнря с открытым ключом.
- Исторически первая схема шифрования с открытым ключом - RSA. Обсуждение, почему её трудно взломать, но можно, если научиться раскладывать на множители. Почему её трудно обобщить на произвольные односторонние функции.
- Схема шифрования одного бита на базе произвольного семейства односторонних перестановок с секретом и трудным битом. Доказательство её надёжности при однократном шифровании. Обсуждение, почему надёжность распространяется на многократную атаку и атаку с выбором сообщений.
- Общая идея привязки к биту/сообщению. Варианты абсолютной и вычислительной непрозрачности и неподменяемости. Почему сочетание абсолютных вариантов невозможно.
- Определение неинтерактивной привязки с вычислительной непрозрачностью и абсолютной неподменяемостью. Конструкция на базе односторонней перестановки с трудным битом.
- Определение аналогичной интерактивной привязки. Конструкция на базе произвольного ГПСЧ.

Сегодня поговорим о приложениях протокола привязки и перейдём к протоколам аутентификации.

#дневниклекций
В прошлый раз изучили псевдослучайные функции и начали шифрование. Вот что было:
- Повторение понятия ПСФ в слабом и сильном смысле.
- Построение семейства ПСФ на базе ГПСЧ. Дерево псевдослучайных слов, построенное генератором типа n->2n. Корень - идентификатор функции, ветвь - её аргумент.
- Доказательство, что такая конструкция будет ПСФ в слабом смысле.
- Обсуждение, почему она будет ПСФ и в сильном смысле (без строгого доказательства)
- Общая постановка задачи о шифровании с закрытым ключом. Виды атаки: однократное подслушивание, многократное подслушивание, атака с выбором сообщений
- Протокол гаммирования (одноразовый блокнот): побитово ксорим сообщение и закрытый ключ. Его надёжность относительно однократного подслушивания и ненадёжность относительно многократного.
- Более эффективный вариант гаммирования при помощи ГПСЧ: ксорим не с ключом, а со значением генератора на нём
- Протокол многократного шифрования при помощи ПСФ: ключ это индекс функции из ПСФ, шифр - пара из случайной строки и ксора сообщения со значением функции на этой строке. Обсуждение, почему слабые ПСФ дают надёжность относительно многократного подслушивания, а сильные - относительно атаки с выбором сообщений.
- Общая схема шифрования с открытым ключом, обсуждение, почему разумно рассматривать только однократную атаку.

Сегодня построим протокол шифрования с открытым ключом и, наверное, начнём протоколы аутентификации.

#дневниклекций
В прошлый раз мы подробно обсудили конструкцию трудного бита и начали псевдослучайные функции. Вот что было:
- Пусть есть f(x) и доступ к вычислению трудного бита с ошибкой. Нужно найти x. Если ошибка нулевая, то биты x просто берутся из значений трудного бита.
- Если ошибка меньше 1/4-ε, то для поиска x_i можно взять случайную самокоррекцию g(e_i+r)-g(r) и амплифицировать, где g - трудный бит с шумом.
- Если ошибка меньше 1/2-ε, то нужно брать большинство из g(e_i+r)-h(r), где g - трудный бит с шумом, h - без шума.
- Мы не знаем значений h(r), вместо этого мы доказываем, что можно взять только попарно независимые r (ЗБЧ для попарно независимых величин).
- Можно построить полиномиальное число попарно независимых r_j из логарифмического числа истинно независимых u_k через всевозможные суммы. При этом h(u_k) однозначно определит h(r_j) по линейности.
- Теперь можно перебрать все возможные h(u_k) и по каждому попробовать восстановить x. Мы можем проверить, правильно ли восстановили, вычислив f(x). Ещё нужно аккуратно оценить вероятности, чтобы вероятность успеха была существенной.

В конце обсудили псевдослучайные функции:
- Неформальное понятие псевдослучайной функции, неадаптивные и адаптивные отличители
- Почему недостаточно просто взять генератор и запустить много раз
- Определение семейства ПСФ в слабом и сильном смысле, построение примера, псевдослучайного в слабом, но не в сильном смысле (без требования эффективной вычислимости)

Сегодня будем строить ПСФ из генераторов. Может быть, успеем начать шифрование.

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

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

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

#дневниклекций
Вчера начали изучать теорему о превращении любой односторонней перестановки в генератор псевдослучайных чисел. А именно, изучили вот что:
- Общее понятие генератора случайных чисел. Отличия между генераторами истинно случайных чисел и псевдослучайных чисел
- Немного о работе ГИСЧ. Источники случайности в природе и технике и улучшение случайности при помощи экстракторов.
- Виды близости (ансамблей) случайных величин: одинаковое распределение, статистическая близость (несколько эквивалентных свойств), вычислительная неотличимость. Всё это - отношения эквивалентности.
- Определение ГПСЧ. Обсуждение, почему распределение его выходов заведомо далеко от настоящей случайности.
- Формулировка теоремы о преобразовании односторонней перестановки в ГПСЧ. План доказательства в 3 этапа: построение перестановки с трудным битом, построение генератора n->n+1, построение генератора n->p(n). Описание конструкций, неформальное обоснование их корректности.
- Доказательство корректности 3-го этапа. Сначала преобразование генератора n->n+1в генератор n->n+2, потом расширение конструкции на произвольный полином. Обсуждение, почему при растущей длине нельзя использовать соображения транзитивности для вычислительной неотличимости, а нужно явное гибридное рассуждение.

Сегодня занятия по расписанию, приходите!

(Отмена сегодня) Доброе утро! К сожалению, я заболел, а найти замену не удалось, так что сегодня лекции не будет. На семинарах будет окончание односторонних функций, а также вычислительная неотличимость - она очень пригодится в следующей теме про генераторы.

Channel photo updated

#дневниклекций
Сегодня почти всю лекцию потратили на теорему об усилении. Вот рассказ подробнее:
- Напоминание: сильно и слабо односторонние функции, конструкция сильно односторонней F из слабо односторонней f, устойчивость относительно наивных обратителей
- Идеи, как использовать любой обратитель F для обращения f: подстановка вместо первого аргумента, многократный повтор, подстановка вместо любого аргумента.
- Псевдокод для итогового обратителя f.
- Доказательство успешности обратителя f: разделение аргументов на трудные и лёгкие, две леммы о вероятностях успехов двух обратителей, выбор параметров, приводящих к противоречию.
- Общие рассуждения о парадигме доказательной криптографии, анонсы её будущих применений в теоремах курса.
- Понятие односторонней перестановки и анонс результата о генераторах ПСЧ.

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

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

Криптография ФПМИ pinned «Служебный пост с информацией на осень 2025 (будет дополняться). Расписание: Лекции - Даниил Мусатов, вт, 10:45, 2.36 Цифра Семинары: 322+325 (Основа) - Илья Степанов, вт, 17:05, 2.35 Цифра 326 (Продва) - Артур Бикеев, вт, 13:55, 201 УПМ Бакалавриат ДМ -…»

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

Расписание:
Лекции - Даниил Мусатов, вт, 10:45, 2.36 Цифра

Семинары:
322+325 (Основа) - Илья Степанов, вт, 17:05, 2.35 Цифра
326 (Продва) - Артур Бикеев, вт, 13:55, 201 УПМ
Бакалавриат ДМ - Максим Коротков, вт, 12:20, 432 ГК

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

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

В этом семестре будет два курса криптографии: стандартный, как в прошлом году, и продвинутый - продолжение. Продвинутый обязателен для студентов кафедры ДМ, которые уже проходили основной, для остальных факультативный. Примерный список тем продвинутого курса: конфиденциальные дву- и многосторонние вычисления, протоколы электронных выборов, блокчейн, неинтерактивные доказательства с нулевым разглашением, снарки.
Если хотите ходить на продвинутый курс, присоединяйтесь к чату: https://t.me/+Mep4YTAYAWIwZDMy

Вторая контрольная будет завтра, 27 декабря, с 16:00 до 19:00, 430 ГК, на утро аудиторий не было. Если вечернее время вам не подходит, пишите в личку, обсудим варианты.