proposal.tex

\documentclass[12pt,a4paper]{article}
\usepackage{amsmath,amssymb,mathtools}
\usepackage{lipsum}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{tikz-cd}
\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
	
امنیت بیشتر سیستم های رمزنگاری کلید عمومی که امروزه استفاده می‌شود بر اساس مسائل سخت ریاضیاتی همچون مساله تجزیه اعداد و لگاریتم گسسته می‌باشد. با این حال کامپیوترهای کوانتومی قادر خواهند بود این دو مساله سخت در کامپیوترهای کلاسیک را به طور موثری حل کنند که تهدیدی جدی برای رمزنگاری مدرن خواهد بود.
\\
\\
رمزنگاری پساکوانتومی ، مطالعه سیستم های رمزنگاری کلاسیک  می‌باشد که در برابر حملات کوانتومی ایمن باقی می‌مانند.
تاکنون چندین سیستم پیشنهادی برای رمزنگاری پسا کوانتومی کاندید شده اند ، از جمله رمزنگاری های مشبکه مبنا ، کد مبنا ، هش مبنا و همین طور رمزنگاری چندمتغیره.
\\
\\
اخیرا سیستم رمزنگاری بر اساس همسانی های بین خم های سوپرسینگولار توسط جائو و همکارانش در
\cite{jao2014towards}
معرفی شده است که این سیستم رمزنگاری شامل پروتکل تبادل کلید ، اثبات دانش صفر هویت و همچنین رمزنگاری کلید عمومی می‌باشد. همسانی ها به دلیل اندازه کلید کوچک و همچنین پیاده سازی موثر آن 
\cite{efficient, jalali2017efficient}
جز کاندیدهای تبادل کلید پسا کوانتومی می‌باشند.
چندین طرح احراز هویت بر مبنای همسانی ها ارائه شده است که ما در این پایان نامه قصد داریم به بررسی  طرح امضای دیجیتال که قویا غیرقابل جعل در برابر حمله متن انتخاب شده
\LTRfootnote{unforgeable under chosen message attack}
 در مدل اوراکل تصادفی کوانتومی هستند 
 \cite{base}
 بپردازیم. در ادامه به بررسی امضای دیجیتال غیرقابل انکار 
 \cite{undeniable}
 و همچنین امضای دیجیتال غیرقابل انکار کور 
 \cite{blind}
 خواهیم پرداخت. 
 
 طرح امضای معرفی شده ، بوسیله اجرای یک انتقال عمومی اثبات دانش صفر هویت ارائه شده در 
\cite{jao2014towards}
به دست می‌آید. در سیستم های کلاسیک (قدیمی) رمزنگاری ، امنیت امضای دیجیتال از طریق اثبات دانش صفر تعاملی
\LTRfootnote{intractive zero-knowledge proof}
با اعمال مدل انتقالی فیات-شمیر
\LTRfootnote{Fiat-Shamir transform}
 قابل پیاده سازی بود. اما برای امنیت درمدل های کوانتومی نیاز به طرحی جدید نیاز شد که به تازگی
 مدل انتقال آنره
 \LTRfootnote{Unrah}
 ارائه شده است که ما برای طرح پیشنهادی خود از این مدل استفاده خواهیم کرد.
 \\
 \\
 \\
 \textbf{رمزنگاری همسانی-مبنا}

با داشتن دو خم بیضوی 
$ E_1 $
و
$ E_2 $
در میدان متناهی 
$F_q $
با مرتبه 
$q$
، یک همسانی 
$\phi$
عبارت است از یک نگاشت جبری از خم بیضوی
$E_1$
به خم بیضوی
$E_2$
 که 
 $$ \phi(x,y) = \Big(\frac{f_1(x,y)}{g_1(x,y)} , \frac{f_2(x,y)}{g_2(x,y)}\Big) $$
 چنان که 
 $\phi(\infty) = \infty$
. (
$f_1,f_2,g_1,g_2$
چندجمله ای های دو متغیره و 
$\infty$
عنصر همانی روی خم بیضوی می‌باشد). به طور معادل ، یک همسانی یک نگاشت جبری؟؟
.دو خم بیضوی 
$E_1$
و
$E_2$
را روی 
$\mathbb{F}_q$
همسان گوییم اگر و تنها اگر یک همسانی بین آنها وجود داشته باشد. قضیه ای معروف به قضیه تیت 
\LTRfootnote{Tate Theorem}
بیان می کند دو خم 
$E_1$
و
$E_2$
همسان هستند اگر و تنها اگر : 
$$ \# E_1(\mathbb{F}_q) =  \# E_2(\mathbb{F}_q)$$

