security.tex

امنیت سیستم های رمزنگاری براساس مسائل سخت ریاضی بنا شده است. منظور از مسائل سخت می‌توان به مسائلی اشاره کرد که پیچیدگی محاسباتی آن‌ها برای حل مسئله فرض شده زمان‌بر بوده و بنابراین حل آن مسئله با فرض داشتن جواب مقرون‌به‌صرفه نمی‌باشد. برپایه‌ی این نوع مسائل سیستم‌های رمزنگاری متفاوتی طراحی  شده‌اند. به‌عنوان مثال تجزیه‌اعداد یک مسئله سخت ریاضی محسوب می‌شود که برای حل آن حتی با بهترین الگوریتم‌های ارائه شده زمانی نمایی لازم است به این معنی که با افزایش طول ارقام مسئله زمان اجرای برنامه برای حل مسئله به صورت نمایی افزایش می‌باید که برای اعداد بزرگ حتی به چندین سال زمان برای حل آن مورد نیاز می‌باشد.  در نتیجه برپایه‌ی این مسئله‌ی سخت سیستم رمزنگاری
$RSA$
طراحی شد که هنوز در بسیاری از پروتکل‌های رمزنگاری مورداستفاده قرار می‌گیرد. 
\\
اما با ورود کامپیوترهای کوانتومی زمان مورد نیاز برای حل چنین مسائلی به شدت کاهش یافت به طوری‌که سیستم‌های رمزنگاری ارائه شده برمبنای چنین مسائلی همچون سیستم رمزنگاری 
$RSA$
کارایی خود را  در برابر کامپیوترهای کوانتومی از دست داد. بنابراین رمزنگاران برای آینده رمزنگاری یعنی زمانی که به جای کامپیوترهای کلاسیک از کامپوترهای کوانتومی که به طور قابل توجهی دارای کارایی بهتر و پردازش سریع‌تری هستند  استفاده شود به دنبال مسائلی برآمدند که حتی با وجود کامپیوترهای کوانتومی نیز مسائلی سخت طلقی شوند. از جمله معتبرترین مسائلی که با وجود کامپیوترها و الگوریتم‌های کوانتومی به عنوان مسائل سخت درنظر گرفته می‌شوند مسائلی است که در حوزه‌ی  همسانی بین خم‌های بیضوی سوپرسینگولار ارائه شده اند. این مسائل به طور کامل در 
\cite{jao2014towards}
ارائه شده‌اند. از آنجا که در طرح خود از دو تا از این  مسائل استفاده می‌کنیم بنابراین در ادامه به تشریح این دو مسئله می‌پردازیم.
\\
\\
برای  بیان این دو مسئله لازم است  یک عدد اول 
$p$
به فرم
$\ell_A^{e_A} \ell_B^{e_B} . f \pm 1 $
انتخاب کنیم سپس یک خم بیضوی سوپرسینگولار 
$E_0$
روی میدان
$\mathbb{F}_{p^2}$
با روش
\cite{broker}
 به‌دست آوریم که زوج نقاط
$\{P_A , Q_A \}$
و
$\{ P_B , Q_B \}$
مولدهای زیرگروه های
$E_0[\ell_A^{e_A}]$
و
$E_0[\ell_B^{e_B}]$
باشند.
\\
\\
 با فرض عدد اول
$p$
، خم سوپرسینگولار
$E_0$
و زیرگروه‌های
 $E_0[\ell_A^{e_A}]$
 و
 $E_0[\ell_B^{e_B}]$
 و همچنین مولدهای آن به تعریف این دو مسئله می‌پردازیم:
%همچون همسانی‌های بین خم های معمولی در بین همسانی‌های هم های سوپرسینگولار نیز مسائل محاسباتی زیر را معرفی می‌کنیم :\\
\\
\\
\textbf{ مساله همسانی سوپرسینگولار محاسباتی :‌}
\LTRfootnote{Computational Supersingular Isogeny (CSSI) problem}
\\
\\
فرض کنیم 
$\phi_A :‌E_0 \rightarrow E_A $
یک همسانی  با هسته 
$\langle [m_A]P_A + [n_A]Q_A \rangle $
می‌باشد که
$m_A$
و
$n_A$
نقاط تصادفی از میدان
$ (\mathbb{Z} / \ell_A^{e_A} \mathbb{Z}) $
هستند با این ویژگی که هردو همزمان عاملی از
$\ell_A$
نمی‌باشند.
\\
 با داشتن خم سوپرسینگولار
