\documentclass[12pt]{article}
\usepackage{russcorr}
\usepackage{amsmath}
\usepackage{amstext}
\addtolength{\textheight}{.5cm}
%\usepackage{fullpage}

\newcounter{вопрос}
\newcommand{\вопрос}{\refstepcounter{вопрос}%
\noindent\theвопрос. }

\newcommand{\poly}{\text{poly}}

\newlength{\newwidth}
\setlength{\newwidth}{.5\textwidth}

\pagestyle{empty}

\begin{document}

\begin{center}
{\large\textbf{Программа экзамена по курсу
``Теоретико-сложностные проблемы в криптографии''. Вторая часть:
необратимые функции и криптографические протоколы (схемы)}}
\end{center}

Чтобы получить 3 или 4 достаточно знать определения, построение
всех схем (протоколов) и формулировки теорем.
Чтобы получить 5 надо знать также и доказательства.


\medskip
\вопрос  Генераторы псевдослучайных чисел (расширители):
два определения и теорема Яо
об эквивалентности этих двух определений.

\вопрос Построение генератора, растягивающего случайное зерно из
$n$ битов в псевдослучайную последовательность из
$\poly(n)$ битов на основе  произвольного
генератора, растягивающего случайное зерно из
$n$ битов в псевдослучайную последовательность из $n+1$ бита.

\вопрос Необратимые функции. Определение и три основных
предположительно необратимых функции:
возведение в степень по простому модулю, функция RSA, функция
Рабина.

\вопрос Слабо необратимые функции. Построение необратимой функции из
слабо необратимой функции.

\вопрос Построение генератора псевдослучайных чисел
на основе любой необратимой перестановки.

\вопрос Теорема об эквивалентности
гипотезы о существовании генератора и
гипотезы о существовании необратимой функции (в одну сторону
без доказательства).

\вопрос Два определения надежной схемы шифрования с закрытым ключом.
Эквивалентность этих определений.

\вопрос Построение надежной схемы шифрования с закрытым ключом	
на основе генератора.

\вопрос Необратимые перестановки с секретом.
Определение и две
основных
предположительно необратимх перестановки с секретом:
функция RSA, функция
Рабина.

\вопрос 
Определение надежной схемы шифрования с открытым ключом.
Построение такой схемы на основе необратимой перестановки с
секретом.

\вопрос Интерактивные доказательства и класс IP.
Последовательное повторение интерактивного доказательства уменьшает
вероятность ошибки.


\вопрос Интерактивное доказательство неизоморфности данных графов.

\вопрос Интерактивные доказательства с нулевым разглашением.
Доказательство с нулевым разглашением  изоморфности данных графов.

\вопрос Определение надежной схемы аутентификации.
Построение такой схемы в предположении
необратимости функции Рабина, функции возведения
в степень по простому модулю или функции, дающей по данному графу и
данной перестановке его вершин исходный граф и
граф с переставленными вершинами.

\вопрос Определение надежного протокола 
``запечатывания конверта'' (bit committment).
Построение такого протокола на основе
генератора псевдослучайных чисел.

\вопрос Определение надежной схемы бросания монетки по телефону.
Построение такой схемы на основе схемы ``запечатывания конверта''.

\вопрос Определение надежной схемы
цифровой подписи.
Определение универсального семейства односторонних хэш-функций.
Схема цифровой подписи Наора и Юнга на основе необратимой функции и
универсального семейства односторонних хэш-функций (без доказательства).

\bigskip

{\bf Литература.}

1. M. Гэри, Д. Джонсон. Вычислительные машины и труднорешаемые задачи.
М.: Мир, 1982.

2. A. Китаев, А. Шень, М. Вялый. Классические и квантовые вычисления.
М.: МЦНМО, ЧеРо, 1999.

3. Введение в криптографию. Под общей редакцией В.В.Ященко. ---
3-е изд. доп. --- М.: МЦНМО: "ЧеРо", 2000. --- 288 с.

4. М.И. Анохин, Н.П.Варновский, В.М.Сидельников, В.В. Ященко.
Криптография в банковском деле. М.: МИФИ, 1997.



\end{document}								   `