OWF2021 — различия между версиями

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск
(→‎Новости)
(не показаны 104 промежуточные версии 2 участников)
Строка 1: Строка 1:
 
= Односторонние функции и их применения (4-ий курс ТИ) 2021 год =
 
= Односторонние функции и их применения (4-ий курс ТИ) 2021 год =
  
−
Лекции проходят по четвергам 14:40 - 16:00 в ауд. D201, семинары по средам 13:00-14:20 в ауд. D109. Первая лекция 2 сентября, первый семинар 8 сентября.
+
Лекции проходят по четвергам 14:40 - 16:00 онлайн https://zoom.us/j/92459176488?pwd=bWRGamhPY0twR2VJdDhvNHVFSEZpZz09 Идентификатор:92459176488 Код доступа: 180250
  
 
==Новости==
 
==Новости==
 +
*Запись на пересдачу коллоквиума 22.01: https://docs.google.com/spreadsheets/d/13MqkF05HkbtDU-q0nICEFs_rAJM-ZAS-MJ3YwuqnIBg/edit?usp=sharing
 +
Пересдача пройдёт в Google meet: meet.google.com/hee-kmku-asd
 +
 +
*Пересдача экзамене 22.01 будет в 10:00. Ссылка https://zoom.us/j/92432770887?pwd=UktIN3MzaUhoK2QrK2djMWJvODZUdz09
 +
 +
