اثبات دانایی صفر یا پروتکل دانایی صفر چیست؟

اثبات دانایی صفر یا پروتکل دانایی صفر در رمزنگاری روشی است که طرف (اثبات‌کننده) می‌تواند به طرف (تصدیق‌کننده) ثابت کند بیانیه‌ی ارائه‌شده صحیح است. این روش فقط صحت بیانیه را تصدیق می‌کند و هیچ اطلاعات اضافه‌ای را بجز این حقیقت که بیانیه واقعاً صحت دارد ارسال نمی‌کند.

ما معمولاً در ریاضی و یا حتی زندگی واقعی می‌خواهیم چیزهایی را به دیگران تفهیم کنیم. برای نمونه، من می‌دانم درست است و اگر بخواهم شما را هم قانع کنم که درست است، سعی می‌کنم تمامیِ حقایقی که می‌دانم و همچنین نتایجِ ضمنی‌ که درست بودن را نشان می‌دهد برای‌تان رو کنم.

اثبات‌کننده () سعی می‌کند تصدیق‌کننده () را متقاعد کند که ادعایش صحیح است. در حالت عادی، در این ارتباط یک‌سری اطلاعات به  می‌دهد و با انجام محاسباتی صحت ادعای را می‌پذیرد. آیا می‌توان بدون انتقال اطلاعات مهم، را متقاعد کرد؟ آیا می‌توان پیام‌های بیشتری رَدوبَدل کرد و در عین‌حال اطلاعات را حفظ کرد؟ آیا می‌توان با درنظر گرفتن احتمال خطای غیر صفر و با انتقال حداقل اطلاعات مفید، را قانع نمود؟

آلیس باید باب را قانع کند که درست است، امّا طوری‌که باب نتواند اطلاعات دیگری خارج از فرآیند قانع شدن از آلیس به‌دست آورد. یعنیباب دانایی صفر را به‌دست می‌آورد.

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

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

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

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

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

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

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

1. با استفاده از اطلاعات خود و با انتخاب یک عدد تصادفی این مسئله‌ی دشوار را به یک مسئله‌ی دشوار جدید تبدیل می‌کند.
2. این مسئله‌ی جدید باید هم‌شکلِ (Isomorphism) مسئله‌ی اوّل باشد.
3. سپس با استفاده از اطلاعات خود و آن عدد تصادفی، مسئله‌ی جدید را حل می‌کند.
4. مسئله‌ی جدید را برای ارسال می‌کند.
5. از می‌خواهد که یکی از دو کار زیر را انجام دهد:
   1. ثابت کند که مسئله‌ی اوّل و مسئله‌ی جدید، هم‌شکل هستند.
   2. جواب مسئله‌ی جدید را بیان کند و نشان دهد که پاسخ آن است.
6. موافقت می‌کند و انجام می‌دهد.
7. مراحل فوق را بار تکرار می‌کنند.

نکات

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

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

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

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

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

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

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

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

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

امنیت پروتکل‌های دانایی صفر معمولاً بر چند مسئله‌ای که “به دشواری حل می‌شوند” تکیه دارد. مهم‌ترین آنها عبارتنداز:

• مسئله‌ی به‌دست‌آوردن لگاریتم گسسته (در هنگ ) یک عدد بزرگ (صدها بیت).
• مسئله‌ی آگاه شدن از این‌که یک عدد در هنگ مربع کامل است، به‌شرط این که از عامل‌های اوّل آن عدد بی‌خبر باشیم.
• مسئله‌ی تجزیه‌ی یک عدد بزرگ که حاصل‌ضرب دو یا چند عدد اوّل بزرگ (صدها بیت) است.

تاریخچه‌ی اثبات دانایی صفر[ویرایش]

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

منبع