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

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

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

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

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

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

#дневниклекций В прошлый раз мы подробно обсудили конструкцию трудного бита и начали псевдослучайные функции. Вот что было: - Пусть есть f(x) и доступ к вычислению трудного бита с ошибкой. Нужно найти x. Если ошибка нулевая, то биты x просто берутся из значений…#дневниклекций В прошлый раз изучили псевдослучайные функции и начали шифрование. Вот что было:- Повторение понятия ПСФ в слабом и сильном смысле.- Построение семейства ПСФ на базе ГПСЧ. Дерево псевдослучайных слов, построенное генератором типа 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, потом расширение конструкции на произвольный полином. Обсуждение, почему при растущей длине нельзя использовать соображения транзитивности для вычислительной неотличимости, а нужно явное гибридное рассуждение.