ds_on_zkp.tex

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

 هر طرح امضای دیجیتالی شامل سه الگوریتم تولیدکلید
\LTRfootnote{Key Generation Algorithm}
برای ساخت کلیدخصوصی و کلیدعمومی امضاکننده، الگوریتم امضا
\LTRfootnote{Signature Algorithm}
برای امضای پیام‌های دریافتی و همچنین الگوریتم تایید‌امضا
\LTRfootnote{Verification Signature Algorithm}
برای بررسی اعتبار امضا، می‌باشد که این الگوریتم‌ها در طرح ما به صورت زیر تعریف می‌‌شوند :
\begin{itemize}
\item{
$\bf KeyGen(\lambda)$
}
		
این الگوریتم یک پارامتر امنیتی 
$\lambda$
(تا امنیت کامل طرح برآورده شود)به عنوان ورودی گرفته و یک زوج کلید 
$(pk,sk)$
را به عنوان زوج کلیدعمومی وکلیدخصوصی تولید می‌کند وبرای تولید امضا و تایید آن مورداستفاده قرار می‌گیرد.این الگوریتم توسط امضاکننده اجرا می‌شود و عمومی نیست.
\item {
$\bf Sign(sk,m)$	
}

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

این الگوریتم با داشتن کلید عمومی امضاکننده 
$\bf pk $
تایید می کند که آیا امضای دریافتی 
$\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}	
بنابراین از طریق یک اثبات دانش صفر غیرتعاملی هویت
\LTRfootnote{NIZK proof of identity} 
$ (P,V)$
، یک طرح امضای دیجیتال 
$ \mathcal{DS}$
به دست می‌آید که شامل تعاریف زیر می‌باشد:
\newline
\newline
$$ \mathcal{DS} = (KeyGen,Sign,Verify)$$
که دراین حالت الگوریتمِ امضا با الگوریتم اثبات‌کننده پروتکل زیگما شبیه‌سازی می‌شود:
$$ Sign(sk,m) = P((pk,m),sk)$$
و الگوریتم تاییدِامضا با الگوریتم تاییدکننده پروتکل زیگما شبیه‌سازی می‌شود:
$$ Verify(pk,m,\sigma = V((pk,m,\sigma)))$$
\\
\begin{theorem}
	
	اگر 
	$(P,V)$
	یک اثبات هویت 
	$NIZK$ \LTRfootnote{Non-Interactive Zero-Knowledge}
	با ویژگی‌های شبیه ‌سازی-صداقت و استخراج-آنلاین باشد آنگاه طرح امضای
	$\mathcal{DS}$
	ذکرشده در بالا یک امضای دیجیتال
	SUF-CMA
	در مدل ارواکل تصادفی کوانتومی خواهد بود.
	
\end{theorem}

\begin{proof}
	content...
\end{proof}

% ---------------------------------------------------------------------------------------------
%        اثبات خوانده شده و به صورت کامل ذکر شود
% ---------------------------------------------------------------------------------------------

\newpage
\section{امضای دیجیتال همسانی مبنا}\label{isogeny_ds}
حال که در بخش قبلی توانستیم از یک طرح اثبات‌دانش‌صفر‌هویت‌غیرقابل‌انکار یک طرح امضای دیجیتال  غیرقابل‌جعل معرفی کنیم، در این بخش خواهان پیاده‌سازی این امضا بر اساس مسئله‌ی همسانی‌ها در خم‌های بیضوی می‌باشیم.
\\
برای معرفی طرح‌امضای‌دیجیتال برا اساس همسانی‌ها لازم است الگوریتم‌هایی که در هر طرح امضایی وجود دارد را به زبان همسانی‌ها بازتعریف کنیم. بنابریان در ادامه به معرفی الگوریتم‌های تولید‌کلید،امضا و تاییدسازی می‌پردازیم. اما از آنجا که طرح ما در یک فضای‌خاصی تعریف می‌شود لازم است که ابتدا به تعریف محیطی که امضا درآن تعریف می‌شود بپردازیم پس ابتدا به عنوان تعریف محیط طرح خود، پارامترهای عمومی را تعریف می‌کنیم:
\\ 
\begin{itemize}
	\item[]{\bf پارامترهای عمومی }\LTRfootnote{Public Parameters}
	
	پارامترهای عمومی ما همان پارامترهای عمومی معرفی شده در پروتکل زیگما می‌باشد:
	\begin{itemize}
		\item {
		 عدد اول به فرم 
		$p = \ell_A^{e_A} \ell_B^{e_B} \cdot f \pm 1$
	}

		\item {
		 خم بیضوی سوپرسینگولار 
		$E$
		از مرتبه‌ی
		$(\ell_A^{e_A} \ell_B^{e_B})^2$
		در میدان 
		$\mathbb{F}_{p^2}$
	}

		\item {
		زوج نقاط 
		$(P_B,Q_B)$
		مولد زیرگروه تابی 
		$E[\ell_B^{e_B} ]$
	}
	\end{itemize}	 
	
	\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
