أوراكل عشوائي

📅 آخر تحديث: ٢٤ يوليو ٢٠٢٦
✍️ نُشر في: ٢٤ يوليو ٢٠٢٦
الموسوعة الحرة

في علم التشفير ، يُعرف "الوسيط العشوائي" بأنه وسيط ( صندوق أسود نظري ) يستجيب لكل استعلام فريد باستجابة عشوائية (حقيقية) مختارة بشكل منتظم من نطاق مخرجاته. إذا تكرر الاستعلام، فإنه يستجيب بنفس الطريقة في كل مرة يُرسل فيها.

وبعبارة أخرى، فإن أوراكل العشوائي هو دالة رياضية يتم اختيارها بشكل عشوائي منتظم، أي دالة تربط كل استعلام ممكن باستجابة عشوائية (ثابتة) من مجال الإخراج الخاص بها.

ظهرت أوراكل العشوائية لأول مرة في سياق نظرية التعقيد، حيث استُخدمت للتأكيد على أن تصنيفات فئات التعقيد قد تواجه عوائق نسبية، وأبرز مثال على ذلك مشكلة P مقابل NP ، وهما فئتان ثبت في عام 1981 أنهما متميزتان بالنسبة لأوراكل عشوائي بشكل شبه مؤكد . [ 1 ] ثم دخلت هذه الأوراكل إلى علم التشفير من خلال نشر ميهير بيلار وفيليب روغاواي في عام 1993، حيث قدّماها كنموذج تشفير رسمي يُستخدم في براهين الاختزال. [ 2 ]

تُستخدم هذه الأساليب عادةً عندما يتعذر إثبات الأمان باستخدام افتراضات أضعف على دالة التجزئة التشفيرية . يُوصف النظام الذي يُثبت أمانه عند استبدال كل دالة تجزئة بمفتاح عشوائي بأنه آمن في نموذج المفتاح العشوائي ، وهو ما يختلف عن كونه آمنًا في النموذج القياسي للتشفير .

التطبيقات

تُستخدم مُستَخدِمات التنبؤ العشوائية عادةً كبديل مثالي لدوال التجزئة التشفيرية في الأنظمة التي تتطلب افتراضات قوية للعشوائية في مُخرجات دالة التجزئة. يُظهر هذا النوع من البراهين غالبًا أن النظام أو البروتوكول آمن من خلال إثبات أن المُهاجم سيحتاج إلى سلوك مُستحيل من المُستَخدِم، أو حل مسألة رياضية بالغة الصعوبة لاختراقه. مع ذلك، فهو يُثبت هذه الخصائص فقط في نموذج مُستَخدِمات التنبؤ العشوائية، ما يضمن عدم وجود عيوب تصميمية جوهرية. ليس صحيحًا عمومًا أن هذا البرهان يُشير إلى نفس الخصائص في النموذج القياسي. ومع ذلك، يُعتبر البرهان في نموذج مُستَخدِمات التنبؤ العشوائية أفضل من عدم وجود أي برهان أمني رسمي على الإطلاق. [ 3 ]

لا تتطلب جميع استخدامات وظائف التجزئة المشفرة أوراكل عشوائية: يمكن في كثير من الأحيان إثبات أمان المخططات التي تتطلب خاصية واحدة أو أكثر لها تعريف في النموذج القياسي (مثل مقاومة التصادم ، ومقاومة الصورة الأصلية ، ومقاومة الصورة الأصلية الثانية ، وما إلى ذلك) في النموذج القياسي (على سبيل المثال، نظام التشفير Cramer-Shoup ).

لطالما حظيت أنظمة التنبؤ العشوائي باهتمام كبير في نظرية التعقيد الحسابي ، [ 4 ] وقد ثبت أمان العديد من المخططات في نموذج التنبؤ العشوائي، مثل التشفير الأمثل غير المتماثل ، و RSA-FDH، و PSS . في عام 1986، قدم آموس فيات وآدي شامير [ 5 ] تطبيقًا رئيسيًا لأنظمة التنبؤ العشوائي، وهو إزالة التفاعل من بروتوكولات إنشاء التوقيعات.

