#дневниклекций
Вчера на лекции закончили доказательство теоремы о преобразовании односторонней перестановки в генератор псевдослучайных чисел. Было вот что:
- Повторение общего плана доказательства с конструкциями. Названия утверждений: теорема Голдрайха-Левина (построение трудного бита), XOR-лемма Яо (дописывание трудного бита создаёт генератор n->n+1), теорема Блюма-Микали (итерирование предыдущей конструкции даёт генератор n->p(n)).
- Общее понятие о кодах, исправляющих ошибки. Расстояние Хэмминга (доля отличающихся битов), модель возникновения ошибок (заведомо не больше какого-то количества), области применения (пример - кодирование данных на компакт-диске)
- Код Уолша-Адамара (WH(x) - скалярные произведения x⊙y для всех y). Две интерпретации: значения всех линейных функций на x и таблица истинности линейной функции с коэффициентами x. Если x≠0, то WH(x) содержит поровну 0 и 1. Если x≠y, то WH(x) и WH(y) совпадают в половине координат.
- Декодирование: если w это правильный код, а w^ испорчен менее, чем в четверти битов, то w можно восстановить однозначно.
- Декодирование списком (б/д): если w^ отличается от w в доле 1/2-ε, то можно написать список размера poly(1/ε), в котором точно есть w.
- Связь с теоремой Голдрайха-Левина. Мы доказываем, что x⊙y трудный бит для (F(x), y). Доказываем контрапозицию: если бит не трудный, то можно обратить F. Пусть есть предсказатель бита: по (F(x),y) угадываем x⊙y. Набор по всем y даст некоторый испорченный код w^. Мы его будем декодировать.
- Настоящий бит x_i это конкретный бит кода x⊙e_i, его мы и будем восстанавливать. Пусть настоящий w это таблица функции f, а испорченный w^ это таблица функции f^. Идея самокоррекции: f(z)=f(z+r)+f(r) (все плюсы по модулю 2). Посмотрим на f^(z+r)+f^(r). Если f^ отличается от f менее, чем в четверти случаев, то f^(z+r)+f^(r) совпадёт с f(z+r)+f(r) больше, чем в половине случаев, т.е. для большинства r даст правильный ответ.
- Однако четверти отличий нам никто не обещал, обещали 1/2-ε. Идея такая - будем брать лишь попарно независимые r_j и смотреть на большинство из f^(z+r_j)+f(r_j). ЗБЧ для попарно независимых величин говорит, что полинома r_j достаточно.
- Но f(r_j) мы не знаем. Вместо этого используем ограниченный перебор. Генерируем независимые u_1,...,u_l и в качестве r_j берём всевозможные суммы какого-то числа u_q. Тогда значения f(u_q) дают все f(r_j), величин r_j экспоненциально много по сравнению с u_q и потому перебор полиномиально ограниченный (порядка числа r_j).
- Ещё нужно перейти от вероятности по (x,y) к вероятности только по y. Тут подсчёт такой: если общая вероятность успешного предсказания 1/2+ε, то для доли ε/2 от всех x вероятность по y хотя бы 1/2+ε/2, вот для этих x и будем обращать F(x).
- Итоговый обратитель: перебираем все варианты f(u_q), считаем по ним f(r_j), считаем f(z) как большинство f^(z+r_j)+f(r_j) для всех z=e_i. Из этих результатов собираем x и проверяем, что оно правильное. Если x хороший, то с вероятностью 1/2 на правильном шаге перебора восстановим x, а потому F не односторонняя.

В следующий раз изучим псевдослучайные функции и может быть начнём шифрование.