proposal_end.tex

\documentclass[12pt,a4paper]{article}
%\documentclass[12pt]{book}
\let\latinrm\mathrm
\usepackage{amsmath,amssymb,mathtools}
\usepackage{lipsum}
\usepackage{algorithm}
%\usepackage{algorithmic}
\usepackage[noend]{algpseudocode}
\usepackage{tikz-cd}
\usetikzlibrary{decorations.pathmorphing}
\usepackage{subcaption}
\usepackage{hyperref}
\usepackage{cite}
\renewcommand{\algorithmiccomment}[1]{$\triangleright$ #1}
\usetikzlibrary{matrix}
 %\usepackage[demo]{graphicx}
% \usepackage{caption}


\linespread{1.5} 

\usepackage{xepersian}
\settextfont{XBZar}
\setdigitfont{XBZar}

\title{امضای دیجیتال مقاوم کوانتومی بر اساس همسانی های بین خم های سوپرسینگولار}
\author{مصطفی قربانی
	\\[1cm]{ استاد راهنما: دکتر حسن دقیق}}
%\author{مصطفی قربانی}
\date{}

\begin{document}
\maketitle
%\tableofcontents
%\listoffigures
%\listoftables
	
%\chapter{پیش نیازها}\label{prerequesties}	
\section{اثبات دانش صفر هویت}\LTRfootnote{Zero-Knowledge Proof of Identity}\label{ZKPOI}
ما از عدد اولی به فرم 
$p = \ell_A^{e_A} \ell_B^{e_B} f \pm 1$
استفاده می‌کنیم که 
$\ell_A$
و
$\ell_B$
اعداد اول کوچک (معمولا ۲ و ۳) می‌باشند با این خاصیت که 
$\ell_A^{e_A} \approx \ell_B^{e_B} $
و 
$f$
یک عامل کوچک است که باعث می‌شود 
$p$
یک عدد اول شود.
پارامترهای عمومی شامل عدد اول 
$p = \ell_A^{e_A} \ell_B^{e_B} f \pm 1$
، خم سوپرسینگولار 
$E(\mathbb{F}_{p^2})$
از مرتبه‌ی 
$(\ell_A^{e_A} \ell_B^{e_B})^2$
و همچنین نقاط
$P_B$
و
$Q_B$
که مولدهای زیرگروه 
$E[ \ell_B^{e_B} ]$
می‌باشند.

اثبات دانش صفر مطابق با طرح شکل ۱ می‌باشد.
پگی(اثبات کننده) نقطه مخفی
$S$
که تولیدکننده هسته همسانی 
$\phi : E \rightarrow E/ \langle S \rangle $
است را به عنوان یک راز در اختیار دارد. بنابریان کلید خصوصی پگی 
$S$
(یا هر مولدی از
$ \langle S \rangle$
)
و کلید عمومی آن شامل خم بیضوی
$E/ \langle S \rangle$
 و تصویر نقاط مولد عمومی یعنی
 $\phi(P_B)$
 و
 $\phi(Q_B)$ 
 می‌باشد.
 
پگی برای آن که به ویکتور (تاییدکننده) اثبات کند که دانش 
$\langle S \rangle $
را می‌داند ، یک نقطه تصادفی 
$R$
از مرتبه‌ی
$\ell_B^{e_B}$
انتخاب و همسانی 
$\psi = E \rightarrow E / \langle R \rangle$
را تعریف می‌کند.توجه به این نکته لازم است که تساوی زیر برقرار است :
$$ (E /  \langle S \rangle) /  \langle \phi(R) \rangle = 
   E /  \langle R,S \rangle = 
   (E/ \langle R \rangle) /  \langle \psi(S) \rangle	
$$
% به عبارت دیگر طرح شکل ۱ ؟؟؟ هست.
% اثبات را بعدا در پایان نامه بیاورم !!!

پگی همسانی‌های طرح ارائه شده در شکل 
\ref{fig:zkp}
 را محاسبه و آنها را برای ویکتور ارسال می‌کند. در ادامه ویکتور یک بیت چالشی 
$b \in \{0,1\}$
خود را برای پگی ارسال می‌کندو متعاقبا پگی همسانی‌ای بر اساس چالش انتخابی ویکتور برای وی ارسال می‌کند تا ویکتور آنها را تایید کند.\\
% ==============================================================================================
% figure 1 for demonstrate zer-konwledge proof of identity
\begin{figure}[H] 
	\begin{center}
		
		\begin{tikzcd}
			E \arrow[r, "\phi"] \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}
		
	\end{center}
\end{figure}
% ==============================================================================================





برای فهم و تشریح بیشتر این پروتکل آن را به صورت الگوریتمیک نشان می‌دهیم :
\begin{enumerate}
	
	\item {
\begin{itemize}
	\item 
	پگی یک نقطه تصادفی 
	$R$
	از مرتبه‌ی
	$\ell_B^{e_B}$
	انتخاب می‌کند.
	
	\item 
	او همسانی
	$\psi : E \rightarrow E / \langle R \rangle$
	را محاسبه می‌کند.
	\item 
	پگی در ادامه همسانی
	$\hat{\phi} : E / \langle R \rangle \rightarrow  E / \langle R,S \rangle $
	را به همراه هسته 
	$\langle \psi(S) \rangle$
(
از سوی دیگر 
	$\hat{\psi} : E / \langle S \rangle \rightarrow  E / \langle R,S \rangle $
را به همراه هسته 
$\langle \phi(R) \rangle$
)
 محاسبه می‌کند.
 \item 
 پس از محاسبات بالا ، پگی تعهد 
 \LTRfootnote{commitment}
 $com = (E_1 , E_2)$
 که 
 $E_1 = E / \langle R \rangle$
 و
 $E_2 = E / \langle R,S \rangle$
‌ را برای ویکتور ارسال می‌کند.
 
\end{itemize}	
} % end item

\item 
ویکتور به طور تصادفی  یک بیت چالشی 
$ch \in \{0,1\}$
را انتحاب و برای پگی ارسال می‌کند.
\item 
پگی پاسخ 
$resp$
را برای ویکتور ارسال می‌کند چنانکه :
\begin{itemize}
	\item
	اگر 
	$ch = 0$
	آنگاه
	$resp = (R,\phi(R))$
	
	\item
	اگر 
	$ch = 1$
	آنگاه
	$resp = \psi(R)$
	
\end{itemize}
\item {
\begin{itemize}
	\item 
	اگر
	$ch = 0 $
	، ویکتور تایید می‌کند که
	$R$
	و
	$\phi(R)$
	هردو از مرتبه‌ی 
	$\ell_B^{e_B}$
	هستند و هسته‌های همسانی‌های
	$E \rightarrow E_1$
	و 
	$E/ \langle S \rangle \rightarrow E_2$
	را تولید می‌کنند.
	\item 
	اگر 
	$ch = 1 $
	، ویکتور تایید می‌کند که 
	$\psi(S)$
	از مرتبه‌ی
	$\ell_A^{e_A}$
	است و هسته‌ی همسانی 
	$E_1 \rightarrow E_2$
	را تولید می‌کند.
\end{itemize}
} % end item
	
	
\end{enumerate}

برای دست‌یابی به 
$\lambda$
بیت امنیت ، لازم است که عدد اول 
$p$
انتخابی ،‌ حتما
$6\lambda$
بیت باشد و پروتکل بالا حتما 
$\lambda$
بار تکرار شود. اگر ویکتور تمام 
$\lambda$
مرحله از پروتکل را تایید کند ، آنگاه اثبات هویت پگی مورد قبول قرار می‌گیرد(ادعای او مبنی بر دانش کلید خصوصی
$S$
 اثبات می‌شود) و در غیر اینصورت ویکتور متقاعد نمی‌شود و آن را رد می‌کند. 


% ==============================================================================================
% fugure 2 for demostrate DSSP assumption for chaaleng ????
\begin{figure}
	\centering
	% ----------------------------------------------------------------
	\begin{subfigure}{0.4\textwidth}
		\centering
		%\includegraphics[width=.4\linewidth]
		\caption{b = 0}
		\label{fig:sub1}
		\begin{tikzcd}
			E \arrow[r, dashrightarrow , "\phi"] \arrow[d, "\psi"] & E/ \langle S \rangle \arrow[d, "{\psi}' "] \\
			E/ \langle R \rangle \arrow[r, dashrightarrow ,"{\phi}' "] & E/\langle R,S \rangle
		\end{tikzcd}
		
	\end{subfigure}
	% -------------------------------------------------------------------
	
	% ---------------------------------------------------------------------
	\begin{subfigure}{0.4\textwidth}
		\centering
		%\includegraphics[width=.4\linewidth]
		\caption{b = 1}
		\label{fig:sub2}
		\begin{tikzcd}
			E \arrow[r, dashrightarrow , "\phi"] \arrow[d, dashrightarrow , "\psi"] & E/ \langle S \rangle \arrow[d, dashrightarrow , "{\psi}' "] \\
			E/ \langle R \rangle \arrow[r, "{\phi}' "] & E/\langle R,S \rangle
		\end{tikzcd}
		
	\end{subfigure}%
	% -------------------------------------------------------------------
	\caption{
		همسانی‌های مخفی با خط‌های مقطع نماش داده شده است. خط های توپر نمایش دهنده همسانی‌هایی می‌باشد که پکی نسبت به چالش انجام شده ظاهر می‌کند. با این حال همسانی‌های ظاهرشده هیچ اطلاعاتی درباره همسانی مخفی
		$\phi$
		افشا نمی‌کند.	
	}
	\label{fig:challenge}
\end{figure}
% ==============================================================================================

