اثبات دانایی صفر

از مفهوماثبات دانایی صفر معمولاً در رمزنگاری استفاده می‌شود. در ریاضی و زندگی ما معمولاً می‌خواهیم چیزهایی را به دیگران بقبولانیم مثلا اگر من بدانم ایکس درست است و بخواهم شما را قانع کنم سعی می‌کنم تمامی حقایقی که می‌دانم و نتایج ضمنی که درست بودن ایکس را نشان می‌دهد حاضر کنم. آلیس باب را قانع می‌کند ایکس درست است و باب به طور کامل قانع می‌شود اما نمی‌تواند هیچ نتیجهٔ دیگر و اطلاعات اضافه تری را در این فرایند به دست آورد. یعنی باب دانایی صفر را به دست می‌آورد. یک اثبات‌کننده(P) سعی‌می‌کند تصدیق‌کننده (V) را متقاعدکند که ادعایش صحیح است. در حالت عادی، P در یک ارتباط یک سری اطلاعات به V می‌دهد و V با محاسباتی صحت ادعای P را تاییدمی‌کند. آیا می‌توان بدون انتقال اطلاعات اضافی، V را متقاعد نمود؟ آیا می‌توان پیام‌های بیشتری ردوبدل‌کرد و در عین حال اطلاعات اضافه منتقل نشود؟ آیا می‌توان با درنظر گرفتن احتمال خطای غیرصفر و با انتقال اطلاعات کم و کافی V را راضی نمود؟

تعریف دانایی صفر

در یک اثبات هنگامی که منظور اصلی بدون هیچ اطلاعات اضافی منتقل شود (واقعیتی برطرف مقابل آشکار شود) آنگاه اثبات با دانایی صفرنامیده می‌شود. در این نوع اثبات V متقاعد می‌شود که P صاحب اطلاعاتی است، اما به‌هیچ طریقی نمی‌تواند این اطلاعات را استخراج کند. در یک پروتکل دانایی – صفر می‌توان کارهایی از قبیل شناسایی، اثبات یک واقعیت یا عملیات دیگر رمزنگاری را، بدون فاش‌کردن اطلاعات محرمانه در هنگام برقراری ارتباط، انجام داد.

مثالی از اثبات دانایی صفر

من می دانم ۲۶۷۸۱ اول نیست برای اثبات دو فاکتور آن را به دست می‌آورم: ۱۱۳*۲۳۷

در اثبات دانایی صفر شما تلاش می‌کنید به فرد دیگری بقبولانید که ۲۶۷۸۱ اول نیست ولی نمی‌خواهید دو فاکتور اول آن را به او بدهید.

حل یک مسئلهٔ دشوار

فرض کنید P حل یک مسئله دشوار را می‌داند. برای اثبات این آگاهی به‌صورت زیر عمل می‌نماید:

1. P با استفاده از اطلاعاتش و با انتخاب یک عدد تصادفی مسئله دشوار را به یک مسئله دشوار جدید تبدیل‌می‌کند.
2. این مسئله جدید باید هم شکل Isomorphic مسئله اول باشد.
3. سپس با استفاده از اطلاعاتش و آن عدد تصادفی مسئله جدید را حل‌می‌کند.
4. P مسئله جدید را برای V ارسال‌می‌کند.
5. V از P می‌خواهد که یکی از دو کار زیر را انجام دهد:
   1. ثابت‌کند که مسئله اول و مسئله جدید هم‌شکل هستند
   2. جواب مسئله جدید را بیان‌کند و نشان دهد که حل آن است
6. P موافقت‌می‌کند و انجام می‌دهد
7. مراحل فوق را n بار تکرارکنند

نکات پروتکل حل یک مسئله دشوار

