sigma_protocol.tex

\section{ پروتکل‌های اثبات }\label{proof_protocol}
\subsection{ پروتکل زیگما}\LTRfootnote{sigma protocol}\label{sigma_protocol}

در یک سیستم اثبات ، اثبات کننده 
$\mathcal{P}$
خواهان آن است تا اظهار 
$x$
را برای تاییدکننده 
$\mathcal{V}$
اثبات کند با این ویژگی که برای متقاعد کردن تاییدکننده برای اظهار
$x$
، شاهد 
$w$
را برای ادعای خود در اختیار دارد. در هر پروتکل اثبات یک رابطه باینری به نام 
$R$
وجود دارد، به این معنی که اگر اظهار
\LTRfootnote{Statement}
$x$
ادعا ‌شود آنگاه باید شاهدی
\LTRfootnote{Witness}
به نام 
$w$
برای آن موجود باشد که در این صورت آن را به صورت 
$(x,w) \in R $
نمایش خواهیم داد. به طور مثال در امضای دیجیتال اگر کلید عمومی 
$v$
برای امضای
$S$
ادعا شود آنگاه کلیدخصوصی
$s$
به عنوان شاهدی برای کلیدعمومی می‌باشد که رابطه‌ی این دو به صورت زیر تعریف می‌شود:
$$(v,s) \in R ~ ; \quad R :\{ ~ ‌sv \equiv 1  \mod ( (p-1)(q-1) )  \} $$
به عبارت دیگر اگر کلید عمومی (ادعا) منتشر شده با کلیدخصوصی(شاهد)  امضاکننده واقعا رابطه‌ای داشته باشند آنگاه برای هر چالشی که توسط تاییدکننده (در اینجا چالش ، پیام 
$m$
می‌باشد) برای امضاکننده (اثبات‌کننده)ارسال می‌شود، باید بعداز دریافت امضای پیام بتوانیم با کلیدعمومی به پیام ارسال شده(
$m$
) برسیم.
بنابراین زمانی ادعای امضاکننده مبنی بر داشتن شاهد یا کلیدخصوصی محرز می‌شود که بتوانیم با کلیدعمومی منتشر شده توسط وی به پیام برسیم ،در غیراینصورت ادعا موردقبول واقع نمی‌شود و درنتیجه آشکار می‌شود که رابطه‌ای بین کلیدها برقرار نبوده و مهمتر آنکه امضا متعلق به امضاکننده نیست.
\\
\\
\subsubsection{ تعریف }\label{sigma_protocol_definition}

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

\begin{itemize}
\item[]{\bf تمامیت }\LTRfootnote{Completeness}:
	
اگر اثبات کننده
$\mathcal{P}$
واقعا شاهد 
$w$
را برای اظهار
$x$
بداند آنگاه طبق این پروتکل ، تاییدکننده 
$\mathcal{V}$
ادعای اثبات کننده را می‌پذیرد. به‌عبارت دیگر احتمال آنکه اثبات‌کننده، شاهد
$w$
را بداند ولی تاییدکننده، متقاعد نشود برابر با صفردرصد می‌باشد.که به‌صورت زیر نمایش می‌دهیم:
$$ Pr(P(x,y) \leftrightarrow V(x) \rightarrow 1) = 1 $$
	
