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

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

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

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

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

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

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

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

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

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

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

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

1. $P$ با استفاده از اطلاعات خود و با انتخاب یک عدد تصادفی این مسئلۀ دشوار را به یک مسئلۀ دشوار جدید تبدیل می‌کند.
2. این مسئلۀ جدید باید هم‌شکلِ (به انگلیسی: یک‌ریختی) مسئلۀ اوّل باشد.
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$ مربع کامل است، به‌شرط این که از عامل‌های اوّل آن عدد بی‌خبر باشیم.
• مسئلۀ تجزیۀ یک عدد بزرگ که حاصل‌ضرب دو یا چند عدد اوّل بزرگ (صدها بیت) است.

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

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

منابع

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