Лекция
Курс о фундаментальных основах криптографии.
Курс о фундаментальных основах криптографии.
Курс о фундаментальных основах криптографии.
Предмет и история криптографии. Криптографические атаки. Криптографические примитивы: хеш–функции, протоколы с секретным и открытым ключом.
Криптография с закрытым ключом
Поточные шифры: линейные сдвиговые регистры, линейная сложность функций, нелинейные сдвиговые регистры. Блочные шифры: ECB, CBC...
Криптография с открытым ключом I
Криптография с открытым ключом II.
Криптосистемы, основанные на частных случаях NP–трудных проблем. Коды, исправляющие ошибки. Линейные коды, коды Гоппы, NP–...
Решётки в криптографии
Лекция 1. Недетерминированные машины Тьюринга. Классы P и NP. Оптимальный алгоритм Левина. Сводимости, NP-полнота.
Лекция 2. NP-полнота задач CIRCUIT-SAT и SAT. Сведение поиска к распознаванию. Существование не NP-полной не полиномиально разрешимой задачи в NP.
Лекция 3. Оракульные вычисления. Полиномиальная иерархия. Полнота задачи . Теоремы о коллапсе. Семейства схем полиномиального размера. Коллапс полиномиальной...
Лекция 4. Вычисления с ограничениями по памяти. Схемы полилогарифмической глубины.
Лекция 5. PSPACE-полнота задачи QBF. Иерархии DSpace, DTime, NTime.
RSA
Генерация случайных простых чисел. Криптография: схемы с закрытым ключом, RSA.
Страница лекции на сайте Computer Science Center
Лекция 6. Вероятностные алгоритмы.
Лекция 7. Интерактивные протоколы.
Лекция 8. Сложность в среднем. Односторонние функции.
Лекция 9. Трудный бит. Псевдослучайный генератор.
Лекция 10. Односторонние функции с секретом, криптосистемы с открытым ключом.
Лекция 11. Цифровые подписи.
Сочетающиеся вектора. Коды из сочетающихся векторов. Конструкция. Семейства сочетащихся векторов. Приложения локально декодируемых кодов в криптографии (...
Вероятностные классы сложности
Вероятностная машина Тьюринга. Классы BPP и RP. Лемма Шварца-Зиппеля и вероятностный тест равенства двух многочленов. Понижение...
Интерактивные протоколы
BPP содержится в ΣP2 ∩ ΠP2. Интерактивные протоколы. Примеры: интерактивный протокол для неизоморфизма графов. Теорема Шамира (IP =...
Игры Артура и Мерлина
Подсчет числа подсказок. Лемма Вэлианта-Вазирани
Лемма Вэлианта-Вазирани. И ее ⨁-версия. Операции с числом выполняющих наборов и следствия из них. ⨁⨁-версия...
Теорема Тода. Схемная сложность класс PP
Классы sharp P и PP. Теорема Тода. P^{PP} = P^{sharp P}. Теорема Вэлианта о sharp-P -полноте 0/1 перманента (без...
Вероятностно проверяемые доказательства
Приближенные алгоритмы для задачи MAXSAT и минимальном вершинном покрытии. Вероятностно проверяемые доказательства....
Экспоненциальная PCP-теорема
NP⊆PCP(poly(n),1). Базис Фурье для булевых функций. Тестирование функции на линейность.
Страница лекции на сайте Computer Science...
Односторонние функции
Генератор псевдослучайных чисел
Трудный бит. Псевдослучайные функции
Построение трудного бита для односторонних перестановок. Декодирование списком кодов Уолша-Адамара. Конструкция семейства...
Протоколы с секретным и открытым ключом
Привязка к биту. Доказательства с нулевым разглашением
Интерактивный протокол привязки к биту. Стратегии, разглашающие только f(x). Разглашение при...
Введение в криптографические примитивы
Введение. Предмет и история криптографии. Виды криптографических атак. Чем вообще занимается криптография сегодня? Виды...
Протоколы с секретным ключом
Криптография с секретным ключом. Как использовать один и тот же ключ много раз? Блочные шифры: ECB, CBC, CFB, OFB. Имитовставки.
Другие задачи криптографии
Oblivious transfer: протокол Рабина, 1–2–OT протокол, их эквивалентность. Секретное вычисление функции. Бросание монетки в колодец,...
Эллиптические кривые в криптографии
Групповой закон на эллиптических кривых. Алгоритм Ленстры (ECM) на эллиптических кривых. Вычисления на эллиптических кривых...
Протоколы согласования ключа
Криптография с открытым ключом: протоколы согласования ключа. Протокол Диффи-Хеллмана. AKEP, протокол Шамира, протокол Отвея-Рииса...
Лекция 6. Энтропия в классической криптографии.
Оценка Шеннона для длины ключа в симметричной схеме шифрования. Схемы совершенного разделения секрета....
Генератор псевдослучайных чисел из односторонней перестановки