اثبات هیچ‌آگاهی

در یک اثبات، هنگامی که منظور اصلی، بدون هیچ اطلاعات اضافی منتقل شود (واقعیتی برای طرف مقابل آشکار می‌شود) که به‌آن اثبات با دانایی صفر می‌گوییم. در این نوع اثبات، ${\displaystyle V}$

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

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

فرض کنید ${\displaystyle P}$

1. ${\displaystyle P}$
   با استفاده از اطلاعات خود و با انتخاب یک عدد تصادفی این مسئلهٔ دشوار را به یک مسئلهٔ دشوار جدید تبدیل می‌کند.
2. این مسئلهٔ جدید باید هم‌شکلِ (به انگلیسی: یک‌ریختی) مسئلهٔ اوّل باشد.
3. سپس با استفاده از اطلاعات خود و آن عدد تصادفی، مسئلهٔ جدید را حل می‌کند.
4. ${\displaystyle P}$
   مسئلهٔ جدید را برای ${\displaystyle V}$
   ارسال می‌کند.
5. ${\displaystyle V}$
   از ${\displaystyle P}$
   می‌خواهد که یکی از دو کار زیر را انجام دهد:
   1. ثابت کند که مسئلهٔ اوّل و مسئلهٔ جدید، هم‌شکل هستند.
   2. جواب مسئلهٔ جدید را بیان کند و نشان دهد که پاسخ آن است.
6. ${\displaystyle P}$
   موافقت می‌کند و انجام می‌دهد.
7. مراحل فوق را ${\displaystyle n}$
   بار تکرار می‌کنند.

نکات

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

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

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

• موازی: به‌نحوی که ${\displaystyle P}$
  تعدادی مسئله تدوین می‌کند و برای ${\displaystyle V}$
  می‌فرستد. آن‌گاه ${\displaystyle V}$
  درخواست‌های مربوط به هر مسئله را به‌صورت یک‌جا برای ${\displaystyle P}$
  می‌فرستد. بدین‌صورت از تعداد ردوبدل شدن پیام‌ها به‌ویژه در مواردی که برقراری ارتباط با تأخیر همراه‌است، کاسته می‌شود.
• تأثیر متقابل: که در آن ${\displaystyle P}$
  و ${\displaystyle V}$
  با ردوبدل کردن متوالی پیام‌هایی، مسیر پروتکل را دنبال می‌کنند. در این حالت، اثبات به‌صورت قسمت‌به‌قسمت محقَق می‌شود.
• زمان غیر واقعی: در این حالت یک تابع دَرهَم و یک‌طرفه بر روی مسئله‌ها و داده‌ها نقش ${\displaystyle V}$
  را بازی می‌کند و برای امضای دیجیتال مورد استفاده قرار می‌گیرد.

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

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

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

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