identification.tex

\section{پروتکل‌های شناسایی}\label{identification}
پروتکل‌های شناسایی
\LTRfootnote{Identification Protocols}
بین دو بخش به‌نام‌های تاییدکنننده و اثبات‌کننده رخ می‌دهد که در طی آن اثبات‌کننده خواهان متقاعدکردن تاییدکننده برای ادعای خود می‌باشد. یک مثال معمولی زمانی است که کاربری خواهان دسترسی به حساب کامپیوتری خود می‌باشد(ورود امن).
\\
عموما پروتکل‌های شناسایی ممکن است براساس یک یا بیشتر فاکتورهای زیر بناشده باشد:
\begin{itemize}
\item {
\textbf{آنچه شما هستید.}
 مانند اثرانگشت، اسکن چشم و ..
}
\item {
\textbf{آنچه شما در اختیار دارید.}
مانند کارت‌هوشمند، سیم‌کارت یا هر توکن‌های سخت‌افزاری 
}

\item {
\textbf{آنچه شما می‌دانید. }
مانند گذرواژه، کلیدهای مخفی و ..
}
\end{itemize}
درادامه خواهان آن هستیم تا پروتکل‌های شناسایی رمزنگاری را که درآن یک اثبات‌کننده تنها نیاز به داشتن( دانستن) یک کلیدمخفی است را بیان کنیم. ساختارهای رمزنگاری بسیار زیادی برای پروتکل‌های شناسایی موجود می‌باشد  و هدف عمومی این است که مقدار محاسبات برای بخش‌های تاییدکننده و همینطور اثبات‌کننده کاهش یابد.
\iffalse
حدوده‌ی امنیت از نسبتا ضعیف پروتکل‌های گذرواژه مبنا تا قوی برای پروتکل‌های اثبات‌دانش‌صفر گسترده می‌باشد.

\\
لازم به ذکر است که مشکلات مربوط به پروتکل‌های شناسایی، ویژه‌ی احراهویت متن (امضاهای دیجیتال) و همچنین مبادله کلید تاییدشده می‌باشد.
\fi

\subsection{معرفی}\label{identification_define}

یک پروتکل شناسایی دراصل قسمتی از یک طرح شناسایی می‌باشد.
یک طرح  کامل شناسایی شامل دو پروتکل به‌نام‌های ثبت‌نام و شناسایی است که میان دو بخش به‌نام‌های اثبات‌کننده و تاییدکننده صورت می‌پذیرد.
طرح‌های شناسایی به دو صورت متقارن و نامتقارن پیاده‌سازی می‌شوند.
دریک طرح شناسایی متقارن ، با اشتراک یک کلیدخصوصی بین هردو بخش، پروتکل ثبت‌نام پایان می‌یابد.
در یک طرح شناسایی نامتقارن ، پروتکل  ثبت‌نام پس از اشتراک یک کلیدعمومی بین  تمام بخش‌ها پایان می‌یابد و تنها اثبات‌کننده از کلیدخصوصی مطلع است.(البته در طرح‌های پیشرفته،  ممکن است تاییدکننده نیز دارای کلیدخصوصی باشد)
\\
یکی از مزیت‌های بزرگ طرح نامتقارن این است که اثبات‌کننده ممکن است چندین مرتبه از کلیدعمومی‌اش در ارتباط با تاییدکننده استفاده کند.
\\
از انواع پروتکل‌های ارائه‌شده برای طرح شناسایی، می‌توان به 
\textbf{طرح گذرواژه مبنا}
، 
\textbf{زنجیره‌ی هش یکطرفه}
 و 
\textbf{پروتکل‌های چالش-پاسخ} 
  اشاره کرد.
از آنجا که در طرح‌امضای ارائه شده در این پایان‌نامه از پروتکل‌های چالش-پاسخ استفاده شده است لذا در ادامه به معرفی این پروتکل خواهیم پرداخت.

\subsection{امنیت طرح شناسایی }\label{security_of_identification}
در این قسمت به حمله‌هایی که ممکن است به طرح شناسایی صورت پذیرد را بررسی می‌کنیم.
با درنظرگرفتن اینکه پروتکل ثبت‌نام در یک محیط امن انجام می‌شود درنتیجه تنها به بررسی حملات رمزنگاری به پروتکل شناسایی می‌پردازیم.
اساسی‌ترین پیش‌نیاز امنیت برای پروتکل شناسایی، متوقف کردن حملات جعل‌هویت
\LTRfootnote{impersonation attacks}
می‌باشد، که در این صورت برای یک مهاجم غیرممکن است تا هویت خودش را  (در برابر  با تاییدکننده یا اثبات‌کننده)با موفقیت جعل کند. در ادامه به معرفی چندین حمله‌ی جعل‌هویت از نوع فعالانه و غیرفعالانه می‌پردازیم.


