#дневниклекций
Сегодня почти всю лекцию потратили на теорему об усилении. Вот рассказ подробнее:
- Напоминание: сильно и слабо односторонние функции, конструкция сильно односторонней F из слабо односторонней f, устойчивость относительно наивных обратителей
- Идеи, как использовать любой обратитель F для обращения f: подстановка вместо первого аргумента, многократный повтор, подстановка вместо любого аргумента.
- Псевдокод для итогового обратителя f.
- Доказательство успешности обратителя f: разделение аргументов на трудные и лёгкие, две леммы о вероятностях успехов двух обратителей, выбор параметров, приводящих к противоречию.
- Общие рассуждения о парадигме доказательной криптографии, анонсы её будущих применений в теоремах курса.
- Понятие односторонней перестановки и анонс результата о генераторах ПСЧ.