#дневниклекций
Сегодня, как и планировалось, разбирали ПСФ и немного шифрование:
- Семейства псевдослучайных функций. Интуитивное определяющее свойство: случайная функция из семейства неотличима от случайной вообще.
- Технические требования к ПСФ: малый размер и полиномиальная вычилимость.
- Слабая псевдослучайность: значения в заданном полиномиальном числе точек вычислительно неотличимы от случайных битов.
- Пример, когда слабая псевдослучайность есть, но интуитивно функция явно отличается от случайной (без требований малого размера и эффективной вычислимости).
- Сильная псевдослучайность (относительно адаптивных отличителей).
- Конструкция ПСФ из ГПСЧ n->2n: двоичное дерево строк, порождённое генераторами. Индекс функции - исходное слово, аргумент - ветка в дереве. Интуитивное объяснение, почему это ПСФ, а также почему перестановка индекса и аргумента даст не ПСФ.
- Объяснение, почему значение на одном слове неотличимо от случайного. Рассуждение с гибридными генераторами: на каком-то уровне заменяем выходы генераторов на случайные слова, дальше продолжаем с генераторами. Обобщение на несколько слов, вывод о слабой псевдослучайности.
- Обсуждение, почему будет и сильная псевдослучайность, но без доказательства.
- Общая задача шифрования с закрытым и открытым ключом
- Простейшая схема шифрования - гаммирование (одноразовый блокнот). Её достоинства и недостатки.