وظيفة أحادية الاتجاه

الموسوعة الحرة
مشكلة لم تُحل في علوم الحاسوب
هل توجد دوال أحادية الاتجاه؟
المزيد من المشاكل التي لم يتم حلها في علوم الحاسوب

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

لا يزال وجود هذه الدوال أحادية الاتجاه فرضية مفتوحة . من شأن وجودها أن يثبت أن فئتي التعقيد P و NP غير متساويتين ، وبالتالي حل أهم مسألة عالقة في علم الحاسوب النظري. [ 1 ] : مثال 2.2، صفحة 70. أما العكس فليس معروفًا، أي أن وجود برهان على أن P  ≠  NP لا يستلزم بالضرورة وجود دوال أحادية الاتجاه. [ 2 ]

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

التعريف النظري

تكون الدالة f  : {0,  1} * → {0,  1} * أحادية الاتجاه إذا أمكن حسابها بواسطة خوارزمية ذات زمن متعدد الحدود، ولكن أي خوارزمية عشوائية ذات زمن متعدد الحدود تكون أحادية الاتجاه.F{\displaystyle F}إن محاولات حساب المعكوس الزائف للدالة f تنجح باحتمالية ضئيلة . (يشير الرمز * إلى أي عدد من التكرارات، انظر نجمة كلين ). أي أن هذا ينطبق على جميع الخوارزميات العشوائية.F{\displaystyle F}، جميع الأعداد الصحيحة الموجبة c وجميع قيم n الكبيرة بما فيه الكفاية = طول( x )،

برو[و(F(و(x)))=و(x)]<ن-ج،{\displaystyle \Pr[f(F(f(x)))=f(x)]<n^{-c},}

حيث يكون الاحتمال متعلقًا باختيار x من التوزيع المنتظم المنفصل على {0،  1} n ، وعشوائية F{\displaystyle F}[ 3 ]​

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

لا يكفي أن تكون الدالة "غير أحادية الاتجاه" (أي ليست دالة "فقدان" للبيانات) لتكون دالة أحادية الاتجاه. على وجه الخصوص، الدالة التي تُخرج سلسلة من n أصفار عند إدخال أي قيمة طولها n ليست دالة أحادية الاتجاه ، لأنه من السهل إيجاد قيمة إدخال تُنتج نفس المخرج. بتعبير أدق: بالنسبة لدالة تُخرج ببساطة سلسلة من الأصفار، فإن خوارزمية F التي تُخرج أي سلسلة طولها n عند إدخال f ( x ) ستجد صورة عكسية مناسبة للمخرج، حتى لو لم تكن هي قيمة الإدخال التي استُخدمت في الأصل لإيجاد سلسلة المخرج.

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

الدالة أحادية الاتجاه ذات الباب الخلفي، أو تبديل الباب الخلفي، هي نوع خاص من الدوال أحادية الاتجاه. يصعب عكس هذه الدالة إلا بمعرفة معلومة سرية تُسمى الباب الخلفي .

دالة التجزئة الخالية من التصادم f هي دالة أحادية الاتجاه ومقاومة للتصادم أيضًا ؛ أي أنه لا يمكن لأي خوارزمية عشوائية ذات وقت متعدد الحدود أن تجد تصادمًا - قيمًا مختلفة x و y بحيث f ( x ) = f ( y ) - باحتمالية غير مهملة. [ 4 ]

المسند الأساسي لدالة أحادية الاتجاه f هو مسند (أي بت واحد) b بحيث يكون من السهل حساب b(x) بمعلومية x ولكن من الصعب حسابه بمعلومية f(x) فقط .

الآثار النظرية للدوال أحادية الاتجاه

إذا كانت f دالة أحادية الاتجاه، فإن إيجاد معكوسها يُعدّ مسألةً يصعب حساب ناتجها (بحكم التعريف) ولكن يسهل التحقق منه (بمجرد حساب f عليها). وبالتالي، فإن وجود دالة أحادية الاتجاه يستلزم أن FP  ≠ FNP ، مما يستلزم بدوره أن P ≠ NP. مع ذلك، فإن كون P ≠ NP لا يستلزم بالضرورة وجود دوال أحادية الاتجاه.     

إن وجود دالة أحادية الاتجاه يستلزم وجود العديد من المفاهيم المفيدة الأخرى، بما في ذلك:

المرشحون للوظائف أحادية الاتجاه

فيما يلي بعض الدوال المرشحة لتكون دوال أحادية الاتجاه (حتى أبريل 2009). من الواضح أنه ليس من المعروف ما إذا كانت هذه الدوال أحادية الاتجاه بالفعل؛ ولكن الأبحاث المكثفة لم تسفر حتى الآن عن خوارزمية عكس فعالة لأي منها.

الضرب والتحليل إلى عوامل

تأخذ الدالة f عددين أوليين p و q في النظام الثنائي كمدخلات، وتعيد حاصل ضربهما. يمكن حساب هذه الدالة بسهولة في زمن قدره O ( b² ) ، حيث b هو العدد الإجمالي لبتات المدخلات. يتطلب عكس هذه الدالة إيجاد عوامل عدد صحيح معطى N. تعمل أفضل خوارزميات التحليل المعروفة فييا(خبرة⁡649ب(سجل⁡ب)23){\displaystyle O\left(\exp {\sqrt[{3}]{{\frac {64}{9}}b(\log b)^{2}}}\right)}الوقت ، حيث b هو عدد البتات اللازمة لتمثيل N.