\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 $
را محاسبه کند.
\\
این ویژگی تضمین می‌کند که تاییدکننده حتما با یک اثبات‌کننده صادق روبرو است که دانش موردنظر و شاهد را می‌داند زیرا درغیراینصورت الگوریتم هیچ شاهدی را استخراج نمی‌کند که در این صورت تاییدکننده پی می‌برد که تاییدکننده، متقلب است و به دانش ادعایی دسترسی ندارد.
\\
\remark
توجه به این نکته لازم است که در اینجا برای یک اظهار
$com$
دو چالش 
$ch$
و
$ch'$
همزمان برای آن ارسال شده و جواب‌های
$resp$
و
${resp~}'$
دریافت می‌شود که در هر پروتکل اثبات همچون زیگما هیچ‌گاه این اتفاق مجاز به انجام نیست و برای هر تعهد
$com$
باید  فقط یک چالش مورد سوال قرار گیرد. اما در اینجا فرض شده است اگر برای هر تعهد بتوانیم دو چالش متفاوت ارسال و دو پاسخ دریافت کنیم آنگاه الگوریتمی موجود هست که باعث افشای شاهد می‌شود.
\\
 همچنین قابل ذکر است که دامنه‌ی چالش‌ها
 $N_{ch}$
 ، حداقل دو یا بیشتر فرض شده است.
	
\item[]{\bf دانش صفر تاییدکننده صادق }\LTRfootnote{Honest-verifier zero-knowledge (HVZK)} :
	
 الگوریتم چندجمله‌ای شبیه ساز 
$S_{\Sigma}$
وجود دارد که یک خروجی شبیه‌سازی شده‌ای به فرم
$(com,ch,resp)$
تولید می‌کند که نسبت به خروجی معتبر دریافت شده توسط تعاملات حقیقی بین اثبات‌کننده و تاییدکننده هیچ  نوع تمایز و فرقی ندارد.
این ویژگی نیز بیانگر آن است که تاییدکننده هیچ اطلاعاتی از دانش موردنظر  اثبات‌کننده دریافت نمی‌کند و تنها متقاعد می‌شود که تاییدکننده به‌راستی دانش را می‌داند. البته در اینجا فرض شده است که تاییدکننده، صادق باشد.
\end{itemize}~
\\
\remark
اگر پروتکل زیگما را به صورت خلاصه‌شده‌ی
$\Sigma = (P,V)$
در نظر بگیریم آنگاه
$P = (P^1,P^2)$
خواهد بود.
\remark
اثبات‌دانش‌صفر‌هویت  همسانی ‌مبنای گفته شده در مثال بالا
\ref{fig:zkp}
 در اصل یک پروتکل زیگما می‌باشد. در بخش ۵ نشان خواهیم داد که تمام ویژگی‌های یک پروتکل زیگما را برآورده می‌کند. 
\\
% =============================================================================================
\subsection{سیستم اثبات غیرتعاملی }\LTRfootnote{Non-interactive Proof System}\label{non-pf}
\\
یک سیستم اثبات غیرتعاملی شامل دو الگوریتم 
\begin{itemize}
	
\item
 اثبات‌کننده 
$P(x,w)$
که یک اثبات
$\pi$
را برای اظهار 
$x$
(که دارای شاهد
$w$
می‌باشد) تولید می‌کند. 

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

ساخت آنره ، پروتکل زیگما 
$(\Sigma)$
را به یک سیستم اثبات غیرتعاملی 
$(P_{OE}, V_{OE})$
تغییر‌شکل می‌دهد بطوریکه اگر پروتکل زیگما
$(\Sigma)$
شامل ویژگی‌های تمامیت ، صداقت ویژه و دانش صفر باشد آنگاه نتیجه یک سیستم اثبات دانش‌صفر  غیرتعاملی با ویژگی  شبیه ‌ساز صداقت با استخراج آنلاین خواهد بود.
% hspace{2mm}
\\
 فرض کنید یک پروتکل زیگما به صورت 
$\Sigma = (P_\Sigma , V_\Sigma)$
که
$P_\Sigma = (P_\Sigma^1 , P_\Sigma^2)$
داشته باشیم که 
$c$
 چالش ممکن متمایز در دامنه‌ی چالش ها 