از اصلی‌ترین حملات جعل‌هویت غیرفعال می‌توان به استراق‌سمع روی یک ارتباط بین اثبات‌کننده و تاییدکننده در یک اجرای قانونی پروتکل شناسایی اشاره کرد. نوع دیگر حملات غیرفعال، حمله‌ی کلید در طرح غیرمتقارن می‌باشد، که درآن حمله‌کننده تلاش دارد تا از طریق کلیدعمومی به کلیدخصوصی دسترسی یابد.
\\
یک فرم ساده از حمله‌ی جعل‌هویت فعال، حمله‌ی حدس
\LTRfootnote{guessing attack}
می‌باشد که درآن حمله‌کننده در نقش اثبات‌کننده درآمده و امیدوار است تا بدون دانستن کلیدخصوصی یا کلیدمخفی اثبات‌کننده، حدس درستی درنظر گرفته باشد.میزان موفقیت حمله‌ی حدس می‌تواند با ترکیب با حمله‌ی تاییدکننده‌ی متقلب
\LTRfootnote{cheating verifier}
افزایش یابد.
در حمله‌ی تاییدکننده‌ی متقلب، متخاصم خود را درنقش تاییدکننده جا می‌زند و امیدوار است تا اطلاعات مفیدی را از طریق اثبات‌کننده با انحراف پروتکل استخراج کند.
\\
در نهایت متخاصم می‌تواند حمله‌ی مردمیانی 
\LTRfootnote{man-in-the-middle}
را اجرا کند. در این حمله، اثبات‌کننده صادق
$\mathcal{P}$
فکر می‌کند که پروتکل شناسایی را با تاییدکننده‌
$\mathcal{V}^*$
اجرا می‌کند، اما درواقع امر،
$\mathcal{V}^*$
تمام پیام‌های ردوبدل شده بین خود و تاییدکننده صادق
$\mathcal{P}$
را به یک تاییدکننده
$\mathcal{V}$
می‌فرستد که خود تاییدکننده
$\mathcal{V}$
نیز فکر می‌کند که در اصل پروتکل را با یک تاییدکننده
$\mathcal{P}$
اجرا می‌کند. به بیان ساده‌تر متخاصم بین تاییدکننده و اثبات‌کننده قرار می‌گیرد و تمام تعاملات از طریق کانال متخاصم انجام شده و هردو بخش تاییدکننده و اثبات‌کننده به این موضوع پی نمیبرند.
\\
حمله مردمیانی یادآور حمله‌ای در شطرنج به‌نام استادبزرگ می‌باشد. در این حمله، یک بازیکن آماتور شطرنج تلاش دارد با بازی کردن همزمان با دو استادشطرنج در یک زمان، مهارت و امتیاز خود را افزایش دهد. در این حمله، یازیکن آماتور دریک بازی مهره‌سفید و در بازی دیگر مهره‌سیاه می‌باشد و با شروع بازی با استادبزرگ اول با مهره مشکی و کپی کردن حرکات شطرنج بین این دواستادبزرگ درانتظار پایان یازی می‌ماند. در پایان بازی‌ها یا بازیکن آماتور در یک بازی پیروزشده و متعاقبا در بازی دیگر شکست خورده و یا هردو بازی به نتیجه مساوی خاتمه یافته است.در پایان با هر کدام از حالت‌های فوق امتیاز بازیکن آماتور  به‌طورقابل‌توجهی افزایش یافته است.

\subsection{پروتکل‌های پرسش-پاسخ اصلی  }\label{ch_resp_protocol}

چهارنوع پروتکل پرسش-پاسخ اصلی وجود دارد. درهریک از این پروتکل‌های شناسایی، تاییدکننده با ارسال یک چالش تصادفی برای تاییدکننده، پروتکل را آغاز می‌کند. درادامه اثبات‌کننده با ارسال یک پاسخ برای تاییدکننده به‌منظور بررسی آن واکنش نشان می‌دهد. طرح کلی این پروتکل در شکل ۱۱۱ به‌صورت خلاصه آمده است.
درادامه برای هر طرح، حملات استراق‌سمع و تاییدکننده‌متقلب را بررسی خواهیم کرد. 


\subsubsection{رمزنگاری متقارن }\label{symmetric_encrypt}

فرض کنید اثبات‌کننده و تاییدکننده  یک کلیدمتقارن
$K ~{\in}_R ~ \{0,1\}^k $
را بین خود به اشتراک گذاشته‌اند. اگر
$E_K$
نشان‌دهنده‌ی الگوریتم رمزگذاری با استفاده از کلید 
$K$
و
$D_K$
نشنان‌دهنده‌ی الگوریتم رمزگشایی مربوطه باشد آنگاه به‌سادگی روشن است که:
$$E_K,D_K : \{0,1\}^k \rightarrow \{0,1\}^k$$

اگر به شکل ۱٫۱٫آ توجه شود پیداست که پروتکل شناسایی با ارسال چالش
$c ~{\in}_R ~ \{0,1\}^k$
توسط تاییدکننده آغاز می‌شود و در ادامه اثبات‌کننده پاسخ
$r = E_K(c)$
را برای تاییدکننده ارسال می‌کند. و درنهایت تاییدکننده تساوی
$D_K(r) = c$
را بررسی می‌کند. اگر تساوی برقرار باشد، پاسخ اثبات‌کننده تایید و درنتیجه شناسایی با موفقیت انجام می‌پذیرد و درغیراینصورت پاسخ اثبات‌کننده رد و پروتکل با موفقیت اتمام نمی‌یابد.
\\



برای ایستادگی در برابر حمله‌ی استراق‌سمع در یک طرح رمزگذاری باید از حمله‌ی متن ساده‌ی شناخته شده 
\LTRfootnote{known-plaintext attack (KPA)}
جلوگیری کرد. و برای  ایستادگی در برابر حمله‌ی تاییدکننده‌متقلب در این طرح لازم است از حمله‌ی متن‌ساده‌ی انتخابی
\LTRfootnote{chosen-plaintext attack(CPA)}
 تطبیقی جلوگیری کرد.
\\
 لازم به ذکر است که ‌حمله‌ی متن ساده‌ی شناخته شده یک نوع مدل حمله است که درآن حمله‌کننده به زوج متن ساده و ورژن رمزگذاری‌شده‌ی آن  دسترسی  دارد  و درصدد است با استفاده از  این زوج‌ها به کشف اطلاعات مخفی همچون کلیدهای خصوصی بپردازد.و حمله‌ی پیام ساده‌ی انتخابی نیز اشاره به مدلی از حمله دارد که در آن حمله‌کننده خواهان آن است تا یک متن ساده‌ی تصادفی را انتخاب و آن را رمزگذاری کند و درنتیجه نسخه‌ی 
