parameter_sizes.tex

\subsection{ اندازه پارامتر}\LTRfootnote{Parameter Sizes}\label{size_parameter} 
همان‌طور که  قبلا بررسی شد، اعداد اولی که برای ساخت همسانی‌ها از آن استفاده می‌کنیم به فرم
$p = \ell_A^{e_A} \ell_B^{e_B} \cdot f \pm 1$
می‌باشد با این ویژگی که 
$\ell_A^{e_A} \approx \ell_B^{e_B}$.
همچنین یادآوری می‌کنیم که برای داشتن 
$\lambda$
بیت امنیت پساکوانتومی لازم است تا اعداد اول مورداستفاده در طرح امضا به طول
$6 \lambda$
بیت باشند(
\ref{sign_security}
)، درنتیجه اندازه عامل‌های اعداد اول به‌صورت
$\ell_A^{e_A} \approx \ell_B^{e_B} \approx 2^{3 \lambda}$
خواهد بود.
ازآنجا که در طرح امضای خود، خم‌های سوپرسینگولار را در میدان
$\mathbb{F}_{p^2}$
تعریف می‌کنیم درنتیجه اندازه عناصر میدان،
$12\lambda$
بیت طول خواهند داشت.
\\
خم‌هایی که در طرح امضای خود استفاده می‌کنیم به فرم خم‌های مونت‌گومری
\\ 
$By^2 = x^3 + Ax^2 + x$
می‌باشد. از مزیت‌های خم‌ مونت‌گومری می‌توان به محاسبات همسانی‌ها اشاره کرد که فقط به ضریب
$A$
نیاز می‌باشد.
از طرف دیگر، یک نقطه روی خط کامر
\LTRfootnote{Kummer line}
 نیز می‌تواند بوسیله‌ی ضریب
$X$
اش نشان داده شود.
 با این اوصاف،برای نمایش هر عنصر میدان در خم به فرم مونت‌گومری و خط کامر، نیاز به 
$12 \lambda$
بیت می‌باشد.
\\
\\
\textbf{فشرده‌سازی.}
آذردرخش و همکارانش در
\cite{azarderakhsh_key_compress}
نشان داده‌اند که نقاط تابی(که مولد زیرگروه‌های تابی می‌باشند) می‌توانند بوسیله‌ی ضریب‌هایشان فشرده شوند. از آن‌جا که پیاده ‌سازی این روش زیادی کند می‌باشد اخیرا کاستللو و همکارانش در
\cite{costello_efficientkey_compress}
یک الگوریتم جدیدتری ارائه داده‌اند که نسبت به روش آذردرخش  هم سریع‌تر است و هم اندازه کلیدعمومی  آن به نسبت طرح قبلی کوچکتر می‌باشد. در مورد اجرای این الگوریتم می‌توان گفت تقریبا برابر با اجرای یک مرحله از پروتکل اثبات‌دانش‌صفر می‌باشد.
\\
همچنین در بخش قبلی اشاره شد که می‌توانیم  زیرگروه تولید شده توسط یک نقطه تابی را تنها با یک مولد و ضریبش نشان دهیم. از آنجا که نقاط مولد زیرگروه ‌‌ها در طرح ما عمومی می‌باشند درنتیجه می‌توانیم برای نمایش یک زیرگروه تابی تنها از یک  ضریب برای اختصار استفاده کنیم، به عبارت دیگر: 
$$ 
R = mP_A + nQ_A  \xrightarrow[]{m^{-1}}
m^{-1}R=m^{-1}mP_A + m^{-1}nQ_A = P_A + m^{-1}nQ_A = P_A + k Q_A 
$$
با توجه به مطالب بالا برای نمایش
$R$
فقط لازم است که 
$k$
را در اختیار داشته باشیم چون 
$P_A$
و
$Q_A$
عمومی هستند.
\\
در محاسبه ترکیبات  خطی‌، برای فشرده‌‌سازی دو مولد یک گروه تابی، نیاز به سه ضریب  می‌باشد که برای هر ضریب  تقریبا 
$3 \lambda$
بیت نیاز می‌باشد.
\\
\subsubsection{فشرده‌سازی امضا}