\newline
\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) $$

الگوریتم های ۳و۴و۵ به طور صریح الگوریتم‌های تولیدکلید ، امضا و تاییدسازی را بر اساس مسئله همسانی  بیان می‌کنند.
\subsection{الگوریتم تولیدکلید}\label{algorithm_keygen}
همان‌طور که در الگوریتم ۳ مشاهده می‌شود
\begin{enumerate}
	\item {
	ابتدا یک نقطه‌تصادفی 
	$S$
	ازمرتبه‌ی
	$\ell_A^{e_A}$
	انتخاب می‌کنیم.
	}

	\item {
	در قدم بعدی همسانی
	$\phi : E \rightarrow E/ \langle S \rangle$
	را از طریق فرمول ولو و با هسته
	$\langle S \rangle$
	به دست می‌آوریم
	}

	\item {
	حال خم 
	$E/ \langle S \rangle$
	و تصویر نقاط 
	$\phi{P_B}$
	و
	$\phi{Q_B}$
	را به عنوان کلیدعمومی
	$pk$
	در نظر می‌گیریم
	}

	\item {
	و همچنین کلیدخصوصی را نقطه تصادفی
	$S$
	درنظر می‌گیریم
	}

	\item {
	در پایان خروجی این الگوریتم زوج کلیدعمومی و خصوصی 
	$(pk,sk)$
	می‌باشد
	}
\end{enumerate}