رمزگذاری شده‌ی آن پیام را به‌دست آورد.

\subsubsection{احرازهویت متقارن }\label{symmetric_authectication}

فرض کنید اثبات‌کننده و تاییدکننده یک کلیدمتقارن
$K~ {\in}_R ~ \{0,1\}^k$
را بین خود به اشتراک گذاشته‌اند. همچنین 
$H : \{0,1\}^* \rightarrow \{0,1\}^k$
معرف یک تابع هش رمزنگاری می‌باشد.
\\
با توجه به شکل ۱.۱.ب 
پروتکل شناسایی با ارسال چالش
$c ~ {\in}_R ~ \{0,1\}^k$
توسط تاییدکننده برای اثبات‌کننده آغاز می‌شود.و متناسب با آن اثبات‌کننده نیز پاسخ
$r = H(K,c)$
را برای تاییدکننده ارسال می‌کند. درنهایت تاییدکننده رابطه‌ی
$r = H(K,c)$
را بررسی می‌کند.
\\
\\
در مدل‌های اوراکل تصادفی، این طرح در برابر حملات استراق‌سمع و تاییدکننده‌متقلب مقاوم می‌باشد. 

\subsubsection{رمزگذاری نامتقارن }\label{asymmetric_enccryption}

فرض کنید اثبات‌کننده و تاییدکننده یک کلیدعمومی
$pk$
را بین خود به‌اشتراک گذاشته‌اند که تنها اثبات‌کننده از کلیدخصوصی 
$sk$
متناظر با کلیدعمومی مطلع است.همنچنین 
$E_{pk}$
معرف یک الگوریتم رمزگذاری بااستفاده از کلیدعمومی
$pk$
می‌باشد و 
$D_{sk}$
نشان‌دهنده‌ی الگوریتم رمزگشای مرتبط با الگوریتم رمزگذاری است که ازکلیدخصوصی
$sk$
استفاده می‌کند.
\\
چنانکه در شکل ج مشاهده می‌شود ابتدا تاییدکننده پیام
$M ~ {\in}_R ~ \{0,1\}^k$
را انتخاب کرده و سپس با استفاده از الگوریتم رمزگذار، چالش
$c = E_{pk}(M)$
را برای اثبات‌کننده ارسال می‌کند و در ادامه اثبات‌کننده پاسخ موردانتظار
$r = D_{sk}(c)$
را تولید می‌کند. در انتها تاییدکننده تساوی
$r = M$
را بررسی می‌کند.
\\
\\
برای مقاومت در برابر حمله‌ی استراق‌سمع لازم است طرح رمزگذار ایمن معنایی باشد. و همچینین برای مقاومت دربرابر حمله‌ی تاییدکننده‌متقلب لازم است که این طرح در برابر حمله‌ی متن‌ساده‌انتخابی انطباقی ایمن باشد.

\subsubsection{احرازهویت نامتقارن}\label{asymmetric_authentication}

فرض کنید اثبات‌کننده و تایییدکننده یک کلیدعمومی
$pk$
را به‌اشتراک گذاشته و تنها اثبات‌کننده از کلیدخصوصی
$sk$
 وابسته به کلیدعمومی آگاهی دارد. همچنین فرض کنید 
$S_{sk}$	
 بیانگر الگوریتم امضا با کلیدخصوصی
$sk$
و
$V_{pk}$
الگوریتم تاییدساز وابسته به الگوریتم امضا می‌باشد که از کلیدعمومی
$pk$
استفاده می‌کند.
مطابق با شکل د، در آغاز پروتکل شناسایی ، تاییدکننده چالش 
$c~ {\in}_R ~ \{0,1\}^k$
را برای اثبات‌کننده ارسال می‌کند و درادامه اثبات‌کننده در جواب چالش دریافت‌شده، مقدار
$r = S_{sk}(c)$
را برمی‌گرداند. درادامه تاییدکننده بررسی می‌کند که آیا خروجی
$V_{pk}(c,r)$
معتبر می‌باشد یا خیر. اگر خروجی معتبر باشد بیانگر آن است که مقدار
$r$
درواقع امضای پیام
$c$
تحت کلبدعمومی
$pk$
می‌باشد.
\\
\\
برای مقاومت دربرابر حمله‌ی استراق‌سمع لازم است که طرح امضای دیجیتال در برابر حمله‌ی پیام‌  شناخته شده ایمن باشد و برای جلوگیری از حمله‌ی تاییدکننده‌متقلب لازم است تا این طرح در برابر حمله‌های پیام‌انتخابی انطباقی ایمن باشد.
\subsection{پروتکل شناسایی دانش صفر}\label{zk_id_protocol}\LTRfootnote{ZERO-KNOWLEDGE IDENTIFICATION PROTOCOLS}

طرح بخش قبل زمانی ایمن است که از طرح‌های احرازهویت یا رمزنگاری بسیارقوی(مثل طول کلید بزرگ و ..) استفاده شود.همچنین هزینه‌ی مقاومت در برابر حمله‌ی پیام انتخابی تطبیقی برای یک طرح امضای دیجیتال نیز بسیار بالا می‌باشد.‌علاوه‌براین محاسبه‌ی پاسخ چالش نیز برای اثبات‌کننده  ممکن است هزینه‌بر باشد. بنابراین برای رفع مشکلات طرح‌های قبلی به معرفی یک پروتکل جدید می‌پردازیم.
\\
در این بخش به معرفی پروتکل شناسایی دانش‌صفر می‌پردازیم که یکی از ویژگی‌های باارزش آن این است که با هر تلاش یک تاییدکننده‌متقلب، هیچ اطلاعات مفیدی از اثبات‌کننده(ی‌معتبر) استخراج نمی‌شود. به‌بیان‌دیگر واژه‌ی دانش‌صفر بیانگر این  حقیقت است که تاییدکننده‌‌متقلب با کسب هر اطلاعاتی که از طریق تعاملاتی که با اثبات‌کننده دارد، با اطلاعاتی که تاییدکننده‌متقلب از طریق خودش بدون تعامل با اثبات‌کننده تولیدشده است تفاوتی ندارد. 
به‌عبارت‌دیگر ممکن است پیامی که که‌بوسیله‌ی اثبات‌کننده ارسال شده است قابل شبیه‌سازی 
\LTRfootnote{simulated}
باشد که درعمل اثبات‌کننده در آن نقشی نداشته باشد.
یک تاییدکننده‌صدق به‌هرحال متقاعد می‌شود که اثبات‌کننده کلیدخصوصی را می‌داند.؟؟؟

