commitment_scheme.tex

\section{ طرح‌های تعهد}\label{commitment_schemes}


برای نشان‌دادن ایده این پروتکل، این سوال را مطرح می‌کینم  که چگونه می‌توان از طریق ایمیل به بازی سنگ، کاغذ، قیچی پرداخت؟ 
\\
اگر بخواهیم به روش مرسوم بازی کنیم و انتخاب‌های خود را با ایمیل ارسال کنیم، شخص باب می‌تواند پس از دریافت انتخاب آلیس از طریق ایمیل، انتخاب خود را برای به‌دست‌اوردن پیروزی تغییر دهد و انتخابی را از طریق ایمیل ارسال کند که با آگاهی از انتخاب طرف دیگر بازی  به‌دست آورده است! و لذا انجام بازی  به‌صورت  عادلانه میسر نیست.
\\
همچنین لازم به ذکر است که احتمال اینکه هردو انتخاب واقعا در یک زمان به طرف مقابل ارسال شود غیرممکن است. حتی واردکردن فرد سوم به بازی به‌عنوان داور هم نمی‌تواند کمکی به اجرای عادلانه بازی داشته باشد زیرا ممکن است یکی از طرف‌های بازی با داور تبانی کند و از حرکت طرف مقابل آگاه شود.
\\
 بنابراین براساس گفته‌های بالا  به این نتیجه می‌رسیم که عملا این بازی از طریق ایمیل با روش معمولی امکان‌پذیر نخواهد بود.
اما راهی وجود دارد که حتی اگر آلیس شروع‌کننده‌ی بازی باشد و باب پاسخ آن را از طریق ایمیل دریافت کند با این حال باب انتخابی که انجام می‌دهد واقعا تصادفی است و از انتخاب آلیس هیچ‌گونه اطلاعی ندارد. این راه‌حل از طریق طرح تعهد قابل پیاده‌سازی می‌باشد که در ادامه به معرفی آن می‌پردازیم.

\subsection{معرفی}\label{commitment_definition}
یک طرح تعهد شامل دو پروتکل به‌نام‌های تعهد و آشکارسازی می‌باشد که معمولا بین دو بخش که به فرستنده و دریافت‌کننده شناخته می‌شوند شکل می‌گیرد. در بیشتر حالت‌ها پروتکل‌های تعهد و آشکارسازی در یک الگوریتم تجمیع ‌می‌شوند. همچنین لازم به ذکر است که برای ارتباط بین فرستنده و دریافت‌کننده نیاز به هیچ تعامل دو سویه نمی‌باشد و درنتیجه این طرح اساسا یک طرح غیرتعاملی می‌باشد.

\begin{definition}\label{commit_scheme_define}
اگر  تعهد یک الگوریتم با زمان چندجمله‌ای و  معین به صورت زیر باشد:
$$ commit : \{ 0,1\}^ k \times \{ 0,1\}^ * \rightarrow \{ 0,1 \}^* $$
که
$k$
پارامتر امنیتی می‌باشد، آنگاه یک طرح تعهد(غیرتعاملی) شامل دو پروتکل بین فرستنده و دریافت‌کننده  می‌باشد که به صورت زیر بیان می‌شوند:
\begin{itemize}
\item[]{
\textbf{مرحله‌ی تعهد .}
در این پروتکل، فرستنده مقدار انتخابی خود یعنی 
$x \in \{ 0,1 \}^*$
را معین و تابع
$C = commit(u,x)$
را محاسبه می‌کند تا مقدار انتخابی خود یعنی 
$x$
با مقدار تصادفی اما معین 
$ u ~ {\in}_R ~ \{ 0,1\}^k$
تلفیق شود و درنتیجه انتخابش، مقداری تصادفی به خود بگیرد. در این مرحله، فرستنده به‌جای مقدار 
$x$
، مقدار 
$C$
 را به‌عنوان تعهدی بر انتخاب اصلی خود ارسال می‌کند. و در طرف دیگر دریافت‌کننده مقدار
 $C$
 را برای ادامه طرح، دخیره می‌کند.
\\
درمثال بالا می‌توان گفت،
$x$
بیانگر حرکت و انتخاب هر بازیکن می‌باشد و 
$u$
یک مقدار تصادفی است که هیچ ارتباطی با انتخاب
$x$
آن ندارد. 
$C$
تعهد و مقداری است که انتخاب 
$x$
در آن مخفی شده است و از طریق ایمیل برای طرف مقابل بازی ارسال می‌شود.
}

