محاسبات چندجانبه امن

محاسبات چندجانبه امن (به انگلیسی: Secure multi-party computation) یکی از زیرشاخه‌های رمزنگاری است و مسایلی چون احراز اصالت، امضاهای رقمی و هیچ آگاهی (Zero Knowledge) حالت‌های خاصی ازمحاسبات چند جانبه‌اند.

هدف این زمینه طراحی روش‌هایی است که با استفاده از آن، افراد بدون آنکه مقدار ورودی‌هایشان را افشا نمایند می‌توانند یک تابع از مقادیر ورودی‌هایشان را محاسبه نمایند.

به بیان دیگر شرکت‌کنندگان $P_{1},P_{2},...,P_{n}$ را در نظربگیرید که هر $x_{i}$ تنها در اختیار $P_{i}$ است و هدف شرکت‌کنندگان محاسبه امن و کارای $f(x_{1},x_{2},...,x_{n})=(y_{1},y_{2},...,y_{n})$ می‌باشد به‌طوری‌که $y_{i}$ خروجی اختصاصی $P_{i}$ باشد. بدیهی است در مواردی ممکن است خروجی همه شرکت‌کنندگان یکسان باشد؛ که به صورت $f(x_{1},x_{2},...,x_{n})=(y_{1},y_{2},...,y_{n})=y$ نمایش داده می‌شود.

ایده محاسبه امن یک تابع روی بستر ناامن در سال ۱۹۸۲ با مسئله میلیونرهای یائو آغاز شد. مسئله‌ای که دو میلیونر قصد دارند از اینکه کدامیک ثروتمندتر هستند آگاه شوند بدون اینکه میزان ثروت خود را برای دیگری افشا کنند. تابعی که در این مسئله محاسبه می‌گردد عمل بزرگ‌تر بودن است و خروجی آن یک بیت است.

ویژگی‌های امنیتی

برای احراز پروتکل محاسباتی امن دو ویژگی حفظ حریم خصوصی و درستی به صورت زیر تعریف می‌شود.

• حریم خصوصی: هیچ شرکت‌کننده‌ای اطلاعاتی جزخروجی خود بدست نیاورد.
• درستی: در انتهای پروتکل مقدار خروجی به درستی محاسبه شده باشد.

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

به عنوان نمونه‌ای دیگر از محاسبات چند جانبه، پروتکل رای‌گیری الکترونیکی با $n$ رای‌دهنده را در نظر بگیرید که با مقادیر رأی $x_{i}=1$ به معنای بله و $x_{i}=0$ به معنای خیر در انتخاباتی که دارای یک کاندید است شرکت می‌کنند و هدف شرکت کنندگان محاسبه امن تابع $\sum _{i\mathop {=} 1}^{n}x_{i}$ است. در صورتی که تابع به صورت امن محاسبه گردد خروجی آن تعداد رای‌های بله خواهد بود. برآورده کردن ویژگی حریم خصوصی، مستلزم این است که رای، تمام رای‌دهندگان مخفی بماند. برقراری ویژگی درستی به این معناست که نتیجه رای‌گیری دقیقاً جمع مقادیر رای‌های داده شده باشد.

پروتکل جمع امن

این پروتکل برای محاسبه امن تابع جمع طراحی گردیده‌است. برای سادگی با حضور سه شرکت‌کننده پروتکل را شرح می‌دهیم.

سه شرکت‌کننده $P_{1},P_{2},P_{3}$ را با داده‌های خصوصی $x_{1},x_{2},x_{3}$ در نظربگیرید که $x_{i}\in z_{p}$ و $p$ عدد اولی است که شرکت کنندگان از قبل روی آن توافق کرده‌اند.

هدف شرکت‌کنندگان محاسبه تابع $f(x_{1},x_{2},x_{3})=\sum _{i\mathop {=} 1}^{3}x_{i}{\pmod {p}}$ به صورت امن است. گام‌های پروتکل به صورت زیر است:

۱-هر $P_{i}$ مقادیر $r_{i,1},r_{i,2}$ را به‌طور تصادفی یکنواخت از $z_{p}$ انتخاب می‌کند و مقدار $r_{i,3}=x_{i}-r_{i,1}-r_{2,i}{\pmod {p}}$ را محاسبه می‌نماید.

۲-هر $P_{i}$ از طریق یک کانال خصوصی، مقادیر $r_{i,2},r_{i,3}$ را به $P_{1}$ و $r_{i,1},r_{i,3}$ را برای $P_{2}$ و $r_{i,1},r_{i,2}$ را برای $P_{3}$ می‌فرستد. به عنوان نمونه در انتهای این گام از پروتکل، $P_{1}$ مقادیر $r_{1,2},r_{1,3},r_{2,2},r_{2,3},r_{3,2},r_{3,3}$ را در اختیار خواهد داشت.