\subsubsection{پروتکل دانش‌صفر اشنور}\label{schnore_zk_protocol}\LTRfootnote{SCHNORE ZERO-KNOWLEDGE PROTOCOL}
\\
 از نمونه‌های موجود پروتکل دانش‌صفر می‌توان به پروتکل اشنور اشاره کرد که براساس  لگاریتم گسسته  طراحی شده است.
\\
فرض کنیم
$\langle g \rangle $
یک گروه از درجه‌ی 
$n$
(که یک عدد اول بسیار بزرگ است) می‌باشد و همچنین 
$\boldsymbol{x} ~{\in}_R ~\mathbb{Z}_n$
 کلیدخصوصی و 
$\boldsymbol{h} = g^x$
نیز کلیدعمومی اثبات‌کننده می‌باشد.تاییدکننده درحین پروتکل ثبت‌‌نام، کلیدعمومی 
$h$
را دریافت می‌کند.یک دور از پروتکل اشنور در شکل ۲۰ نشان داده شده است. درمجموع این پروتکل، به تعداد
$k$
بار به‌صورت پی‌در‌پی بین اثبات‌کننده و تاییدکننده تکرار می‌شود.
$k$
یک پارامتر امنیتی می‌باشد.یک ساختار سه قسمتی به‌مانند اکثر پروتکل‌های دانش‌صفر در هربار تکرار پروتکل اشنور به‌صورت انتقال پیام انجام می‌شود؛ 
\begin{itemize}
\item {
 پیام اول،
$a$
 می‌باشد که دراصل تعهدی برای 
$u$
می‌باشد
}
\item {
 پیام دوم، 
$c$
است که چالش نامیده می‌شود
}
\item {
و پیام سوم،  
$r$
می‌باشد که پاسخ نامیده می‌شود
}
\end{itemize}~
\subsubsubsection{ویژگی صداقت}\label{soundness_property}
\\
درابتدا می‌خواهیم این بحث را شروع کنیم که چگونه پروتکل  اشنور، تاییدکننده را متقاعد می‌سازد که اثبات‌کننده واقعا کلیدخصوصی یعنی
$x = log_g^h$
را می‌داند.
 این خاصیت، ویژگی 
 \textbf{صداقت}
  نامیده می‌شود. و اگر تاییدکننده مجاب شود که اثبات‌کننده راست می‌گوید بنابراین ویژگی صداقت این پروتکل برآورده می‌شود.
\\
  اگر اثبات‌کننده مقدار
$x$
 را نداند، بهترین کاری که می‌تواند انجام دهد این است که اعلان
$a$
را چنان تولید کند که پاسخ
$r$
 برای حالت‌های 
$c=0$
و
$c=1$
درست عمل کند. بدین منظور یک اثبات‌کننده متقلب، برای مهیا کردن پاسخ چالش 
$c=0$
، مقدار اعلان را به‌صورت 
$a = g^u$
درنظر می‌گیرد و 
$r=u$
را ارسال می‌کند. همچنین برای پاسخ به چالش
$c=1$
 می‌تواند اعلان
$a = {g^u}/ h$
 را تنظیم و
$r=u$
 را ارسال کند؛ درادامه هنگام تاییدسازی رابطه‌ی
$g^r = ah$
 رخ خواهد داد.
\\ 
 نکته مهمی که باید در اینجا ذکر شود آن است که اثبات‌کننده بدون دانستن کلیدمخفی
$x$
  هیچ‌گاه نمی‌تواند پاسخی هم برای 
$c=0$
 و هم برای
