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

Напоминаю, что завтра будет к/р для тех, кто не писал в декабре. Планируемое время начала - 15 часов, возможна задержка, если экзамен по теории игр затянется. Аудиторию уточним утром, пока что есть только поточка Цифры, но там неудобные столики. По возможности…

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

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

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

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

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

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

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

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

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

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

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

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

#дневниклекций В прошлый раз мы подробно обсудили конструкцию трудного бита и начали псевдослучайные функции. Вот что было: - Пусть есть f(x) и доступ к вычислению трудного бита с ошибкой. Нужно найти x. Если ошибка нулевая, то биты x просто берутся из значений…

#дневниклекций Сегодня продолжили доказательство теоремы о преобразовании односторонней перестановки в ГПСЧ, но целиком не закончили. Было следующее: - Напоминание общей схемы доказательства: построение перестановки с трудным битом (теорема Левина-Голдрайха…

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

#дневниклекций Вчера начали изучать теорему о превращении любой односторонней перестановки в генератор псевдослучайных чисел. А именно, изучили вот что: - Общее понятие генератора случайных чисел. Отличия между генераторами истинно случайных чисел и псевдослучайных…

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