۳-هر $P_{j}$ برای $j\neq \ell$ مقادیر $s_{\ell }=r_{1,\ell }+r_{2,\ell }+r_{3,\ell }{\pmod {p}}$ را محاسبه نموده و برای شرکت کنندگان دیگر اعلام می‌کند. به عنوان نمونه $P_{1}$ مقدار $s_{2},s_{3}$ را محاسبه می‌کند و برای $P_{2},P_{3}$ اعلام می‌کند ومقدار $s_{1}$ را از $P_{2},P_{3}$ دریافت می‌کند.

۴- در انتها شرکت کنندگان نتیجه را به صورت $v=s_{1}+s_{2}+s_{3}{\pmod {p}}$ محاسبه می‌نمایند.

• بررسی ویژگی‌های امنیتی پروتکل:

با توجه به رابطه $\sum _{j}s_{j}{\pmod {p}}=\sum _{j}\sum _{i}r_{i,j}{\pmod {p}}=\sum _{i}\sum _{j}r_{i,j}{\pmod {p}}=\sum _{i}x_{i}{\pmod {p}}$

مشاهده می‌کنیم که مقدار $v$ نتیجه جمع ورودی‌های شرکت کنندگان در پیمانه $p$ است؛ بنابراین با فرض صادق بودن همه شرکت کنندگان خاصیت درستی برآورده می‌شود.

برای بررسی ویژگی حفظ حریم خصوصی باید به این پرسش پاسخ داد که آیا در پایان پروتکل شرکت کنندگان غیر از مقدار $v$ اطلاعات جدید دیگری بدست می‌آورند یا خیر؟ مشاهده می‌کنیم که شرکت کنندگان علاوه بر $v$ اطلاعاتی را در گام سوم پروتکل کسب می‌کنند. $P_{1}$ مقدار $s_{1}$ و $P_{2}$ مقدار $s_{2}$ و $P_{3}$ مقدار $s_{3}$ را بدست می‌آورند. اما ادعا می‌کنیم که مشاهده $s_{i}$ توسط $P_{i}$ تنها در بدست آوردن مقدار $v$ مؤثر خواهد بود و اطلاعات جدیدی برای $P_{i}$ به دنبال نخواهد داشت. برای نمونه $P_{1}$ مقادیر $s_{2},s_{3},v$ را در پایان در اختیار خواهد داشت و می‌تواند با محاسبه $s_{1}=v-s_{2}-s_{3}$ مقدار $s_{1}$ را بدست آورد. در واقع با اطلاع از مقدار که در اختیار دارد می‌تواند اطلاعاتی که در طی پروتکل مشاهده نموده‌است را محاسبه (شبیه‌سازی) نماید؛ بنابراین می‌توان نتیجه گرفت که $P_{1}$ اطلاعات جدیدی جز $v$ بدست نیاورده است.

• در اینجا فرض کردیم همه شرکت کنندگان به درستی پروتکل را اجرا می‌کنند و ارتباطات بین آن‌ها از طریق کانال‌های خصوصی می‌باشد. اما در واقعیت همواره چنین فرضیاتی برقرار نیستند؛ بنابراین جهت تحلیل و اثبات امنیت یک پروتکل نیاز به تعریف دقیق‌تر ویژگی‌های امنیتی، محیط اجرای پروتکل و توانایی‌های مهاجم داریم.

قدرت مهاجم

پیچیدگی محاسباتی، استراتژی تخریب و فعال بودن یا غیرفعال بودن از موارد مهم جهت تعیین قدرت یک مهاجم هستند.

• پیچیدگی محاسباتی مهاجم:

1. مهاجم توان محاسباتی محدود (از درجه چندجمله‌ای) دارد.
2. مهاجم توان محاسباتی نامحدود دارد.

• استراتژی تخریب:

1. مهاجم تعداد مشخصی از شرکت کنندگان را تخریب می‌کند و این شرکت کنندگان تا انتها تخریب شده باقی می‌مانند و هیچ شرکت‌کننده دیگری به مجموعه تخریب شده گان اضافه نمی‌شود.
2. مهاجم می‌تواند در هر زمان دلخواهی از اجرای پروتکل به تخریب هر یک از شرکت کنندگان بپردازد و تخریب شده‌گان تا انتها تخریب شده باقی می‌مانند.
3. در این حالت مهاجم به صورت دوره‌ای به تخریب شرکت کنندگان می‌پردازد.

محاسبات دوجانبه امن

محاسبات دوجانبه امن زیر مسئله‌ای از محاسبات چند جانبه است و مورد توجه خاص پژوهشگران حوزه محاسبات چند جانبه است. آن‌ها در پی پاسخ به این سؤال اند که آیا محاسبات دوجانبه‌ای با کارایی بهتر و فرضیات امینیتی ضعیف‌تر نسبت به محاسبات چند جانبه، قابل دستیابی است؟

جستارهای وابسته

• رمزنگاری

منابع

مشارکت‌کنندگان ویکی‌پدیا. «Secure multi-party computation». در دانشنامهٔ ویکی‌پدیای انگلیسی.

• 1- Ronald Cramer , Ivan Damgrd , Jesper Buus Nielsen " Secure Multiparty Computation and Secret Sharing An Information Theoretic Approach" Book Drft (۱۱ مه ۲۰۱۳)