$c=1$
مهیا کند. به‌عبارت‌دیگر فرض کنید بعد از ارسال اعلان
$a$
، اثبات‌کننده‌‌ای قادر باشد به هر دو چالش
$c=0$
و
$c=1$
به‌درستی پاسخ دهد. این مطلب به این معنی است که اثبات‌کننده قادر است تا دو پاسخ
$r_0$
و
$r_1$
را تولید کند که به‌ترتیب متناسب با چالش‌های
$c=0$
و
$c=1$
می‌باشد. با این حساب، مقادیر
$a$ 
و
$r_0$
و
$r_1$
رابطه‌ی
$$ g^{r_0} = a , \quad g^{r_1} = ah $$
را موجب می‌شوند که اشاره به رابطه‌ی زیر دارد:
$$ h = g^{r_1 - r_0} $$
و رابطه‌ی بالا دراصل نشان‌دهنده‌ی آن است که اثبات‌کننده عملا مقدار
$x$
را می‌داند. دلیل این امر هم آن است که رابطه‌ی زیر برقرار است:
$$ x \equiv {r_1 - r_0} \pmod n $$
درنتیجه با هربار تکرار پروتکل اشنور، اثبات‌کننده‌متقلب به‌احتمال
$ 50 \% $
موفق می‌شود تا به یکی از چالش‌ها به درستی جواب دهد ولی با تکرار 
$k$
بار، احتمال موفقیت اثبات‌کننده‌متقلب حداکثر به‌احتمال
$2^{-k}$
خواهد بود که با این احتمال بسیار کم عملا مشخص می‌شود که اثبات‌کننده‌ی متقلب هیچ شانسی برای پیروز شدن در این پروتکل را ندارد و درنتیجه ویژگی صداقت ضمانت حقیقی بودن اثبات‌کننده و اشراف به دانش موردنظر رادر این پروتکل تضمین می‌کند. 
\\
\subsubsubsection{ویژگی دانش‌صفر}\label{zero_knowledge_property}
\\
دراین قسمت می‌خواهیم نشان دهیم که پروتکل اشنور ویژگی دانش‌صفر را نیز برآورده می‌کند.
یک تاییدکننده‌ی متقلب می‌تواند چندین‌بار برای به‌دست‌آوردن گفگتگوهای
$(a;c;r)$
در هریک از مراحل پروتکل شناسایی مشغول شود. عبارت چندین‌بار به‌معنی حداکثر
$\mathcal{O}(k^\lambda)$
برای ثابت
$\lambda \in \mathbb{N}$
(محدود چندجمله‌ای در پارامترامنیتی
$k$)
می‌باشد.
علاوه‌براین تاییدکننده‌ی متقلب می‌تواند تعاملات
$(a;c;r)$
زیادی را به‌دست آورد.بااین حال تاییدکننده‌ی متقلب می‌تواند تعاملات بالا را بدون تعامل با  اثبات‌کننده به‌دست آورد. دراین حالت تعاملات به‌دست‌آمده‌ی
$(a;c;r)$
را نسخه‌ی شبیه‌سازی شده می‌نامیم که تاییدکننده‌متقلب،نقش تاییدکننده‌ی واقعی و اثبات‌کننده‌ی واقعی را خود تنها بازی می‌کند.
\\
در قدم اول ویژگی دانش‌صفر را برای یک تاییدکننده‌ی صادق
$\mathcal{V}$
نشان می‌دهیم که در این حالت تاییدکننده یک چالش
$c$
را به‌صورت اتفاقی از
$\{0,1\}$
انتخاب می‌کند.درادامه دو الگوریتم چندجمله‌ای احتمالاتی یکی برای تعاملات واقعی و دیگری برای تعاملات شبیه‌سازی شده ارائه می‌کنیم:
\\
sdsdsd
\\
هردو الگوریتم، تعاملات
$(a;c;r)$
را به‌صورت تصادفی و موردپذیرش تولید می‌کنند با این حال احتمال آن‌که تعامل شبیه‌سازی شده چندتایی
$(A;C;R) \in \langle g \rangle \times \{0,1\} \times \mathbb{Z}_n$
که در عبارت
$g^R = Ah^C$
صدق کند به‌صورت زیر می‌باشد:??
$$Pr[(a;c;r)=(A;C;R)] = \frac{1}{2n}$$
با این تفاوت که که تعاملات واقعی دسترسی به کلیدخصوصی 
$x$
را منجر می‌شود در صورتیکه تعاملات شبیه‌سازی شده منجر به تولید کلیدعمومی
$h$
 می‌شود.
\\
\remark
حقیقت این است که یک پروتکل شناسایی در برابر یک تاییدکننده صادق(حقیقی)، ویژگی دانش‌صفر را در خود دارد که درنتیجه‌ی آن هر حمله‌ به کلید کاهش می‌یابد؟؟؟. به‌خصوص آن‌که استراق‌سمع تعاملات میان اثبات‌کننده صادق با تاییدکننده هیچ اطلاعاتی در مورد کلیدخصوصی اثبات‌کننده افشا نمی‌کندُ حتی اگر کلیدعمومی را نیز دراختیار داشته باشیم؟؟؟.
\\
\\
در قدم بعدی ویژگی دانش‌صفر را برای هر حالت عمومی برای هر تاییدکننده‌ی متقلب 
$\mathcal{V}^*$
با زمان چندجمله‌ای احتمالاتی درنظر می‌گیریم. در اینجا از تاییدکننده‌ی ‌متقلب
$\mathcal{V}^*$
که یک نوع ماشین تورینگ احتمالاتی می‌باشد به‌عنوان یک جعبه‌سیاه
\LTRfootnote{black-box}
قابل چاپ مجدد
\LTRfootnote{rewindable}
استفاده خواهیم کرد، به‌این معنی که :
\begin{itemize}
\item 
دسترسی 
$\mathcal{V}^*$
فقط در درون جعبه سیاه می‌باشد، به این معنی که تبادل پیام‌ها با 
$\mathcal{V}^*$
از طریق ورودی خودش و خروجی نوار می‌باشد.
\item 
حالت
$\mathcal{V}^*$
را می‌توانیم به هر حالت قبلی بازگردانی کنیم.
\end{itemize}
از قسمت ۱٫۲٫۱ یادآوری می‌کنیم که تنظیمات یک ماشین تورینگ احتمالاتی از طریق حالت قسمت کنترل متناهی معین می‌شود. محتویات نوار به موقعیت هدر نوار بستگی دارد.از طریق بازگردانی
$\mathcal{V}^*$
می‌توانیم برای چندین ورودی‌ تست کنیم تا خروجی دلخواه ما به‌دست آید. 
\\
fsdfsdfsdf
\\
در مرحله‌ی شش‌ام شبیه‌سازی، از آنجا که
$c \in_R \{0,1\}$
، احتمال آن‌که 
$c=c'$
دقیقا برابر با
$1/2$
می‌باشد.بنابراین به‌طور متوسط بعداز دو مرحله‌ تکرار می‌توان تعاملات
$(a;c;r)$
را شبیه‌سازی کرد. نتیجه آن‌که، مهم نیست تاییدکننده‌متخاصم
$\mathcal{V}^*$
با چه الگوریتمی سعی در استخراج اطلاعات مهم از اثبات‌کننده می‌کند، از همین الگوریتم می‌توان به تولید تعامل توزیع‌شده منحصربه‌فرد بدون نیاز داشتن به همکاری با تاییدکننده نیز پرداخت.
البته قابل ذکر است این وقایع درحالی رخ می‌دهد که تعاملات واقعی از طریق کلیدخصوصی 
$x$
به‌عنوان ورودی تولید شده‌اند و تعاملات شبیه‌سازی شده از طریق کلیدعمومی 
$h$
به‌عنوان ورودی تولید شده‌اند.