في عام ١٩٨٩، استخدم راسل إمباغليازو وستيفن روديتش [ ٦ ] أوراكل عشوائية لإثبات وجود فصل بين الدوال أحادية الاتجاه وتبادل المفاتيح السرية، وذلك من خلال عرض أوراكل تُحدد فيه الدوال أحادية الاتجاه، بينما لا يُحدد فيه تبادل المفاتيح السرية - وبالتالي التشفير بالمفتاح العام . تُظهر نتائجهم أنه لا يوجد بناء مُبهم للتشفير بالمفتاح العام انطلاقًا من الدوال أحادية الاتجاه، مما يُشير إلى أن الدوال أحادية الاتجاه تُعدّ فرضية أضعف من التشفير بالمفتاح العام.

في عام 1993، كان ميهير بيلاري وفيليب روغاواي [ 2 ] أول من دعا إلى استخدامها في البنى التشفيرية. ووفقًا لتعريفهما، ينتج جهاز التنبؤ العشوائي سلسلة بتات ذات طول لانهائي يمكن اقتطاعها إلى الطول المطلوب.

عند استخدام أوراكل عشوائي ضمن دليل أمني، فإنه يصبح متاحًا لجميع اللاعبين، بما في ذلك الخصم أو الخصوم.

فصل النطاقات

يمكن التعامل مع وسيط واحد على أنه عدة وسائط بإضافة سلسلة بتات ثابتة في بداية كل استعلام (على سبيل المثال، يمكن اعتبار الاستعلامات المنسقة كـ "1||x" أو "0||x" بمثابة استدعاءات لوسيطين عشوائيين منفصلين، وبالمثل، يمكن استخدام "00||x" و"01||x" و"10||x" و"11||x" لتمثيل استدعاءات لأربعة وسائط عشوائية منفصلة). تُعرف هذه الممارسة عادةً بفصل النطاقات . استنساخ الوسيط هو إعادة استخدام الوسيط العشوائي الذي تم إنشاؤه مرة واحدة ضمن نفس البرهان (وهذا عمليًا يُقابل استخدامات متعددة لنفس التجزئة المشفرة ضمن خوارزمية واحدة لأغراض مختلفة). [ 7 ] يؤدي استنساخ الوسيط مع فصل غير سليم للنطاقات إلى كسر براهين الأمان، وقد يؤدي إلى هجمات ناجحة. [ 8 ]

القيود

وفقًا لأطروحة تشيرش-تورينج ، لا يمكن لأي دالة قابلة للحساب بواسطة خوارزمية محدودة أن تنفذ أوراكل عشوائي حقيقي (والذي يتطلب بحكم التعريف وصفًا لانهائيًا لأنه يحتوي على عدد لا نهائي من المدخلات الممكنة، ومخرجاته كلها مستقلة عن بعضها البعض وتحتاج إلى تحديدها بشكل فردي بواسطة أي وصف).

في الواقع، توجد بعض أنظمة التوقيع والتشفير المصطنعة التي ثبت أمانها في نموذج أوراكل العشوائي، ولكنها غير آمنة بشكل واضح عند استبدال أوراكل العشوائي بأي دالة حقيقية. [ 9 ] [ 10 ] ومع ذلك، بالنسبة لأي بروتوكول أكثر طبيعية، فإن إثبات الأمان في نموذج أوراكل العشوائي يُقدم دليلاً قوياً جداً على الأمان العملي للبروتوكول. [ 11 ]

بشكل عام، إذا ثبت أمان بروتوكول ما، فإن الهجمات عليه إما أن تكون خارج نطاق ما تم إثباته، أو أن تنتهك أحد افتراضات البرهان؛ على سبيل المثال، إذا كان البرهان يعتمد على صعوبة تحليل الأعداد الصحيحة إلى عواملها الأولية ، فإن انتهاك هذا الافتراض يتطلب اكتشاف خوارزمية سريعة لتحليل الأعداد الصحيحة إلى عواملها الأولية. في المقابل، لانتهاك افتراض أوراكل العشوائية، يجب اكتشاف خاصية غير معروفة وغير مرغوب فيها لدالة التجزئة الفعلية؛ بالنسبة لدوال التجزئة الجيدة التي يُعتقد أن مثل هذه الخصائص غير محتملة، يمكن اعتبار البروتوكول المدروس آمنًا.

فرضية أوراكل العشوائي

