\documentclass[10pt]{article}

\usepackage{listings}
\usepackage[framed]{mcode}
\usepackage[a4paper]{geometry}


\usepackage{epstopdf}

\usepackage{graphicx}
\usepackage{graphics}
\usepackage{underscore}
\usepackage{geometry}
\usepackage[english]{babel}
\geometry{legalpaper,margin=2cm,includehead=true}
\usepackage{amsfonts,graphics,epsfig,cite}
\usepackage{amssymb,amsthm,enumitem}
\usepackage{pgf}
\usepackage{pgfpages}
\usepackage{amsmath} 

\usepackage{tabularx}
\usepackage{xepersian}


\pgfpagesdeclarelayout{boxed}
{
  \edef\pgfpageoptionborder{0pt}
}
{
  \pgfpagesphysicalpageoptions
  {%
    logical pages=1,%
  }
  \pgfpageslogicalpageoptions{1}
  {
    border code=\pgfsetlinewidth{2pt}\pgfstroke,%
    border shrink=\pgfpageoptionborder,%
    resized width=0.9\pgfphysicalwidth,%
    resized height=0.9\pgfphysicalheight,%
    center=\pgfpoint{.5\pgfphysicalwidth}{.5\pgfphysicalheight}%
  }%
}

\pgfpagesuselayout{boxed}

\settextfont[Scale=1.4]{B Nazanin}
%\setlatintextfont[Scale=1.4]{Times New Roman}
\renewcommand{\baselinestretch}{2.4} %setting line spacing 2.4 as much as default
\renewcommand{\bibname}{مراجع}

\begin{document}
\begin{figure}
\hspace{8cm}
\includegraphics[height=2cm]{logo.png}
\end{figure}

\begin{center}


دانشگاه صنعتی شریف\\

دانشکده مهندسی برق \\

گزارش درس ریاضیات رمزنگاری\\
\end{center}

\begin{center}
\huge
\centerline{عنوان:}
\huge
رمزگذاری  جستجوپذیر متقارن پویا
 \vspace{1\baselineskip}
 \end{center}

\large
\begin{center}
استاد درس:

\textbf{
مهندس }

 \vspace{2\baselineskip}

نگارنده:

\textbf{ز}

\textbf{94}


 \vspace{3\baselineskip}
 
دی ماه 1394
 \end{center}
 \renewcommand{\baselinestretch}{0.6}
 \newpage
\tableofcontents

\newpage
\section*{چکیده}
\textbf{
با استفاده از رمزگذاری 
 جستجوپذیر متقارن  کاربر می تواند داده های خود را به گونه ای رمز کند که قابل جستجو باشند. یکی از کاربردهای مهم این نوع رمزگذاری در رایانش ابری است که کاربر داده های خود را روی یک ابر عمومی که  لزوماٌ مورد اعتماد او نیست ذخیره سازی می کند. یک طرح جستجوپذیر با  سه ویژگی  را می توان عملی دانست : امکان به روزرسانی یا اضافه و پاک کردن فایل ها(پویایی ), زمان جستجوی خطی و امنیت در برابر حمله کلیدواژه منتخب وفقی. طرح های بسیاری تا کنون برای رمزگذاری جستجوپذیر  متقارن مطرح شده اند که هرکدام یک یا چندی از این ویژگی ها را برآورده می سازند. در این مقاله  ابتدا به بررسی طرح های موجود و مقایسه عملکرد آن ها می پردازیم , سپس یک طرح دارای ویژگی پویایی و امنیت اثبات پذیر در برابر حمله کلیدواژه منتخب وفقی را به تفصیل شرح می دهیم.
}
%پیدایش  ابری
%\LTRfootnote{Cloud computing}
%صاحبان داده های حجیم را برآن داشته است تا مدیریت داده ها و محاسبات پیچیده خود را به منظور انعطاف پذیری و صرفه اقتصادی بیشتر به ابر های عمومی واگذار کنند