يمكن تعميم هذه الدالة بالسماح لـ p و q بالتنقل ضمن مجموعة مناسبة من الأعداد شبه الأولية . لاحظ أن f ليست دالة أحادية الاتجاه للأعداد الصحيحة p و q المختارة عشوائيًا والتي يكون فيها p و q أكبر من 1 ، لأن حاصل الضرب سيكون له عامل 2 باحتمالية 3/4 (لأن احتمالية أن يكون p عددًا فرديًا هي 1/2، وكذلك بالنسبة لـ q ، لذا إذا تم اختيارهما بشكل مستقل، فإن احتمالية أن يكون كلاهما فرديًا هي 1/4؛ وبالتالي فإن احتمالية أن يكون p أو q عددًا زوجيًا هي 1 - 1/4 = 3/4 ).

دالة رابين (التربيع المعياري)

دالة رابين ، [ 1 ] : 57 أو التربيع moduloشمال=صq{\displaystyle N=pq}يُعتقد أن ، حيث p و q عددان أوليان، عبارة عن مجموعة من الدوال أحادية الاتجاه. نكتب

رابينشمال⁡(x)≜x2مودشمال{\displaystyle \operatorname {Rabin} _{N}(x)\triangleq x^{2}{\bmod {N}}}

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

الدوال الأسية واللوغاريتمية المنفصلة

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

لتكن G زمرة أبيلية منتهية ذات عدد عناصر n . نرمز إلى عملية الزمرة بالضرب. لنعتبر عنصرًا أوليًا α ∈ G وعنصرًا آخر β ∈ G. تتمثل مسألة اللوغاريتم المنفصل في إيجاد العدد الصحيح الموجب k ، حيث 1 ≤ k ≤ n ، بحيث:

αك=α⋅α⋅...⋅α⏟كتأنامهـs=β{\displaystyle \alpha ^{k}=\underbrace {\alpha \cdot \alpha \cdot \ldots \cdot \alpha } _{k\;\mathrm {times} }=\beta }

يُطلق على العدد الصحيح k الذي يحل المعادلة α k = β اسم اللوغاريتم المتقطع لـ β للأساس α . ويُكتب k = log α β .

الخيارات الشائعة للمجموعة G في التشفير اللوغاريتمي المنفصل هي المجموعات الدورية ( Z p ) × (على سبيل المثال تشفير ElGamal ، وتبادل مفاتيح Diffie-Hellman ، وخوارزمية التوقيع الرقمي ) والمجموعات الفرعية الدورية للمنحنيات الإهليلجية على الحقول المنتهية ( انظر تشفير المنحنيات الإهليلجية ).

المنحنى الإهليلجي هو مجموعة من أزواج عناصر حقل تحقق المعادلة y² = x³ + ax + b . تشكل عناصر المنحنى زمرةً تحت عملية تُسمى "جمع النقاط " (وهي تختلف عن عملية جمع الحقل). يُعرَّف ضرب النقطة P في عدد صحيح k ( أي ، تأثير زمرة الجمع للأعداد الصحيحة) بأنه جمع النقطة مع نفسها بشكل متكرر. إذا عُلم كل من k و P ، فمن السهل حساب R = kP ، أما إذا عُلم كل من R و P فقط ، فيُفترض صعوبة حساب k .

دوال التجزئة الآمنة تشفيرياً

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

مرشحون آخرون

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

وظيفة أحادية الاتجاه عالمية

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

توجد أيضًا دالة أحادية الاتجاه إذا كان تعقيد كولموغوروف المحدود زمنيًا متعدد الحدود صعبًا نوعًا ما في المتوسط. وبما أن وجود الدوال أحادية الاتجاه يستلزم أن تعقيد كولموغوروف المحدود زمنيًا متعدد الحدود صعب نوعًا ما في المتوسط، فإن هذه الدالة تُعدّ دالة أحادية الاتجاه شاملة. [ 6 ]

انظر أيضاً

مراجع

  1. 1 2 أوديد غولدريتش (2001). أسس التشفير: المجلد 1، الأدوات الأساسية ( مسودة متاحة على موقع المؤلف). مطبعة جامعة كامبريدج. ISBN 0-521-79172-3انظر أيضًا wisdom.weizmann.ac.il .
  2. ↑ غولدواسير، إس. وبيلار ، إم. "ملاحظات محاضرات في علم التشفير" مؤرشفة في 21-04-2012 في آلة Wayback . دورة صيفية في علم التشفير، معهد ماساتشوستس للتكنولوجيا، 1996-2001.
  3. ↑ يرى العديد من المؤلفين أن هذا التعريف هو دالة أحادية الاتجاه قوية. ويمكن تعريف دالة أحادية الاتجاه ضعيفة بشكل مشابه، باستثناء أن احتمال كل خصمF{\displaystyle F}يُلاحظ عدم القدرة على عكس الدالة f . مع ذلك، يمكن بناء دوال أحادية الاتجاه قوية بالاعتماد على دوال ضعيفة. وبشكل عام، فإن النسختين القوية والضعيفة من الدوال أحادية الاتجاه متكافئتان نظريًا. انظر كتاب غولدرايش "أسس التشفير"، المجلد  الأول، الفصل  2.1-2.3.
  4. ↑ راسل، أ. (1995). "الشروط الضرورية والكافية للتجزئة الخالية من التصادم". مجلة علم التشفير . 8 (2): 87-99 . doi : 10.1007/BF00190757 . S2CID 26046704 . 
  5. ↑ ليفين، ليونيد أ. (يناير 2003). "قصة الدوال أحادية الاتجاه". مشاكل نقل المعلومات . 39 (39): 92-103 . arXiv : cs.CR/0012023 . doi : 10.1023/A:1023634616182 .
  6. ↑ ليو، ياني؛ باس، رافائيل (24-09-2020). "حول الدوال أحادية الاتجاه وتعقيد كولموغوروف". arXiv : 2009.11514 [ cs.CC ].

للمزيد من القراءة