OWF2023

Односторонние функции и их применения (4-ий курс ТИ) осенний семестр 2023 года

Лекции проходят по пятницам на второй паре. Первая лекция - 29 сентября. Семинары проходят по пятницам в 13:00 в ауд. D106.

Новости

• Письменный экзамен будет 21 декабря в 9:30 в ауд. D725
• Таблица для записи на коллоквиум 1 декабря.
• Выложена программа коллоквиума, который состоится 1 декабря.
• Лекции начинаются 29 сентября. Первые три недели будут сдвоенные лекции.

Контакты

Лектор: Верещагин Николай Константинович, nikolay.vereshchagin@gmail.com, телеграм: nikolay_vereshchagin

Семинарист: Мануйленко Никита Сергеевич, nikitamann1910@gmail.com, телеграм: Ni_Mans

Группа в Телеграм: https://t.me/joinchat/seYgH4TaKrsxY2Yy

Краткое описание

Функция f, отображающая слова в слова, называется односторонней, если по x можно найти f(x) за полиномиальное от длины x время, однако в обратную сторону, 
по f(x) найти x или какой-то другой прообраз f(x) за полиномиальное время можно только на ничтожной доле входов. В спецкурсе будут доказаны основные факты об односторонних функциях. Односторонние функции применяются в криптографии для построения доказуемо надежных генераторов псевдослучайных чисел, 
схем шифрования с открытым и закрытым ключом, протоколов привязки, протоколов бросания монетки по телефону и протоколов идентификации.


Необходимы предварительные знания: знакомство с основными вычислительными 
моделями: машинами Тьюринга, вероятностными машинами Тьюринга 
и схемами из функциональных элементов.

Более подробная программа.

Отчётность по курсу и критерии оценки

Итоговая оценка складывается из оценок за домашние задания, за колллоквиум, за экзамен и за дополнительные сложные задачи. Она вычисляется так, чтобы усердный студент, хорошо усвоивший курс, но не сделавший ни одной дополнительной задачи, получил 8 баллов. Оценки за домашние задания, за колллоквиум и за экзамен ставятся по десятибалльной системе. Дополнительные задачи входят в домашние задания и имеют специальные пометки, их будет всего четыре, по одной в каждом ДЗ. За каждую решеннную дополнительную задачу к итоговой оценке прибавляется 0.5 балла. Точнее, итоговая оценка выставляется по следующуй формуле MIN{8, 0.2*(оценка за домашние задания)+ 0.4*(оценка за коллоквиум)+ 0.4*(оценка за экзамен)} + (оценка за дополнительные задачи).

Для студентов МКН СПбГУ: для получения зачёта нужно набрать не менее 4-х итоговых баллов (при наборе 4 баллов досрочно можно экзаменационную работу не сдавать). Для получения "тройки" надо получит итоговый балл 4, для "четверки" - 6, для "пятерки" - 8.

Домашние задания

В течение двух модулей студентам будет дано 4 домашних задания. Оценка за каждое домашнее задание равна доле решенных задач, умноженной на 10. Общая оценка за домашние задания равна среднему арифметическому оценок за решение каждого из заданий. На решение каждого ДЗ дается не менее 14 дней, решение ДЗ нужно присылать семинаристу (в телеграм или на почту)

Коллоквиум и письменный экзамен

Коллоквиум (устный) и экзамен (письменный) проводятся в конце второго модуля и оцениваются по десятибалльной системе.

Те, кто не смог прийти на коллоквиум по болезни, могут его сдать отдельно в день пересдачи (один раз). Это же относится и к тем, кто не смог прийти на экзамен. На пересдачу также могут прийти те, кто в итоге получил менее 4 баллов, и заново сдать коллоквиум и/или экзамен. Те, кто после всех пересдач получил итоговую оценку менее 4 баллов, сдают устный экзамен комиссии, в этом случае все полученные ранее оценки аннулируются и оценка, полученная на экзамене, является окончательной.

Правила округления

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

Коллоквиум

Коллоквиум будет 1 декабря онлайн по ссылке на Зум: https://us06web.zoom.us/j/82380215216?pwd=E4iiHaYWkhP0rCTkZofj1HZEUKNavO.1

