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_21%2F22 2026-06-06T12:34:11Z История изменений этой страницы в вики 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_21/22&diff=1171&oldid=prev 2024-04-14T06:51:09Z

<p>Migrated current public revision from wiki.cs.hse.ru</p> <p><b>Новая страница</b></p><div>== О курсе ==<br /> Курс посвящён относительно новому направлению в криптографии–криптографии на решётках, которая известна также как постквантовая криптография. Как всегда, в основе криптографических протоколов лежит некоторая алгоритмически сложная задача. Здесь роль такой задачи выполняет задача о поиске кратчайшего вектора в решётке большой размерности. Все известные алгоритмы поиска короткого вектора имеют экспоненциальную (в зависимости от размерности) сложность. Поэтому, выбирая размерность достаточно большой (например, 1000), можно полагаться на стойкость криптосистем.<br /> <br /> В первой части курса будет дано краткое введение в геометрию чисел. Будет рассказано о решётках и их основных свойствах. Затем мы с разных сторон посмотрим на задачу о поиске короткого вектора в данной решётке. В частности, мы изучим алгоритм Эрмита, который можно рассматривать как предварительную версию LLL-алгоритма.<br /> <br /> Главная цель курса – познакомиться с LLL-алгоритмом – первым алгоритмом поиска короткого вектора, для которого удалось доказать полиномиальную сложность. Этот алгоритм позволил решать самые разнообразные задачи, но все его приложения останутся за границами курса.<br /> <br /> В заключение мы познакомимся с тем, как устроены криптографические протоколы на решётках, и поймём, зачем вообще надо искать короткие векторы.<br /> <br /> Лектор — [https://www.hse.ru/org/persons/530309935 Устинов Алексей Владимирович ]<br /> <br /> == Лекции ==<br /> <br /> Проходят по вторникам 16:20 - 17:40 в R503. <br /> <br /> == План занятий ==<br /> <br /> 1. Решётки и их свойства. Матрица Грама.<br /> <br /> 2. Теорема Минковского о выпуклом теле. Процесс ортогонализации Грама-Шмидта. Укороченные базисы.<br /> <br /> 3. Минимумы Минковского. Константы Эрмита. Алгоритм Лагранжа построения приведённого базиса в двумерной решётке. Вычисление константы Эрмита в размерности. Неравенство Эрмита.<br /> <br /> 4. Алгоритмы Эрмита. LLL-приведённые базисы и их свойства. LLL-алгоритм.<br /> <br /> 5. Криптографические протоколы на решётках<br /> <br /> [https://drive.google.com/file/d/1iB0xESfwbN2H4hr8m_ebXTBZFADHXYdF/view?usp=sharing Черновик первых лекций]<br /> <br /> == Контрольные мероприятия ==<br /> <br /> === Экзамен ===<br /> 1 . Решётки и их свойства.<br /> <br /> 2. Матрица Грама.<br /> <br /> 3. Теорема Минковского о выпуклом теле.<br /> <br /> 4. Процесс ортогонализации Грама - Шмидта.<br /> <br /> 5. Минимумы Минковского. Константа Эрмита.<br /> <br /> 6. Алгоритм Лагранжа построения приведённого базиса в двумерной решётке.<br /> <br /> 7. Вычисление константы Эрмита в размерности 2.<br /> <br /> 8. Неравенство Эрмита. Алгоритм Эрмита.<br /> <br /> 9. LLL-приведённые базисы и их свойства.<br /> <br /> 10. LLL-алгоритм.<br /> <br /> 11. Применение LLL-алгоритма к решению задачи о сумме подмножеств.<br /> <br /> Дополнительно требуется уметь доказывать свойства LLL-приведённых базисов (задача 5.23 из файла).<br /> <br /> === Правила выставления оценок ===<br /> <br /> == Список литературы ==</div>

imported>Ustinov