Материалы для заочного обучения по курсу «Математическая криптография» (весенний семестр 2019/2020 уч. г.)

Прошу разобрать указанные темы по конспекту лекций и попытаться решить задачи. Решения задач присылайте (в формате PDF или (La)TeX) по адресу электронной почты, указанному на главной странице курса. Разумеется, активность в решении задач зачтется на экзамене. Если возникнут какие-либо вопросы и/или замечания по курсу или конспекту лекций, пишите на тот же адрес.

Решения задач прошлых виртуальных занятий см. здесь.


Виртуальное занятие 25 мая 2020 г. (последнее)

Темы:

Протоколы интерактивного доказательства. Границы полноты и корректности. Абсолютная полнота. Игры Артура и Мерлина. Класс сложностей $\mathrm{IP}$. Пример: протокол интерактивного доказательства для языка КВАДРАТИЧНЫЕ НЕВЫЧЕТЫ (раздел 16 конспекта лекций).

Протоколы доказательства с нулевым разглашением. Вычислительно, статистически и абсолютно нулевое разглашение. Классы сложностей $\mathrm{CZK}$, $\mathrm{SZK}$ и $\mathrm{PZK}$. Теорема Гольдрайха–Микали–Вигдерсона о протоколах интерактивного доказательства с вычислительно нулевым разглашением для языков из $\mathrm{NP}$. Пример: протокол интерактивного доказательства с абсолютно нулевым разглашением для языка ИЗОМОРФИЗМ ГРАФОВ (раздел 17 конспекта лекций).

Задачи:

  1. Доказать, что если для языка $L$ существует протокол интерактивного доказательства с границей полноты, отличной от $0$ для всех $n$, в котором проверяющий никогда не принимает доказательства для строк не из $L$, то $L\in\mathrm{NP}$. См. также [Gol, Volume 1, Subsection 4.12.4, Exercise 5] (там есть указание к решению).
  2. Доказать, что если для языка $L$ существует однораундовый протокол интерактивного доказательства (в котором пересылается лишь одно сообщение от доказывающего к проверяющему) с границами полноты и корректности $2/3$ и $1/3$ соответственно и с вычислительно нулевым разглашением, то $L\in\mathrm{BPP}$.

Виртуальное занятие 18 мая 2020 г. (предпоследнее)

Темы:

Протоколы электронной подписи. Атаки на протоколы электронной подписи. Угрозы стойкости протоколов электронной подписи. Теорема Ромпеля о существовании стойких протоколов электронной подписи (без доказательства). Протокол Лэмпорта электронной подписи (раздел 15 конспекта лекций).

Задачи:

  1. (Для разминки.) Пусть существует протокол электронной подписи, стойкий против экзистенциальной подделки на основе адаптивной атаки с выбором сообщений. Доказать, что существует протокол электронной подписи (с теми же пространствами сообщений), удовлетворяющий тому же условию стойкости и такой, что по произвольной допустимой подписи для сообщения $m$ (относительно некоторого открытого ключа) можно эффективно вычислить это сообщение $m$. См. также [Gol, Volume 2, Subsection 6.6.7, Exercise 4].
  2. Пусть $(I_n\mathbin|n\in\mathbb N)$ — семейство непустых попарно непересекающихся подмножеств $\{0,1\}^*$ и $I=\bigcup_{n\in\mathbb N}I_n$. Пусть также функция $\nu\colon I\to\mathbb N$ ставит в соответствие каждому $i\in I$ единственное число $n\in\mathbb N$ такое, что $i\in I_n$. Мы предполагаем, что функция $i\mapsto1^{\nu(i)}$ ($i\in I$) полиномиально вычислима. Предположим также, что каждого $n\in\mathbb N$ заданы множества $X_n,M_n\subseteq\{0,1\}^{\leqslant\operatorname{poly}(n)}$ и распределения вероятностей $\mathcal G_n$ и $\mathcal X_n$ на множествах $I_n\times\{0,1\}^*$ и $X_n$ соответственно, причем условие $w\in X_n$ может быть проверено по $(1^n,w)$ за полиномиальное время и семейства распределений вероятностей $(\mathcal G_n\mathbin|n\in\mathbb N)$ и $(\mathcal X_n\mathbin|n\in\mathbb N)$ полиномиально конструируемы, когда индексы заданы в унарной записи. Пусть теперь $(f_i\colon X_{\nu(i)}\to M_{\nu(i)}\mathbin|i\in I)$ — семейство сюръективных функций с секретом относительно семейств распределений вероятностей $(\mathcal G_n\mathbin|n\in\mathbb N)$ и $(\mathcal X_{\nu(i)}\mathbin|i\in I)$. Рассмотрим протокол электронной подписи $(G,S,V)$ с семейством пространств сообщений $(M_n\mathbin|n\in\mathbb N)$, в котором
    • $G$ на входе $1^n$ ($n\in\mathbb N$) выбирает $(\mathrm i,\mathrm t)\gets\mathcal G_n$ и возвращает $((\mathrm i,\mathrm t),\mathrm i)$ (т. е. $(\mathrm i,\mathrm t)$ — секретный ключ, а $\mathrm i$ — открытый ключ);
    • $S$ на входе $(1^n,(i,t),m)$, где $n\in\mathbb N$, $(i,t)\in\operatorname{supp}\mathcal G_n$ и $m\in M_n$, возвращает некоторый элемент $f_i^{-1}(m)$ (вычисляемый с помощью алгоритма инвертирования из п. 2 определения 12.1 конспекта лекций);
    • $V(1^n,i,m,w)=1$ (т. е. $w$ принимается в качестве подписи для сообщения $m\in M_n$ при открытом ключе $i\in I_n$, где $n\in\mathbb N$), если и только если $w\in X_n$ и $f_i(w)=m$.

    Сформулировать условие стойкости протокола электронной подписи $(G,S,V)$, вытекающее из односторонности семейства $(f_i\mathbin|i\in I)$.