Программа коллоквиума 

Подключившись к конференции в то время, в которое записались (см. ниже ссылку на таблицу), Вы получите 
один вопрос на теорему с доказательством.
 На подготовку ответа на этот вопрос у Вас будет 30 минут, и в это время можно пользоваться любыми источниками. 
После ответа на этот вопрос Вы получите второе задание, состоящее
из двух вопросов на определение или формулировку теоремы.
 На эти вопросы надо отвечать сразу. 
Коллоквиум Вы сдаёте устно он-лайн одному из преподавателей.
 Для уточнения оценки 
преподаватель может задавать дополнительные вопросы на знание определений и
 основных фактов курса.
 Оценка за коллоквиум формируется следующим образом.
 Полный ответ на первый вопрос оценивается в 5 баллов, а полные ответы на другие два вопроса --- в 2.5 балла. Таблица для записи на коллоквиум.

Экзамен

Письменный экзамен будет 21 декабря в 9:30 в ауд. D725 и будет продолжаться 90 минут. Экзамен будет происходить очно, вариант будет состоять из 4 задач. Разрешено пользоваться печатными конспектами лекций, а также любыми бумажными материалами. Выходить из аудитории во время экзамена нельзя.

Студенты на он-лайн обучении пишут экзаменационное задание с прокторингом. Более подробная инструкция тут:

1. Присоединиться к конференции https://us02web.zoom.us/j/83665346300 надо на десять минут раньше, то есть, в 9:20. В 9:30 станут доступны задания, которые надо загрузить по ссылке в чате конференции. Студенты решают задания на бумаге, в конце экзамена делают фотографии/сканы решений и посылают на адрес nikolay.vereshchagin@gmail.com. Черновики отсылать не надо. Крайний срок посылки - 15 мин после конца экзамена.

2. Экзамен длится 90 минут. Во время экзамена должны быть включены камеры и микрофоны, отходить от компьютера не разрешено. Разрешено только смотреть на условия задач и на конспекты лекций (можно и на электронный вариант), писать на листах бумаги, а также смотреть на любые бумажные материалы на столе. Студенты могут пользоваться мышью и клавиатурой только для того, чтобы перелистывать конспекты лекций и условия задач. Если во время экзамена у студента возникнет вопрос по условию задачи, он может устно задать его и преподаватель даст на него ответ.

3. Если у студента случился один или два обрыва связи продолжительностью менее пяти минут, он может продолжить написание экзамена (дополнительное время при этом не предоставляется). Если случился обрыв связи продолжительностью дольше 5 минут или более двух пятиминутных, то считается, что студент пропустил экзамен. В этом случае ему будет предложено без штрафов сдать экзамен устно в течение недели с момента данного экзамена.

Пересдачи

Пересдачи состоятся января и и (пересдача комиссии) февраля.

Примерные сроки контрольных мероприятий

Первое домашнее задание 13 октября (выкладывание), 1 ноября (сдача).

Второе домашнее задание 1 ноября (выкладывание), 15 ноября (сдача).

Третье домашнее задание 15 ноября (выкладывание), 29 ноября (сдача).

Четвертое домашнее задание 2 декабря (выкладывание), 16 декабря (сдача).

Домашние задания

Домашнее задание 1 Срок сдачи 1 ноября 23:59.

Домашнее задание 2 Срок сдачи 15 ноября 23:59.

Домашнее задание 3 Срок сдачи 2 декабря 23:59.

Домашнее задание 4 Срок сдачи 16 декабря 23:59.

Результаты

Общая ведомость оценок

Прочитанные лекции

Лекция 1 (29 сентября).

Слабо и сильно необратимые функции для равномерного и неравномерного противника. Односторонние функции.
 Если P=NP, то односторонних функций нет.
 Функция Mult. 
Функция SubsetSum. Функция Code.

Лекция 2 (29 сентября).

Преобразование слабо необратимой функции в сильно необратимую. Всюду определенные односторонние перестановки. Функция Рабина
. 


Лекция 3 (6 октября).