\item[]{
\textbf{مرحله‌ی آشکارسازی .}
پروتکلی است که در طی آن فرستنده با ارسال
$u$
و
$x$
برای دریافت‌کننده،  با کمک تابع 
$C = commit ~ (u,x)$
توانایی آشکارسازی مقدار
$x$
از تعهد
$C$ 
را به دریافت‌کننده می‌سپارد.
به‌عبارت‌دیگر در این مرحله دریافت‌کننده به محاسبه‌ی تابع
$commit(u,x)$
می‌پردازد و بررسی می‌کند که آیا خروجی این تابع با مقدار  
$C$
که قبلا دریافت کرده است برابر هستند یا خیر.
\\
برای شبیه‌سازی این مرحله در مثال بالا می‌توان گفت که پس از ارسال تعهدها از طرف آلیس و باب برای یکدیگر در مرحله‌ی قبل، در این مرحله بازی هریک از بازیکن‌ها به بررسی تعهد طرف مقابل پرداخته و درانتها با نمایش انتخاب‌ها پیروز بازی مشخص می‌شود.
}
\end{itemize}

\end{definition}~

لازم به ذکر است که یک حالت خاص از طرح بالا زمانی است که مقدار تعهد شده تک بیتی یعنی 
$x \in \{0,1\}$
باشد که به 
\textbf{طرح تعهد بیتی}
 معروف است. به‌عبارت دیگر برای انجام این پروتکل  فرستنده تنها دو انتخاب دارد که ارزش آن یا صفر یا یک می‌باشد.
 \\
 \\
 برای امنیت کامل این طرح لازم است تا ویژگی‌های زیر در هر طرح تعهدی وجود داشته باشد:
 
\begin{itemize}
\item []{
\textbf{انقیاد .}\LTRfootnote{Binding}
فرستنده نباید بعد از ارسال تعهد
$C$
 قادر به تغییر مقدار 
$x$
 شود.  
 در مثال بالا می‌توان گفت که  آلیس بعد از ارسال حرکت خود از طریق ایمیل، نمی‌تواند بعد از انتخاب حرکت باب، انتخاب خود را تغییر دهد. 
}
	
	
\item[]{
\textbf{‌مخفی‌سازی .}\LTRfootnote{Hiding}
بیانگر آن است که هنگام دریافت تعهد توسط دریافت‌کننده، مقدار موردنظر 
$x$
از طریق تعهد
$C$
قابلیت کشف نداشته باشد.
در مثال بالا می‌توان گفت باب با دریافت تعهد آلیس از طریق ایمیل قابلیت کشف مقدار انتخاب‌ شده‌ی آلیس را ندارد و انتخاب خود را کاملا تصادفی انتخاب می‌کند.
}
\end{itemize}

اگر بخواهیم ویژگی‌های بالا را به‌صورت یک تابع ریاضی پیاده‌سازی کنیم، این دو ویژگی به صورت زیر خواهند بود:
\begin{itemize}
	
