#дневниклекций
Краткое содержание прошлой и сегодняшней лекций:
- Односторонние перестановки с секретом (точнее, их семейства). Определение через 4 вероятностных алгоритма: генератор ключей, сэмплер, вычислитель и обратитель. Генератор возвращает пару (индекс, секрет), сэмплер возвращает случайный элемент области определения, вычислитель вычисляет перестановку, обратитель обращает при известном секрете. Определение труднообратимости без знания секрета.
- Примеры предположительно односторонних перестановок с секретом на базе функций Рабина и RSA.
- Общая идея, как используются односторонние перестановки с секретом в асимметричной криптографии.
- Понятие о генераторах случайных чисел. Генераторы истинной случайности и псевдослучайности. Борьба генераторов и тестов случайности. Улучшение качества случайности при помощи экстракторов.
- Виды близости случайных величин (точнее, их последовательностей - ансамблей). Статистическое расстояние между величинами и 2 его определения. Статистическая близость и её эквивалентность неотличимости никакими тестами. Вычислительная неотличимость (неотличимость простыми тестами). Всё это - отношение эквивалентности.
- Формальное определение ГПСЧ. Теорема: если существуют ГПСЧ, то существуют односторонние функции (например, сам ГПСЧ).
- Обратная теорема: если существуют односторонние функции, то существуют ГПСЧ (б/д). Более простая версия: если существуют односторонние перестановки, то существуют ГПСЧ.
- Общая конструкция доказательства: построение односторонней перестановки с трудным битом, построение из неё генератора n->n+1, построение генератора n->p(n)
- Формальное определение трудного бита.
- Вторая часть теоремы (XOR-лемма Яо): если g - односторонняя перестановка, а h - трудный бит, то G(x)=g(x)h(x) - генератор. Доказательство через преобразование отличителя строк в предсказатель последнего бита.
- Третья часть теоремы: итерация предыдущей конструкции. Построение генератора n->n+2: G(x)=g(g(x))h(g(x))h(x). Построение гибридного генератора, доказательство неотличимости нашего от гибридного, а гибридного от случайной строки. Обобщение на полиномиальную длину, некорректность рассуждения по транзитивности и его исправление.

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