افتراضات الصلابة الحسابية
افتراضات الصلابة الحسابية هي تخمينات غير مُبرهنة ولكنها مدروسة جيدًا — مثل صعوبة التحليل إلى عوامل، واللوغاريتمات المنفصلة، ومسائل الشبكة — التي يستند إليها أمن المخططات التشفيرية في نهاية المطاف.
Definition
افتراض الصلابة الحسابية هو تخمين بأن مشكلة حسابية معينة لا يمكن حلها بكفاءة (في زمن متعدد الحدود) بواسطة أي خصم واقعي، وهو بمثابة الأساس الذي يُبنى عليه الأمان القابل للإثبات.
Scope
يغطي هذا الموضوع الافتراضات التي يعتمد عليها التشفير: وجود دوال أحادية الاتجاه، ومسائل نظرية الأعداد (التحليل إلى عوامل، RSA، اللوغاريتم المنفصل)، ومسائل الشبكة والترميز المستخدمة في التشفير ما بعد الكمومي. ويتناول التسلسل الهرمي بين الافتراضات، والتمييز بين الصلابة في أسوأ الحالات ومتوسط الحالات، وكيفية فحص الافتراضات. ويستثني آليات الاختزال التي تربط الافتراضات بالمخططات وتعريفات الأمان نفسها، والتي تُعالج في مواضيع ذات صلة.
Core questions
- لماذا يجب أن يستند الأمن التشفيري إلى افتراضات صلابة غير مُبرهنة؟
- ما هي الافتراضات الرئيسية (الدوال أحادية الاتجاه، التحليل إلى عوامل، اللوغاريتم المنفصل، الشبكات)؟
- كيف ترتبط الافتراضات ببعضها البعض من حيث القوة؟
- ما الفرق بين الصلابة في أسوأ الحالات ومتوسط الحالات؟
- كيف يتم فحص المسائل الصعبة المرشحة، وماذا يحدث عندما يفشل أحدها؟
Key concepts
- دالة أحادية الاتجاه
- دالة الباب الخلفي
- افتراض تحليل الأعداد الصحيحة
- افتراض اللوغاريتم المنفصل
- افتراضات RSA ودي في-هيلمان
- التعلم مع الأخطاء (LWE)
- الصلابة في أسوأ الحالات مقابل متوسط الحالات
- P مقابل NP
- التسلسل الهرمي للافتراضات
Key theories
- الدوال أحادية الاتجاه كافتراض أدنى
- إن وجود الدوال أحادية الاتجاه — سهلة الحساب، صعبة العكس — ضروري وكافٍ للكثير من التشفير المتماثل وهو الافتراض الأساسي؛ تقريبًا كل التشفير يفترض هذا على الأقل.
- افتراضات نظرية الأعداد والشبكة
- يعتمد التشفير بالمفتاح العام على مسائل منظمة — تحليل الأعداد الصحيحة، ومسألة RSA، واللوغاريتمات المنفصلة (كلاسيكيًا)، والتعلم مع الأخطاء ومسائل المتجه الأقصر في الشبكات (ما بعد الكمومي) — وكل منها مدعوم بعقود من التدقيق التحليلي التشفيري.
Mechanisms
يحتاج التشفير إلى مسائل صعبة في المتوسط (على حالات عشوائية)، وليس فقط في أسوأ الحالات، نظرًا لأن المفاتيح تُختار عشوائيًا. تُنظّم الافتراضات في تسلسل هرمي تقريبي: غالبًا ما يؤدي كسر افتراض أضعف (مثل التحليل إلى عوامل) إلى كسر المخططات المبنية عليه، بينما تربط الاختزالات الافتراضات ببعضها البعض. تُعرف افتراضات الشبكة باختزالات أسوأ الحالات إلى متوسط الحالات، مما يمنح ثقة أقوى. تأتي الثقة في أي افتراض من الجهد المستمر والفاشل في التحليل التشفيري بدلاً من البرهان.
Clinical relevance
تحدد افتراضات الصلابة ما هو آمن وما هو غير آمن للنشر. أدى اكتشاف أن أجهزة الكمبيوتر الكمومية ستكسر التحليل إلى عوامل واللوغاريتمات المنفصلة (عبر خوارزمية شور) إلى إبطال الافتراضات الكامنة وراء RSA وتشفير المنحنيات الإهليلجية ضد الخصوم الكموميين، مما دفع مباشرة إلى الانتقال إلى معايير ما بعد الكمومية القائمة على الشبكة. يعد اختيار المخططات المبنية على افتراضات مدروسة جيدًا، وتتبع حالتها، أمرًا ضروريًا للأمن طويل الأجل.
Evidence & guidelines
تفضل هيئات المعايير الافتراضات ذات السجلات الطويلة في التحليل التشفيري؛ وقد قامت عملية NIST لما بعد الكمومية بتقييم صريح لنضج وثقة افتراضات الشبكة والترميز والتجزئة الأساسية. تتجنب أفضل الممارسات الافتراضات الغريبة أو المقترحة حديثًا للأنظمة عالية الضمان وتفضل المسائل المحافظة والمُختبرة جيدًا، مع تحديد أحجام المفاتيح لمواجهة أفضل الهجمات المعروفة.
History
ظهر الاعتماد على الصلابة مع التشفير بالمفتاح العام في عام 1976، عندما ربط ديفي وهيلمان الأمان باللوغاريتم المنفصل، و RSA بالتحليل إلى عوامل. في الثمانينيات، تم إضفاء الطابع الرسمي على الدوال أحادية الاتجاه والتمييز بين أسوأ الحالات ومتوسط الحالات. أدت اختزالات أسوأ الحالات إلى متوسط الحالات لأجتاي (1996) ومسألة التعلم مع الأخطاء لريجيف (2005) إلى ترسيخ افتراضات الشبكة، والتي اكتسبت أهمية كأسس مقاومة للكموم وتدعم المعايير الجديدة لما بعد الكمومية.
Key figures
- Whitfield Diffie
- Martin Hellman
- Oded Goldreich
- Oded Regev
- Andrew Yao
Related topics
Seminal works
- diffie1976
- goldreich2001
- katz2020
Frequently asked questions
- لماذا لا يمكننا ببساطة إثبات أن هذه المسائل صعبة؟
- إثبات أن مسألة تتطلب وقتًا فوق متعدد الحدود سيحل مسائل مفتوحة عميقة في نظرية التعقيد (وأبرزها P مقابل NP)، والتي لا تزال دون حل. لذا يعتمد التشفير على افتراضات تأتي معقوليتها من عقود من المحاولات الفاشلة لحلها بكفاءة.
- ماذا يحدث إذا تم كسر افتراض صلابة؟
- يصبح كل مخطط يعتمد أمانه على هذا الافتراض غير آمن محتملاً ويجب استبداله. هذا هو السبب في أن التهديد الكمومي للتحليل إلى عوامل واللوغاريتمات المنفصلة دفع إلى هجرة عالمية نحو مخططات مبنية على افتراضات مختلفة ومقاومة للكموم.