\item[]{
\textbf{مقاومت ثانویه .}
برای هر ورودی داده شده، ورودی دیگری که خروجی مشابهی را موجب شود، دشوار باشد. به عبارت دیگر برای هر متخاصم
$\varepsilon$
احتمال تولید
$u,u' \in \{0,1\}^k$
که رابطه‌ی 
$commit(u,0) = commit(u',1)$
را موجب شود، ناچیز باشد.
}
	
	
\item[]{
\textbf{معکوس‌سازی سخت (یکطرفه )}
با داشتن ورودی محاسبه خروجی آسان است اما از طریق خروجی محاسبه ورودی آن مشکل است.
 به‌عبارت دیگر می‌توان گفت توزیع‌های ناشی از
 $commit(u,0)$
 و
 $commit(u,1)$
 زمانیکه
 $u~ {\in}_R \{0,1\}^k $
 ،غیرقابل‌تشخیص(یکنواخت) باشند.
}
\end{itemize}~
\iffalse
علاوه‌براین، یک طرح تعهد، انقیادمحاسباتی
\LTRfootnote{computationally binding}
 خوانده می‌شود اگر متخاصم
$\varepsilon$
محدود به یک الگوریتم احتمالاتی چندجمله‌ای باشد. به‌عبارت دیگر چون متخاصم محدودیت محاسباتی دارد بنابراین طرح ما از امنیت برخوردار است. درغیراینصورت یعنی زمانیکه متخاصم هیچ‌گونه محدودیت محاسباتی نداشته باشد آنگاه این طرح را انقیاد اطلاعاتی نظری
\LTRfootnote{information-theoretically binding}
می‌نامیم و به بیان بهتر می‌توان گفت که از نظر نظری امنیت سیستم پابرجاست ولی درعمل با  این فرض که متخاصم هیچ محدودیت محاسباتی ندارد امنیت طرح لزوما برآورده نمی‌شود.
\\
\\
به‌طور مشابه اگر توزیع‌های ناشی از 
$commit(u,0)$
و
$commit(u,1)$
 نیز به‌صورت محاسباتی غیرقابل‌تشخیص باشند آنگاه طرح تعهد را مخفی‌سازی محاسباتی
 \LTRfootnote{computationally hiding}
 گوییم و همچنین طرح را مخفی‌سازی اطلاعاتی نظری
 \LTRfootnote{information-theoretically hiding}
 گوییم اگر این توزیع‌ها از نظر آماری غیرقابل‌تشخیص باشند.
\\
\\
در پایان ذکر این نکته نیز لازم است که امنیت بالا تنها در برابر حملات فرستنده یا گیرنده صدق می‌کند. به‌طورمثال اگر فرض شود بخش
$\mathcal{A}$
به‌عنوان فرستنده و بخش
$\mathcal{B}$
در نقش دریافت‌کننده باشد و تعهد
$C$
از طرف
$\mathcal{A}$
برای
$\mathcal{B}$
ارسال می‌شود آنگاه هیچ ضمانتی وجود ندارد که دریافت‌کننده
$\mathcal{B}$
متوجه شود که یک متخاصم مقدار تعهد
$C$
را با تعهدجعلی
$C' = commit(u',x')$
را درحین اجرای پروتکل تعهد جایگزین کرده است و درنتیجه مقدارهای
$u,x$
را با مقدارهای
$u',x'$
را در حین پروتکل آشکارسازی جایگزین کرده است. برای جلوگیری از این حمله استفاده از یک کانال احراز شده بین
$\mathcal{A}$
و
$\mathcal{B}$
ضروری می‌باشد.
\fi

\example{
	اگر یک تابع هش رمزنگاری
	$H$
	را دراختیار داشته باشیم آنگاه طرح تعهد بیتی خود را می‌توانیم به صورت زیر به‌دست بیاوریم:
	$$ {commit}_0(u,x) = H(u,x) $$
	که درآن مقدار تعهد
	$x \in \{0,1\}$
	و
	$u \in \{0,1\}^k $
	می‌باشند.
	
	\begin{itemize}
		\item {
			ویژگی مقاوم-تصادم تابع هش
			$H$
			ضمانت می کند که شخص متعهدشده نمی‌تواند 
			$u$
			،
			$x$
			و
			$u'$
			،
			$1-x$
			را به‌دست آورد بطوریکه
			$$ H(u,x) = H(u',1-x) $$
			بنابراین طرح ما خاصیت انقیاد را دارا می‌باشد.
		}
		
		\item {
			ویژگی مقاوم در برابر تضاهر برای خاصیت مخفی‌سازی لازم می‌باشد ولی با این ویژگی هیچ ضمانتی نیست که مقدار
			$x$
			مخفی(به اندازه مقدار
			$u$
			) بماند.بدین منظور لازم است که از مدل اوراکل تصادفی استفاده کنیم.
		}
	\end{itemize}

}

\subsection{طرح تعهد در اثبات دانش صفر}
طرح تعهد در بسیاری از پروتکل‌های رمزنگاری مورداستفاده قرار می‌گیرند. از جمله‌ی این پروتکل‌ها می‌توان به اثبات دانش صفر اشاره کرد.
در ادامه به‌ دلایل استفاده اثبات دانش صفر از طرح تعهد می‌پردازیم.