$(N_{ch})$
داشته باشد و ‌قرار است  پروتکل به تعداد 
$t$
بار(که به پارامتر امنیتی
$\lambda$
بستگی دارد) اجرا شود. و همچنین فرض کنید اوراکل‌های تصادفی کوانتومی
$G$
و
$H$
را نیز در اختیار داریم. 
\\ 
$(P_{OE} , V_{OE})$
یک سیستم اثبات غیرتعاملی براساس پروتکل زیگما می‌باشد که 
$P_{OE}$
به عنوان اثبات‌کننده و 
$V_{OE}$
به عنوان تاییدکننده از طریق الگوریتم های 
\ref{algorithm_prover}
 و 
\ref{algorithm_verifier} 
 به دست می‌آیند.
\\
\\
لازم به ذکر است  در طرح امضای دیجیتال معرفی شده در این پایان نامه، مقادیر فرض شده در پروتکل زیگما  به صورت
$N_{ch} = \{0,1\}$
،
$c = 2$ 
 و
$t = 2\lambda $ 
می‌باشند.
\\
\\
% ==========================================================================================
% algorithm 1&2 
% ==========================================================================================
\subsubsection{الگوریتم اثبات‌کننده}\label{algorithm_prover}
\begin{enumerate}
	\item {
همان‌طور که در خط اول الگوریتم اثبات‌کننده ذکر شده است خواهان آن هستیم که تعداد
$ t\cdot c $
اثبات (از طریق پروتکل زیگما) تولید کنیم. دلیل استفاده از این مقدار به این خاطر است که طبق آنچه قبلا در پروتکل زیگما اشاره کردیم برای امنیت کامل لازم است تا پروتکل زیگما به تعداد
$t$
بار تکرار شود.
 اما مقدار 
$c$
، به این دلیل است که در پروتکل زیگما، تاییدکننده به انتخاب خود یک چالش را از میان چالش‌های مجاز(دامنه‌ی چالش‌ها)	انتخاب می‌کند ولی به دلیل آنکه در ساخت آنره هدف آن است که ارتباط با تاییدکننده حذف شود بنابراین در این سیستم تمام چالش‌ها  شبیه‌سازی می‌شود تا هیچ دانش خاصی در به‌کارگرفتن چالش در هر مرحله صورت نگیرید و اثبات کاملا تصادفی و یکنواخت باشد.
}

\item {
بنابراین برای ایجاد امنیت کامل لازم است تا به تعداد  
$t$
مرتبه رویه اثبات شبیه‌سازی شود که بدین منظور از یک حلقه‌ی تکرار استفاده می‌کنیم. 
}

\item {
در هر بار تکرار حلقه، ادعای 
$x$
 با الگوریتم 
$P^1_{\Sigma}$
 مطرح می‌شود و به عنوان یک تعهد خروجی الگوریتم در متغیر
$com_i$
ذخیره می‌گردد
}

\item {
به منظور شبیه‌سازی تمام حالت‌های ممکن برای ارسال درخواست یک چالش توسط تاییدکننده ، تمام مقادیر دامنه‌ی چالش‌ها( که 
$c$
حالت ممکن برای آن وجود دارد
)  توسط حلقه‌ی تکرار تولید می‌شود
}

\item {
در این مرحله یک چالش به صورت کاملا تصادفی و یکنواخت از دامنه‌ی چالش‌های مجاز انتخاب می‌شود و مقدار انتخاب شده از دامنه‌ی چالش‌ها حذف می‌گردد
}

\item {
براساس چالش دریافتی می‌بایست یک پاسخ از طرف تاییدکننده ارسال شود بنابراین الگوریتم
$P^2_{\Sigma}$
اجرا می‌شود و خروجی در متغیر
$resp_{i,j}$
ذخیره می‌شود
}

\item {
در این مرحله، از پاسخ هر چالش با الگوریتم
$G$
هش گرفته می‌شود و در متغیر 
$h_{i,j}$
ذخیره می‌شود. دلیل این امر آن است که مطمئن باشیم که پاسخ هر چالش بدون تغییر ذخیره شده است.
}\\
 تا پایان این مرحله به تعداد
$t \cdot c $
پاسخ داریم که البته هش شده است و غیرقابل‌تغییر می‌باشند.

