عائلة الدوال شبه العشوائية

في علم التشفير ، تُعرف عائلة الدوال شبه العشوائية ، ويُرمز لها اختصارًا بـ PRF ، بأنها مجموعة من الدوال القابلة للحساب بكفاءة عالية ، والتي تُحاكي مُستَخدِمًا عشوائيًا على النحو التالي: لا تستطيع أي خوارزمية فعّالة التمييز (بفارق كبير ) بين دالة مُختارة عشوائيًا من عائلة PRF ومُستَخدِم عشوائي (دالة تكون مُخرجاتها ثابتة تمامًا بشكل عشوائي). تُعدّ الدوال شبه العشوائية أدوات أساسية في بناء العناصر التشفيرية الأولية ، وخاصة أنظمة التشفير الآمنة .

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

يمكن إنشاء عائلة دوال شبه عشوائية من أي مولد شبه عشوائي، باستخدام، على سبيل المثال، بنية "GGM" التي قدمها غولدريتش ، وغولدواسير ، وميكالي . ^{[ 1 ]} في حين أن تشفيرات الكتل تُستخدم عمليًا في معظم الحالات التي تتطلب دالة شبه عشوائية، إلا أنها لا تُشكل، بشكل عام، عائلة دوال شبه عشوائية، لأن تشفيرات الكتل مثل AES مُعرَّفة لعدد محدود فقط من أحجام المدخلات والمفاتيح. ^{[ 2 ]}

الدالة العشوائية الزائفة هي دالة فعالة (أي قابلة للحساب في وقت متعدد الحدود)، وحتمية، تقوم برسم مجموعتين متميزتين (المجال والمدى) وتبدو كدالة عشوائية حقيقية.

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

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

تأخذ الدوال شبه العشوائية مدخلات${\displaystyle x\in \{0,1\}^{*}}$، أين${\displaystyle {}^{*}}$هي نجمة كلين . حجم الإدخال${\displaystyle I=|x|}$وحجم الإخراج${\displaystyle \lambda }$يعتمد فقط على حجم الفهرس${\displaystyle n:=|s|}$.

مجموعة من الدوال،

${\displaystyle f_{s}:\left\{0,1\right\}^{I(n)}\rightarrow \left\{0,1\right\}^{\lambda (n)}}$

تكون شبه عشوائية إذا تحققت الشروط التالية:

• توجد خوارزمية تعمل في وقت متعدد الحدود تقوم بحساب${\displaystyle f_{s}(x)}$مع أي${\displaystyle s}$و${\displaystyle x}$.
• يترك${\displaystyle F_{n}}$توزيع الدوال${\displaystyle f_{s}}$أين${\displaystyle s}$موزعة بشكل منتظم على${\displaystyle \{0,1\}^{n}}$ودع${\displaystyle RF_{n}}$يرمز إلى التوزيع المنتظم على مجموعة جميع الدوال من${\displaystyle \{0,1\}^{أنا(ن)}}$ل${\displaystyle \{0,1\}^{\lambda (n)}}$ثم نحتاج${\displaystyle F_{n}}$و${\displaystyle RF_{n}}$لا يمكن التمييز بينهما حسابيًا، حيث n هو معامل الأمان . أي أنه بالنسبة لأي خصم يمكنه الاستعلام من قاعدة بيانات دالة مأخوذة من أي منهما${\displaystyle F_{n}}$أو${\displaystyle RF_{n}}$إن ميزة قدرتها على التمييز بين أنواع العرافة التي تُعطى لها ضئيلة للغاية.${\displaystyle n}$[ ^{3 ]​}

في دالة شبه عشوائية غير واعية (OPRF)، تُخفى المعلومات عن طرفين مشاركين في دالة شبه عشوائية. ^{[ 4 ]} بمعنى آخر، إذا قامت أليس بتشفير قيمتها السرية، ثم أخفت التشفير الناتج لإنتاج الرسالة التي أرسلتها إلى بوب، وقام بوب بإضافة قيمته السرية وإعادة النتيجة إلى أليس التي كشفتها للحصول على الناتج النهائي، فلن يتمكن بوب من رؤية قيمة أليس السرية أو الناتج النهائي، ولن تتمكن أليس من رؤية مدخلات بوب السرية، لكنها سترى الناتج النهائي وهو دالة شبه عشوائية للمدخلين - دالة شبه عشوائية لسر أليس وسر بوب. ^{[ 5 ]} وهذا يُمكّن من تأمين معاملات المعلومات المشفرة الحساسة حتى بين أطراف غير موثوق بها.

يُستخدم OPRF في بعض تطبيقات اتفاقية المفاتيح المعتمدة على كلمة المرور . ^{[ 5 ]}

يتم استخدام OPRF في وظيفة مراقبة كلمات المرور في Microsoft Edge . ^{[ 6 ]}

يمكن استخدام PRFs من أجل: ^{[ 7 ]}

1. التجزئة المثالية الديناميكية ؛ حتى لو تمكن الخصم من تغيير توزيع المفاتيح اعتمادًا على القيم التي خصصتها دالة التجزئة للمفاتيح السابقة، فلن يتمكن الخصم من فرض حدوث تصادمات.
2. بناء مخططات مصادقة حتمية وخالية من الذاكرة ( تعتمد على رمز مصادقة الرسائل ) والتي يمكن إثبات أمانها ضد هجوم الرسائل المختارة.
3. توزيع أرقام تعريف غير قابلة للتزوير ، والتي يمكن التحقق منها محليًا بواسطة محطات تحتوي على مساحة تخزين صغيرة فقط.
4. بناء أنظمة تحديد الصديق والعدو .

• التبديل شبه العشوائي

• جولدرايش، أوديد (2001). أسس التشفير: الأدوات الأساسية . كامبريدج: مطبعة جامعة كامبريدج. ISBN 978-0-511-54689-1.
• باس، رافائيل، دورة في علم التشفير (ملف PDF) ، تم الاطلاع عليه بتاريخ 22 ديسمبر 2015