\subsubsection{پروتکل اشنور}\label{schnorr_protocol}

پروتکل شکل ۴٫۲ یک پروتکل دانش‌صفر می‌باشد.بنابرآنچه قبلا بحث کردیم، احتمال موفقیت اثبات‌کننده‌ی متقلب 
$50\%$
می‌باشد.با استفاده از 
$k$
تکرار پی‌در‌پی این پروتکل، ویژگی دانش‌صفر قاعدتا حفظ خواهد شد اما احتمال موفقیت اثبات‌کننده‌ی متقلب به 
$2^{-k}$
کاهش پیدا خواهد کردکه این عدد مقدار بسیار ناچیز به عنوان یک تابع از مقدار امنیتی
$k$
خواهد بود.
\\

به‌دلیل آنکه هم اثبات‌کننده و هم تاییدکننده نیاز به  محاسبه‌ی 
$\mathcal{O}(k)$
عمل توان در گروه
$\langle g \rangle$
خواهند داشت بنابریان پیچیدگی محاسباتی پروتکل نتیجه نسبتا بالا می‌باشد. بنابریان اشنور همچنین استفاده ؟؟ را در شکل ۴٫۳ ارائه کرده است(که به عنوان پروتکل اشنور سناخته می‌شود). در این پروتکل، تاییدکننده چالش خود را از یک  میدان بسیار بزرگ به عنوان مثال
$c \in \mathbb{Z}_n$
انتخاب می‌کند.
\\


ویژگی صداقت پروتکل اشنور می‌تواند همچون بالا آنالیز شود.فرض کنید یک اثبات‌کننده  پس از ارسال 
$a$
به‌عنوان اعلان،
قادر باشد تا به حداقل دو چالش 
$c$
و
$c'$ 
با این فرض که
$c \neq c'$
،به‌درستی جواب دهد. درنتیجه اثبات‌کننده قادر خواهد بود تا دو مبادله‌ی
$(a;c;r)$
و
$(a;c';r')$
را تولید کند. البته ذکر این نکته لازم است که این اوامر در صورتی رخ می‌دهد که اثبات‌کننده واقعا لگاریتم گسسته زیر را بداند:
$$ x = \log_g h $$
همچنین 
$$ g^r = ah^c , \quad g^{r'} = ah^{c'}  $$
نشان‌دهنده‌ی آن است که:
$$ h = g^{(r-r') / (c-c')} $$
بنابراین 
بعد از ارسال اعلان 
$a$
اگر اثبات‌کننده کلیدخصوصی
$x$
را نداند آنگاه حداکثر می‌تواند به یک چالش به‌درستی پاسخ درست دهد.از آنجا که 
$n$
حالت ممکن برای چالش وجود دارد(چالش‌ها از یک میدان بسیار بزرگ انتخاب می‌شوند)، احتمال موفقیت 
$1 / n$
می‌باشد که عدد بسیار کوچکی می‌باشد.
\\
~
figure 4.3
~
\\
ویژگی دانش‌صفر نیز همچنین مي تواند در پروتکل اشنور همچون بالا برای یک تاییدکننده صادق 
$\mathcal{V}$
اثبات شود. مراودات دو گفگتگوی واقعی(تولیدشده توسط کلیدخصوصی 
$x \in \mathbb{Z}_n$)
و گفتگوی شبیه‌سازی شده‌(تولیدشده توسط کلیدعمومی
$h \in \langle g \rangle$)
به‌صورت زیر می‌باشند:
$$\{ (a;c;r) :‌u,c \in_R \mathbb{Z}_n ;~ a \leftarrow g^u ;~ r {\leftarrow}_n u+cx \}$$
$$\{ (a;c;r) : c,r \in_R \mathbb{Z}_n ;~ a \leftarrow g^rh^{-c} \}$$
این مراودات یکتا هستند،


\newpage
\subsection{اثبات دانش‌صفر}\label{zero_knowledge_proof}
اثبات دانش‌صفر یک کلاس عمومی از پروتکل‌هایی است که بین دو بخش به‌نام های اثبات‌کننده و تاییدکننده صورت می‌پذیرد.از طریق اثبات دانش‌صفر، اثبات‌کننده تاییدکننده را متقاعد می‌کند که یک عبارت داده شده معتبر است بدون آن‌که هیچ اطلاعات ارزشمندی از حقیقت عبارت را افشا کند.
\\
\\
در پروتکل‌های شناسایی دانش‌صفر، عبارت اثبات‌شده شبیه چیزی مثل "من کلیدخصوصی این کلیدعمومی را می‌دانم" می‌باشد. البته عبارت می‌تواند بزرگتر و بیشتر هم باشد،به‌عنوان مثال "من کلیدخصوصی را برای این کلید عمومی یا آن کلیدعمومی می‌دانم،که در هر حالت کلیدهای خصوصی می‌توانند متفاوت باشند."
\\
\\
درحقیقت، نظریه‌ی اثبات دانش‌صفر گویای این است که هر جمله‌ی چندجمله‌ای غیرمعین
\LTRfootnote{NP-statment}
می‌تواند به طور موثر در دانش‌صفر اثبات شود.

\subsubsection{پروتکل زیگما}\label{sigma_protocols}