على الرغم من أن نظرية بيكر-جيل-سولوفاي [ 12 ] أثبتت وجود وسيط A بحيث يكون P A = NP A ، فقد أظهر عمل لاحق لبينيت وجيل [ 13 ] أنه بالنسبة لوسيط عشوائي B (دالة من {0,1} إلى {0,1} بحيث يتم تعيين كل عنصر إدخال إلى 0 أو 1 باحتمالية 1/2، بشكل مستقل عن تعيين جميع المدخلات الأخرى)، فإن P B ⊊ NP B باحتمالية 1. أدت عمليات الفصل المماثلة، بالإضافة إلى حقيقة أن الوسائط العشوائية تفصل الفئات باحتمالية 0 أو 1 (كنتيجة لقانون كولموغوروف للصفر والواحد )، إلى إنشاء فرضية الوسيط العشوائي ، التي تنص على أن فئتي التعقيد "المقبولتين" C1 و C2 متساويتان إذا وفقط إذا كانتا متساويتين (باحتمالية 1) في ظل وسيط عشوائي (تم تعريف مقبولية فئة التعقيد في BG81 [ 13 ] ). وقد تبين لاحقًا أن هذه الفرضية خاطئة، حيث تبين أن فئتي التعقيد المقبولتين IP و PSPACE متساويتان [ 14 ] على الرغم من أن IP A ⊊ PSPACE A بالنسبة لأوراكل عشوائي A باحتمالية 1. [ 15 ]

التشفير المثالي

التشفير المثالي هو نموذج تبديل عشوائي يُستخدم لمحاكاة تشفير الكتل المثالي. يقوم التبديل العشوائي بفك تشفير كل كتلة نص مشفر إلى كتلة نص عادي واحدة فقط، والعكس صحيح، مما يُحقق تطابقًا تامًا . بعض البراهين التشفيرية لا تُتيح التبديل "الأمامي" فقط لجميع اللاعبين، بل تُتيح أيضًا التبديل "العكسي".

أظهرت الأعمال الحديثة أنه يمكن إنشاء تشفير مثالي من أوراكل عشوائي باستخدام شبكات فيستل ذات 10 جولات [ 16 ] أو حتى 8 جولات [ 17 ] .

التبديل المثالي

التبديل المثالي هو كائن مثالي يُستخدم أحيانًا في علم التشفير لنمذجة سلوك تبديل لا يمكن تمييز مخرجاته عن مخرجات التبديل العشوائي. في نموذج التبديل المثالي، يُمنح وصول إضافي إلى التبديل المثالي ومعكوسه. ويمكن اعتبار نموذج التبديل المثالي حالة خاصة من نموذج التشفير المثالي، حيث يُمنح الوصول إلى تبديل واحد فقط، بدلًا من مجموعة من التبديلات كما في حالة نموذج التشفير المثالي.

أوراكل عشوائية يمكن الوصول إليها كمياً

تدرس التشفير ما بعد الكمومي الهجمات الكمومية على أنظمة التشفير الكلاسيكية. وبما أن أوراكل عشوائي هو تجريد لدالة التجزئة ، فمن المنطقي افتراض أن المهاجم الكمومي يستطيع الوصول إلى أوراكل عشوائي في حالة التراكب الكمومي . [ 18 ] تنهار العديد من براهين الأمان الكلاسيكية في نموذج أوراكل عشوائي الكمومي هذا، وتحتاج إلى مراجعة.

انظر أيضاً

