نناقش في هذا المقال مفهوم رياضي رائد فاز الأسبوع الماضي أحد رواده بجائزة أبيل Abel Prize، التي تُعتبر جائزة نوبل في الرياضيات.
هذا المفهوم هو إثبات المعرفة الصفرية zero-knowledge proof له العديد من التطبيقات في التشفير الرقمي.
عادة في الرياضيات – وفي الحياة – عندما تريد إثبات صحة جملة ما، فأنت بحاجة إلى تقديم دليل لدعم ادعائك. مع إثبات عدم المعرفة، من الممكن إثبات صحة البيان دون الكشف عن أي معلومات داعمة.
على سبيل المثال، لنفترض أنني قمت بحل لعبة سودوكو صعبة للغاية، وأريد أن أثبت لك أنني قمت بحلها. سيقنعك دليل عدم المعرفة أنني قد قمت بحلها دون الكشف عن أي شيء على الإطلاق حول الحل الذي قدمته.
عندما ظهر إثبات عدم المعرفة لأول مرة في ثمانينيات القرن الماضي، كان المجتمع الرياضي الأوسع متعصبًا. بدت الفكرة بأكملها غريبة وغير بديهية. ومع ذلك، فقد مثلت في النهاية ثورة مفاهيمية في كيفية تفكير علماء الرياضيات في الإثبات، وتم تطبيقها في العملات المشفرة وأنظمة التشفير، حيث يرغب المستخدمون في بناء الثقة مع الحفاظ على سرية المعلومات المهمة.
مشبك الورق المسروق
أنت تعمل في مكتب يضم 100 شخص. في يوم من الأيام سُرق مشبك الورق المفضل لديك. وأنت تعلم جيداً من فعل ذلك. تخبرك زميلتك أنابيل أن لديها فكرة جيدة أيضًا.
تريد أن تتحقق مع أنابيل من أن كلاكما يشك في نفس الشخص، لكن لا أحد منكما على استعداد لتحديد المشتبه به فقط في حال كنت تفكر في أشخاص مختلفين. (بسبب سياسات المكتب، لا أحد يريد توجيه أصابع الاتهام نحو شخص بعينه).
فكر في طريقة تسمح لك ولأنابيل بالتحقق مما إذا كان المشتبه به الذي تفكر فيه والمشتبه به الذي تفكر هي فيه هو نفس الشخص، دون أن يكشف أي منكما عن أي معلومات عن المشتبه بهم.
ما يطرحه اللغز هو: هل يمكنك أنت وأنابيل الاتفاق على طريقة لمقارنة معلوماتك دون التخلي عن أي شيء؟ في نهاية “المقارنة” إما أنك ستثبت أن المشتبه بهم هم نفس الشخص، أو أنك ستثبت أنهم ليسوا كذلك. في الحالة الأخيرة، لن تكون قد سربت أي معلومات إلى أنابيل، ولن تكون قد سربت أي شيء لك. وبالتالي، فإن إجراء التحقق هو “عدم المعرفة”، حيث لا يتم إفشاء أي معرفة تمنع حقيقة أو زيف التحقق نفسه.
أوافق ، يبدو الأمر مستحيلاً!
إليك شيء واحد لا يمكنك فعله: لا يمكنك مشاركة أي شيء مع أنابيل يحدد هوية المشتبه به. لا يمكنك أن تقول على سبيل المثال: “المشتبه به يأتي في وقت متأخر يوم الاثنين”، لأن ذلك يكشف عن بعض المعلومات حول هذا الشخص.
عادةً ما أقول في عمود الكتابة “لا يوجد افشاء للاحداث” (بأحرف واضحة!). لكن اليوم مختلف لأنني أطلب منك أن تحفز عقلك للعمل بطريقة ربما لم تقم بتجربتها من قبل. وهناك العديد من الحلول ولكل منها نقاط قوة ونقاط ضعف.
إليكم إحداها: تخيل أن لديك أنت وأنابيل صديقًا جيدًا، تثق بهما كلاكما. إليك طريقة ناجحة باستخدام “دان”: الخطوة 1 توافق أنت وأنابيل على طريقة لتخصيص رقم من 1 إلى 100 لكل شخص في المكتب. الخطوة 2 اكتب رقم الشخص الذي تشك فيه على قطعة من الورق. أنابيل تفعل الشيء نفسه. الخطوة 3 سلمت إلى دان قطعتين من الورق ، واطلب منه أن يخبرك إذا كانت كلتا القطعتين لهما نفس الرقم.
إذا قال دان أن الأرقام هي نفسها، فأنت تعلم أن المشتبه بهم متماثلون. إذا كانت الأرقام مختلفة، فإن المشتبه بهم مختلفون، ولا أنت ولا أنابيل تعلكون شيئاً بشأن من يشتبه به الشخص الآخر. تم إنجاز المهمة!
ومع ذلك، فإن خيار دان ليس مثاليًا. أولاً، يعتمد على وجود دان، أي مدقق مستقل وصادق، وقد لا يكون الأمر كذلك دائمًا. والأهم من ذلك، أنكما تكشفان بعض المعلومات لدان. بيت القصيد من هذا التمرين هو عدم الكشف عن أي شيء لأي شخص. هل هناك طريقة لا تشمل أي شخص آخر؟
ذكرت في الأعلى أن جائزة أبيل 2021 كرمت أحد رواد برهان المعرفة الصفرية. اسمه آفي ويغدرسون، البالغ من العمر 64 عامًا، وحصل على الجائزة مع لازلو لوفاش البالغ من العمر 73 عامًا، “لدورهم الرائد في تشكيل [علوم الكمبيوتر النظرية والرياضيات المنفصلة] في المجالات المركزية للرياضيات الحديثة.”
في الثمانينيات أظهر ويغدرسون مع أوديد غولدريتش وسيلفيو ميكالي، أن أي بيان رياضي حقيقي له إثبات عدم المعرفة. في ذلك الوقت، كانت هذه النتيجة تقدمًا نظريًا بحتًا، ولكن في السنوات الأخيرة وجدت أدلة المعرفة الصفرية تطبيقات مهمة في الأمن الرقمي، وخاصة في أنظمة التشفير والمصادقة. يسمح إثبات المعرفة الصفرية لشخصين بتأسيس الثقة مع عدم الكشف عن أي شيء.
إذا كنت مهتمًا بمعرفة المزيد عن العمل الذي تم تكريمه بجائزة Abel 2021 ، فيمكنك الاستمتاع بهذا الفيديو القصير الذي صنعته لجائزة Abel التي تم بثها خلال حفل الإعلان. يقدم ملخصًا للشخص العادي لعمل Lovász و Wigderson و (من 4 دقائق) يقدم مثالًا لإثبات عدم المعرفة (والذي قد يكون مفيدًا في محاولة حل لغز اليوم).
تفسير إثبات المعرفة الصفرية يبدأ من الدقيقة الرابعة
Comments