1. در این الگوریتم P هیچ گاه نباید برای مسئله دشوار جدیدی که به‌دست می‌آورد هر دو درخواست بند (۵) را پاسخ دهد.
2. تبدیل‌های تصادفی و مسئله‌ها نیز باید به‌گونه مناسبی انتخاب شوند تا V اطلاعاتی برای حل مسئله اصلی به‌دست نیاورد.
3. همه مسایل دشوار برای این کاربرد مناسب نیستند. اما تعداد زیادی از این مسایل می‌توانند استفاده شوند.

ویژگی‌های پروتکل دانایی صفر

1. تصدیق‌کننده هیچ معلوماتی از پروتکل به‌دست نمی‌آورد: تصدیق کننده با اتکا به خودش نمی‌تواند مراحل پروتکل را طی کند و به کنش و واکنش اثبات کننده نیاز دارد. پروتکل هیچ اطلاعات محرمانه‌ای را فاش نمی‌کند، در غیر این صورت پروتکل را با حداقل افشاسازی می‌نامند.
2. اثبات‌کننده نمی‌تواند تصدیق کننده را فریب دهد: باتکرارپروتکل احتمال موفقیت اثبات‌کننده متقلب رامی توان به‌اندازه دلخواه کاهش داد. دراین پروتکل‌ها با اولین اشتباه اثبات‌کننده می توان اثبات‌کننده متقلب را شناسایی کرد.
3. تصدیق‌کننده نمی‌تواند اثبات کننده را فریب دهد: تصدیق‌کننده نمی‌تواند از اطلاعات اثبات کننده آگاهی یابد.
4. تصدیق‌کننده نمی‌تواند خودرابه‌عنوان اثبات کننده برای شخص سومی معرفی کند:تصدیق‌کننده حتی نمی‌تواندبه شخص سومی اثبات کندکه اثبات‌کننده دارای اطلاعات سری است.

روش‌های استفاده از پروتکل‌های دانایی صفر

برای استفاده از پروتکل‌های دانایی صفر به سه طریق زیر می‌توان عمل نمود:

• موازی:به‌نحوی که P تعدادی مسئله تدوین‌می‌کند و برای V می‌فرستد. آن‌گاه V درخواست‌های مربوط به هر مسئله را به‌صورت یک جا برای P می‌فرستد. بدین‌صورت از تعداد ردوبدل پیام در مواردی که برقرار ارتباط با تاخیر همراه‌است، کاسته می‌شود.

• تاثیر متقابل:که در آن P و V با ردوبدل متوانی پیام‌هایی مسیر پروتکل را دنبال‌می‌کنند. دراین حالت اثبات به‌صورت قسمت‌به‌قسمت محقق می‌شود.

• زمان غیر واقعی:در این حالت یک تابع درهم یک‌طرفه برروی مسئله‌ها و داده‌ها نقش V را بازی‌می‌کند و برای امضای دیجیتال مورد استفاده قرار می‌گیرد.

امنیت پروتکل‌های دانایی صفر

امنیت پروتکل‌های دانایی صفر معمولاً بر چند مسئله "سخت برای حل" تکیه دارد. مهمترین آنها عبارتنداز: -مسئله به‌دست آوردن لگاریتم گسسته (در هنگ n) یک عدد بزرگ (صدها بیت) -مسئله آگاه شدن از این که یک عدد در هنگ n مربع کامل است، به‌شرط این که از عامل‌های اول آن عدد بی‌خبر باشیم -مسئله تجزیه یک عدد بزرگ که حاصل‌ضرب دو یا چند عدد اول بزرگ (صدها بیت) است

تاریخچه اثبات دانایی صفر

اثبات دانایی صفر توسط گلدواسر میکالی و راکف در سال ۱۹۸۲ معرفی شد. مقالهٔ آنها به یکی از زیباترین و تاثیر گذارترین مفاهیم در علوم کامپیوتر تبدیل شد که دامنهٔ وسیعی از کاربردها از اسکیم‌های امضا تا اثبات اینکه بسیاری از مسائل ان-پی حتی در مرحله تخمین نیز بسیار دشوار هستند را شامل می‌شود.

منابع

دانشگاه پرینستون مفاهیم و کاربردهای عملی دانایی صفر