Просмотр кода страницы OWF2022

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

Лекции проходят по средам 11:10 - 12:30 в ауд. N507. Первая лекция - 7 сентября.
Семинары проходят по средам 13:00-14:20 в ауд. G407 (во втором модуле K417), начиная с 7 сентября. Трансляция лекций  
и семинаров через Zoom:    https://us02web.zoom.us/j/84159303889?pwd=Q0piemZJWTJrZWtoOXNaaDZlYUJIQT09 Код доступа:   782688.

==Новости==

* 19 октября 2022 года лекция будет онлайн https://us02web.zoom.us/j/84159303889?pwd=Q0piemZJWTJrZWtoOXNaaDZlYUJIQT09

* 12 октября 2022 года лекции не будет

==Контакты== 

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

Семинарист: Милованов Алексей Сергеевич almas239@gmail.com, телеграм: AlexeySMilovanov

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

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

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

[https://www.dropbox.com/s/hjdi78zxb2sx3fz/program.pdf?dl=0 Более подробная программа].

==Видеозаписи==
https://disk.yandex.ru/d/HtAZTRB4MupXWw

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

Итоговая оценка складывается из оценок за домашние задания,  оценки за коллоквиум и экзамен. Оценки за колллоквиум и экзамен входят в итоговую оценку с коэффициентами 0.4, а оценки за домашние задания - с коэффициентом 0.2.

В домашних заданиях иногда будут даваться бонусные задания. За каждую решеннную бонусную задачу к итоговой оценке будет прибавляться 0.5 балла.  

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

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

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

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

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

====Коллоквиум====
Коллоквиум будет 14 декабря  [ Программа коллоквиума.]

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

====Экзамен====

Письменный экзамен будет ... и будет продолжаться 90 минут.

====Пересдачи====

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

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

Первое домашнее будет выложено 28 сентября, срок сдачи 12 октября.

Второе домашнее будет выложено 19 октября, крайний срок сдачи 2 ноября.

Третье домашнее будет выложено 9 ноября, крайний срок сдачи 23 ноября.

Четвертое домашнее будет выложено 2 декабря, крайний срок сдачи - 16 декабря.

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

[https://drive.google.com/file/d/1TbZs6wmDGEe3Q9mK9DhB3cx6zXd9WZl3/view?usp=sharing Домашнее задание 1] Срок сдачи 12 октября.

==Результаты ==
[https://docs.google.com/spreadsheets/d/1xMxIDFpNPU8t3rMG-rBuXsUJLOvKDeja-fsO6yXtMGI/edit?usp=sharing Общая ведомость оценок]

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

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

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

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

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

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

====Лекция 4 (28 сентября).  ====

Односторонние  перестановки с секретом (определение) и улучшенные односторонние  перестановки с секретом.

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

====Лекция 5 (5 октября).  ====
Статистически неотличимые и вычислительно неотличимые случайные величины.  Свойства вычислительно неотличимых случайных величин . 
Общий план построения генератора ПСЧ, исходя из односторонней перестановки. 
Теорема Блюма и Микэли.

==Планируемые лекции==
====Лекция 6 (19 октября).  ====
Определение трудного предиката. Лемма Яо. Использование трудного предиката и  инвариантного распределения для построения генератора ПСЧ.
  
====Лекция 7 (2 ноября).  ====   
Теорема Левина-Голдрайха о коде Адамара.   Построение трудного предиката для данной односторонней   функции.  [https://drive.google.com/file/d/1gyqhhTjfplOOnvS228MM4ByI4pxxNuij/view?usp=sharing Запись лекции]

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

====Лекция 9 (16 ноября).  ====
    Многоразовые  схемы шифрования.  Семейства ПСФ. Построение семейства ПСФ на основе  генератора ПСЧ. 



====Лекция 10 (23 ноября).  ====
Многоразовая СШЗК на основе семейства ПСФ.    
Неинтерактивные протоколы привязки к биту.  Построение протокола привязки к биту на основе инъективной односторонней  функции. Построение неинтерактивного протокола привязки к строке.  

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

Интерактивные алгоритмы. Интерактивные протоколы привязки к биту.     
Построение интерактивного протокола привязки к биту на основе генератора ПСЧ.



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

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

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

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

==Планируемые лекции==

==Семинары  ==

=== Семинар 1 (7 сентября). ===

[https://drive.google.com/file/d/1vtVgUYqZGPq3NbYx5DqtzbhwAw-EBDl1/view?usp=sharing Листок 1]

=== Семинар 2 (14 сентября). ===

[https://drive.google.com/file/d/19WV5n2RCr-ZbWzqrU5c-KSknz89RRfJp/view?usp=sharing Листок 2]

=== Семинар 3 (21 сентября). ===

[https://drive.google.com/file/d/1fEuaTCUW8Jhhf6RIsxD5fhpzXvxgABTQ/view?usp=sharing Листок 3]

=== Семинар 4 (28 сентября). ===

[https://drive.google.com/file/d/1uV042xWXH1CvQEz5ArUTDCpgPlzeTDj-/view?usp=sharing Листок 4]

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

[https://drive.google.com/file/d/1UfHakKASzuJWWiPDM58qaWAtiHw4NoE_/view?usp=sharing Листок 5]
[https://jamboard.google.com/d/1v_DgBHvbC1ET5n68jDHpEagiY2NUnpBtX4OkP2IkEVQ/edit?usp=sharing Доска]



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

[https://disk.yandex.com/i/_KCz99TW3CVMpw Листок 6]
[https://jamboard.google.com/d/19H_iBBwA1Szc-XRDnu3XaWtYwl5eSfdNvR9CFeIUS_c/edit?usp=sharing Доска]

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

[https://www.dropbox.com/s/tgb6ipbgd9wfpre/lectures.pdf?dl=0 В этой незаконченной книге есть все, что будет на лекциях.]

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

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.