مفهوم یک پروتکل زیگما، پروتکل شناسایی (ارائه شده توسط اشنور) را تعمیم می‌دهد. یک پروتکل زیگما فقط باید دربرابر تاییدکننده‌ی صادق، ویژگی دانش‌صفر را دارا باشد.؟؟
\\
به‌دلایل فنی، یک پروتکل زیگما در واقع نیاز دارد تا یک دانش‌صفرِ ‌تاییدکننده‌ی صادقِ ویژه باشد، به‌این‌معنی که شبیه‌ساز بتواند چالش
$c$
را به‌عنوان یک ورودی اضافی انتخاب و یک گفگتگو براساس چالش مشخص
$c$
تولید کند.تمام پروتکل‌های ذکرشده در بالا همگی دانش‌صفر تاییدکننده‌صادق ویژه می‌باشند(بررسی آن آسان است.)
\\

$R = \{ (v;w) \subseteq V \times W \}$
را یک رابطه‌ی باینری فرض کنیم که 
$v \in V$
معرف ورودی عمومی اثبات‌کننده و تاییدکننده می‌باشد و 
$w \in W$
معرف
\textbf{شاهد}
است که ورودی خصوصی اثبات‌کننده می‌باشد.
  
\definition 
یک پروتکل زیگما برای رابطه‌ی
$R$
، پروتکلی طبق شکل ۵٫۱ است بین یک اثبات‌کننده
$\mathcal{P}$
و یک تاییدکننده
$\mathcal{V}$
که دارای ویژگی‌های زیر می‌باشد:
\begin{itemize}
\item{ \textbf{کامل بودن.}}
اگر اثبات‌کننده
$\mathcal{P}$
و تاییدکننده
$\mathcal{V}$
از پروتکل پیروی کنند آنگاه تاییدکننده همواره خروجی 
\textbf{موافقت}
را تولید می‌کند.
\item{\textbf{صداقت ویژه.}}
یک الگوریتم چندجمله‌ای احتمالاتی 
$E$
(استخراج‌کننده) وجود دارد که با دریافت هر 
$v \in V$
و هر جفت گفتگوهای موردپذیرش
$(a;c;r)$
و
$(a';c';r')$
که
$c \neq c'$
همواره شاهد
$w$
را محاسبه می‌کند که رابطه‌ی
$(v;w) \in R$
 برقرار می‌باشد.
\item{\textbf{دانش‌صفرِ تاییدکننده‌صادقِ ویژه.}}
یک الگوریتم چندجمله‌ای احتمالاتی 
$S$
(شبیه‌ساز) وجود دارد که با دریافت هر
$v \in L_R$
و چالش
$c \in C$
، یک گفتگوی
$(a;c;r)$
را با همان توزیع احتمال تولید گفتگو بین اثبات‌کننده‌ی صادق
$\mathcal{P}$
و تاییدکننده‌ی صادق
$\mathcal{V}$
با ورودوی عمومی 
$v$
و چالش
$c$
تولید می کند. البته قابل ذکر است که اثبات‌کننده‌ی
$\mathcal{P}$
از شاهد
$w$
برای برقراری رابطه‌ی
$(v;w) \in R$
استفاده می‌کند.
\end{itemize}
همچنین ذکر این نکته نیز لازم است که اگر 
$C$
شامل یک عضو باشد آنگاه پروتکل زیگما را بدیهی می‌نامیم.
\\

ویژگی صداقت ویژه اشاره یه این نکته دارد که احتمال موفقیت اثبات‌کننده‌ی متقلب حداکثر
$1/n$
است که در اینجا
$n$
نشان‌دهنده‌ی اندازه‌ی فضای چالش‌ها یا
$C$
می‌باشد.ازاین‌رو بااین فرض که 
$n$
نسبتا بزرگ می‌باشد آنگاه یک پروتکل زیگما دانش یک شاهد
$w$
برای یک ورودی عمومی
$v$
را اثبات می‌کند.

\proposition
پروتکل شکل ۴٫۳ یک پروتکل زیگما برای رابطه‌ی 
$\{ (h;x) : h=g^x \}$
می‌باشد.
\refproof~
\\
\begin{itemize}
\item{کامل بودن.}
این ویژگی به‌راحتی قابل بیان است:
$$g^r = g^{u+cx} = g^u(g^x)^c = ah^c$$
قابل ذکر است که اثبات‌کننده 
$r = u+cx$
‌را محاسبه می‌کند.
\item{صداقت ویژه.}
با دریافت دو گفتگوی موردپذیرش 
$(a;c;r)$
و
$(a';c';r')$
درحالیکه
$c \neq c'$
، آنگاه داریم:
\begin{align}
 &\quad ~~ g^r = ah^c, g^{r'} = ah^{c'} \\
 & \Rightarrow g^{r-r'} = h^{c-c'}\\
 & \Longleftrightarrow h = \frac{r-r'}{c-c'}
\end{align}
ازاین‌روز شاهد به صورت 
$ x = (r-r') / (c-c') $
 به‌دست می‌آید.
\item{دانش‌صفرِ تاییدکننده‌ی صادقِ ویژه.}
برای نشان دادن این ویژگی نیز، با دریافت دو توزیع از گفتگوها، یکی با تاییدکننده‌ی صادق(که با اجرای پروتکل رخ می‌دهد و شاهد 
$x$
به‌عنوان ورودی استفاده می‌شود) و دیگری گفتگوی شبیه‌سازی شده(که با انحراف پروتکل، از کلیدعمومی
$h$
به‌عنوان ورودی استفاده می‌شود) داریم:
\begin{align}
& \{ (a;c;r) : u \in_R \mathbb{Z}_n ; a \leftarrow g^u ; r {\leftarrow}_n u+cx \},\\
& \{ (a;c;r) : r \in_R \mathbb{Z}_n ; a \leftarrow g^rh^{-c} \}
\end{align} 
که با دریافت چالش
$c$
دلخواه، این توزیع‌ها یکتا هستند(هر توزیع دقیقا با احتمال
$1/n$
رخ می‌دهند). 
\end{itemize}~
\\
\\
\\
\subsubsection{پروتکل زیگماي غیرتعاملی}\label{non_interactive_sigma_protocol}

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

یک روش ساده و موثر وجود دارد که هر پروتکل زیگما را غیرتعاملی می‌سازد، این روش توسط فیات و شمیر ارائه شده‌اند و به طرح فیات-شمیر شناخته می‌شود.
\\
????
\\
یک ویژگی متمایز اثبات زیگمای غیرتعاملی این است که هر موجودیتی می‌تواند نقش اثبات‌کننده را ایفا کند. به‌عنوان نتیجه می‌توان گفت که اثبات زیگمای غیرتعاملی می‌تواند توسط هر موجودیتی مستقلا تایید شود( مانند امضای دیجیتال که توسط هرشخصی که علاقه به تاییدسازی آن دارد انجام می‌شود).
\\
\\
\subsubsection{امضای دیجیتال ازطریق پروتکل زیگما}\label{ds_from_sigma_protocol}

یک طرح امضای دیجیتال شامل سه الگوریتم می‌باشد:
\begin{itemize}
	\item 
	الگوریتم تولید کلید
	\item 
	الگوریتم تولید امضا
	\item 
	الگوریتم تاییدسازی امضا
\end{itemize}
با یک مثال می‌خواهیم نشان دهیم تا چگونه از هر پروتکل‌ زیگما(که برای شناسایی استفاده می‌شود) یک طرح امضای دیجیتال معادل بسازیم. برای این منظور لازم است تا از تابع هش
$H$
استفاده کنیم.
\\

در پروتکل اشنور(شکل ۴٫۳)، برای اثبات دانش
~$\pmb{x = \log_g h}$~
از کلیدخصوصی 
$x$
و کلیدعمومی
$h$
استفاده می‌کنیم.
طرح امضای دیجیتال اشنور از طریق اعمال پروتکل فیات-شمیر به پروتکل اشنور به‌دست می‌آید. این به‌معنی ان است که چالش
$c$
ازطریق مقدار هش به‌دست‌ آمده از طریق تابع هش با دو ورودی پیام
$M$
و اعلان
$a$
به‌دست می‌آید،
$c \leftarrow H(a,M)$.
البته قابل ذکر است که چالش
$c$
به‌صورت کاملا تصادفی و مستقل از اعلان
$a$
به‌دست می‌آید. در این روش هیچ تعاملی بین تاییدکننده و تاییدکننده نیاز نیست  و تاییدکننده خود به تولید چالش
$c$
می‌پردازد. امنیت این طرح امضا به تابع هش
$H$‌‌
به‌عنوان یک اوراکل تصادفی می‌باشد.از آنجا که 
$H$
یک تابع تصادفی می‌باشد، بنابریان به‌نظر می‌رسد  مقدار چالش
$c= H(a,M)$
با هر پیام 
$M$
متفاوتی برای امضا، به همان میزان تصادفی باشد که اثبات‌کننده چالش را از تاییدکننده‌ی صادق با تعامل دریافت می‌کند. علاوه بر این لازم است تا اثبات‌کننده قبل از محاسبه‌ی چالش
$c$
، اعلان 
$a$
را انتخاب کند.
همچنین فرض می‌شود که 
$2^k \leq n$.
درنتیجه رشته بیتی در
$\{0,1\}^k$
می‌تواند با مقدارهای عددی در 
$\{0,1, \dots , 2^k-1\} \subseteq \mathbb{Z}_n$
یکتا باشد؟؟؟.
طرح امضای اشنور از سه الگوریتم زیر تشکیل شده است، که تمام کاربران گروه
$\langle g \rangle$
با مرتبه‌ی عدد اول
$n$ 
و تابع هش
$H : \{0,1\}^* \rightarrow \{0,1\}^k$
به اشتراک می‌گذارند.
\begin{itemize}
	\item{\textbf{الگوریتم تولید کلید.}}
	یک جفت کلید
	$(h;x)$
	با انتخاب کلیدخصوصی
	$x \in_R \mathbb{Z}_n$
	و مقدار کلیدعمومی
	$h$
	که از طریق 
	$h \leftarrow g^x$
	به‌دست می‌آید، ساخته می‌شوند.
	\item{\textbf{الگوریتم تولید امضا.}}
	با ورودی پیام
	$M$
	و کلیدخصوصی
	$x$
	و انتخاب
	$u \in_R \mathbb{Z}_n$
	و محاسبه‌ی 
	$a \leftarrow g^u$
	،
	$c \leftarrow H(a,M) $
	،
	$ r \leftarrow_n u + cx $
	، امضای پیام
	$M$
	، زوج
	$(c,r)$
	می‌باشد.
	\item{\textbf{الگوریتم تاییدساز امضا.}}
	با دریافت پیام
	$M$
	و زوج
	$(c,r)$
	به‌عنوان امضا و یک کلیدعمومی
	$h$
	،امضای
	$(c,r)$
	بر پیام
	$M$
	مورد پذیرش است اگر تساوی زیر برقرار باشد:
	$$ c = H(g^rh^{-c}, M) $$
\end{itemize}~
\\

کاملا واضح است که طرح امضای اشنور بسیار کارآمد است.هزینه‌ی محاسباتی تولید امضا وابسته به زمان انجام یک عمل توان برای تشکیل
$g^u$
می‌باشد ؟؟ .
هزینه محاسباتی تاییدسازی امضا وابسته به زمان انجام دوعمل توان رسانی
$g^rh^{-c}$
می‌باشد