\subsection{الگوریتم امضا}\label{algorithm_sign}
الگوریتم امضا با ورودی پیام
$m$
و کلیدخصوصی 
$sk$
در طرح ما در یک مرحله انجام نمی‌شود و لازم است که برای تولید خروجی الگوریتم عملیاتی بارها انجام شود بنابراین در این الگوریتم روال زیر طی خواهد شد :
\begin{enumerate}
	\item {
	همان‌طور که قبلا توضیح دادیم، الگوریتم امضای ما براساس الگوریتم اثبات‌کننده در ساخت آنره به دست می‌آید بنابراین برای امنیت کامل لازم است که الگوریتم به تعداد مشخصی تکرار شود و طبق آنچه قبلا ذکر شد لازم است که ایت تکرار به اندازه
	$2\lambda$
	باشد، بنابراین از یک حلقه تکرار استفاده می‌کنیم
	}

	\item {
	 عدد  
	$R$
	به صورت کاملا تصادفی از مرتبه‌ی
	$\ell_B^{e_B}$
	 انتخاب می‌شود
	}

	\item {
	درادامه همسانی
	$\psi$
	از طریق فرمول ولو و با زیرگروه
	$\langle R \rangle$
	به صورت
	$\psi : E \rightarrow E/ \langle R \rangle $
	محاسبه می‌شود
	}

	\item {
	سپس دو همسانی
	 $\phi'$
	 و
	 $\psi '$
	 مستقلا توسط زیرگروه‌های مشخص زیر توسط فرمول ولو محاسبه می‌شود :
	 $$ \phi' : E/ \langle R \rangle \rightarrow E/ \langle R,S \rangle $$
	 $$ \psi' :  E/ \langle S \rangle  \rightarrow E/ \langle R,S \rangle $$
	}

	\item {
	خم‌های به دست آمده از دوهمسانی 
	$\phi'$
	و
	 $\psi '$
	 را به صورت زیر نامگذاری می‌کنیم :
	 $$ (E_1,E_2) \leftarrow (E/ \langle R \rangle ,  E/ \langle R,S \rangle) $$
	}

	\item {
	همان‌طور که در ساخت آنره(برگرفته از پروتکل زیگما) مشاهده کردیم لازم است اثبات‌کننده (در اینجا امضاکننده) تعهدی را برای اثبات ارائه کند، بنابراین تعهد مطرح شده در الگوریتم امضا به صورت زیر خواهد بود :
	$$ com_i \leftarrow (E_1,E_2) $$
	}

	\item {
	برای به چالش کشیدن امضاکننده براساس تعهدی که ارائه کرده است لازم است چالشی توسط ساخت آنره تولید شود و چون دامنه‌ی چالش‌ها محدود به دو انتخاب است بنابراین چالش ما به صورت تصادفی از بین دو مقدار صفرو یک انتخاب می‌شود :
	$$ ch_{i,0} {\leftarrow}_R ~ \{0,1\} $$
	}

	\item {
	در این مرحله بدون درنظر گرفتن چالش انتخابی مرحله قبل، پاسخ‌های را براساس زیر تولید می‌کنیم. دلیل این امر این است که پاسخ‌های امضاکننده در هرمرحله ثابت ولی نسبت به چالش ارائه شده جایگشتی در ارائه آنها در مرحله‌ی بعدی صورت می‌گیرد. با این اوصاف پاسخ‌های الگوریتم به صورت زیر تعیین می‌شوند:
	$$ (resp_{i,0} , resp_{i,1}) \leftarrow ( (R , \phi(R)) , \psi(S)) $$
	}

	\item {
	در این مرحله مشخص می‌شود براساس چالش دریافتی پاسخ چه باشد. اگر بیت چالش صفر باشد پاسخ همان ترتیب بالا خواهد بود وگرنه جای پاسخ‌ها با یکدیگر عوض شده و سپس ارسال می‌شود
	}

	\item {
	در این مرحله به منظور اطمینان از ثبت درست مراحل بالا طبق الگوریتم امضا لازم است که از پاسخ‌ها با کمک تابع
	$G$
	هش گرفته شود بنابراین :
	$$ h_{i,j} \leftarrow G(resp_{i,j}) $$
	}

	\item {
	همان‌طور که در الگوریتم اثبات‌کننده مطرح شد لازم است که چالش توسط خود الگوریتم به صورت تصادفی و بدون هرگونه دخالت دانش قبلی تولید شود بنابراین 
	$2\lambda$
	چالش ممکن توسط کد زیر تولید می‌شود:
	$$ 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$
    تابع هش می‌باشد
	}

	\item{
	خروجی الگوریتم، امضای امضاکننده (اثبات اثبات‌کننده) می‌باشد که به صورت زیر تولید می‌شود:
	$$ \sigma \leftarrow ( (com_i)_i , (ch_{i,j})_{i,j} , (h_{i,j})_{i,j} , (resp_{i,J_i})_i ) $$
و برای تاکیید بیشتر لازم به یادآوری است که پاسخ‌های
	$resp$
تولید شده در مراحل قبلی کاملا به صورت تصادفی و بدون هیچ ترتیب خاصی و وابسته به چالش‌های
	$J_i$
	در اثبات جاسازی می‌شوند
	}
\end{enumerate}

\subsection{الگوریتم تایید امضا}\label{algorithm_verify_signature}
 با داشتن کلیدعمومی