با داشتن یک همسانی 
$\phi = E_1 \rightarrow E_2$
 از درجه 
 $n$
 ، همسانی 
 $\hat{\phi} : E_2 \rightarrow E_1$
 از درجه
 $n$
 وجود خواهد داشت که :
 $$\phi o \hat{\phi} = \hat{\phi} o \phi = [n]$$
که 
 $[n]$
 یک نگاشت چندبرابر کردن و همسانی
 $\hat{\phi}$
 دوگان همسانی
 $\phi$
 می‌باشد.
 
 
 برای هر عدد طبیعی 
 $n$
 ، زیرگروه 
 $E[n]$
 را به صورت زیر معرفی می‌کنیم :
 $$ E[n] = \{ P \in E(\bar{\mathbb{F}_{q}})  : nP = \infty \} $$
به عبارت دیگر ، 
$E[n]$
 هسته نگاشت 
 $n$
 برابر کردن بستار جبری 
 $\bar{\mathbb{F}}_q$
 	روی میدان 
$\mathbb{F}_q$
 	می‌باشد.؟؟؟
گروه
$E[n]$
با گروه
$(\mathbb{Z} / n\mathbb{Z})^2$
(که 
$n$
و
$q$
نسبت به هم اول اند) یکریخت می‌باشد.


حلقه درون ریختی 
$End(E)$
را مجموعه ای از تمام همسانی ها از خم
$E$
 به خودش روی بستار جبری 
 $\bar{\mathbb{F}_q}$
 از میدان
 $\mathbb{F}$
 می‌نامیم.
 حلقه درون ریختی همراه با عمل جمع گروه  و عمل ترکیب تشکیل یک گروه می‌دهد. اگر
 $dim_{\mathbb{Z}}(End(E)) = 2 $
 باشد آنگاه خم بیضوی
 $E$
 را یک خم معمولی گوییم و اگر 
  $dim_{\mathbb{Z}}(End(E)) = 4 $
  آنگاه خم بیضوی 
  $E$
  را سوپرسینگولار می نامیم.
  دو خم بیضوی همسان یا هر دو معمولی اند یا هر دو سوپرسینگولار هستند.
\\

همسانی 
$\phi : E_1 \rightarrow E_2$
را جداپذیر گوییم هرگاه ؟؟؟  
یک ویژگی مهم یک همسانی جداپذیر آن است که اندازه هسته یک همسانی برابر با درجه همسانی می‌باشد . طبق الگوریتم ولو هر تولید کننده هسته یک همسانی منحصر به فرد تولید خواهد کرد.
\\
\\
\textbf{گراف همسانی}
\\
یک گراف
$\ell$
-همسانی گرافی است که راس های آن خم های بیضوی همریخت و بین دو خم 
$E_1$
و
$E_2$ 
یک یال وجود دارد اگر وتنها اگر یک 
$\ell$
-همسانی بین این دو خم وجود داشته باشد. در خم های سوپرسینگولار ، گراف 
$\ell$
-همسانی گراف متصل است. با داشتن دو راس متفاوت از این گراف پیدا کردن مسیری با اندازه ثابت یک مسئله سخت منظور می‌شود که این سختی مسئله در طراحی سیستم های رمزنگاری همسانی مبنا مورد استفاده قرار می‌گیرد.
\\
\\
\\
\textbf{اثبات دانش صفر}
\LTRfootnote{Zero Knowledge Proof}


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

در عمل ، یک سیستم اثبات دانش صفر (تعاملی) به این شکل است که چندین مرحله ارتباط به صورت چالش و پاسخ بین پگی و ویکتور برقرار می‌شود. در یک مرحله از این ارتباط ویکتور چالشی را برای پگی ارسال می‌کند و پگی متناسب با آن چالش یک پاسخ ارائه می‌دهد و سپس ویکتور با ارزیابی این پاسخ اگر متقاعد شود آنگاه پاسخ را می‌پذیرد و در غیر اینصورت آن را رد می‌کند. پس از طی چندین مرحله مشخص از این پرسش و پاسخ ، یک اثبات دانش صفر خوب مقدار
$y$
که ویژگی
$\mathcal{P}$
را دارد؟؟ دو ویژگی زیر را برآورده می‌کند :
\begin{itemize}
	
\item {تمامیت}\LTRfootnote{Completeness}
\\
	اگر پگی صادق باشد و رازی داشته باشد که بخواهد ویکتور را متقاعد کند که راز را می‌داند و همچنین اگر ویکتور نیز صادق باشد آنگاه این پروتکل به درستی انجام می‌پذیرد.
	
