% 18-Apr-2003
% 22-Apr-2005
% 26-Apr-2006
% 20-Apr-2007
%\documentclass[12pt]{article}
\documentclass{article}
% babel staff
\usepackage[T2A]{fontenc}
\usepackage[koi8-r]{inputenc}
\usepackage[russian]{babel}

%\usepackage{russcorr}
\usepackage{amsmath}
\usepackage{amstext}
\addtolength{\textheight}{2.5cm}
%\usepackage{fullpage}

\newcounter{que}
\newcommand{\question}{\refstepcounter{que}%
\noindent\theque. }

\newcommand{\poly}{\text{poly}}
\newcommand{\nuP}{\text{n.u.P}}
\renewcommand{\P}{\text{P}}
\newcommand{\F}{\text{F}}
\newcommand{\BP}{\text{BP}}
\newcommand{\nuFP}{\text{n.u.FP}}

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

%\pagestyle{empty}

\begin{document}

\begin{center}
{\large\textbf{Программа экзамена по курсу
теоретико-сложностные проблемы криптографии (2007).}}
\end{center}

\medskip

\question Машины Тьюринга (одноленточные),
выполняющие арифметические операции над
$n$-битовыми числами за время $\poly(n)$.

\question Машина Тьюринга (одноленточная),
возводящая в степень по данному модулю за полиномиальное
время. Вычисление НОД двух натуральных чисел
за полиномиальное количество шагов.

\question Теорема о том, что любая функция, вычислимая
некоторой многоленточной машиной Тьюринга за полиномиальное
время, вычисляется
некоторой одноленточной машиной Тьюринга за полиномиальное  время.
Классы $\P$ и $\F\P$.

\question
Схемы из функциональных элементов.
Схемы полиномиального от $n$ размера,
складывающие и умножающие $n$-битовые числа.

\question
Класс $\nuP$ и включение
$\P\subset\nuP$.

\question
Вероятностные полиномиальные алгоритмы и классы
BPP и  FBPP.
Теорема о том,
что ошибку вероятностного алгоритма можно сделать сколько угодно малой.

\question
Включение
$\BP\P\subset\nuP$.

\question
Вероятностный полиномиальный алгоритм Миллера--Рабина
распознавания простоты чисел.

\question
Класс NP. Примеры проблем из класса NP.
Полиномиальная сводимость.
Понятие NP-полной проблемы.

\question
Теорема Кука--Левина об NP-полноте проблемы выполнимости
схем из функциональных элементов.

\question
NP-полнота задачи выполнимости
формул в 3-КНФ.

\question
NP-полнота задачи о раскраске графа в 3 цвета.

\question
NP-полнота задач КЛИКА, НЕЗАВИСИМОЕ МНОЖЕСТВО и
ВЕРШИННОЕ ПОКРЫТИЕ.

\question
NP-полнота задачи о сумме подмножеств.

\question
NP-полнота задач о гамильтонове цикле и о коммивояжере.


\question Необратимые и односторонние функции. Три
примера предположительно односторонних функций.

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

\question Определение статистически и вычислительно неотличимых последовательностей случайных величин. Свойства неотличимых последовательностей случайных величин.
\question Частично односторонние функции. Примеры: функция Рабина, функци RSA, функция Блюма--Микэли. Построение односторонней функции из любой частично односторонней функции. Если P=NP, то односторонних функций нет. 



\question  Генераторы псевдослучайных чисел.
Теорема об эквивалентности
гипотезы о существовании генератора и
гипотезы о существовании необратимой функции (в одну сторону
без доказательства).
\question Расширители. Построение генератора, исходя из расширителя. 
\question Односторонние перестановки. Односторонние обобщенные перестановки, примеры. 
\question Трудный бит, характеризация расширителей в терминах трудного бита. 
\question Вероятностное декодирование списком кода Адамара

\question Построение генератора псевдослучайных чисел
на основе любой обобщенной односторонней перестановки (теорема Левина-Голдрайха).


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

\question Односторонние обобщенные перестановки с секретом.

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

\question Неинтерактивные протоколы привязки к биту (bit commitment). Построение такой схемы на основе односторонней инъективной функции.


\question Интерактивные протоколы привязки к биту. Построение такого протокола на основе
генератора псевдослучайных чисел.

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


\question Определение надежной схемы аутентификации.
Построение такой схемы 
в предположении
необратимости функции Рабина.

\bigskip

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

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

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

3. O. Goldreich.
Foundations of cryptography. Basic tools.
Cambridge Univ. Press. 2001. 372 p.

\end{document}								   `