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

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

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

\pagestyle{empty}

\begin{document}

\begin{center}
{\Large\textbf{Теоретико-сложностные проблемы в криптографии}}\\
Н.К. Верещагин, В.Н. Крупский.\\
\end{center}

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

\bigskip
\вопрос Многоленточные машины Тьюринга. Время и объём памяти (зона) как меры
сложности вычислений. Возможные упрощения многоленточной модели, их цена.

\вопрос Универсальные машины Тьюринга. Теорема о иерархии по зоне.
Теорема о иерархии по времени.





\вопрос P --- класс проблем, разрешимых за полиномиальное время.
Примеры проблем из класса P: целочиселнная арифметика, арифметика
остатков, сложение и умножение матриц, связность графа.


\вопрос Булевы схемы, их размер и глубина. Класс P/poly.
Включение  P$\subset$P/poly.

\вопрос Класс NP. Примеры проблем из класса NP: выполнимость булевых формул,
существование гамильтонова цикла, задача о клике, полимино (краевая задача),
решение системы линейных неравенств в целых числах.

\вопрос Полиномиальная сводимость (сводимость Карпа) и NP-полные
проблемы. Теорема Кука --- Левина об NP-полноте проблемы выполнимости
пропозициональных формул. Другие NP-полные проблемы.

\вопрос Вероятностные вычисления за полиномиальное время
и класс BPP.
Вложение $\text{BPP}\subset\text{P/poly}$.


\вопрос Вероятностый алгоритм проверки простоты числа.

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

\вопрос Включение BPP в $\Sigma_2$.

\вопрос Вычисления на полиномиальной зоне и класс PSPACE.
Игровая характеризация класса PSPACE.
PSPACE-полнота проблемы истинности булевских формул с кванторами.

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

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

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

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

\вопрос Шифрование с закрытым ключом на основе расширителя.

\вопрос Необратимые функции с секретом. 
Шифрование с открытым ключом на основе необратимой функции с
секретом.

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

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

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

\вопрос Генерация ключей
на
основе необратимой функции с
секретом.

\вопрос Криптографические хеш-функции.

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

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

\вопрос Надежные протоколы бросания монетки по телефону 
на основе расширителя.

\вопрос Разделение секрета между несколькими участниками.

\вопрос Протоколы конфиденциальных вычисления на основе 
необратимой функции с секретом.


\bigskip

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

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

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

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

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



\end{document}								   `