\item {صداقت}\LTRfootnote{Soundness}
\\
	اگر پگی رازی برای اثبات نداشته باشد ولی خواهان آن باشد که ویکتور را به اشتباه متقاعد کند که راز را می‌داند ُ این عمل با احتمال بسیار زیادی غیرممکن است(شانس این عمل خیلی خیلی کم می‌باشد).

\item {دانش صفر}\LTRfootnote{Zero knowledge}
\\
در حین انجام این پروتکل هیچ اطلاعات اضافی توسط پگی نباید فاش شود تا ویکتور نتواند بعد از اتمام این اثبات خود در نقش یم اثبات کننده در مقابل دیگران باشد.	
\end{itemize}

\textbf{مثال}
پگی دو عدد اول بزرگ 
$p$
و
$q$
را انتخاب و 
$N (= p \times q)$
را منتشر می‌کند. وظیفه پگی این است که عدد مشخصی مانند
$y$
را که در میدان 
$N$
مربع است را به ویکتور ثابت کند به نحوی که هیچ اطلاعات اضافی را برای ویکتور افشا نکند تا ویکتور نتواند با این اطلاعات خودش در نقش یک اثبات کننده برای 
$y$
باشد. در این صورت 
$y$
مربعی در میدان 
$N$
است اگر پگی عامل های 
$N$
را بداند و در نتیجه می‌تواند ریشه مربعی برای
$y$
همچون 
$x$
به دست آورد :
$$ x^2 \equiv y \pmod N $$
در هر مرحله ، پگی و ویکتور مراحل زیر را انجام می‌دهند :
\begin{enumerate}
\item{
پگی یک عدد تصادفی 
$r$
را در میدان 
$N$
انتخاب کرده و مقدار
$s$
را به طریق زیر محاسبه و برای ویکتور ارسال می‌کند :
 $$ s \equiv r^2 \pmod{N} $$
	
}

\item{
ویکتور به طور تصادفی یک مقدار
$\beta \in \{0,1\}$
انتخاب و 
$\beta$
را برای پگی ارسال می‌کند.
}

\item{
پگی عدد زیر را محاسبه و برای ویکتور ارسال می‌کند :
\begin{equation}
	z \equiv 
	\begin{cases}
		r \pmod{N} \qquad if \ \beta = 0 ,\\
		xr \pmod{N} \qquad if \  \beta = 1
	\end{cases}
\end{equation}
}

\item {
ویکتور ، 
$ z^2 \pmod{N}$
را محاسبه و بررسی زیر را انجام می‌دهد :
\begin{equation}
z^2 \equiv 
\begin{cases}
s \pmod{N} \qquad if \ \beta = 0 ,\\
ys \pmod{N} \qquad if \  \beta = 1
\end{cases}
\end{equation}
اگر جواب 
true
باشد ، ویکتور جواب پگی را می‌پذیرد و در غیر اینصورت آن را رد می‌کند.

}
\end{enumerate}
پگی و ویکتور این مراحل را 
n
بار (که عدد نسبتا بزرگی است، به طور مثال ۸۰ بار) تکرار می‌کنند. اگر تمام پاسخ های پگی مورد قبول واقع شود آنگاه ویکتور اثبات پگی ( که  
$y$
 مربعی در میدان 
 $N$
 ) را می‌پذیرد (قانع می‌شود که پگی اثبات را می‌داند) در غیر اینصورت اثبات را نمی‌پذیرد.
 % به راحتی می‌توان ویژگی های تمامیت و صداقت را بررسی کرد. 
 % ادامه در قسمت اثبات دانش صفر کتاب سیلورمن
\newline
\newline
\textbf{انواع اثبات}
 \begin{itemize}
 	
 	\item {اثبات تعاملی}
 	\\
 	در این نوع اثبات نیاز به یک ارتباط دوطرفه بین ادعاکننده و اثبات کننده می‌باشد و برای هر ارتباط ادعاکننده با اثبات کننده متفاوت باید ارتباط دوطرفه مجزایی برقرار شود.
 	
 	\item {اثبات غیر تعاملی}
 	\\
 	در این نوع اثبات نیازی به ارتباط بین ادعا کننده و اثبات کننده نیست و بنابراین ادعای یک راز می‌تواند توسط هر اثبات کننده ای ارزیابی شود.
 	
 \end{itemize}