$pk$
،پیام
$m$
و امضای دریافتی 
$\sigma$
از طرف امضاکننده، هر شخصی می‌تواند بدون تعامل با امضاکننده به تایید امضا بپردازد. تاییدکننده باید طبق الگوریتم تایید مراحل زیر را انجام دهد :
\begin{enumerate}
	\item { 
  از آنجا که طرح امضای ما براساس ساخت آنره می‌باشد ودر این پروتکل تعاملی بین 
  اثبات‌کننده(امضاکننده) و تاییدکننده برقرار نیست باید راهی وجود داشته باشد تا تاییدکننده نیز به چالش‌هایی که اثبات‌کننده نسبت به آن‌ها پاسخ داده است اشراف داشته باشد بنابراین همان‌طور که در الگوریتم امضا مشاهده شد، چالش‌ها از قسمت‌هایی به‌دست می‌آید که آن قسمت‌ها توسط امضاکننده منتشر و عمومی می‌شود بنابراین تاییدکننده نیز می‌تواند خود مستقلا به تولید چالش‌ها بپردازد. این عمل نشان می‌دهد که چالش‌ها واقعا به صورت تصادفی خلق شده‌اند.
  بنابراین در اولین قدم اجرای الگوریتم، چالش‌ها مستقلا بازتولید می‌شوند تا در قدم‌های بعدی الگوریتم مورد استفاده قرار گیرد:
	$$ 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} )
	$$
	}

	\item {
	از آنجا که برای تولید امضا
	$\pi$
	، به 
	$2\lambda$
	راند نیاز بود بنابراین برای تایید آن نیز به 
	$2\lambda$
	مرحله نیاز است که برای این امر از حلقه تکرار استفاده می‌کنیم
	}

	\item {
	چون تابع هش 
	$G$
	عمومی است پس می‌توان بررسی کرد که آیا هش پاسخ‌ها 
	$h_{i,j} $
	به عنوان بخشی از اثبات 
	$\pi$
	از پاسخ‌های 
	$resp_{i,j}$
	الگوریتم امضا به‌دست آمده است یا خیر. درنتیجه این بررسی در الگوریتم تایید مستقلا انجام می‌شود:
	$$ \textbf{check} ~ h_{i,J_i} = G(resp_{i,J_i})$$
	}

	\item {
	از آنجا که برای تولیدامضا 
	$2\lambda$
	مرحله نیاز بود برای تاییدامضا نیز باید این تعداد مرحله انجام شود. همچنین می‌دانیم در طرح خود چالش یا صفر است یا یک، درنتیجه اگر چالش صفر باشد عملیات خاصی انجام می‌شود و اگر چالش یک باشد عملیاتی متناظر با آن انجام خواهد شد.
	}
	\item {
	اگر چالش  صفر انتخاب شده باشد آنگاه عملیات زیر به ترتیب انجام می‌شود:
	\begin{itemize}
		\item {
		پاسخ
		$resp_{i,J_i}$
		به عنوان مقدار
		$(R,\phi(R))$
		انتخاب می‌شود ؟؟؟؟؟؟؟
		}
	
		\item {
		در قدم بعدی بررسی می‌شود که آیا
		$(R,\phi(R))$
		از مرتبه‌ی
		$\ell_B^{e_B}$
		می‌باشد یا خیر
		}
		\item {
		با داشتن دو خم 
		$E$
		و
		$E_1$
		و همچنین فرمول ولو بررسی می‌شود که آیا 
		$R$
		تولیدکننده‌ی هسته‌ی همسانی
		$\psi : E \rightarrow E_1$
		می‌باشد یا خیر
		}
	
		\item {
			درآخرین قسمت این مرحله بررسی می‌شود که آیا
		$\phi(R)$
		تولیدکننده هسته‌ی همسانی
		${\psi}' : E / \langle S \rangle \rightarrow E_2$
		می‌باشد یا خیر. این بررسی نیز با داشتن دو خم 
		$E / \langle S \rangle$
		و
		$E_2$
		و همچنین فرمول ولو و  الگوریتم ؟؟؟ قابل انجام می‌باشد
		
		}
	\end{itemize}		
	}

	\item {
	اگر چالش حاوی مقدار یک باشد آنگاه مراحل زیر انجام می‌شود:
	\begin{itemize}
		\item {
		پاسخ 
		$resp_{i,J_i}$
		به عنوان 
		$\psi(S)$
		درنظرگرفته می‌شود؟؟؟
		}
	
		\item {
		بررسی می‌شود که آیا
		$\psi(S)$
		از مرتبه‌ی
		$\ell_A^{e_A}$
		می‌باشد یاخیر
		}
	
		\item {
		همچنینی بررسی می‌شود که آیا 
		$\psi(S)$
		
		تولیدکننده‌ی هسته‌ی همسانی
		${\phi}' :‌E_1 \rightarrow E_2$
		می‌باشد یا خیر
		}
	\end{itemize}
	}

	\item {
	اگر در تمام بررسی‌های بالا پاسخ بلی باشد آنگاه الگوریتم یک رو به عنوان خروجی تولید می‌کند به این معنی که امضا پذیرفته شده است.
	}
\end{enumerate}
\end{itemize}