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

#дневниклекций
Сегодня продолжили доказательство теоремы о преобразовании односторонней перестановки в ГПСЧ, но целиком не закончили. Было следующее:
- Напоминание общей схемы доказательства: построение перестановки с трудным битом (теорема Левина-Голдрайха, 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+ε). Идея декодирования списком. Основные вехи доказательства: самокоррекция с учётом неизвестных настоящих значений, амплификация за счёт попарно независимых запусков, построение семейства попарно независимых случайных строк из логарифмического числа истинно случайных, полный перебор значений кода на этих истинно случайных и построение списка возможных декодированных строк.

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

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

#дневниклекций
В прошлый раз мы подробно обсудили конструкцию трудного бита и начали псевдослучайные функции. Вот что было:
- Пусть есть 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). Ещё нужно аккуратно оценить вероятности, чтобы вероятность успеха была существенной.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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