\item {
مهمترین قسمت پروتکل آنره در این قسمت از الگوریتم انجام می‌پذیرد. 
از آنجا که با پروتکل آنره خواهان آن هستیم که از یک اثبات دانش‌صفر تعاملی به یک اثبات‌دانش‌صفر غیرتعاملی برسیم بنابراین با استفاده از مجموع تعهد‌ها،چالش‌ها و پاسخ‌های به هر  چالش  که توسط خود اثبات‌کننده در مراحل قبلی الگوریتم شبیه‌سازی شد به تولید چالش‌هایی می‌پردازیم که شبیه به چالش‌هایی باشد که از طرف تاییدکننده دریافت می‌شود با این ویژگی که کاملا تصادفی تولید شوند. در نتیجه برای تولید چالش‌ها از متغیرهای به‌دست آمده از مراحل قبلی الگوریتم با تابع
$H$
هش می‌گیریم و از آنجا که خروجی هش کاملا تصادفی می‌باشد بنابراین در هریک از 
$J_i$
ها مقدار یک یا صفر خواهیم داشت با این ویژگی که تابع هش
$H$
و ورودی‌های آن عمومی می‌باشند به این منظور که رشته 
$ (J_1 \parallel \cdots  \parallel J_t) $
توسط تاییدکننده قابل بررسی باشد.
}
\item {
بعد از اتمام تمام مراحل بالا، اثبات 
$\pi$
به عنوان خروجی الگوریتم اثبات‌کننده تولید می‌شود. اثبات موردنظر شامل یک چندتایی شامل تمام تعهدها(
$com_i$
)
،چالش‌ها(
$ch_{i,j}$
)
و همچنین هش‌شده‌ی پاسخ‌های اثبات‌کننده(
$h_{i,j}$
)
می‌باشدو آخرین قطعه‌ی این اثبات شامل پاسخ‌های شفاف ارائه‌شده توسط اثبات‌کننده می‌باشد با این تفاوت که چینش پاسخ‌ها براساس چینش تولید شده نمی‌باشد به عبارت دیگر پاسخ‌های 
$resp_{i,j}$
متناسب با چالش‌های ساخته شده توسط 
$J_i$
ها به دست می‌آید یعنی به جای ارسال 
$resp_{i,j}$
، الگوریتم
$resp_{i,J_i}$
را به دست آورده و آن‌ها را در اثبات
$\pi$
قرار می‌دهد.
}
	
\end{enumerate}

% ===========================================================================================
% Algorithm 1 
% ===========================================================================================
\begin{algorithm}\label{alg_prover}
	\caption{Prover : $P_{OE}$ on input $(x,w)$}
	\begin{latin}
		%\resetlatinfont
		\begin{algorithmic}[1]
			\State // Create t.c proofs and hash each response
			\For{ $ i=1 \ \textbf{to} \ t $ }
			\State $com_i \leftarrow P_{\Sigma}^{1}(x,w)$
			\For{ $j=1 \ \textbf{to} \ c $ }
			\State $ch_{i,j} \leftarrow_{R} N_{ch} \setminus \{ch_{i,1} , \cdots , ch_{i,j-1} \}$
			\State $resp_{i,j} \leftarrow P_{\Sigma}^2 (x,w,com,ch_{i,j})$
			\State $h_{i,j} \leftarrow G(resp_{i,j})$ 
			\EndFor 
			\EndFor
			
			\State // Get challenge by hashing
			\State $ J_1 \parallel \cdots \parallel j_t \leftarrow H(x(com_i)_i , (ch_{i,j})_{i,j} , (h_{i,j})_{i,j}   ) $ \Comment{Get challenge by hashing}
			
			\State // return proof
			\State \textbf{return} $\pi \leftarrow ( (com_i)_i , (ch_{i,j})_{i,j} , (h_{i,j})_{i,j} , (resp_{i,J_i})_i  )$ \Comment{return proof}
		\end{algorithmic}
	\end{latin}