\textbf{پروتکل فیات شمیر}\LTRfootnote{Fiat-Shamir heuristic}

پروتکل فیات شمیر تکنیکی در رمزنگاری است که می‌توان یک امضای دیجیتال بر اساس پروتکل دانش صفر تعاملی که ویژگی سکه عمومی
\LTRfootnote{public-coin}
را دارد ، معرفی کرد. در واقع اگر اثبات تعاملی ، یک پروتکل احراز هویت باشد آنگاه نسخه غیرتعاملی آن می‌تواند به عنوان یک امضای دیجیتال استفاده شود. در واقع پروتکلی که فیات-شمیر معرفی کرده اند این است که با تکنیکی از یک اثبات دانش تعاملی با فرض یک ویژگی معین به یک اثبات دانش صفر غیرتعاملی می‌رسیم که با این پروتکل می‌توان یک انضای دیجیتال طراحی کرد.
\\
\textbf{تذکر.}
در واقع از اثبات دانش تعاملی برای طراحی پروتکل های احراز هویت و از اثبات دانش غیرتعاملی برای طراحی یک سیستم امضای دیجیتال استفاده می‌شود.
\\
\\
در ادامه برای معرفی کامل تر این پروتکل مثال آورده شده است :
\\
\textbf{مثال. }
اثبات دانش صفر تعاملی بر اساس مسئله لگاریتم گسسته
\\
\begin{enumerate}
	\item 
	پگی می‌خواهد ویکتور را متقاعد کند که
	$x$
	را می‌داند : 
	$$y \equiv g^x \pmod{q }$$
	 
	که 
	$y$
	و
	$g$
	و میدان 
	$q$
	عمومی‌اند.
	\item 
	پگی یک عدد تصادفی 
	$ v \in {\mathbb{Z}_q}^*$
	 را انتخاب و 
	 $t = g^v$
	 را محاسبه و برای ویکتور ارسال می‌کند.
	 \item
	 ویکتور یک عدد تصادفی 
	 $c \in {\mathbb{Z}_q}^*$
	 انتخاب و برای پگی ارسال می‌کند.
	 \item 
	 پگی
	 $r = v -cx$
	 را محاسبه و 
	 $r$
	 را برای ویکتور ارسال می‌کند.
	 \item 
	 ویکتور تساوی زیر را بررسی می‌کند :
	 $$ t \equiv g^rg^c \pmod{q }$$
	 اگر طرف دوم را باز کنیم ، داریم :
	 $$ g^rg^c = g^{v-cx}g^{xc} = g^v = t $$
	 
\end{enumerate}

\textbf{نکته. }
اگر در مرحله سوم از یک اوراکل تصادفی غیرتعاملی استفاده کنیم آنگاه طرح اثبات تعاملی ما به یک طرح اثبات غیرتعاملی تبدیل می‌شود که برای رسیدن به این منظور می‌توانیم از تابع هش استفاده کنیم :

\begin{enumerate}
	
	\item 
	پگی می‌خواهد ویکتور را متقاعد کند که
	$x$
	را می‌داند : 
	$$y \equiv g^x \pmod{q }$$
	
	که 
	$y$
	و
	$g$
	و میدان 
	$q$
	عمومی‌اند.
	\item 
	پگی یک عدد تصادفی 
	$ v \in {\mathbb{Z}_q}^*$
	را انتخاب و 
	$t = g^v$
	را محاسبه و برای ویکتور ارسال می‌کند.
	\item 
	پگی 
	$c = H(g,y,t)$
	را محاسبه می‌کند که 
	$H()$
	یک تابع هش می‌باشد.
	\item 
	پگی 
	$r = v - cx$
	را محاسبه می‌کند و زوج 
	$(t,r)$
 به عنوان اثبات نظر گرفته می‌شود.(چنانکه 
 $r$
 توانی از
 $g$
 باشد در پیمانه 
 $q-1$
 محاسبه می‌شود).
 \item 
 هرکسی می‌تواند 
 $t = g^rg^c$
 را بررسی کند.
\end{enumerate}



البته در طرح امضای دیجیتال معرفی شده در پایان نامه از پروتکل آنره
\LTRfootnote{Unruh Construction}
برای ساخت یک اثبات دانش غیرتعاملی  از اثبات دانش تعاملی نظیر آن استفاده می‌کنیم‌ ، که در ادامه به تشریح این پروتکل‌ می‌پردازیم و چون خود این پروتکل از پروتکل زیگما
\LTRfootnote{Zigma Protocol}
بهره می‌برد بنابراین توضیح مختصری در ادامه آمده است.\\
\\