\textbf{کلمات کلیدی:}
ر
طرح ارائه شده در 
\cite{Curtmola}
به یک پیچیدگی زمانی ثابت دست یافته است, در عین حال از به روز رسانی داده ها پشتیانی نمی کند.به این معنی که برای اضافه یا پاک کردن یک فایل باید تمامی فایل ها از اول اندیس گذاری شوند. 

طرح 
\cite{Liesdonk}
%\lr { SSE} 
\cite{Curtmola}
 برای  هر به روزرسانی 
می بایست  تمامی داده ها را تغییر دهیم که بسیار زمان بر و ناکارآمد خواهدبود.

-نشت اطلاعات مربوط به الگوی جستجوی
\LTRfootnote{Search pattern}
 کاربر را مورد توجه قرار می دهد.  
 
تا سال 2012 این تنها طرح معرفی شده با دو  ویژگی بالاست که امنیت آن در برابر حمله کلیدواژه منتخب وفقی
\LTRfootnote{adaptive chosen keyword
attacks} 
اثبات شده است
\cite{kamara}.
این طرح در سال های بعد مبنایی برای طرح مختلف مانند
\cite{k}
قرار گرفت.
قابل ذکر است که محدودیت عمده این روش بزرگ بودن اندیس رمز شده  می باشد.
جدول  1 به طور خلاصه مقایسه ای از طرح های مختلف رمزنگاری متقارن و قابلیت های هر کدام را نشان می دهد:

\begin{center}

\begin{table}[htp]

\caption{مقایسه طرح های مختلف} 
\centering
\begin{tabular}{c c c c} % centered columns (4 columns)
\hline\hline 
طرح & پویایی & زمان جستجو & اندازه اندیس \\ 
 % inserts table
%heading
\hline % inserts single horizontal line
\lr{SWP} \cite{song} & - & $O(\vert f \vert)$ & اندیس ندارد  \\ 