\end{algorithm}

% ===========================================================================================
% ===========================================================================================
\newpage~
\\
\\
\subsubsection{الگوریتم تاییدکننده}\label{algorithm_verifier}
\begin{enumerate}
\item {
در آغاز این الگوریتم، تاییدکننده خود جدای از آن‌که چالش‌ها را دریافت کند به تولید چالش‌ها می‌پردازد به عبارت دیگر چالش موجود در پروتکل آنره به صورت تصادفی ولی با یک روش مشخص به دست می‌آید چنان‌که هم اثبات‌کننده و هم تاییدکننده می‌توانند با یک تابع مشخص(
$H$
)
به آن برسند. لازم به ذکر است که تمام ورودی‌های این تابع بوسیله اثبات‌کننده به‌عنوان اثبات (
$\pi$
)	
برای تاییدکننده فرستاده شده است.
}

\item {
برای آن‌که اثبات 
$\pi$
توسط تاییدکننده تایید شود لازم است که بررسی‌های زیر به‌تعداد ادعاهای مطرح‌شده توسط اثبات‌کننده صورت بپذیرد بنابراین از یک حلقه تکرار استفاده می‌کنیم
}

\item {
تمام چاش‌های تولید شده در الگوریتم قبلی باید نسبت به هم متفاوت باشند بنابراین بررسی می‌شود که آیا هر دو زوج متفاوت از چالش‌ها باهم متفاوت هست یا خیر
}

\item {
در این خط از الگوریتم بررسی می‌شود که آیا مقدار هش پاسخ‌ها با هش دریافتی در اثبات باهم برابر هستند یا خیر. دلیل این امر آن است که تابع
$G$
عمومی است و تاییدکننده باید از هش دریافتی مطمئن شود
}
\item {
تاییدکننده بررسی می‌کند که آیا خروجی الگوریتم 
$V_{\Sigma}$
براساس ورودی‌های متناظر با آن یک می‌شود یا خیر. ذکر این نکته لازم است به دلیل آن‌که هنگام دریافت اثبات
$\pi$
از طرف اثبات‌کننده، پاسخ‌ها با چینش متناظر با چالش‌های به دست آمده از طریق 
$J_i$
ها بود یعنی 
$resp_{i,J_i}$
ها را دریافت کردیم بنابراین برای تایید پاسخ متناظر با چالش‌ها لازم است که به‌جای
$ch_{i,j}$
از مقدار
$ch_{i,J_i}$
که متناظر با 
$resp_{i,J_i}$
می‌باشد استفاده کنیم
}

\item {
اگر تمام بررسی‌های بالا صحیح باشد آنگاه خروجی الگوریتم یک می‌باشد به این معنی که اثبات توسط تاییدکننده پذیرفته شده است
}
\end{enumerate}~
\\
\\	

% ===========================================================================================
% Algorithm 2 
% ===========================================================================================
\begin{algorithm}\label{alg_verifier}
	\caption{
		Verifier : $V_{OE}$ on input $(x,\pi) $
		where \newline
		\qquad $\pi =  ( (com_i)_i , (ch_{i,j})_{i,j} , (h_{i,j})_{i,j} , (resp_{i,J_i})_i  )$
	}
	\begin{latin}
	%\resetlatinfont
	\begin{algorithmic}[1]
		\State // Compute the challenge hash
		\For{ $ i=1 \ \textbf{to} \ t $ }
		\State $ \textbf{check} ~ ch_{i,1} , \cdots ch_{i,m} pairwise distinct $
		\State $ \textbf{check} ~ h_{i,J_i} = G(resp_i) $
		\State $ \textbf{check} ~ V_{\Sigma}(x,com_i,ch_{i,J_i} , resp_i) = 1 $
		\EndFor
		\If{ all checks succeed} 
		\textbf{return} 1
		\EndIf
		
	\end{algorithmic}
	\end{latin}
\end{algorithm}