به دو روش می‌توانیم، طرح امضای خود را فشرده کنیم:
\begin{itemize}
\item{
فشرده‌سازی کلیدعمومی	
}

\item{
فشرده سازی پاسخ
$\psi(S)$
زمانیکه در مرحله‌ای از الگوریتم امضا،
$ch=1$
انتخاب شده باشد
}
\end{itemize}
لازم به ذکر است، کلیدخصوصی
$S$
 و پاسخ 
$ch = 0$
 یعنی
$(R,\phi(R))$
به دلیل آنکه با ضریب
$3 \lambda$
بیتی قابل نمایش‌اند، لذا نیازی به فشرده‌سازی ندارند.
\\
\begin{itemize}
\item{\textbf{کلیدعمومی. }}
از آنجا که از خم مونتگومری استفاده می‌کنیم بنابراین کلیدعمومی ما به فرم
$pk = (a, x(P_B), x(Q_B), x(P_B-Q_B))$
می‌باشد که 
$a$
بیانگر ضریب
$A$
 در خم عمومی 
 $E / \langle S \rangle$
 می‌باشد. این چهار عنصر میدان به
 $48 \lambda (= 4 \times 12 \lambda)$
 بیت برای ‌نمایش نیاز دارند.	
\\ 
 کلیدعمومی را می‌توانیم با فشرده‌سازی نقاط تابی
 $(\phi({P_B}) , \phi({Q_B}) )$
، که نیاز به سه ضریب
$3 \lambda$
بیتی دارند را فشرده کنیم.
به‌دلیل آنکه مختصات نقاط
$P_B$
و
$Q_B$
از طریق ضرایب فشرده‌شان قابل تولید می‌باشد بنابراین
نیازی به ضریب
$X$
نقطه‌ی
$\phi(P_B-Q_B)$
نمی‌باشد. 
بنابراین به‌طورکلی در کلیدعمومی برای نمایش خم،
$12\lambda$
بیت و برای مولدها نیز
$9 \lambda$
بیت نیاز داریم که جمعا 
$21 \lambda$
بیت می‌شود.
% ----------------------------------------------
\item{\textbf{کلیدخصوصی.}}
کلیدخصوصی
$S$
می‌تواند تنها با یک ضریب
$n$
که نیاز به
$3 \lambda$
بیت می‌باشد ذخیره شود. دلیل این امر هم این است که کلیدخصوصی
$S$
از مرتبه‌ی
$\ell_A^{e_A}$
می‌باشد و 
$ S = P_A + [n] Q_A $.
% ----------------------------------------------
\item{\textbf{امضا.}} 
برای هر مرحله‌ی
$i$
ام از پروتکل اثبات‌دانش‌صفر، امضا شامل چندتایی

$(com_i, ch_{i,j}, h_{i,j}, resp_{i,J_i})$
می‌باشد. بنابراین:
\begin{itemize}
\item{
	هر تعهد شامل دو خم
	$(E_1,E_2)$
	می‌باشد که هر کدام از این خم‌ها به یک عنصر میدان که همان ضریب 
	$A$
	می‌باشد، نیاز دارند.

}
\item{
یک بیت برای نمایش بیت چالشی
$ch_{i,0}$
نیازاست. البته قابل ذکر است که اگر مقدار
$ch_{i,0}$
را داشته باشیم نیازی به ارسال
$ch_{i,1}$
نمی‌باشد، دلیل این امر هم تساوی 
$ch_{i,1} = 1 - ch_{i,0}$
می‌باشد.
}
\item{
چنانچه در
\ref{sign_security}
 توضیح داده شده است، برای هش
$h_{i,j} = G(resp_{i,J_I})$
نیز به
$3 \lambda$
بیت فضا نیاز می‌باشد.
\\
 ذکر این نکته نیز لازم است که با 
$resp_{i,J_i}$
، می‌توان
$h_{i,j}$
را محاسبه کرد و بنابراین نیازی به ارسال این هش وجود ندارد.
}
\item{
براساس بیت چالشی
$J_i$
جواب‌های متفاوتی خواهیم داشت و ازاین‌رو طول بیت متفاوتی نیز برای ذخیره‌سازی لازم خواهد بود. اگر
$J_i = 0$
آنگاه پاسخ موردنظر
$(R,\phi(R))$
خواهد بود که دراین صورت با توجه به وجود مولدهای عمومی، بدون هیچ هزینه محاسباتی نیاز به 
$3 \lambda$
بیت برای ذخیره‌سازی لازم خواهد بود.
اگر
$J_i = 1$
آنگاه پاسخ،
$\psi(S)$
است که به
$12 \lambda$
بیت به‌عنوان یک عنصر میدان لازم خواهد بود که با فشرده سازی به
$3 \lambda$
بیت تقلیل می‌یابد.
}
\end{itemize}
   