مراجع

  1. ↑ بينيت، تشارلز؛ جيل، جون (1981). "بالنسبة إلى أوراكل عشوائي A،  فإن N^A ≠ NP^A  ≠ coNP^A باحتمالية 1" . مجلة SIAM للحوسبة : 96-113 . doi : 10.1137/0210008 .
  2. 1 2 بيلاري، ميهير ؛ روغاواي، فيليب (1993). "الوسائط العشوائية عملية: نموذج لتصميم بروتوكولات فعالة". وقائع المؤتمر الأول لجمعية ACM حول أمن الحاسوب والاتصالات - CCS '93 . الصفحات 62-73 . doi : 10.1145/168588.168596 . ISBN  0-89791-629-8. S2CID 3047274 . 
  3. ↑ كاتز، جوناثان؛ ليندل، يهودا (2015). مقدمة في علم التشفير الحديث ( الطبعة الثانية). بوكا راتون: تشابمان آند هول/سي آر سي. الصفحات 174-175 ، 179-181 . ISBN   978-1-4665-7027-6.
  4. ↑ بينيت، تشارلز هـ .؛ جيل، جون (1981)، "بالنسبة إلى أوراكل عشوائي A، فإن P^A != NP^A != co-NP^A باحتمالية 1"، مجلة SIAM للحوسبة ، 10 (1): 96-113 ، doi : 10.1137/0210008 ، ISSN 1095-7111   
  5. ↑ فيات، آموس؛ شامير، آدي (1986). "كيفية إثبات نفسك: حلول عملية لمشاكل تحديد الهوية والتوقيع". كريبتو . ص 186-194 . 
  6. ↑ إمباغليازو، راسل؛ روديتش، ستيفن (1989). "حدود النتائج القابلة للإثبات للتباديل أحادية الاتجاه". STOC : 44-61 .
  7. ^ بيلاري وديفيز وغونتر 2020 ، ص. 3.
  8. ^ بيلاري وديفيز وغونتر 2020 ، ص. 4.
  9. ↑ ران كانيتي، أوديد غولدريتش وشاي هاليفي، إعادة النظر في منهجية أوراكل العشوائي، STOC 1998، ص 209-218 (PS وPDF) .
  10. ↑ كريج جينتري وذو الفقار رمضان. "التخلص من أوراكل التبديل العشوائي في شيفرة إيفن-منصور" . 2004.
  11. ↑ كوبليتز، نيل؛ مينيزيس، ألفريد ج. (2015). "نموذج أوراكل العشوائي: نظرة استرجاعية على مدى عشرين عامًا" (ملف PDF) . نظرة أخرى . مؤرشف من الأصل (ملف PDF) في 2 أبريل 2015. تم الاطلاع عليه في 6 مارس 2015 .
  12. ↑ بيكر، ثيودور؛ جيل، جون؛ سولوفاي، روبرت (1975). "نسبية مسألة P = ؟ NP". مجلة SIAM للحوسبة 4 ( 4). SIAM: 431– 442. doi : 10.1137/0204037 .
  13. 1 2 بينيت، تشارلز؛ جيل، جون (1981). "بالنسبة إلى أوراكل عشوائي A، فإن P ≠ NP ≠ co-NP باحتمالية 1". مجلة SIAM للحوسبة 10 ( 1). SIAM: 96-113 . doi : 10.1137/0210008 .  
  14. ↑ شامير، عدي (أكتوبر 1992). "IP = PSPACE" . مجلة ACM . 39 (4): 869-877 . doi : 10.1145/146585.146609 . S2CID 315182 . 
  15. ↑ تشانغ، ريتشارد؛ تشور، بيني ؛ غولدريتش، أوديد؛ هارتمانيس، جوريس؛ هاستاد، يوهان؛ رانجان، ديش؛ روهاتجي، بانكاج (أغسطس 1994). "فرضية أوراكل العشوائي خاطئة" . مجلة علوم الحاسوب والأنظمة . 49 (1): 24-39 . doi : 10.1016/S0022-0000(05)80084-4 . ISSN 0022-0000 . 
  16. ↑ داشمان-سوليد، دانا؛ كاتز، جوناثان؛ ثيروفينغادام، أيشواريا (2016). "تشفير فيستل ذو العشر جولات لا يمكن تمييزه عن التشفير المثالي". مؤتمر يورو كريبت 2016. سبرينغر. الصفحات 649-678 . doi : 10.1007/978-3-662-49896-5_23 . 
  17. ↑ داي، يوانشي؛ شتاينبرغر، جون (2016). "عدم التمييز بين شبكات فيستل ذات 8 جولات". CRYPTO 2016. سبرينغر.
  18. ↑ دان بونيه، أوزغور داغديلين، مارك فيشلين، أنيا ليمان، كريستيان شافنر، ومارك زاندري (2011). "التنبؤات العشوائية في عالم الكم". التطورات في علم التشفير - ASIACRYPT 2011. سلسلة محاضرات في علوم الحاسوب. المجلد 7073. سبرينغر. الصفحات 41-69 . arXiv : 1008.0931 . doi : 10.1007/978-3-642-25385-0_3 . ISBN   978-3-642-25384-3.{{cite conference}}: صيانة CS1: أسماء متعددة: قائمة المؤلفين ( رابط )

مصادر