#дневниклекций
В прошлый раз мы подробно обсудили конструкцию трудного бита и начали псевдослучайные функции. Вот что было:
- Пусть есть f(x) и доступ к вычислению трудного бита с ошибкой. Нужно найти x. Если ошибка нулевая, то биты x просто берутся из значений трудного бита.
- Если ошибка меньше 1/4-ε, то для поиска x_i можно взять случайную самокоррекцию g(e_i+r)-g(r) и амплифицировать, где g - трудный бит с шумом.
- Если ошибка меньше 1/2-ε, то нужно брать большинство из g(e_i+r)-h(r), где g - трудный бит с шумом, h - без шума.
- Мы не знаем значений h(r), вместо этого мы доказываем, что можно взять только попарно независимые r (ЗБЧ для попарно независимых величин).
- Можно построить полиномиальное число попарно независимых r_j из логарифмического числа истинно независимых u_k через всевозможные суммы. При этом h(u_k) однозначно определит h(r_j) по линейности.
- Теперь можно перебрать все возможные h(u_k) и по каждому попробовать восстановить x. Мы можем проверить, правильно ли восстановили, вычислив f(x). Ещё нужно аккуратно оценить вероятности, чтобы вероятность успеха была существенной.
В конце обсудили псевдослучайные функции:
- Неформальное понятие псевдослучайной функции, неадаптивные и адаптивные отличители
- Почему недостаточно просто взять генератор и запустить много раз
- Определение семейства ПСФ в слабом и сильном смысле, построение примера, псевдослучайного в слабом, но не в сильном смысле (без требования эффективной вычислимости)
Сегодня будем строить ПСФ из генераторов. Может быть, успеем начать шифрование.
3October 14, 2025 1.1K
