اثبات دانایی صفر یا پروتکل دانایی صفر در رمزنگاری روشی است که طرف (اثباتکننده) میتواند به طرف (تصدیقکننده) ثابت کند بیانیهی ارائهشده صحیح است. این روش فقط صحت بیانیه را تصدیق میکند و هیچ اطلاعات اضافهای را بجز این حقیقت که بیانیه واقعاً صحت دارد ارسال نمیکند.
ما معمولاً در ریاضی و یا حتی زندگی واقعی میخواهیم چیزهایی را به دیگران تفهیم کنیم. برای نمونه، من میدانم درست است و اگر بخواهم شما را هم قانع کنم که
درست است، سعی میکنم تمامیِ حقایقی که میدانم و همچنین نتایجِ ضمنی که درست بودن
را نشان میدهد برایتان رو کنم.
اثباتکننده () سعی میکند تصدیقکننده (
) را متقاعد کند که ادعایش صحیح است. در حالت عادی،
در این ارتباط یکسری اطلاعات به
میدهد و
با انجام محاسباتی صحت ادعای
را میپذیرد. آیا میتوان بدون انتقال اطلاعات مهم،
را متقاعد کرد؟ آیا میتوان پیامهای بیشتری رَدوبَدل کرد و در عینحال اطلاعات را حفظ کرد؟ آیا میتوان با درنظر گرفتن احتمال خطای غیر صفر و با انتقال حداقل اطلاعات مفید،
را قانع نمود؟
آلیس باید باب را قانع کند که درست است، امّا طوریکه باب نتواند اطلاعات دیگری خارج از فرآیند قانع شدن از آلیس بهدست آورد. یعنیباب دانایی صفر را بهدست میآورد.
در یک اثبات، هنگامی که منظور اصلی، بدون هیچ اطلاعات اضافی منتقل شود (واقعیتی برای طرف مقابل آشکار میشود) که بهآن اثبات با دانایی صفر میگوییم. در این نوع اثبات، متقاعد میشود که
صاحب اطلاعاتی است، اما بههیچ طریقی نمیتواند این اطلاعات را استخراج کند. در یک پروتکل دانایی–صفر میتوان کارهایی از قبیل شناسایی، اثبات یک واقعیت یا دیگر عملیات رمزنگاری را، بدون فاشکردن اطلاعات محرمانه در هنگام برقراری ارتباط، انجام داد.
من میدانم ۲۶۷۸۱ یک عدد اوّل نیست، و برای اثبات، دو فاکتور آن را به دست میآورم: ۱۱۳*۲۳۷
در اثبات دانایی صفر، شما تلاش میکنید به فرد دیگری بقبولانید که ۲۶۷۸۱ یک عدد اول نیست و در عینحال نمیخواهید دو فاکتور اول آنرا هم برایش آشکار کنید.
فرض کنید حل یک مسئلهی دشوار را میداند. برای اثبات این آگاهی بهصورت زیر عمل مینماید:
نکات
- در این الگوریتم،
هیچگاه نباید برای مسئلهی دشوار جدیدی که بهدست میآورد هردو درخواست بند (۵) را پاسخ دهد.
- تبدیلهای تصادفی و مسئلهها نیز باید بهگونهی مناسبی انتخاب شوند تا
اطلاعاتی برای حل مسئلهی اصلی بهدست نیاورد.
- همهی مسائل دشوار برای این کاربرد مناسب نیستند. اما تعداد زیادی از این مسائل میتوانند استفاده شوند.
برای استفاده از پروتکلهای دانایی صفر به سه طریق زیر میتوان عمل نمود:
اثبات دانایی صفر توسط گلدواسر میکالی و راکف در سال ۱۹۸۲ معرفی شد. مقالهٔ آنها به یکی از زیباترین و تأثیر گذارترین مفاهیم در علوم کامپیوتر تبدیل شد که دامنهٔ وسیعی از کاربردها از اسکیمهای امضاء تا اثبات اینکه بسیاری از مسائل ان-پی حتی در مرحلهی تخمین نیز بسیار دشوار هستند را شامل میشود.