\end{itemize}	
در مجموع، برای هر مرحله از اثبات دانش صفر تقریبا به طورمتوسط به 
$$24 \lambda + 1  + 3 \lambda + \frac{3\lambda + 12\lambda}{2} \approx 34.5\lambda$$
بیت فضا بدون فشرده سازی نیازاست که با فشرده‌سازی تقریبا به‌طور متوسط به 
$$24 \lambda + 1 + 3 \lambda + 3 \lambda \approx 30\lambda$$
بیت نیاز خواهد بود.
\\

اگرچه برای تامین
$\lambda$
بیت امنیت پساکوانتومی کفایت می‌کند تا پروتکل اثبات دانش صفر،
$\lambda$
بار تکرار شود اما به‌دلیل آنکه هش چالش‌ها دربرابر الگوریتم گراور
\cite{grover}
آسیب‌پذیر نباشد(بخش ۵٫۳)، لازم است که پروتکل امضا،
$2\lambda$
بار پروتکل اثبات دانش صفر را تکرار کند. با این اوصاف در کل، امضا تقریبا به‌طورمتوسط
$69{\lambda}^2(=2\lambda \times 34.5\lambda)$
بیت در حالت عادی و 
$60{\lambda}^2$
بیت درحالت فشرده‌سازی لازم دارد.
\\
به‌عنوان مثال برای دست‌یابی به 
$128$
بیت امنیت پساکوانتومی(تعداد بیتی که در حالت پساکوانتومی ایمن باشد) برای طرح امضای ارائه شده، به‌طور متوسط به
$48\lambda = 6144$
(
$2688$
در حالت فشرده) بیت برای کلیدعمومی، 
$3\lambda = 384$
بیت برای کلیدخصوصی و
\\
$69{\lambda}^2 = 1,130,496$
($122,880$
برای حالت فشرده) بیت برای امضا لازم است.
\subsubsection{سنجش}
دراین قسمت می‌خواهیم سایز پارامترهای لازم در طرح خود را با سایر طرح‌های امضای پساکوانتومی مقایسه می‌کنیم.
\\
همان‌طور که از جدول زیر قابل مشاهده‌ است، طرح امضای معرفی شده در این پایان‌نامه دربرابر سایر طرح‌های امضای پساکوانتومی موجود دارای کلید با طول سایز کوچکتر می‌باشد. البته قابل ذکر است که گونه‌هایی از طرح امضای مرکل وجود دارد که دارای طول کلید کوچکتری(۳۲ بیت) با همان درجه امنیت می‌باشد اما؟؟.

\begin{center}
	\begin{table}[h]\label{tbl:comparison_signature_scheme}
	\caption{
	سنجش سایز پارامترها(به بایت) در طرح‌های امضاهای پساکوانتومی 
	\\
	متفاوت در سطح امنیتی ۱۲۸ بیت کوانتومی
	}	
	\begin{tabular}{ r | c | c | c }
		طرح امضا & سایز کلیدعمومی & سایز کلیدخصوصی & سایز امضا  \\ 
		\hline
		هش مبنا & 1,056 & 1,088 & 41,000 \\ 
		کد مبنا & 192,192 & 1,400,288 & 370 \\ 
		مشبکه مبنا & 7,168 & 2,048 & 5,120 \\ 
		حلقه مبنا & 7,168 & 4,608 & 3,488 \\ 
		چندمتغیره مبنا & 99,100 & 74,000 & 424 \\ 
		\hline
		همسانی مبنا & 768 & 48 & 141,312 \\ 
		همسانی مبنای فشرده & 336 & 48 & 122,880 \\   
	\end{tabular}
\end{table}
\end{center}