*Выложены [https://www.dropbox.com/s/nczlmy0yslwzuhn/exam-23-12-2021.pdf?dl=0 решения задач экзамена]. Присланные решения проверены и оценки с критериями их выставления занесены в общую ведомость. Апелляции принимаются лектором (5 и 7 задачи) и семинаристом (остальные задачи) через Телеграм 23 и 24 декабря.
 +
 +
*Письменный экзамен начнется 23 декабря с 10:00 онлайн с прокторингом и будет продолжаться 90 минут. Подключиться к конференции
 +
https://zoom.us/j/98778960078?pwd=RVJzMHNYK2R1Y2FmMldJanVwYitCQT09 надо в 9:50.
 +
 +
*Уточнение правил сдачи коллоквиума: Подключившись к конференции в то время, в которое записались (см. ниже ссылку на таблицу), Вы получите 
один вопрос на теорему с доказательством.
 На подготовку ответа на этот вопрос у Вас будет 30 минут, и в это время можно пользоваться любыми источниками. 
После ответа на этот вопрос Вы получите второе задание, состоящее
из двух вопросов на определение или формулировку теоремы.
 На эти вопросы надо отвечать сразу. 
Коллоквиум Вы сдаёте устно он-лайн одному из преподавателей.
 Для уточнения оценки 
преподаватель может задавать дополнительные вопросы на знание определений и
 основных фактов курса.
 Оценка за коллоквиум формируется следующим образом.
Полный ответ на третий вопрос оценивается в 5 баллов, а полные ответы на первые два вопроса  --- в 2.5 балла.
 +
 +
*Таблица для записи на коллоквиум: https://docs.google.com/spreadsheets/d/1Xb01jzzcgSvy2nuk5MOvKMIqER83hg_-F6OfYxay0PU/edit?usp=sharing
 +
 +
*Письменный экзамен будет 23 декабря с 10:00 он-лайн.
 +
 +
*Выложено четвёртое домашнее задание
 +
 +
*Коллоквиум будет 16 декабря в 14:30. [https://drive.google.com/file/d/1C40POwqIaZzt9MkUGapdSGK1LlY3bwBv/view?usp=sharing Программа коллоквиума.]
 +
 +
*Выложено третье домашнее задание
 +
 +
*Лекции переносятся в Zoom: https://zoom.us/j/92459176488?pwd=bWRGamhPY0twR2VJdDhvNHVFSEZpZz09
 +
[https://drive.google.com/file/d/1gyqhhTjfplOOnvS228MM4ByI4pxxNuij/view?usp=sharing Запись лекции 28.10.2]
 +
 +
*Срок сдачи второго ДЗ перенесен на 7 ноября.
 +
 +
*Выложено второе домашнее задание.
 +
 +
*Семинар пройдёт 30 сентября вместо лекции (в 14.40 в D725).
 +
 +
*Выложено первое домашнее задание.
 +
 +
*Лекция 30 сентября отменяется!
 +
 +
*Семинар 15 сентября будет онлайн. Ссылка: meet.google.com/itr-jufj-bxb
  
 
==Контакты==  
 
==Контакты==  
  
−
Лектор: Верещагин Николай Константинович, nikolay.vereshchagin@gmail.com
+
Лектор: Верещагин Николай Константинович, nikolay.vereshchagin@gmail.com, телеграм: nikolay_vereshchagin
  
 
Семинарист: Милованов Алексей Сергеевич almas239@gmail.com, телеграм: AlexeySMilovanov
 
Семинарист: Милованов Алексей Сергеевич almas239@gmail.com, телеграм: AlexeySMilovanov
  
 
Группа в Телеграм: https://t.me/joinchat/seYgH4TaKrsxY2Yy
 
Группа в Телеграм: https://t.me/joinchat/seYgH4TaKrsxY2Yy
−
 
  
 
==Краткое описание==
 
==Краткое описание==
 
Функция f, отображающая слова в слова, называется односторонней, если по x можно найти f(x) за полиномиальное от длины x время, однако в обратную сторону, 
по f(x) найти x или какой-то другой прообраз f(x) за полиномиальное время можно только на ничтожной доле входов. В спецкурсе будут доказаны основные факты об односторонних функциях. Односторонние функции применяются в криптографии для построения доказуемо надежных генераторов псевдослучайных чисел, 
схем шифрования с открытым и закрытым ключом, протоколов привязки, протоколов бросания монетки по телефону и протоколов идентификации.
  
 
Функция f, отображающая слова в слова, называется односторонней, если по x можно найти f(x) за полиномиальное от длины x время, однако в обратную сторону, 
по f(x) найти x или какой-то другой прообраз f(x) за полиномиальное время можно только на ничтожной доле входов. В спецкурсе будут доказаны основные факты об односторонних функциях. Односторонние функции применяются в криптографии для построения доказуемо надежных генераторов псевдослучайных чисел, 
схем шифрования с открытым и закрытым ключом, протоколов привязки, протоколов бросания монетки по телефону и протоколов идентификации.
  
  
−
Необходимы предварительные знания: знакомство с основными вычислительными 
моделями: машинами Тьюринга, вероятностными машинами Тьюринга 
и схемами из функциональных элементов.  
+
Необходимы предварительные знания: знакомство с основными вычислительными 
моделями: машинами Тьюринга, вероятностными машинами Тьюринга 
и схемами из функциональных элементов.
 +
 
 +
[https://www.dropbox.com/s/hjdi78zxb2sx3fz/program.pdf?dl=0 Более подробная программа].
  
 
==Отчётность по курсу и критерии оценки==
 
==Отчётность по курсу и критерии оценки==
Строка 36: Строка 73:
 
Коллоквиум (устный) и экзамен (письменный) проводятся в конце второго модуля и оцениваются по десятибалльной системе.
 
Коллоквиум (устный) и экзамен (письменный) проводятся в конце второго модуля и оцениваются по десятибалльной системе.
  
−
Те, кто не смог прийти на коллоквиум по болезни, могут его сдать отдельно в день пересдачи (один  раз). Это же относится и к тем, кто не смог прийти на экзамен. Те, кто после всех пересдач получил итоговую оценку менее 4 баллов, сдают устный экзамен комиссии, в этом случае все полученные ранее оценки аннулируются и оценка, полученная на экзамене, является окончательной.  
+
Те, кто не смог прийти на коллоквиум по болезни, могут его сдать отдельно в день пересдачи (один  раз). Это же относится и к тем, кто не смог прийти на экзамен. На пересдачу также могут прийти те, кто в итоге получил менее 4 баллов, и заново сдать коллоквиум и/или экзамен. Те, кто после всех пересдач получил итоговую оценку менее 4 баллов, сдают устный экзамен комиссии, в этом случае все полученные ранее оценки аннулируются и оценка, полученная на экзамене, является окончательной.
  
 
===Правила округления===  
 
===Правила округления===  
Строка 43: Строка 80:
  
 
====Коллоквиум====
 
====Коллоквиум====
−
Коллоквиум будет ... .
+
Коллоквиум будет 16 декабря в 14:30. [https://drive.google.com/file/d/1C40POwqIaZzt9MkUGapdSGK1LlY3bwBv/view?usp=sharing Программа коллоквиума.]
  
−
[ Программа коллоквиума.]
+
Уточнение правил сдачи коллоквиума: Подключившись к конференции в то время, в которое записались (см. ниже ссылку на таблицу), Вы получите 
один вопрос на теорему с доказательством.
 На подготовку ответа на этот вопрос у Вас будет 30 минут, и в это время можно пользоваться любыми источниками. 
После ответа на этот вопрос Вы получите второе задание, состоящее
из двух вопросов на определение или формулировку теоремы.
 На эти вопросы надо отвечать сразу. 
Коллоквиум Вы сдаёте устно он-лайн одному из преподавателей.
 Для уточнения оценки 
преподаватель может задавать дополнительные вопросы на знание определений и
 основных фактов курса.
 Оценка за коллоквиум формируется следующим образом.
 Полный ответ на третий вопрос оценивается в 5 баллов, а полные ответы на первые два вопроса --- в 2.5 балла. [https://docs.google.com/spreadsheets/d/1Xb01jzzcgSvy2nuk5MOvKMIqER83hg_-F6OfYxay0PU/edit?usp=sharing Таблица для записи на коллоквиум.]
  
 
====Экзамен====
 
====Экзамен====
  
 +
Письменный экзамен будет 23 декабря с 10:00 онлайн с прокторингом и будет продолжаться 90 минут. Более подробная инструкция тут:
  
 +
1.  Экзамен письменный и проходит с прокторингом через Зум: https://zoom.us/j/98778960078?pwd=RVJzMHNYK2R1Y2FmMldJanVwYitCQT09
 +
Присоединиться к конференции надо на десять минут раньше, то есть, в 9:50. В 10:00 станут доступны задания, которые надо  загрузить по ссылке в чате конференции. Студенты решают задания на бумаге, в конце экзамена делают фотографии/сканы решений и посылают на адрес nikolay.vereshchagin@gmail.com.  Черновики отсылать не надо. Крайний срок посылки - 15 мин после конца экзамена.
 +
 +
2.  Экзамен длится 90 минут. Во время экзамена должны быть включены камеры и микрофоны, отходить от компьютера не разрешено. Разрешено только смотреть на условия задач и на конспекты лекций (можно и на электронный вариант), писать на листах бумаги, а также смотреть на любые бумажные материалы на столе. Студенты могут пользоваться мышью и клавиатурой только для того, чтобы перелистывать конспекты лекций и условия задач. Если во время экзамена у студента возникнет вопрос по условию задачи, он может устно задать его и преподаватель даст на него ответ.
 +
 +
3.  Если у студента случился один или два обрыва связи продолжительностью менее пяти минут, он может продолжить написание экзамена (дополнительное время при этом не предоставляется). Если случился обрыв связи продолжительностью дольше 5 минут или более двух пятиминутных, то считается, что студент пропустил экзамен. В этом случае ему будет предложено без штрафов сдать экзамен устно в течение недели с момента данного экзамена.
 +
 +
 +
Присланные решения проверены и оценки с критериями их выставления занесены в общую ведомость. Апелляции принимаются лектором (5 и 7 задачи) и семинаристом (остальные задачи) через Телеграм (23 и 24 декабря).
  
 
====Пересдачи====
 
====Пересдачи====
 +
 +
Пересдачи состоятся 22 января и 5 и 12 (пересдача комиссии) февраля.
  
 
==Примерные сроки контрольных мероприятий==
 
==Примерные сроки контрольных мероприятий==
Строка 65: Строка 114:
 
==Домашние задания  ==
 
==Домашние задания  ==
  
 +
[https://drive.google.com/file/d/1CKK5GYA_fCun7gL83hXCDBTLZOnGlHNc/view?usp=sharing Домашнее задание 1] Cрок сдачи 14 октября.
  
 +
[https://drive.google.com/file/d/1hl9Z2qEB0WmFvDEKo8UVX5qTuXRKoCdW/view?usp=sharing Домашнее задание 2] Срок сдачи 7 ноября.
  
 +
[https://drive.google.com/file/d/1zbJGeRC4Lzp9r0qy3P64A3Geb9ifsKQo/view?usp=sharing Домашнее задание 3] Срок сдачи 5 декабря.
  
−
[https://www.dropbox.com/s/anfjigs9fjqvegn/hw1_expanders.pdf?dl=0 Домашнее задание 1] Cрок сдачи 4.03.2021
+
[https://drive.google.com/file/d/1LXhy2QO53WwlFP1llG9eqwJV9OCjdJpD/view?usp=sharing Домашнее задание 4] Срок сдачи 19 декабря.
−
 
+
−
[https://www.dropbox.com/s/0tso7xdebecqm73/hw2_expanders.pdf?dl=0 Домашнее задание 2] Срок сдачи 15.04.2021
+
−
 
+
−
[https://www.dropbox.com/s/btmjoyf1x9vgu5n/CCTI_3.pdf?dl=0 Домашнее задание 3] Срок сдачи 13.05.2021
+
−
 
+
−
[https://www.dropbox.com/s/fji1td797iz4tlu/CCTI_4.pdf?dl=0 Домашнее задание 4] Срок сдачи 17.06.2021
+
  
 
==Результаты ==
 
==Результаты ==
−
[https://www.dropbox.com/scl/fi/z8d7384cwf2e1mfzdimlo/results.xlsx?dl=0&rlkey=92hfs1kvcy19tjcpl4w5f3jtd Общая ведомость оценок (в нее вносятся и результаты тестов)]
+
[https://www.dropbox.com/scl/fi/uq45japkvry39dbvka66n/results.xlsx?dl=0&rlkey=eccbofa79m9xbjay98pwc5r9w Общая ведомость оценок]
−
 
+
−
[https://drive.google.com/drive/folders/1TIy7t8d__Eq5ZkVGc84hEj0u1cNSzIVN?usp=sharing Результаты тестов]
+
  
 
==Прочитанные лекции==
 
==Прочитанные лекции==
  
−
[https://www.youtube.com/playlist?list=PLEwK9wdS5g0otnz2d5xArMHyloteZLR5_ Записи лекций и семинаров]
+
====Лекция 1 (2 сентября). ====
  
−
[https://www.dropbox.com/sh/qe4p5oxyj6y42pr/AAB2jG92VGHt9BfxoU8hAxLJa?dl=0 Ссылка на записи на доске, сделанные во время лекции]
+
Слабо и сильно необратимые функции для равномерного и неравномерного противника.  
 +
Односторонние функции.
 Если P=NP, то односторонних функций нет.
 Функция Mult. 
Функция SubsetSum.
  
−
====Лекция 1 (15 января).  ====
+
====Лекция 2 (9 сентября).  ====
  
−
Определение комбинаторного однородного экспандера. Существование (вероятностное доказательство).
+
Преобразование слабо необратимой функции в сильно необратимую. Полиномиально моделируемые и доступные распределения.
 

−
Реберное расширение и его связь с вершинным расширением.
+
  
−
====Лекция 2 (22 января).  ====
+
====Лекция 3 (16 сентября).  ====
 +
Функция Рабина
, функция RSA и дискретная экспонента.
  
−
Матрица графа и ее собственные числа.
+
====Лекция 4 (23 сентября). ====
−
Максимальное по абсолютной величине собственное число регулярного графа.  
+
Односторонние перестановки - общее определение.

−
Лемма о перемешивании. От спектрального экспандера к комбинаторному.
+
Односторонние
 перестановки с секретом (определение) и улучшенные односторонние
 перестановки с секретом.
  
−
====Лекция 3 (29 января). ====
+
Генераторы ПСЧ. Любой генератор ПСЧ является слабо односторонней функцией.
 Теорема о существовании генератора ПСЧ (без доказательства),
 если существуют односторонние функции.
−
Нижняя оценка sqrt(d) на второе собственное число d-регулярного графа. Формула для числа Каталана (без доказательства).
+
  
−
====Лекция 4 (5 февраля). ====
 
  
−
Вероятностное доказательство существования d-регулярного спектрального экспандера с d^c вершинами.
+
====Лекция 5 (7 октября). ====
 +
Статистически неотличимые и вычислительно неотличимые случайные величины.
 Свойства вычислительно неотличимых случайных величин
. Теорема о существовании
 +
генератора ПСЧ, если существуют ОФ (без доказательства).
 +
Общий план построения генератора ПСЧ, исходя из односторонней перестановки.
 +
Теорема Блюма и Микэли (формулировка).
  
−
====Лекция 5 (12 февраля). ====
+
====Лекция 6 (14 октября). ====
−
Степень графа и тензорное произведение графов и их собственные числа.
+
−
Зигзаг-произведение графов и первая оценка его собственных чисел.
+
  
−
====Лекция 6 (19 февраля). ====
+
Определение трудного предиката. Лемма Яо. Использование трудного предиката и
 инвариантного распределения для построения генератора ПСЧ.


−
Первая рекурсивная конструкция спектрального экспандера со сколь угодно большим количеством вершин.
+
====Лекция 7 (28 октября). ====  
−
Вторая рекурсивная конструкция спектрального экспандера со сколь угодно большим количеством вершин.
+
Теорема Левина-Голдрайха о коде Адамара.   Построение трудного предиката для данной односторонней
  функции.
 [https://drive.google.com/file/d/1gyqhhTjfplOOnvS228MM4ByI4pxxNuij/view?usp=sharing Запись лекции]
−
Вторая оценка для спектрального зазора зигзаг-произведения.
+
  
−
====Лекция 7 (26 февраля). ====
+
====Лекция 8 (11 ноября). ====
−
Второе собственное число связного недвудольного графа.
+
Построение генератора ПСЧ из односторонней перестановки.

Одноразовые схемы шифрования с закрытым ключом.
 +

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

 
 Многоразовые  схемы шифрования.
 Семейства ПСФ. Построение семейства ПСФ на основе
 генератора ПСЧ.  
  
−
====Лекция 8 (5 марта). ====
 
−
Применение экспандеров для дерандомизации.
 
  
−
====Лекция 9 (12 марта). ====
 
−
Экспандер Маргулиса.
 
  
−
====Лекция 10 (19 марта). ====
+
====Лекция 10 (25 ноября). ====
−
Двудольные экспандеры: определение и вероятностное доказательство существования.
+
Многоразовая СШЗК на основе семейства ПСФ. 
 
 +
Неинтерактивные протоколы привязки к биту.
 Построение протокола привязки к биту на основе инъективной односторонней
 функции. Построение неинтерактивного протокола привязки к строке. 

  
−
====Лекция 11 (26 марта). ====
+
====Лекция 11 (2 декабря). ====
  
−
Экспандер Варди - Парвареша.
+
Интерактивные алгоритмы. Интерактивные протоколы привязки к биту.
   
 +
Построение интерактивного протокола привязки к биту на основе генератора ПСЧ.
  
−
====Лекция 12 (9 апреля). ====
 
−
Коды с исправлением ошибок и их параметры. Оценка Синглтона и коды Рида - Соломона. Декодирование кодов Рида - Соломона за полиномиальное время.
 
  
−
====Лекция 13 (16 апреля).  ====
 
−
Оценка Хэмминга.
 
−
Линейные коды, проверочная матрица. Коды Хэмминга. Кодирование и декодирование для кодов Хэмминга.
 
−
Оценка Гилберта.
 
  
−
====Лекция 14 (23 апреля) ====
+
====Лекция 12 (9 декабря).  ====
  
−
Функция Шеннона. Графики оценок Хэмминга и Гилберта. Оценка Варшамова - Гилберта. Случайные линейные коды.
+
Протоколы генерации случайного бита. Игра в орлянку по телефону.


  
−
====Лекция 15 (30 апреля) ====
+
Протоколы идентификации: определение. Три вида атаки: простая атака,
 атака с подслушиванием и атака с фальшивым банкоматом.
 Построение протоколов идентификации
 с закрытым ключом  для всех трех видов атаки (для самой сильной атаки - без доказательства).
−
Коды Возенкрафта. Каскадные коды. Декодирование каскадного кода.
+
Построение протокола идентификации с открытым ключом для простой атаки.
 +
==Планируемые лекции==
  
−
====Лекция 16. (14 мая) ====
+
==Семинары ==
−
Коды Форни. Экспандерные коды: определение, последовательный алгоритм декодирования.
+
  
−
====Лекция 17  (21 мая) ====
+
=== Семинар 1 (8 сентября). ===
−
Оценка Плоткина и коды Адамара. Декодирование списком: определение и аналоги оценок Хэмминга и Гилберта.
+
[https://drive.google.com/file/d/1Va_E-LpRwAaA0a9uqoPim14AThGok_-x/view?usp=sharing Листок 1]
  
−
====Лекция 18 (28 мая ) ====
+
=== Семинар 2 (15 сентября). ===
−
Доказательство оценок Хэмминга и Гилберта.
+
[https://drive.google.com/file/d/1p7_qk9QolzD5C7IUCLwHiYSvSbG0yzbP/view?usp=sharing Листок 2]
−
Деревья разрешения, метод противника. Сертификатная сложность. Чувстительность и блочная чувствительность. Неравенствo D < C^2
+
  
−
====Лекция 19 (4 июня). ====
+
[https://drive.google.com/file/d/1Cy3lPOUYO0EIURdvt7ND4V-JpnAdZV4Z/view?usp=sharing Видео]
−
Вероятностные деревья и неравенство bs = O(R).
+
−
Неравенствo D < C*bs.
+
−
Неравенство C< bs*s.
+
  
−
====Лекция 20 (11 июня). ====
+
=== Семинар 3 (22 сентября). ===
−
Представление булевых функций многочленами с действительными коэффициентами.
+
[https://drive.google.com/file/d/10UtiAtVlbHsGUEkRTfGf4CG5ng0GojsF/view?usp=sharing Листок 3]
−
Теорема Маркова.
+
−
Связь между блочной чувствительностью и степенью многочлена (Нисан - Сегеди).
+
−
Связь между чувствительностью и степенью многочлена (Hao Huang), без доказательства.
+
  
−
==Семинары  ==
+
[https://drive.google.com/file/d/1OlSPOLeGPVLWzBQfoKc0-Rjfk6acN9aS/view?usp=sharing Видео]
  
−
=== Семинар 1 (15 января) ===
+
=== Семинар 4 (30 сентября). ===
−
[https://jamboard.google.com/d/15TB6_iZW1cd7wK5mGuzfJbE7vmBBCtbeMPPzjjEpF0M/edit?usp=sharing Доска]
+
−
[https://www.dropbox.com/s/zmh1pxi6bpuek1o/cw1.pdf?dl=0 Листок 1  (комбинаторные экспандеры)]
+
  
−
=== Семинар 2 (22 января) ===
+
[https://drive.google.com/file/d/1GhPxFQ_GIWEbJ1ybBemA4VLDQrjJGcm1/view?usp=sharing Листок 4]
−
[https://jamboard.google.com/d/1jFFFGM6vXwLYC3fbhpTb7ylc9ZFMU3U1HjJfSh9yr6M/edit?usp=sharing Доска] [https://www.dropbox.com/s/pu34evbm8y2maqe/cw_2.pdf?dl=0 Листок 2  (спектр графов)]
+
  
−
=== Семинар 3 (29 января) ===
+
[https://drive.google.com/file/d/1nupIT8_JSV5H6CqWKV8Z0pHmxYja-aU0/view?usp=sharing Видео]
−
[https://jamboard.google.com/d/13VaSk9iQs5XPvakLMuvLiCGmKA41E0Qey4c1HWNJIzo/edit?usp=sharing Доска] [https://www.dropbox.com/s/4pi5nlbw4xu9wmg/cw_3.pdf?dl=0 Листок 3 ]
+
  
−
=== Семинар 4 (5 февраля) ===
+
=== Семинар 5 (7 октября). ===
−
[https://jamboard.google.com/d/10Z44MB2F2occAHvqJ4PrSpQvlgFenAC6k4N7uJpXv5w/edit?usp=sharing Доска] [https://www.dropbox.com/s/7vnehil6djh8y79/cw_4.pdf?dl=0 Листок 4]
+
[https://drive.google.com/file/d/1EasLxzyJzXDh1frIFgeQOekyXd3gIdj1/view?usp=sharing Листок 5]
  
−
=== Семинар 5 (12 февраля) ===
+
[https://drive.google.com/file/d/1VTUWrPiuQPeZVu5MgwD-wnbhel5wZINA/view?usp=sharing Видео]
−
[https://jamboard.google.com/d/1mfGj2sLgBOpKfsZjvuahPzfJUk6wm5zhninahVDKUwo/edit?usp=sharing Доска] [https://www.dropbox.com/s/ihc3k6jregc9e6z/cw_5.pdf?dl=0 Листок 5]
+
  
−
=== Семинар 6 (19 февраля) ===
+
=== Семинар 6 (14 октября). ===
−
[https://jamboard.google.com/d/1h79fb2Nug016xprBRoD74ZDEeUAQ7sClfbrPGx0lTeI/edit?usp=sharing Доска] [https://www.dropbox.com/s/wupmaf9ynus9oxv/cw_6.pdf?dl=0 Листок 6]
+
[https://drive.google.com/file/d/1_Kj-BrIqTh2s9fwe3wKZEadnb19tsVkp/view?usp=sharing Листок 6]
  
−
=== Семинар 7 (26 февраля) ===
+
[https://drive.google.com/file/d/1oREJyL5W6ie-YpJWDofoeubyUR_ViWc9/view?usp=sharing Видео]
−
[https://jamboard.google.com/d/1rX6f9LyJ6SvhYmanIF84BG_bR6ZzMesnTlKY3uxifcQ/edit?usp=sharing Доска] [https://www.dropbox.com/s/7jkedcoj8g8p9p8/cw_7.pdf?dl=0 Листок 7]
+
  
−
=== Семинар 8 (5 марта) ===
 
  
−
[https://jamboard.google.com/d/1dyKtH9f1zdYCFDns83kxXHsYqONjdGxWpdw-uaAraGA/edit?usp=sharing Доска] [https://www.dropbox.com/s/ufbizzkfklhhmhz/cw_8.pdf?dl=0 Листок 8]
+
=== Семинар 7 (28 октября). ===
 +
[https://drive.google.com/file/d/1gZpbOT-MjSR4zmRDc-YLd0DREtYiOTLz/view?usp=sharing Листок 7]
  
−
=== Семинар 9 (12 марта) ===
+
[https://jamboard.google.com/d/1sjdGmo028dRy3KkwtTrTGD8AWWGqKASRQBVKQnXuOkg/edit?usp=sharing Доска]
−
[https://jamboard.google.com/d/1awQ5fqIkaENm91WkSoFXvrYEue65yiNu9Q0GXsgE9O0/edit?usp=sharing Доска] [https://www.dropbox.com/s/r8hz79f1fa1ndjs/cw_9.pdf?dl=0 Листок 9]
+
  
−
=== Семинар 10 (19 марта) ===
+
=== Семинар 8 (11 ноября). ===
−
[https://jamboard.google.com/d/1kjRHLzpG0HWqGPSnIlr-ZGWKzDPailwz87UlXoHj1Gc/edit?usp=sharing Доска] [https://www.dropbox.com/s/t6qfr25e8r8mduw/cw_10.pdf?dl=0 Листок 10]
+
  
−
=== Семинар 11 (26 марта) ===
+
[https://drive.google.com/file/d/1YccD_ZSVLHP2G2FGIPI58UhVNkldCwPM/view?usp=sharing Листок 8]
−
[https://jamboard.google.com/d/1oQXvMNVkZHETueXWy6USr2YpJKgT5AeuIj-IJ-CJjBA/edit?usp=sharing Доска] [https://www.dropbox.com/s/1aj3ypcq0t0kfkg/cw_11.pdf?dl=0 Листок 11]
+
  
 +
[https://jamboard.google.com/d/1bSlfEaQSwuarxgUiRjSfTNGntjAvZ6BJz9A7wPCStUM/edit?usp=sharing Доска]
  
−
=== Семинар 12 (9 апреля) ===
+
=== Семинар 9 (18 ноября). ===
−
[https://jamboard.google.com/d/1jTOBiX-gIAlsVdle6cEaHNL7Q9NCWQ_HRFhGCDfUTEo/edit?usp=sharing Доска] [https://www.dropbox.com/s/rlwh8uzn2r199ve/cw_12.pdf?dl=0 Листок 12]
+
  
−
=== Семинар 13 (16 апреля) ===
+
[https://drive.google.com/file/d/1IY2yyfvMckTiGsdIeVO5h8ViZWb8xlXL/view?usp=sharing Листок 9]
−
[https://jamboard.google.com/d/1hllQuFEhbXf8gF9MzuDzkrveCjr7KxmchwAekLknFL8/edit?usp=sharing Доска] [https://www.dropbox.com/s/fzaev9wgqszjrc1/cw_13.pdf?dl=0 Листок 13]
+
  
−
=== Семинар 14 (23 апреля) ===
+
[https://jamboard.google.com/d/1l3KEa2CN41mWOXJG0uSUbjUXo0W_qedb9rXc4DUL1Tg/edit?usp=sharing Доска]
−
[https://jamboard.google.com/d/106LwxU3Ka7TG8E3IM_LU8_fdAJzyKrlhKJaFtOQw1Wc/edit?usp=sharing Доска] [https://www.dropbox.com/s/iwzik10dli0msx8/cw_14.pdf?dl=0 Листок 14]
+
  
−
=== Семинар 15 (30 апреля) ===
+
=== Семинар 10 (25 ноября). ===
−
[https://jamboard.google.com/d/1Cd_lpV-O-Xc3_V-s_dOixN0D1CCqSk6sx9BunRX1A3U/edit?usp=sharing Доска] [https://www.dropbox.com/s/jt20v54p3g36shi/cw_15.pdf?dl=0 Листок 15]
+
  
−
=== Семинар 16 (14 мая) ===
+
=== Семинар 11 (2 декабря). ===
−
[https://jamboard.google.com/d/19A2vtH6NxD63mu8L94fy-zBw64lWsCjKzeo3hy7iZaI/edit?usp=sharing Доска] [https://www.dropbox.com/s/6689hmged6mq9s4/cw_16.pdf?dl=0 Листок 16]
+
  
−
=== Семинар 17 (21 мая) ===
+
[https://drive.google.com/file/d/1sAlOwMqDapIOBm0agWuLOySXpK8E4E4v/view?usp=sharing Листок 11]
−
[https://jamboard.google.com/d/1m9VRnjirxzsx6opLOkP4wAdiYJEFAdkTDEJdJykYYU0/edit?usp=sharing Доска] [https://www.dropbox.com/s/30nbn8qoey1sggu/cw_17.pdf?dl=0 Листок 17]
+
  
 +
[https://jamboard.google.com/d/1w82ftHffP4qQrBgFlAD7YsDq86ItuwApVvUNJu3F5v4/edit?usp=sharing Доска]
  
−
=== Семинар 18 (28 мая) ===
+
=== Семинар 12 (9 декабря). ===
−
[https://jamboard.google.com/d/10B76x8eCre_Bwz9a0rU8I0FcsalqLbsm_brLI19QLWU/edit?usp=sharing Доска] [https://www.dropbox.com/s/yzxt4cv4pcxctuo/cw_18.pdf?dl=0 Листок 18]
+
  
−
=== Семинар 19 (4 июня) ===
+
[https://drive.google.com/file/d/1cIfCxOwQ4l_HG4Gajhxw-jUB8qD_6C4L/view?usp=sharing Листок 12]
  
−
[https://jamboard.google.com/d/1YPP85Y37bfS_rULYUxhKSxSeoLaAXNtbP_MaAJfAoxo/edit?usp=sharing Доска] [https://www.dropbox.com/s/hlm2xgdiypk1ypz/cw_19.pdf?dl=0 Листок 19]
+
[https://jamboard.google.com/d/1DX41VBYy66VT-xlDic9006ek9yrYkmQgSJbVYvvOJWI/edit?usp=sharing Доска]
−
 
+
−
=== Семинар 20 (11 июня) ===
+
−
 
+
−
[https://jamboard.google.com/d/1UcyZ7H8K_nxVCNZkexqXTxQrbVQ633QzHNbYgnto6L4/edit?usp=sharing Доска] [https://www.dropbox.com/s/9h46829jva4gat3/cw_20.pdf?dl=0 Листок 20]
+
  
 
==Конспекты лекций==
 
==Конспекты лекций==
−
[https://www.dropbox.com/s/1fl4vg99nblb9yo/vereshchagin-revised.pdf?dl=0 Конспекты лекций об экспандерах, полученные переработкой книги Ромащенко]
 
  
−
[https://www.dropbox.com/s/y4vifj9lzd5xic8/DecisionTrees.pdf?dl=0 Конспект лекций о деревьях разрешения.]
+
[https://www.dropbox.com/s/tgb6ipbgd9wfpre/lectures.pdf?dl=0 В этой незаконченной книге есть все, что будет на лекциях.]
  
−
[https://www.dropbox.com/s/2uw24ocj405b3yu/main.pdf?dl=0 Конспект лекций о кодах с исправлением ошибок] (переработанная версия брошюры Ромащенко, Румянцева, Шеня. "Заметки по теории кодирования."
+
==Рекомендуемая литература  ==
  
−
[https://www.dropbox.com/s/exx1jyype7dks5b/sensitivity.pdf?dl=0 Sensitivity for dummies (решение  Sensitivity conjecture).]
+
0. Китаев А., Шень А., Вялый М.
Классические и квантовые вычисления. 
Изд-во МЦНМО.
 

−
 
+
−
==Рекомендуемая литература  ==
+
  
−
[https://www.mccme.ru/~anromash/courses/expanders-notes-2014.pdf А.Е. Ромащенко. Экспандеры: конструкции и приложения.]
+
1. Введение в криптографию. Под общей редакцией В.В.Ященко. ---
3-е изд. доп. --- М.: МЦНМО: "ЧеРо", 2000. --- 288 с.

 +


  
−
[https://www.researchgate.net/publication/2508255_On_the_Degree_of_Boolean_Functions_as_Real_Polynomials Noam Nisan, Mario Szegedy. On the Degree of Boolean Functions as Real Polynomials. Computational Complexity 4(4) · January 1995]
+
2. М.И. Анохин, Н.П.Варновский, В.М.Сидельников, В.В. Ященко.
Криптография в банковском деле. М.: МИФИ, 1997.


  
−
N. Nisan, CREW PRAM's and decision trees, STOC 1989, pages 327-335.
+
3. O. Goldreich.
Foundations of cryptography. Basic tools.
Cambridge Univ. Press. 2001. 400 p.


  
−
Alexander Razborov, Nikolay Vereshchagin. One Property of Cross-Intersecting Families. ECCC TR99-014. https://eccc.weizmann.ac.il/report/1999/014/
+
4. O. Goldreich.
Foundations of cryptography. Basic applications.
Cambridge Univ. Press. 2004.

Версия 10:20, 22 января 2022

Содержание

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

Лекции проходят по четвергам 14:40 - 16:00 онлайн https://zoom.us/j/92459176488?pwd=bWRGamhPY0twR2VJdDhvNHVFSEZpZz09 Идентификатор:92459176488 Код доступа: 180250

Новости

Пересдача пройдёт в Google meet: meet.google.com/hee-kmku-asd

  • Выложены решения задач экзамена. Присланные решения проверены и оценки с критериями их выставления занесены в общую ведомость. Апелляции принимаются лектором (5 и 7 задачи) и семинаристом (остальные задачи) через Телеграм 23 и 24 декабря.
  • Письменный экзамен начнется 23 декабря с 10:00 онлайн с прокторингом и будет продолжаться 90 минут. Подключиться к конференции

https://zoom.us/j/98778960078?pwd=RVJzMHNYK2R1Y2FmMldJanVwYitCQT09 надо в 9:50.

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

Запись лекции 28.10.2

  • Срок сдачи второго ДЗ перенесен на 7 ноября.
  • Выложено второе домашнее задание.
  • Семинар пройдёт 30 сентября вместо лекции (в 14.40 в D725).
  • Выложено первое домашнее задание.
  • Лекция 30 сентября отменяется!
  • Семинар 15 сентября будет онлайн. Ссылка: meet.google.com/itr-jufj-bxb

Контакты

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


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

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

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

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

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

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

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

Сдать ДЗ лектору можно с помощью Google Meet https://meet.google.com/noy-cait-jph

Сдать ДЗ семинаристу можно ... .

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

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

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

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

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

Коллоквиум

Коллоквиум будет 16 декабря в 14:30. Программа коллоквиума.

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

Экзамен

Письменный экзамен будет 23 декабря с 10:00 онлайн с прокторингом и будет продолжаться 90 минут. Более подробная инструкция тут:

1. Экзамен письменный и проходит с прокторингом через Зум: https://zoom.us/j/98778960078?pwd=RVJzMHNYK2R1Y2FmMldJanVwYitCQT09 Присоединиться к конференции надо на десять минут раньше, то есть, в 9:50. В 10:00 станут доступны задания, которые надо загрузить по ссылке в чате конференции. Студенты решают задания на бумаге, в конце экзамена делают фотографии/сканы решений и посылают на адрес nikolay.vereshchagin@gmail.com. Черновики отсылать не надо. Крайний срок посылки - 15 мин после конца экзамена.

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

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


Присланные решения проверены и оценки с критериями их выставления занесены в общую ведомость. Апелляции принимаются лектором (5 и 7 задачи) и семинаристом (остальные задачи) через Телеграм (23 и 24 декабря).

Пересдачи

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

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

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

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

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

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

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

Домашнее задание 1 Cрок сдачи 14 октября.

Домашнее задание 2 Срок сдачи 7 ноября.

Домашнее задание 3 Срок сдачи 5 декабря.

Домашнее задание 4 Срок сдачи 19 декабря.

Результаты

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

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

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

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

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

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


Лекция 3 (16 сентября).

Функция Рабина
, функция RSA и дискретная экспонента.

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

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

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


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

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

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

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



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

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

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

Построение генератора ПСЧ из односторонней перестановки.

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

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


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


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

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


Лекция 11 (2 декабря).

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


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

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



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

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

Семинары

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

Листок 1

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

Листок 2

Видео

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

Листок 3

Видео

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

Листок 4

Видео

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

Листок 5

Видео

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

Листок 6

Видео


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

Листок 7

Доска

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

Листок 8

Доска

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

Листок 9

Доска

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

Семинар 11 (2 декабря).

Листок 11

Доска

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

Листок 12

Доска

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

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

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

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.

Источник — «http://wiki.cs.hse.ru/index.php?title=OWF2021&oldid=64708»