$E_A$
و همچنین نقاط 
$\phi_A(P_B)$
و
$\phi_A(Q_B)$
 یافتن مولد هسته‌ی همسانی، یعنی
$\langle R_A \rangle  = \langle [m_A]P_A + [n_A]Q_A \rangle $
یک مسئله سخت محاسباتی در همسانی‌ها می‌باشد. به عبارت دیگر با داشتن دو خم 
$E_0$
و
$E_A$
و همسانی بین آنها یعنی
$\phi_{A}$
و همچنین نقاط کمکی 
$\phi_A(P_B)$
و
$\phi_A(Q_B)$
 پیداکردن هسته همسانی مشکل است.
\\
 این مسئله به عنوان مسئله‌ی 
$\bf {CSSI}$
شناخته می‌شود.
\\
\\
\textbf{توجه.}
ذکر این نکته لازم است که با داشتن مولد
$R_A(= [m_A]P_A + [n_A]Q_A)$
و زوج نقاط
$P_A$
و
$Q_A$
، یافتن نقاط
$m_A$
و
$n_A$
به سادگی توسط لگاریتم گسسته توسیع‌یافته
\LTRfootnote{extended discrete logarithms}
 با این فرض که خم 
$E_0$
هموار باشد، امکان‌پذیر است
\cite{eDS}
، در نتیجه در فرض بالا نگاشت نقاط یعنی
$\phi_A(P_B)$
و
$\phi_A(Q_B)$
را به عنوان نقاط کمکی درنظر گرفتیم.
\newpage
\textbf{ مسئله ساخت خم سوپرسینگولار تصمیم‌پذیر : }
 \LTRfootnote{Decisional Supersingular Product (DSSP problem)}
\\
\\
 برای فهم بیشتر این مسئله لازم است ابتدا به شکل زیر دقت شود :
 
 % ==============================================================================================
 % figure for demonstrate DSSP problem
 \begin{figure}[H] 
 	\begin{center}
 		
 		\begin{tikzcd}
 			E_0 \arrow[r, "\phi"] \arrow[d] & E_3 \arrow[d] \\
 			E_1  \arrow[r, "{\phi}' "] & E_2 
 		\end{tikzcd}
 		
 		\caption{
 			% DSSP ‌Problem    
 		}
 		\label{fig:dssp}
 		
 	\end{center}
 \end{figure}
 % ==============================================================================================