Виртуальное занятие 27 апреля 2020 г.

Темы:

Системы шифрования (криптосистемы). Системы шифрования с секретным и с открытым ключом. Блоковые системы шифрования. Атаки на системы шифрования. Угрозы стойкости систем шифрования. Построение IND-CPA-стойкой блоковой системы шифрования с секретным ключом на основе псевдослучайного полиномиально инвертируемого семейства перестановок (см. определения 9.1 и 9.7 конспекта лекций; достаточно знать, что этот примитив существует тогда и только тогда, когда существуют односторонние функции — см. замечание 9.9 конспекта лекций). Построение IND-стойкой (на основе атаки с открытым ключом) блоковой системы шифрования с открытым ключом исходя из семейства $F$ перестановок с секретом и семейства функций, трудного для $F$. Преобразование блоковой системы шифрования с открытым ключом в систему с открытым ключом, позволяющую шифровать сообщения произвольной длины, с сохранением IND-стойкости на основе атаки с открытым ключом (раздел 14 конспекта лекций).

Задачи:

  1. (См. начало раздела 2 конспекта лекций, где даны все необходимые определения.) Пусть $N$ — полиномиально перечислимое множество целых неотрицательных чисел и $f\colon\bigcup_{n\in N}\{0,1\}^n\to\{0,1\}^*$. Доказать, что
    • если функция $f$ является односторонней в смысле определения 2.2 конспекта лекций, то она также является односторонней в смысле определения 2.1 конспекта лекций;
    • если функция $f$ является односторонней в смысле определения 2.1 конспекта лекций, то функция $x\mapsto1^n0f(x)$ ($n\in N$, $x\in\{0,1\}^n$) является односторонней в смысле определения 2.2 конспекта лекций.
  2. Доказать, что если существует IND-CPA-стойкая система шифрования с секретным (открытым) ключом, то существует IND-CPA-стойкая система шифрования с секретным (соответственно открытым) ключом и с теми же пространствами сообщений, для которой CCA позволяет найти секретный ключ. См. также [Gol, Volume 2, Subsection 5.5.7, Exercise 35] (там есть указание к решению).

Виртуальное занятие 20 апреля 2020 г.

Темы:

Элементы теории Шеннона систем секретной связи (secrecy systems). Понятия замкнутой, совершенной и чистой системы секретной связи. Нижняя оценка мощности носителя распределения ключей для произвольной совершенной системы секретной связи. Разложение чистой системы секретной связи в дизъюнктное объединение совершенных систем. Система секретной связи Вернама (раздел 13 конспекта лекций).