\newpage
\section{ساخت آنره}\LTRfootnote{Unruh's Construction}\label{unruh}

ساخت آنره 
\cite{unruh}
یک سیستم اثبات دانش صفر تعاملی را به سیستم اثبات دانش صفر غیرتعاملی متناظر با آن انتقال می‌دهد. این ساخت ، ویژگی استخراج آنلاین
\LTRfootnote{online extractability}
را که اجازه می‌دهد شاهد(کلید خصوصی) را از یک متخاصم موفق بدون چرخش
\LTRfootnote{rewinding}
استخراج کنیم ، را دارا می‌باشد.
% مطالب بیشتر مقاله باید تحقیق شود

در این پروتکل ما یک رابطه باینری به نام 
$R$
استفاده خواهیم کرد. یک اظهار 
$x$
رخ می‌دهد اگر شاهدی به نام 
$w$
برای آن موجود باشد که در این صورت آن را به صورت 
$(x,w) \in R $
نمایش خواهیم داد.در یک سیستم اثبات ، یک اثبات کننده 
$\mathcal{R}$
خواهان آن است تا اظهار 
$x$
را برای تاییدکننده 
$\mathcal{V}$
اثبات کند (به عبارت دیگر اثبات کننده درصدد متقاعد کردن تاییدکننده است که شاهد 
$w$
را برای 
$x$
در اختیار دارد).در ابتدای امر این فرص را داریم که تمام بخش های این پروتکل به یک اوراکل تصادفی کوانتومی 
\LTRfootnote{quantum random oracle}
$H$
دسترسی دارند.
% ادامه باید بررسی شود !!!

\subsection{پروتکل زیگما}\LTRfootnote{Sigma Protocols}\label{sigma}

یک پروتکل زیگما 
$\Sigma = ((P^1,P^2),V)$
، یک سیستم اثبات تعاملی است که شامل سه قسمت به ترتیب زیر می‌باشد:
\begin{itemize}
	\item 
	یک تعهد
	\LTRfootnote{commitment}
	$com = P^1(x,w)$
	ارائه شده توسط اثبات کننده 
	\item 
	یک چالش 
	$ch$
	یکنواخت و به طور تصادفی انتخاب شده توسط تاییدکننده
	\item 
	یک پاسخ 
	$resp = P^2(x,w,com,ch)$
	محاسبه شده توسط اثبات کننده بر اساس چالش دریافتی 
	$ch$
	
	\item
	خروجی 
	$V(x,com,ch,resp)$
	توسط تاییدکننده که بر اساس آن ، اثبات یا پذیرفته می‌شود یا مورد قبول واقع نمی‌شود.
	
\end{itemize}

اگر پروتکل زیگما را به صورت 
$\Sigma = (P,V)$
در نظر بگیریم آنگاه  
$P = (P^1,P^2)$
خواهد بود.

پروتکل زیگما شامل ویژگی‌هایی می‌باشد که آنها را به صورت زیر بیان می‌کنیم :

\begin{itemize}
	\item[]{\bf تمامیت }\LTRfootnote{Completeness}:
	
	اگر اثبات کننده
	$\mathcal{R}$
	واقعا شاهد 
	$w$
	را برای اظهار
	$x$
	بداند آنگاه طبق این پروتکل ، تاییدکننده 
	$\mathcal{V}$
	ادعای اثبات کننده را می‌پذیرد.
	
	\item[]{\bf صداقت ویژه }\LTRfootnote{Special soundness}:
	
	یک الگوریتم چندجمله‌ای استخراج
	\LTRfootnote{polynomial time extractor}
	$E_{\Sigma}$
	وجود دارد که با دریافت هر جفتی از تعاملات معتبر
	$(com , ch , resp)$
	و
	$(com , ch' , resp')$
	که هم
	$ch \ne ch'$
	و هم مورد پذیرش تاییدکننده می‌باشد، 
%	$E_{\Sigma}$
	می‌تواند یک شاهد 
	$w$
	محاسبه کند که  
	$(x,w) \in R $
	
	\item[]{\bf دانش صفر تاییدکننده صادق }\LTRfootnote{Honest-verifier zero-knowledge (HVZK)} :
	
	یک الگوریتم چندجمله‌ای شبیه ساز 
	$S_{\Sigma}$
	وجود دارد که خروجی
	$(com,ch,resp)$
	را تولید می‌کند به طوری که نسبت به خروجی تعامل انجام شده  میان اثبات کننده و تاییدکننده صادق، توسط هیچ الگوریتم چندجمله‌ای کوانتومی قابل تشخیص نمی‌باشد.

\end{itemize}

ذکر این نکته لازم است که اثبات دانش صفر هویت همسانی مبنای گفته شده در بخش قبلی در اصل یک پروتکل زیگما می‌باشد.
\newpage
\subsection{سیستم اثبات غیرتعاملی }\LTRfootnote{Non-interactive Proof System}\label{non-pf}

یک سیستم اثبات غیرتعاملی شامل دو الگوریتم می‌باشد :
\begin{itemize}
	
	\item
	یک اثبات کننده 
	$P(x,w)$
	، یک اثبات
	$\pi$
	برای اظهار 
	$x$
	(که دارای شاهد
	$w$
	می‌باشد) تولید می‌کند. 
	
	\item
	تاییدکننده 
	$V(x,\pi)$
	، یا خروجی 
	\textbf{تایید}
	برای پذیرش ادعا یا خروجی  
	\textbf{انکار}
	را برای اثبات 
	$\pi$
	مطرح شده توسط اثبات کننده تولید می‌کند.
	
\end{itemize}

یک سیستم اثبات غیرتعاملی 
$(P,V)$
شامل سه ویژگی لازم است که در زیر آنها را تشریح می‌کنیم :
\begin{itemize}
	
	\item[]{\bf تمامیت} :
	
	‌اگر 
	$(x,w) \in R$
	آنگاه تاییدکننده 
	$V$
	، اثبات 
	$\pi = P(x,w)$
	را می‌پذیرد. 
	
	\item[]{\bf دانش صفر}\LTRfootnote{Zero-knowledge (NIZK)} :
	
	یک الگوریتم چندجمله‌ای شبیه ساز 
	$S$
	که به یک اوراکل تصادفی دسترسی دارد (می‌تواند یک اوراکل را اجرا کند) ، وجود دارد که می‌تواند اثبات‌هایی متفاوت از اثبات‌های تولید شده توسط اثبات کننده
	$P$
	 را تولید کند. الگوریتم شبیه‌ساز به وسیله دو الگوریتم  \\
	 $S = (S_{init} , S_P)$
	 بیان می‌شود.
	 % تعریف کامل نیست و نیاز به مطالعه بیشتر در زمینه الگوریتم های کوانتومی‌ می‌باشد.
	 
	 \item[]{\bf شبیه‌ساز صداقت با ویژگی استخراج آنلاین }\LTRfootnote{
		Simulation-sound online-extractability }
	
	یک الگوریتم چندجمله‌ای استخراج
	$E$
	وجود دارد که توانایی تولید یک شاهد 
	$w$
	برای ادعای 
	$x$
	مطرح شده توسط اثبات‌کننده ، را دارا می‌باشد.
	% تعریف کامل نیست !!!!!!!
\end{itemize}

\newpage
% ====================================================================================
% Unruh Construction
% ====================================================================================

\subsection{ساخت آنره}\label{unruh_constuction}

ساخت آنره ، یک پروتکل زیگما 
$(\Sigma)$
را به یک سیستم اثبات غیرتعاملی 
$(P_{OE}, V_{OE})$
منتقل می‌کند چنانکه اگر پروتکل 
$(\Sigma)$
شامل ویژگی‌های تمامیت ، صداقت خاص و دانش صفر باشد آنگاه نتیجه یک سیستم اثبات با ویژگی تمامیت ، دانش صفر به همراه ویژگی شبیه ‌ساز صداقت با استخراج آنلاین خواهد بود.

اگر فرض کنیم یک پروتکل زیگما به صورت 
$\Sigma = (P_\Sigma , V_\Sigma)$
که
$P_\Sigma = (P_\Sigma^1 , P_\Sigma^2)$
داشته باشیم که 
$c$
 چالش ممکن در دامنه‌ی چالش ها 
$N_{ch}$
داشته باشیم و بخش‌ها  خواهان اجرای پروتکل به تعداد 
$t$
بار باشد (که 
$t$
به پارامتر امنیتی
$\lambda$
بستگی دارد ـ در طرح امضای دیجیتال معرفی شده در این پایان نامه : 
$N_{ch} = \{0,1\} , c = 2 , t = 2\lambda $ 
)
در این صورت اگر
$G$
و
$H$
را اوراکل‌های تصادفی کوانتومی در نظر بگیریم که 
$G$
در همان دامنه باشد آنگاه سیستم اثبات غیرتعاملی 
$(P_{OE} , V_{OE})$
را تعریف می‌کنیم که 
$P_{OE}$
و
$V_{OE}$
را به صورت الگوریتم های ۱ و ۲ به دست می‌آیند.
% ==============================================================================================

\begin{algorithm}\label{algorithm_1}
	\caption{
اثبات‌کننده :
$P_{OE}$
بر اساس ورودی
$(x,w)$	
}
    %\begin{flushleft}
	\resetlatinfont
	\begin{algorithmic}[1]
		\For{ $ i=1 to t $ }
		\EndFor
	\end{algorithmic}
	%\end{flushleft}
\end{algorithm}

% ==============================================================================================

ایده آن است که تعامل 
$\Sigma$
را بوسیله چالش 
$J = J_1 || \cdots || J_t $
به عنوان خروجی تابع تصادفی 
$H$
شبیه سازی کرد.


\subsection{امضا براساس اثبات دانش صفر غیرتعاملی }\LTRfootnote{Signature from Non-interactive Zero-Knowledge Proofs}\label{sign_from_nzkp}

یک طرح امضای دیجیتال شامل سه الگوریتم زیر می‌باشد :
\begin{itemize}
	\item{
		$\bf KeyGen(\lambda)$
	}
		
	این الگوریتم یک پارامتر امنیتی 
	$\lambda$
	به عنوان ورودی گرفته و یک زوج کلید 
	$(pk,sk)$
	تولید می‌کند.
	\item {
	$\bf Sign(sk,m)$	
}

این الگوریتم پیام
$m$
وکلید خصوصی
$sk$
را به عنوان ورودی گرفته و خروجی آن امضای 
$\sigma$
می‌باشد.
\item{
$\bf Verify(pk,m,\sigma)$
}

این الگوریتم با داشتن کلید عمومی امضاکننده 
$\bf sk $
تایید می کند که آیا امضای دریافتی 
$\bf \sigma $
متعلق به پیام 
$\bf m $
می‌باشد یا نه
\end{itemize}

یک طرح امضای دیجیتال قویا تحت حمله متن انتخاب شده
\LTRfootnote{chosen message attack}
، غیرقابل جعل 
\LTRfootnote{SUF-CMA}
است اگر برای هر متخاصم
$\mathcal{A}$
\LTRfootnote{Adversary}
با داشتن الگوریتم زمان چندجمله‌ای کوانتومی و دسترسی کلاسیک به اوراکل امضای 
$\bf sig : m \mapsto Sign(sk,m)$
، حتی با احتمال خیلی کم هم نتواند یک زوج پیام-امضای جدید تولید کند.

فرض ‌کنیم یک تابع تولید کلید 
$\bf KeyGen$
، در اختیار داریم که یک جفت کلید عمومی-خصوصی
$\bf (sk,pk)$
را تولید می‌کند و هیج الگوریتم چندجمله‌ای کوانتومی حتی با احتمال خیلی کوچک  هم نتواند از طریق کلید عمومی
$\bf pk$
، یک کلید خصوصی
$\bf sk$
معتبر (متناظر با کلید عمومی) بازیابی کند. در این صورت یک اثبات هویت می‌تواند به صورت اثبات اظهار 
$\bf x=pk$
با شاهد 
$\bf w = sk$
در نظر گرفته شود که 
$\bf (x,w) \in R$
اگر و تنها اگر
$\bf (x,w)$
یک زوج کلید معتبر در نطر گرفته شود که می‌تواند توسط تابع 
$\bf KeyGen$
تولید شده باشد.	

در این صورت ، یک امضای دیجیتال اساسا یک اثبات دانش صفر غیرتعاملی هویت می‌باشد به جر آنکه لازم است یک پیام مشخص داخل
{\bf{اثبات(امضا)}}
وارد کنیم ، این عمل را به این صورت انجام می‌دهیم که متن موردنظر را به عنوان بخشی از اظهار 
$\bf x$
درنظر می‌گیریم به عبارت دیگر اظهار جدید ما به صورت 
$\bf x = (pk,m)$
درنظر گرفته می‌شود که در این صورت رابطه 
$\bf R $
پیام را در نظر نمی‌گیرد؛ به طور خلاصه ،
\begin{center}
$\bf ((pk,m),w) \in R$
\quad
اگر و تنها اگر
\quad
$\bf (pk,m)$
یک زوج کلید معتبر باشند	
\end{center}	
بنابراین از طریق یک اثبات هویت 
$\bf (P,V)$
با ویژگی 
$\bf NIZK$
 ، یک طرح امضای دیجیتال 
 \newline
 $\bf \mathcal{DS} = (KeyGen,Sign,Verify)$
 که
 $\bf Sign(sk,m) = P((pk,m),sk)$
 و
 \newline
 $\bf Verify(pk,m,\sigma = V((pk,m,\sigma)))$
 به دست می‌آید.
\newpage 
\textbf{ قضیه ۲ .}
اگر 
$(P,V)$
یک اثبات هویت 
$NIZK$ \LTRfootnote{Non-Interactive Zero-Knowledge}
با ویژگی‌های شبیه ‌سازی-صداقت و استخراج-آنلاین باشد آنگاه طرح امضای
$\mathcal{DS}$
ذکرشده در بالا یک امضای دیجیتال
SUF-CMA
در مدل ارواکل تصادفی کوانتومی خواهد بود.
% ---------------------------------------------------------------------------------------------
%        اثبات خوانده شده و به صورت کامل ذکر شود
% ---------------------------------------------------------------------------------------------


\section{امضای دیجیتال همسانی مبنا}\label{isogeny_ds}

در این بخش قصد داریم طرح امضای دیجیتال همسانی مبنای خود را بر اساس نتیجه‌ی خود از بخش قبلی بیان کنیم. اگر 
$\Sigma$
را به عنوان اثبات دانش صفر هویت همسانی مبنای توصیف شده در بخش 
[1]
نظر بگیریم آنگاه با اعمال ساخت آنره روی این پروتکل(زیگما) ، یک اثبات هویت غیرتعاملی 
$(P_{OE},V_{OE})$
به دست می‌آید که از این طریق یک طرح امضای دیجیتال معرفی می‌کنیم: 
\begin{itemize}
	\item[]{\bf پارامترهای عمومی }\LTRfootnote{Public Parameters}
	
	پارامترهای عمومی ما همان پارامترهای عمومی معرفی شده در پروتکل زیگما می‌باشد: یک عدد اول به فرم 
	$p = \ell_A^{e_A} \ell_B^{e_B} f \pm 1$
	، یک خم بیضوی سوپرسینگولار 
	$E$
	از مرتبه‌ی
	$(\ell_A^{e_A} \ell_B^{e_B})^2$
	در میدان 
	$\mathbb{F}^2$
	و نقاط 
	$(P_B,Q_B)$
	مولد زیرگروه تابی 
	$E[\ell_B^{e_B} ]$.
	
	\item[]{\bf تولیدکلید}\LTRfootnote{Key Generation}
	
	برای تولید کلید ، یک نقطه تصادفی
$S$
از مرتبه‌ی
$\ell_A^{e_A}$	
انتخاب و همسانی
\newline
$\phi : E \rightarrow E/ \langle S \rangle $
را محاسبه می‌کنیم و زوج کلید 
$(pk,sk)$
که  
$$pk = \Big(E/ \langle S \rangle , \phi (P_B) , \phi (Q_B) \Big)$$
و
$$ sk = S $$	
را به عنوان خروجی نمایش می‌دهیم.
\newline
\item[]{\bf امضا}\LTRfootnote{Signing}

برای امضای پیام 
$m$
، الگوریتم امضا را به صورت زیر انجام می‌دهیم: 
$$ Sign(sk,m) = P_{OE}((pk,m),sk)$$

\item[]{\bf تاییدسازی}\LTRfootnote{Verification}

برای تایید امضای
$\sigma$
برای پیام مشخص
$m$
، الگوریتم تایید را به صورت زیر انجام می‌دهیم:
$$ Verify(pk,m,\sigma) = V_{OE}((pk,m),\sigma) $$

الگوریتم های ۳و۴و۵ به طور صریح الگوریتم‌های تولبدکلید ، امضا و تاییدسازی را بیان می‌کنند.

\end{itemize}

% -----------------------------------------------------------
% algorithms 3,4,5
% ------------------------------------------------------------

\section{\bf جنبه های الگوریتمیک}\LTRfootnote{Algorithmic Aspects}\label{algorithm_aspect}

\subsection{\bf تولید پارامترها}\LTRfootnote{Parameter generation}\label{parameter_generate}

برای انتخاب‌های مشخص
$\ell_A^{e_A}$
و
$\ell_B^{e_B}$
، می‌توان هر مقدار تصادفی برای
$f$
(با هر اندازه رمزنگاری دلخواه) آزمایش کرد تا مقداری به دست آید که
$p = \ell_A^{e_A} \ell_B^{e_B} \cdot f - 1$
 یا  \\
$p = \ell_A^{e_A} \ell_B^{e_B} \cdot f + 1$
یک عدد اول شود. قضیه عدد اول در پیشرفت حساب ؟؟؟؟؟؟؟(به طور مشخص نسخه اثرگذار لاگارایز و اودلیزکو 
\cite{lagarias}
) یک کران پایین کافی چنین اعداد اولی مهیا می‌کنند؟؟؟؟؟.

بروکر در
\cite{broker}
نشان داده است برای هر عدد اول 
$p = \ell_A^{e_A} \ell_B^{e_B} \cdot f \pm 1$
مشخص ، می‌توان به راحتی یک خم بیضوی سوپرسینگولار 
$E$
روی میدان
$\mathbb{F}_{p^2}$
با مرتبه 
$({p \mp 1}^2) = ({\ell_A^{e_A} \ell_B^{e_B} \cdot f}^2)$
به دست آورد.

با شروع از خم
$E$
می‌توان یک خم سوپرسینگولار 
$E_0$
روی میدان
$\mathbb{F}_{p^2}$
با استفاده از گام تصادفی روی گراف همسانی انتخاب کرد. به طور معادل می‌توان به سادگی 
$E_0 = E$
در نظر گرفت. در هر دو مورد ، 
$E_0$
ساختار گروهی
${(\mathbb{Z} / (p \mp 1)\mathbb{Z})}^2$
را دارا می‌باشد.\\
برای انتخاب نقاط مولد زیرگروه
$E_0[\ell_A^{e_A}]$
، می‌توان یک نقطه تصادفی 
$P \:  {\in}_R \: E_0(\mathbb{F}_{p^2}) $
انتخاب و آن را در 
${(\ell_B^{e_B} \cdot f )}^2$
ضرب کرد تا نقطه
$P'$
 با مرتبه توانی از 
% $\ell_A^{e_A}$
$\ell_A$
 حاصل شود.با احتمال بسیار بالایی 
 $P'$
 دقیقا از مرتبه
 $\ell_A^{e_A}$
 می‌باشد؛ برای اثبات این ادعا می‌توان با ضرب 
$P'$
در توان‌هایی از 
 $\ell_A$
 آن را بررسی کرد. اگر بررسی موفقیت آمیز بود آنگاه 
 $P_A = P'$
 در نظر می‌گیریم در غیر اینصورت به دنبال یافتن نقطه‌ای دیگر برای یافتن
 $P$
 می‌شویم. برای به دست آوردن نقطه دوم ،
 $Q_A$
 از مرتبه‌ی
 $\ell_A$
 می‌توان از همین روش استفاده کرد.برای بررسی این که آیا نقطه
 $Q_A$
 از نقطه
 $P_A$
 متفاوت است ، می‌توان به راحتی با استفاده از زوجیت وایل
 \LTRfootnote{Weil Pairing}
  و محاسبه
 $e(P_A,Q_A)$
 در میدان
$E[\ell_A]$
 بررسی کرد که آیا نتیجه از مرتبه 
 $\ell_A$
 می‌باشد یا خیر ؛ مثل قبل با احتمال بسیار زیادی ممکن است این دو نقطه متفاوت از هم باشند ولی در صورتیکه این گونه نباشد می‌توان از نقطه  
   $Q_A$
 دیگری استفاده کرد.\\
 \textbf{توجه .}
 انتخاب نقاط مولد ، هیچ گونه تاثیری روی امنیت این طرح ندارد ؛ از آنجا که هر کدام از نقاط مولد با استفاده از لگاریتم گسسته توسیع یافته 
 \LTRfootnote{extended discrete logarithms}
 ، قابل تبدیل به یکدیگر می‌باشند . چنانچه در 
\cite{teske}
 اشاره شده است این محاسبه به راحتی در زیرگروه
 $E[\ell_A]$
 قابل انجام می‌باشد. 
 
 \newpage
 \subsection{\bf تبادل کلید و دیگر پروتکل‌ها}\label{key_exchange}
 \LTRfootnote{Key Exchange and other protocols}
 
 تبادل کلید در دو مرحله انجام می‌پذیرد. در هر مرحله آرش و بابک عملیات زیر را در هر طرف انجام می‌دهند:
 \begin{enumerate}
 	\item
 	محاسبه زیرگروه (هسته همسانی) 
 	$\langle R \rangle = \langle [m]P + [n]Q \rangle $
 	برای نقاط مشخص
 	$P$
 	و
 	$Q$.
 	
 	\item
 	محاسبه همسانی  
 	$\phi : E \rightarrow E/ \langle R \rangle $
 	برای خم بیضوی
 	$E$.
 	
 	\item 
 	(فقط)در مرحله اول ، محاسبه
 	$\phi(R)$
 	و
 	$\phi(S)$
 	برای بعضی نقاط
 	$R$
 	و
 	$S$؛
 \end{enumerate}
چنان که خم 
$E$
و نقاط
$P$
،
$Q$
،
$R$
،
$S$
وابسته به هر مرحله و هر بازیکنی که در یک طرف پروتکل می‌باشند.
%fiqure 1 in Jao paper %
عملیات مشابه نیاز دیگر پروتکل های قسمت 
\ref{isogeny_ds}
 دارند. در ادامه پیاده سازی موثر هر مرحله را نشان خواهیم داد.

\subsection{\bf 
محاسبه 
$\langle [m]P + [n] Q \rangle $
}\label{computing_kernel}
؟؟؟
بدون کوچکترین خدشه‌ای به این زیرگروه ، می‌توان فرض کنیم که 
$m$
دارای عنصر وارون در پیمانه‌ی مرتبه‌ی گروه می‌باشد ، در این حالت 
$R' = P + [m^{-1}n]Q$
زیرگروهی همانند دیگر مولدها می‌باشد. محاسبه 
$R'$
با روش استاندارد رویکرد دوبرابرکردن-و-جمع 
\LTRfootnote{double-and-add}
نیاز یه نصف عملیات محاسبات
$[m]P + [n]Q$
معمولی را دارا می‌باشد( برای روش های بهتر محاسبه عملیات معمولی به مراجعه 
\cite{ antipa, elgamal, solinas}
شود).

با این حال ،  محاسبه 
$P + [m^{-1}n]Q$
با روش دوبرابرکردن-و-جمع یک حفره امنیتی (اشکال بزرگ) را داراست : در برابر حملات آنالیز قدرت ساده 
\LTRfootnote{simple power analysis (SPA)}
\cite{spa}
آسیب پذیر می‌باشد. برای جلوگیری از این حمله می‌توان از نردبان مونتگومری
\LTRfootnote{Montgomery ladder}
\cite{montgomery}
برای محاسبه 
$[m^{-1}n]Q$ 
استفاده کرد و سپس 
$P$
را به آن اضافه کرد ، اما این روش به طور قابل ملاحظه‌ای کند می‌باشد.

در عوض در الگوریتم ۱ ، یک نردبان بسیار موثرتری ارائه می‌دهیم و مستقیما 
$P + [m^{-1}n]Q$
را محاسبه می‌کنیم. ایده اصلی این طرح ساده است : در هر تکرار ، ثبات های 
$A$
و
$B$
و
$C$
محتوی مقدارهای به ترتیب
$[x]Q$
و
$[x+1]Q$
و
$P+[x]Q$
می ‌باشند ، که 
$x$
حاوی ارزش چپ ترین بیت
$m^{-1}n$
می‌باشد.تابع 
$dadd(A,B,C)$
معرف جمع تفاضلی 
\LTRfootnote{differential addition}
\cite{montgomery}
می‌باشد.تاثیر پیاده سازی نردبان معرفی شده در این قسمت به کارآمدی روش دوبرابرکردن-و-جمع ساده روی خم های دوقولوی ادوارد
\LTRfootnote{twisted Edwards curves}
\ref{model_choice}
می‌باشد.

\subsection{\bf   محاسبه همسانی‌های با درجه هموار}\label{smooth_isogeny}
\LTRfootnote{Computing smooth degree isogenies}

در این قسمت به تشریح چگونگی محاسبه و ارزیابی همسانی‌ها توسط آرش و بابک می‌پردازیم. فرض کنیم 
$E$
یک خم بیضوی و 
$R$
یک نقطه از مرتبه 
$\ell^e$
باشد. هدف ما محاسبه تصویر خم 
$E/ \langle R \rangle $
و ارزیابی همسانی 
$\phi : E \rightarrow E/ \langle R \rangle $
در بعضی نقاط روی خم 
$E$
می‌باشد. 
% ==============================================================================================
\begin{figure}[H]\label{}
	\begin{center}
		
		
		\caption{
			ساختمان محاسبات ساخت 
			$\phi = {\phi}_5 \circ \cdots  \circ {\phi}_0$    
		}
		
	\end{center}
\end{figure}
% ==============================================================================================
زمانیکه درجه 
$\phi$
هموار باشد بهتر است آن را به زنجیره‌ای از
$\ell$
-همسانی ها تجزیه کرد. اگر
$E_0 = E$
و
$R_0 = R$
در نظر بگیریم ، آنگاه برای هر 
$0 \leq i < e $
می‌توان مقادیر زیر را در نظر گرفت :
$$
 E_{i+1} = E_i / \langle \ell^{e-i-1}R_i \rangle , \quad
 \phi_i : E_i \rightarrow E_{i+1} , \quad
 R_{i+1} = \phi_i(R_i).
$$
چنانکه 
$E / \langle R \rangle = E_e$
و
$\phi = \phi_{e-1} \circ \cdots \circ \phi_0$
می‌باشد.

توجه به این نکته لازم است که از آنجا که زیرگروه 
$\ell$
-تابی 
$\langle R_i \rangle $
خم 
$E_i$
مشخص می‌باشند ، 

 خم بیضوی 
$E_{i+1}$
و همسانی
$\phi_i$
می‌توانند توسط فرمول ولو 
\LTRfootnote{Velu's formulas}
\cite{velu}
به راحتی محاسبه شوند.
در 
\cite{jao2011towards}
، دو پیشنهاد برای داشتنی پیچیدگی درجه دو برای 
$e$
بیان شده است  ؟؟؟؟؟.
% به هر حال می‌توانیم این کار را بهتر انجام دهیم. 
\\
شکل بالا خلاصه‌ای از ساختار محاسباتی مسئله برای 
$e = 6$
می‌باشد. نقطه‌های توپر این گراف نشان دهنده نقاط می‌باشد. نقطه‌های موجود در یک سطح افقی نشان دهنده آن است که این نقاط از یک مرتبه می‌باشند و همچنین نقطه‌های روی خط مورب چپین نشان دهنده آن است که این نقطه‌ها همگی متعلق به یک خم می‌باشند. یال‌های نقطه‌چین همگی جهت‌دار و به سمت پایین می‌باشند ؛ یال‌های چپین معرف آن هستند که نقطه‌ها 
$\ell$
برابر شده‌اند و یال‌های راست‌چین هم یک 
$\ell$
ـ همسانی را نشان می‌دهند.
% try to better writing ..
در ابتدای اجرای الگوریتم ، تنها نقطه 
$R_0$
را در اختیار داریم. به بیان دیگر هدف ما در این الگوریتم  محاسبه تمام نقاط روی خط پایانی توسط نقطه آغازین 
$R_0$
می‌باشد (ورودی این الگوریتم نقطه 
$R_0$
و خروجی این الگوریتم نقاط 
$[\ell^5]R_0$
،
$[\ell^4]R_1$
،
$[\ell^3]R_2$
،
$[\ell^2]R_3$
،
$[\ell^1]R_4$
و
$R_5$
می‌باشد).
در واقع با دانستن نقطه 
$[\ell^{e-i-1}]R_i$
، می‌توانیم هسته همسانی
$\phi_i$
را به تعداد
$\mathcal{O}(\ell)$
جمع نقاط ، محاسبه کنیم ؛ که در این صورت پیچیدگی محاسبات به طور قابل توجهی کم می‌شود. در ادامه می‌توانیم از طریق فرمول ولو ، همسانی 
$\phi_i$
و خم 
$E_{i+1}$
را محاسبه کنیم. 
% complete next statemnet correctly !!!
\\
برای فهم بیشتر این الگوریتم مراحل ذکر شده در مثال 
$e=6$
را مرحله به مرحله نمایش می‌دهیم :
\begin{itemize}
	
	\item[] {}
	\begin{flushleft}
		$
		i=0 \Rightarrow \quad 
		E_1 = E_0 / \langle \ell^{4}R_0 \rangle , \quad 
		\phi_0 : E_0 \rightarrow E_1 , \quad 
		R_1 = \phi_0(R_0)
		$
	\end{flushleft}
	
	\item[] {}
	\begin{flushleft}
		$
		i=1 \Rightarrow \quad 
		E_2 = E_1 / \langle \ell^{3}R_1 \rangle , \quad 
		\phi_1 : E_1 \rightarrow E_2 , \quad 	R_2 = \phi_1(R_1) = \phi_1(\phi_0(R_0))
		$
	\end{flushleft}

	\item[] {}
	\begin{flushleft}
		$
		i=2 \Rightarrow \quad 
		E_3 = E_2 / \langle \ell^{2}R_2 \rangle , \quad 
		\phi_2 : E_2 \rightarrow E_3 , \quad 	R_3 = \phi_2(R_2) = \phi_2(\phi_1(\phi_0(R_0)))
		$
	\end{flushleft}

	\item[] {}
	\begin{flushleft}
		$
		i=3 \Rightarrow \quad 
		E_4 = E_3 / \langle \ell^{1}R_3 \rangle , \quad 
		\phi_3 : E_3 \rightarrow E_4 , \quad 	R_4 = \phi_3(R_3) = \phi_3(\phi_2(\phi_1(\phi_0(R_0))))
		$
	\end{flushleft}

	\item[] {}
	\begin{flushleft}
		$
		i=4 \Rightarrow \quad 
		E_5 = E_4 / \langle \ell R_4 \rangle , \quad 
		\phi_4 : E_4 \rightarrow E_5 , \quad 	R_5 = \phi_4(R_4) = 
		\phi_4(\phi_3(\phi_2(\phi_1(\phi_0(R_0)))))
		$
	\end{flushleft}

	\item[] {}
	\begin{flushleft}
		$
		i=5 \Rightarrow \quad 
		E_6 = E_5 / \langle R_5 \rangle , \quad 
		\phi_5 : E_5 \rightarrow E_6 , \quad 	R_6 = \phi_5(R_5) = 
		\phi_5(\phi_4(\phi_3(\phi_2(\phi_1(\phi_0(R_0))))))
		$
	\end{flushleft}
			
\end{itemize}

\subsection{\bf انتخاب مدل}\LTRfootnote{choice of the model}\label{model_choice}

\subsection{\bf ساده سازی نقاط تاب دار}\LTRfootnote{Sampling Torsion Points}\label{torsion_point}

\subsection{\bf محاسبه‌ی همسانی‌ها}\LTRfootnote{Computing Isogenies}\label{compute_isogeny}
 
\subsection{\bf سایز پارامترها}\LTRfootnote{Parameter Sizes}\label{size_parameter} 

% =========================== Security =========================================================
\section{\bf امنیت}\LTRfootnote{Security}\label{security}

امنیت سیستم های رمزنگاری همسانی مبنا بر اساس سختی مسائلی همچون دو مساله  بیان شده در زیر بنا شده است که حتی در برابر کامپیوترهای کوانتومی نیز کاملا ایمن می‌باشند. در طرح امضای دیجیتال ارائه شده در این پایان نامه ، امنیت بر اساس این دو مساله بنا شده است.\\


اگر عدد اول 
$p$
را به فرم
$\ell_A^{e_A} \ell_B^{e_B} . f \pm 1 $
در نظر بگیریم ، آنگاه یک خم بیضوی سوپرسینگولار 
$E_0$
روی میدان
$\mathbb{F}_{p^2}$
وجود دارد که زوج نقاط
$\{P_A , Q_A \}$
و
$\{ P_B , Q_B \}$
مولدهای زیرگروه های
$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}$
و همچنین نقاط کمکی گفته شده در بالا نمی‌توان زیرگروهی که از طریق فرمول ولو امکان‌پذیر است را به دست آورد ؟؟؟.
\\
\textbf{توجه.}
ذکر این نکته لازم است که با داشتن مولد
$R_A = [m_A]P_A + [n_A]Q_A$
، یافتن نقاط
$m_A$
و
$n_A$
به سادگی توسط لگاریتم گسسته توسیع‌یافته 
\LTRfootnote{extended discrete logarithms}
 با این فرض که خم 
$E$
هموار باشد، امکان‌پذیر است.
\cite{eDS}
\\
\\
\textbf{ مسئله ساخت خم سوپرسینگولار تصمیم‌پذیر : }
 \LTRfootnote{Decisional Supersingular Product (DSSP problem)}

فرض کنیم
$\phi : E_0 \rightarrow E_3$
یک همسانی با مرتبه 
$\ell_A^{e_A}$
باشد. با داشتن
$(E_1 , E_2 , {\phi}' )$
 ساده سازی شده با احتمال 
 $1/2$
 از طریق دو توزیع زیر ، فهمیدن اینکه کدام رخ می‌دهد یک مسپله سخت می‌باشد :
 \begin{itemize}
 	
 	\item 
 	
 	\item 
 	
 \end{itemize}
 


\subsection{\bf امنیت اثبات دانش صفر}\label{zkp_security}
\LTRfootnote{Security of the Zero-Knowledge Proof}


 در 
$[12,S 6.2]$
اثبات شده است که طرح اثبات دانش صفر هویت همسانی مبنای معرفی شده در قسمت 
\ref{ZKPOI}
دارای ویژگی‌های تمامیت ، صداقت ویژه و دانش صفر تاییدکننده صادق می‌باشد اگر فرض کنیم که مسائل 
$CSSI$
و
$DSSP$
مسائلی سخت می‌باشند.با این وجود برای امنیت کامل ، ساخت آنره باید دارای ویژگی صداقت ویژه باشد.\\

\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)$
یک مولد هسته 
${\psi}'$
می‌باشد ، بنابراین می‌توانیم دوگان همسانی یعنی
${\psi}' : E/ \langle R \rangle \rightarrow E $
را به دست آوریم و 
${\psi}' (resp_1)$
را به عنوان مولد
$\langle S \rangle $
به دست آوریم.

% ==============================================================================================
\begin{figure}[H]
	\begin{center}
		
		\begin{tikzcd}
			E \arrow[r, dashrightarrow ,"\phi"] \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{
			اگر
			$\psi$
			و
			${\phi}'$    
			هر دو همزمان معلوم باشند آنگاه می‌توان زیرگروه مخفی 
			$\langle S \rangle$
			را به دست آوریم.
		}
		\label{}
		
	\end{center}
\end{figure}
% ==============================================================================================

\subsection{امنیت امضا}\label{sign_security}







% ======================================================================
% Undeniable Signature
% ======================================================================
\newpage
\section{\bf امضای غیرقابل انکار}\label{Undeniable_signature}\cite{undeniable}
\LTRfootnote{Undeniable Signature}
% تعریفات از مقاله universally Compasable Undeniable Signature
مفهوم طرح امضای غیرقابل انکار اولین بار توسط چام و آنترپن
\cite{undeniable_chaum}
معرفی شده است. در یک طرح امضای غیرقابل انکار، امضاکننده یک امضای غیرقابل انکار
$\sigma$
را تولید می‌کند که توسط هرکسی(به صورت عمومی) قابل تایید نمی‌باشد. بنابراین تاییدکننده برای تایید امضا نیاز به تعاملاتی با امضاکننده دارد که برای تایید یا انکار امضای 
$\sigma$
، امضاکننده یک اثبات دانش صفر را بوسیله اجرای پروتکل تایید یا پروتکل انکار انجام می‌دهد.
\\
طرح امضای غیرقابل انکار موجب پیدایش برنامه‌های کاربردی فراوانی در رمزنگاری شده است. از جمله‌ی این کاربردها می‌توان به نرم‌افزار صدور مجوز
\LTRfootnote{licensing software}
،پول الکترونیکی
\LTRfootnote{electronic cash}
، رای‌گیری الکترونیکی
\LTRfootnote{voting electronic}
و حراج الکترونیکی
\LTRfootnote{electronic auction}
اشاره کرد.
% ادامه‌ی مقاله که به مباحث امنیت آن برمی‌گردد در اینجا ذکر نکردم.
\subsection{\bf تعریف}
مطابق با تعریف رسمی ارائه شده در
\cite{convertibleـundeniable}
، یک طرح امضای غیرقابل انکار بوسیله چندتایی زیر مشخص شده است:
$$ \Sigma = \big( G_{sign} , Sign , Check , Sim , \pi_{con} , \pi_{dis} \big). $$

الگوریتم
$G_{sign}$
تولیدکننده کلید، الگوریتم
$Sign$
یک الگوریتم امضا، الگوریتم 
$Check$
یک الگوریتم بررسی اعتبار، الگوریتم
$Sim$
یک شبیه‌ساز امضا ، پروتکل 
$\pi_{con}$
یک پروتکل تایید و پروتکل 
$\pi_{dis}$
یک پروتکل انکار می‌باشد.
\\
الگوریتم تولیدکننده کلید 
$G_{sign}$
، یک الگوریتم چندجمله‌ای احتمالاتی 
\LTRfootnote{PPT(probabilistic polynomial-time)}
می‌باشد که خروجی آن زوج کلید
$(vk,sk)$
می‌باشد که 
$vk$
یک کلید تاییدساز و 
$sk$
یک کلید امضا 
\RTLfootnote{فرض می‌کنیم که 
$sk$
به طور منحصر به فرد توسط
$vk$
تعیین شده است.
}
می‌باشد.
\\
 فضای پیام 
$\mathcal{M}$
توسط 
$vk$
مشخص شده است.
\\
 الگوریتم امضای
$Sign$
، یک الگوریتم چندجمله‌ای احتمالاتی می‌باشد که امضای 
$\sigma$
را از طریق پیام 
$m \in \mathcal{M}$
 و کلید امضای 
$sk$
 به عنوان ورودی‌هایش تولید می‌کند.
 \\
  اگر 
$\sigma$
 ، خروجی الگوریتم
$Sign(sk,m)$
با رشته تصادفی 
$r$
باشد، آنگاه زوج 
$(m,\sigma)$
را معتبر می‌گوییم، در غیر این صورت آن را نامعتیر می‌گوییم.
\\
الگوریتم بررسی اعتبار
$Check$
، یک الگوریتم چندجمله‌ای قطعی می‌باشد که:
$$ Check \big( (vk,m),\sigma \big) = 
	\begin{cases}
		1 & \text{
			اگر خروجی زوج 
			$(m,\sigma)$
			معتبر باشد.
				} \\
			0 & \text{
				اگر خروجی زوج 
				$(m,\sigma)$
				نامعتبر باشد.
			}
	\end{cases}
$$

الگوریتم شبیه‌ساز
$Sim$
یک الگوریتم چندجمله‌ای احتمالاتی است که یک امضای شبیه‌سازی‌شده‌ی
${\sigma}' = Sim(vk,m)$
را تولید می‌کند.

یک طرح امضای غیرقابل انکار باید ویژگی‌های غیرقابل جعلی
\LTRfootnote{unforgeability}
و غیرقابل دسترس‌پذیری (نامرئی بودن)
\LTRfootnote{invisibility}
را داشته باشد. غیرقابل دسترس‌پذیری به معنای آن است که برای یک پیام 
$m$
، دریافت‌کننده نمی‌تواند متوجه شود که 
$\sigma$
، یک امضای معتبر است یا یک امضای شبیه‌سازی شده. این بدین معنی است که دریافت کننده نمی‌تواند اعتبار زوج 
$(m,\sigma)$
را به تنهایی تایید کند.درعوض با همکاری امضاکننده می‌توان اعتبار و عدم اعتبار زوج 
$(m,\sigma)$
را با اجرای پروتکل تاییدساز
$\pi_{con}$
و پروتکل انکار
$\pi_{dis}$
و خروجی متناظر با آن پروتکل به دست آورد. پروتکل
$\pi_{con}$ 
، یک سیستم اثبات دانش صفر تعاملی
\LTRfootnote{zero-knowledge interactive proof system (ZKIP)}
روی یک زبان 
$L_0 = \{ (vk,m,\sigma) | 
\text{زوچ 
$(m,\sigma)$
معتبر هستند
}
\}$
 و پروتکل 
$\pi_{dis}$
، یک سیستم اثبات دانش صفر تعاملی روی یک زبان 

$L_1 = \{ (vk,m,\sigma) | 
\text{زوچ 
	$(m,\sigma)$
	معتبر نیستند
}
\}$
می‌باشد. هر سیستم اثبات دانش صفر تعاملی باید ویژگی‌های تمامیت ، صداقت و اثبات صفر را داشته باشند.


\subsection{امنیت امضای غیرقابل انکار}
\LTRfootnote{Security of Undeniable Signature}
\\
\textbf{غیرقابل جعل بودن .}
مفهوم غیرقابل جعل بودن را توسط بازی زیر بین یک چالشگر 
$\mathcal{CH}$\LTRfootnote{challenger}
 و یک متخاصم
$\mathcal{A}$\LTRfootnote{adversary}
تشریح می‌کنیم.
\begin{enumerate}
	
	\item 
	چالشگر یک زوج کلید
	$(vk,sk)$
	را به صورت تصادفی تولید و کلید تاییدساز 
	$vk$
	را به متخاصم می‌دهد.
	\item 
	% for i = 1,2, ... , q_s for some q_s
	برای 
	$i = 1,2,\cdots, q_s$
	وبرای بعضی
	$q_s$
	،متخاصم برای امضای پیام 
	$m_i$
	درخواستی به اوراکل امضا می‌فرستد و متعاقبا یک امضای
	$\sigma_i$
	دریافت می‌کند.
	\item 
	در پایان، متخاصم زوج جعلی 
	$(m^*,{\sigma}^*)$
	را به عنوان خروجی نمایش می‌دهد.
\end{enumerate}
متخاصم این اجازه را دارد تا درخواست
$(m_j,\sigma_j)$
را در مرحله دوم برای اوراکل تایید/انکار ارسال کند و پاسخ اوراکل تایید/انکار به صورت زیر می‌باشد:
\begin{itemize}
	\item 
	اگر 
	$(m_j,\sigma_j)$
	یک زوج معتبر باشد آنگاه اوراکل بیت
	$\mu = 1$
	را به عنوان خروجی برمی‌گرداند و اجرای پروتکل تایید
	$\pi_{con}$ 
	را با متخاصم در جریان می‌گذارد.
	
	\item 
	در غیر‌اینصورت، اوراکل بیت
	$\mu = 0$
	را برمی‌گرداند و بر این اساس پروتکل انکار 
	$\pi_{dis}$
	را با متخاصم در جریان می‌گذارد.
\end{itemize}

گوییم متخاصم در جعل(قوی) موفق شده است اگر زوج
$(m^*,\sigma^*)$
معتبر باشد و این زوج در میان زوج‌های 
$(m_i,\sigma_i)$
تولید شده در میان درخواست‌های امضای اوراکل نباشد.
\RTLfootnote{
گوییم متخاصم در جعل(ضعیف) موفق شده است اگر
$(m^*,\sigma^*)$
معتبر باشد و 
$m^*$
هرگز برای امضا از اوراکل درخواست نشده باشد.غیرقابل‌جعلی(ضعیف) و غیرقابل‌جعلی(قوی) یکی هستند اگرالگوریتم امضا قطعی باشد و درنتیجه برای هر پیام یک امضای منحصر به فرد وجود دارد که به درستی تایید می‌شود.
}
\\
\textbf{تعریف ۱ .}
گوییم 
$\Sigma$
قویا غیرقابل‌جعل است اگر احتمال آنکه متخاصم در جعل(قوی) موفق شود (برای هر متخاصم چندجمله‌ای احتمالاتی در بازی بالا)، ناچیز باشد.
\\
\\
\textbf{غیرقابل دسترس‌پذیری . }
دامگارد و پدرسون بوسیله بازی زیر بین چالشگر و متخاصم در 
\cite{convertibleـundeniable}
به معرفی مفهوم غیرقابل‌دسترس‌پذیری پرداخته‌اند.
\begin{enumerate}
	
	\item 
	چالشگر یک زوج کلید
	$(vk,sk)$
	را به صورت تصادفی تولید و کلید تاییدساز 
	$vk$
	را به متخاصم می‌دهد.
	\item 
	متخاصم مجاز است یک سری درخواست برای امضای پیام
	$m_i$
	به اوراکل امضا ارسال کند و امضای
	$\sigma_i$
	را دریافت کند.
	\item 
	% at some point
	در برخی موارد، متخاصم یک پیام 
	$m^*$
	را انتخاب و برای چالشگر ارسال می‌کند.
	\item 
	چالشگر یک بیت تصادفی 
	$b$
	را انتخاب می‌کند.
	\item 
	اگر 
	$b = 1$
	آنگاه چالشگر امضای واقی
	$\sigma^* = Sign(sk,m^*)$
	را محاسبه می‌کند. در غیر اینصورت امضای ساختگی(جعلی) 
	$\sigma^* = Sim(sk,m^*)$
	را محاسبه می‌کند. و در ادامه امضای
	$\sigma^*$
	را برای متخاصم برمی‌گرداند.
	\item 
	متخاصم دوباره چند درخواست امضا را انجام می‌دهد.
	\item 
	در انتهای بازی، متخاصم یک بیت حدسی 
	$b'$
	را برمی‌گرداند.
	\\
	متخاصم مجاز است در مراحل ۲ و ۵ ، درخواست 
	$(m_j,\sigma_j)$
	را برای اوراکل تایید/انکار ارسال کند.
\end{enumerate}

با این حال متخاصم اجازه ندارد تا چالش 
$(m^*,\sigma^*)$
را در مرحله‌ی ۵ از اوراکل تایید/انکار درخواست کند. همچنین متخاصم مجاز نیست تا درخواست
$m^*$
را برای اوراکل امضا ارسال کند.
\\
\textbf{تعریف ۲ .}
گوییم
$\Sigma$
غیرقابل‌دسترس است اگر برای هر متخاصم با زمان چندجمله‌ای احتمالاتی در بازی بالا،‌  احتمال آن‌که 
$b = b'$
خیلی ناچیز باشد.

\subsection{پروتکل}\LTRfootnote{Protocol}

برای پیاده‌سازی این طرح امضا به روی خم‌های سوپرسینگولار لازم است تا عدد اول 
$p$
 به فرم 
 $\ell_A^{e_A} \ell_M^{e_M} \ell_C^{e_C} \cdot f \pm 1$
داشته باشیم و سپس یک خم بیضوی سوپرسینگولار 
$E$
روی میدان
$\mathbb{F}_{p^2}$
معرفی کنیم چنانکه مرتبه‌ی خم (
$\# E(\mathbb{F}_{p^2})$
)
، مقدار
$(\ell_A^{e_A} \ell_M^{e_M} \ell_C^{e_C})^2$
را عاد کند.همچنین لازم است تا مولدهای زیرگروه‌های 
$E[\ell_A^{e_A}]$
،
$E[\ell_M^{e_M}]$
و
$E[\ell_C^{e_C}]$
را که به ترتیب شامل
$\{ P_A,Q_A\}$
،
$\{P_M,Q_M\}$
و
$\{P_C,Q_C\}$
می‌باشد را نیز به دست آوریم.در طراحی این پروتکل معمولا نقاط
$\{ P_A,Q_A\}$
ساخت کلید و نقاط
$\{P_M,Q_M\}$
برای داده‌ی پیام و نقاط
$\{P_C,Q_C\}$
برای داده‌های تعهد مورد استفاده قرار می‌گیرند.
% ادامه مقاله جائو با مقاله اصلی همپوشانی دارد و یکبار باید ذکر شود !!!!!!!!!!!!!!

امضاکننده به صورت تصادفی دو عدد صحیح
$m_A$
و
$n_A$
را از میدان
$\mathbb{Z} / \ell_A^{e_A} \mathbb{Z}$
انتخاب می‌کند(
$m_A,n_A \in \mathbb{Z} / \ell_A^{e_A} \mathbb{Z}$
)
. و سپس زیرگروه
$K_A = [m_A]P_A + [n_A]Q_A$
را به دست آورده و خم بیضوی
$E_A = E/ \langle K_A \rangle$
را محاسبه می‌کند. در انتها همسانی
$\phi_A$
که از
$E$
به
$E_A$
می‌باشد (
$ \phi_A : E \rightarrow E_A $
) را محاسبه می‌کند.
\begin{itemize}
	\item[]{\bf پارامترهای عمومی:}
	$p$
	،
	$E$
	،
	$\{ P_A,Q_A\}$
	،
	$\{P_M,Q_M\}$
	،
	$\{P_C,Q_C\}$
	و  تابع هش 
	$H : \{0,1\}^* \rightarrow \mathbb{Z}$
	.
	\item[]{\bf کلید عمومی :  }
	$E_A$
	،
	$\phi_A(P_C)$
	و
	$\phi_A(Q_C)$
	.
	\item[]{\bf کلید خصوصی :   }
	$m_A$
	و
	$n_A$
	.
\end{itemize}

برای امضای پیام
$M$
لازم است تا با استفاده از تابع هش به مقدار
$h = H(M)$
دست بیابیم. هسته همسانی به شکل
$K_M  = P_M + [h]Q_M$
خواهد بود. در ادامه امضاکننده همسانی‌های زیر 

\begin{itemize}
	
	\item 
	$\phi_M : E \rightarrow E_M = E / \langle K_M \rangle $
	
	\item 
	$\phi_{M,AM} : E_M \rightarrow E_{AM} = E_M / \langle \phi_{M}(K_A) \rangle$
	
	\item 
	$\phi_{A,AM} : E_A \rightarrow E_{AM} = E_A / \langle \phi_A(K_M) \rangle $
\end{itemize}
همراه با نقاط کمکی 
$\phi_{M,AM}(\phi_M(P_C))$
و
$\phi_{MaAM}(\phi_M(Q_C))$
محاسبه می‌کند.امضاکننده سپس این دو نقطه کمکی را به همراه خم بیضوی
$E_{AM}$
به عنوان امضا منتشر می‌کند.(شکل 
\ref{fig:sig_generation}
).

پروتکل تایید به شکل زیر انجام می‌شود.در ابتدا خم 
$E_{AM}$
را بدون افشای همسانی‌های که آن را ساخته‌اند تایید می‌کنیم، برای این منظور خم
$E_{AM}$
را بوسیله همسانی 
$\phi_C$
کور می‌کنیم و سپس همسانی‌های کورشده را نمایش می‌دهیم‌.(شکل 
\ref{fig:confirmation}
).

\begin{enumerate}
	\item 
	امضاکننده به صورت مخفی اعداد تصادفی
	$m_C$
	و
	$n_C$
	را از میدان 
	$\mathbb{Z} / \ell_C^{e_C} \mathbb{Z}$
	انتخاب می‌کند(
	$m_C , n_C \in \mathbb{Z} / \ell_C^{e_C} \mathbb{Z}$
	)
	، و نقطه
	$K_C = [m_C]P_C + [n_C]Q_C$
	را به همراه خم‌ها و همسانی‌های شکل ۳ محاسبه می‌کند.چنانچه در شکل گویاست داریم:
	\begin{itemize}
		\item 
		$E_C = E / \langle K_C \rangle$
		
		\item 
		$E_{MC} = E_M / \langle \phi_M(K_C) \rangle = E_C / \langle \phi_C(K_M) \rangle$
		
		\item 
		$E_{AC} = E_A / \langle \phi_A(K_C) \rangle = E_C / \langle \phi_C(K_A) \rangle$
		
		\item 
		$E_{AMC} = E_{MC} / \langle \phi_{C,MC}(K_A) \rangle $
	\end{itemize}

	\item 
	امضاکننده خم‌های
	$E_C$
	،
	$E_{AC}$
	،
	$E_{MC}$
	،
	$E_{AMC}$
	و همچنین 
	$ker(\phi_{C,MC})$
	را به عنوان تعهد منتشر می‌کند.
	
	\item 
	تاییدکننده به طور تصادفی بیت 
	$b \in \{0,1\}$
	را انتخاب می‌کند.
	
	\item 
	اگر 
	 $b=0$
	 آنگاه امضاکننده 
	 $ker(\phi_C)$
	 را منتشر می‌کند. تاییدکننده به همراه کلیدعمومی امضاکننده 
	 $ker(\phi_{A,AC})$
	 را محاسبه می‌کند.با دانستن
	 $ker(\phi_M)$
	 ،تاییدکننده می‌تواند 
	 $\phi_{M,MC}$
	 را محاسبه کند. همچنین تاییدکننده با کمک نقاط کمکی داده شده در امضا ، می‌تواند
	 $\phi_{AM,AMC}$
	 را محاسبه کند. تاییدکننده همچنین هر نگاشت همسانی‌ بین دو خم اشاره شده در تعهد را بررسی می‌کند.
% why ?????
با اطلاع از 
$ker(\phi_C)$
، همچنین به طور مستقل می‌تواند 
$\phi_{C,MC}$
را دوباره محاسبه و بررسی کند که آیا با تعهد ارائه شده همخوانی دارد یا نه.
% please understand the two last statement and write to persian correctly !!!!!

\item 
اگر
$b=1$
آنگاه امضاکننده 
$ker(\phi_{C,AC})$
را نمایش می‌دهد. در ادامه تاییدکننده همسانی‌های 
$\phi_{MC,AMC}$
و
$\phi_{AC,AMC}$
را محاسبه می‌کند و نگاشت‌های 
$\phi_{C,AC}$
،
$\phi_{MC,AMC}$
و
$\phi_{AC,AMC}$
را بین دو خم معرفی شده متناظر در تعهد را بررسی می‌کند.
\end{enumerate}


حال به تشریح پروتکل انکار می‌پردازیم. فرض کنید امضاکننده یک امضای جعلی
$(E_F,F_P,F_Q)$
برای پیام 
$M$
ارائه کند، که 
$E_F$
خم جعلی 
$E_{AM}$
،
$\{F_P,F_Q\}$
نقاط کمکی جعلی به‌جای نقاط معادل کمکی صحیح
$\phi_{M,AM}(\phi_M(P_C))$
و
$\phi_{M,AM}(\phi_M(Q_C))$
باشند.پس طبق طرح ارائه شده ما موظفیم تا خم
$E_F$
را بدون افشای خم
$E_{AM}$
، انکار کنیم.بدین منظور قبل از به دست آوردن خم
$E_{AMC}$
،
خم
$E_{AM}$
را کور می‌کنیم. و  اطلاعاتی به اندازه کافی در اختیار تاییدکننده می‌گذاریم تا بتواند خم
$E_{FC}$
را محاسبه و رابطه
$E_{FC} \ne E_{AMC}$
را بررسی کند.
\begin{enumerate}
	\item 
	امضاکننده به صورت مخفی اعداد تصادفی 
	$m_C$
	و
	$n_C$
	را از میدان
	$\mathbb{Z} / \ell_C^{e_C} \mathbb{Z}$
	انتخاب می‌کند، و 
	$K_C = [m_C]P_C + [n_C]Q_C$
	را به همراه تمام خم‌ها و همسانی‌های نشان داده شده در شکل 
\ref{fig:disavowal}
	 محاسبه می‌کند.
	
	\item 
	امضاکننده خم‌های
	$E_C$
	،
	$E_{AC}$
	،
	$E_{MC}$
	و
	$E_{AMC}$
	را به همراه 
	$ker(\phi_C)$
	به عنوان تعهد منتشر می‌کند.
	
	\item 
	تاییدکننده یک بیت تصادفی
	$b \in \{0,1\}$
	انتخاب می‌کند.
	
	\item 
	اگر
	$b=0$
	آنگاه امضاکننده 
	$ker(\phi_C)$
	را منتشر می‌کند. در ادامه تاییدکننده همسانی‌های 
	$\phi_C$
	،
	$\phi_{M,MC}$
	،
	$\phi_{A,AC}$
	را به‌همراه همسانی
	$\phi_F : E_F \rightarrow E_{FC} = E_F / \langle [m_C]F_P + [n_C]F_Q \rangle$
	محاسبه کرده و هر نگاشت همسانی بین دوخ مشخص شده در در تعهد را بررسی می‌کند. تاییدکننده به طور مستقل همسانی
	$\phi_{C,MC}$
	را محاسبه و بررسی می‌کند که آیا خروجی، همان همسانی ذکرشده در تعهد می‌باشد یا خیر
	
	\item 
	اگر 
	$b=1$
	آنگاه امضاکننده 
	$ker(\phi_{C,AC})$
	را منتشر می‌کند و در ادامه تاییدکننده همسانی‌های 
	$\phi_{AC,AMC}$
	و
	$\phi_{MC,AMC}$
	را محاسبه و بررسی میکند که آیا این همسانی‌ها نگاشتی به خم
	$E_{AMC}$
	دارند یا خیر.
\end{enumerate}

% ==============================================================================================
% figure !! for demontrate Signature generation
\begin{figure}[H] 
	\begin{center}
		
		%\begin{tikzcd}
			% & E_A \arrow[dd , dashed , "\phi_{A,AM}" description]   \\
			% & E \arrow[dd , "\phi_{M}" description ]
			% & & E_{AM} \\
			% & E_M \arrow[ur , dashed , "\phi_{M,AM}" description] \\
		    % ----------------------------------------------------------------------
			% E \arrow{d} {\phi_M} \arrow{r}{\phi_A} & E_A \arrow{d} {\phi_{A,AM}}\\ 
			% E_M \arrow{r} {\phi_{M,AM}} & E_{AM}			
			
			
		%\end{tikzcd}
		
		\caption{ تولید امضا}
		\label{fig:sig_generation}
		
	\end{center}
\end{figure}
% ==============================================================================================

% ==============================================================================================
% figure !! for demonstrate Confirmation protocol
\begin{figure}[H] 
	\begin{center}
		
		\begin{tikzcd}[row sep=scriptsize, column sep=scriptsize]
			& E_A  \arrow[rr ,dashed, "\phi_{A,AC}" description] 
			\arrow[dd , dashed , "\phi_{A,AM}" description] 
			& & E_{AC} \arrow[dd , dashed , "\phi_{AC,AMC}" description] \\
			E \arrow[ur, dashed , "\phi_A" description]
			\arrow[rr, crossing over , dashed , "\phi_C" description]
			\arrow[dd , "\phi_{M}" description]
			& & E_C \arrow[ur , dashed , "\phi_{C,AC}" ]  \\
			& E_{AM} \arrow[from=dl  , dashed ,  "\phi_{M,AM}" description]
			\arrow[rr , dashed , "\phi_{AM,AMC}" description]
			& & E_{AMC} \\
			E_M \arrow[rr , dashed , "\phi_{M,MC}" description]
			& & E_{MC} \arrow[from=uu, crossing over , "\phi_{C,MC}"  description ,near start]
			\arrow[ur , dashed , "\phi_{MC,AMC}" description]\\
		\end{tikzcd}
		
		\caption{پروتکل تایید}
		\label{fig:confirmation}
		
	\end{center}
\end{figure}
% ==============================================================================================

% ==============================================================================================
% figure !! for demonstrate disavowal protocol
\begin{figure}[H] 
	\begin{center}
		
		\begin{tikzcd}[row sep=scriptsize, column sep=scriptsize]
			& E_A  \arrow[rr ,dashed, "\phi_{A,AC}" description] 
				   \arrow[dd , dashed , "\phi_{A,AM}" description] 
			& & E_{AC} \arrow[dd , dashed , "\phi_{AC,AMC}" description] \\
			E \arrow[ur, dashed , "\phi_A" description]
			  \arrow[rr, crossing over , dashed , "\phi_C" description]
			  \arrow[dd , "\phi_{M}" description]
			& & E_C \arrow[ur , dashed , "\phi_{C,AC}" ]  \\
			& E_{AM} \arrow[from=dl  , dashed ,  "\phi_{M,AM}" description]
				\arrow[rr , dashed , "\phi_{AM,AMC}" description]
		    & & E_{AMC} \\
			E_M \arrow[rr , dashed , "\phi_{M,MC}" description]
			& & E_{MC} \arrow[from=uu, crossing over , "\phi_{C,MC}"  description ,near start]
				\arrow[ur , dashed , "\phi_{MC,AMC}" description]\\
			\end{tikzcd}
		
		\caption{پروتکل انکار}
		\label{fig:disavowal}
		
	\end{center}
\end{figure}
% ==============================================================================================

\subsection{اثبات‌های امنیت}\LTRfootnote{Security Proofs}
\subsubsection{پروتکل تایید}\LTRfootnote{Confirmation Protocol}
\subsubsection{پروتکل انکار}\LTRfootnote{Disavowal Protocol}





% ======================================================================
% Undeniable Blind Signature
% ======================================================================
\newpage
\section{امضای کور غیرقابل انکار}\label{undeniable_blind_sig}
\LTRfootnote{Undeniable Blind Signature}

طرح امضای کور پروتکلی است که طی آن درخواست‌کننده بدون افشای محتوای سند از امضاکننده در خواست می‌کند تا سند را امضا کند.در سال ۱۹۸۲ اولین بار چام طرح امضای کور رامعرفی کرد.
\cite{chaum@blind}
این طرح براساس مسئله 
$RSA$
بنا شده است.
\cite{rivest@rsa}
از آنجا که اکثر طرح‌های امضای کور و تغییرات آن براساس سختی مسائل متفاوتی از جمله مسئله لگاریتم گسسته
\LTRfootnote{Discrete Logarithm Problem (DLP)}
 ، مسائل زوجیت‌مبنا 
\LTRfootnote{pairing-based problems}
  و مسائل مشکبه‌مبنا
\LTRfootnote{lattice-based problems}
   ارائه شده است 
\cite{discrete@blind, lattice@blind, pairing@blind}
، ولی تمام این طرح‌ها یک مشکل اساسی دارند و مشکل این است که در برابر متخاصم کوانتومی ایمن نمی‌باشند. امضاهای کور معرفی شده توسط چام 
\cite{chaum@blind}
، کامنیش  
\cite{discrete@blind}
و ژانگ‌و‌کیم 
\cite{pairing@blind}
به دلیل الگوریتم شور 
\RTLfootnote{در زمان چندجمله‌ای مسائل لگاریتم گسسته و تجزیه‌اعداد را در کامپیوترهای کوانتومی حل می‌کند}
 در برابر حملات کوانتومی ایمن نیستند.
چنان‌که در  
\cite{shamir@quantum}
نشان داده شده است ، امضای کور مشبکه‌مبنای معرفی شده توسط روکرت  
\cite{lattice@blind}
که از مدل فیات‌شمیر 
\cite{fiat@prove}
استفاده می‌کند در برابر مدل اوراکل تصادفی کوانتومی ایمن 
\LTRfootnote{quantum random oracle model}
نمی‌باشد.

امضای کور هر دو ویژگی ناشناس‌بودن
\LTRfootnote{anonymity}
 و احرازهویت 
\LTRfootnote{authentication}
 را در خود دارد.
\cite{untraceable, untraceability}
در‌نتیجه این طرح در بسیاری از پروتکل‌های حفظ حریم‌خصوصی 
\LTRfootnote{privacy-preserving}
ازجمله پول‌الکترونکی 
\LTRfootnote{e-cash}
و رای‌گیری‌الکترونیکی
\LTRfootnote{e-voting}
استفاده می‌شود.
\cite{e_vote@mobile, e_vot@net }
چنان‌چه در ابتدا گفته‌شد امضاکننده هیچ کنترلی بر محتوای سندی که قرار است امضا شود را ندارد ، علاوه‌بر‌این امضاکننده هیچ کنترلی در نحوه استفاده از امضا را هم ندارد. با این اوصاف احساس می‌شود اعطای درجه‌ای از کنترل به امضاکننده نیاز است. یک از راه‌های ممکن آن است که امضاکننده و درخواست کننده(امضا) روی بخشی از محتوای سند توافق کنند. این راه توسط تکنیکی که آبه و فوجیساکی در 
\cite{date@blind}
ارائه کرده‌اند قابل دستیابی می‌باشد.

راه دیگر آن است که این اختیار به امضاکننده داده شود تا تصمیم بگیرد چه‌کسی مجاز به تایید امضا می‌باشد.این روش ؟؟؟؟.
طرح امضای غیرقابل‌انکار معرفی‌شده توسط چام و ون‌آنترپن 
\cite{undeniable_chaum}
دقیقا مطالب بالا
\RTLfootnote{در یک طرح امضای غیرقابل‌انکار، امضاکننده تصمیم می‌گیرد تا چه کسی امضا را تایید کند}
 را دربرمی‌گیرد. 
 
بنابراین مطلوب است طرحی داشته باشیم که ناشناس‌بودن و تاییدسازی‌کنترل‌شده را درخود داشته باشد که ویژگی‌های هر دو طرح امضای کور و امضای غیرقابل‌انکار را برآورده کند.
% چنین طرحی می تواند طراحی شود اما مشخص نیست.
در سال ۱۹۹۶ ، ساکوری و یامانه 
\cite{1st_blind_undeniable_sig}
یک طرح امضای کور غیرقابل‌انکار را براساس مساله لگاریتم گسسته ارائه دادند. چنان‌که در 
\cite{undeniable_chaum}
گفته‌شده‌است با این تکنیک می‌توان یک طرح امضای کور غیرقابل‌انکار بر اساس مسئله آراس‌آ 
\LTRfootnote{RSA}
طراحی کرد. ذکر این نکته لازم است که تمام این طرح‌ها در برابر حملات کوانتموی ایمن نیستند.

در این پایان‌نامه در نظر داریم یک طرح امضای کور غیرقابل‌انکار مقاوم کوانتومی بر اساس سختی مسائل همسانی روی خم‌های بیضوی سوپرسینگولار ارائه کنیم.


سوخارو و همکارانش در 
\cite{soukharev}
پیشنهادی درباره‌ی ساخت یک طرح امضا با تاییدکننده معین‌شده براساس سختی مسائل همسانی که مقاوم کوانتومی نیز می‌باشد ارائه کرده است.آنها همچنین یک ساخت عمومی از طرح رمزگذاری تایید‌اعتبار کلید نامتقارن ؟؟؟ را نشان داده‌اند.جائو و سوخارو در
\cite{undeniable}
یک طرح امضای غیرقابل‌انکار همسانی‌مبنا ارائه کرده‌اند.در این پایان‌نامه قصد داریم طرح جائو‌ و سوخارو را به یک طرح امضای کور غیرقابل‌انکار توسعه دهیم.

\subsection{تعریف استاندارد}\label{blind_def}\LTRfootnote{Formal Definition}

انتظار می‌رود طرح امضای کور غیرقابل‌انکار
$(UBSS)$\LTRfootnote{Undeniable Blind Signature Scheme }
، ویژگی‌های طرح امضای غیرقابل‌انکار و طرح امضای کور را همزمان داشته باشد.در نتیجه این طرح باید ویژگی‌های ناخوانابودن محتوای پیام‌اولیه(قبل از امضا)
\LTRfootnote{anonoymity of the message origination}
 و تاییدسازی کنترل شده 
\LTRfootnote{controlled verification}
 را دارا باشد.

\textbf{تعریف۱.}\label{definition_ubss}
طرح امضای کور غیرقابل‌انکار ، یک طرح امضای تعاملاتی است که‌بوسیله چندتایی زیر معرفی می‌شود:

$$ \mathcal{UBSS} = \big( KeyGen , Blind , Sign , Unblind , Check , \mathcal{CON} , \mathcal{DIS} \big) $$

\begin{enumerate}
	\item 
الگوریتم تولید کلید تصادفی 
$KeyGen$
، پارامتر امنیتی
$1^\lambda$
را به عنوان ورودی گرفته و زوج کلیدهای
$(vk,sk)$
را که به عنوان کلیدتاییدساز و کلید‌مخفی نامیده می‌شوند، به عنوان خروجی تولید می‌کند. شکل شماتیک این الگوریتم به‌صورت زیر می‌باشد:
$$ (vk,sk) \longleftarrow KeyGen(1^{\lambda}) $$

\item 
الگوریتم کورسازی تصادفی
$Blind$
، پیام 
$m$
را به عنوان ورودی گرفته و خروجی آن کورشده‌ی پیام، یعنی
$m'$
می‌باشد. شکل شماتیک این الگوریتم به شکل زیر می‌باشد که 
$r$
کاملا به صورت تصادفی توسط الگوریتم ساخته
می‌شود:
$$ m' \longleftarrow {_{r}Blind(m)} $$

\item
الگوریتم امضای قطعی یا تصادفی 
$Sign$
، کلید مخفی
$sk$
و پیام
$m$
را به عنوان ورودی گرفته و امضای
$\sigma$
را به عنوان خروجی تولید می‌کند. این الگوریتم را می‌توان به صورت زیر نشان داد:
$$ \sigma \longleftarrow Sign_{sk}(m) $$

\item 
الگوریتم شفاف‌ساز قطعی 
$Unblind$
،امضای کور
$\sigma'$
و عددتصادفی 
$r$
(انتخاب شده توسط الگوریتم کورسازی) را به عنوان ورودی گرفته و امضای شفاف
$\sigma$
را به عنوان خروجی تولید می‌کند. این الگوریتم را می‌توان به شکل زیر نمایش داد:
$$ \sigma := Unblind_r(\sigma') $$

\item 
الگوریتم قطعی بررسی 
$Check$
، پیام 
$m$
، امضای شفاف
$\sigma$
و زوج کلیدهای
$(vk,sk)$
را به عنوان ورودی گرفته و بیت 
$b$
را به عنوان خروجی تولید می‌کند.
$b=1$
به معنای آن است که امضا متعلق به پیام می‌باشد و 
$b=0$
نیز به این معناست که امضا غیرمعتبر می‌باشد. این الگوریتم به‌صورت زیر قابل نمایش است:
$$ b := Check_{(vk,sk)}(m,\sigma) $$

\item
پروتکل تایید
$\pi_{con}$
توسط امضاکننده اجرا می‌شود تا تاییدکننده اطمینان یابد که امضا معتبر است.

\item 
پروتکل انکار
$\pi_{dis}$
نیز توسط امضاکننده اجرا می‌شود و تاییدکننده متقاعد می‌شود که امضا نامعتبر است.
\end{enumerate}

برای هر زوج کلید 
$(vk,sk)$
که توسط الگوریتم 
$KeyGen(1^{\lambda})$
تولید می‌شود و همچنین هر
$m$
از میان فضای پیام و هر عددتصادفی
$r$
که توسط الگوریتم 
$Blind$
تولید شده است، باید تساوی زیر برقرار باشد:
$$ Check_{(vk,sk)}(m,Unblind_r(Sign_{sk}(_{r}Blind(m)))) = 1 $$


علاوه‌براین، اگر الگوریتم امضا قطعی باشد آنگاه می‌توان فرض کرد اثر مراحل الگوریتم‌های کورسازی-امضا-شفافیت روی پیام دقیقا مشابه اجرای مستقیم الگوریتم امضا روی پیام می‌باشد. برای درک این مطلب آن را به صورت زیر نمایش می‌دهیم:
$$ Unblind_r(Sign_{sk}(_{r}Blind(m))) = Sign_{sk}(m) $$

\newpage
\subsection{کارکرد UBSS}\label{working_ubss}
\LTRfootnote{Workinf of UBSS}

برای درک بهتر نقش الگوریتم‌های گفته شده در بخش قبلی، پروتکل را به صورت کامل اجرا می‌کنیم.

در ابتدا امضاکننده یک پارامتر امنیتی 
$\lambda$
را انتخاب و الگوریتم 
$KeyGen(1^\lambda)$
را برای به دست آوردن زوج کلید
$(vk,sk)$
اجرا می‌کند.کلید امضای
$sk$
به صورت مخفی پیش امضاکننده حفظ می‌شود و کلید تاییدساز
$vk$
توسط امضاکننده منتشر می‌شود.
$m$
پیامی است که درخواست‌کننده خواهان امضای آن به صورت ناخوانا است؟؟. به این منظور ، درخواست‌کننده ابتدا 
$m$\RTLfootnote{پیام خوانا}
 را با اجرای الگوریتم 
$Blind(m)$
به 
$m'$\RTLfootnote{پیام ناخوانا}
تبدیل می‌کند.
\RTLfootnote{
در زمان اجرای الگوریتم ، یک انتخاب تصادفی
$r$
توسط خود الگوریتم تولید می‌شود.
}
درادامه درخواست‌کننده 
$m'$
را به همراه شناسه هویتی خود
$Id_R$
، ارسال می‌کند. امضاکننده ابتدا شناسه درخواست‌کننده را تایید (
\ref{remark_1}
) و سپس الگوریتم 
$Sign_{sk}$
را روی
$m'$
اجرا می‌کند تا امضای کور
$\sigma'$
به دست آید. دریافت‌کننده پس از دریافت امضای کور از امضاکننده ، توسط الگوریتم
$Unblind$
 و مقدارتصادفی 
$r$
انتخاب شده در مرحله کورسازی، امضا را از حالت کور خارج کرده وسپس زوج پیام اصلی و امضای شفاف
$(m,\sigma)$
پیام رابرای بخش تایید؟؟ ارسال می‌کند.

هربخشی که خواهان تایید امضا باشد، شناسه خود
$Id_V$
را به همراه زوج پیام و امضا 
$(m,\sigma)$
برای امضاکننده ارسال می‌کند. امضاکننده در ابتدا شناسه تاییدکننده را بررسی می‌کند(
\ref{remark_1}
) آنگاه اگر
$Id_V$
یک شناسه معتبر در میان تاییدکنندگان احراز شده(مجاز) نباشد، امضاکننده از ادامه ارتباط خودداری می‌کند. در غیراینصورت الگوریتم بررسی 
$Check$
را اجرا می‌کند. اگر خروجی این الگوریتم معتبر باشد آنگاه پروتکل تایید
$\mathcal{CON}$
توسط امضاکننده آغاز می‌شود؛ درغیراینصورت پروتکل انکار
$\mathcal{DIS}$
اجرا می‌شود(شکل 
\ref{fig:ubss}
 تمام مفاهیم طرح 
$UBSS$
را نشان می‌دهد).

% ==============================================================================================
% figure for demonstrate full of information in UBSS
\begin{figure}[H] 
	\begin{center}
		
		\begin{tikzcd}[row sep=5em,column sep=5em]
			& \color{red} \fbox{امضاکننده} \arrow[dl,red,"\sigma'" ,red] 
			         \arrow[dr,red,leftrightsquigarrow , "\mathcal{CON} / \mathcal{DIS}" ,red] & \\
			\color{blue} \fbox{درخواست‌کننده} \arrow[rr,blue, "{(m,\sigma)}",blue ] 
						\arrow[ur ,blue, shift left , "Id_R ||m' ",blue] &
			& \color{green} \fbox{تاییدکننده} \arrow[ul ,green , shift left , "Id_V|| {(m,\sigma)}" ,green]
		\end{tikzcd}
		
		\caption{ اطلاعات کامل طرح امضای کور غیرقابل‌انکار}
		\label{fig:ubss}
		
	\end{center}
\end{figure}
% ==============================================================================================

\textbf{توجه۱.}\label{remark_1}
در این پایان‌نامه عمدا چگونگی احراز هویت  بین درخواست‌کننده و تاییدکننده با امضاکننده را مشخص نمی‌کنیم. این امر مستلزم آشنایی با احراهویت‌ متقابل می‌باشد. این طرح در
\cite{boneh@secure , goorden@secure}
به‌صورت کامل آورده شده است که در مقابل حملات کوانتومی نیز ایمن می‌باشند.

\subsection{ویژگی‌ها}\label{ubss_properties}\LTRfootnote{Properties}






































% ======================================================================
% Refrences
% ======================================================================
\newpage
\setLTRbibitems
% \resetlatinfont
\bibliographystyle{plain}
\bibliography{ref.bib}
	
\end{document}


\begin{itemize}
	
	\item[] {}
	\begin{flalign}
	i=0 \Rightarrow \quad 
	E_1 = E_0 / \langle \ell^{4}R_0 \rangle , \quad 
	\phi_0 : E_0 \rightarrow E_1 , \quad 
	R_1 = \phi_0(R_0)
	\end{flalign}
	
	
	\item[] {}
	\begin{flalign}
	i=1 \Rightarrow \quad 
	E_2 = E_1 / \langle \ell^{3}R_1 \rangle , \quad 
	\phi_1 : E_1 \rightarrow E_2 , \quad 
	R_2 = \phi_1(R_1)
	R_2 = \phi_1(\phi_0(R_0))
	\end{flalign}
	
	
	
	
\end{itemize}



% triangle diagram
\begin{tikzcd}[row sep=3em,column sep=3em]
	x_1(k+1) \arrow[d,swap,"x_1(k)"] & \\
	x_2(k+1) \arrow[d,swap,"x_2(k)"] &
	x_4(k+1)
	\arrow[lu,swap,"x_1(k)"]
	\arrow[l,swap,"x_2(k)"]
	\arrow[l,loop right,"x_4(k)"]
	\arrow[dl,shift right]
	\\
	x_3(k+1) \arrow[ru,shift right,swap,"x_3(k)"]
\end{tikzcd}