\lr{SSE-1} \cite{Curtmola} & - & $O(\#f_w)$ & $O(\Sigma_w \#f_w + \#W)$ \\
\lr{SSE-2} \cite{Curtmola}& - & $O(\#f)$& $O(\#f . \#W)$ \\
\cite{kamara} & \lr{$\surd$}&  $O(\#f_w)$ & $O(\Sigma_w \#f_w + \#W)$ \\
\lr{vLSDHJ10} \cite{Liesdonk}& \lr{$\surd$} & $O(Log \#W)$ & $O(\#W . m_f)$\\ [1ex] % [1ex] adds vertical space
\hline %inserts single line
\end{tabular}
 % is used to refer this table in the text
\end{table}

\end{center}

\section{
نماد گذاری و تعریف مسئله
}

فرض کنید کاربر می خواهد$ n$ فایل 
$D_i=(M_i,W_i) , i=1,2,...,n$
را روی کارگزار ذخیره کند .  $M_i$ داده اصلی و $W_i $ مجموعه ای از کلید واژه ها را نشان می دهد که به داده اصلی موجود در هر فایل افزوده شده است:
$$W_i=\{w_1,w_2,...,w_n\}$$

$W_i $
را افزونه فایل
 $i$ 
 ام می نامیم.
 هر یک از فایل ها  با یک شناسه 
\LTRfootnote{Document identifier} 
 شناخته می شوند به طوری که $ID_i$ شناسه مربوط به فایل $D_i$ است.
 فایل ها باید  به گونه ای روی کارگزار ذخیره گردند که محرمانگی   $M_i$ و $W_i $ متناظر آن حفظ شود.

هدف کاربر جستجوی کلید واژه ای مانند $w$ و یافتن $M_i$ ای است که به ازای آن   $w\in W_i  $ باشد. در رمز نگاری  جستجوپذیر تعریف امنیت عدم اطلاع کارگزار از هیچ یک از افزونه ها به جز افزونه فایل حاوی کلیدواژه مورد نظر است.به بیان دیگر برای حفظ امنیت هیچ اطلاعاتی به جز نتیجه جستجو نباید به کارگزار نشت کند. روشهای معمول رمزگذاری جستجوپذیر متقارن در چهار مرحله زیر عمل جستجو را انجام می دهند:



\textbf{1-}
\lr {\textbf{keygen(s)} }
\textbf{:} 
یک  الگوریتم تولید کلید است که توسط کاربر اجرا می شود .ورودی آن یک پارامتر امنیتی$ s $و خروجی آن کلید$ K $می باشد. به طوریکه:
$$K=(k_M,k_W)$$ 
کلید $K_M$ برای رمز کردن داده اصلی و کلید $K_W$ برای رمز کردن افزونه استفاده می شود.

\textbf{2-}
\lr {\textbf{Document-Storage(D)}}
\textbf{:}
فایل ِ$ D $با استفاده از کلید $K $رمز شده و روی کارگزار ذخیره می شود.این تابع خود از دو زیر تابع زیر تشکیل  می شود:

\textbf{-}
\lr {\textbf{Data-Storage(M,kM)}}
\textbf{:}
داده اصلی$ M $را با استفاده از کلید $K_M$رمز کرده و خروجی $E_{K_M }$  , $ID_i$را پس می دهد.

\textbf{-}
\lr {\textbf{Metadata-Storage(W,kW)}}
\textbf{:}
افزونه  $ w$ را با استفاده از کلید  $K_W$  به یک نمایش جستجوپذیر  $S_W$ تبدیل میکند .

\textbf{3-}
\lr {\textbf{Trapdoor(w,kW)}}
\textbf{:}
کاربر با استفاده از $w$ و $k_W$  دریچه $T_w$ را ایجاد می کند .

\textbf{4-}
\lr {\textbf{Search(Tw,SW)}}
\textbf{:}
کارگزار با داشتن $S_W$ و دریچه عمل جستجو را انجام می دهد و در صورتی که $w\in W_i  $ باشد خروجی 1 را پس می دهد.

واضح است که انجام چهار مرحله بالا برای یک عمل جستجو به  $O(n)$  زمان احتیاج دارد .چون کارگزار با دریافت یک $T_W$ 
باید الگوریتم 
\lr {\textbf{Search(Tw,SW)}}
را روی تمامی $S_W $ های ذخیره شده اجرا کند. 

طرح های
\lr { SWP} 
\cite{song}
و 
\cite{Curtmola}
برخلاف روش بالا به جای تبدیل هر افزونه به یک نمایش جستجوپذیر هر کلیدواژه را به یک نمایش جستجو پذیر تبدیل می کنند این باعث می شود برای  هر به روزرسانی 
\LTRfootnote{Update}
مجبور باشیم تمامی داده ها را تغییر دهیم که بسیار زمان بر و ناکارآمد خواهدبود. 
\section{
رمزگذاری جستجوپذیر متقارن پویا
\cite{Liesdonk}
}
فرض کنید کاربر به دنبال فایل هایی است که کلید واژه $w$ در آن ها اتفاق افتاده اند.برای این کار مجموعه $I_W$
به صورت زیر تشکیل می شود:
$$I_W=\{ID_i|w\in W_i\} $$
این مجموعه شامل شناسه تمام فایل هایی است که کلیدواژه مورد جستجو در افزونه آن ها یافت شده است.ایده اصلی این طرح تبدیل هر کلید واژه $w$ به یک نمایش جستجوپذیر $S_W$است به گونه ای که کاربر بتواند بااستفاده از دریچه $T_w$  به فایل های حاوی $w$  دست یابد.برای این مقصود نمایش جستجوپذیر هر کلیدواژه $w$ به صورت زیر تشکیل می شود .
\begin{equation}
S_W=(f_{k_f}(w),m(I_w),R(w))
\end{equation}

که در آن  $F_{k_f}$  یک تابع شبه تصادفی و $k_f$ همان کلید خصوصی $K_W$ یا بخشی از آن می باشد. $m$  تابع پوشش  گذار 
\LTRfootnote{Masking function}
و $R$ حاوی اطلاعاتی برای برداشتن پوشش $I_w$ می باشد. هر بار که کاربر می خواهد کلید واژه ای مانند $w$ را جستجو کند دریچه زیر را برای کارگزار می فرستد :
\begin{equation}
T_w=(f_{k_f}(w),R^{'}(w))
\end{equation}

کارگزار با داشتن دریچه ابتدا تمامی نمایش های جستجوپذیر $S_W$ را برای یافتن $F_{k_f(w)}$ جستجو میکند .هر جا که انطباقی رخ داد $m(I_w)$  متناظر با استفاده از 
 $R(w)$ و 
 $R^{'}(w)$
 پوشش آن حذف می شود. سپس کارگزار شناسه مربوط به فایل هایی که در  $I_w$  اتفاق افتاده اند را برای کاربر می فرستد.به این ترتیب عمل جستجو به پایان می رسد. 
 در این روش برای مخفی کردن الگوی جستجوی  کاربر $I_w$ را تا زمان انجام جستجو توسط تابع پوشش $m$ پوشیده نگه می داریم.بسته به نوع پوشش استفاده شده  این طرح را می توان به دو صورت تعاملی و غیر تعاملی استفاده نمود. طرح اول بار محاسباتی کمتری دارد در عین حال به صورت تعاملی بین کاربر و کارگزار انجام می شود.در عین حال طرح دوم به صورت غیر تعاملی عمل کرده و عمل ذخیره سازی و جستجو را با بکارگیری یک زنجیره چکیده ساز انجام می دهد.
 
 \subsection{
 طرح 1:جستجو و ذخیره به صورت تعاملی}
 در
 این طرح نمایش جستجوپذیر هر کلیدواژه $w$  به صورت زیر است:
\begin{equation}
S_W=(f_{k_f}(w),I_w \oplus G(r),E_{k_E}(w ) )
\end{equation}
برای دست یابی به این نمایش جستجوپذیر ابتدا توابع
\lr{
\textbf{keygen(s)}
}
و
\lr{
\textbf{Data-Storage(M,kM)}
}
  مذکور در بخش 4 محاسبه شده ,  سپس برای  انجام مرحله ذخیره سازی افزونه ها الگوریتم زیر به صورت تعاملی بین کاربر و کارگزار اجرا می شود:
  
  1-
  کاربر مجموعه $U_w$  که شامل شناسه افزونه  های شامل کلیدواژه 
  $w$
 است را  به صورت زیر تشکیل داده و 
 $f_{k_f}(w)$
را به کارگزار ارسال می کند :

2-
کارگزار اولین مولفه ی نمایش های جستجوپذیر را برای یافتن 
$f_{k_f}(w)$
جستجو می کند و  
$E_{k_E(r)}$
(مولفه سوم نمایش جستجوپذیر متناظر ) را برای  کاربر ارسال می کند.

3-
کاربر با داشتن 
 $E_{k_E}(r)$    
و رمزگشایی آن  به صورت
$r=E_{k_E}^{-1}(E_{K_E}(r))$
,
$r$
را بدست می آورد .سپس  با انتخاب  
$r^{'}$
به  صورت تصادفی  
$C$
را به صورت زیر محاسبه و  به کارگزار ارسال  می کند:
\begin{equation}
C=(f_{k_{f}}(w),U_w \oplus G(r) \oplus G^{'}(r) , E_{k_E}(r^{'}}) )
\end{equation}

4-
نمایش جستجوپذیر به روزرسانی شده به صورت زیر خواهد بود:
\begin{equation}
C=(f_{k_{f}}(w),U_w \oplus I_w \oplus G^(r') , E_{k_E}(r^{'}) )
\end{equation}

به عبارت دیگر لیست به روز رسانی شده اندیس های به دست آمده از جستجو برابر با  
$I^{'}(w)=U_w \oplus I_w $
است.

حال نوبت به تولید دریچه توسط کاربر می رسد. به این منظور کاربر با داشتن کلیدخصوصی  
$K_W=(K_f,K_W)$
دریچه 
$T_w=f_{k_f}(w)$
را تولید کرده و برای کارگزار می فرستد. این دریچه در واقع مجوز جستجو است که توسط کاربر به کارگزار داده می شود.در آخر الگوریتم جستجو طی دو مرحله زیر به صورت تعاملی بین کاربر و کارگزار انجام می شود:

1-
کارگزار که دریچه 
$T_w$
را در اختیار دارد اولین مولفه نمایش های جستحوپذیر 
$S_w$
را برای یافتن 
$T_w$
بررسی میکند و در صورد وقوع انطباق مولفه سوم 
نمایش جستجوپذیر متناظر 
($S_3$)
را برای کاربر ارسال میکند.

2-
کاربر 
$E_{k_E}^{-1}(S_3) $
را برای کارگزار می فرستد تا کارگزار طبق رابطه زیر 
$I_w$
را حساب می کند:
\begin{equation}
I_w=S_2 \oplus G(E_{K_E}^{-1}(S_3))
\end{equation}
 به این ترتیب کارگزار  با ارسال 
 فایل هایی که شناسه آن ها در 
 $I_w$
 وجود دارد به کاربر عمل جستجو را به پایان می رساند.

 این طرح دارای دو محدودیت اساسی است:
 
 1-
 الگوریتم ذخیره سازی افزونه ها و همچنین الگوریتم جستجو به صورت تعاملی بین کاربر و کارگزار انجام می شوند.
 
 2-
 الگوریتم ذخیره سازی افزونه ها  پنهای باند  زیادی را اشغال میکند به عبارتی چون 
 $U_w$
 هم اندازه با 
 $I_w$
  است پهنای باند موردنیاز دوبرابر می شود.
 \subsubsection{امنیت اثبات  پذیر}
 
 به طور کلی امنیت یک سیستم رمزگذاری طی انجام یک بازی بین چالشگر و مهاجم 
  اثبات می شود و با نشان دادن  ناچیز بودن احتمال برد مهاجم می توان گفت امنیت سیستم اثبات شده است. در زیر یک نمونه ساده از اثبات امنیت را به اختصار توضیح می دهیم:
  فرض کنید 
  \lr{A}
 مهاجم و 
 \lr{C}
 چالشگر باشند . چالشگر برای به چالش کشیدن مهاجم ابتدا کلیدواژه ای را به صورت تصادفی و با طول 
 $\lambda$
 به صوررت 
 $K \in _ {R} \{0,1\}^ {\vert \lambda \vert} $
تولید می کند و مقدار 
$ \lambda$
 را برای مهاجم می فرستد . مهاجم   
 \lr{A}
  با انتخاب کلید واژه های
 $W_0$
 و
 $W_1$
 از چالشگر می خواهد که یکی را به انتخاب خود رمز کرده و به مهاجم بازگرداند یعنی :
 \begin{equation}
b \in _ {R} \{0,1\}  ,
  C_b=Enc_{K}(W_b)
\end{equation} 

با فرض اینکه مهاجم دریچه 
$T_w$
را در اختیار داشته باشد عمل جستجو را برای کلیدواژه 
$C_b$
انجام داده و حاصل جستجو را تعیین می کند:
\begin{equation}
search(T_{W_0} , C_b)=b^{'}  
\end{equation}

مهاجم 
\lr{A}
,
\lr{$b^{'}$}
را برای چالشگر می فرستد و چالشگر در صورتی که 
$b=b^{'}$
 باشد مهاجم را برنده اعلام می کند.
 در امنیت اثبات  پذیر هدف نشان دادن ناچیز بودن احتمال برد مهاجم 
است.
%\subsection{
% طرح 2:جستجو و ذخیره به صورت غیر تعاملی}


 
  
\section{نتیجه گیری و کارهای آینده}
در این مقاله مروری بر طرح های موجود برای رمزگذاری جستجوپذیر متقارن داشتیم و طرح های مختلف را از حیث پیچیدگی ، پویایی و سایر قابلیت ها با هم مقایسه کرده و در نهابت یک  طرح نمونه را به تفصیل شرح دادیم.

در تحقیقات آینده توجه به نیاز دنیای واقعی ما را به ارایه طرح های عملی  تر و برآوردن نیاز های دنیای امروز  رمزنگاری نزدیک تر می کند . به عنوان نمونه ارایه طرح های جدید برای جستجو در بین ایمیل ها و یا در سیستم های 
\lr{PHR}
و هر سامانه چندکاربره دیگری می تواند مفید واقع شود.

همچنین تعمیم روش های رمزگذاری جستجوپذیر برای یافتن گروهی از کلیدواژه ها و یا یافتن واژه های با تکرار زیاد در اسناد  رمزشده زمینه مناسبی برای تحقیقات آینده به نظر می رسد.

\newpage
\setLTRbibitems
 \begin{thebibliography}{9}
 \resetlatinfont
 
 \bibitem{song}
 Song, D.X., Wagner, D. and Perrig, A., 2000.
 \newblock  Practical Techniques for Searches on Encrypted Data,
 \newblock { Proc. of the 2000 IEEE symposium on Security and Privacy (S\&P 2000).}
 \bibitem{Boneh}
 Boneh, D., Di Crescenzo, G., Ostrovsky, R. and Persiano, G., 2004, 
 \newblock  Public key encryption
 with keyword search,
 \newblock {In Advances in Cryptology-Eurocrypt 2004 (pp. 506-522). Springer Berlin Heidelberg.}
 
 \bibitem{Liesdonk}
 Van Liesdonk, P., Sedghi, S., Doumen, J., Hartel, P. and Jonker, W., 2010.  
 \newblock  Computationally Efficient Searchable Symmetric
 Encryption,
 \newblock {\em EUROCRYPT 2004.
 LNCS, vol. 3027, pp. 506–522. Springer, Heidelberg (2004)}
 
 
 \bibitem{Bosch}
 Bösch, C., Hartel, P., Jonker, W. and Peter, A., 2014.
 \newblock  A Survey of Provably Secure Searchable Encryption,
 \newblock {ACM Computing Surveys (CSUR), 47(2), p.18.}
 




\bibitem{Goh}
Goh, E.J., 2003. 
\newblock  Secure Indexes ,
\newblock {IACR Cryptology ePrint Archive, 2003, p.216.}

\bibitem{Curtmola}
Curtmola, R., Garay, J., Kamara, S. and Ostrovsky, R., 2006, October.  
\newblock Searchable symmetric encryption: improved definitions and efficient constructions,
\newblock {In Proceedings of the 13th ACM conference on Computer and communications security (pp. 79-88). ACM .}


\bibitem{kamara}
 Kamara, S., Papamanthou, C. and Roeder, T., 2012, October. 
 \newblock Dynamic searchable symmetric encryption ,
 \newblock { In Proceedings of the 2012 ACM conference on Computer and communications security (pp. 965-976). ACM.}

\bibitem{k}
Cash, D., Jaeger, J., Jarecki, S., Jutla, C., Krawczyk, H., Rosu, M.C. and Steiner, M., 2014, October
 \newblock  Dynamic searchable encryption in very-large databases: Data structures and implementation.
 \newblock {In Network and Distributed System Security Symposium (NDSS’14).
 Vancouver	
 }


\end{thebibliography}

\end{document}