تخيل أن لديك بعض المعرفة المفيدة - ربما وصفة سرية ، أو مفتاح الشفرة. هل يمكنك أن تثبت لصديق أن لديك تلك المعرفة ، دون أن تكشف عن أي شيء عنها؟ أثبت علماء الكمبيوتر منذ أكثر من 30 عامًا أنه يمكنك ، إذا استخدمت ما يسمى إثبات عدم المعرفة.
للحصول على طريقة بسيطة لفهم هذه الفكرة ، دعنا نفترض أنك تريد أن تُظهر لصديقك أنك تعرف كيفية اجتياز متاهة ، دون الكشف عن أي تفاصيل حول المسار. يمكنك ببساطة اجتياز المتاهة في غضون فترة زمنية محددة ، بينما يُمنع صديقك من المشاهدة. (يعد الحد الزمني ضروريًا لأنه إذا أعطيت الوقت الكافي ، يمكن لأي شخص أن يجد طريقه في النهاية من خلال التجربة والخطأ.) سيعرف صديقك أنه يمكنك القيام بذلك ، لكنه لن يعرف كيف.
تُعد البراهين الصفرية المعرفة مفيدة لمصممي التشفير ، الذين يتعاملون مع المعلومات السرية ، ولكن أيضًا للباحثين ذوي التعقيد الحسابي ، الذين يتعاملون مع تصنيف صعوبة المشكلات المختلفة. قال "يعتمد الكثير من التشفير الحديث على افتراضات التعقيد - على افتراض أن بعض المشكلات يصعب حلها ، لذلك كانت هناك دائمًا بعض الروابط بين العالمين" كلود كريبو، عالم كمبيوتر في جامعة ماكجيل. "لكن [هذه] البراهين خلقت عالمًا كاملاً من التواصل."
تنتمي براهين المعرفة الصفرية إلى فئة تُعرف باسم البراهين التفاعلية ، لذا لمعرفة كيفية عمل السابق ، من المفيد فهم الأخير. أولاً وصف في بحث عام 1985 من قبل علماء الكمبيوتر شافي جولدواسر، سيلفيو ميكالي وتشارلز راكوف ، تعمل البراهين التفاعلية مثل الاستجواب: عبر سلسلة من الرسائل ، يحاول أحد الطرفين (المدقق) إقناع الطرف الآخر (المدقق) بأن بيانًا معينًا صحيحًا. يجب أن يلبي الدليل التفاعلي خاصيتين. أولاً ، البيان الصحيح سيقنع دائمًا في النهاية المحقق الصادق. ثانيًا ، إذا كانت العبارة المعطاة خاطئة ، فلا يمكن لأي مُثبِّت - حتى من يتظاهر بامتلاك معرفة معينة - إقناع المدقق ، إلا باحتمالية ضئيلة جدًا.
البراهين التفاعلية احتمالية بطبيعتها. يستطيع المُثبِّت الإجابة على سؤال أو سؤالين بشكل صحيح بمجرد الحظ ، لذلك يتطلب الأمر عددًا كبيرًا بما يكفي من التحديات ، وكلها يجب على المُثبِّت أن يكون صحيحًا ، حتى يصبح المُحقق واثقًا من أن المُثِّل يعرف في الواقع أن العبارة صحيحة.
جاءت فكرة التفاعلات هذه عندما حير Micali و Goldwasser - ثم خريجو جامعة كاليفورنيا ، بيركلي - من خلال الخدمات اللوجستية للعب البوكر عبر شبكة. كيف يمكن لجميع اللاعبين التحقق من أنه عندما يحصل أحدهم على بطاقة من المجموعة الافتراضية ، تكون النتيجة عشوائية؟ البراهين التفاعلية يمكن أن تقود الطريق. ولكن بعد ذلك ، كيف يمكن للاعبين التحقق من أن البروتوكول بأكمله - مجموعة القواعد الكاملة - تم اتباعه بشكل صحيح ، دون الكشف عن يد كل لاعب على طول الطريق؟
لتحقيق هذا الهدف ، أضاف ميكالي وجولدفاسر خاصية ثالثة إلى الاثنين المطلوبين لإثبات تفاعلي: يجب ألا يكشف الدليل شيئًا عن المعرفة نفسها ، فقط صدق البيان. قال Goldwasser: "هناك فكرة عن اتباع بروتوكول ، وفي نهايته تعتقد أن [لاعبي البوكر] لا يعرفون أي شيء أكثر مما يفترض بهم أن يعرفوه".
لنفكر في المثال الكلاسيكي. تريد أليس أن تثبت لبوب أن رسمًا بيانيًا معينًا G - مجموعة فريدة من الرؤوس (النقاط) المتصلة بالحواف (الخطوط) - لها "دورة هاميلتونية". هذا يعني أن الرسم البياني يحتوي على مسار يزور كل نقطة مرة واحدة بالضبط وينتهي عند نفس النقطة التي بدأ منها. يمكن لأليس القيام بذلك ببساطة عن طريق إظهار بوب المسار الذي يقوم بذلك ، ولكن بالطبع بعد ذلك سيعرف المسار أيضًا.
إليك كيف يمكن لأليس أن تقنع بوب بأنها تعرف أن مثل هذا المسار موجود ، دون أن تظهره له. أولاً ، ترسم رسمًا بيانيًا جديدًا ، H، هذا لا يبدو G لكنها متشابهة بطريقة حاسمة: لها نفس عدد الرؤوس ، متصلة بنفس الطرق. (إذا G بالفعل دورة هاميلتونية ، وهذا التشابه يعني H سوف أيضا.) ثم ، بعد تغطية كل حافة في H بشريط لاصق ، تقفل H في صندوق ويعطي الصندوق لبوب. هذا يمنعه من رؤيته مباشرة ولكنه يمنعه أيضًا من تغييره. ثم يتخذ بوب خيارًا: إما أن يطلب من أليس إظهار ذلك H حقا مشابه ل G، أو يمكنه أن يطلب منها أن تظهر له دورة هاميلتون في H. كلا الطلبين يجب أن يكون سهلاً لأليس ، بافتراض ذلك H حقا مشابه بما فيه الكفاية ل G، وأنها تعرف الطريق حقًا.
بالطبع ، حتى لو لم تكن أليس تعرف دورة هاميلتون G، يمكنها محاولة خداع بوب ، إما عن طريق رسم رسوم بيانية لا تشبه G، أو بإرسال الرسوم البيانية ، فهي لا تعرف مسارها. ولكن بعد أن لعبوا عدة جولات ، فإن فرصة أليس لخداع بوب في كل مرة تصبح ضئيلة للغاية. إذا فهمت كل شيء بشكل صحيح ، فسيقتنع بوب في النهاية بأن أليس تعرف دورة هاميلتونية في الرسم البياني G، دون أن يراه بوب على الإطلاق.
بعد الورقة الأولية التي وصفت مثل هذه البراهين لأول مرة ، اكتشف ميكالي واثنان من علماء الرياضيات - أوديد غولدريتش وآفي ويغدرسون - نتيجة غير متوقعة ذات تأثيرات بعيدة المدى. يتعلق الأمر بفئة رئيسية من المشكلات ذات الصعوبة المتساوية تقريبًا ، والمعروفة باسم NP. يصعب حل هذه المشكلات ، لكن من السهل التحقق من حلولها. الباحثون الثلاثة وجدت أن، إذا كان التشفير آمنًا حقًا ممكن، ثم يمكن أيضًا إثبات حل كل مشكلة في NP بإثبات المعرفة الصفرية. ساعدت هذه الدراسة الباحثين تصور المتغيرات من براهين المعرفة الصفرية التي لا تتطلب حتى تشفيرًا آمنًا في المقام الأول ؛ تُعرف هذه البراهين التفاعلية متعددة الأمثال.
وفي عام 1988 ، ميكالي وآخرون أظهرت أنه إذا كان المُثبِت والمحقق يشتركان في سلسلة قصيرة من البتات العشوائية ، فلا داعي للتفاعل. هذا يعني من الناحية النظرية أن براهين عدم المعرفة الصفرية لا يجب أن تكون تفاعلية ، مما يعني أن التواصل المستمر بين طرفين ليس ضروريًا. هذا من شأنه أن يجعلها أكثر فائدة للباحثين ، ولكن لم تنتشر مثل هذه البراهين إلا بعد نهاية القرن الحادي والعشرين.
قال: "في أواخر العقد الأول من القرن الحادي والعشرين ، بدأنا نشهد تطور التقنيات الفعالة لبناء براهين انعدام المعرفة" ماثيو د، عالم التشفير في جامعة جون هوبكنز. "لقد وصلنا إلى النقطة التي أدركنا فيها ،" انتظر لحظة ، قد تكون هناك بالفعل طريقة لاستخدام هذا في الممارسة. "
الآن يمكن للمثبت إرسال رسالة واحدة إلى المدقق دون الحاجة إلى أن يكون كلاهما متصلاً بالإنترنت ، ويمكن للباحثين إنشاء دليل قصير جدًا يمكن التحقق منه بسرعة ، حتى بالنسبة للمشكلات المعقدة للغاية. وقد أدى ذلك إلى العديد من الاستخدامات العملية ، مثل القدرة على التحقق بسرعة من blockchain بعد معاملة عملة مشفرة مع إخفاء تفاصيل المعاملة. وفي عام 2016 ، قامت مجموعة من الفيزيائيين أظهرت كيف يمكن لأدلة عدم المعرفة أن تساعد في نزع السلاح النووي: بدون الكشف عن أي سر حول تصميم رأسها الحربي النووي ، يمكن لأي بلد الآن أن يثبت للمفتشين النوويين ما إذا كان الرأس الحربي نشطًا أم غير نشط.
في الآونة الأخيرة ، أجبرت التطورات في الحوسبة الكمومية Crépeau على اختبار الإجهاد السابق للتأكد من أن بروتوكولات المعرفة الصفرية لا تزال قابلة للتطبيق. في عام 2021 ، ساعد شرح أن البراهين التفاعلية متعددة الأمثال تحتفظ بسريتها حتى عندما تكون أجهزة الكمبيوتر الكمومية متورطة ، لكن تحقيق نفس المستوى من الأمان يجعل البروتوكول أبطأ بكثير. وقال إن النتيجة كانت أخبارًا جيدة ، لكن مخاوف جديدة ستنشأ مع تقدم التكنولوجيا.
قال كريبو: "كل نوع من العمليات الحسابية التي قد نقوم بها في المستقبل سوف تشمل أجهزة الكمبيوتر الكمومية". "لذا بصفتنا مصممين مشفرين جيدين مصابين بجنون العظمة ، كلما قمنا بتقييم أمان النظام ، نريد التأكد من أن نظامنا آمن."
ملاحظة المحرر: تلقى شافي جولدواسر تمويلًا من مؤسسة Simons ، التي تمول هذا أيضًا منشور مستقل تحريري. لا تؤثر قرارات تمويل مؤسسة Simons على تغطيتنا.
