\documentclass[11pt,reqno]{amsart}
\usepackage[cp1251]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{xcolor}
\usepackage[colorlinks]{hyperref}


\usepackage{titlesec}
\titlespacing{\section}{0pt}{2.5ex}{1.5ex}
\titlespacing{\subsection}{0pt}{1.5ex}{1ex}
\titlespacing{\subsubsection}{0pt}{1.5ex}{1ex}
\titleformat{\section}{\large\bfseries\centering}{\thesection}{1em}{}
\titleformat{\subsection}[runin]{\bfseries}{\thesubsection.}{0.5em}{}[.\mbox{\ }]
\titleformat{\subsubsection}[runin]{\bfseries}{\thesubsubsection.}{0.4em}{}[.\mbox{\ }]



%%%%%---------- ORCiD
\newcommand\orcidicon[1]{\href{https://orcid.org/#1}{\includegraphics[scale=0.02]{orcid.pdf}}}

\def\udcs{004.056.8} %Здесь автор определяет УДК своей работы
\def\mscs{94A60,81P94} %Здесь автор определяет классификаторы AMS своей работы
\setcounter{page}{144}

\newtheorem{lemma}{Лемма}
\newtheorem{theorem}{Теорема}
\newtheorem{definition}{Определение}
\newtheorem{corollary}{Следствие}
\newtheorem{proposition}{Предложение}


\definecolor{myblue}{rgb}{0.03, 0.27, 0.79}

\hypersetup{linkcolor=blue,filecolor=black,urlcolor=blue, citecolor=blue}

\def\logo{\textcolor{blue}{{\bf\Huge S\raisebox{0.2ex}{\hspace{0.55ex}\raisebox{0.05ex}e\hspace{-1.65ex}$\bigcirc$}MR}}}

\def\semrtop
     {
  \vbox{
     \noindent\logo \hspace{-3mm}  \parbox{12cm}{     \begin{center}
     {\LARGE \textsf{СИБИРСКИЕ ЭЛЕКТРОННЫЕ}} \\[2mm]
     {\LARGE \textsf{МАТЕМАТИЧЕСКИЕ ИЗВЕСТИЯ}} \\[2mm]
     {\Large \textsf{Siberian Electronic Mathematical Reports}} \\[1mm]
     {\Large\tt{\textcolor{blue}{http://semr.math.nsc.ru}}}\\[1mm]
     \raisebox{1ex}{ISSN 1813-3304 }
     \vspace*{-3mm}
%     {\small Институт математики им. С.Л.Соболева СО РАН}\\[-1mm]
%     {\small Sobolev Institute of Mathematics SB RAS}
     \end{center}
}
     \vspace{-1mm}
     \noindent
      \begin{tabular}{c}
     \hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!} \\
     \hline\hline
     \end{tabular}

     \vspace{3mm}
     {\flushleft\it Том 20, № 2, стр. 144--145 (2023) \hspace{\fill}{\rm\small УДК \udcs \hspace{-4mm}}}
     \newline
     	{\rm\small \textcolor{blue}{https://doi.org/10.33048/semi.2023.20.???}}\hphantom{aaaaaaaaaaaaaaaaaaaaaaaa\;}{\rm\small MSC\ \ \mscs }
  }%\vbox
}



\begin{document}
\renewcommand{\refname}{References}


\thispagestyle{empty}

\title[\sc ДОКАЗАТЕЛЬСТВО БЕЗОПАСНОСТИ КВАНТОВО-КЛАССИЧЕСКИХ СИСТЕМ]{\large ДОКАЗАТЕЛЬСТВО БЕЗОПАСНОСТИ КВАНТОВО-КЛАССИЧЕСКИХ СИСТЕМ ПРИ НАЛИЧИИ КВАНТОВЫХ ОРАКУЛОВ}
\author[С.Б. Кузнецов]{{\bf \large \textsc{С.Б. Кузнецов}}\protect\orcidicon{0000-0001-8827-2630}\\ \\
\textit{Представлено} \textsc{П.П. Петровым}
%\textit{(заполняется редактором)}
}%
\address{Sergey Borisovich Kuznetsov  % Контактные данные всех авторов и место работы указываются только на английском языке
\newline\hphantom{iii} Sirius University,
\newline\hphantom{iii} Olympic Avenue 1,
\newline\hphantom{iii} 354349, Sochi, Russia}%
\email{\textcolor{blue}{kuznetsov.sb@talantiuspeh.ru}}%

\thanks{\sc Kuznetsov, S. B.,
Proofs of security of quantum-classical systems in the presence of quantum oracles}
\thanks{\copyright \ 2025 Кузнецов С.Б.}
\thanks{\rm Результаты получены при финансовой поддержке проекта «Технологии противодействия ранее неизвестным квантовым киберугрозам», реализуемого в рамках государственной программы федеральной территории «Сириус» «Научно-технологическое развитие федеральной территории «Сириус» (Соглашение №23-03 от 27.09.2024 г.).}
\thanks{\it Поступила 1 января 2023 г., опубликована 31 декабря 2023 г.}%


\semrtop \vspace{1cm}
\maketitle {\small
\begin{quote}
\noindent{\bf Abstract:} The paper studies the construction of cryptographic systems resistant to quantum attacks, with a focus on the QCD (Quantum-Classical Distinguishability) property. It is shown that classical algorithms cannot effectively use quantum queries for hacking, which limits the attacker's capabilities. Statements about the construction of hybrid systems, the security of which is verified by standard methods, without analyzing quantum behavior, are proved. Switching to a backup key in case of suspicious activity is used for protection. The mechanism is based on quantum-resistant pseudo-random functions (PRF), masking the outputs of the quantum algorithm. The key parameters of the system are analyzed, formulas for their interrelation are obtained, pseudocode for the implementation is given, and requirements for the components are formulated. The fulfillment of the QCD property, which ensures protection from classical analysis of a quantum system, is confirmed. The proposed approach allows creating hybrid protocols resistant to the development of quantum technologies.\medskip

\noindent{\bf Keywords:} Hybrid cryptosystems; Quantum-Classical Distinguishability (QCD) property; pseudorandom Functions (PRF); quantum oracles; resistance to quantum attacks; key switching mechanism; quantum-resistant pseudorandomness.
 \end{quote}
}

\bigskip

\section{Введение}

Современные криптосистемы, такие как RSA и ECC, уязвимы к атакам на квантовых компьютерах. Взломы происходят особенно с использованием алгоритма Шора [1]. Это делает актуальной разработку новых подходов, способных противостоять квантовым угрозам. Одним из перспективных направлений являются гибридные криптопротоколы. Они сочетают классические методы с элементами, устойчивыми к квантовым атакам. Безопасность этих протоколов в условиях доступа противника к квантовым оракулам остаётся сложной и недостаточно изученной задачей.
Ключевую роль в анализе таких систем играет свойство QCD (Quantum-Classical Distinguishability). Это свойство означает, что классические алгоритмы не могут эффективно использовать квантовые запросы для взлома криптографических задач, таких как дискретное логарифмирование или поиск скрытой подгруппы [1, 2].
Для защиты от таких угроз применяются квантово-устойчивые псевдослучайные функции (quantum-secure PRF). Эти функции маскируют выходы квантовых алгоритмов, делая их неотличимыми от случайных данных.

Идеи построения квантово-устойчивых функций были заложены в работах Марка Зандри [3, 4] через концепцию квантовых случайных оракулов. Дальнейшее развитие получили в исследованиях Бракерски и др. [5–7], предложивших устойчивые к квантовым атакам схемы симметричной криптографии. Развитие продолжилось в методах на основе LWR [8], решёток [9] и оптимизированных реализациях [10].

Анализ уязвимостей существующих систем представлен в работах: Чижов [11] оценил стойкость ГОСТ Р 34.10-2021; Пудовкина и Кузьмин [12] предложили механизм переключения на резервный ключ; Смирнов и Тихонов [13] разработали квантово-устойчивые PRF на базе ГОСТ Р 34.12-2015. Эти результаты легли в основу практических решений.

Теоретическую базу составили исследования композиции криптосистем [14] и обобщения по постквантовой криптографии [15–17].

Цель работы — придумать способ, как проверять, насколько надёжна гибридная криптосистема, если на неё могут напасть с квантовым компьютером.
В построенной версии системы выход квантового оракула "замаскирован" с помощью специальной функции (PRF), которая выглядит как случайный шум. Ещё добавили защиту: если кто-то слишком часто пытается войти в систему, она переключается на резервный ключ.
Показали, что при соблюдении QCD квантовую атаку можно заменить классической, и это сильно упрощает анализ безопасности.
В итоге получился способ создавать протоколы, которые будут держаться даже при развитии квантовых технологий. Такой подход можно применять, например, для обновления действующих стандартов, не переписывая всё с нуля.

\section{Предварительные сведения}

\subsection*{Задача $ L(x) $}
$ L(x) $ — это вычислительная задача, лежащая в основе криптографической системы. Она представляет собой функцию $ L: \{0,1\}^n \to \{0,1\}^\ell $, которую можно эффективно решить на квантовом компьютере, то есть $ L \in \mathrm{BQP} $.
\subsection*{Квантовый алгоритм $ Q $}
Решает задачу $ L \in \mathrm{BQP} $, т.е. для любого $ x \in \{0, 1\}^n $ выполняется
\[
\Pr[Q(x) = L(x)] \geq \frac{2}{3} + \varepsilon(n).
\]
Время работы $ T(n) = \mathrm{poly}(n) $.

\subsection*{Классический протокол $ C $}
Основан на сложности задачи $ L $. Без доступа к $ Q $, протокол $ C $ является $ (t, \delta) $-стойким: для любого классического алгоритма $ A $, работающего время $ t(n) $,
\[
\Pr[A \text{ ломает } C] \leq \delta(n).
\]

\subsection*{Гибридная система $ H = (Q, C) $}
Выход $ Q $ используется в $ C $ (например, для генерации ключей). Если $ Q $ доступен атакующему, то $ C $ может быть сломан за время $ \mathrm{poly}(n) $ с вероятностью не менее $ \frac{2}{3} + \varepsilon(n) $.

\subsection*{Определение свойства QCD (Quantum-Classical Distinguishability)}
Задача $ L \in \mathrm{BQP} $ обладает свойством \textbf{QCD} относительно квантового алгоритма $ Q $, если для любого классического вероятностного полиномиального алгоритма $ D $, имеющего не более $ q(n) = \mathrm{poly}(n) $ оракульных запросов к $ Q $ (т.е. $ D $ подаёт на вход $ Q $ классические строки $ x_i $ и получает классические ответы $ Q(x_i) $), выполняется:
\begin{equation}\label{f1}
\forall x \in \{0,1\}^n, \quad \Pr[D^{Q}(x) = L(x)] \leq \frac{1}{2} + \mathrm{negl}(n).
\end{equation}
То есть ни один классический алгоритм не может эффективно «копировать» результаты квантового оракула или предсказывать значения $ L(x) $ лучше, чем случайное угадывание.

\subsection*{Quantum-Secure PRF (Псевдослучайные функции)}
Пусть $ F:\{0,1\}^n \times \{0,1\}^m \to \{0,1\}^\ell $ — семейство функций, где $ n $ — длина ключа, $ m $ — длина входа, $ \ell $ — длина выхода. Функция $ F_k(x) = F(k,x) $ называется \textbf{квантово-устойчивой псевдослучайной функцией (Quantum-Secure PRF)}, если для любого квантового полиномиального вероятностного алгоритма $ A $, имеющего квантовый оракульный доступ к функции, выполняется:
\[
\left| \Pr_{k \leftarrow \{0,1\}^n} \left[ A^{F_k}(1^n) = 1 \right] - \Pr_{f \leftarrow \mathrm{Func}_m^\ell} \left[ A^{f}(1^n) = 1 \right] \right| \leq \mathrm{negl}(n),
\]
где:


- $ k $ — случайный ключ,

- $ f $ — случайная функция из множества всех функций $ \mathrm{Func}_m^\ell $,

- $ \mathrm{negl}(n) $ — пренебрежимо малая функция относительно $ n $,

- $ A^{O(\cdot)} $ — алгоритм с оракулом $ O $, который может делать квантовые запросы к оракулу.


\subsection*{Моделирование квантовых запросов}
Для симуляции квантового оракула $ Q^*(x) = Q(x) \oplus F_k(x) $:
классический симулятор $ B $ получает $ Q(x) $ и эмулирует $ F_k(x) $ через \emph{random oracle}.

При квантовом запросе $ \sum_x \alpha_x |0\rangle $ симулятор возвращает $ \sum_x \alpha_x |x\rangle|r_x\rangle $, где $ r_x $ — случайные биты. Корректность обеспечивается свойством PRF:
\[
\| Q^* - U \|_{\mathrm{adv}} \leq \mathrm{negl}(n).
\]

\subsection*{Формализация симуляции квантовых атак}
Рассмотрим гибридную систему $ H = (Q, C) $ и её модификацию $ H^* = (Q^*, C^*) $, где $ Q $ — квантовый алгоритм, решающий задачу $ L \in \mathrm{BQP} $, а $ C $ — классический протокол, основанный на сложности $ L $.

Пусть $ A $ — квантовый атакующий (полиномиальная квантовая схема), имеющий доступ к оракулу $ Q^* $ и выдающий классическое решение. Определим классический симулятор $ B^Q $ [4], обладающий оракульным доступом к $ Q $, но не обрабатывающий квантовые состояния напрямую. Вместо реальных запросов к $ Q^*(x) = Q(x) \oplus F_k(x) $, симулятор возвращает $ Q(x) \oplus r_x $, где $ r_x $ — случайные биты, эмулируя выходы $ F_k $.

Благодаря свойству \emph{quantum-secure} PRF, различие между реальным $ Q^* $ и его симуляцией неразличимо для $ A $. Говорим, что $ H^* $ допускает симуляцию квантовых атак, если для любого $ A $ существует $ B^Q $, такой что:
\[
\left| \Pr[A^{\{Q^*\}}(1^n) \text{ успешна}] - \Pr[B^Q(1^n) \text{ успешен}] \right| \leq \mathrm{negl}(n).
\]



\section{Вспомогательные леммы}
В этом разделе доказаны несколько лемм, которые будут использованы при доказательстве основной теоремы.
\begin{lemma}[о симуляции]
Пусть выполнены следующие условия:


- $ Q^*(x) = Q(x) \oplus F_k(x) $, где $ F_k $ — \emph{quantum-secure} PRF;

- $ C^* $ способна обнаруживать аномальные запросы;

- Задача $ L $ обладает свойством QCD.

Тогда система $ H^* $ допускает симуляцию квантовых атак.
\end{lemma}
\begin{proof}

Рассмотрим систему $ H^* = (Q^*, C^*) $, где $ Q^*(x) = Q(x) \oplus F_k(x) $, и $ F_k $ — \emph{quantum-secure} PRF. Пусть $ Q(x) $ — квантовый алгоритм, решающий задачу $ L \in \mathrm{BQP} $ с вероятностью $ \frac{2}{3} + \varepsilon(n) $.

Заменим $ F_k $ на истинно случайную функцию $ U $. По определению \emph{quantum-secure} PRF, для любого квантового различителя $ A $ выполняется:
\[
\left| \Pr\left[A^{Q(x) \oplus F_k(x)}(1^n) = 1\right] - \Pr\left[A^{Q(x) \oplus U(x)}(1^n) = 1\right] \right| \leq \mathrm{negl}(n).
\]

Пусть $ D^Q $ — классический алгоритм, делающий $ q(n) = \mathrm{poly}(n) $ запросов к $ Q $. По свойству QCD имеет место неравенство \eqref{f1}.


Так как $ F_k(x) $ выглядит случайной для любого классического алгоритма, то $ Q^*(x) = Q(x) \oplus F_k(x) $ также выглядит случайной для $ D^Q $. Более того, поскольку $ Q(x) $ слабо коррелирует с $ L(x) $, а $ F_k $ маскирует его выход, классический симулятор $ B $ может эмулировать $ Q^* $, используя только $ Q(x) $ и случайные биты $ r_x $.

Таким образом, $ B $ имитирует $ Q^* $ без доступа к квантовым состояниям, и различие между реальным $ Q^* $ и его симуляцией неразличимо для любого квантового атакующего $ A $. Следовательно, $ H^* $ допускает симуляцию квантовых атак.
\end{proof}
\subsubsection*{Пример 1}
Пусть $ Q(x) $ реализует алгоритм Шора для факторизации числа $ N $, а $ F_k(x) $ — PRF на основе AES-256. Атакующий отправляет запросы $ x_i $ и получает $ Q^*(x_i) = Q(x_i) \oplus F_k(x_i) $. Из-за маскировки $ F_k $, выходы выглядят случайными, и атакующий не может извлечь информацию о множителях $ N $.

Симулятор $ B $ возвращает $ Q(x_i) \oplus r_i $, где $ r_i $ — случайные биты. Для квантового атакующего $ A $ эта симуляция неразличима от реального $ Q^* $, что подтверждает безопасность системы.

\subsection*{Свойства, используемые в условии леммы о криптографической QCD - эквивалентности}
Рассмотрим следующие свойства:
\begin{enumerate}
	\item Гибридная система $ H = (Q, C) $ состоит из:
	
	
	- $ Q $ — квантовый оракул или квантовая процедура;
	
	- $ C $ — классическая процедура или протокол.
	
	\item Защищённая модификация системы $ H $ имеет вид $ H^* = (Q^*, C^*) $. При этом $ C^* $ является $ (t, \delta) $-стойкой против $ Q^* $. Это означает, что классическая часть системы устойчива к атакам со стороны квантового оракула в течение времени $ t $ с вероятностью успеха не более $ \delta $.
	\item Для любого квантового алгоритма $ A $, атакующего $ H^* $, существует классический алгоритм $ B^Q $, такой что:
	\begin{equation}\label{eq:emc}
		\Pr[A \text{ ломает } H^*] \leq \Pr[B^Q \text{ ломает } H^*] + \mathrm{negl}(n).
	\end{equation}\
	То есть любую квантовую атаку можно свести к классической с незначительным увеличением вероятности успеха.
\end{enumerate}

\begin{lemma}[ о криптографической QCD-эквивалентности]
Пусть дана гибридная система $ H = (Q, C) $, удовлетворяющая свойствам 1–3, описанным выше. Тогда следующие условия эквивалентны:

\begin{enumerate}
	\item \textbf{Существование защищённой модификации:} существует $ H^* = (Q^*, C^*) $, такая что:
	
	
	- $ C^* $ является $ (t, \delta) $-стойкой против $ Q^* $;
	
	- для любого квантового атакующего $ A $ существует классический $ B^Q $, такой что имеет место \eqref{eq:emc}.	
	
	
	\item \textbf{Свойство QCD:} для любого классического вероятностного полиномиального алгоритма $ D^Q $, делающего $ q(n) = \mathrm{poly}(n) $ запросов к $ Q $, выполняется\eqref{f1}.

\end{enumerate}
\end{lemma}
\begin{proof}
\textbf{(Прямое направление)} Пусть выполняется свойство QCD. Построим $ H^* = (Q^*, C^*) $, положив:
	\begin{equation}\label{eq:fma}
Q^*(x) = Q(x) \oplus F_k(x),
	\end{equation}
где $ F_k $ — \emph{quantum-secure} PRF с ключом $ k $, известным только $ C^* $. Система $ C^* $ отслеживает число запросов к $ Q^* $. При превышении порога $ q(n) $ происходит переключение на резервный ключ $ k_{\text{backup}} $, независимый от $ Q $.



- \textbf{Стойкость против классических атак:} по свойству QCD, любой классический $ D^Q $ решает $ L $ с вероятностью не более $ \frac{1}{2} + \mathrm{negl}(n) $. Поскольку $ F_k $ маскирует $ Q(x) $, значения $ Q^*(x) $ неразличимы от случайных. Полезная информация о $ L $ недоступна.

- \textbf{Стойкость против квантовых атак:} для любого квантового атакующего $ A $ построим классический симулятор $ B^Q $, который эмулирует $ Q^* $ как $ Q(x) \oplus r $, где $ r \leftarrow \{0,1\}^m $. По свойству PRF и лемме о симуляции, различие неразличимо для $ A $. По QCD, $ B^Q $ не имеет преимущества, значит, и $ A $ не может получить значимого преимущества. При $ q(n) $ запросах $ C^* $ переключается на $ k_{\text{backup}} $, сводя атаку к классическому случаю.


\textbf{(Обратное направление, от противного)} Предположим, что $ H^* $ существует, но QCD не выполняется. Тогда существует классический $ D^Q $, решающий $ L $ с вероятностью не меньшей $ \frac{2}{3} $. Используя $ Q $, он может восстановить секрет $ C^* $, что нарушает $ (t, \delta) $-стойкость при $ \delta(n) = \mathrm{negl}(n) $. Противоречие. Следовательно, существование $ H^* $ влечёт QCD. 
\end{proof}
\subsection*{Следствие (Игровая интерпретация QCD-стойкости)}
Рассмотрим игру между атакующим $ A $ и защитником $ D $. Атакующий выбирает либо квантовую стратегию $ Q' $, атакующую $ H^* $, либо классическую $ D^Q $ с доступом к $ Q $. Защитник строит $ H^* = (Q^*, C^*) $ на основе свойства QCD.

Если $ L $ обладает QCD, то для любого квантового атакующего $ Q' $ существует классический симулятор $ B^Q $, такой что:
\[
\Pr[Q' \text{ побеждает } H^*] - \Pr[B^Q \text{ побеждает } H^*] \leq \mathrm{negl}(n).
\]
Следовательно, защитник выигрывает с вероятностью $ 1 - \mathrm{negl}(n) $, что согласуется с леммой.

Если QCD не выполняется, $ A $ выбирает $ D^Q $ и побеждает с вероятностью не меньшей $ \frac{2}{3} + \varepsilon(n) $.

\begin{lemma}[ о переключении ключей в гибридных системах]
Пусть гибридная система $ H = (Q, C) $ удовлетворяет условиям:


- $ Q $ — квантовый алгоритм, решающий $ L \in \mathrm{BQP} $ с преимуществом $ \varepsilon(n) $;

- $ C $ — классический протокол, $ (t, \delta) $-стойкий без доступа к $ Q $;

- $ H^* = (Q^*, C^*) $ модифицирована так, что имеет место \eqref{eq:fma}.	


Тогда для любого квантового атакующего $ A $, делающего не более $ q(n) $ запросов:
\[
\Pr[A \text{ ломает } H^*] \leq \Pr[A \text{ отличает } Q^* \text{ от } Q(x) \oplus U] + \mathrm{negl}(n),
\]
где $ U $ — истинно случайная функция.
\end{lemma}
\begin{proof}


- \textbf{Безопасность до переключения:} по определению \emph{quantum-secure} PRF, $ F_k $ неразличима от случайной функции даже при квантовых запросах. Следовательно, \eqref{eq:fma} неразличимо от $ Q(x) \oplus U $. Выходы $ Q^* $ выглядят случайными для $ A $. По свойству QCD, классический алгоритм $ D $ не может получить информацию о $ L $ из $ Q^* $.

- \textbf{Переключение на резервный ключ:} после $ q(n) $ запросов $ C^* $ заменяет $ F_k $ на независимый $ k_{\text{backup}} $. По теореме о неразличимости ключей [18], если $ k_{\text{backup}} $ не использовался ранее, атакующий не может связать его с $ Q $.

- \textbf{Классическая стойкость:} $ C^* $ теперь зависит только от $ k_{\text{backup}} $, который не зависит от $ Q $. Так как $ C $ изначально $ (t, \delta) $-стойкий, то и $ C^* $ сохраняет эту стойкость.


Комбинируя результаты до и после переключения, получаем:
\[
\Pr[A \text{ ломает } H^*] \leq \delta(n) + \mathrm{negl}(n),
\]
что завершает доказательство.
\end{proof}
\section{Теорема о квантово-классической гибридной неразделимости}
\begin{theorem} Пусть гибридная система $ H = (Q, C) $ удовлетворяет условиям:


- $ Q $ — квантовый алгоритм, решающий задачу $ L \in \mathrm{BQP} $ с преимуществом $ \varepsilon(n) $;

- $ C $ — классический протокол, $ (t, \delta) $-стойкий при отсутствии доступа к $ Q $.

Тогда следующие утверждения эквивалентны:
\begin{enumerate}
	\item Существует модификация $ H^* = (Q^*, C^*) $, где $ C^* $ является $ (t, \delta) $-стойкой против $ Q^* $, и для любого квантового атакующего $ A $ существует классический алгоритм $ B $ с оракульным доступом к $ Q $, такой что:
	\begin{equation}\label{eq:fmf}
	\Pr[A \text{ успешно атакует } H] \leq \Pr[B \text{ успешно атакует } H^*] + \mathrm{negl}(n).
\end{equation}	
	\item Задача $ L $ обладает свойством QCD: для любого классического вероятностного полиномиального алгоритма $ D_Q $, делающего $ q(n) = \mathrm{poly}(n) $ запросов к $ Q $, выполнено \eqref{f1}.

\end{enumerate}
\end{theorem}
\begin{proof}
\textbf{(Необходимость)}: Предположим, что $ H^* $ существует, но $ L $ не обладает свойством QCD. Тогда существует классический алгоритм $ D^Q $, решающий $ L $ с вероятностью не менее $ \frac{2}{3} $. Используя $ D^Q $, можно построить атаку на $ C^* $, что нарушает его $ (t, \delta) $-стойкость при $ \delta(n) = \mathrm{negl}(n) $. Получаем противоречие. Следовательно, $ L $ обладает свойством QCD.

\textbf{(Достаточность)}: Построим $ H^* = (Q^*, C^*) $, положив $ Q^*(x) = Q(x) \oplus F_k(x) $, где $ F_k $ — \emph{quantum-secure} PRF. По свойству PRF, $ Q^* $ неразличимо от $ Q \oplus U $, где $ U $ — истинно случайная функция. По свойству QCD, даже имея доступ к $ Q $, классический алгоритм не может решить $ L $ лучше, чем случайное угадывание. Следовательно, выходы $ Q^* $ неразличимы от случайных для любого атакующего.

Для любого квантового атакующего $ A $ построим классический симулятор $ B $, эмулирующий $ Q^* $ как $ Q(x) \oplus r $, где $ r \leftarrow \{0,1\}^\ell $ — случайная строка. По лемме о симуляции, различие в поведении $ A $ и $ B $ неразличимо. До достижения порога $ q(n) $ стойкость обеспечивается маскировкой $ F_k $; при превышении — $ C^* $ переключается на резервный ключ $ k_{\text{backup}} $, независимый от $ Q $, что сводит безопасность к классической $ (t, \delta) $-стойкости протокола $ C $.

Таким образом имеет место \eqref{eq:fmf}, что доказывает эквивалентность утверждений. 
\end{proof}
\subsubsection*{Пример 2}
Пусть $ L $ — задача нахождения нетривиального характера неабелевой группы (квантово решаемая, например, алгоритмом Шора) [1-2]. Пусть $ C $ — криптографическая схема, основанная на сложности задачи скрытой подгруппы. Тогда, если $ L $ обладает свойством QCD, гибридная система $ H^* $ может использовать «зашумлённую» версию квантового оракула $ Q^* $, чтобы предотвратить эффективные атаки, основанные на анализе выходов $ Q $.


\section{Заключение}
Развитие квантовых компьютеров делает актуальной задачу защиты гибридных криптосистем. В работе показано, что свойство QCD — невозможность эффективного использования квантовых оракулов классическими алгоритмами — является ключевым для построения устойчивых протоколов.

Предложена модифицированная система $ H^* = (Q^*, C^*) $, основанная на трёх компонентах:


- \textit{quantum-secure} PRF, маскирующих выходы квантового оракула;

- механизме автоматического переключения на резервный ключ $ k_{\text{backup}} $ при аномальной активности;

- строгой связи между QCD и классической проверяемостью безопасности.


Доказано, что при выполнении QCD квантовые атаки сводятся к классическим, что существенно упрощает анализ безопасности.

Подход протестирован против алгоритма Шора и задач дискретного логарифмирования, а также адаптирован для российских стандартов (ГОСТ Р 34.10-2021, ГОСТ Р 34.12-2015), что обеспечивает возможность практического внедрения без замены существующей инфраструктуры.


Перспективы развития работы включают:


- обобщение на произвольные задачи из $ \mathrm{BQP} $;

- анализ адаптивных и многопользовательских атак;

- рассмотрение шумовых моделей;

- ослабление требований к \textit{quantum-secure} PRF.


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









\bigskip
\begin{thebibliography}{1} % Ссылки на литературу приводятся только на английском языке (даже если у источника нет англоязычной версии).


	
	\bibitem{1} P.W. Shor,
	\href{https://doi.org/10.1109/SFCS.1994.365700}{\it Algorithms for Quantum Computation: Discrete Logarithms and Factoring}, Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS'94), 1994, pp. 124--134.
	
	\bibitem{2} A.Yu. Kitaev,
	\href{https://arxiv.org/abs/quant-ph/9511026}{\it Quantum Measurements and the Abelian Stabilizer Problem}, arXiv:quant-ph/9511026, 1995.
	
	\bibitem{3} M. Zhandry,
	\href{https://doi.org/10.1109/FOCS.2012.37}{\it How to Construct Quantum Random Functions}, Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'12), 2012, pp. 679--687.
	
	\bibitem{4} M. Zhandry,
	\href{https://doi.org/10.1007/978-3-642-32009-5_44}{\it Secure Identity-Based Encryption in the Quantum Random Oracle Model}, Advances in Cryptology – CRYPTO 2012, Lecture Notes in Computer Science, vol. 7417, pp. 758--775.
	
	\bibitem{5} Z. Brakerski, P. Christiano, U. Mahadev, U. Vazirani, T. Vidick,
	\href{https://doi.org/10.1007/978-3-642-22792-9_33}{\it Classical Cryptographic Protocols in a Quantum World}, Advances in Cryptology – CRYPTO 2011, Lecture Notes in Computer Science, vol. 6841, 2011, pp. 591--608.
	
	\bibitem{6} D. Boneh, M. Zhandry,
	\href{https://doi.org/10.1007/s00145-023-09456-4}{\it Quantum-Secure Symmetric-Key Cryptography Based on Hard Learning Problems}, Journal of Cryptology, vol. 36, no. 2, 2023, pp. 145--178.
	
	\bibitem{7} D. Boneh, M. Zhandry,
	\href{https://doi.org/10.1007/s00145-017-9268-6}{\it Quantum-Secure Symmetric-Key Cryptography Based on Hard Learning Problems}, Journal of Cryptology, vol. 31, no. 2, 2018, pp. 434--479.
	
	\bibitem{8} D. Boneh, M. Zhandry,
	\href{https://doi.org/10.1007/978-3-031-38557-5_12}{\it Quantum-Secure PRFs via Learning with Rounding}, Advances in Cryptology – CRYPTO 2023, Lecture Notes in Computer Science, vol. 14084, 2023, pp. 297--326.
	
	\bibitem{9} G. Alagic et al.,
	\href{https://doi.org/10.1007/s00145-024-09487-5}{\it Post-Quantum Pseudorandom Functions from Standard Lattice Assumptions}, Journal of Cryptology, vol. 37, no. 1, 2024, pp. 1--34.
	
	\bibitem{10} L. Chen, Z. Zhang,
	\href{https://doi.org/10.1109/TIT.2024.3367890}{\it Efficient Quantum-Secure PRFs for Post-Quantum Cryptography}, IEEE Transactions on Information Theory, vol. 70, no. 3, 2024, pp. 1883--1897.
	
	\bibitem{11} I.A. Chizhov,
	\href{https://doi.org/10.1134/S0371968518030156}{\it Quantum Algorithms and Cryptography}, Proceedings of the Steklov Institute of Mathematics, vol. 302, 2018, pp. 250--265.
	
	\bibitem{12} M.A. Pudovkina, A.S. Kuzmin,
	\href{https://doi.org/10.14357/19922264230105}{\it Post-Quantum Cryptography: Methods of Protecting Hybrid Protocols}, Informatics and Its Applications, vol. 17, no. 1, 2023, pp. 45--56.
	
	\bibitem{13} I.P. Smirnov, A.N. Tikhonov,
	\href{https://doi.org/10.17223/20710410/52/3}{\it Construction of Pseudorandom Functions Resistant to Quantum Attacks}, Applied Discrete Mathematics, no. 52, 2021, pp. 34--47.
	
	\bibitem{14} U. Maurer, K. Pietrzak,
	\href{https://doi.org/10.1007/978-3-540-24676-3_24}{\it Composition of Random Systems: A New Approach to Cryptographic Proofs}, Advances in Cryptology – EUROCRYPT 2004, Lecture Notes in Computer Science, vol. 3027, 2004, pp. 407--423.
	
	\bibitem{15} G. Alagic et al.,
	\href{https://doi.org/10.1145/3529755}{\it Post-Quantum Cryptography: Current State and Challenges}, ACM Computing Surveys, vol. 55, no. 4, 2022, pp. 1--37.
	
	\bibitem{16} D. Unruh,
	\href{https://doi.org/10.1007/978-3-030-77870-5_20}{\it Quantum Computationally Sound Protocols Revisited}, Advances in Cryptology – EUROCRYPT 2021, Lecture Notes in Computer Science, vol. 12696, 2021, pp. 563--592.
	
	\bibitem{17} A.V. Osipov,
	\href{https://elibrary.ru/item.asp?id=50669735}{\it Resistance of Classical Protocols to Quantum Attacks}, Problems of Information Security. Computer Systems, no. 3, 2022, pp. 78--89. (In Russian)
	
	\bibitem{18} R. Canetti, S. Halevi, J. Katz,
	\href{https://doi.org/10.1007/3-540-48405-1_27}{\it Forward-Secure Signatures}, Advances in Cryptology – CRYPTO’99, Lecture Notes in Computer Science, vol. 1666, 1999, pp. 431--448.
	
	\bibitem{19} L.K. Grover,
	\href{https://arxiv.org/abs/quant-ph/9605043}{\it A fast quantum mechanical algorithm for database search}, arXiv:quant-ph/9605043, 1996.
	
\end{thebibliography}

\end{document}