\textbf{پروتکل زیگما
$(\Sigma)$
}

مفهوم پروتکل زیگما را با یک مثال نشان می‌دهیم :

$p$
را عددی اول و 
$q$
را عاملی از 
$p-1$
در نظر می‌گیریم. همچنین 
$g$
عنصری از مرتبه 
$q$
در 
$\mathbb{Z}_p^*$
می‌باشد.در ادامه اثبات کننده 
$\mathcal{P}$
، یک عدد تصادفی 
$w \leftarrow_R \mathbb{Z}_q$
را انتخاب می‌کند و 
$h \equiv g^w \pmod{p}$
را منتشر می‌کند.تاییدکننده 
$\mathcal{V}$
 ، چندتایی 
 $(p,q,g,h)$
 را دریافت می‌کند(
 $(p,q,g,h)$
  عمومی اند). پس از دریافت بررسی می‌کند که اعداد 
  $p,q$
  اعدادی اول هستندو همچنین بررسی می‌کند که آیا 
  $g,h$
  از مرتبه‌ی 
  $q$
  هستند یا خیر؟ . از آنجا که فقط یک زیرگروه از مرتبه‌ی
  $q$
  در 
  $\mathbb{Z}_p^*$
  وجود دارد بنابراین بدیهی است که 
  $h \in <g>$
  و در نتیجه همواره یک مقدار 
  $w$
  وجود دارد که 
 $h = g^w$
 (دلیل این امر به این دلیل است که در یک گروه از مرتبه عدد اول تمام عناصر به غیر از عنصر همانی مولدند و درنتیجه 
 $g$
 یک مولد خواهد بود). با این اوصاف دلیلی وجود ندارد که ثابت کننده 
 $\mathcal{P}$
 حتما از 
   $w$
  آگاه باشد.
  
  پروتکل اشنور یک راه خیلی موثر ارائه می‌کند تا اثبات کننده
  $\mathcal{P}$
  ، تاییدکننده 
 $\mathcal{V}$
 را متقاعد سازد که مقدار یکتای 
 $w \in \mathbb{Z}_q$
 را که 
 $h \equiv g^w \pmod{p}$
 می‌داند: \\
 
\textbf{پروتکل اشنور (بر اساس مسئله لگاریتم گسسته)} 

\begin{itemize}
	\item{ورودی عمومی : }
	اثبات کننده و تاییدکننده هر دو مقادیر 
	$(p,q,g,h)$
	را می‌دانند.
	\item {ورودی خصوصی : }
	اثبات کننده ، مقدار
	$w \in \mathbb{Z}_q^*$
	را در اختیار دارد که :
	$h \equiv g^w \pmod{p}$
	
	\item{پروتکل : }
	\begin{enumerate}
		\item 
		اثبات کننده 
		$\mathcal{P}$
		 ، مقدار تصادفی 
		 $r$
		 (
		 $r \leftarrow_R \mathbb{Z}_q$
		 )
		 را انتخاب و 
		 $a \equiv g^r \pmod{p}$
		 را برای تاییدکننده 
		  $\mathcal{V}$
		  ارسال می‌کند.
		  \item
		  تاییدکننده یک چالش تصادفی 
		  $e$
		  (
		 $e \leftarrow_R \{ 0,1 \}^t$
		  )
		  را برای اثبات کننده ارسال می‌کند (که 
		  $t$
		  ثابت با شرط 
		  $2^t < q$
		  )
		  
		  \item 
		  اثبات کننده مقدار 
		  $z \equiv r + ew \pmod{q }$
		  را برای تاییدکننده ارسال می‌کند.
		  \item 
		  تاییدکننده بررسی می‌کند که آیا 
		  $g^z \equiv ah^e \pmod{p}$
		  (با این دانش که 
		  $p$
		  و
		  $q$
		  اعداد اولند و 
		  $g$
		  و
		  $h$
		  هر دو از مرتبه 
		  $q$
		  هستند) ودر نتیجه اگر عبارت بالا برقرار بود آنگاه اثبات پذیرفته و در غیر اینصورت آن را رد می‌کند.\\
		  توجه :
		  $$ (g^z \equiv g^{r+ew} \equiv g^r.g^{ew} \equiv a.(g^w)^e \pmod{q }) \equiv 
				a.h^e \pmod{p}	 $$
		  
	\end{enumerate}
\end{itemize}




































\newpage
\setLTRbibitems
%\resetlatinfont
\bibliographystyle{plain}
\bibliography{ref.bib}

\end{document}