اگر
$\phi : E_0 \rightarrow E_3$
یک همسانی با مرتبه 
$\ell_A^{e_A}$
باشد. با دریافت چندتایی
$(E_1 , E_2 , {\phi}' )$
، مشخص کردن اینکه کدامیک از دو توزیع زیر (که به احتمال 
$1/2$
رخ می‌دهند) موجب تشکیل آنها شده است به عنوان یک مسئله سخت در همسانی‌ها شناخته می‌شود:
 \begin{itemize}
 	
\item {
 انتخاب یک نقطه تصادفی
 $R$
 از مرتبه‌ی
 $\ell_B^{e_B}$
 و ساخت خم‌های
 $E_1 = E_0 / \langle R \rangle $
 و 
 \\
 $E_2 = E_3 / \langle \phi_{R} \rangle $
 و تولید همسانی
 ${\phi}' : E_1 \rightarrow E_2$
 با درجه‌ی
 $\ell_A^{e_A}$	
}
 
 	
\item {
انتخاب تصادفی خم 
$E_1$
در میان خم‌های هم‌مرتبه با 
$E_0$
و همچنین انتخاب تصادفی همسانی
${\phi}' : E_1 \rightarrow E_2 $
با درجه‌ی
$\ell_A^{e_A}$
}
 	
\end{itemize}
این مسئله به عنوان مسئله 
$\bf{DSSP}$
شناخته می‌شود.
\\
\\


در ادامه برای آن‌که امنیت طرح امضای دیجیتال خود را براساس مسائل سختی که معرفی شد تشریح کنیم لازم است ابتدا به امنیت اثبات دانش صفر بپردازیم. علت این امر آن است که همان‌طور که در بخش‌های قبلی بیان شد، طرح امضای ما براساس یک نوع سیستم اثبات دانش صفر غیرتعاملی بناشده است  که خود از طریق پروتکل زیگما و ساخت آنره تشکیل شده است. بنابراین در قدم اول به امنیت اثبات دانش صفر و در قدم بعدی به امنیت امضای دیجیتال می‌پردازیم. 
\\
امنیت  ساخت آنره به طور کامل در
\cite{unruh}
بیان شده است. 

\newpage
\section{\bf امنیت اثبات دانش صفر}\label{zkp_security}
\LTRfootnote{Security of the Zero-Knowledge Proof}
\\
برای تشریح امنیت پروتکل زیگما کافی است قضیه زیر را اثبات کنیم: 
\\

\begin{theorem}\label{thm:zkp}
اثبات دانش صفر هویت همسانی مبنا ، ویژگی‌های تمامیت ، صداقت ویژه و دانش صفر تاییدکننده صادق را برآورده می‌کند.
\end{theorem}~
%\begin{refproof}[Proof of Theorem \ref{thm:neat}]
%\end{refproof}
\\
\textbf{ اثبات.}
با بهره‌گیری از تکنیک‌های کلاسیک ارائه شده در
\cite{feige1988zero , goldreich1991proofs}
، در سه مرحله مستقلا ‌به اثبات ویژگی‌های پروتکل زیگما می‌پردازیم :  
\begin{itemize}
	
\item[]{
\textbf{تمامیت . }
اثبات‌کننده با استفاده از الگوریتم ارائه شده  در بخش
$[4]$
می‌تواند به راحتی و در زمان چندجمله‌ای دیاگرام 
\ref{fig:zkp}
را به راحتی تشکیل داده و تاییدکننده نیز در زمان چندجمله‌ای می‌تواند ادعای اثبات‌کننده را تایید کند.
}

\item [] {
\textbf{صداقت .}
برای اثبات این قسمت اجازه می‌دهیم شخصی به‌نام چارلز به عنوان یک متخاصم چندجمله‌ای با احتمال نه چندان کمی‌ توانایی متقاعد کردن ویکتور به عنوان تاییدکننده را داشته باشد
}

\item[] {
\textbf{صداقت ویژه .}
فرض کنیم دو رونوشت از تعاملات بین تاییدکننده و اثبات‌کننده به شکل
$(com,0,resp_0)$
و
$(com,1,resp_1)$
که 
$com = (E_1,E_2)$
را در اختیار داریم. بنابراین با استفاده از
$resp_0 = (R,\phi(R))$
، می‌توانیم همسانی
$\psi : E \rightarrow E / \langle R \rangle $
را محاسبه کنیم. از آنجا که 
$resp_1 = \psi(S)$
مولد هسته‌ی
${\phi} '$
می‌باشد، درنتیجه می‌توانیم دوگان همسانی
$\psi$
(که یکتا نیز می‌باشد) یعنی
${\psi}' : E / \langle R \rangle \rightarrow E $
را محاسیه کنیم. و در آخر با محاسبه‌ی
${\psi}'(resp_1)$
می‌توانیم یک مولد برای
$\langle S \rangle $
تولید کنیم. برای فهم بیشتر مطالب بالا لازم است به شکل زیر دقت شود:


% ==============================================================================================
% figure for demonstrate security of special soundness
\begin{figure}[H] 
	\begin{center}
		
		\begin{tikzcd}
			E \arrow[r, dashed, "\phi"] \arrow[d, thick,  "\psi"] & E/ \langle S \rangle \arrow[d, thick,  "{\psi}' "] \\
			E/ \langle R \rangle \arrow[r, thick, "{\phi}' "] & E/\langle R,S \rangle
		\end{tikzcd}
		
		\caption{}
		\label{fig:soundness_security}
		
	\end{center}
\end{figure}
% ==============================================================================================


\begin{corollary}\label{corol: sound}
	با داشتن همزمان هر دو همسانی
	${\phi}'$
	و
	$\psi$
	، می‌توانیم زیرگروه مخفی
	$\langle S \rangle $
	را به دست آوریم.
\end{corollary}

}

\item [] {
\textbf{دانش صفر .}
برای اثبات این ویژگی، یک تاییدکننده متقلب
\LTRfootnote{cheating verifier}
که به‌عنوان یک جعبه‌سیاه طلقی می‌شود، یک شبیه‌ساز
$(S)$
را می‌سازد. درهربار تکرار(پرسش و پاسخ بین تاییدکننده و اثبات‌کننده)، شبیه‌ساز
$S$
به‌صورت کاملا تصادفی و یکنواخت به تولید یک حدسی که انتظار دارد در مرحله‌ی بعد، تاییدکننده آن را به عنوان چالش موردسوال قرار دهد، می‌پردازد.
\\
\\
اگر 
$b=0$
، حدس شبیه‌ساز 
$S$
باشد آنگاه یک نقطه‌ی
$R \in E $
از زیرگروه 
$ E [ \ell_B^{e_B} ] $
لنتخاب کرده و نگاشت
$ \phi(R) $
را محاسبه می‌کند(لازم به یادآوری است که نگاشت 
$\phi$
روی زیرگروه
$ E [ \ell_B^{e_B} ] $
قسمتی از داده‌ی عمومی می‌باشد). درادامه شبیه‌ساز همسانی‌های
$ \psi : E \rightarrow E / \langle R \rangle  $
$ {\psi}' : E / \langle S \rangle \rightarrow E / \langle S,R \rangle $
را محاسبه کرده: 
% ==============================================================================================
% figure for demonstrate security of zer-konwledge when b=0
\begin{figure}[H] 
	\begin{center}
		
		\begin{tikzcd}
			E  \arrow[d, "\psi"] & E/ \langle S \rangle \arrow[d, "{\psi}' "] \\
			E/ \langle R \rangle \arrow[r, "{\phi}' "] & E/\langle R,S \rangle
		\end{tikzcd}
		
		\caption{}
		\label{fig:zkp_security_b0}
		
	\end{center}
\end{figure}
% ==============================================================================================
 و در انتها
$E_1 = E / \langle R \rangle $
و
$E_2 = E / \langle S,R \rangle $
را برای تاییدکننده‌ی متقلب ارسال می‌کند.
}
\\
\\
اگر
$b=1$
حدس شبیه‌ساز باشد آنگاه یک خم بیضپی سوپرسینگولار تصادفی
$E'$
هم‌مرتبه با خم
$E$
و همچنین یک نقطه تصادفی
$R \in E'$
از زیرگروه
$E[\ell_A^{e_A}]$
انتخاب کرده و سپس همسانی
${\phi}' : E' \rightarrow E' / \langle R \rangle $
را تشکیل داده:
% ==============================================================================================
% figure  for demonstrate zer-konwledge security when b=1
\begin{figure}[H] 
	\begin{center}
		
		\begin{tikzcd}
			E \arrow[r, dashed, "\phi"] & E/ \langle S \rangle  \\
			E/ \langle R \rangle \arrow[r, "{\phi}' "] & E/\langle R,S \rangle
		\end{tikzcd}
		
		\caption{}
		\label{fig:zkp_security_b1}
		
	\end{center}
\end{figure}
% ==============================================================================================
و در پایان 
$E_1 = E'$
و
$E_2 = E' / \langle R \rangle $
را برای تاییدکننده‌ی متقلب ارسال می‌کند.
\\
\\
اگر تاییدکننده‌ی متقلب هیچ سوال موردانتظاری (چالش)را مورد پرسش قرار ندهد آنگاه شبیه‌ساز به‌سادگی تلاشش را متوقف می‌کند. اما اگر تاییدکننده‌ی متقلب سوال موردانتظار را بپرسد، شبیه‌ساز در جواب چندتایی
$(E_1,E_2,b,R)$
را به‌عنوان خروجی‌اش نشان می‌دهد. شبیه‌ساز بعداز 
$m$
بار تعامل موفق یا تاییدکننده‌ی متقلب و یا درصورت امتناع تاییدکننده، عملیات را متوفق می‌کند.
\\
\\
برای اثبات ویژگی دانش‌صفر لازم است نشان دهیم که شبیه‌ساز
$S$
در زمان چندجمله‌ای اجرا شده است و خروجی‌اش نیز به‌صورت چندجمله‌ای غیرقابل تشخیص  نسبت به تعاملات واقعی بین تاییدکننده‌ی متقلب و اثبات‌کننده‌ی واقعی می‌باشد:
\begin{itemize}
\item {
	برای نشان دادن آن‌که شبیه‌ساز 
	$S$
	در زمان چندجمله‌ای اجرا می‌شود کافی است تا نشان دهیم در هر تکرار برای هر حدس بیت
	$b$
	توسط شبیه‌ساز
	$S$
	احتمال آن‌که تاییدکننده‌ی متقلب سوالی بپرسد مقدار
	$1-b$
	خواهد بود که به‌طور معکوس نزدیک به 
	$1/2$
	خواهد بود. اگر فرض کنیم چنینی حالتی رخ نمی‌دهد پس اثبات‌کننده‌ی متقلب می‌تواند از یک اوراکل برای مسئله‌ی 
	$DSSP$
	استفاده کند.
}

\item {
برای اثبات غیرقابل تمایز بودن لازم است از تکنیک هیبریدی گفته شده در
\cite{}
استفاده کنیم. بنابراین کافی است تا اثبات کنیم که هیج متمایزکننده‌ی چندجمله‌ای دیگری برای یک مرحله از روند طرح تاییدهویت وجود ندارد. بنابراین به روشنی معلوم است که هیچ چنین متمایزکننده‌ای برای پرسش حالت
$b=0$
وجود ندارد. دلیلی این امر هم این است که خروجی شبیه‌ساز 
$S$
و اثبات‌کننده‌ی واقعی در این حالت کاملا یکتاست.

حال فرض کنید که یک متمایزکننده‌ی 
$D$
موجود است که روی ورودی
${\phi}' : E_1 \rightarrow E_2$
به احتمال خیلی زیاد می‌تواند مشخص کند که آیا تعاملات از طرف شبیه‌ساز 
$S$
رخ داده یا تعامل بین تاییدکننده‌ی متقلب و اثبات‌کننده‌ی واقعی انجام شده است یا خیر. بنابراین متمایزکننده‌ی
$D$
می‌تواند به عنوان یک اوراکل از مس‌سله‌ی
$DSSP$
استفاده کند.

}
\end{itemize}

\end{itemize}~
\\
\\





\newpage
\section{امنیت امضا}\label{sign_security}

همان‌گونه که در قضیه ۲ بیان شد، طرح امضای دیجیتال به دست‌آمده از بخش ۴ ، یک امضای دیجیتال مقاوم دربرابر حمله‌ی جعل متن انتخابی یا به اختصار
\text{SUF-CMA}
 می‌باشد.
یک بخش مهم طرح امضای ما مربوط به  اثبات آنره می‌باشد که اساس این اثبات برپایه‌ی اوراکل تصادفی کوانتومی
$G$
پایه‌گذاری شده است. یک ویژگی الزامی و پایه‌ای این اوراکل این است که دامنه و برد یکسانی برای هر دو نوع پاسخ داشته باشد.
\\
 همچنین در بخش 
4.2
تکنیکی معرفی کردیم که باعث فشرده‌سازی امضا می‌شد(کلیدعمومی و پاسخ‌ها فشرده می‌شوند) که درنتیجه‌ی آن امضای ما حجم کمتری در مقایسه با حالت اولیه به‌دست می‌آورد. همچنین تابع 
$G$
را اوراکل تصادفی کوانتومی‌امی درنظر گرفتیم که هش‌هایی به طول 
$k \approx 3\lambda$
تولید می‌کند.
\\
با این اوصاف به دلیل آنکه اثبات آنره تابع 
$G$
را اوراکلی درنظر می‌گیرد که دامنه و بردی از یک نوع و اندازه دارد بنابراین برخلاف حالت فشرده، در امضای حالت نافشرده به‌دلیل آنکه پاسخ‌های ما طول‌های متفاوت 
$k$
و
$4k$
دارند و دامنه‌ي تابع 
$G$
در بعضی حالت‌ها متفاوت با برد آن می‌شود بنابراین اثبات آنره غیرمعتبر و درنتیجه امضای ما غیرمعتبر می گردد.
تنها راه‌حلی که برای این موضوع می‌توان به کار برد این است که پاسخ‌های کوتاه‌تر را از
$k$
 بیت به 
$4k$
بیت افزایش دهیم و از طرف دیگر لازم است تا تابع
$G$
، هش‌هایی به‌اندازه 
$4k$
بیت تولید کند تا تابع 
$G$
دامنه و برد یکسانی به‌صورت 
$\{ 0,1 \}^{4k}$
داشته باشد که درنتیجه‌ی آن اثبات آنره و بالطبع آن امضای ما معتبر گردد. البته با این روش  سایز امضای ما دقیقا 
$18 \lambda$
بیت افزایش خواهد یافت.
\\
درادامه با یک استدلال موقت نشان خواهیم داد که در طرح امضای خود نیازی به فشرده‌سازی نداریم  و اگر تابع 
$G$
هش‌هایی به‌اندازه 
$k \approx 3\lambda$ 
تولید کند آنگاه امضای نافشرده‌ی ما ایمن باقی می‌ماند.
 در ادامه بحث
$\mathcal{DS}_u$
معرف امضای نافشرده و
$\mathcal{DS}_c$
بیان‌کننده‌ی امضای فشرده(پاسخ
$\psi(S)$
فشرده می‌شود) خواهد بود.
\\
\theorem{
$\mathcal{DS}_c$
یک
\text{SUF-CMA}
در مدل اوراکل تصادفی می‌باشد.
}\label{theorem_3}

\refproof{
از آنجا که تمام پاسخ‌ها به‌اندزه
$k$
بیت ارائه می‌شوند درنتیجه ورودی و خروجی الگوریتم امضا یکسان و
$k$
می‌باشد، بنابراین امنیت 
$\mathcal{DS}_c$
 وابسته به امنیت قضیه ۲ می‌باشد.
}
\\
\theorem{
$\mathcal{DS}_u$
یک 
\text{SUF-CMA}
در مدل اوراکل تصادفی می‌باشد.
}
\refproof{
برای اثبات این قضیه از روش حل مسائل کاهشی استفاده می‌کنیم. به‌عبارت دیگر اگر 
$\mathcal{DS}_u$
و
$\mathcal{DS}_c$
را دومسئله درنظربگیریم و 
$\mathcal{DS}_u$
قابل کاهش به 
$\mathcal{DS}_c$
باشد، آنگاه اگر امنیت مسئله‌ی اول نقض شود مطمئنا امنیت مسئله‌ی دوم نیز به‌خطر می‌افتد و درطرف دیگر، اگر مسئله‌ی دوم در برابر هر متخاصمی ایمن باشد اطمینان می‌یابیم که مسئله‌ی اول نیز کاملا ایمن می‌باشد.
در ادامه می‌خواهیم این امر را اثبات کنیم که 
$\mathcal{DS}_u$
قابل کاهش به 
$\mathcal{DS}_c$
است و از آنجا که در قضیه‌
\ref{theorem_3}
اثبات شد که 
$\mathcal{DS}_c$
 ایمن است بنابراین به این نتیجه برسیم که 
$\mathcal{DS}_u$
نیز ایمن می‌باشد.
}
\\
\\
فرض کنید متخاصم چندجمله‌ای کوانتومی
$\mathcal{A}$
موجود می‌باشد که قادر به شکستن امنیت
$\mathcal{DS}_u$
می‌باشد.
می‌خواهیم نشان دهیم اگر این متخاصم به  یک اوراکل امضای کلاسیک برای 
$\mathcal{DS}_c$
و یک اوراکل تصادفی کوانتومی 
$G_c : \{ 0,1 \}^k \rightarrow \{ 0,1\}^k$
دسترسی داشته باشد، می‌تواند
یک زوج پیام-امضای معتبر برای 
$\mathcal{DS}_c$
جعل کند.
\\
بدین منظور فرض کنید کلیدعمومی
$pk$
 و یک اوراکل امضا برای نمونه‌ی
$\mathcal{DS}_c$
 را به‌همراه اوراکل‌های تصادفی کوانتومی
$G_c$
و
$H$
دراختیار داریم. همچنین فرض کنید 
$C_0$
و
$C_1$
نیز به‌ترتیب معرف مجموعه جواب‌های ممکن چالش‌های
$ch=0,1$
در  
$\mathcal{DS}_c$
باشند(البته قابل ذکر است که تعداد اعضای هر دو مجموعه دقیقا
$2^k$ 
و هر یک از اعضای مجموعه، رشته‌بیت‌هایی به طول
$k$
می‌باشند). 
حال می‌خواهیم از طریق الگوریتم‌های بیان شده در بخش‌های قبلی و همچنین موارد فرض شده در بالا  یک نمونه امضای 
$\mathcal{DS}_u$
را تولید کنیم با این تفاوت که تابع تصادفی کوانتومی 
$G_u$
به‌صورت زیر تعریف می‌شود.
\\
\\
قبل از معرفی تابع 
$G_u$
، ابتدا به معرفی چندمتغیر می‌پردازیم.
\begin{itemize}
\item {
مجموعه پاسخ‌های ممکن چالش‌های
$ch=0,1$
در امضای
$\mathcal{DS}_u$
را به ‌ترتیب 
$U_0$
و
$U_1$
می‌نامیم. همان‌طور که قابل بررسی است روابط
$C_0 = U_1$
و
$|C_1| = |U_1|$
بین این متغیرها برقرار می‌باشد با این نکته که عناصر 
$U_1$
، 
$4k$
بیتی می‌باشند.
}

\item {
تابع 
$\mathcal{C} : U_1 \rightarrow C_1$
نمایش یک نگاشت فشرده‌سازی است که نقاط
$\psi(s)$
در
$U_1$
 را به ضریب فشرده‌سازی معادلش در
$C_1$
نگاشت می‌کند.
\\
تابع
$\mathcal{C} : U_1 \rightarrow C_1$
یک تابع دوطرفه می‌باشد که .. ؟؟؟
}

\item {
تابع
$G'_u : \{0,1\}^{4k} \rightarrow \{0,1\}^k$
یک اوراکل تصادفی کوانتومی می‌باشد که 
$$ \forall x \in \{0,1\}^{4k}~: \quad G'_u(z \parallel x) = G_c(x)  $$
و 
$z$
نشان‌دهنده‌ی رشته‌هایی تماما صفر به‌ طول
$3k$
می‌باشد.
}
\end{itemize}~
\\
با توجه به تعاریف بالا، تابع 
$G_u : \{0,1\}^{4k} \rightarrow \{0,1\}^k$
را به‌صورت زیر تعریف می‌کنیم:
$$  G_u(x) = 
	\begin{cases}
	G'_u(z \parallel \mathcal{C}(x)) & \hfill x \in U_1 ~ {\text{اگر}} \\
	
	G'_u(\mathcal{C}^{-1}(y)) & 
	 y \in C_1 ~
	 {\text{زمانیکه}} ~
	\hfil  ~ x=z \parallel y 
	~ {\text{اگر}}\\
	
	G'_u(x) & \hfill  \text{درغیراینصورت}
	\end{cases}
$$
\\
از آنجا که تابع
$G_u$
تنها به تغییر ورودی‌ها  طبق تابع دوطرفه‌ی
$\mathcal{C}$
قبل از اعمال اوراکل تصادفی کوانتومی
$G'_u$
می‌پردازد بنابراین تابع 
$G_u$
همانند تابع
$G'_u$
می‌باشد و قابل تفکیک نیستند. درنتیجه متخاصم 
$\mathcal{A}$
می‌تواند زمانیکه 
$G_u$
تشکیل می‌شود، امضای
$\mathcal{DS}_u$
را بشکند.
\\

اگر متخاصم 
$\mathcal{A}$
به کلیدعمومی
$pk$
و اوراکل‌های تصادفی کوانتومی
$G_u$
و
$H$
دسترسی داشته باشد و تقاضای امضا برای پیام 
$m$
را داشته باشد،
 برای آن‌که بتوانیم امضای 
$\mathcal{DS}_c$
را جعل کنیم(می‌دانیم که طبق آنچه درابتدا فرض کردیم امضای
$\mathcal{DS}_u$
توسط متخاصم قابل جعل می‌باشد) کافیست درخواستش را به اوراکل امضای
$\mathcal{DS}_c$
ارسال کنیم و امضای 
$$ \sigma \leftarrow ( (com_i)_i , (ch_{i,j})_{i,j} , (h_{i,j})_{i,j} , (resp_{i,J_i})_i ) $$
را دریافت ‌کنیم.
 دراین حالت رابطه‌های زیر را خواهیم داشت: 
$$ J_1 \parallel \cdots \parallel J_{2 \lambda} \leftarrow 
H(pk , m , (com_i)_i , (ch_{i,j})_{i,j} , (h_{i,j})_{i,j} )
$$
$$h_{i,J_i} = G(resp_{i,J_i})$$
از آنجا که امضای به‌دست آمده امضای فشرده می‌باشد و متخاصم
$\mathcal{A}$
، قادر به جعل امضای نافشرده می‌باشد بنابراین لازم است تا تمام
$resp_{i,J_i}$
 در 
$\sigma$
را زمانیکه 
$ch_{i,J_i} = 1 $
می‌باشند را از حالت فشرده خارج کرده و امضای 
$\sigma$
اصلاح‌شده که متناسب با طرح امضای
$\mathcal{DS}_u$
می‌باشد را برای 
$\mathcal{A}$
ارسال کنیم.
البته باتوجه به روابط 
$G_u$
پایین،
$h_{i,j}$
به‌دست آمده متناظر با یک هش واقعی در امضای
$\mathcal{DS}_u$
خواهند بود و  درنتیجه
$\sigma$
اصلاح‌شده، یک امضای معتبر برای پیام
$m$
در امضای
$\mathcal{DS}_u$
خواهد بود:
$$
\begin{cases}

G_u(x) = G'_u(z \parallel x) = G_c(x) & \hfill x \in C_0, U_0 ~~ {\text{اگر}} \\


G_u(\mathcal{C}^{-1}(x)) = G'_u(z \parallel x) = G_c(x) & \hfill x \in C_1 ~~ {\text{اگر}} \\

G_u(x) = G'_u(z \parallel \mathcal{C}(x)) = G_c(\mathcal{C}(x)) & \hfill x \in U_1 ~~ {\text{اگر}} \\

\end{cases}
$$
\\

بنابراین با توجه به مطالب بالا، به‌راحتی می‌توانیم درخواست‌های متخاصم
$\mathcal{A}$
را از طریق اوراکل‌های 
$\mathcal{DS}_c$
 جواب دهیم( ونه با 
$\mathcal{DS}_u$ 
) و می‌دانیم که متخاصم
 $\mathcal{A}$
می‌تواند یک جفت پیام-امضای معتبر 
$(m,\sigma)$
از نوع
$\mathcal{DS}_u$
جعل کند.حال اگر این امضای جعلی را بدون محاسبه‌ی هش‌ها، فشرده کنیم آنگاه یک زوج پیام-امضای معتبر برای
$\mathcal{DS}_c$
به‌دست آوریم که این امر مخالف با قضیه‌ی
\ref{theorem_3}
 می‌باشد و نتیجه می‌گیریم به‌دلیل آنکه امضای 
 $\mathcal{DS}_c$
 امن است پس امضای
 $\mathcal{DS}_u$
 نیز ایمن است و  دربرابر هر حمله‌ی کوانتومی مقاوم خواهد بود.



 




 
\section{تعداد مراحل}\label{number_of_rounds}
همان‌طور که قبلا بیان شد برای دست‌یابی به
$\lambda$
بیت امنیت، لازم است تا پروتکل حداقل
$t=2 \lambda$
بار تکرار شود. در ادامه این بخش، به اثبات این ادعا می‌پردازیم.

با توجه به تابع 
$H$
که ورودی و خروجی‌های آن به شکل زیر است :
$$J_1 \parallel \dots \parallel J_t \longleftarrow 
H \big(~pk,m,({com}_i)_i, ({ch}_{i,j})_{i,j} , (h_{i,j})_{i,j}~ \big)$$
فرض کنید یک متخاصم کوانتومی می‌تواند رشته‌ی دلخواه 
$ \big( J_1 \parallel \dots \parallel J_t \big)$
را به‌عنوان چالش انتخاب  و با  استفاده از الگوریتم گراور
\cite{grover}
، به‌جستجوی ؟؟ روی تابع 
$H$
بپردازد تا بتواند یک پیام
$m$
متناسب با هش به‌دست آمده تولید کند. و از آنجا که بقیه‌ی پارامترها عمومی هستند به تولید اثبات شبیه‌سازی شده‌ی
$\pi$
اقدام کند. یک حمله‌ی ؟؟؟
\\
\\
درنتیجه برای داشتن 
$\lambda$
بیت امنیت در برابر حمله‌ی متخاصم کوانتومی لازم است تا طرح امضای ما، اثبات‌دانش‌صفر را 
$t = 2\lambda$
بار تکرار کند.

همان‌طور که قبلا بیان شد در اثبات دانش صفر، اگر پاسخ هر دو چالش 
$b=0,1$
همزمان داده شود آنگاه هرکسی توانایی محاسبه کلیدخصوصی را خواهد داشت. بنابراین یک امرمسلم در طرح امضای دیجیتال ما این است تا یک تعهد، دوبار استفاده نشود. درادامه می‌خواهیم نشان دهیم رخ دادن این اتفاق در طرح امضای ما، احتمال بسیار کوچکی دارد که قابل چشم‌پوشی می‌باشد و امنیت امضا برقرار می‌باشد.


چنانچه می‌دانیم، عدداول انتخابی ما به فرم
$p = \ell_A^{e_A}  \ell_B^{e_B} .f \pm 1 \approx 2^{6\lambda} ~$
که
\\
$\ell_A^{e_A} \approx \ell_B^{e_B} \approx 2^{3\lambda} ~$
می‌باشد. با این حال، دقیقا
$\ell_B^{e_B-1} - 1 \approx 2^{3\lambda} ~$
زیرگروه دوری متفاوت برای 
$E[\ell_B^{e_B}]$
وجود خواهد داشت که هر یک از ادعاها از این زیرگروه‌ها به صورت تصادفی انتخاب می‌شوند.
برای هر امضا، پروتکل دانش‌صفر به تعداد
$2\lambda$
بار تکرار می‌شود، حال اگر فرض کنیم که
$2^s$
پیام را می‌خواهیم امضا کنیم آنگاه 
$2^{s+1} \lambda$
زیرگروه دوری به‌صورت تصادفی از
$E[\ell_B^{e_B}]$
انتخاب خواهیم کرد. یک احتمال بالا از اینکه یک زیرگروه را حداقل دو بار انتخاب می‌کنیم با ؟؟‌:
$$
\frac{2^{s+1}\lambda (2^{s+1}\lambda -1)}{2 . 2^{3\lambda}} 
\frac{2^{2s+2}{\lambda}^2}{2^{3\lambda+1}}
\frac{\lambda^2}{2^{\lambda -1 }}
$$
که برای
$s \lambda$