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

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