Задачи:

  1. Пусть $((e_i\colon M\to C\mathbin|i\in K),\mathcal K)$ — система секретной связи. Найти множество всех распределений вероятностей $\mathcal M$ на $M$ таких, что система секретной связи $(((e_i,\dots,e_i)\colon M^n\to C^n\mathbin|i\in K),\mathcal K)$ совершенна относительно $\mathcal M^n$ для всех $n\in\mathbb N$. (Разумеется, $(e_i,\dots,e_i)(m_1,\dots,m_n)=(e_i(m_1),\dots,e_i(m_n))$ для всех $i\in K$ и $(m_1,\dots,m_n)\in M^n$.)
  2. Доказать, что если существует универсальное одностороннее семейство хэш-функций $(h_{n,d}\colon\{0,1\}^{k(n)}\to\{0,1\}^{m(n)}\mathbin|n\in\mathbb N, d\in\{0,1\}^{l(n)})$ относительно семейства распределений вероятностей $(\mathcal U(\{0,1\}^{l(n)})\mathbin|n\in\mathbb N)$, где $m(n)\lt k(n)-1$, $l(n)\lt k(n)$ и $2^{-l(n)}=\operatorname{negl}(n)$, то существует универсальное одностороннее семейство хэш-функций (относительно того же семейства распределений), не являющееся семейством хэш-функций с трудно обнаружимыми коллизиями (относительно любого семейства распределений на $\{0,1\}^{l(n)}$). См. также [Gol, Volume 2, Subsection 6.6.7, Exercise 20] (там есть указание к решению).

Виртуальное занятие 13 апреля 2020 г.

Темы:

Семейства функций и перестановок с секретом. Семейство перестановок RSA. Семейство функций Рабина (по модулям, являющимся числами Блюма). Семейство функций Рабина, ограниченных на элементы нечетного порядка (раздел 12 конспекта лекций).

Задачи:

  1. (Для разминки.) Пусть $f_{N,e}(x)=x^e\bmod N$ ($x\in\mathbb Z_N^\star$) для всех $N,e\geqslant2$. Пусть также $A$ — полиномиальный вероятностный алгоритм, инвертирующий функцию $f_{N,e}$ на случайном аргументе $\widetilde x\gets\mathcal U(\mathbb Z_N^\star)$ с вероятностью $\delta_{N,e}$, т. е. такой, что $\Pr[A(N,e,f_{N,e}(\widetilde x))\in f_{N,e}^{-1}(f_{N,e}(\widetilde x))]=\delta_{N,e}$ для всех $N,e\geqslant2$. Доказать, что существует полиномиальный вероятностный алгоритм $B$, инвертирующий функцию $f_{N,e}$ на произвольном аргументе с той же вероятностью $\delta_{N,e}$, т. е. такой, что $\Pr[B(N,e,f_{N,e}(x))\in f_{N,e}^{-1}(f_{N,e}(x))]=\delta_{N,e}$ для всех $N,e\geqslant2$ и $x\in\mathbb Z_N^\star$. (Мы предполагаем, что генерация случайных элементов $r\gets\mathcal U(\mathbb Z_N^\star)$ выполнима по $N$ за полиномиальное время.)
  2. В этой задаче используются обозначения примера 12.5 конспекта лекций. Для произвольного нечетного числа $N\geqslant3$ положим \[ \alpha_N(x)=\begin{cases}x,&\text{если }x\in\{1,\dots,(N-1)/2\},\\ N-x,&\text{если }x\in\{(N+1)/2,\dots,N-1\},\end{cases} \] и $M_N=\{x\in\{1,\dots,(N-1)/2\}\mathbin|\left(\frac xN\right)=1\}$, где $\left(\frac xN\right)$ — символ Якоби. Доказать, что при том же предположении, что и в теореме 12.6 конспекта лекций $(\alpha_i(\operatorname{Rabin}_i|_{M_i})\mathbin|i\in I)$ является семейством перестановок с секретом относительно семейств распределений вероятностей $(\mathcal G_n\mathbin|n\in\mathbb N)$ и $(\mathcal U(M_i)\mathbin|i\in I)$. См. также [Gol, Volume 2, Section C.1].

Виртуальное занятие 6 апреля 2020 г.

Темы:

Универсальные односторонние семейства хэш-функций. Теорема о композиции для таких семейств. Теорема Ромпеля о существовании универсальных односторонних семейств хэш-функций (без доказательства). Конструкция Наора–Юнга универсального одностороннего семейства хэш-функций на основе односторонней перестановки (раздел 11 конспекта лекций).

