💆🏿 🐸 ↕️ الحوادث ليست عشوائية: من هي عائلات الوظائف العشوائية الزائفة (PRFs) 🕘 ⏫ 🛌🏽

في عام 1984 ، قام Goldreich و Goldwasser و Micali بإضفاء الطابع الرسمي على مفهوم الوظائف العشوائية الزائفة واقترحوا تطبيق PRF على أساس المولد العشوائي الزائف المضاعف (PRG). منذ ذلك الحين ، أثبتت الوظائف العشوائية الزائفة أنها تجريد مهم للغاية وجد تطبيقات في مجالات مختلفة ، مثل مصادقة الرسائل وإثبات النظرية. سأشرح في هذا المقال:

ما هي وظائف عشوائية (RF)
ما هي وظائف شبه عشوائية (PRF)
من هي عائلاتك هذه؟
PRF مقابل. PRG
ما علاقة شفرات الكتلة بها؟

العشوائية

بالفعل من الاسم يتضح أن الوظيفة شبه العشوائية هي شيء "يشبه" وظيفة عشوائية. حسنًا ، ما هي وظيفة عشوائية في حالتنا؟ بادئ ذي بدء ، سنقصر نطاق اعتبارنا على الدوال التي تعرض سلسلة من الأصفار والآحاد بطول سلسلة من الأصفار والآحاد بنفس الطول ، أي

$\ underbrace {1110 ... 0010} _ {n} \ rightarrow \ underbrace {0100 ... 0011} _ {n} \ Leftrightarrow \ {0،1 \} ^ n \ rightarrow \ {0،1 \} ^ n$

يمكن حذف هذا ، بشكل عام ، ويمكننا التفكير في تعيينات سلاسل بطول واحد إلى سلاسل بطول آخر ، ولكن في هذه الحالة يتعين على المرء الانتباه إلى الاختلافات في الأبعاد. بعد ذلك ، نقدم مجموعة من جميع الوظائف التي تؤدي التعيين $\ {0،1 \} ^ n \ rightarrow \ {0،1 \} ^ n$ والإشارة إليها $\ text {Func} _n$ .

ضع في اعتبارك العناصر الأساسية لهذه المجموعة. من الواضح $| {\ text {Func} _n} | = 2 ^ {n2 ^ n}$ .

$\ نص {إجمالي طول السلاسل المميزة} n \ مسافة - \ مسافة 2 ^ n.$ $\ text {To store} 2 ^ n \ text {الأسطر التي تحتاجها} n2 ^ n \ text {bits.}$ $\ text {هذه} n2 ^ {n} \ text {بتات وسوف تعين التعيين المطلوب} 2 ^ n \ text {lines.}$ $\ text {وسيكون هناك إجمالي مثل هذه التعيينات} 2 ^ {n2 ^ n}.$

. – $\ text {Func} _n$ . , 2 ^ ن - 2 ^ ن . ,