Полиномиально моделируемые и доступные распределения.
 Функция RSA и дискретная экспонента. Односторонние перестановки - общее определение.
 Односторонние
 перестановки с секретом (определение) и улучшенные односторонние
 перестановки с секретом.

Лекция 4 (6 октября).

Генераторы ПСЧ. Любой генератор ПСЧ является слабо односторонней функцией.
 Теорема о существовании генератора ПСЧ (без доказательства),
 если существуют односторонние функции.

Статистически неотличимые и вычислительно неотличимые случайные величины.
 Свойства вычислительно неотличимых случайных величин
. Общий план построения генератора ПСЧ, исходя из односторонней перестановки.

Лекция 5 (13 октября).

Теорема Блюма и Микэли.

Определение трудного предиката. Теорема Яо. Использование трудного предиката и
 инвариантного распределения для построения генератора ПСЧ.

Лекция 6 (13 октября).

Теорема Левина-Голдрайха о коде Адамара. Построение трудного предиката для данной односторонней
 функции.


Лекция 7 (20 октября).


Одноразовые схемы шифрования с закрытым ключом. 
Построение одноразовой СШЗК на основе генератора ПСЧ. 
 
Одноразовые схемы шифрования с открытым ключом.
 Построение одноразовой СШOК на основе генератора односторонней перестановки с секретом.

Лекция 8 (3 ноября).

Многоразовые схемы шифрования.
 Семейства ПСФ. Построение семейства ПСФ на основе
 генератора ПСЧ. Многоразовая СШЗК на основе семейства ПСФ. 


Лекция 9 (10 ноября).


Неинтерактивные протоколы привязки к биту.
 Построение протокола привязки к биту на основе инъективной односторонней
 функции. Интерактивные алгоритмы. Интерактивные протоколы привязки к биту.


Лекция 10 (17 ноября).

Протоколы генерации случайного бита. Игра в орлянку по телефону.

 Протоколы идентификации: определение. Три вида атаки: простая атака,
 атака с подслушиванием и атака с фальшивым банкоматом.
 Построение протокола идентификации с закрытым и открытым ключом для простой атаки.

Лекция 11 (24 ноября).

Построение протоколов идентификации
 с закрытым ключом для двух других видов атаки. Построение протоколов идентификации
 с открытым ключом для двух других видов атаки.

Лекция 12 (8 декабря).

Доказательство неразглашения информации для протокола идентификации с открытым ключом.

Криптографические семейства хэш-функций.

Лекция 13 (15 декабря).

Протоколы электронной подписи. Подпись с закрытым ключом. Одноразовая схема подписи с открытым ключом.

Семинары

Семинар 1 (2 октября).

Листок 1

Семинар 2 (4 октября).

Листок 2

Семинар 3 (9 октября).

Листок 3

Семинар 4 (11 октября).

Листок 4

Семинар 5 (15 октября).

Листок 5

Семинар 6 (18 октября).

Листок 6

Семинар 7 (23 октября).

Листок 7

Семинар 8 (3 ноября).

Листок 8

Семинары 9 и 10 (18 ноября).

Листок 9

Листок 10

Семинар 11 (25 ноября).

Листок 11

Семинар 12 (8 декабря).

Листок 12

Семинар 13 (16 декабря).

Листок 13

Конспекты лекций

В этой незаконченной книге есть все, что будет на лекциях.

Рекомендуемая литература

0. Китаев А., Шень А., Вялый М.
Классические и квантовые вычисления. 
Изд-во МЦНМО.
 


1. Введение в криптографию. Под общей редакцией В.В.Ященко. ---
3-е изд. доп. --- М.: МЦНМО: "ЧеРо", 2000. --- 288 с.
 


2. М.И. Анохин, Н.П.Варновский, В.М.Сидельников, В.В. Ященко.
Криптография в банковском деле. М.: МИФИ, 1997.



3. O. Goldreich.
Foundations of cryptography. Basic tools.
Cambridge Univ. Press. 2001. 400 p.



4. O. Goldreich.
Foundations of cryptography. Basic applications.
Cambridge Univ. Press. 2004.