Задачи:

  1. Доказать, что если $(\widetilde x_n\mathbin|n\in\mathbb N)$ и $(\widetilde y_n\mathbin|n\in\mathbb N)$ — вычислительно неотличимые семейства случайных величин (когда индексы заданы в унарной записи), причем $\widetilde x_n$ и $\widetilde y_n$ принимают значения в $\{0,1\}^n$, то $\lvert\Pr[\widetilde x_n\in L]-\Pr[\widetilde y_n\in L]\rvert=\operatorname{negl}(n)$ для любого языка $L\in\mathrm{BPP}$. См. также [Gol, Volume 1, Subsection 3.8.4, Exercise 4].
  2. Доказать, что если существуют семейства хэш-функций с трудно обнаружимыми коллизиями, то существуют односторонние семейства функций (и, следовательно, односторонние функции). См. также [Gol, Volume 2, Subsection 6.6.7, Exercise 14].
  3. Доказать, что если $(h_{n,d}\colon\{0,1\}^{k(n)}\to\{0,1\}^{m(n)}\mathbin|n\in\mathbb N, d\in D_n)$ — универсальное одностороннее семейство хэш-функций, то $2^{-m(n)}=\operatorname{negl}(n)$.

Виртуальное занятие 23 марта 2020 г.

Темы:

  1. Односторонность псевдослучайного генератора, отображающего $\{0,1\}^n$ в $\{0,1\}^{m(n)}$, где функция $m$ инъективна (предложение 7.9 конспекта лекций).
  2. Построение псевдослучайного генератора на основе произвольной односторонней перестановки (предложение 7.10 конспекта лекций).
  3. Семейства хэш-функций с трудно обнаружимыми коллизиями. Конструкция Меркле–Дамгорда. Построение семейства хэш-функций с трудно обнаружимыми коллизиями в предположении трудности задачи факторизации целых чисел (раздел 10 конспекта лекций).

Задачи:

  1. Пусть $x_n\in X_n\subseteq\{0,1\}^{m(n)}$ для всех $n\in\mathbb N$ (где $m$ — полиномиальный параметр), причем
    • проблема вхождения в $X_n$ для строк из $\{0,1\}^{m(n)}$ разрешима за полиномиальное от $n$ время;
    • $\lvert X_n\lvert/2^{m(n)}=\delta_n\geqslant1/p(n)$ для некоторого полинома $p$;
    • функция $1^n\mapsto x_n$ полиномиально вычислима.

    Рассмотрим полиномиальный вероятностный алгоритм $A$, который на входе $(1^k,1^n)$ ($k,n\in\mathbb N$) выполняет следующие шаги не более $kp(n)$ раз:

    • Выбрать $w\gets\{0,1\}^{m(n)}$.
    • Если $w\in X_n$, то возвратить $w$ и закончить работу.

    Если же $w\notin X_n$ на всех $kp(n)$ итерациях, то алгоритм $A$ возвращает $x_n$.

    Доказать, что статистическое расстояние между распределением случайной величины $A(1^k,1^n)$ и равномерным распределением на $X_n$ не превосходит $e^{-k}$ (и, следовательно, $2^{-k}$), где $e$ — основание натуральных логарифмов.

  2. Пусть $g$ — псевдослучайный генератор, отображающий $\{0,1\}^n$ в $\{0,1\}^{m(n)}$ для всех $n\in\mathbb N$. Пусть также $M_n\subseteq\{0,1\}^n$, причем проблема вхождения в $M_n$ для строк из $\{0,1\}^n$ разрешима за полиномиальное от $n$ время. Определим $g’$ на $\{0,1\}^n$ при каждом $n\in\mathbb N$ следующим образом: $g’(x)=0^{m(n)}$ при $x\in M_n$ и $g’(x)=g(x)$ при $x\in\{0,1\}^n\setminus M_n$. Доказать, что $g’$ — псевдослучайный генератор тогда и только тогда, когда $\lvert M_n\rvert/2^n=\operatorname{negl}(n)$.
  3. Пусть $a_n\in\{0,1\}^n$ и $b_n\in\{0,1\}^{m(n)}$, где $m$ — полиномиальный параметр такой, что $m(n)>n$ для всех $n\in\mathbb N$. Предположим, что функции $1^n\mapsto a_n$ и $1^n\mapsto b_n$ полиномиально вычислимы. Доказать, что если существуют псевдослучайные генераторы, то существует псевдослучайный генератор $g$ такой, что $g(a_n)=b_n$ для всех $n\in\mathbb N$.

[Gol]
O. Goldreich. Foundations of cryptography. Volume 1 (Basic tools). Volume 2 (Basic applications). Cambridge University Press, 2001 (v. 1), 2004 (v. 2).

Адрес редакции сайта: dialogus@cryptography.ru
© При копировании материалов ссылка на авторов,
© а при их отсутствии — на сайт, обязательна