https://wikicshse.ru/index.php?action=history&feed=atom&title=%D0%9A%D1%80%D0%B8%D0%BF%D1%82%D0%BE%D0%B3%D1%80%D0%B0%D1%84%D0%B8%D1%8F_%D0%BD%D0%B0_%D1%80%D0%B5%D1%88%D1%91%D1%82%D0%BA%D0%B0%D1%85_24%2F25 2026-06-06T17:07:34Z История изменений этой страницы в вики MediaWiki 1.45.3 https://wikicshse.ru/index.php?title=%D0%9A%D1%80%D0%B8%D0%BF%D1%82%D0%BE%D0%B3%D1%80%D0%B0%D1%84%D0%B8%D1%8F_%D0%BD%D0%B0_%D1%80%D0%B5%D1%88%D1%91%D1%82%D0%BA%D0%B0%D1%85_24/25&diff=1173&oldid=prev 2025-12-27T13:34:10Z

<p>Migrated current public revision from wiki.cs.hse.ru</p> <p><b>Новая страница</b></p><div>= О курсе =<br /> <br /> <br /> <br /> В 2016 г. Национальный институт стандартов и технологий США (NIST) объявил о программе и конкурсе по обновлению своих стандартов для того, чтобы включить в них постквантовую криптографию, т. е. такие криптосистемы, которые оставались бы стойкими даже после появления квантовых компьютеров, см [https://en.wikipedia.org/wiki/NIST_Post-Quantum_Cryptography_Standardization NIST Post-Quantum Cryptography Standardization]. После трёх туров отбора в финал вышло 7 криптосистем, из которых 5 основаны на решётках.<br /> <br /> Курс посвящён именно этому новому направлению в криптографии – криптографии на решётках. Как всегда, в основе криптографических протоколов лежит некоторая алгоритмически сложная задача. Здесь роль такой задачи выполняет задача о поиске кратчайшего вектора в решётке большой размерности. Все известные алгоритмы поиска короткого вектора имеют экспоненциальную (в зависимости от размерности) сложность. Поэтому, выбирая размерность достаточно большой (например, 1000), можно полагаться на стойкость криптосистем.<br /> <br /> В первой части курса будет дано краткое введение в геометрию чисел. Будет рассказано о решётках и их основных свойствах. Затем мы с разных сторон посмотрим на задачу о поиске короткого вектора в данной решётке. В частности, мы изучим алгоритм Эрмита, который можно рассматривать как предварительную версию LLL-алгоритма.<br /> <br /> Главная цель курса – познакомиться с LLL-алгоритмом – первым алгоритмом поиска короткого вектора, для которого удалось доказать полиномиальную сложность. Этот алгоритм позволил решать самые разнообразные задачи, но все его приложения останутся за границами курса.<br /> <br /> В заключение мы познакомимся с тем, как устроены криптографические протоколы на решётках, и поймём, зачем вообще надо искать короткие векторы.<br /> <br /> Лектор — [https://www.hse.ru/org/persons/530309935 Устинов Алексей Владимирович]<br /> <br /> === Ассистент ===<br /> <br /> [https://t.me/dsolunov Данила Солунов]<br /> <br /> == Лекции ==<br /> <br /> Лекция 1 (04.04.2025) Решётки и их свойства. Матрица Грама. [ГН] Теорема Минковского о выпуклом теле.<br /> <br /> Лекция 2 (11.04.2025) Процесс ортогонализации Грама — Шмидта. Минимумы Минковского. Константа Эрмита. [LLL+]<br /> <br /> Лекция 3 (18.04.2025) Оценка констант Эрмита с помощью теоремы Минковского. Приведённые по Лагранжу базисы. Алгоритм Лагранжа. Неравенство Эрмита (два доказательства). [LLL+]<br /> <br /> Лекция 4 (25.04.2025) Алгоритм Эрмита (два варианта). Свойства базиса, приведённого по Эрмиту. LLL-приведённые базисы. Три интерпретации условия Ловаса. LLL-алгоритм. Оценка числа шагов LLL-алгоритма. [LLL+]<br /> <br /> Лекция 5 (02.05.2025) Задача о подмножестве с данной суммой. Криптосистема Меркла — Хеллмана. Линейные коды. Порождающая и проверочная матрицы. Минимальное расстояние кода. Код Хемминга. Синдром кодового слова. Задача декодирования. Задача декодирования синдрома.<br /> <br /> Лекция 6 (16.05.2025) Двойственные коды. Эквивалентность задач декодирования слова и декодирования синдрома. Криптосистемы Мак-Элиса и Нидеррайтера. Алгоритмически сложные задачи на решётках.<br /> <br /> Лекция 7 (23.05.2025) Криптосистема, основанная на сравнениях. Прототип системы полного гомоморфного шифрования. Алгоритм Бабая. Криптосистема GGH (Goldreich — Goldwasser — Halevi).<br /> <br /> Лекция 8 (30.05.2025) Дискретное преобразование Фурье. Криптосистема PASS.<br /> <br /> == Домашние задания ==<br /> <br /> <br /> <br /> [https://drive.google.com/file/d/1aN3o7GWGIACtXeLvT3gXQ7icbNmjREs5/view?usp=sharing ДЗ-1] <br /> [https://drive.google.com/file/d/17wajLJlCICOBX4gqz-1isKF2735pKvLi/view?usp=sharing ДЗ-2] [https://drive.google.com/file/d/1LqHySgvBVW237NXpsoxDh2Xnfewx0nid/view?usp=sharing ДЗ-3] [https://drive.google.com/file/d/1noJ4ba1RmHbbkMp4glx2KwxTj_epJdWR/view?usp=sharing ДЗ-4] [https://drive.google.com/file/d/1bO7hoVEVEoza8K5hL4-JeeUn5LMYKgYm/view?usp=sharing ДЗ-5] [https://drive.google.com/file/d/12fOvdOSFmzQemniogGJfIQkwca8WZOhe/view?usp=sharing ДЗ-6][https://drive.google.com/file/d/1SclHpFXpOcMZApZp3uJPGdHnrRkmHqch/view?usp=sharing ДЗ-7]<br /> <br /> &lt;!--<br /> --&gt;<br /> <br /> === Правила сдачи заданий ===<br /> <br /> В домашнем задании каждая задача оценивается в 10 баллов. Баллы за задачи суммируются и линейно шкалируются на 10-балльную шкалу без округления. Итоговая оценка за ДЗ получается усреднением оценок по всем ДЗ (без округления). Округление происходит только в конце при вычислении итоговой оценки за курс.<br /> <br /> == Экзамен ==<br /> <br /> 13.06.2025 На экзамен можно принести собственноручно написанную шпаргалку - лист А4.<br /> <br /> == Оценка ==<br /> <br /> Итоговая оценка=0.5*экзамен + 0.5*ДЗ (округляется арифметически).<br /> <br /> == Полезные материалы ==<br /> ===Основные источники===<br /> # [ГН] [http://new.math.msu.su/department/number/dw/lib/exe/fetch.php?media=%D1%82%D1%87%D0%BC%D0%BA.pdf Герман О. Н., Нестеренко Ю. В. Теоретико-числовые методы в криптографии. 2012 ]<br /> # [HS] [https://libgen.li/edition.php?id=28163895 Hoffstein J., Pipher J., Silverman J. H. An introduction to mathematical cryptography. 2008 ]<br /> # [LLL+] [https://libgen.li/edition.php?id=136753335 Nguyen Phong Q., Vallée Brigitte (ed.) The LLL algorithm. Survey and applications. 2010 ]<br /> <br /> ===Дополнительные материалы===<br /> <br /> # Конвей Дж., Слоэн Н. Упаковки шаров, решетки и группы (в 2 томах), 1990. [https://libgen.li/edition.php?id=135785023 том 1], [https://libgen.li/edition.php?id=135785024 том 2].<br /> # Берлекэмп Э. Алгебраическая теория кодирования, 1971.<br /> # Блейхут Р. Теория и практика кодов, контролирующих ошибки, 1986.<br /> # Bremner M. R. Lattice basis reduction. An introduction to the LLL algorithm and its applications. 2012 <br /> # [LLL] [https://www.cs.cmu.edu/~avrim/451f11/lectures/lect1129_LLL.pdf Lenstra A. K., Lenstra H. W. jun., Lovász L. Factoring polynomials with rational coefficients. Math. Ann., Vol. 261 (1982), 515-534.]<br /> # Micciancio D., Goldwasser Sh. [https://libgen.li/edition.php?id=136697143 Complexity of Lattice Problems: a cryptographic perspective 2002] <br /> # Milnor J., Husemoller D. [https://libgen.li/edition.php?id=135780681 Symmetric bilinear forms 1973 ]<br /> # Silverman J. H. [https://www.ntwebseminar.org/previous-talks#h.nc99vbqpdgq8 &quot;More Tips on Keeping Secrets in a Post-Quantum World: Lattice-Based Cryptography&quot;] (Обзорная лекция + криптосистемы GGH и PASS)<br /> # [https://www.youtube.com/@tanjalangepost-quantumcryp2802 Tanja Lange: Post-quantum cryptography] (серия лекций на YouTube)</div>

imported>Ustinov